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
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to fricas-devel+unsubscr...@googlegroups.com.
To post to this group, send email to fricas-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
