Uniform finite presentation for groups of polynomial growth

Uniform finite presentation for groups of polynomial growth, Discrete Analysis 2025:1, 29 pp.

Let $G$ be a finitely generated infinite group with generators $a_1,\dots,a_k$. The ball of radius $r$ in $G$ is defined to be the set of all elements of $G$ that can be written as words of length at most $r$ in $a_1,\dots,a_k$ and their inverses, and the growth rate of $G$ with respect to $a_1,\dots,a_k$ is defined to be the function that takes $r$ to the size of the ball of radius $r$. For example, the growth rate of the free Abelian group on $k$ generators is roughly $(2r)^k/k!$ (with respect to those generators), and the growth rate of the free group on $k$ generators is $2k+2k(2k-1)+2k(2k-1)^2+\dots+2k(2k-1)^{r-1}$.

It can be shown without too much difficulty that the growth rate does not depend very strongly on the generating set chosen: for instance, if the growth rate is within a constant factor of a polynomial for one set of generators, it will be within a constant factor of the same polynomial for any other set of generators. In particular, the following notion is well defined: a group is of polynomial growth if for some (and hence every) set of generators the growth rate is bounded above by some polynomial.

A famous theorem of Gromov, proved in 1981, states that a finitely generated group is of polynomial growth if and only if it is virtually nilpotent, which means that it has a nilpotent subgroup of finite index. (The “if” part of this statement is not trivial, but it is much easier, and was proved in 1968.) A consequence of this theorem is that groups of polynomial growth are finitely presented – that is, they have a presentation with a finite number of relations. Note that saying that a group $G$ with generators $x_1,\dots,x_k$ is finitely presented is equivalent to saying that there exists $n$ such that the set of relations of length at most $n$ that hold among $x_1,\dots,x_k$ gives a presentation for $G$.

This paper is interested in a quantitative version of the fact that groups of polynomial growth are finitely presented. As such, it fits into a general programme of obtaining quantitative versions of results connected with Gromov’s theorem, of which a famous example is a theorem of Breuillard, Green and Tao, which yields a quantitative version of Gromov’s theorem itself.

What does this mean? Well, if $B_r$ is the ball of radius $r$ and $|B_r|$ grows like a polynomial of degree $d$, then $|B_{Cr}|$ will be around $C^d|B_r|$. It turns out that a convenient quantitative notion of polynomial growth is that $|B_{3r}|\leq K|B_r|$ for some sufficiently large $r$. We shall not state the Breuillard-Green-Tao theorem here (it is stated in the paper on page 2), but in broad terms it implies that for every $K$ there exist $r_0$ and $C$ such that if $|B_{3r}|\leq K|B_r|$ for some $r\geq r_0$, then $|B_{mr}|\leq m^C|B_r|$ for every $m$, and the group satisfies a quantitative version of the virtual nilpotency property.

This paper does something similar with the property of being finitely presented. Let $G$ be a group with a symmetric set of generators $x_1,\dots,x_k$ and let $R_s$ be the set of words in $x_1,\dots,x_k$ of length at most $s$ that yield the identity in $G$. Then as commented above, the statement that $G$ is finitely presented is the statement that for some $s$ the words in $R_s$ give a presentation of $G$, or equivalently that $F_k/\langle\langle R_s\rangle\rangle\cong G$, where $F_k$ is the free group on $x_1,\dots,x_k$ and $\langle\langle R_s\rangle\rangle$ is the normal subgroup of $F_k$ generated by $R_s$. This in turn is equivalent to the statement that the sequence of normal subgroups $\langle\langle R_s\rangle\rangle$ is eventually constant.

The main result of this paper is to make this statement uniform in a certain sense. The statement is that for every $K$ and $k$ there exist $r_0$ and $C$ such that if $G$ has $k$ generators and $|B_{3r}|\leq K|B_r|$ for some $r\geq r_0$, then there are at most $C$ integers $n\geq\log_2r$ for which $\langle\langle R_{2^{n+1}}\rangle\rangle\ne\langle\langle R_{2^n}\rangle\rangle$. That is, if we say that $G$ has a new relation on scale $n$ if $\langle\langle R_{2^{n+1}}\rangle\rangle\ne\langle\langle R_{2^n}\rangle\rangle$, then beyond $r_0$ there are at most $C$ scales on which $G$ has a new relation.

This result has been strengthened in a subsequent paper of Romain Tessera and Matthew Tointon. However, the proof in this paper is considerably shorter.

One might think of asking for more, namely an upper bound for the scale on which the last new relation appears. However, as the authors point out, simple examples show that that is too much to ask for. The example they give is $\prod_{i=1}^k\mathbb Z/n_i\mathbb Z$, with the obvious generators, which has a new relation on scale $\log_2 n_i$ (give or take integer parts) for each $i$. Note that the number of scales at which new relations appear is $k$, so very nicely bounded in terms of $k$ and $K$ (which is around $3^k$), but nothing can be said about the sizes of those scales.

The main result is interesting in itself, but it is proved with a major application in mind, known as Schramm’s locality conjecture, which the authors prove in another paper. This conjecture concerns percolation in vertex-transitive graphs, and states the following. Let $G$ be an infinite connected graph and let $p\in[0,1]$. Now choose a random subset of the edges of $G$, by picking each edge with probability $p$, with all choices independent. We are then interested in whether the resulting graph contains an infinite component. The critical probability of $G$ is defined to be the infimum over all $p$ such that there is an infinite component with probability 1. Typically, one studies vertex-transitive graphs (that is, graphs for which the automorphism group acts transitively on the vertices), in which case there is an infinite component with probability 1 if and only if for every vertex $x$ there is a positive probability that $x$ is contained in an infinite component.

Schramm conjectured that the critical probability should depend only on the “local structure” of $G$, in the following sense. Let $(G_n)$ be a sequence of vertex transitive graphs, each with critical probability less than 1, that converges to a vertex-transitive connected graph $G$. Then the critical probabilities of the graphs $G_n$ converge to the critical probability of $G$. Here the notion of convergence for the graphs is that for every $r$ there exists $n_0$ such that for every $n\geq n_0$ the ball of radius $r$ in $G_n$ is isomorphic to the ball of radius $r$ in $G$.

Not surprisingly, there are close connections between groups of polynomial growth and vertex-transitive graphs of polynomial growth (this just means that the sizes of the balls around each vertex grow polynomially). The proof by the authors of Schramm’s locality conjecture involves a delicate splitting into cases according to the growth rate of the graph $G$ – surprisingly, their two cases are whether or not $G$ has quasi-polynomial growth – and makes important use of the uniformity obtained in this paper.