Read-back: growth_dichotomy_of_isPolycyclic

Preliminary vocabulary, as the statement uses it

Throughout, $\Gamma$ is a set carrying a group structure; nothing else is assumed about it (it may be finite or infinite, trivial or not). The group operation is written multiplicatively, with identity $1$.

Word balls and the counting function. For a subset $T \subseteq \Gamma$ and a natural number $n$, the ball of radius $n$ is

$$B_T(n) \;=\; \Bigl\{\, g \in \Gamma \;:\; \exists\, k \le n \text{ and } x_1,\dots,x_k \in \Gamma \text{ with } \bigl(x_j \in T \text{ or } x_j^{-1} \in T\bigr) \text{ for each } j, \text{ and } g = x_1 x_2 \cdots x_k \,\Bigr\}.$$

Three details of this definition matter. The condition on the letters is disjunctive: each letter must lie in $T$ or have its inverse in $T$, i.e. the letters are drawn from $T \cup T^{-1}$. The length condition is $\le n$, not $= n$; in particular the empty product is allowed, so $1 \in B_T(n)$ for every $n$, and $B_T(0) = \{1\}$. And the product $x_1 x_2 \cdots x_k$ is taken in the listed order.

For a finite subset $S \subseteq \Gamma$ the growth function is

$$\beta_S(m) \;=\; \#\, B_S(m) \in \mathbb{N},$$

the number of elements of the ball. The counting operation used is the natural-number cardinality, which by convention returns $0$ on an infinite set; that convention never bites here, because $S$ is finite and therefore each $B_S(m)$ is a finite set (it is the image of the finitely many words of length $\le m$ over the finite alphabet $S \cup S^{-1}$). So $\beta_S(m)$ is the honest cardinality, and $\beta_S(0) = 1$.

Generation. "$S$ generates $\Gamma$" means: the intersection of all subgroups of $\Gamma$ containing $S$ is $\Gamma$ itself.

Nilpotency class. For a group $H$, let $Z_0(H) \subseteq Z_1(H) \subseteq \cdots$ be the upper central series, defined by $Z_0(H) = \{1\}$ and $Z_{n+1}(H) = \{x \in H : [x,y] \in Z_n(H) \text{ for all } y \in H\}$, where $[x,y] = x y x^{-1} y^{-1}$. The group $H$ is nilpotent if $Z_n(H) = H$ for some $n$, and its nilpotency class $c(H)$ is the least such $n$. If $H$ is not nilpotent, then $c(H)$ is defined to be $0$ by convention (a junk value). Note also that $c(H) = 0$ when $H$ is the trivial group.

Lower central series and its ranks. For a group $H$ put $H_0 = H$ and $H_{k+1} = [H_k, H]$, the subgroup generated by all commutators $[p,q] = p q p^{-1} q^{-1}$ with $p \in H_k$ and $q \in H$. For each $k$ define the abelian group

$$F_k(H) \;=\; \frac{H_k / [H_k, H_k]}{\pi_k\bigl(H_{k+1} \cap H_k\bigr)},$$

where $\pi_k : H_k \to H_k/[H_k,H_k]$ is the canonical projection onto the abelianization and the subgroup divided out is the image under $\pi_k$ of $H_{k+1} \cap H_k$ (this intersection is how the definition literally views $H_{k+1}$ as a subgroup of $H_k$). Since $F_k(H)$ is abelian it is a $\mathbb{Z}$-module when written additively, and we set

$$r_k(H) \;=\; \text{the } \mathbb{Z}\text{-rank of } F_k(H),$$

where "rank" means: the supremum of the cardinalities of the $\mathbb{Z}$-linearly independent subsets of $F_k(H)$, converted to a natural number, with the convention that an infinite supremum is converted to $0$. (For a finitely generated abelian group this is the usual torsion-free rank; for a general abelian group it is the truncation just described, and it is $0$ whenever that supremum is infinite.)

The two exponents. For a group $H$, define the natural numbers

$$E_1(H) \;=\; \sum_{k=0}^{c(H)-1} (k+1)\, r_k(H), \qquad\qquad E_2(H) \;=\; \sum_{k=0}^{c(H)-1} 2^{k}\, r_k(H),$$

both sums being over $k \in \{0, 1, \dots, c(H)-1\}$, i.e. over $k < c(H)$. Note the indexing: the first weight is $k+1$ and the first summand is $k = 0$, and the second weight is $2^k$. If $c(H) = 0$ — which happens when $H$ is trivial and also when $H$ is not nilpotent — both sums are empty and $E_1(H) = E_2(H) = 0$.

