ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 07 Sep 2019 13:42:37 +0200Finitely presented group simplificationhttps://ask.sagemath.org/question/47636/finitely-presented-group-simplification/Hi! I have a bunch of finitely presented groups, with many generators and relations. I know that all of these are in fact cyclic groups, but many times using the "simplified()" function, I get a simpler presentation with 2 generators, rather than only one. The following is one example:
G.<x0,x5> = FreeGroup()
H =G/[(x5^-1*x0)^2*x5^-3, (x0^-1*x5^-1)^2*x0^-2*x5*x0^-1]
H is in fact just Z/27Z. Is there another way to simplify these presentations, in order to get a minimal one?
The problem here is that I do not only need to identify the specific group, but also to recover the image of the previous generators in the simplified one (as done by the simplification_isomorphism() function).Wed, 28 Aug 2019 12:25:45 +0200https://ask.sagemath.org/question/47636/finitely-presented-group-simplification/Answer by tmonteil for <p>Hi! I have a bunch of finitely presented groups, with many generators and relations. I know that all of these are in fact cyclic groups, but many times using the "simplified()" function, I get a simpler presentation with 2 generators, rather than only one. The following is one example:</p>
<pre><code> G.<x0,x5> = FreeGroup()
H =G/[(x5^-1*x0)^2*x5^-3, (x0^-1*x5^-1)^2*x0^-2*x5*x0^-1]
</code></pre>
<p>H is in fact just Z/27Z. Is there another way to simplify these presentations, in order to get a minimal one?
The problem here is that I do not only need to identify the specific group, but also to recover the image of the previous generators in the simplified one (as done by the simplification_isomorphism() function).</p>
https://ask.sagemath.org/question/47636/finitely-presented-group-simplification/?answer=47637#post-id-47637Note that in your example i have:
sage: H.cardinality()
216
Do you know by other means that H is isomorphic to Z/27Z ? Something might be buggy in Sage.Wed, 28 Aug 2019 13:15:56 +0200https://ask.sagemath.org/question/47636/finitely-presented-group-simplification/?answer=47637#post-id-47637Comment by danieleC for <p>Note that in your example i have: </p>
<pre><code>sage: H.cardinality()
216
</code></pre>
<p>Do you know by other means that H is isomorphic to Z/27Z ? Something might be buggy in Sage.</p>
https://ask.sagemath.org/question/47636/finitely-presented-group-simplification/?comment=47648#post-id-47648It might be that the previous example I gave was wrong (still unsure), but the following one has 17 elements (so, it's necessarily Z/17Z), but still it can't seem to be reducible.
`<x0, x5 | x5*x0*x5*x0^-1*x5^-1*x0^-1, x0^-1*x5^-1*x0^-1*(x0^-1*x5^-3)^3*x0^-1*x5^-1>`Wed, 28 Aug 2019 17:26:11 +0200https://ask.sagemath.org/question/47636/finitely-presented-group-simplification/?comment=47648#post-id-47648Answer by rburing for <p>Hi! I have a bunch of finitely presented groups, with many generators and relations. I know that all of these are in fact cyclic groups, but many times using the "simplified()" function, I get a simpler presentation with 2 generators, rather than only one. The following is one example:</p>
<pre><code> G.<x0,x5> = FreeGroup()
H =G/[(x5^-1*x0)^2*x5^-3, (x0^-1*x5^-1)^2*x0^-2*x5*x0^-1]
</code></pre>
<p>H is in fact just Z/27Z. Is there another way to simplify these presentations, in order to get a minimal one?
The problem here is that I do not only need to identify the specific group, but also to recover the image of the previous generators in the simplified one (as done by the simplification_isomorphism() function).</p>
https://ask.sagemath.org/question/47636/finitely-presented-group-simplification/?answer=47652#post-id-47652The first example you gave is not cyclic, as seen e.g. by
sage: H.structure_description()
'Q8 : C27'
The meaning of this output can be found in [GAP's manual for StructureDescription](https://www.gap-system.org/Manuals/doc/ref/chap39.html#X87BF1B887C91CA2E).
The second example (in your comment to tmonteil) is cyclic:
sage: G.<x0,x5> = FreeGroup()
sage: H = G/[x5*x0*x5*x0^-1*x5^-1*x0^-1, x0^-1*x5^-1*x0^-1*(x0^-1*x5^-3)^3*x0^-1*x5^-1]
sage: H.structure_description()
'C17'
In general, to find out if an element is a generator of a cyclic group you can take powers of it and see if you get the whole group. The difficulty here is that you need to put elements in a kind of normal form to compare them. Here you can do it with a confluent rewriting system:
sage: k = H.rewriting_system()
sage: k.make_confluent()
sage: H_reps = set([k.reduce(h) for h in H])
sage: next((h for h in H if set([k.reduce(h^m) for m in range(len(H))]) == H_reps), None)
x0
This shows `x0` is a generator; the relation is `x0^17 == 1`. (Note there is room for optimization of this code, e.g. in calculating the powers.)
I'm not a group theorist, but I would guess that for finite groups such a rewriting system always exists.
Note for cyclic groups of prime order, all non-identity elements are generators, and more generally in a cyclic group of order $n$, $\varphi(n)$ of the elements are generators.Wed, 28 Aug 2019 20:01:10 +0200https://ask.sagemath.org/question/47636/finitely-presented-group-simplification/?answer=47652#post-id-47652Comment by danieleC for <p>The first example you gave is not cyclic, as seen e.g. by</p>
<pre><code>sage: H.structure_description()
'Q8 : C27'
</code></pre>
<p>The meaning of this output can be found in <a href="https://www.gap-system.org/Manuals/doc/ref/chap39.html#X87BF1B887C91CA2E">GAP's manual for StructureDescription</a>.</p>
<p>The second example (in your comment to tmonteil) is cyclic:</p>
<pre><code>sage: G.<x0,x5> = FreeGroup()
sage: H = G/[x5*x0*x5*x0^-1*x5^-1*x0^-1, x0^-1*x5^-1*x0^-1*(x0^-1*x5^-3)^3*x0^-1*x5^-1]
sage: H.structure_description()
'C17'
</code></pre>
<p>In general, to find out if an element is a generator of a cyclic group you can take powers of it and see if you get the whole group. The difficulty here is that you need to put elements in a kind of normal form to compare them. Here you can do it with a confluent rewriting system:</p>
<pre><code>sage: k = H.rewriting_system()
sage: k.make_confluent()
sage: H_reps = set([k.reduce(h) for h in H])
sage: next((h for h in H if set([k.reduce(h^m) for m in range(len(H))]) == H_reps), None)
x0
</code></pre>
<p>This shows <code>x0</code> is a generator; the relation is <code>x0^17 == 1</code>. (Note there is room for optimization of this code, e.g. in calculating the powers.)</p>
<p>I'm not a group theorist, but I would guess that for finite groups such a rewriting system always exists.</p>
<p>Note for cyclic groups of prime order, all non-identity elements are generators, and more generally in a cyclic group of order $n$, $\varphi(n)$ of the elements are generators.</p>
https://ask.sagemath.org/question/47636/finitely-presented-group-simplification/?comment=47781#post-id-47781Sorry for the late reply, it seems like your answer works perfectly, thanks!!Sat, 07 Sep 2019 13:42:37 +0200https://ask.sagemath.org/question/47636/finitely-presented-group-simplification/?comment=47781#post-id-47781