$G$ is polycyclic means that $G$ has a normal series $$ G = G_1 \unrhd G_2 \unrhd \dotsm \unrhd G_n \unrhd G_{n+1} = 1 $$ such that $G_i/G_{i+1}$ is cyclic.
All $p$-groups are polycyclic. Polycyclic implies soluble and finitely generated.
For $g_i$ chosen such that $\langle g_iG_{i+1}\rangle = G_i/G_{i+1}$, the tuple $(g_1,\dotsc,g_n)$ is a polycyclic (generating) sequence for $G$, pcgs in short. Furthermore, set $r_i = [G_i:G_{i+1}]$, so that $r_i\in\NN\cup\{\infty\}$. Then $(r_1,\dotsc,r_n)$ is the sequence of relative orders.
1) Lemma. Fix a pcgs for $G$. Every $g\in G$ can be written as a word $g = g_1^{e_1}\dotsm g_i^{e_i}$ relative to the pcgs, with $e_i\in\ZZ$ and $0\leq e_i\leq r_i$ if $r_i<\infty$, and the tuple $(e_1,\dotsm,e_n)$ is unique to $g$. This tuple determines the normal form $g_1^{e_1}\dotsm g_n^{e_n}$ of $g$.
Observe $\size G = r_1\dotsm r_n$. The Hirsch length of $G$ is $$ h(G) = \# \{i\in\{1,\dotsc,n\}\mid r_i=\infty\}. $$ (The number of finite indices is not an invariant.)
2) Theorem. For each pcgs $(g_1,\dotsc,g_n)$ with relative orders $(r_1,\dotsc,r_n)$ there exist $e_{ij},e_{ijk},\overline{e_{ijk}}\in\ZZ$ such that the following defines a polycyclic presentation (pcp) $$ \langle g_1,\dotsc,g_n \mid \begin{cases} g_i^g = g_{j+1}^{e_{i,j,j+1}} \dotsm g_n^{e_{ijn}}, j\lt i \\\ g_i^{g_j^{-1}} = g_{j+1}^{\overline{e_{i,j,j_1}}} \dotsm g_n^{\overline{e_{ijn}}}, j\lt i \\\ g_i^{r_i} = g_{j+1}^{e_{i,i+1}} \dotsm g_n^{e_{in}}, r_i\neq \infty \end{cases} \rangle $$ (where in the above expression, by abuse of notation, the $g_i$ are abstract generators which are not the same as the group elements $g_i$) and this presentation defines $G$. It allows effective computations in $G$. (The second line of relations can always be ommitted if $G$ is finite.)
A pcp in which the third set of relations reads $$ g_i^{s_i} = g_j+1^{e_{i,i+1}} \dotsm g_n^{e_{in}}, s_i\neq \infty $$ is consistent if $s_i =\size{g_i}$ for all $i$.
If a presentation is consistent, then the normal form is well-defined and this makes it possible to solve the word problem in $G$ (with respect to this set of generators).
Collection computes the word in normal form by rewriting an expression in the generators using the relations of Theorem 2.
Example. The infinite dihedral group $D_{\infty}$ is available in GAP as
gap> DihedralPcpGroup(0);
Pcp-group with orders [ 2, 0 ]and has presentation $$ \langle g_1,g_2 \mid g_1^2 = 1, g_2^{g_1} = g_2^{-1} \rangle. $$
Polycyclic presentations make it easy to find certain group-theoretic properties, like derived subgroups, centers, nilpotency and abelian invariants. For example, this can be helpful when working with matrices over the integers.
It is also possible to start with a pcp and try to determine the group.
GAP has some functionality for this; see
FromTheLeftCollector(n), SetRelativeOrder(C,i,j), SetConjugate(C,i,j,tup), IsConfluent(C)
and PcpGroupByCollector(C).
If $U$ is a subgroup of $G$, we can compute an induced generating sequence of the form $$ \begin{gather} u_1 = g_1^{f_{11}} \dotsm g_n^{f_{1n}} \\ \dotsc \\ u_s = g_1^{f_{s1}} \dotsm g_n^{f_{sn}} \end{gather} $$ which defines a $s\times n$-matrix over $\ZZ$, conjugate to an upper-triangular matrix. Then $(u_1,\dotsc,u_s)$ is a pcgs for $U$.
The finite polycyclic groups are exactly the finite soluble groups. The infinite polycyclic groups are exactly the infinite soluble groups whose subgroups are finitely generated. In this part, we look at the finite polycyclic groups; the infinite case will be treated in the next.
Let $G$ be a finite polycyclic group. Without loss of generality, we may assume additionally
As useful notation, set $N = G_2$, that is, a maximal subgroup of prime index, and set $A = G_{w_{s-1}}$ a maximal elementary abelian normal (characteristic) subgroup in $G$.
3) Lemma. Suppose $G$ acts on $\Om$, $\om\in\Om$, $S = \Stab_N(\om)$. Then
Given $G$ and a prime $p$, one can determine a Sylow $p$-subgroup of $G$ by induction up the subnormal series. Then we may assume that $S$ is a Sylow $p$-subgroup of $N$ is given. Recall that $N$ is normal of prime index.
In the latter case, $x$ may be determined by induction down the normal series, and so we may assume that $x$ modulo $A$ is determined, that is, $\langle S,g_1x\rangle A/A$ is a Sylow $p$-subgroup in $G/A$.
In the latter case, we may use the following lemma.
4) Lemma. Let $S = \langle s_1,\dotsc,s_r\rangle$. Then $[s_j,g_1x] = t_ja_j$, for $t_j\in S$ and $a_j\in A$. Also $(g_1x)^p = ta$. If $y\in A$ with $t_j=[y,s_j^{g_1x}]$ and $t = (y^{(g_1x)^{p-1}}y^{(g_1x)^{p-2}}\dotsm y)^{-1}$, then $\langle S,g_1xy\rangle$ is a Sylow $p$-subgroup of $G$.
The advantage of this lemma is that the criteria lie entirely in $A$, and hence the methods of linear algebra are available. In particular, a solution may easily be found using Gauss over $\FF_q$.
This solves the problem in all cases. Many other approaches have the same inductive flavour.
Given $G$, compute $\Aut(G)$, or at least its generators and its order. By induction we may assume we have $\Aut(G/A)$, where $A$ is the characteristic elementary abelian subgroup as above.
5) Theorem. There exists a homomorphism $$\begin{align} \rho:\Aut(G) & \to \Aut(G/A)\times\Aut(A) \\ \al & \mapsto (\al\rvert_{G/A},\al\rvert_A) \end{align} $$ with $\ker(\rho) \cong Z^1(G/A,A)$.
Determine $\im(\rho)$. Recall that $G$ acts on $A$ by conjugation and this induces a homomorphism $G/A\to\Aut(A)$. We write this using bar notation. Define the set of compatible pairs $$ \op{Comp}(G,A) = \{ (\bt,\gm)\in\Aut(G/A)\times\Aut(A) \mid \overline{\bt(g)} = \gm^{-1}\overline g\gm \forall g\in G/A \}. $$ Now $\Aut(G/A)$ is known inductively and $\Aut(A)$ is $GL_d(p)$. The compatible pairs $\op{Comp}(G,A)$ act on $Z^2(G/A,A)$ where, for $\dl\in Z^2(G/A,A)$, $$ (\bt,\gm):\dl\mapsto\gm(\dl(\bt^{-1}(g),\bt^{-1}(h))). $$
Suppose $G$ is an extension of $A$ by $G/A$ via $\dl+B^2(G/A,A) = [\dl]$. Then $\im(\rho) = \Stab_{\op{Comp}(G/A,A)}([\dl])$.
In finite polycylic groups, every problem is decidable, and very many problems have effective solutions. (Effective means that, even though there is no complexity analysis, the methods can be very fast. [The word problem has no good complexity analysis, and this, via collection, is fundamental to our method.])
In infinite polycyclic groups, there are undecidable problems (mostly somewhat exotic), problems whose decidability is not known (such as the determination of a minimal generating set), decidable problems for which no effective algorithms are available (such as the determination of the automorphism group, where our stabiliser methods are not applicable since orbits may be infinite), and of course problems with known effective solutions (of which there are still many, including the word problem solved by collection, conjugacy problems, finite-index subgroups, some finite subgroups, and the $H^2$, $H^1$, $H^0$ cohomology groups).
Groups can be found from algebraic number fields: Let $K$ be an algebraic number field, $[K:\QQ] = n$, $M$ the maximal order of $K$ (so that, as an additive group, $(M,+)\cong\ZZ^n$), and U the unit group of $K$ (a finitely generated abelian group). Then $M\rtimes U$ is infinite polycyclic, where $U$ acts by multiplication on $M$. Hence one often needs some algebraic number theory for working with infinite polycyclic groups.
Crystallographic groups: take $T \unlhd G$ with $T \cong \ZZ^d$ and $G/T$ finite; then $G$ is polycylic if and only if $G/T$ is soluble.
Given $G$ polycyclic with pcp, and $g,h\in G$, does there exist $x\in G$ such that $g^x = h$? The dual problem is to determine $C_G(g)$.
Use induction down the normal series of the form $$ G = G_1 \rhd G_2 \rhd \dotsm \rhd G_\ell \rhd G_{\ell+1} = 1 $$ with $G_i\lhd G$ and every $G_i/G_{i+1}$ either elementary abelian or free abelian. Again set $A = G_\ell$, and assume that the problem is solved in $G/A$, that is, we found some $y\in G$ such that $g^y = h$ modulo $A$, and $C_G/A(gA)$ has been found too. Fix the subgroup $C\leq G$ such that $C/A = C_G(gA)$. Replace $h$ by $h^{y^{-1}}$. Then $gA = hA$ and therefore $g^{-1}h = a \in A$.
6) Lemma. Consider $\dl:C\to A,c\mapsto [g,c]$.
$A$ is either elementary abelian or free abelian, in the former case, $A$ can be identified with the vector space $\FF_p^d$, in the latter, with the lattice $\ZZ^d$. Set $R = \FF_p$ if $A$ is elementary abelian and $R = \ZZ$ if $A$ is free abelian. Let $\rho:G\to\Aut(A)$ denote the conjugacy action of $G$ on $A$. Note $\Aut(A) = GL_d(R)$. Define $\al:C\to GL_{d+1}(R)$ by $$ c\mapsto \begin{pmatrix} & & & 0 \\ & \rho(c) & & \vdots \\ & & & 0 \\ & \dl(c) & & 1 \end{pmatrix}. $$ Then $\ker(\dl) = \Stab_C(0,0,\dotsc,0,1)$ and $\im(\dl) = \op{Orbit}_C(0,0,\dotsc,0,1)$. In this special case of $A = \ZZ^d$, orbits and stabilisers can still be determined, despite being infinite.
There are only finitely many conjugacy classes of finite subgroups (but each class is infinite). $G$ has a torsion subgroup $T=T(G)$ if there exists a unique maximal finite subgroup; otherwise, the collection of finite-order elements is not closed under multiplication, and we say $T(G)$ does not exist. For example, $D_\infty$ has two maximal subgroups $\langle a\rangle^{D_\infty},\langle ab\rangle^{D_\infty}$, so it is torsion-free. $T(G)$ is nontrivial if $G$ is nilpotent.
To compute these, we induct up a subnormal series with cyclic factors (as given in the pcp). Let $N\lhd G$ with $G/N$ cyclic and either infinite or of prime order. We have $T(N)$ determined by induction.
7) Theorem.
Computing complements is a cohomology question and hence reduces to solving linear equations, which is doable even in the infinite groups.
$p$-groups are an interesting special case of polycyclic groups, and many of our methods are even more effective for $p$-groups.
A classification of $p$-groups of low order is easy. There are $1,2,5,15$ groups of order $p,p^2,p^3,p^4$ (or $14$ groups of order $2^4$). The number of $p$-groups of orders $p^5$, $p^6$, $p^7$ has been determined as a polynomial in $p$, where some terms involve lowest common denominators. But the expressions are complicated and (extremely) difficult to find. (This problem is well-known for incorrect classification attempts.)
Higman's Porc conjecture is that the number $f(n)$ of groups of rder $p^n$ is a polynomial in residue classes, if $p$ is large enough. (Some recent research by du Sautoy suggests that this may not be the case.)
How does one generate the groups of order $p^n$? $p$-group generation (due to Newman and O'Brien) takes an inductive approach on descendants. Suppose that $G$ is a $p$-group, for a fixed $p$, with a central characteristic series of elementary abelian factors. $H$ is a descendant of $G$ if and only if $H/H_e \cong G$ and $H_{e+1}$ is the trivial group.
An improvement (Eick & O'Brien) is to consider families of $p$-groups for $p$ a variable, and then consider descendants.
Similar to the problem of determining automorphism groups, it all boils down to orbit-stabiliser methods under the action of $\Aut G$. (These cannot be easily generalised to nonfixed $p$. One way of getting around this is to replace $p$-groups with multiplicative structure by Lie rings with additive structure.)
An approach to classification is to divide cases by coclass instead of by the order of the group. The coclass of $G$ of size $p^n$ is $n - c$, where the class $c$ of $G$ is the length of its lower central series. The coclass graph $\Gm(p,r)$ has vertices which are groups of order $p^n$ and coclass $r$, up to isomorphism. The vertices can be graded by level, where groups of order $p^n$ sit in level $n$. There is an edge between $G$ and $H$ if there exists $N\lhd H$ with $\size N = p$ and $H/N\cong G$. Of course $\Gm(p,r)$ is infinite; furthermore it is a forest.
Suppose that $G = G_0,G_1,\dotsc$ is an infinite path in $\Gm(p,r)$. Let $T_G$ be the full tree of descedants of $G$ in $\Gm(p,r)$. Then $T_G$ is a coclass tree if and only if it contains exactly one infinite path. Every infinite path defines an infinite pro-$p$ group $P = \lim G_i$, also of coclass $r$.
A deep theorem by Leedham-Green, Shalev and Zelmanov states that there are only finitely many infinite pro-$p$-groups of coclass $r$ (and hence only finitely many infinite paths in the coclass graphs), every infinite prop-$p$-group of coclass $r$ corresponds to a coclass tree in $\Gm(p,r)$, and that $\Gm(p,r)$ hence only consists of finitely many coclass trees, and finitely many other groups.
The number of infinite pro-$p$-groups of given coclass can be asymptotically estimated (and is rather large).
If $T_G$ is a coclass tree, let $B_i$ be the subtree of $T_G$ of all descendants of $G_i$ which are not descendants of $G_{i+1}$. Also set $B_{i,k}$ to be the subtree of $B_i$ of nodes at distance at most $k$ from the root $G_i$. Then $B_{i,k}$ is a branch of $T_G$. (Gardening metaphor thanks to du Sautoy.)
8) Theorem. The branches begin to repeat, that is, for every $k$ there exist $d$ and $l = l(k)$ such that $B_{i,k} \cong B_{i+d,k}$ for all $i\geq l$.
Conjectured by Newman and O'Brien in 1999, proved by du Sautoy in 2001 using zeta functions and by Eick and Leedham-Greene using group theory in 2006. This allows the definition of infinite coclass families.
For $p=2$, there exists $k=k(r)$ such that $B_i = B_{i,k}$, that is, the branches stop growing. In the odd-prime case, the periodicity is less well-understood. The original conjecture was inspired by computation results; current computational methods are not strong enough to inspire conjectures in this harder case.
The infinite pro-$p$-group $P$ of coclass $r$ is somewhat understood by algorithmic methods. The key problem is determining the $p$-adic (rational) space groups of coclass $r$. But the numbers get large rather quickly. One approach is to (use GAP to) construct finite parts of $T_G$ from $P$.
9) Theorem. The groups in an infinite coclass family can be described by a single parametrised (polycyclic!) presentation. In particular, the $2$-groups of coclass $r$ can be classified by finitely many presentations.
It is conjectured that the order of a nonabelian $p$-group divides the order of its automorphism group. Since the automorphism groups of the groups in an infinite coclass family are periodic, there are at most finitely many counterexamples to this conjecture among the $2$-groups of coclass $r$.
Another application is to the old problem of finding all $p$-groups with trivial Schur multiplicator. Among odd $p$-groups of coclass $r$, there are at most finitely many with trivial Schur multiplicator; among $2$-groups of coclass $r$ there are infinite coclass families with trivial Schur multiplicator.
Notes by Felix Rehren / rehrenf@maths.bham.ac.uk
Based on a course by Bettina Eick
July 29th to August 2nd 2013, St Andrews