Fp-group handling

[hungaborhorvath]

I played around with fp-groups a bit, and found some weird behaviour in GAP. I am not sure if these are bugs or neccessities due to the presentation of the group.

I played with the following group:

gap> F := FreeGroup("x", "y", "z");;
gap> x := F.1;; y := F.2;; z := F.3;;
gap> G := F/[x*y*x^(-1)*y^(-1), x*z*x^(-1)*z^(-1), z*y*z^(-1)*y^(-1), (x*y)^180, (x*y^5)^168];;

First of all, IsAbelian(G) did not give me any results in a reasonable time (couple minutes). If I invert the relations then GAP immediately recognizes them as commutators, and IsAbelian(G) is instantenous.

Second, AbelianInvariants is instantenous. Then, however, IndependentGeneratorsOfAbelianGroup takes again an immensely long time. Without having IsAbelian set to true, it seems that it is stuck with trying to check some properties to determine which method to use. If I set IsAbelian to true, then it runs lib/grpfp.gi:6041 for again a very long time (85 seconds).

I checked this method and ran all but the last two lines of it. These all ran instantenous. The last two lines are

  base := List( base, gen -> MappedWord( gen, gens, GeneratorsOfGroup( G ) ) );
  return base;

The interesting thing is, that if I simply ask GAP to print base, it already takes an enormous time (around 40 seconds).

If I TraceMethod it, then this is what uses the most time:

#I  Setter(IndependentGeneratorsOfAbelianGroup): system setter

This seems to mean that the algorithm itself is fine, the problem seems to lie in how the elements of an fp-group are represented for GAP.

Is that really the case and can this be helped in any way?

[hungaborhorvath]

I tried this experiment with CyclicGroup(IsFpGroup, Factorial(100));

Again all but the last two lines ran instantenous, then when I ask for base I get this error:

gap> base; 
Error, Range: <first> must be an integer less than 2^60 (not a integer (>= 2^60)) in
  [ for i  in [ n, n - 1 .. 1 ]  do
        list[i] := obj;
    od; at /home/ghorvath/work/gap/lib/list.gi:3541 called from 
ListWithIdenticalEntries( n, g 
     ) at /home/ghorvath/work/gap/lib/wordrep.gi:1329 called from
    LetterRepAssocWord( elm 
     ) at /home/ghorvath/work/gap/lib/wordrep.gi:250 called from
    NiceStringAssocWord( elm 
     ) at /home/ghorvath/work/gap/lib/wordrep.gi:266 called from
    ViewObj( list[i] 
     ); at /home/ghorvath/work/gap/lib/list.gi:3574 called from
    SetUserHasQuit( 1 
     ); at /home/ghorvath/work/gap/lib/error.g:248 called from
    ...  at line 34 of *stdin*
you can replace <first> via 'return <first>;'
brk> 

Same error if I run the last line. I am not even sure what the elements of this base are, they seem to have Length, but not Size.....

Another interesting thing, already mentioned in #592 by @bh11 is that for pc groups IndependentGeneratorsOfAbelianGroup actually finishes, but in a very long time (was about 5 minutes the last time I ran it on my laptop). Here, lib/grppc.gi:2375 is executed, and the system setter is activated at the end.

BTW, I know these are in some sense ridiculous examples that are probably will never tried by any user, so just let me know if I should stop.

[bh11]

In your first example, IndependentGeneratorsOfAbelianGroup is fast (once it knows that the group is abelian), but displaying the result takes a very long time (the reason is that GAP tries to find a nice representation). Enter the relevant commands with a double semicolon, and they will be instant. base is just a list of words in free generators. If I recall correctly, this code is by @alex-konovalov, maybe he wants to have a look.

[hulpke]

Leaving aside that this is a constructed example there are a couple of items that an interested person could code and thereby improve the system:

• We do not have finitely generated abelian groups and their subgroups as objects on their own. The calculations are easy (essentially Smith Normal Form) and it might be possible to piggyback on fp groups for element representation, but in the end all basic machinery needs to be installed as methods.
• IsAbelian for an infinite fp group will test whether commutators of the generators are trivial.
  If these happen to be relators there is a shortcut (which was requested some time ago) that will do so immediately, but anything more complicated (even just inverses) goes through the general rewriting machinery.

This is -- both in terms how to convert to a monoid, i.e. addition of generators for inverses, and the actual Knuth Bendix implementation by far weaker than standalone code and thus could be improved substantially (with what also would amount to substantial work).

• There are two representations of words, one as letter sequence LetterRep, one as generator/exponent pairs. I believe the constructor for cyclic (maybe even abelian) fp groups uses the second representation, while most generic fp group code uses the first. Thus Abelian Invariants tries to write a^(100!) in letter representation, which runs out of memory. One could fix this by adding a secondary code path for this representation -- frankly I don't consider this worth my time, but someone else might do so.
• As Burchard already mentioned, printing the (long) words takes time, as the print routine tries to find a nice, short representation. I still believe doing so is worth it (in the example one gets
  [ z, (x*y^785)^4, (x*y^785)^3, y^2016, y^1440, y^1120, y^315 ] instead of 10 screenfuls) if the user wants to see the elements, but the implementation is likely suboptimal and I suspect someone with more CS knowledge could design a better algorithm.

[hungaborhorvath]

@hulpke Yes, I completely agree that abelian fp groups should be handled differently, because you basically only do Gaussian elimination (Smith normal form, whatever) on them. If somebody points me to the right direction on how to make them new objects, etc. , I would be willing (at some point) to look at this. However, currently I have zero knowledge on a) how exactly GAP handles fp-groups and b) how new objects/categories/whatever would need to be introduced.

