Read-back: growthFunction_freeAbelian_eq_and_bounds

The group that the statement is about

Fix a natural number $n$ (the statement quantifies over all $n \in \mathbb{N}$, including $n = 0$).

The ambient group, call it $G_n$, has as its underlying set all functions from $\{0, 1, \dots, n-1\}$ to $\mathbb{Z}$ — that is, all $n$-tuples of integers. Its group law is written multiplicatively throughout the statement, but it is defined to be componentwise integer addition:

$$(x \cdot y)(i) = x(i) + y(i), \qquad e(i) = 0, \qquad (x^{-1})(i) = -x(i)$$

for each coordinate $i$. So $G_n$ is the free abelian group of rank $n$, $\mathbb{Z}^n$, with additive notation relabelled as multiplicative notation. Every product, inverse, power and identity appearing below is to be read through this relabelling. When $n = 0$ the underlying set has exactly one element (the empty tuple), so $G_0$ is the trivial group.

The word ball and the growth function

For a subset $S \subseteq G_n$ and a natural number $m$, define the word ball

$$B(S,m) \;=\; \Bigl\{\, g \in G_n \;\Bigm|\; \exists\, k \in \mathbb{N},\ \exists\, x_1, \dots, x_k \in G_n \ \text{ such that }\ k \le m,\ \bigl(\forall j,\ x_j \in S \text{ or } x_j^{-1} \in S\bigr),\ \text{and } x_1 x_2 \cdots x_k = g \,\Bigr\}.$$

Points of detail that the definition fixes:

• The witnessing datum is a finite list $(x_1, \dots, x_k)$ of elements of $G_n$, so repetitions among the $x_j$ are allowed, and the constraint is on the list's length, namely $k \le m$ — a closed ball of radius $m$, not a sphere.
• The condition on each entry is $x_j \in S$ or $x_j^{-1} \in S$; equivalently each $x_j$ lies in $S \cup S^{-1}$. The set $S$ is not required to be symmetric, nor to omit the identity.
• The product is the right-nested product $x_1 \cdot \bigl(x_2 \cdot (\cdots \cdot (x_k \cdot e))\bigr)$, with the empty list ($k = 0$) having product $e$. Since $0 \le m$ for every $m$, the identity $e$ therefore belongs to $B(S,m)$ for every $m$, including $m = 0$. (In $G_n$ the group law is commutative and associative, so the nesting and the order of the factors do not affect which elements are obtained.)
• $B(S,m)$ is a set of group elements, not of words; distinct words with the same product are counted once.

For a finite subset $S$ of $G_n$ and a natural number $m$, the growth function is

$$\gamma_S(m) \;=\; \#\, B(S, m),$$

the number of elements of the word ball, returned as a natural number. The counting operation used is the one that is defined for an arbitrary set and, by convention, returns $0$ when the set is infinite; so $\gamma_S(m) = 0$ would be the value reported for an infinite ball. (The sets $S$ occurring in the statement are all finite.)

Generation and minimality

For a subset $X \subseteq G_n$, the subgroup generated by $X$ is the intersection of all subgroups of $G_n$ containing $X$, i.e. the smallest such subgroup. Saying that this subgroup is the whole group $G_n$ is what "$X$ generates $G_n$" means below.

The assertion

For every natural number $n$, and for every finite subset $T \subseteq G_n$ such that

1. $T$ generates $G_n$, and
2. (minimality) for every finite set $T'$ with $T' \subseteq T$ and $T' \neq T$, the subgroup generated by $T'$ is not the whole of $G_n$,

both of the following hold.

Part (a) — an exact formula for the minimal generating set $T$

For every natural number $m$ — including $m = 0$ —

$$\gamma_T(m) \;=\; \sum_{l=0}^{n} 2^{\,l} \binom{n}{l} \binom{m}{l}.$$

