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 :
Remark 1 The 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 3 If , 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.