Polynomial growth of degree at most $E$. For a natural number $E$, the group $\Gamma$ has polynomial growth of degree at most $E$ means: there exist a finite subset $S' \subseteq \Gamma$ that generates $\Gamma$ and a real number $c > 0$ such that $\beta_{S'}(m) \le c \, m^{E}$ for every natural $m \ge 1$. The generating set here is existentially quantified and is unrelated to any other generating set in the statement.

Exponential growth. $\Gamma$ has exponential growth means: there exist a finite subset $S'' \subseteq \Gamma$ that generates $\Gamma$ and a real number $c > 1$ such that $c^{n} \le \beta_{S''}(n)$ for every natural $n$, with no lower restriction on $n$; at $n = 0$ this reads $1 \le \beta_{S''}(0) = 1$. Again $S''$ is existentially quantified and unrelated to the other generating sets appearing.

Hypotheses

The statement is made for an arbitrary type $\Gamma$ (in an arbitrary universe) equipped with a group structure, and it takes three further hypotheses.

(H1) $\Gamma$ is polycyclic, in the following explicit sense: there exist a natural number $t$ and subgroups $A_0, A_1, \dots, A_t$ of $\Gamma$ (a family indexed by $\{0,1,\dots,t\}$) such that

• $A_0 = \Gamma$,
• $A_t = \{1\}$,
• for every $i \in \{0, 1, \dots, t-1\}$: $A_{i+1} \subseteq A_i$, and the subgroup $A_{i+1} \cap A_i$, viewed as a subgroup of $A_i$, is normal in $A_i$ and the quotient group $A_i / (A_{i+1} \cap A_i)$ is cyclic, meaning some single element $g$ of that quotient has the property that every element of the quotient is an integer power $g^{z}$, $z \in \mathbb{Z}$.

Two literal points. The normality requirement is phrased as the existence of a normality certificate, and the cyclicity of the quotient is asserted using that certificate; since normality is a property (not extra data), this amounts exactly to the conjunction "$A_{i+1}$ is normal in $A_i$ and the quotient is cyclic". And the subgroup divided out is written as $A_{i+1} \cap A_i$, which by the accompanying inclusion $A_{i+1} \subseteq A_i$ is just $A_{i+1}$. Degenerate case $t = 0$: the family is just $A_0$, and the first two conditions then require $\Gamma = A_0 = \{1\}$, so $t = 0$ is available exactly when $\Gamma$ is trivial; the third condition is vacuous. No claim is made that the $A_i$ are normal in $\Gamma$, nor that the chain is strictly decreasing.

(H2) $S$ is a finite subset of $\Gamma$. It is not assumed nonempty, and it is not assumed symmetric.

(H3) $S$ generates $\Gamma$.

Conclusion

The conclusion is the conjunction of the following two claims, (A) and (B). Both are asserted; neither is offered as an alternative to the other.

(A) For every nilpotent subgroup of finite index

For every subgroup $\Delta \subseteq \Gamma$ such that

• $\Delta$, regarded as a group in its own right, is nilpotent (nothing is assumed about how $\Delta$ sits inside $\Gamma$ beyond being a subgroup — in particular $\Delta$ is not assumed normal in $\Gamma$), and
• $\Delta$ has finite index in $\Gamma$, meaning the number of cosets in $\Gamma / \Delta$ is a nonzero natural number — equivalently, the coset space is finite,

the following two things hold.

(A1) A two-sided bound on the growth function of the given $S$. There exist real numbers $c_1, c_2$ with

$$0 < c_1 \qquad\text{and}\qquad c_1 \le c_2,$$

such that for every natural number $m$ with $m \ge 1$, both

$$c_1 \, m^{\,E_1(\Delta)} \;\le\; \beta_S(m) \qquad\text{and}\qquad \beta_S(m) \;\le\; c_2 \, m^{\,E_2(\Delta)} .$$

Here the powers are real numbers raised to natural-number exponents (repeated multiplication, with $x^0 = 1$), and $\beta_S(m)$ is the natural number above, read as a real number. The exponents $E_1(\Delta)$ and $E_2(\Delta)$ are computed from the lower central series of $\Delta$ and the nilpotency class of $\Delta$, while $\beta_S$ counts balls in $\Gamma$ with respect to the given generating set $S$. No compatibility between $S$ and $\Delta$ is assumed or asserted: $S$ need not lie in $\Delta$, and $\Delta$ need not be generated by anything related to $S$. The constants $c_1, c_2$ may depend on $\Delta$ (and on $\Gamma$ and $S$), since they are chosen inside the scope of the quantifier over $\Delta$. The condition $c_1 \le c_2$ is a relation between the two constants only; nothing is asserted relating $E_1(\Delta)$ and $E_2(\Delta)$, and the lower bound uses $E_1$ while the upper bound uses $E_2$.

