I’ve just uploaded to the arXiv my paper “Inverse theorems for sets and measures of polynomial growth“. This paper was motivated by two related questions. The first question was to obtain a qualitatively precise description of the sets of polynomial growth that arise in Gromov’s theorem, in much the same way that Freiman’s theorem (and its generalisations) provide a qualitatively precise description of sets of small doubling. The other question was to obtain a non-abelian analogue of inverse Littlewood-Offord theory.
Let me discuss the former question first. Gromov’s theorem tells us that if a finite subset of a group exhibits polynomial growth in the sense that grows polynomially in , then the group generated by is virtually nilpotent (the converse direction also true, and is relatively easy to establish). This theorem has been strengthened a number of times over the years. For instance, a few years ago, I proved with Shalom that the condition that grew polynomially in could be replaced by for a single , as long as was sufficiently large depending on (in fact we gave a fairly explicit quantitative bound on how large needed to be). A little more recently, with Breuillard and Green, the condition was weakened to , that is to say it sufficed to have polynomial relative growth at a finite scale. In fact, the latter paper gave more information on in this case, roughly speaking it showed (at least in the case when was a symmetric neighbourhood of the identity) that was “commensurate” with a very structured object known as a coset nilprogression. This can then be used to establish further control on . For instance, it was recently shown by Breuillard and Tointon (again in the symmetric case) that if for a single that was sufficiently large depending on , then all the for have a doubling constant bounded by a bound depending only on , thus for all .
In this paper we are able to refine this analysis a bit further; under the same hypotheses, we can show an estimate of the form
for all and some piecewise linear, continuous, non-decreasing function with , where the error is bounded by a constant depending only on , and where has at most pieces, each of which has a slope that is a natural number of size . To put it another way, the function for behaves (up to multiplicative constants) like a piecewise polynomial function, where the degree of the function and number of pieces is bounded by a constant depending on .
One could ask whether the function has any convexity or concavity properties. It turns out that it can exhibit either convex or concave behaviour (or a combination of both). For instance, if is contained in a large finite group, then will eventually plateau to a constant, exhibiting concave behaviour. On the other hand, in nilpotent groups one can see convex behaviour; for instance, in the Heisenberg group , if one sets to be a set of matrices of the form for some large (abusing the notation somewhat), then grows cubically for but then grows quartically for .
To prove this proposition, it turns out (after using a somewhat difficult inverse theorem proven previously by Breuillard, Green, and myself) that one has to analyse the volume growth of nilprogressions . In the “infinitely proper” case where there are no unexpected relations between the generators of the nilprogression, one can lift everything to a simply connected Lie group (where one can take logarithms and exploit the Baker-Campbell-Hausdorff formula heavily), eventually describing with fair accuracy by a certain convex polytope with vertices depending polynomially on , which implies that depends polynomially on up to constants. If one is not in the “infinitely proper” case, then at some point the nilprogression develops a “collision”, but then one can use this collision to show (after some work) that the dimension of the “Lie model” of has dropped by at least one from the dimension of (the notion of a Lie model being developed in the previously mentioned paper of Breuillard, Greenm, and myself), so that this sort of collision can only occur a bounded number of times, with essentially polynomial volume growth behaviour between these collisions.
The arguments also give a precise description of the location of a set for which grows polynomially in . In the symmetric case, what ends up happening is that becomes commensurate to a “coset nilprogression” of bounded rank and nilpotency class, whilst is “virtually” contained in a scaled down version of that nilprogression. What “virtually” means is a little complicated; roughly speaking, it means that there is a set of bounded cardinality such that for all . Conversely, if is virtually contained in , then is commensurate to (and more generally, is commensurate to for any natural number ), giving quite a (qualitatively) precise description of in terms of coset nilprogressions.
The main tool used to prove these results is the structure theorem for approximate groups established by Breuillard, Green, and myself, which roughly speaking asserts that approximate groups are always commensurate with coset nilprogressions. A key additional trick is a pigeonholing argument of Sanders, which in this context is the assertion that if is comparable to , then there is an between and such that is very close in size to (up to a relative error of ). It is this fact, together with the comparability of to a coset nilprogression , that allows us (after some combinatorial argument) to virtually place inside .
Similar arguments apply when discussing iterated convolutions of (symmetric) probability measures on a (discrete) group , rather than combinatorial powers of a finite set. Here, the analogue of volume is given by the negative power of the norm of (thought of as a non-negative function on of total mass 1). One can also work with other norms here than , but this norm has some minor technical conveniences (and other measures of the “spread” of end up being more or less equivalent for our purposes). There is an analogous structure theorem that asserts that if spreads at most polynomially in , then is “commensurate” with the uniform probability distribution on a coset progression , and itself is largely concentrated near . The factor of here is the familiar scaling factor in random walks that arises for instance in the central limit theorem. The proof of (the precise version of) this statement proceeds similarly to the combinatorial case, using pigeonholing to locate a scale where has almost the same norm as .
A special case of this theory occurs when is the uniform probability measure on elements of and their inverses. The probability measure is then the distribution of a random product , where each is equal to one of or its inverse , selected at random with drawn uniformly from with replacement. This is very close to the Littlewood-Offord situation of random products where each is equal to or selected independently at random (thus is now fixed to equal rather than being randomly drawn from . In the case when is abelian, it turns out that a little bit of Fourier analysis shows that these two random walks have “comparable” distributions in a certain sense. As a consequence, the results in this paper can be used to recover an essentially optimal abelian inverse Littlewood-Offord theorem of Nguyen and Vu. In the nonabelian case, the only Littlewood-Offord theorem I am aware of is a recent result of Tiep and Vu for matrix groups, but in this case I do not know how to relate the above two random walks to each other, and so we can only obtain an analogue of the Tiep-Vu results for the symmetrised random walk instead of the ordered random walk .