# Finite Group Permutation to Presentation

### Example D3

 In order to get some intuition lets look at the dihedral group of dimension 3. This has 2 generators: r - for rotate (modulo 3) m - for mirror.

Then we get the following presentation and permutation:

presentation permutation
<r,m | rrr, mm, rmrm > r := (1,2,3) m := (1,2)

We can see how these two views interact by seeing what the rules do to permutations:

rrr mm rmrm

As we can see each rule sends each point back to itself. This is to be expected because a rule corresponds to a loop in the Cayley table above.

So how do we derive a presentation from the permutation? We already gan get the generators from the existing permgrps.spad code. So the problem is to work out the rules.

My first thought is that each rule corresponds to the loops in the Cayley graph (above). A brute force way to get all the loops is to start at 'e' and keep applying generators in a tree structure until we get back to 'e', the each of these paths from 'e' back to 'e' is a loop.

### Examples

 ```(1) -> )expose PermutationGroupExamples PermutationGroupExamples is now explicitly exposed in frame frame1 (1) -> d3 := dihedralGroup(3)\$PermutationGroupExamples (1) <(1 2 3),(1 3)> Type: PermutationGroup(Integer) (2) -> initializeGroupForWordProblem(d3) Type: Void (3) -> sg := strongGenerators(d3) (3) [(2 3),(1 3)] Type: List(Permutation(Integer)) (4) -> b := base(d3) (4) [1,2] Type: List(Integer)```

 ```From: Martin Baker Subject: [PATCH] add coerce from PermutationGroup to GroupPresentation Organization: axiom Date: Mon, 14 Nov 2016 18:08:13 +0000 Patch is here: https://github.com/martinbaker/fricasAlgTop/blob/master/permgrps1.patch File is here: https://github.com/martinbaker/fricasAlgTop/blob/master/permgrps.spad It is used like this: permgp := dihedralGroup(3)\$PermutationGroupExamples (1) <(1 2 3),(1 3)> Type: PermutationGroup(Integer) permgp::GroupPresentation (2) Type: GroupPresentation As discussed before, improvements to simplification in GroupPresentation would be good but that is not part of this code. Martin B```
 ```Subject: Re: [fricas-devel] [PATCH] add coerce from PermutationGroup to GroupPresentation From: Waldek Hebisch To: fricas-devel@googlegroups.com Date: Mon, 23 Jan 2017 06:37:51 +0100 (CET) Martin Baker wrote: > > Patch is here: > https://github.com/martinbaker/fricasAlgTop/blob/master/permgrps1.patch I have tried it now. AFAICS it is _extremally_ inefficient: coerce(symmetricGroup(4))@GroupPresentation crashes due to running out of memory (tested on sbcl with default 1GB limit), coerce(dihedralGroup(7))@GroupPresentation works but takes a lot of time and produces large presentation. Very naive and inefficient way to produce group presentation is to first produce a word for each group element and then for each pair (g,w) where g i a generator and w is an element to produce relation gw = z where z is word representing gw (since we have word for each element we can find it via lookup). Clearly, denoting by n number of generators and by N number of group elements this methods needs nN multiplications and will produce nN relations. This should work well when nN is of order several thousend. AFAICS you try something similar, but there is something wrong with your method because it cannot handle _very_ small groups. Little remark: you use both generators and inverses. This may give shorter words, so there may be useful for representing group elements. However relations obtained from inverses are redundant: inverse a power of generator so once we have relations for gw relations for inverses are a conseqence. The main routine in PERMGRP computes base and strong generating set for the group. Effectively, this means that we have sequence of generators g_ik and groups G_i such that G_i = and G_0 = G and G_i for i>0 is stabilizer of point b_i (set of b_i-s is called a base and g_ik are called strong generators). In terms of stong generators one can recursively build presentation. More precisely, given presentation for G_{i+i} we can build presentation for G_i in the following way. Let S_i be G_ib_i (that is G_i-orbit of b_i). For each s in S w fix a word w_s in terms of strong generators such that w_sb_i = s. Each element of G_i can be written as w_sz with z in G_{i+1}. Namely, if x is an arbitrary element of G_i, and s = xb_i then ((w_s)^{-1}x)(b_i) = b_i, so z = (w_s)^{-1}x in G_{i+1} and x = w_sg. We call w_sz canonical word for x (more precisely we should recursively find canonical word for z in G_{i+1}). Now, relations for G_i are relations for G_{i+1} plus new relations of form gw_s = w_tz where g runs over (stong) generators of G_i and w_tz is canonical word corresponding to gw_s. This is presentation for G_i because: - for each element of G_i we have a canonical word - each word is eqivalent to a canonical word (proved by induction: by our choice of relations gw_sz_1 is equivalent to w_tz_2z_1 and by assumption about G_{i+1} z_2z_1 is equivalent to canonical word z_3 - action of free group F_i on strong generators of G_i acting on canonical words via multiplication from left and reduction to canonical form agrees with natural action of F_i on G_i The first two point means that we can identify as a set resulting finitely presented group with G_i. The third one means that group actions coincide. Once we have presentation in terms of strong generators we can produce also presentation in terms of original generators. The trick is that first we express each strong generator in terms of original generators. Then we rewrite each relation using fixed correspondence from the first step. Finally for each original generator h and each strong generator g we add relation hg = z where z is word representing hg in terms of strong generators rewritten in terms of original generators using fixed relation from first step. As before, for each element of G we get a canonical word. Again we can rewrite any word in terms of original generators to a canonical word and we can prove that multiplication on canonical words agrees with multiplication in G. Obtained presentations are likely to be quite large, but AFAICS size of presentation will be similar to cost of producing strong generating set. So we should be able to handle groups having more than 10^20 elements, which is clearly beyond what naive method could do. -- Waldek Hebisch```

 ```From: Waldek Hebisch Subject: Re: [fricas-devel] [PATCH] add coerce from PermutationGroup to GroupPresentation To: fricas-devel@googlegroups.com Date: Mon, 23 Jan 2017 17:58:32 +0100 (CET) A little example of using strong generators: (1) -> s5 := symmetricGroup(5)\$PGE (1) <(1 2 3 4 5),(1 2)> Type: PermutationGroup(Integer) (2) -> initializeGroupForWordProblem(s5) Type: Void (3) -> strongGenerators(s5) (3) [(4 5),(3 4 5),(2 5 3),(1 2)] Type: List(Permutation(Integer)) (4) -> base(s5) (4) [1,2,3,4] Type: List(Integer) So we have: G = G_0 = <(1,2), G_1>, G_1 = <(2,5,3), G_2>, G_2 = <(3,4,5), G_3>, G_3 = <(4,5)>. Writing a = (1,2), b = (2,5,3), c = (3,4,5), d = (4,5) we get the following relations: for G_3: base point 4, orbit is {4, 5}, single generator d and single relation d^2 for G_2: base point is 3, orbit is {3, 4, 5}, single generator c produces the orbit: 3 = c^0(3), 4 = c(3), 5 = c^2(3), c^3(3) = 3 and we get relation c^3 dc(3) = 5 so dc = c^2d. We need no extra relation for product of d and c^2 as this follows from relation for dc: dc^2 = (dc)c = c^2dc = c^2c^2d = cd for G_1: base point 2, orbit is {2, 3, 4, 5} we need two generators to produce the orbit: b(2) = 5, b^2(2) = 3, db(2) = 4. We get relation b^3, cb(2) = 3 so cb = b^2dcd, cb^2(2) = 4 so cb^2 = dbdc, since d^2 = e we have d^2b = b and need no extra relation for product of d and db, cdb(2) = 5 so cdb = bd, bdb(2) = 4 so bdb = dbc for G_0: base point is 1, orbit is {1, 2, 3, 4, 5}, we need 3 generators to get orbit: a(1) = 2, ba(1) = 5, b^2a(1) = 3, dba(1) = 4. We get relation a^2, aba(1) = 5 so aba = ba*dcb, ab^2a(1) = 3, so ab^2a = b^2acdbc, adba(1) = 4 so adba = dba*dcb, for product of b and a we need no extra relation as ba is already canonical, similarly for product of b and ba, for product of b and b^2a we need no extra relation because b^3a = a by relation b^3, bdba(1) = 4 so bdba = dbac. In similar way we get relations ca = ac, cba = b^2adcd, cb^2a = dbadc, cdba = bad, da = ad, db^2a = b^2acd, (for dba we need no extra relation because it is canonical, for d(dba) from d^2 = e we get ddba = ba). Together we get generators a, b, c, d and relations: d^2 = e, c^3 = e, dc = c^2d, b^3 = e, cb = b^2dcd, cb^2 = dbdc, bdb = dbc, a^2 = e, aba = badcb, ab^2a = b^2acdbc, adba = dbadcb, bdba = dbac, ca = ac, cba = b^2adcd, cb^2a = dbadc, cdba = bad, da = ad, db^2a = b^2acd. Note: I used wordInStrongGenerators as a helper, but part of calculation is by hand so there may be mistakes. However, it should be clear that method scales to much larger groups and already in this case presentation is smaller than obtained by naive algorithm. I skip expressing relations in terms of original generators, but for this we would get 8 extra relations so this still will have smaller number of relations than naive algorithm gives (admitedly, the relations would be quite long). -- Waldek Hebisch ```

 ```From: Martin Baker Subject: Re: [fricas-devel] [PATCH] add coerce from PermutationGroup to GroupPresentation To: fricas-devel@googlegroups.com Date: Mon, 23 Jan 2017 16:59:01 +0000 On 01/23/2017 05:37 AM, Waldek Hebisch wrote: > Martin Baker wrote: >> Patch is here: >> https://github.com/martinbaker/fricasAlgTop/blob/master/permgrps1.patch > I have tried it now. AFAICS it is _extremally_ inefficient: > coerce(symmetricGroup(4))@GroupPresentation crashes due to > running out of memory (tested on sbcl with default 1GB limit), > coerce(dihedralGroup(7))@GroupPresentation works but takes > a lot of time and produces large presentation. Waldek, Thank you for looking at this. I did not find a published algorithm for this so I just worked out a simple algorithm myself, I did not think much about efficiency I was just happy to hit on a method that worked. The main issue is finding the relations. It seems to me that each relation corresponds to a loop in the Cayley graph. So I just wrote an algorithm that found all the relations (loops) by doing a tree search of the Cayley graph. Obviously this finds a lot of redundant rules (loops). Am I correct in thinking that the algorithm that you are proposing is more efficient because it uses a stabilizer chain (sequence of subgroups, each containing the next and each stabilizing one more point). So when we work out the loops in the subgroup we implicitly encode information about the loops in the cosets so we consider less loops? Martin B```

 ```Subject: Re: [fricas-devel] [PATCH] add coerce from PermutationGroup to GroupPresentation To: fricas-devel@googlegroups.com From: Martin Baker Date: Mon, 23 Jan 2017 17:13:06 +0000 On 01/23/2017 04:58 PM, Waldek Hebisch wrote: > Note: I used wordInStrongGenerators as a helper I find it hard to understand the functions in PermutationGroup. Partly because I cant find any documentation (I searched the usual places but its easy to miss things) and its hard to follow the code because Rep is so complicated. For example, how does wordInGenerators work? I sort of expected that the generators would be represented by a single element in the word. So I expected that the following would give [[1],[2]]: dg3 := dihedralGroup(3) (1) <(1 2 3),(1 3)> Type: PermutationGroup(Integer) g := generators(dg3) (2) [(1 2 3),(1 3)] Type: List(Permutation(Integer)) [wordInGenerators(x,dg3) for x in g] (3) [[1,2,2],[2]] Type: List(List(NonNegativeInteger)) I realise this is the same as [[1],[2]] because 2 is self inverse but it would be good if it could do some simplification. wordsForStrongGenerators is different from wordInGenerators in that it does not seem to use indexes. sg := strongGenerators(dg3) (4) [(2 3),(1 3)] Type: List(Permutation(Integer)) w := wordsForStrongGenerators(dg3) (5) [[1,2],[2]] Type: List(List(NonNegativeInteger)) Now that I have your example hopefully I will now be able to understand it better. Thanks, Martin```

 ```Subject: Re: [fricas-devel] [PATCH] add coerce from PermutationGroup to GroupPresentation From: Waldek Hebisch To: fricas-devel@googlegroups.com Date: Mon, 23 Jan 2017 18:13:40 +0100 (CET) Martin Baker wrote: > > On 01/23/2017 05:37 AM, Waldek Hebisch wrote: > > Martin Baker wrote: > >> Patch is here: > >> https://github.com/martinbaker/fricasAlgTop/blob/master/permgrps1.patch > > I have tried it now. AFAICS it is _extremally_ inefficient: > > coerce(symmetricGroup(4))@GroupPresentation crashes due to > > running out of memory (tested on sbcl with default 1GB limit), > > coerce(dihedralGroup(7))@GroupPresentation works but takes > > a lot of time and produces large presentation. > > Waldek, > > Thank you for looking at this. I did not find a published algorithm for > this so I just worked out a simple algorithm myself, I did not think > much about efficiency I was just happy to hit on a method that worked. > > The main issue is finding the relations. It seems to me that each > relation corresponds to a loop in the Cayley graph. Yes. > So I just wrote an algorithm that found all the relations (loops) by > doing a tree search of the Cayley graph. Obviously this finds a lot of > redundant rules (loops). > > Am I correct in thinking that the algorithm that you are proposing is > more efficient because it uses a stabilizer chain (sequence of > subgroups, each containing the next and each stabilizing one more > point). So when we work out the loops in the subgroup we implicitly > encode information about the loops in the cosets so we consider less loops? Yes. Within coset we get a lot of implied relations (loops). We only need to add a single loop for each pair (generator, coset representative). In fact, for some pairs (generator, coset representative) we need no relation as in example from another message. -- Waldek Hebisch```

 ```Subject: Re: [fricas-devel] [PATCH] add coerce from PermutationGroup to GroupPresentation From: Waldek Hebisch To: fricas-devel@googlegroups.com Date: Mon, 23 Jan 2017 18:22:33 +0100 (CET) Martin Baker wrote: > > On 01/23/2017 04:58 PM, Waldek Hebisch wrote: > > Note: I used wordInStrongGenerators as a helper > > I find it hard to understand the functions in PermutationGroup. Partly > because I cant find any documentation (I searched the usual places but > its easy to miss things) and its hard to follow the code because Rep is > so complicated. > > For example, how does wordInGenerators work? It first writes word in terms of strong generators and then rewrites strong generators in terms of generators. > I sort of expected that the > generators would be represented by a single element in the word. So I > expected that the following would give [[1],[2]]: > > dg3 := dihedralGroup(3) > > (1) <(1 2 3),(1 3)> > Type: PermutationGroup(Integer) > g := generators(dg3) > > (2) [(1 2 3),(1 3)] > Type: List(Permutation(Integer)) > [wordInGenerators(x,dg3) for x in g] > > (3) [[1,2,2],[2]] > Type: List(List(NonNegativeInteger)) > > I realise this is the same as [[1],[2]] because 2 is self inverse but it > would be good if it could do some simplification. I would have to check if there are some simplifications. But basically, there is no efficient algorithm to directly work with original generators, so all is done in terms of strong generators and (if requested) rewritten later. > wordsForStrongGenerators is different from wordInGenerators in that it > does not seem to use indexes. > It uses indexes. Note that 'wordsForStrongGenerators' and 'wordInStrongGenerators' are different functions. -- Waldek Hebisch```