Read-back: eight definitions

All eight declarations below are definitions, not theorems: each introduces a new symbol and fixes its meaning. Nothing below is asserted to be true or non-vacuous; what is recorded is what each symbol denotes.

Throughout, $G$ denotes a type (in an arbitrary universe) carrying a group structure supplied as a typeclass assumption. In the first definition $G$ is an implicit argument, inferred from the other arguments; in all the others it is given explicitly. Every definition applies to every group whatsoever: no finiteness, finite generation, nilpotence, solvability or commutativity is assumed anywhere.

Two conventions recur and are stated once here.

Counting. All cardinalities below are natural-number cardinalities, with the convention that an infinite set is assigned the value $0$, exactly as an empty set is. So a cardinality of $0$ records either "empty" or "infinite", and the two are not distinguished.

Ranks. The rank used below is the natural-number rank of a module: it is the supremum, over all subsets of the module that are linearly independent over the base ring, of the cardinality of that subset, converted to a natural number with the same convention — if that supremum is an infinite cardinal, the rank is $0$.

---

1. The growth function of a finite subset

Given a group $G$, a finite subset $S \subseteq G$, and a natural number $m$, this defines a natural number, the number of elements of the ball of radius $m$.

The ball of radius $m$ about the identity with respect to $S$ is the set

$$B_S(m) \;=\; \Bigl\{\, g \in G \;\Big|\; \exists\, \ell \ge 0,\ \exists\, x_1,\dots,x_\ell \in G :\ \ell \le m,\ \bigl(\forall j,\ x_j \in S \ \text{or}\ x_j^{-1} \in S\bigr),\ x_1 x_2\cdots x_\ell = g \,\Bigr\}.$$

Points of detail, all of which are literally what is written:

• The witness is a finite list $x_1,\dots,x_\ell$ of elements of $G$, of length at most $m$, not exactly $m$. Repetitions are allowed; the $x_j$ need not be distinct.
• The product is taken in the order of the list, bracketed to the right against the identity: $x_1\cdot(x_2\cdot(\dots\cdot(x_\ell\cdot 1)))$. For a group this is the ordinary ordered product $x_1x_2\cdots x_\ell$.
• The empty list ($\ell = 0$) is permitted, and its product is the identity. Hence the identity lies in $B_S(m)$ for every $m$, including $m = 0$, and $B_S(0) = \{1\}$.
• The condition on each letter is "$x_j \in S$ or $x_j^{-1} \in S$". $S$ itself is not required to be symmetric; the symmetrization is performed here, by the disjunction.
• $S$ is a finite subset, used through its underlying set $\{x : x \in S\}$. $S$ may be empty, in which case only the identity is reachable and $B_\emptyset(m) = \{1\}$ for all $m$.

The value of the definition is the number of elements of $B_S(m)$, under the counting convention above: if $B_S(m)$ were infinite the value would be $0$.

2. Polynomial growth of degree at most $E$

Given a group $G$ and a natural number $E$, this defines a proposition. It holds precisely when:

there exists a finite subset $S \subseteq G$ such that the subgroup generated by $S$ is all of $G$, and there exists a real number $c$ with $c > 0$ such that for every natural number $m$ with $m \ge 1$,

$$\bigl|B_S(m)\bigr| \;\le\; c\,m^{E},$$

where $|B_S(m)|$ is the count of §1, cast from a natural number into the reals, $m$ on the right is likewise cast into the reals, and $m^E$ is the $E$-fold product of $m$ with itself in the reals.

Points of detail:

