Growth of finitely presented groups

Growth of finitely presented groups

Definitions and mathematical statement

For a finitely generated group $G$ with finite symmetric generating set $S$, let \[ \gamma_{G,S}(n)=\#\{g\in G:|g|_S\le n\}, \] where $|g|_S$ is the minimum word length. Intermediate growth means simultaneously \[ \lim_{n\to\infty}\frac{\log\gamma_{G,S}(n)}n=0, \qquad\text{and}\qquad \nexists C,d:\gamma_{G,S}(n)\le C(n+1)^d\text{ for all }n. \] The existence problem asks for such a $G$ that also has a finite presentation, with finitely many defining relations. These growth properties are unchanged on changing the finite generating set. No precise intermediate rate is prescribed, and an infinitely related finitely generated construction does not meet the extra finite-presentation requirement.

Formulation and concept references: [S1].

Short English statement

Does a finitely presented group exist whose growth is slower than exponential but faster than every polynomial bound?

Research attempt

Scope and source audit (27 September 2026).

The requested example must satisfy three separate conditions: finite generation, finite presentation, and the two growth conditions in the statement. A finite recursive description or a finite-state automaton is not the same as a finite list of defining relations. The source survey [S1] explicitly distinguishes these notions and the known intermediate-growth constructions from the finite-presentation problem. Its full text was inspected; no general resolution is imported here.

The phrase "faster than every polynomial" is used in the precise sense printed in the statement: no polynomial is a global upper bound. We do not silently replace it by a stronger regularity assertion about a limit for every quotient $\gamma(n)/n^d$. Growth functions may have substantial changes of scale, so all estimates below keep their quantifiers visible.

The attack examines two possible routes: truncate the relations of a known intermediate-growth group, or place it inside a finitely presented amenable group. Exact growth comparisons and explicit examples show why neither route gives the required conclusion without additional uniform estimates. We also prove the amenability consequence of subexponential growth and a useful local-stabilization theorem for increasing relator lists.

Submultiplicativity gives an actual exponential growth rate.

Let $B(n)$ be the word ball and $\gamma(n)=|B(n)|$. Every word of length at most $n+m$ splits into a prefix of length at most $n$ and a suffix of length at most $m$, so \[ B(n+m)\subseteq B(n)B(m),\qquad \gamma(n+m)\le\gamma(n)\gamma(m). \tag{374.1} \] Put $a_n=\log\gamma(n)$. Then $a_{n+m}\le a_n+a_m$. A direct proof of the subadditive limit formula is short. For a fixed $k\ge1$, write $n=qk+r$, $0\le r<k$. Then $a_n\le q a_k+a_r$, so $\limsup a_n/n\le a_k/k$. Taking the infimum over $k$, and comparing with the automatic lower bound by that infimum, gives \[ h(G,S)=\lim_{n\to\infty}\frac{\log\gamma(n)}n =\inf_{n\ge1}\frac{\log\gamma(n)}n\ge0. \tag{374.2} \] Thus the first growth condition is equivalent to $h(G,S)=0$. For each $\varepsilon>0$, it implies $\gamma(n)\le C_\varepsilon e^{\varepsilon n}$ for all $n$, with a finite constant absorbing the initial segment. It does not give a single polynomial bound: the constant and the cutoff may deteriorate as $\varepsilon\downarrow0$.

Changing generators preserves both requested conditions.

For two finite symmetric generating sets $S,T$, there are finite constants $L,L'$ such that each generator of $S$ has $T$-length at most $L$ and each generator of $T$ has $S$-length at most $L'$. Replacing letters in words gives \[ \gamma_{G,S}(n)\le\gamma_{G,T}(Ln),\qquad \gamma_{G,T}(n)\le\gamma_{G,S}(L'n). \tag{374.3} \] If one growth rate is zero, these inequalities force the other to be zero by $374.2$. A polynomial upper bound on either side similarly transfers to the other after changing its constant. Hence absence of such a bound also transfers. No equivalence of exact pointwise formulas or of leading constants is being asserted.

The same argument gives useful one-sided comparisons for maps. A quotient generated by the images of $S$ has at most $\gamma_{G,S}(n)$ elements in its radius-$n$ ball. A finitely generated subgroup with generators of ambient length at most $L$ has intrinsic growth at most $\gamma_{G,S}(Ln)$. The latter says that a group containing an intermediate-growth subgroup cannot have polynomial growth. It gives no subexponential upper bound on the larger group.

Finite-index passage can be controlled on both sides.

Let $H\le G$ have finite index $m$, and choose representatives $r$ for the right cosets $Hg$, including $1$. Let each representative have $S$-length at most $L$. The finite Schreier generating set for $H$ consists of the nonidentity elements \[ t=r s(r')^{-1},\qquad Hr s=Hr',\quad s\in S. \] It can be taken symmetric and each such generator has ambient length at most $2L+1$. Reading a word one letter at a time rewrites its value as a product of at most its length many Schreier generators followed by one representative. For elements of $H$ the final representative is $1$. Thus these elements really generate $H$, and \[ \gamma_{H,T}(n)\le\gamma_{G,S}((2L+1)n),\qquad \gamma_{G,S}(n)\le m\gamma_{H,T}(n). \tag{374.4} \] The second inequality follows by counting the final representative and the preceding Schreier word; uniqueness is not needed for this upper bound. Subexponential growth and polynomial boundedness therefore pass in both directions across finite index. This gives a valid way to move an example between commensurable groups, but does not turn an arbitrary infinite-index embedding into such a comparison.

Two fully explicit finitely presented boundary classes.

The group $\mathbb Z^d$ has the finite presentation with $d$ generators and all pairwise commutator relations. With the standard generators, word length is the $\ell^1$ norm. Hence for $d\ge1$, \[ (2\lfloor n/d\rfloor+1)^d \le\gamma_{\mathbb Z^d}(n)\le(2n+1)^d. \] This is polynomial growth, so it fails the second requested condition. Finite groups also fail it, since their growth is bounded.

The free group of rank $r\ge2$ has a finite presentation with no relators. Its nonidentity reduced words of length $j$ number $2r(2r-1)^{j-1}$: choose the first letter freely and forbid only the inverse of the preceding letter thereafter. Thus \[ \gamma_{F_r}(n)=1+2r\sum_{j=1}^n(2r-1)^{j-1}, \qquad h(F_r,S)=\log(2r-1)>0. \] It fails the first condition. These elementary examples show that a finite relator list by itself allows both familiar extremes, while locating neither an intermediate construction nor an obstruction to it.

Subexponential growth supplies Følner sets.

Proposition 374.1. Every finitely generated group with $h(G,S)=0$ is amenable.

Proof. For every $\eta>0$ there are arbitrarily large integers $n$ with $\gamma(n+1)\le(1+\eta)\gamma(n)$. Otherwise for all sufficiently large $n$ the ratio would exceed $1+\eta$, and iterating would give positive exponential rate, contrary to $374.2$.

For a generator $s$, both $sB(n)$ and $B(n)$ lie in $B(n+1)$ and have equal cardinality. Therefore \[ \frac{|sB(n)\mathbin\triangle B(n)|}{|B(n)|} \le2\frac{\gamma(n+1)-\gamma(n)}{\gamma(n)}. \tag{374.5} \] Choose $n_j\to\infty$ with this ratio of consecutive ball sizes at most $1+1/j$. The normalized averages on $B(n_j)$ are positive normalized functionals on $\ell^\infty(G)$. By weak-star compactness of the dual unit ball, take a convergent subnet. Estimate $374.5$ makes its limit invariant under every generator, hence under every finite product of generators. The limit is an invariant mean. $\square$

Only a sequence of good radii is needed. We did not assume that $\gamma(n+1)/\gamma(n)$ tends to one at every radius. This is an important distinction for attempts based on observed local growth. The weak-star compactness passage proves existence of a mean, not an efficient algorithm for testing amenability from a presentation.

Amenability alone leaves exponential growth possible.

Consider the lamplighter group $L=(\bigoplus_{\mathbb Z}C_2)\rtimes\mathbb Z$. Write elements as $(f,k)$, with finitely supported binary functions $f$, and multiply by \[ (f,k)(g,l)=(f+\operatorname{shift}_k g,k+l). \] Let $a$ toggle the lamp at zero and let $t$ move the cursor one step. For each binary string $(\varepsilon_0,\ldots,\varepsilon_{m-1})$, the word \[ a^{\varepsilon_0}t\,a^{\varepsilon_1}t\cdots a^{\varepsilon_{m-1}}t \] has length at most $2m$, ends with cursor $m$, and records those $m$ lamp choices at distinct sites. The resulting $2^m$ elements are distinct. Thus $\gamma_L(2m)\ge2^m$, implying positive exponential growth rate by monotonicity and $374.2$.

Nevertheless it is amenable by explicit Følner sets. Let $F_m$ consist of configurations supported in $[-m,m]$ with cursor also in $[-m,m]$. Its size is $(2m+1)2^{2m+1}$. Right multiplication by $a$ preserves $F_m$, because it toggles the lamp at the current cursor. Right multiplication by $t$ or $t^{-1}$ changes only the allowed cursor interval, so \[ |F_m t\mathbin\triangle F_m|/|F_m|=2/(2m+1). \] Right averages therefore give a right-invariant mean, and inversion converts it to a left-invariant one. This proves amenability directly.

The example is used only to disprove the implication "amenable implies subexponential". It is not offered as a finitely presented candidate. In particular a finite-state or finite-generator description of this wreath product is not treated as a finite presentation.

A finite presentation can already permit an exponential semigroup.

For another exact growth test, take \[ B=\langle a,t\mid tat^{-1}=a^2\rangle. \]

Define affine transformations of the real line by $a(x)=x+1$ and $t(x)=2x$. They satisfy the relation, so give a homomorphism from $B$ to the affine group. The $2^m$ words \[ a^{\varepsilon_0}t\,a^{\varepsilon_1}t\cdots a^{\varepsilon_{m-1}}t \] act as $x\mapsto2^m x+b$, where $b=\sum_{i=0}^{m-1}2^i\varepsilon_i$ under right-to-left composition. They have distinct translation coefficients and length at most $2m$. Thus this finitely presented group also has exponential growth. Faithfulness of the entire affine representation is not needed: different images already certify different group elements.

This calculation is a useful adversarial test for constructions involving an ascending conjugation relation. Such a relation can encode a finite recursive scheme, but it may also create exponentially many independently addressable choices. Compressing infinitely many descriptions into a short presentation is not automatically compatible with a subexponential upper bound.

Truncating an infinite relation list reverses the useful upper bound.

Suppose a finitely generated group is given by an infinite presentation \[ G=F(S)/\langle\!\langle R_1,R_2,\ldots\rangle\!\rangle, \qquad G_m=F(S)/\langle\!\langle R_1,\ldots,R_m\rangle\!\rangle. \] Every $G_m$ is finitely presented and maps onto $G$. Consequently \[ \gamma_G(n)\le\gamma_{G_m}(n) \quad\text{for every }m,n. \tag{374.6} \] If $G$ has no polynomial growth bound, neither does any $G_m$; otherwise that bound would descend to $G$. This successfully transfers the superpolynomial side of the desired example. It transfers the subexponential side in the wrong direction: an upper bound for $G$ says nothing about an upper bound for its larger approximants $G_m$.

There is a genuine local stabilization theorem, but its quantifiers are weaker than the needed global estimate. Lemma 374.2. For each fixed radius $R$, there exists $m_R$ such that the marked radius-$R$ balls in $G_m$ and $G$ agree for all $m\ge m_R$.

Proof. Two words of length at most $R+1$ are equal in $G$ exactly when their quotient word, of length at most $2R+2$, belongs to the normal closure of the whole relator set. Each such membership has a finite expression as a product of conjugates of relators and inverses. Only finitely many relators occur in that expression. There are finitely many pairs of words of length at most $R+1$. Choose $m_R$ large enough to include the relators in an expression for every pair that is equal in $G$. Every such equality then holds in $G_m$. Conversely every equality in $G_m$ holds in its quotient $G$. This proves equality of the ball identifications and their marked edge incidences wherever the edges remain in the ball: an edge from $u$ to $v$ labeled $s$ tests the equality $us=v$, and $us$ has length at most $R+1$.$\square$

The lemma does not give one finite $m$ that works at all radii. Even if $m_R$ were computable, replacing $m$ by a radius-dependent value would produce a sequence of groups rather than one finitely presented group with the required growth estimate.

Exactly which uniform estimate would make truncation succeed.

Suppose $G$ has intermediate growth and, for some fixed $m$, one can prove \[ \forall\varepsilon>0\ \exists C_\varepsilon<\infty\ \forall n:\qquad\gamma_{G_m}(n)\le C_\varepsilon e^{\varepsilon n}. \tag{374.7} \] Then $374.2$ gives subexponential growth of $G_m$, while $374.6$ excludes any polynomial upper bound for it. Since $G_m$ is finitely presented, this would solve the existence problem. The entire difficulty of that route is therefore concentrated in proving $374.7$ for one fixed truncation, not in the formal passage to a finite presentation.

A family of estimates only for $n\le R_m$ with $R_m\to\infty$ does not have the quantifier order in $374.7$. Nor does an estimate with exponential rate $\varepsilon_m\downarrow0$ give a member of rate zero: every $\varepsilon_m$ may remain positive. A limit group can have zero rate even though each fixed approximant still grows exponentially. No continuity theorem ruling out this possibility is proved or assumed here.

Subgroup embeddings and quotients have different failures.

If an intermediate-growth group embeds into a finitely presented group $H$, the comparison after $374.3$ rules out polynomial growth of $H$. But $H$ can have many more elements in its balls, so subexponential upper bounds do not transfer upward. Assuming $H$ amenable only provides the insufficient condition exposed by the lamplighter example. Additional distortion estimates would control the embedded subgroup's metric but would still not count all elements outside it.

In the other direction, taking a quotient of a finitely presented group preserves finite presentation only when the new normal subgroup is finitely normally generated. An infinitely related quotient can have the desired growth without satisfying this finiteness condition. The normal-closure expression for each individual word is finite, but a single finite list generating all extra relations is a different assertion. Lemma 374.2 makes the distinction explicit.

Diagnostics and outcome.

Exact finite checks count reduced free words, integer lattice balls, and the distinct affine images in the exponential diagnostic. They also enumerate lamp configurations to verify the stated Følner boundary ratios. These tests establish finite formulas and expose specific failed implications; no finite collection of growth values determines whether one presentation satisfies both asymptotic conditions.

Outcome: UNRESOLVED. The attempt proves the generator and finite-index invariances, the amenability consequence, and the local stabilization lemma with its exact quantifiers. It identifies a sufficient uniform bound for a finite truncation and why embeddings or amenability do not replace that bound. No fixed finitely presented group with a proved zero exponential rate and absence of every polynomial upper bound is constructed, and no general impossibility theorem is obtained.

Sources

• S1 R. Grigorchuk, Milnor's Problem on the Growth of Groups and its Consequences, arXiv:1111.0512 (2011, revised 2013). https://ar5iv.labs.arxiv.org/html/1111.0512. Formulation source.