A few days ago, I received the sad news that Yahya Ould Hamidoune had recently died. Hamidoune worked in additive combinatorics, and had recently solved a question on noncommutative Freiman-Kneser theorems posed by myself on this blog last year. Namely, Hamidoune showed
Theorem 1 (Noncommutative Freiman-Kneser theorem for small doubling) Let , and let be a finite non-empty subset of a multiplicative group such that for some finite set of cardinality at least , where is the product set of and . Then there exists a finite subgroup of with cardinality , such that is covered by at most right-cosets of , where depend only on .
One can of course specialise here to the case , and view this theorem as a classification of those sets of doubling constant at most .
In fact Hamidoune’s argument, which is completely elementary, gives the very nice explicit constants and , which are essentially optimal except for factors of (as can be seen by considering an arithmetic progression in an additive group). This result was also independently established (in the case) by Tom Sanders (unpublished) by a more Fourier-analytic method, in particular drawing on Sanders’ deep results on the Wiener algebra on arbitrary non-commutative groups .
Theorem 1 is not, strictly speaking, contained in Hamidoune’s paper, but can be extracted from his arguments, which share some similarity with the recent simple proof of the Ruzsa-Plünnecke inequality by Petridis (as discussed by Tim Gowers here), and this is what I would like to do below the fold. I also include (with permission) Sanders’ unpublished argument, which proceeds instead by Fourier-analytic methods.
— 1. Hamidoune’s argument —
Fix , , and . For any finite set (possibly empty), and any real number , consider the quantity defined by the formula
we thus have
and the claim follows after subtracting copies of (2).
Following Hamidoune, we make the following definitions, for fixed and :
- The connectivity is the infimum of over all finite non-empty sets .
- A fragment is a finite non-empty set that attains the infimum : .
- An atom is a finite non-empty fragment of minimal cardinality.
Hamidoune only considered the case, but much of his machinery extends to the case , and in fact becomes slightly simpler for . (In contrast, the argument of Petridis is more focused on the case when is large, and in particular on the unique for which vanishes.) In this argument, we will specialise to be
In particular, is always positive for non-empty , and takes on a discrete set of values. This implies that is positive, and that at least one fragment exists, which (by the well-ordering principle) implies that at least one atom exists.
From (1) we see that any left-translate of a fragment is a fragment, and any left-translate of an atom is an atom.
Let and be fragments with non-empty intersection, then from Lemma 2 we have
On the other hand, since and are finite and non-empty, we have . This forces , and so and are also fragments. Specialising to atoms (which, by definition, do not contain any strictly smaller fragments), we conclude that any two atoms are either equal or disjoint. From this and the left-invariance of the atoms, we see that there is a unique atom that contains the identity. This atom is either equal or disjoint to any of its left-translates, which implies that is a finite group.
Now we use the hypothesis that there exists a set with and , which implies that
In particular, we have , which by (3) implies an upper bound on :
We can also expand the inequality as
bounding crudely by and rearranging, we conclude that
We conclude that (and hence ) can be covered by at most translates of , and the claim follows.
— 2. Sanders’ argument —
To motivate Sanders’ argument, let us first establish a continuous qualitative analogue of the non-commutative Freiman theorem, in the context of open precompact sets in a locally compact group with a bi-invariant Haar measure . (By convention, Haar measures assign a positive finite measure to every non-empty open precompact set.)
Proposition 3 (Qualitative noncommutative Freiman-Kneser theorem in locally compact groups) Let be a locally compact Hausdorff group with a bi-invariant Haar measure , and let be an open precompact non-empty subset of such that for some . Then there exists a compact open subgroup of , and is the union of finitely many right cosets of .
Proof: We consider the convolution
Since are bounded, compactly supported functions, we see that the convolution is a continuous, compactly supported function. If lies in the support of , then , and thus for some . But then
on the support of . In other words, there is a “gap” in the range of , in that it cannot take on values in the interval . This gap disconnects the support from its complement; both sets become both open and closed. In particular, is now compact. By continuity and compactness, this implies that there exists a neighbourhood of the identity such that . Letting be the group generated by , we conclude that is open and contained in the compact set , and thus must also be compact, with the union of finitely many right-cosets of as required.
Now we return to the discrete setting. Again, we analyse the function
for all in the support of . So we once again have a gap in the range of . However, in this discrete setting, we do not have any obvious quantitative control on the “continuity” of the convolution to exploit this gap (this is ultimately because does not have good “measurability” properties). However, it turns out that is controlled in a certain Wiener algebra , which roughly speaking is the non-commutative analogue of functions with absolutely convergent Fourier transform. In the abelian setting, the fact that we have control in the Wiener algebra is a consequence of Plancherel’s theorem (that asserts that functions have square-summable Fourier coefficients), the Cauchy-Schwarz inequality, and the observation that convolution corresponds to pointwise multiplication of Fourier coefficients. It turns out that an analogous statement can be made in the non-abelian case.
In the classical setting of Fourier series, functions in the Wiener algebra have absolutely convergent Fourier series, and in particular are necessarily continuous. A deep result of Sanders asserts, roughly speaking, that in more general non-abelian groups , functions in the Wiener algebra can be uniformly approximated by continuous functions “outside of a set of negligible measure”. A precise version of this statement is as follows:
Proof: See Proposition 20.1 of this paper of Sanders. The “continuous” function is in fact of the form for some set larger than (but small compared to ).
We remark that Sanders’ paper uses a nontrivial amount of spectral theory (or nonabelian Fourier analysis). It is possible to use “softer” (and significantly simpler) methods to obtain weaker regularity results on convolutions (giving “ continuity” rather than “ continuity”), as was done by Croot and Sisask, but unfortunately it does not appear that these easier results suffice for the application here (which relies on iterating the control given by continuity, and so cannot handle the small exceptional sets allowed by an regularity result).
From this and the gap property (5) we see that also has a gap, in that it cannot take values in the interval (say) if is small enough. In particular, from this and (6) we see that the set is closed under left-multiplication by , if is small enough; since this set contains , it must therefore contain the group generated by . On the other hand, has an norm of , and so by Markov’s inequality we have
in the other direction we have
so is of comparable size to . As is large () on , we can use (7) to ensure (for small enough) that is also large on on average (specifically, ); this ensures from the pigeonhole principle that some right-translate of has large intersection (cardinality ) with , and this combined with the bounded doubling of ensures that is covered by right-translates of , and the claim follows.