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.
dihedral group

Then we get the following presentation and permutation:

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

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

rrr mm rmrm
rotaterotaterotate mirrormirror rotatemirrorrotatemirror

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.

presentation tree

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)
    <ha b |
         a*a*a, a*a*b*a*a*b, a*a*b*a*a*-b, a*b*a*b, a*b*a*-b, b*b, 
a*a*b*-a*b
     ,
         a*b*-a*-a*b, b*a*a*-b*-a, a*a*b*-a*-b, a*a*-b*a*a*-b, a*-b*a*-b
     >
                                         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 = <g_ik, G_{i+1}> 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


metadata block
see also:
Correspondence about this page

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

flag flag flag flag flag flag Fundamental Algorithms for Permutation Groups by Gregory Butler

 

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2017 Martin John Baker - All rights reserved - privacy policy.