• "The subgroup generated by $S$" is the smallest subgroup of $G$ containing $S$, i.e. the intersection of all subgroups containing $S$; the requirement is that this equals the whole group $G$.
• The generating set is existentially quantified, and the constant $c$ is existentially quantified after it, so $c$ may depend on $S$. Nothing asserts the bound for every generating set.
• The inequality is required only for $m \ge 1$. The case $m = 0$ is explicitly excluded, so no constraint is placed on $|B_S(0)|$.
• The exponent $E$ is a fixed natural number, and the bound is $\le$, not $<$. The degenerate value $E = 0$ is allowed: the requirement is then $|B_S(m)| \le c$ for all $m \ge 1$, since $m^0 = 1$ in the reals (including for $m$ whose cast is $0$ — but $m \ge 1$ there anyway).
• $c$ is required to be strictly positive, but no upper bound on $c$ is imposed, and $c$ need not be an integer.
• Because an infinite set is counted as $0$, any radius at which the ball were infinite would satisfy the inequality automatically rather than violating it.
• $S$ is permitted to be empty; the generation condition then forces $G$ to be the trivial group.

3. Polycyclicity

Given a group $G$, this defines a proposition. It holds precisely when:

there exist a natural number $t$ and a family of subgroups $A_0, A_1, \dots, A_t$ of $G$, indexed by the $t+1$ indices $0,1,\dots,t$, such that

1. $A_0 = G$ (the whole group);
2. $A_t = \{1\}$ (the trivial subgroup);
3. for every index $i$ with $0 \le i \le t-1$, both of the following hold:
   • $A_{i+1} \le A_i$, and
   • writing $H_i$ for the subgroup of the group $A_i$ consisting of those $x \in A_i$ with $x \in A_{i+1}$ (that is, $A_{i+1} \cap A_i$, regarded as living inside $A_i$), the subgroup $H_i$ is normal in $A_i$, and the quotient group $A_i / H_i$ — taken with the group structure that this normality provides — is cyclic, meaning that there is an element $g$ of $A_i/H_i$ for which the map $n \mapsto g^n$ from $\mathbb{Z}$ to $A_i/H_i$ is surjective.

Points of detail:

• The normality of $H_i$ in $A_i$ and the cyclicity of $A_i/H_i$ are asserted together: the statement is "there is a proof of normality such that the resulting quotient group is cyclic", which amounts to the conjunction "$H_i$ is normal in $A_i$, and the quotient is cyclic". The cyclicity claim cannot even be phrased without the normality, since it is a claim about the quotient's group structure.
• $H_i$ is literally described as the intersection $A_{i+1}\cap A_i$ viewed inside $A_i$, not as $A_{i+1}$ itself; the inclusion $A_{i+1} \le A_i$ is imposed separately, in the same clause.
• Cyclicity is stated via surjectivity of $n \mapsto g^n$ for $n$ ranging over all of $\mathbb{Z}$, so it covers both finite and infinite cyclic quotients. The trivial group is cyclic in this sense.
• Nothing requires the chain to be strictly decreasing: $A_{i+1} = A_i$ is allowed at any step (the quotient is then trivial, hence cyclic).
• Nothing requires any $A_i$ to be normal in $G$; normality is required only of each term inside its immediate predecessor.
• The degenerate case $t = 0$ is included. Then there is a single subgroup $A_0$, conditions 1 and 2 read $A_0 = G$ and $A_0 = \{1\}$ simultaneously, and condition 3 is vacuous (there are no indices $i$ with $0 \le i \le -1$). So $t = 0$ witnesses the property exactly when $G$ is trivial.
• $t$ is existentially quantified with no bound, and the family is an arbitrary function of the index, subject only to the listed conditions.

4. The lower central series

Given a group $G$ and a natural number $k$, this defines a subgroup of $G$, written $\gamma_k$ below. It is the lower central series of $G$, computed as the lower central series of the subgroup $G$ of itself, with the indexing

$$\gamma_0 \;=\; G, \qquad \gamma_{k+1} \;=\; [\,\gamma_k,\ G\,],$$

where for subgroups $H, K \le G$ the symbol $[H,K]$ denotes the subgroup generated by the set of commutators $\{\, hkh^{-1}k^{-1} \;:\; h \in H,\ k \in K \,\}$ (not merely that set of commutators).

