Computing nilpotent quotients in finitely presented Lie rings
A nilpotent quotient algorithm for finitely presented Lie rings over \textbfZ (and \textbfQ) is described. The paper studies the graded and non-graded cases separately. The algorithm computes the so-called nilpotent presentation for a finitely presented, nilpotent Lie ring. A nilpotent presentation...
Main Author: | |
---|---|
Format: | Article |
Language: | English |
Published: |
Discrete Mathematics & Theoretical Computer Science
1997-01-01
|
Series: | Discrete Mathematics & Theoretical Computer Science |
Subjects: | |
Online Access: | https://dmtcs.episciences.org/234/pdf |
_version_ | 1797270192039919616 |
---|---|
author | Csaba Schneider |
author_facet | Csaba Schneider |
author_sort | Csaba Schneider |
collection | DOAJ |
description | A nilpotent quotient algorithm for finitely presented Lie rings over \textbfZ (and \textbfQ) is described. The paper studies the graded and non-graded cases separately. The algorithm computes the so-called nilpotent presentation for a finitely presented, nilpotent Lie ring. A nilpotent presentation consists of generators for the abelian group and the products expressed as linear combinations for pairs formed by generators. Using that presentation the word problem is decidable in L. Provided that the Lie ring L is graded, it is possible to determine the canonical presentation for a lower central factor of L. Complexity is studied and it is shown that optimising the presentation is NP-hard. Computational details are provided with examples, timing and some structure theorems obtained from computations. Implementation in C and GAP interface are available. |
first_indexed | 2024-04-25T02:00:21Z |
format | Article |
id | doaj.art-2776f56dbbc846bea3e7fbcff0e98f6d |
institution | Directory Open Access Journal |
issn | 1365-8050 |
language | English |
last_indexed | 2024-04-25T02:00:21Z |
publishDate | 1997-01-01 |
publisher | Discrete Mathematics & Theoretical Computer Science |
record_format | Article |
series | Discrete Mathematics & Theoretical Computer Science |
spelling | doaj.art-2776f56dbbc846bea3e7fbcff0e98f6d2024-03-07T14:56:02ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80501997-01-01Vol. 110.46298/dmtcs.234234Computing nilpotent quotients in finitely presented Lie ringsCsaba Schneider0School of Mathematical Sciences [Canberra]A nilpotent quotient algorithm for finitely presented Lie rings over \textbfZ (and \textbfQ) is described. The paper studies the graded and non-graded cases separately. The algorithm computes the so-called nilpotent presentation for a finitely presented, nilpotent Lie ring. A nilpotent presentation consists of generators for the abelian group and the products expressed as linear combinations for pairs formed by generators. Using that presentation the word problem is decidable in L. Provided that the Lie ring L is graded, it is possible to determine the canonical presentation for a lower central factor of L. Complexity is studied and it is shown that optimising the presentation is NP-hard. Computational details are provided with examples, timing and some structure theorems obtained from computations. Implementation in C and GAP interface are available.https://dmtcs.episciences.org/234/pdfnilpotent presentationlie ringsnilpotent lie ringsfinitely presented lie rings[info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
spellingShingle | Csaba Schneider Computing nilpotent quotients in finitely presented Lie rings Discrete Mathematics & Theoretical Computer Science nilpotent presentation lie rings nilpotent lie rings finitely presented lie rings [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
title | Computing nilpotent quotients in finitely presented Lie rings |
title_full | Computing nilpotent quotients in finitely presented Lie rings |
title_fullStr | Computing nilpotent quotients in finitely presented Lie rings |
title_full_unstemmed | Computing nilpotent quotients in finitely presented Lie rings |
title_short | Computing nilpotent quotients in finitely presented Lie rings |
title_sort | computing nilpotent quotients in finitely presented lie rings |
topic | nilpotent presentation lie rings nilpotent lie rings finitely presented lie rings [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
url | https://dmtcs.episciences.org/234/pdf |
work_keys_str_mv | AT csabaschneider computingnilpotentquotientsinfinitelypresentedlierings |