Properness of nilprogressions and the persistence of polynomial growth of given degree

Properness of nilprogressions and the persistence of polynomial growth of given degree, Discrete Analysis 2018:17, 38 pp.

A $k$-dimensional arithmetic progression is a set $P$ of the form $\{a_0+\sum_{i=1}^ka_id_i:0\leq a_i<m_i\}$, or equivalently a sum $P_1+\dots+P_k$, where $P_i$ is an arithmetic progression of length $m_i$. Low-dimensional arithmetic progressions are “highly additively structured”. For example, it is not hard to prove that if $P$ is a $k$-dimensional arithmetic progression, then $|P+P|\leq 2^k|P|$. A famous theorem of Freiman, with a very influential alternative proof by Ruzsa, gives a converse to this fact. It states that a set of integers $A$ of size $n$ for which the sumset $A+A$ has size at most $Cn$ is contained in an arithmetic progression of dimension at most $k(C)$ and size at most $K(C)n$. Freiman’s theorem, and the ideas in Ruzsa’s proof, have had a huge influence on additive combinatorics and have led to many important applications.

It is sometimes convenient to ask for slightly more in the statement of Freiman’s theorem. In the definition of a $k$-dimensional arithmetic progression given above, the sums $\sum_{i=1}^ka_id_i$ were not required to be distinct for distinct choices of the $a_i$. If they are distinct, then the arithmetic progression is said to be proper, and then it has cardinality $m_1\dots m_k$. It was shown in a paper of Bilu, following an argument of Freiman, that if a $k$-dimensional arithmetic progression is not proper, then it is contained in a not too much larger $(k-1)$-dimensional progression. It follows that one can indeed obtain a proper arithmetic progression in the statement of Freiman’s theorem.

Freiman’s theorem was generalized by Green and Ruzsa in 2007 to subsets of arbitrary Abelian groups: they proved that a set with a small sumset must be contained in the sum of a low-dimensional arithmetic progression and a coset of a subgroup, which they called a coset progression. Later it came to be realized that the problem of formulating and proving a generalization to subsets of general groups was extremely interesting and important. As one might expect, it is intimately connected with the subject of growth in groups, since in a group of high growth one cannot expect a product set to be small. Thus, describing the structure of sets with small product sets requires one to prove, amongst other things, that they live in groups of small growth. A non-Abelian Freiman theorem was proved by Breuillard, Green and Tao, and one of its consequences was a new proof of Gromov’s polynomial-growth theorem.

The object that replaces a coset progression in the non-Abelian version of Freiman’s theorem is a structure known as a coset nilprogression. The analogue of a $k$-dimensional progression in a general group is a set of products of $k$ generators $x_1,\dots,x_k$ where $x_i$ and its inverse are used at most $m_i$ times. If the $x_i$ generate an $s$-step nilpotent subgroup, then the progression is called a nilprogression of rank $k$ and step $s$. A coset nilprogression is the product of a finite subgroup with a nilprogression that normalizes it.

As with multidimensional progressions in Abelian groups, one can ask for a nilprogression to be proper – that is, for all the products to be distinct. There is a further desirable property, defined in the paper, called upper triangular form. It says that the commutator of any two generators $x_i$ and $x_j$ with $i<j$ is efficiently generated by the generators $x_{j+1},\dots,x_k$. There is also a modification of the notion of a progression that seems quite drastic, and would indeed be drastic without the nilpotency, which is that the progression should be ordered – that is, that instead of taking all products of a certain size of the generators, one should take only products of the form $x_1^{a_1}\dots x_k^{a_k}$.

The main result of the paper is that a coset nilprogression is contained in the union of a small number of translates of an ordered coset nilprogression of the same step and rank not too much larger. Moreover, this ordered coset nilprogression is proper and in upper triangular form. The proof involves finding an appropriate non-Abelian analogues of arguments from the geometry of numbers that were used in the Abelian case.

This result allows one to reformulate the non-Abelian Freiman theorem of Breuillard, Green and Tao, as well as many other related results, in a useful way. As one example of the usefulness of the result, the authors confirm a conjecture of Benjamini, by showing that for every $M$ and $D$ there exists $N$ such that if $n\geq N$ and $S$ is a symmetric set of generators that contains the identity and satisfies the growth condition $|S^n|\leq Mn^D$, then there is a constant $M'$ such that $|S^m|\leq M'm^D$ for every $m\geq n$. The results of Breuillard, Green and Tao imply that $S$ has polynomial growth in this situation, but not that the polynomial can be taken to be of degree $D$. Further applications are given, to scaling limits of Cayley graphs, in a subsequent paper of the authors (arXiv:1711.08295).