This is an equality of natural numbers; all of the arithmetic on the right-hand side takes place in $\mathbb{N}$. The index $l$ runs over $0, 1, \dots, n$ inclusive (that is, $n+1$ terms). Each summand is the natural number $\bigl(2^{\,l} \cdot \binom{n}{l}\bigr) \cdot \binom{m}{l}$, where $2^{\,l}$ is the $l$-th power of $2$ in $\mathbb{N}$ and both binomial coefficients are the total natural-number binomial coefficient, which takes the value $0$ whenever its lower index exceeds its upper index. Consequently the term indexed by $l$ vanishes as soon as $l > m$; in particular for $m = 0$ only the $l = 0$ term survives and the right-hand side equals $1$.

Part (b) — two-sided polynomial bounds for every generating set

For every finite subset $S \subseteq G_n$ such that $S$ generates $G_n$, there exist real numbers $c_1$ and $c_2$ satisfying

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

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

$$c_1 \, m^{\,n} \;\le\; \gamma_S(m) \quad\text{and}\quad \gamma_S(m) \;\le\; c_2 \, m^{\,n}.$$

Here $m$ and $\gamma_S(m)$ are natural numbers regarded as real numbers via the standard embedding, the inequalities are inequalities of real numbers, and $m^{\,n}$ is the $n$-th power of the real number $m$ with natural-number exponent $n$.

Points of logical precision:

• The quantifier order is: $S$ first, then $c_1, c_2$, then $m$. So the constants are allowed to depend on $S$ (and on $n$); nothing asserts a choice of constants uniform over the generating sets $S$.
• The constants are only asserted to exist; no uniqueness, no explicit value, and no optimality is claimed.
• The range $m \ge 1$ excludes $m = 0$; nothing is asserted about $\gamma_S(0)$ in part (b).
• The chain is $0 < c_1 \le c_2$ (strict at the left end, non-strict between the two constants), and both displayed bounds are non-strict ($\le$).
• Part (b) does not mention $T$ at all, and does not require $S$ to be minimal in the sense of hypothesis 2. It is asserted, however, only under hypotheses 1 and 2 about $T$ — those hypotheses are part of the ambient assumptions of the whole conjunction.

Degenerate and edge cases silently included

• $n = 0$. $G_0$ is the trivial group. Hypothesis 1 then holds for every finite $T$, while hypothesis 2 forces $T = \varnothing$: if $T$ were $\{e\}$, then $T' = \varnothing$ is a finite proper subset of $T$ that nevertheless generates the (trivial) whole group, contradicting hypothesis 2. The sum in part (a) reduces to the single term $l = 0$, whose value is $2^0 \binom{0}{0} \binom{m}{0} = 1$, so part (a) asserts $\gamma_\varnothing(m) = 1$ for all $m$. In part (b), $m^{\,0} = 1$, so the assertion becomes $c_1 \le \gamma_S(m) \le c_2$ with no dependence on $m$.
• $m = 0$ in part (a). Included by the universal quantifier; as noted, the right-hand side is then $1$.
• $T = \varnothing$ or $S = \varnothing$. Both are admissible finite sets as far as the types go; each is additionally subject to the requirement that it generate $G_n$. The word ball of the empty set is $\{e\}$ at every radius.
• Satisfiability of the hypotheses. Hypotheses 1 and 2 are constraints on $T$, and a reader should check they can be met. They can: for each $n$, the set of the $n$ standard basis tuples (the tuple with $1$ in coordinate $i$ and $0$ elsewhere, for $i = 0, \dots, n-1$) generates $G_n$, and removing any one of them leaves a set generating a proper subgroup. So neither hypothesis is impossible, and the assertion is not vacuous for any $n$.
• No finiteness or decidability assumptions beyond those recorded above are imposed: the only hypotheses in the statement are the two conditions on $T$, plus the generation condition on $S$ inside part (b). In particular no separate assumption of the form "$G_n$ is finitely generated" or "$T$ is nonempty" appears.

What the two parts do not jointly claim

Part (a) gives the exact count only for sets $T$ satisfying both hypothesis 1 and hypothesis 2; part (b) gives only two-sided bounds with unspecified constants, and gives them for all generating finite sets $S$, minimal or not. No exact formula is claimed for a non-minimal generating set, and no relation between the constants of part (b) and the polynomial of part (a) is asserted.