Let be a finite subset of a non-commutative group . As mentioned previously on this blog (as well as in the current logic reading seminar), there is some interest in classifying those which obey *small doubling* conditions such as or . A full classification here has still not been established. However, I wanted to record here an elementary argument (based on Exercise 2.6.5 of my book with Van Vu, which in turn is based on this paper of Izabella Laba) that handles the case when is very close to :

Proposition 1If , then and are both finite groups, which are conjugate to each other. In particular, is contained in the right-coset (or left-coset) of a group of order less than .

Remark 1The constant is completely sharp; consider the case when where is the identity and is an element of order larger than . This is a small example, but one can make it as large as one pleases by taking the direct product of and with any finite group. In the converse direction, we see that whenever is contained in the right-coset (resp. left-coset ) of a group of order less than , then (resp. ) is necessarily equal to all of , by the inclusion-exclusion principle (see the proof below for a related argument).

*Proof:* We begin by showing that is a group. As is symmetric and contains the identity, it suffices to show that this set is closed under addition.

Let . Then we can write and for . If were equal to , then and we would be done. Of course, there is no reason why should equal ; but we can use the hypothesis to boost this as follows. Observe that and both have cardinality and lie inside , which has cardinality strictly less than . By the inclusion-exclusion principle, this forces to have cardinality greater than . In other words, there exist more than pairs such that , which implies that . Thus there are more than elements such that for some (since is uniquely determined by ); similarly, there exists more than elements such that for some . Again by inclusion-exclusion, we can thus find in for which one has simultaneous representations and , and so , and the claim follows.

In the course of the above argument we showed that every element of the group has more than representations of the form for . But there are only pairs available, and thus .

Now let be any element of . Since , we have , and so . Conversely, every element of has exactly representations of the form where . Since occupies more than half of , we thus see from the inclusion-exclusion principle, there is thus at least one representation for which both lie in . In other words, , and the claim follows.

To relate this to the classical doubling constants , we first make an easy observation:

Again, this is sharp; consider equal to where generate a free group.

*Proof:* Suppose that is an element of for some . Then the sets and have cardinality and lie in , so by the inclusion-exclusion principle, the two sets intersect. Thus there exist such that , thus . This shows that is contained in . The converse inclusion is proven similarly.

Proposition 3If , then is a finite group of order , and for some in the normaliser of .

The factor is sharp, by the same example used to show sharpness of Proposition 1. However, there seems to be some room for further improvement if one weakens the conclusion a bit; see below the fold.

*Proof:* Let (the two sets being equal by Lemma 2). By the argument used to prove Lemma 2, every element of has more than representations of the form for . By the argument used to prove Proposition 1, this shows that is a group; also, since there are only pairs , we also see that .

Pick any ; then , and so . Because every element of has representations of the form with , , and occupies more than half of and of , we conclude that each element of lies in , and so and .

The intersection of the groups and contains , which is more than half the size of , and so we must have , i.e. normalises , and the proposition follows.

Because the arguments here are so elementary, they extend easily to the infinitary setting in which is now an infinite set, but has finite measure with respect to some translation-invariant Kiesler measure . We omit the details. (I am hoping that this observation may help simplify some of the theory in that setting.)

** — 1. Beyond the barrier — **

It appears that one can push the arguments a bit beyond the barrier, though of course one has to weaken the conclusion in view of the counterexample in Remark 1. Here I give a result that increases to the golden ratio :

Proposition 4 (Weak non-commutative Kneser theorem)If for some , then for some finite subgroup , and some finite set with for some depending only on .

*Proof:* Write . Let us say that *symmetrises* if , and let be the set of all that symmetrise . It is clear that is a finite group with and thus also.

For each , let be the number of representations of of the form with . Double counting shows that , while by hypothesis ; thus the average value of is at least . Since , . Since for all , we conclude that for at least values of , for some explicitly computable .

Suppose is such that , thus has more than representations of the form with . On the other hand, the argument used to prove Proposition 1 shows that has at least representations of the form with . By the inclusion-exclusion formula, we can thus find representations for which , which implies that . Since was arbitrary, this implies that . Thus . Since and , this implies that can be covered by at most right-cosets of for some depending only on , and the claim follows.

