Read-back: exists_const_polynomial_bounds_of_generating

The vocabulary the statement uses, written out

Two auxiliary notions occur in the statement. Neither is standard, so both are unfolded here in full; after this section they are used only through the descriptions given.

Balls of words. Let $\Gamma$ be a group, let $A \subseteq \Gamma$ be a subset, and let $n \in \mathbb{N}$. The word ball $B_A(n)$ is the set of all $g \in \Gamma$ for which there exists a finite list $x_1, x_2, \dots, x_k$ of elements of $\Gamma$ such that

• its length satisfies $k \le n$ (so lists shorter than $n$, and the empty list, are allowed);
• every entry $x_i$ satisfies $x_i \in A$ or $x_i^{-1} \in A$ — that is, every letter is drawn from the symmetrised alphabet $A \cup A^{-1}$; and
• the product of the entries, taken in the order in which they are listed, equals $g$:

$$x_1 \cdot \big(x_2 \cdot ( \cdots (x_k \cdot 1) \cdots )\big) \;=\; g .$$

The product is the group product in list order, left factor first; since no commutativity is assumed anywhere, this order is part of the definition. The empty list is permitted and its product is the identity, so $1 \in B_A(n)$ for every $n$, including $n = 0$. Letters may repeat, and the same element may be reachable by many lists. So $B_A(n)$ is the closed ball of radius $n$ around the identity in the word metric determined by the symmetrised alphabet $A \cup A^{-1}$.

The growth function. For a finite subset $A \subseteq \Gamma$ and $m \in \mathbb{N}$, write

$$\gamma_A(m) \;=\; \#\, B_A(m) \in \mathbb{N},$$

the number of elements of the word ball of radius $m$. The cardinality here is the natural-number-valued cardinality, which is defined for every set and returns $0$ when the set is infinite. That degenerate branch is never reached in this statement: because $A$ is finite, the alphabet $A \cup A^{-1}$ is finite, there are only finitely many lists of length at most $m$ over it, and $B_A(m)$ is the image of that finite collection of lists under the product map. Hence $\gamma_A(m)$ is an honest count, and $\gamma_A(m) \ge 1$ for all $m$, since the identity always lies in the ball.

Generation. "The subgroup generated by $A$ is all of $\Gamma$" means: the smallest subgroup of $\Gamma$ containing $A$ is $\Gamma$ itself. Equivalently, every element of $\Gamma$ is a product of finitely many elements of $A$ and inverses of elements of $A$ — no bound on the number of factors. Note that this is subgroup generation, so inverses are available for free.

What the statement asserts

Fix the following data.

1. A type $\Gamma$ — arbitrary, in an arbitrary universe — carrying a group structure. Nothing further is assumed of $\Gamma$: it is not assumed abelian, nilpotent, solvable, finite, or torsion-free, and it may be finite or infinite. (Finite generation is not assumed either, but it follows from hypothesis 3 below.)
2. Two finite subsets $S, T \subseteq \Gamma$. They are given as finite sets, with no multiplicities, and no relation between them is assumed: they may coincide, overlap, or be disjoint, and either may be empty.
3. The subgroup generated by $S$ is all of $\Gamma$.
4. The subgroup generated by $T$ is all of $\Gamma$.
5. Two real numbers $b_1, b_2$.
6. $0 < b_1$.
7. $b_1 \le b_2$ (hence also $0 < b_2$).
8. Two natural numbers $p, q$.
9. $p \le q$.
10. For every natural number $m$ with $m \ge 1$, both of the following inequalities hold, as inequalities between real numbers (the integer count $\gamma_T(m)$ and the integer $m$ are each read as real numbers in the usual way, and the exponent is a natural number, so $m^0 = 1$):

$$b_1 \, m^{\,p} \;\le\; \gamma_T(m) \qquad\text{and}\qquad \gamma_T(m) \;\le\; b_2 \, m^{\,q}.$$

Nothing is assumed at $m = 0$.

Under these assumptions the statement asserts:

There exist real numbers $c_1$ and $c_2$ such that

$$0 < c_1, \qquad c_1 \le c_2,$$

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

$$c_1 \, m^{\,p} \;\le\; \gamma_S(m) \qquad\text{and}\qquad \gamma_S(m) \;\le\; c_2 \, m^{\,q}.$$

