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 {0 < \epsilon \leq 1}, and let {S \subset G} be a finite non-empty subset of a multiplicative group {G} such that {|A \cdot S| \leq (2-\epsilon) |S|} for some finite set {A} of cardinality {|A|} at least {|S|}, where {A \cdot S := \{ as: a \in A, s \in S \}} is the product set of {A} and {S}. Then there exists a finite subgroup {H} of {G} with cardinality {|H| \leq C(\epsilon) |S|}, such that {S} is covered by at most {C'(\epsilon)} right-cosets {H \cdot x} of {H}, where {c(\epsilon), C(\epsilon) > 0} depend only on {\epsilon}.

One can of course specialise here to the case {A=S}, and view this theorem as a classification of those sets {S} of doubling constant at most {2-\epsilon}.

In fact Hamidoune’s argument, which is completely elementary, gives the very nice explicit constants {C(\epsilon) := \frac{2}{\epsilon}} and {C'(\epsilon) := \frac{2}{\epsilon} - 1}, which are essentially optimal except for factors of {2} (as can be seen by considering an arithmetic progression in an additive group). This result was also independently established (in the {A=S} case) by Tom Sanders (unpublished) by a more Fourier-analytic method, in particular drawing on Sanders’ deep results on the Wiener algebra {A(G)} on arbitrary non-commutative groups {G}.

This type of result had previously been known when {2-\epsilon} was less than the golden ratio {\frac{1+\sqrt{5}}{2}}, 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 {S}, {G}, and {\epsilon}. For any finite set {A} (possibly empty), and any real number {K \in {\bf R}}, consider the quantity {c(A) = c_{K,S}(A)} defined by the formula

\displaystyle  c(A) := |A\cdot S| - K|A|.

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

\displaystyle  c( x \cdot A ) = c( A ) \ \ \ \ \ (1)

for all finite sets {A} and {x \in G}. It also obeys an important submodularity inequality (also implicitly exploited by Petridis):

Lemma 2 (Submodularity) For any finite subsets {A, B, S} of {G}, and any {K \in {\bf R}} one has

\displaystyle  c( A \cup B ) + c( A \cap B ) \leq c( A ) + c( B ).

Proof: From the inclusion-exclusion principle one has

\displaystyle  |A \cup B| + |A \cap B| = |A| + |B| \ \ \ \ \ (2)


\displaystyle  |(A \cdot S) \cup (B \cdot S)| + |(A \cdot S) \cap (B \cdot S)| = |A \cdot S| + |B \cdot S|.


\displaystyle  (A \cup B) \cdot S = (A \cdot S) \cup (B \cdot S)


\displaystyle  (A \cap B) \cdot S \subset (A \cdot S) \cap (B \cdot S)

we thus have

\displaystyle  |(A \cup B) \cdot S| + |(A \cap B) \cdot S| \leq |A \cdot S| + |B \cdot S|,

and the claim follows after subtracting {K} copies of (2). \Box

Following Hamidoune, we make the following definitions, for fixed {K} and {S}:

  • The connectivity {\kappa = \kappa_K(S)} is the infimum of {c(A)} over all finite non-empty sets {A}.
  • A fragment is a finite non-empty set {A} that attains the infimum {\kappa}: {c(A) = \kappa}.
  • An atom is a finite non-empty fragment {A} of minimal cardinality.

Hamidoune only considered the {K=1} case, but much of his machinery extends to the case {K \leq 1}, and in fact becomes slightly simpler for {K<1}. (In contrast, the argument of Petridis is more focused on the case when {K} is large, and in particular on the unique {K} for which {\kappa} vanishes.) In this argument, we will specialise {K} to be

\displaystyle  K := 1 - \epsilon/2.

With this choice, observe that for any {A}, we have

\displaystyle  c(A) \geq |A| - K|A| = \epsilon |A| / 2. \ \ \ \ \ (3)

In particular, {c(A)} is always positive for non-empty {A}, and takes on a discrete set of values. This implies that {\kappa} 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 {A} and {B} be fragments with non-empty intersection, then from Lemma 2 we have

\displaystyle  c(A \cup B) + c(A \cap B) \leq c(A) + c(B) = 2\kappa.

On the other hand, since {A \cup B} and {A \cap B} are finite and non-empty, we have {c(A \cup B), c(A \cap B) \geq \kappa}. This forces {c(A \cup B) = c(A \cap B) = \kappa}, and so {A \cup B} and {A \cap B} are also fragments. Specialising to atoms (which, by definition, do not contain any strictly smaller fragments), we conclude that any two atoms {A, B} are either equal or disjoint. From this and the left-invariance of the atoms, we see that there is a unique atom {H} that contains the identity. This atom is either equal or disjoint to any of its left-translates, which implies that {H} is a finite group.

Now we use the hypothesis that there exists a set {A} with {|A| \geq |S|} and {|A \cdot S| \leq (2-\epsilon) |S|}, which implies that

\displaystyle  c(A) \leq (2-\epsilon)|S| - (1-\epsilon/2) |S| = (1-\epsilon/2) |S|.

In particular, we have {c(H) = \kappa \leq c(A) \leq (1 - \epsilon/2) |S|}, which by (3) implies an upper bound on {H}:

\displaystyle  |H| \leq (\frac{2}{\epsilon} - 1) |S|.

We can also expand the inequality {c(H) \leq (1-\epsilon/2) |S|} as

\displaystyle  |H \cdot S| \leq (1 - \epsilon/2) |S| + (1-\epsilon/2) |H|;

bounding {|S|} crudely by {|H \cdot S|} and rearranging, we conclude that

\displaystyle  |H \cdot S| \leq (\frac{2}{\epsilon} - 1) |H|.

We conclude that {H \cdot S} (and hence {S}) can be covered by at most {\frac{2}{\epsilon} - 1} translates of {H}, 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 {G} with a bi-invariant Haar measure {\mu}. (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 {G} be a locally compact Hausdorff group with a bi-invariant Haar measure {\mu}, and let {A \subset G} be an open precompact non-empty subset of {G} such that {\mu( A \cdot A ) \leq (2-\epsilon) \mu( A )} for some {\epsilon>0}. Then there exists a compact open subgroup {H} of {G}, and {A \cdot A^{-1}} is the union of finitely many right cosets of {H}.

Proof: We consider the convolution

\displaystyle  f(x) := \frac{1}{\mu(A)} 1_{A} * 1_{A^{-1}}(x)

\displaystyle  = \frac{1}{\mu(A)} \int_G 1_{A}(y) 1_{A^{-1}}( y^{-1} x )\ d\mu(y)

\displaystyle  = \frac{1}{\mu(A)} \mu( A \cap x \cdot A ).

Since {1_A, 1_{A^{-1}}} are bounded, compactly supported functions, we see that the convolution {f = 1_A * 1_{A^{-1}}} is a continuous, compactly supported function. If {x} lies in the support {A \cdot A^{-1}} of {f}, then {x \in A \cdot A^{-1}}, and thus {x = ab^{-1}} for some {a,b \in A}. But then

\displaystyle  f(x) = \frac{1}{\mu(A)} \mu( (a \cdot A) \cap (b \cdot A) ).

Since {a \cdot A} and {b \cdot A} both lie in {A \cdot A} and have measure {\mu(A)}, we see from the hypothesis {\mu(A \cdot A) \leq (2-\epsilon) \mu(A)} and the inclusion-exclusion principle that we thus have the uniform lower bound

\displaystyle  f(x) \geq \epsilon \ \ \ \ \ (4)

on the support {A \cdot A^{-1}} of {f}. In other words, there is a “gap” in the range of {f}, in that it cannot take on values in the interval {(0,\epsilon)}. This gap disconnects the support {A \cdot A^{-1}} from its complement; both sets become both open and closed. In particular, {A \cdot A^{-1}} is now compact. By continuity and compactness, this implies that there exists a neighbourhood {U} of the identity such that {U \cdot A \cdot A^{-1} = A \cdot A^{-1}}. Letting {H} be the group generated by {U}, we conclude that {H} is open and contained in the compact set {A \cdot A^{-1}}, and thus must also be compact, with {A \cdot A^{-1}} the union of finitely many right-cosets of {H} as required. \Box

Now we return to the discrete setting. Again, we analyse the function

\displaystyle  f(x) := \frac{1}{|A|} 1_A * 1_{A^{-1}}(x)

\displaystyle  := \frac{1}{|A|} \sum_{y \in G} 1_A(y) 1_A( y^{-1} x )

\displaystyle  = \frac{1}{|A|} |A \cap x \cdot A|.

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

\displaystyle  f(x) \geq \epsilon \ \ \ \ \ (5)

for all {x} in the support {A \cdot A^{-1}} of {f}. So we once again have a gap in the range of {f}. However, in this discrete setting, we do not have any obvious quantitative control on the “continuity” of the convolution {f} to exploit this gap (this is ultimately because {A} does not have good “measurability” properties). However, it turns out that {f} is controlled in a certain Wiener algebra {A(G)}, 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 {L^2} 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 {G}, functions in the Wiener algebra {A(G)} 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 {f} be as above, and let {\sigma > 0}. Then there exists symmetric subset {S'} of the identity with {|S'| \gg_\sigma |A|} and a function {F: G \rightarrow {\bf R}^+} such that

\displaystyle  |F(s' x) - F(x)| \ll \sigma \ \ \ \ \ (6)


\displaystyle  (\sum_{s' \in S'} |F(s' x) - f(s'x)|^2)^{1/2} \ll \sigma |S'|^{1/2} \ \ \ \ \ (7)

for all {s' \in S'} and {x \in G}.

Proof: See Proposition 20.1 of this paper of Sanders. The “continuous” function {F} is in fact of the form {F := \frac{1}{|S|} 1_S * \frac{1}{|S|} 1_S * f} for some set {S} larger than {S'} (but small compared to {A}).

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 “{L^p} continuity” rather than “{L^\infty} 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 {L^p} regularity result). \Box

Let {\sigma > 0} be a sufficiently small parameter depending on {\epsilon} to be chosen later, and let {F} be the approximation to {f} given above. From (6), (7) we have

\displaystyle  (\sum_{s' \in S'} |F(x) - f(s'x)|^2)^{1/2} \ll \sigma |S'|^{1/2}.

From this and the gap property (5) we see that {F} also has a gap, in that it cannot take values in the interval {[\epsilon/3,2\epsilon/3]} (say) if {\sigma} is small enough. In particular, from this and (6) we see that the set {\Omega := \{ x \in G: F(x) > 2\epsilon/3 \}} is closed under left-multiplication by {S'}, if {\sigma} is small enough; since this set contains {1}, it must therefore contain the group {H} generated by {S'}. On the other hand, {F} has an {\ell^1} norm of {O(|A|)}, and so by Markov’s inequality we have

\displaystyle |H| \leq |\Omega| \ll |A| / \epsilon;

in the other direction we have

\displaystyle  |H| \geq |S'| \gg_\sigma |A|,

so {H} is of comparable size to {A}. As {F} is large ({\gg \epsilon}) on {H}, we can use (7) to ensure (for {\sigma} small enough) that {f} is also large on {H} on average (specifically, {\|f\|_{\ell^2(H)} \gg |H|^{1/2} / \epsilon}); this ensures from the pigeonhole principle that some right-translate of {A} has large intersection (cardinality {\gg |H|/\epsilon}) with {H}, and this combined with the bounded doubling of {A} ensures that {A} is covered by {O( \frac{|A|}{\epsilon |H|} ) = O_{\epsilon,\sigma}(1)} right-translates of {H}, and the claim follows.