Hamidoune's Freiman-Kneser theorem for nonabelian groups

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 .

This type of result had previously been known when was less than the golden ratio , as first observed by Freiman; see my previous blog post for more discussion.

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

This measures the extent to which “expands” , compared against the reference expansion constant . Clearly, this quantity is left-invariant, thus

for all finite sets and . It also obeys an important submodularity inequality (also implicitly exploited by Petridis):

Lemma 2 (Submodularity) For any finite subsets of , and any one has

Proof: From the inclusion-exclusion principle one has

and

Since

and

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

With this choice, observe that for any , we have

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

Since and both lie in and have measure , we see from the hypothesis and the inclusion-exclusion principle that we thus have the uniform lower bound

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

As in the continuous case, we can show that is bounded away from zero on its support, in the sense that

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:

Proposition 4 (Almost uniform approximation by continuous functions) Let be as above, and let . Then there exists symmetric subset of the identity with and a function such that

and

for all and .

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).

Let be a sufficiently small parameter depending on to be chosen later, and let be the approximation to given above. From (6), (7) we have

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.

About these ads