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
--
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 [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
