Read-back: four definitions on the growth of a group

Throughout, $G$ is a group (an arbitrary type equipped with a group structure; no further assumptions, so $G$ may be trivial, finite, infinite, or not finitely generated). Group multiplication is written $xy$, the identity $1$, and the inverse $x^{-1}$.

1. The word ball $B_S(n)$

For any subset $S \subseteq G$ (not required to be finite, symmetric, generating, or non-empty) and any natural number $n \in \{0, 1, 2, \dots\}$, the word ball $B_S(n)$ is the following subset of $G$:

$$B_S(n) \;=\; \bigl\{\, g \in G \;:\; \text{there is a finite sequence } (x_1, \dots, x_k) \text{ of elements of } G \text{ with } k \le n,\ \text{each } x_i \in S \text{ or } x_i^{-1} \in S,\ \text{and } x_1 x_2 \cdots x_k = g \,\bigr\}.$$

In words: $B_S(n)$ is the set of all products of at most $n$ factors, each factor taken from $S \cup S^{-1}$ (where $S^{-1} = \{s^{-1} : s \in S\}$). The product is taken in the listed order, left to right (formally it is computed as $x_1 (x_2 (\cdots (x_k \cdot 1)))$, which by associativity is the ordinary product $x_1 x_2 \cdots x_k$).

Edge cases the definition includes:

• The empty sequence ($k = 0$) is allowed for every $n$, and its product is $1$. So $1 \in B_S(n)$ for every $n$ and every $S$, even when $S$ is empty; and $B_S(0) = \{1\}$.
• The length condition is $k \le n$, not $k = n$; so $B_S(n) \subseteq B_S(n+1)$.
• Nothing requires $S$ to be finite here; the definition is stated for an arbitrary subset of $G$.

2. "Has exponential growth"

$G$ has exponential growth means:

There exists a finite subset $S \subseteq G$ such that

(i) the subgroup of $G$ generated by $S$ (the smallest subgroup of $G$ containing $S$) is all of $G$; and

(ii) there exists a real number $c$ with $1 < c$ such that for every natural number $n \ge 0$,

$$c^{\,n} \;\le\; \#B_S(n),$$

where $\#B_S(n)$ is the number of elements of the word ball $B_S(n)$ defined above, regarded as a real number.

Points of precision:

• The quantifier structure is: $\exists S$ finite generating, $\exists c > 1$, $\forall n$. In particular the property is asserted for some finite generating set, and both $S$ and $c$ are chosen before $n$.
• The inequality is non-strict ($\le$) and is required for all $n$ including $n = 0$, where it reads $1 \le \#B_S(0) = 1$.
• $c^n$ is the $n$-th power of the real number $c$ (with $c^0 = 1$).
• $\#B_S(n)$ is a natural-number cardinality with the convention that an infinite set has cardinality $0$. Because $S$ is finite, every element of $B_S(n)$ is a product of at most $n$ factors from the finite set $S \cup S^{-1}$, so $B_S(n)$ is finite and this convention is not triggered.
• If $G$ is not generated by any finite subset, then no $S$ satisfies (i), and the property is false for $G$.

3. "Is exponentially bounded"

$G$ is exponentially bounded means:

There exists a finite subset $S \subseteq G$ such that

(i) the subgroup of $G$ generated by $S$ is all of $G$; and

(ii) for every real number $c$ with $1 < c$, there exists a natural number $N$ such that for every natural number $n$ with $n \ge N$,

$$\#B_S(n) \;\le\; c^{\,n}.$$

Points of precision:

• The quantifier structure is: $\exists S$ finite generating, $\forall c > 1$, $\exists N$, $\forall n \ge N$. The finite generating set $S$ is fixed first and must work for all $c > 1$ simultaneously; the threshold $N$ may depend on $c$.
• The inequality is non-strict ($\le$), in the direction "cardinality of the ball is at most $c^n$", and is only required for $n \ge N$; nothing is asserted for $n < N$.
• "$n \ge N$" means $N \le n$; $n = N$ is included.
• As in the previous definition, $\#B_S(n)$ is the natural-number cardinality (convention: $0$ for an infinite set, which does not arise since $S$ is finite), and $c^n$ is the real power.
• If $G$ is not generated by any finite subset, the property is false for $G$.
• Note that this is not the condition "some exponential $c^n$ bounds the ball"; it is the condition that every exponential $c^n$ with base $c > 1$ eventually bounds the ball.

4. "Has a free subsemigroup of rank two"

$G$ has a free subsemigroup of rank two means:

There exist elements $a, b \in G$ such that the map

$$\varphi \colon \{\text{finite words in the two letters } 0, 1\} \;\longrightarrow\; G$$

is injective, where $\varphi$ sends a word $i_1 i_2 \cdots i_k$ ($k \ge 0$, each $i_j \in \{0,1\}$) to the product $x_{i_1} x_{i_2} \cdots x_{i_k}$ with $x_0 = a$ and $x_1 = b$; the empty word ($k = 0$) is sent to $1$.

Equivalently: whenever two words $u, v$ in the letters $\{0, 1\}$ (including the empty word) have $\varphi(u) = \varphi(v)$ in $G$, then $u = v$ as words.

Points of precision:

• The domain is the free monoid on two letters, i.e. the set of all finite words including the empty word, with concatenation as multiplication; $\varphi$ is the monoid homomorphism determined by $0 \mapsto a$, $1 \mapsto b$. Consequently injectivity includes the requirement that no non-empty word in $a, b$ equals $1$ (since the empty word maps to $1$), in addition to distinct non-empty words giving distinct elements.
• Only positive words are considered: the letters map to $a$ and $b$, never to $a^{-1}$ or $b^{-1}$.
• The existential does not explicitly require $a \ne b$; but if $a = b$ then the one-letter words $0$ and $1$ have the same image, so injectivity fails. Likewise $a = 1$ or $b = 1$ makes injectivity fail (the one-letter word would collide with the empty word). So in effect $a$ and $b$ are distinct non-identity elements.
• Nothing is asserted about the subgroup generated by $a, b$, only about the set of positive products.