> < ^ Date: Mon, 07 Feb 1994 16:17:00 +0100
> < ^ From: Volkmar Felsch <Volkmar.Felsch@Math.RWTH-Aachen.DE >
< ^ Subject: Re: a question about fp groups

Steve Fisk writes:

If I have a group with three generators

gap> g := FreeGroup(3,"g");

and the relations

gap> g.relators := [g.1*g.2*g.3];

and I simplify the presentation

gap> h := SimplifiedFpGroup(g);

then GAP tells me that there are two generators, and no relations.

gap> h.generators;
[ g.1, g.2 ]

gap> h.relators;
[ IdWord ]

Note that since version 3.3 the appropriate way to create f.p. groups
is as follows;

gap> f := FreeGroup(3,"f");
gap> g := f / [f1*f2*f3];

I have four questions:
1) How can I find an expression for the generator
g.3 in terms of g.1 and g.2? (In practice, there might be 20 relators;
this is just a simple example.)

2) How can I tell if an expression is the identity? e.g. g.1*g.2*g.3
(Well, this is the word problem, so can I control the time
that GAP devotes to this question - i.e. if more than 30
seconds, then return "unknown".)

There are no GAP functions for this purpose. In particular, the
SimplifiedFpGroup function does not trace the substitutions it performs.
Indeed, there is a possibility to force GAP to at least print out all
substitutions made by the SimplifiedFpGroup function: If you replace your
statement

        h := SimplifiedFpGroup(g);
by
        p := PresentationFpGroup( g, 2 );
        SimplifyPresentation( p );
        h := FpGroupPresentation( p );

thus increasing the default print level value to 2, then you will get
some additional output which, in particular, lists all substitutions
made. However, I would like to warn you that this output enforced by
print level 2 may be very voluminous.

So it might be a better idea, just to comment out the relevant checks of
the print level in the code of the Tietze transformation routines in
the GAP library "fptietze.g" instead of enlarging the print level. This
would have to affect the TzEliminate and TzSubstitute routines (in your
case the routine "TzEliminateGen1") and should not be too difficult as
all routines in question are written in the GAP language. Moreover,
instead of just printing some information by commenting out the
corresponding print level checks, you could save a list of whatever
data you like for later use.

3) Similarly, can I ask for Size(g) to return "unknown" if it has
to spend more than 30 seconds on it (or perhaps 10M of memory
instead of time).?

There is a global variable CosetTableFpGroupDefaultMaxLimit which is
set to a value of 64000 by GAP if you don't define it differently.
This global variable defines the maximal number of cosets to be defined
in an call of the ordinary CosetTableFpGroup function before it is
aborted. A similar variable for the AugmentedCosetTableMtc function
which is called by the Size function for f.p. groups has not yet been
introduced. We will introduce it in the next release.

4) I asked for the size of h, and got the following. Is this a bug
or a feature?

gap> g := FreeGroup(3,"g");
Group( g.1, g.2, g.3 )

gap> g.relators := [g.1*g.2*g.3];
[ g.1*g.2*g.3 ]

gap> h := SimplifiedFpGroup(g);
Group( g.1, g.2 )

gap> Size(h);
Error, Subword: illegal <from> value at
while LengthWord( rel ^ Subword( rel, 1, 1 ) ) < LengthWord( rel ) ... in
RelatorRepresentatives( G.relators ) called from
RelsSortedByStartGen( G, table ) called from
AugmentedCosetTableMtc( G, H, 1, "_x" ) called from
D.operations.Size( D ) called from
Size( h ) called from
main loop
brk>

Of course, you should not have got this error message. This is a bug,
and we will correct it properly in the next release. For the moment
you may fix it by the following change in the code of function
"FpGroupPresentation" in the GAP library file "fptietze.g".

Please replace the statements

numrels := tietze[TZ_NUMRELS];
grels := 0 + [ 1 .. numrels ];
for i in [ 1 .. numrels ] do
    grels[i] := TzWord( tietze, rels[i] );
od;

by

grels := [];
for i in rels do
    if i <> [] then Add( grels, TzWord( tietze, i ) ); fi;
od;

Then your above example should work properly.

Volkmar Felsch, Aachen


> < [top]