It looks like one should be able to get a bit more structural information on than is given by the above conclusion, and I doubt the golden ratio is sharp either (the correct threshold should be , in analogy with the commutative Kneser theorem; after that, the conclusion will fail, as can be seen by taking to be a long geometric progression). Readers here are welcome to look for improvements to these results, of course.

## 15 comments

Comments feed for this article

11 November, 2009 at 12:54 pm

AnonymousTerry,

Coincidentally I was just looking into this same issue in connection with some lecture notes I’m writing. I agree that the threshold should be 2.

The 3/2 result and also golden ratio result you give are actually contained in an admittedly somewhat obscure paper of Freiman from 1962, the main aim of which is to completely classify sets with doubling at most 8/5. Here is the original reference:

Groups and the inverse problems of additive number theory. (Russian) Number-theoretic studies in the Markov spectrum and in the structural theory of set addition (Russian), pp. 175–183. Kalinin. Gos. Univ., Moscow, 1973.

It’s in Russian. A Masters student of mine at Bristol, Lloyd Husbands, did a very nice translation-exposition which, if I can get his permission, I will link to.

I think that in the torsion-free case there is an argument of Kemperman which will take one up to 2.

Ben

12 November, 2009 at 10:33 am

Terence TaoThanks Ben! I had a suspicion that these results must already be in the literature, but did not have the reference (though now that you mention it, the 8/5 result does ring a bell, I think it was referenced in the K=2 paper, which I believe is actually due to Hamiduone, Llado and Serra.)

11 November, 2009 at 12:55 pm

Ben GreenTerry,

Two points pertaining to the previous post, both rather obvious: firstly, it was by me, and secondly, the paper of Freiman is in fact from 1973 and not from 1962.

Ben

11 November, 2009 at 4:27 pm

Miguel LacruzTerry, there is a small typo in the proof of proposition 1. It should read instead of . Also, the parentheses around are redundant.

Regards,

Miguel

[Corrected, thanks – T.]14 November, 2009 at 1:47 am

AnonymousI take it that proposition 1 should read “group of order less than ” instead of “group of order less than “?

14 November, 2009 at 8:14 pm

Terence TaoWell, both are true, but is the sharp bound, since S has cardinality equal to that of . (The preliminary bound is established in the course of the proof, but is eventually improved upon.)

15 November, 2009 at 11:18 pm

SevaOn a historical note, the proof of Proposition 4 is essentially the same as

that of Theorem 3 in my 2000

paper, where it is shown that if is a finite subset of a group

(written additively, but not assumed to be Abelian) such that its restricted

sumset differs from

the “regular” sumset , then it is large: (where is the largest number of elements

of the group, sharing the same doubling). I also conjectured that, indeed, if

, then — at least in

the case where the underlying group is Abelian.

6 December, 2009 at 6:54 pm

Non-commutative Freiman theorems, and model theory « What’s new[…] a finite subgroup by an element in the normaliser of . More generally, as we mentioned earlier in this post, it can be shown by elementary means that if , where is the golden ratio, then sets of doubling […]

27 January, 2010 at 11:09 am

Linear approximate groups « What’s new[…] proving this statement is the noncommutative Freiman theorem problem, discussed in these earlier blog […]

15 January, 2011 at 8:15 am

A note on approximate subgroups of GL_n(C) and uniformly nonamenable groups « What’s new[…] a new proof of a “noncommutative Freiman” type theorem in linear groups . As discussed in earlier blog posts, a general question in additive (or multiplicative) combinatorics is to […]

12 March, 2011 at 2:18 pm

Hamidoune’s Freiman-Kneser theorem for nonabelian groups « What’s new[…] 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) […]

26 March, 2011 at 8:21 pm

Hamidoune’s Freiman-Kneser theorem for nonabelian groups « IMAGINATION of MATH[…] 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 […]

18 May, 2013 at 8:11 am

Sandeep MurthyHi, wouldn’t Proposition 1 be true for all finite groups, abelian and non-abelian?

[Yes. In this context, “non-commutative” should really be read as “not necessarily commutative”. -T.]26 April, 2016 at 12:12 pm

AnonymousWhat is the explicit value of C(K) in the proof of Proposition 4

26 April, 2016 at 12:45 pm

Terence TaoThe above argument works with and . It may be though that one can do better (e.g. using submodularity methods https://terrytao.wordpress.com/2011/03/12/hamidounes-freiman-kneser-theorem-for-nonabelian-groups/ ).