3
$\begingroup$

This is more of a question specifically about how GAP handles calculations with finitely presented groups rather than about group theory.

I have several finite group presentations that I would like to do computations on using GAP. Suppose I have denoted one as G. For this example, suppose that by entering the command 'Size(G);', GAP takes approximately a minute to determine that G is of a large finite order. My understanding (please correct me if I am wrong) is that GAP determined this through a Todd-Coxeter coset enumeration of the trivial subgroup of G.

Ultimately, I have other computations to perform on G which I have been approaching by creating a coset table of G (w.r.t. a particular subgroup H, although taking H to be the trivial subgroup is fine for my purposes), but the command 'CosetTable(G,H);' takes an absurdly long time to complete (for this example, absurdly long is defined to mean longer than 30 minutes).

Is there any way to extract or directly access the coset table GAP generated for the trivial subgroup while computing 'Size(G);', or is there more going on behind the scenes that would make such a coset table useless? In particular, being able to trace the action of words in the free group on the generators of G make the output of 'CosetTable(G,H);' ideal for my research. Is this why it takes so long for GAP to generate this coset table, as it has to determine how the generators of G act on every coset of H, including when I define H to be the trivial subgroup of G?

$\endgroup$
4
  • 1
    $\begingroup$ Interesting! Could you show a particular example of a finite group G for which CosetTable(G,H) takes enormously long time, please? $\endgroup$ – Alexander Konovalov Apr 14 '15 at 19:29
  • $\begingroup$ @Alexander Konovalov At this time, I would prefer to keep those group presentations private as they are part of a small set of unpublished results that has been shared with me. What I will say at the moment is that the first (although not the largest so far) of these presentations which started giving me trouble has approximately 24 million elements. It also has a subgroup of small order (<20) with which I am seeking to generate a coset table. This takes my computer (which has 8GB of ram) approximately an hour to process. However, another presentation has recently been found to be much larger, $\endgroup$ – Archie Apr 21 '15 at 20:31
  • $\begingroup$ GAP has a very friendly user mailing list, which is a better place for this sort of thing, no? $\endgroup$ – Mariano Suárez-Álvarez Apr 21 '15 at 21:57
  • $\begingroup$ @MarianoSuárez-Alvarez yes, there is GAP Forum which is fully public, and GAP Support which is not. Also, for the discussions on GAP development there is another public list here. $\endgroup$ – Alexander Konovalov Apr 22 '15 at 12:12
4
$\begingroup$

If you ask GAP for the Size of a finitely presented group, the system will (unless it already knows it) enumerate the cosets of a cyclic subgroup (typically generated by one generator), used (Modified Todd-Coveter) rewriting to get a 1-generator presentation for this cyclic group, and then calculates the group order as order of this subgroup * index. If the subgroup is large clearly the coset table by the trivial subgroup will take much longer than the index of the subgroup. (To decide whether this is the reason, one would need to know the presentation.)

If you want the coset table for the trivial subgroup, i.e. the regular permutation representation, and an order computation terminated, I would rather use IsomorphismPermGroup to obtain a faithful permutation representation, and then in that group call CosetTableBySubgroup(<permgroup>,Group(())).

$\endgroup$
2
  • $\begingroup$ Is there a way to determine specifically which cyclic subgroup GAP is using in the size calculation? $\endgroup$ – Archie Apr 21 '15 at 20:31
  • $\begingroup$ @Archie Not in the Size methods, but you could define a subgroup generated by one (or several) elements and ask for its Index and then use IsomorphismFpGroup on this subgroup. $\endgroup$ – ahulpke Apr 21 '15 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.