Grigorchuk Gap Conjecture

Grigorchuk Gap Conjecture

Definitions and mathematical statement

For a finite generating set $X$ of $G$, let $\gamma_{G,X}(n)$ count elements represented by words of length at most $n$ in $X\cup X^{-1}$. Write $f\preceq g$ if an integer $C\ge1$ gives $f(n)\le Cg(Cn)$ for every $n\ge1$, and $f\prec g$ when $f\preceq g$ but not $g\preceq f$. The conjecture is \[ \gamma_{G,X}\prec\exp(\sqrt n)\quad\Longrightarrow\quad \gamma_{G,X}(n)=O(n^d)\text{ for some }d. \] Equivalently the conclusion is virtual nilpotence: a finite-index subgroup is nilpotent. Strict comparison of growth classes is essential; an ordinary pointwise little-o comparison can hold between functions in the same growth class after rescaling the argument.

Formulation and concept references: [S1].

Short English statement

Is there a genuine gap between polynomial group growth and the growth class of the exponential of the square root?

Research attempt: scale comparisons and a polynomial-growth model

GPT-6 Astra Ultra, 27 September 2026. Status: UNRESOLVED.

The gap concerns growth classes under rescaling, not merely the size of a function at a fixed argument. I first verify that distinction and compute two polynomial-growth models, including a nonabelian one. I then test a possible route through doubling estimates and identify the precise structural implication that it lacks. The resulting calculations do not rule out an actual group with growth strictly between polynomials and the square-root exponential class.

The generating set does not change the issue.

If $X,Y$ are finite generating sets of $G$, let $L$ be the largest $Y$-word length of an element of $X\cup X^{-1}$. Then \[ B_X(n)\subseteq B_Y(Ln),\qquad \gamma_X(n)\le\gamma_Y(Ln). \] Interchanging $X,Y$ gives the reverse comparison. Thus the equivalence class used in the question is independent of the generating set. Constants in pointwise estimates can change, which is exactly why the rescaling convention cannot be dropped.

For $a>0$, the functions $e^{a\sqrt n}$ and $e^{\sqrt n}$ are equivalent: choosing an integer $C\ge\max(a^2,a^{-2},1)$ absorbs either coefficient by replacing $n$ with $Cn$. Nevertheless, if $0<a<1$, \[ e^{a\sqrt n}/e^{\sqrt n}\longrightarrow0. \] So a pointwise little-o estimate of this kind does not satisfy the strict-class hypothesis. By contrast, for $0<\alpha<1/2$ one has \[ e^{n^\alpha}\prec e^{\sqrt n}. \] The upper comparison is immediate. A reverse comparison would give $\sqrt n\le\log C+C^\alpha n^\alpha$ for all $n$, which fails after division by $\sqrt n$. This is the scale at which a prospective counterexample would matter.

An exact abelian ball count.

For $\mathbb Z^d$ with its standard generators, word length is the sum of the absolute values of the coordinates. To count points of length at most $n$, choose the $j$ nonzero coordinates, their signs, and positive absolute values with sum at most $n$. Stars and bars gives \[ \gamma_{\mathbb Z^d}(n) =\sum_{j=0}^d 2^j\binom dj\binom nj. \tag{1} \] The leading term is $(2^d/d!)n^d$. For $d=2$, this is $2n^2+2n+1$, not the square-box count $(2n+1)^2$. The difference is a useful check that the metric being counted is the word metric for the specified generating set.

Every polynomial is strictly below $e^{\sqrt n}$ in the required sense. Indeed $n^d\le C e^{\sqrt{Cn}}$ for a sufficiently large $C$, while an inequality $e^{\sqrt n}\le C(Cn)^d$ fails after taking logarithms. Thus these examples lie safely on the conjecture's proposed polynomial side.

A nonabelian calculation: the integer Heisenberg group.

