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
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
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.
14 comments
Comments feed for this article
14 March, 2011 at 2:12 am
Petridis
Both proofs are very nice. Is the approach of using the submodularity to deduce the uniqueness of the atom containing the identity new?
14 March, 2011 at 8:04 am
Terence Tao
I got this from Proposition 2.6 of Hamidoune’s paper, which dates back to this 1984 (!) paper of Hamidoune: http://www.ams.org/mathscinet-getitem?mr=782052
The term submodularity is, strictly speaking, not used in these papers, but if one looks at the proofs, one eventually sees that this is what is underlying the arguments.
14 March, 2011 at 9:57 am
Petridis
Thanks for this. In any case it is a very neat proof.
14 March, 2011 at 1:03 pm
Weekly Picks « Mathblogging.org — the Blog
[…] a more research related note, Terry Tao wrote about the late Yahya Ould Hamidoune version of the Freiman-Kneser theorem, at the n-Category Cafe you read about homotopy type theory and Almost Sure announced a new series […]
14 March, 2011 at 2:31 pm
Vu ha Van
My condolences, Van.
15 March, 2011 at 2:42 am
Lior Silberman
In the statement of Thm 1, don’t you want an upper bound on the cardinality of ? (you actually derive one in the text). If I’m not confused, some lower bound ought to follow from the condition that covers .
[Corrected, thanks – T.]
18 March, 2011 at 12:06 pm
obryant
Typo: the definition of atom should refer to fragments. [Corrected, thanks – T.]
19 March, 2011 at 4:58 am
Anonymous
Yahya Ould Hamidoune death is a big loss of the entire world.we have to wait for an other 1000 year so one like him will comeback.
20 March, 2011 at 3:51 am
Sidilimam
Yahya Ould Hamidoune is a Mauritanien just as I am, and his departure from our world is a tremendous loss that can never be recompensated.
It is a duty on the backs of all the Mathematiciens worldwide to commemorate him along with his unforgattable scientific additions in the field.
May God put His mercy on him
Amen
30 March, 2011 at 12:04 pm
Xiaoxi
Yesterday in Paris, a Jornee in memoiry of Yahya Ould Hamidoune was organized by his friends from Paris, Lyon and Barcelona, during which he talked about Yahya’s main contributions to math.
see the link:
http://people.math.jussieu.fr/~balandraud/YoH/YoH.html
26 December, 2011 at 9:54 pm
A variant of Kemperman’s theorem « What’s new
[…] us now prove Theorem 2. It uses a submodularity argument related to one discussed in this previous post. We fix and with , and define the […]
26 December, 2011 at 10:28 pm
A variant of Kemperman’s theorem | t1u
[…] us now prove Theorem 2. It uses a submodularity argument related to one discussed in this previous post. We fix and with , and define the […]
11 November, 2016 at 9:12 pm
Alireza Abdollahi
In the statement of Theorem 1, what is $c(\epsilon)$? is it the same as $C'(\epsilon)$?
[Yes – T.]
22 September, 2019 at 3:48 pm
Med-94
Yahya ould Hamidoun was a way more than a scientist who loved what he was doing and more than an accomplished mathmatician , he was a thinker who worked on so many things -perhaps unpublished work- and we as Mauritanians have a great loss in his departure.
I also admire Mr. Terence Tao for his extensive involvement in introducing other mathematicians and their work.