Note the indexing: the series starts at $0$ with the whole group, so $\gamma_1 = [G,G]$ is the commutator subgroup, $\gamma_2 = [[G,G],G]$, and so on. (This is one index lower than the convention in which the whole group is called $\gamma_1$.)

5. The $k$-th lower central factor

Given a group $G$ and a natural number $k$, this defines a type, which carries a commutative group structure. With $\gamma_k$ as in §4, let

• $\mathrm{Ab}(\gamma_k) = \gamma_k / [\gamma_k,\gamma_k]$ be the abelianization of the group $\gamma_k$ (the quotient of $\gamma_k$ by its own commutator subgroup), and
• $\pi_k : \gamma_k \to \mathrm{Ab}(\gamma_k)$ be the canonical projection.

Let $N_k \le \gamma_k$ be the subgroup of $\gamma_k$ consisting of those $x \in \gamma_k$ with $x \in \gamma_{k+1}$ — that is, $\gamma_{k+1} \cap \gamma_k$ regarded as a subgroup of $\gamma_k$. Then the definition is the quotient group

$$\mathrm{Ab}(\gamma_k) \,\big/\, \pi_k(N_k),$$

the quotient of the abelianization of $\gamma_k$ by the image under $\pi_k$ of $N_k$. Since $\mathrm{Ab}(\gamma_k)$ is commutative, that image is automatically a normal subgroup and the quotient is a commutative group; no hypothesis is needed for this.

Two literal readings worth spelling out: the object quotiented is the abelianization of $\gamma_k$, not $\gamma_k$ itself; and what is divided out is the image of $\gamma_{k+1}\cap\gamma_k$ in that abelianization, not $\gamma_{k+1}$ itself. In particular at $k = 0$ this is $\mathrm{Ab}(G)$ divided by the image of $[G,G] \cap G$ in $\mathrm{Ab}(G)$.

6. The rank of the $k$-th lower central factor

Given a group $G$ and a natural number $k$, this defines a natural number: the rank, over the ring $\mathbb{Z}$, of the abelian group of §5 written additively. Writing that commutative group additively makes it a $\mathbb{Z}$-module in the canonical way (with $n \cdot x$ the $n$-fold sum of $x$), and the value is the natural-number rank of that module in the sense fixed at the top of this document: the supremum of the cardinalities of $\mathbb{Z}$-linearly independent subsets, turned into a natural number, and equal to $0$ if that supremum is infinite.

Consequences of that convention, present in the definition: a factor group that is entirely torsion (for example a finite group, or the trivial group) has rank $0$, and a factor group of infinite rank also has value $0$. The two are not distinguished.

7. First growth exponent

Given a group $G$, this defines a natural number:

$$\sum_{k=0}^{c-1} (k+1)\, r_k,$$

where $r_k$ is the rank of §6 and $c$ is the nilpotency class of $G$. The summation index $k$ runs over $0, 1, \dots, c-1$; the value $k = c$ is not included. All arithmetic is in the natural numbers.

The nilpotency class is defined as the least natural number $n$ for which the $n$-th term of the upper central series of $G$ equals $G$, if $G$ is nilpotent; if $G$ is not nilpotent it is assigned the junk value $0$. Consequently, for a non-nilpotent $G$ the sum here is empty and the definition yields $0$; the same happens for the trivial group, whose class is $0$.

8. Second growth exponent

Given a group $G$, this defines a natural number:

$$\sum_{k=0}^{c-1} 2^{k}\, r_k,$$

with $r_k$ and $c$ exactly as in §7: $r_k$ the rank of §6, $c$ the nilpotency class of $G$ with the junk value $0$ when $G$ is not nilpotent, the index $k$ running over $0,1,\dots,c-1$ and $k=c$ excluded, and all arithmetic — including $2^k$ — performed in the natural numbers. The $k=0$ term is $2^0 r_0 = r_0$.

This differs from §7 only in the coefficient: $2^k$ here in place of $k+1$ there. The two agree in the first two terms ($k = 0$ and $k = 1$) and differ from $k = 2$ onwards.