(A2) A polynomial growth statement about $\Gamma$. $\Gamma$ has polynomial growth of degree at most $E_2(\Delta)$, in the sense defined above: there exist some finite generating subset $S'$ of $\Gamma$ and some real $c > 0$ with $\beta_{S'}(m) \le c\, m^{E_2(\Delta)}$ for all $m \ge 1$. This is a separate existential and does not have to be witnessed by the given $S$ or by the constant $c_2$ from (A1).

(B) If no nilpotent subgroup has finite index

If there is no subgroup $\Delta \subseteq \Gamma$ that is simultaneously nilpotent (as a group) and of finite index in $\Gamma$, then the following two things hold.

(B1) An exponential two-sided bound on the growth function of the given $S$. There exists a real number $v$ with $v > 1$ (strictly) such that for every natural $m \ge 1$, both

$$v^{m} \;\le\; \beta_S(m) \qquad\text{and}\qquad \beta_S(m) \;\le\; \bigl(\beta_S(1)\bigr)^{m} .$$

The upper bound's base is the count of the radius-one ball for the same $S$ — the number of elements of $\{1\} \cup S \cup S^{-1}$ — read as a real number and raised to the natural power $m$. The exponents on both sides are $m$ itself, not a multiple of $m$.

(B2) $\Gamma$ has exponential growth, in the sense defined above: there exist some finite generating subset $S''$ of $\Gamma$ and some real $c > 1$ with $c^n \le \beta_{S''}(n)$ for all naturals $n$, including $n = 0$. Again this existential need not be witnessed by the given $S$ or by the $v$ from (B1).

Degenerate and edge cases the quantifiers include

• Exactly one of (A) and (B) can have content. If some nilpotent finite-index subgroup of $\Gamma$ exists, the hypothesis of (B) is false and (B) holds vacuously. If none exists, the universal quantifier in (A) ranges over the empty collection and (A) holds vacuously. So for any particular $\Gamma$ one of the two conjuncts carries no information.

• (A) is unconditional. It is not placed under any hypothesis asserting that a nilpotent finite-index subgroup exists; it is a universally quantified claim that happens to be vacuous when there are none.

• The trivial subgroup is an admissible $\Delta$ when $\Gamma$ is finite. The trivial subgroup $\{1\}$ is nilpotent, and it has finite index precisely when $\Gamma$ is finite. Its nilpotency class is $0$, so $E_1(\{1\}) = E_2(\{1\}) = 0$ and the bounds of (A1) read $c_1 \le \beta_S(m) \le c_2$ for all $m \ge 1$, with $c_1 > 0$; (A2) then asserts polynomial growth of degree at most $0$, i.e. a constant bound $\beta_{S'}(m) \le c$ for some generating $S'$ and all $m \ge 1$. Correspondingly, the hypothesis of (B) can only be satisfied by an infinite $\Gamma$: no finite group satisfies it.

• $\Delta = \Gamma$ is an admissible $\Delta$ (it always has finite index), so when $\Gamma$ itself is nilpotent the claims of (A) apply with $\Delta = \Gamma$.

• Exponents can vanish for non-obvious reasons. $E_1(\Delta)$ and $E_2(\Delta)$ are $0$ whenever $c(\Delta) = 0$, and individual summands vanish whenever the corresponding rank $r_k(\Delta)$ is $0$ — which happens both when the factor $F_k(\Delta)$ is a torsion group and, by the truncation convention, when its supremum of independent-set cardinalities is infinite. The nilpotency hypothesis on $\Delta$ means the junk-value branch of the nilpotency class ($c(H) = 0$ for non-nilpotent $H$) is not reached for $\Delta$ itself, though the ranks $r_k(\Delta)$ carry their own truncation convention regardless.

• $\Gamma$ trivial. Then $S$ may be the empty set, (H3) holds, $\beta_S(m) = 1$ for all $m$, and (A) applies with $\Delta = \{1\} = \Gamma$ and both exponents $0$.

• $m = 0$ is excluded from (A1) and (B1) — both inner claims are quantified over $m \ge 1$ only — but $n = 0$ is included in the definition of exponential growth used by (B2).

• The polycyclicity hypothesis (H1) does not reappear in the conclusion; the conclusion mentions only $\Gamma$, $S$, subgroups of $\Gamma$, and the quantities defined above.