Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose I have a group $G$ with a finite presentation, and I know that $G$ is polycyclic. So I input the group into GAP via generators and relators. Now I want to find a presentation of an infinite index subgroup; I can do this by hand (usually), by doing a Reidemeister-Schreier rewriting, and then simplifying the presentation as best I can. GAP will, in general, not attempt to find presentations of infinite index subgroups. But if I tell GAP the group is polycyclic, are there various algorithms out there such that GAP can in fact give me a finite presentation for this infinite index subgroup?

If that is too much, can GAP do it for certain "nice" subgroups (the commutator, etc.)?

share|improve this question
If you can convert the presentation to a polycyclic presentation, there are lots of fairly efficient algorithms (efficient as linear algebra over Z). The polycyclic package has lots of information. If the group is actually nilpotent, then there are better algorithms and they can handle a wider variety of inputs. If you mention a more specific group, I can mention more specific techniques, but in general you just want to use the data type of PcpGroup rather than FpGroup. –  Jack Schmidt Jan 20 '11 at 13:10
Hi Jack - Can we start with something easy, say the Klein bottle group <a,b | aabb=1>? Supposing all I know is the presentation and that the group is polycyclic, how can I get GAP to give presentations of, for example, the commutator subgroup? –  user641 Jan 20 '11 at 13:59
Just FWIW: I asked but have yet to hear back on how to automatically convert such a group to a polycyclic presentation. If you can find a polycyclic generating sequence, then you can ask gap for the relative orders and power and conjugate words, and set up the group as a PcpGroup. Once it is a PcpGroup, your question is easy: DisplayPcpGroup( DerivedSubgroup( G ) ); will display a polycyclic presentation with trivial relations omitted, and Display(ImagesSource(IsomorphismFpGroup(DerivedSubgroup(G)))); will display all the relations. –  Jack Schmidt Jan 20 '11 at 23:37
IsomorphismPcpGroup is probably not suitable for you, as it assumes that you are giving it a polycyclic presentation, with omitted polycyclic relations being trivial. In particular, it will abelianize your Klein bottle group. –  Jack Schmidt Jan 20 '11 at 23:38
OK, thanks Jack. So I still need to do a little work in converting to a polycylic presentation. Does DisplayPcpGroup return a presentation? I would like to be able to run Tietze transformations on it. –  user641 Jan 21 '11 at 1:48

1 Answer 1

up vote 2 down vote accepted

To do what you want, you need a tool that takes a finitely presented group, and, given the information that this group is polycyclic, determines a polycyclic presentation for this group. In general, this is a computationally very difficult problem, although in certain special cases it may be much simpler.

The best approach that I know to this problem in general is to apply a polycyclic quotient algorithm, such as the one described in the paper "A Polycyclic Quotient Algorithm" by Eddie Lo (J. Symbolic Computation (1998) 25, 61–97). He implemented this in C and GAP3, which makes it a tad difficult to use on modern day computers.

The idea then is to take your finite presentation, and compute a maximal PC quotient of it. Since you know your group is polycyclic, this will definitely terminate, but it might take a looong time and a lot of memory (and loong could easily mean more than your life time if things are bad... :/).

But once you have a pc presentation, you can usually work quite effectively with it, with the help of the polycyclic package, as Jack Schmidt already pointed out.

Anyway, if you still want to try to find a pc presentation for a specific group, I implemented a pc quotient algorithm in GAP 4 last year, which can perhaps solve your problem. It's not yet been published, though I hope to get this finally done sometime soon. In the meantime, feel free to get in touch with my privately and perhaps I can help you in concrete cases.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.