Fine print

The quantifier order. The two constants are chosen once and then serve all $m \ge 1$: the universal quantifier over $m$ sits inside the existential over $c_1, c_2$. The constants may depend on everything fixed beforehand — on $\Gamma$, on $S$, on $T$, on $b_1, b_2$, on $p, q$, and on the hypotheses themselves.

Existence, not uniqueness. Mere existence of such a pair is asserted, not uniqueness, and no formula, bound, or method for producing $c_1, c_2$ from the given data is asserted. In particular nothing is claimed about the size of $c_1$ or $c_2$ relative to $b_1$ or $b_2$: the conclusion does not say one may take $c_1 = b_1$, or $c_2 = b_2$, or that $c_1$ and $c_2$ are bounded in terms of $b_1, b_2$ and the two alphabets in any stated way.

The exponents are unchanged. The exponents in the conclusion are the same natural numbers $p$ and $q$ as in the hypothesis. The statement transfers the two-sided polynomial bound from the alphabet $T$ to the alphabet $S$ keeping both exponents, changing only the two constants. The hypothesis concerns $T$ only and the conclusion concerns $S$ only.

The direction of each inequality. The lower bounds are $b_1 m^p \le \gamma_T(m)$ and $c_1 m^p \le \gamma_S(m)$, non-strict, with the multiple of the power on the small side; the upper bounds are $\gamma_T(m) \le b_2 m^q$ and $\gamma_S(m) \le c_2 m^q$, non-strict, with the multiple of the power on the large side. The positivity condition on the first constant is strict ($0 < b_1$, and $0 < c_1$ in the conclusion), while the comparison between the two constants is non-strict ($b_1 \le b_2$, and $c_1 \le c_2$ in the conclusion). Likewise $p \le q$ is non-strict, so $p = q$ is permitted, in which case hypothesis and conclusion each pin the growth function between two constant multiples of the same power.

The range of $m$. Both the hypothesis and the conclusion quantify over natural numbers $m \ge 1$ and say nothing whatsoever about $m = 0$. This matters, because at $m = 0$ the ball is $\{1\}$, so $\gamma_A(0) = 1$, while $0^p$ is $0$ for $p \ge 1$ and $1$ for $p = 0$; the excluded case is exactly where the upper bound would fail for $q \ge 1$.

Degenerate exponents. $p = 0$ is permitted, and then $m^p = 1$ and the lower bounds read $b_1 \le \gamma_T(m)$ and $c_1 \le \gamma_S(m)$. Likewise $q = 0$ is permitted, which combined with $p \le q$ forces $p = 0$; the hypothesis then says the growth function of $T$ is bounded between the two constants $b_1$ and $b_2$ for all $m \ge 1$, and the conclusion says the growth function of $S$ is bounded between two constants as well.

Empty alphabets. Either $S$ or $T$ may be empty as a finite set. The subgroup generated by the empty set is the trivial subgroup, so the generation hypothesis then forces $\Gamma$ to be the trivial group; in that situation every ball is $\{1\}$ and both growth functions are identically $1$, and the hypothesis at large $m$ additionally forces $p = 0$. This is a constrained but not contradictory corner of the statement.

The hypotheses are satisfiable. No hypothesis is vacuous or impossible. For instance, taking $\Gamma = \mathbb{Z}$ and $S = T = \{1\}$: the ball of radius $m$ is $\{-m, \dots, m\}$, so $\gamma_T(m) = 2m + 1$, and the choices $p = q = 1$, $b_1 = 2$, $b_2 = 3$ satisfy $2m \le 2m+1 \le 3m$ for all $m \ge 1$, with $\{1\}$ generating $\mathbb{Z}$ as a group. So the implication has non-trivial instances; conversely the hypothesis is a real restriction, since it requires $\Gamma$ to have a finite generating set whose growth function is bounded above by a constant multiple of $m^q$.

Nothing about limits or rates. The statement is purely a pair of inequalities holding for all $m \ge 1$. It does not mention limits, asymptotic equivalence, growth types up to quasi-isometry, or any comparison of growth functions of two different alphabets pointwise — in particular it does not assert $\gamma_S(m) \le \gamma_T(Cm)$ or any such change-of-alphabet inequality, only the existence of the two constants described above.