In mathematics, specifically group theory, a descendant tree is a hierarchical structure that visualizes parent-descendant relations between isomorphism classes of finite groups of prime power order , for a fixed prime number and varying integer exponents . Such groups are briefly called finite p-groups. The vertices of a descendant tree are isomorphism classes of finite p-groups.
Additionally to their order , finite p-groups have two further related invariants, the nilpotency class and the coclass . It turned out that descendant trees of a particular kind, the so-called pruned coclass trees whose infinitely many vertices share a common coclass , reveal a repeating finite pattern. These two crucial properties of finiteness and periodicity admit a characterization of all members of the tree by finitely many parametrized presentations. Consequently, descendant trees play a fundamental role in the classification of finite p-groups. By means of kernels and targets of Artin transfer homomorphisms, descendant trees can be endowed with additional structure.
An important question is how the descendant tree can actually be constructed for an assigned starting group which is taken as the root of the tree. The p-group generation algorithm is a recursive process for constructing the descendant tree of a given finite p-group playing the role of the tree root. This algorithm is implemented in the computational algebra systems GAP and Magma.
Definitions and terminology According to M. F. Newman, there exist several distinct definitions of the parent of a finite p-group . The common principle is to form the quotient of by a suitable normal subgroup which can be either
the centre of , whence is called the central quotient of , or the last non-trivial term of the lower central series of , where denotes the nilpotency class of , or the last non-trivial term of the lower exponent-p central series of , where denotes the exponent-p class of , or the last non-trivial term of the derived series of , where denotes the derived length of .
In each case, is called an immediate descendant of and a directed edge of the tree is defined either by in the direction of the canonical projection onto the quotient or by in the opposite direction, which is more usual for descendant trees. The former convention is adopted by C. R. Leedham-Green and M. F. Newman, by M. du Sautoy and D. Segal, by C. R. Leedham-Green and S. McKay, and by B. Eick, C. R. Leedham-Green, M. F. Newman and E. A. O'Brien. The latter definition is used by M. F. Newman, by M. F. Newman and E. A. O'Brien, by M. du Sautoy, and by B. Eick and C. R. Leedham-Green.
In the following, the direction of the canonical projections is selected for all edges. Then, more generally, a vertex is a descendant of a vertex , and is an ancestor of , if either is equal to or there is a path , with , of directed edges from to . The vertices forming the path necessarily coincide with the iterated parents of , with : , with ,
In the most important special case (P2) of parents defined as last non-trivial lower central quotients, they can also be viewed as the successive quotients of class of when the nilpotency class of is given by : , with .
Generally, the descendant tree of a vertex is the subtree of all descendants of , starting at the root . The maximal possible descendant tree of the trivial group contains all finite p-groups and is somewhat exceptional, since, for any parent definition (P1–P4), the trivial group has infinitely many abelian p-groups as its immediate descendants. The parent definitions (P2–P3) have the advantage that any non-trivial finite p-group (of order divisible by ) possesses only finitely many immediate descendants.
Pro-p groups and coclass trees For a sound understanding of coclass trees as a particular instance of descendant trees, it is necessary to summarize some facts concerning infinite topological pro-p groups. The members , with , of the lower central series of a pro-p group are closed (and open) subgroups of finite index, and therefore the corresponding quotients are finite p-groups. The pro-p group is said to be of coclass when the limit of the coclass of the successive quotients exists and is finite. An infinite pro-p group of coclass is a p-adic pre-space group , since it has a normal subgroup , the translation group, which is a free module over the ring of p-adic integers of uniquely determined rank , the dimension, such that the quotient is a finite p-group, the point group, which acts on uniserially. The dimension is given by
, with some .
A central finiteness result for infinite pro-p groups of coclass is provided by the so-called Theorem D, which is one of the five Coclass Theorems proved in 1994 independently by A. Shalev
and by C. R. Leedham-Green , and conjectured in 1980 already by C. R. Leedham-Green and M. F. Newman. Theorem D asserts that there are only finitely many isomorphism classes of infinite pro-p groups of coclass , for any fixed prime and any fixed non-negative integer . As a consequence, if is an infinite pro-p group of coclass , then there exists a minimal integer such that the following three conditions are satisfied for any integer .
, is not a lower central quotient of any infinite pro-p group of coclass which is not isomorphic to , is cyclic of order .
The descendant tree , with respect to the parent definition (P2), of the root with minimal is called the coclass tree of and its unique maximal infinite (reverse-directed) path
is called the mainline (or trunk) of the tree.
Tree diagram Further terminology, used in diagrams visualizing finite parts of descendant trees, is explained in Figure 1 by means of an artificial abstract tree. On the left hand side, a level indicates the basic top-down design of a descendant tree. For concrete trees, such as those in Figure 2, resp. Figure 3, etc., the level is usually replaced by a scale of orders increasing from the top to the bottom. A vertex is capable (or extendable) if it has at least one immediate descendant, otherwise it is terminal (or a leaf). Vertices sharing a common parent are called siblings.
If the descendant tree is a coclass tree with root and with mainline vertices labelled according to the level , then the finite subtree defined as the difference set
is called the nth branch (or twig) of the tree or also the branch with root , for any . The depth of a branch is the maximal length of the paths connecting its vertices with its root. Figure 1 shows an artificial abstract coclass tree whose branches and both have depth , and the branches and are pairwise isomorphic as graphs. If all vertices of depth bigger than a given integer are removed from the branch , then we obtain the depth- pruned branch . Correspondingly, the depth- pruned coclass tree , resp. the entire coclass tree , consists of the infinite sequence of its pruned branches , resp. branches , connected by the mainline, whose vertices are called infinitely capable.
Virtual periodicity The periodicity of branches of depth-pruned coclass trees has been proved with analytic methods using zeta functions
of groups by M. du Sautoy , and with algebraic techniques using cohomology groups by B. Eick and C. R. Leedham-Green . The former methods admit the qualitative insight of ultimate virtual periodicity, the latter techniques determine the quantitative structure.
Theorem. For any infinite pro-p group of coclass and dimension , and for any given depth , there exists an effective minimal lower bound , where periodicity of length of pruned branches of the coclass tree sets in, that is, there exist graph isomorphisms
for all .
For the proof, click show on the right hand side.
The graph isomorphisms of depth- pruned branches with roots of sufficiently large order are derived with cohomological methods in Theorem 6, p. 277 and Theorem 9, p. 278 by Eick and Leedham-Green
and the effective lower bound for the branch root orders is established in Theorem 29, p. 287, of this article.
These central results can be expressed ostensively: When we look at a coclass tree through a pair of blinkers and ignore a finite number of pre-periodic branches at the top, then we shall see a repeating finite pattern (ultimate periodicity). However, if we take wider blinkers the pre-periodic initial section may become longer (virtual periodicity).
The vertex is called the periodic root of the pruned coclass tree, for a fixed value of the depth . See Figure 1.
Multifurcation and coclass graphs Assume that parents of finite p-groups are defined as last non-trivial lower central quotients (P2). For a p-group of coclass , we can distinguish its (entire) descendant tree and its coclass- descendant tree , that is the subtree consisting of descendants of coclass only. The group is called coclass-settled if , i.e., if there are no descendants of with bigger coclass than .
The nuclear rank of in the theory of the p-group generation algorithm by M. F. Newman
and E. A. O'Brien
provides the following criteria.
is terminal, and thus trivially coclass-settled, if and only if . If , then is capable, but it remains unknown whether is coclass-settled. If , then is capable and definitely not coclass-settled.
In the last case, a more precise assertion is possible: If has coclass and nuclear rank , then it gives rise to an m-fold multifurcation into a regular coclass-r descendant tree and irregular descendant graphs of coclass , for . Consequently, the descendant tree of is the disjoint union
.
Multifurcation is correlated with different orders of the last non-trivial lower central of immediate descendants. Since the nilpotency class increases exactly by a unit, , from a parent to any immediate descendant , the coclass remains stable, , if the last non-trivial lower central is cyclic of order , since then the exponent of the order also increases exactly by a unit, . In this case, is a regular immediate descendant with directed edge of step size , as usual. However, the coclass increases by , if with . Then is called an irregular immediate descendant with directed edge of step size .
If the condition of step size is imposed on all directed edges, then the maximal descendant tree of the trivial group splits into a countably infinite disjoint union
of directed coclass graphs , which are rather forests than trees. More precisely, the above-mentioned Coclass Theorems imply that
is the disjoint union of finitely many coclass trees of pairwise non-isomorphic infinite pro-p groups of coclass (Theorem D) and a finite subgraph of sporadic groups lying outside of any coclass tree.
Identifiers The SmallGroups Library identifiers of finite groups, in particular of finite p-groups, given in the form
in the following concrete examples of descendant trees, are due to H. U. Besche, B. Eick and E. A. O'Brien .
When the group orders are given in a scale on the left hand side, as in Figure 2 and Figure 3, the identifiers are briefly denoted by
.
Depending on the prime , there is an upper bound on the order of groups for which a SmallGroup identifier exists, e.g. for , and for . For groups of bigger orders, a notation with generalized identifiers resembling the descendant structure is employed. A regular immediate descendant, connected by an edge of step size with its parent , is denoted by
,
and an irregular immediate descendant, connected by an edge of step size with its parent , is denoted by
.
The implementations of the p-group generation algorithm in the computational algebra systems GAP and Magma use these generalized identifiers, which go back to J. A. Ascione in 1979 .
Concrete examples of trees In all examples, the underlying parent definition (P2) corresponds to the usual lower central series. Occasional differences to the parent definition (P3) with respect to the lower exponent-p central series are pointed out.
Coclass 0 The coclass graph