BTW, this task may be easier than at first look, because one could always say GAP to compute the independent generators, and the simply have an isomorphism e.g. to an abelian pc-group, no?

[markuspf]

Dear Alexander, Gabor, just to note that I have started working on some research to do with finitely presented groups (and semigroups, while I am at it), in particular in relation to hyperbolic groups. I was planning on improving some of the GAP infrastructure here, but haven't gotten there yet. Thanks for the heads up on the current state in this though! Cheers, Markus

[fingolfin]

Note that finitely generated abelian groups already can be dealt with quite efficiently in GAP: just represent them as pcp-groups, using the polycyclic package. So I am not sure we need another type just for those.

[hulpke]

@hungaborhorvath PcGroups are inherently finite and cannot be used to represent infinite groups.

[hungaborhorvath]

@fingolfin I tried to use them, but got an error message that I cannot really place, see #595.

@hulpke Sorry for my ignorance, I thought pc-groups are polycyclic groups, thus Z can be in the representation, as well. Or are you saying that for practical purposes, GAP only deals with finite polycyclic groups?

[hulpke]

@hungaborhorvath
PcGroups (lin library) are finite
PcpGroups (in polycyclic) may be infinite.

[hulpke]

@fingolfin Does "polycyclic" provide a method for AbelianGroup if one of the arguments is 0, overriding the library method? That would be very useful.

[fingolfin]

@hulpke Not quite: AbelianGroup is a function, so I cannot provide such a method for it. So you have to explicitly tell it to create pcp groups:

gap> G:=AbelianGroup(IsPcpGroup, [2,0,Factorial(20)]);
Pcp-group with orders [ 2, 0, 2432902008176640000 ]
gap> Size(G);
infinity

[fingolfin]

@hungaborhorvath both pc-groups and pcp-groups are special representations of polycyclic groups, designed around polycylic presentations. But of course e.g. a permutation group can be polycylic, too, without being a pc-group or a pcp-group. This is why there are two chapters in the GAP manual, one on "pc groups", one on "polycyclic groups"

[ EDIT: oops, sorry, that was for @hungaborhorvath and not @hulpke ]

[hulpke]

@fingolfin Ah, yes -- it's a constructor. The library creates infinite abelian groups by default as fp groups because it does not know better -- it would be nice if one could make them Pcp if the package is available (but that seems to be more tricky). Thanks!