Represent the group by triples $(a,b,c)\in\mathbb Z^3$ with multiplication \[ (a,b,c)(a',b',c')=(a+a',b+b',c+c'+ab'). \tag{2} \] Let $x=(1,0,0)$, $y=(0,1,0)$ and $z=(0,0,1)=[x,y]$, where the commutator convention is $[x,y]=xyx^{-1}y^{-1}$. A word of length at most $n$ has $|a|,|b|\le n$. Each multiplication by $y^{\pm1}$ changes $c$ by at most the current $|a|\le n$, while multiplication by $x^{\pm1}$ does not change it. Hence $|c|\le n^2$ and \[ \gamma(n)\le(2n+1)^2(2n^2+1)=O(n^4). \tag{3} \]

For the lower bound, central powers are cheap. For an integer $m\ge1$, put $a=\lfloor\sqrt m\rfloor$, $b=\lfloor m/a\rfloor$, and $r=m-ab$, so $0\le r<a$. Then \[ z^m=[x^a,y^b][x^r,y]. \tag{4} \] This word has length at most $2(a+b+r+1)\le6\sqrt m+6$; the case $m<0$ follows by inversion, and $m=0$ requires no letters. Thus $|z^m|\le6\sqrt{|m|}+6$ is a convenient uniform bound.

Every triple has the normal form \[ (a,b,c)=x^ay^bz^{c-ab}. \] For $|a|,|b|\le\varepsilon n$ and $|c|\le\varepsilon n^2$, \[ |(a,b,c)|\le2\varepsilon n +6\sqrt{\varepsilon+\varepsilon^2}\,n+6. \] Choose a fixed small $\varepsilon>0$ so that the coefficient of $n$ is less than one. For all sufficiently large $n$, the entire resulting box lies in the ball. It contains a positive constant times $n^4$ integer triples. Combined with $3$, this proves $\gamma(n)\asymp n^4$.

This calculation illustrates why the number of matrix coordinates is not the polynomial growth degree: the central coordinate has weight two. It also shows the role of commutators in converting a large central displacement into a short word. Neither feature is visible in a naive comparison with an abelian group of the same rank.

A sufficient doubling condition and its missing input.

Suppose a group satisfies a fixed doubling estimate \[ \gamma(2n)\le K\gamma(n)\qquad(n\ge n_0). \tag{5} \] Iteration gives $\gamma(2^j n_0)\le K^j\gamma(n_0)$. Taking $j$ just large enough that $n\le2^j n_0$ and using monotonicity yields \[ \gamma(n)=O\left(n^{\log_2 K}\right). \] So $5$ is a concrete sufficient route to the polynomial conclusion. Gromov's theorem then identifies the resulting groups as virtually nilpotent [E1]. The theorem is being used after obtaining polynomial growth, not as an argument that the weaker hypothesis already implies it.

The gap is that $\gamma\prec e^{\sqrt n}$ does not, as a statement about functions alone, imply a bounded doubling ratio. Consider \[ h(n)=\lceil e^{n^{1/3}}\rceil,\qquad n\ge0. \] It is increasing, integer valued, and submultiplicative. Indeed $(m+n)^{1/3}\le m^{1/3}+n^{1/3}$ and \[ \lceil ab\rceil\le\lceil a\rceil\lceil b\rceil \quad(a,b>0) \] give $h(m+n)\le h(m)h(n)$. Yet $h(2n)/h(n)$ tends to infinity, while $h\prec e^{\sqrt n}$ and $h$ grows faster than every polynomial.

This is explicitly a test function, not a claimed group growth function. In fact, its very first values impose additional issues if one tries to realize it with a particular generating set. Its purpose is narrower and rigorous: monotonicity, integer values, submultiplicativity and the strict growth comparison are insufficient to prove $5$. A successful group-theoretic argument must use stronger structure of balls, approximate subgroups, quotients, or some other feature absent from this list of functional inequalities.

Finite observations and quotient reductions.

Finite ball counts cannot determine an asymptotic growth class without an additional theorem. For every $R$, the cyclic group $\mathbb Z/m\mathbb Z$ with $m>2R+1$ and the infinite cyclic group have identical balls and counts up to radius $R$. Their eventual growths are bounded and linear respectively. This does not provide an intermediate-growth counterexample, but it proves that even polynomial degree is not generally read off from an arbitrarily long finite prefix.

For a quotient $G\to Q$ with the image generating set, every word descends, so $\gamma_Q(n)\le\gamma_G(n)$. Slow growth therefore passes to quotients. The reverse direction is unavailable: the trivial quotient has bounded growth for every group, including free groups. Any reduction that strips away normal subgroups must also control their growth and how extensions combine it. Polynomial growth of one quotient alone cannot close the gap.

There are important established structural cases. Grigorchuk's source [S1], Theorems 6.1 and 6.3, states the gap theorem for finitely generated residually finite-$p$ groups and more generally for residually nilpotent groups. Those hypotheses supply genuine algebraic input. Replacing "residually nilpotent" by an arbitrary finitely generated group is precisely an extension not justified by those theorems.

Verification and outcome.

The exact script checks $1$ by enumeration in small dimensions and verifies the Heisenberg multiplication, commutator identity $4$, and word-length upper bound on a finite range. These tests are attached to proofs and do not extrapolate a growth class from data. The completed partial work is the exact abelian count, the full $n^4$ Heisenberg bounds, and the doubling-to-polynomial implication. The first unresolved step in this route is extracting an appropriate structural bound from strict comparison with $e^{\sqrt n}$ for an arbitrary finitely generated group. No such extraction is proved here, so the universal gap conjecture remains unresolved.

Sources

• S1 Rostislav Grigorchuk, On the Gap Conjecture Concerning Group Growth $2012/2014$, Conjecture 1; Eberhard and Maini $2025$, Section 1 comparison convention. https://arxiv.org/pdf/1202.6044. Formulation source.
• E1 M. Gromov, Groups of polynomial growth and expanding maps, Publications Mathématiques de l'IHÉS 53 $1981$, 53--73. Used only for the implication from polynomial growth to virtual nilpotence. https://pmihes.centre-mersenne.org/articles/10.1007/BF02698687/.