Let {X} be a finite subset of a non-commutative group {G}. As mentioned previously on this blog (as well as in the current logic reading seminar), there is some interest in classifying those {X} which obey small doubling conditions such as {|X \cdot X| = O(|X|)} or {|X \cdot X^{-1}| = O(|X|)}. 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 {|X \cdot X|} is very close to {|X|}:

Proposition 1 If {|X^{-1} \cdot X| < \frac{3}{2} |X|}, then {X \cdot X^{-1}} and {X^{-1} \cdot X} are both finite groups, which are conjugate to each other. In particular, {X} is contained in the right-coset (or left-coset) of a group of order less than {\frac{3}{2} |X|}.

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

Proof: We begin by showing that {S := X \cdot X^{-1}} is a group. As {S} is symmetric and contains the identity, it suffices to show that this set is closed under addition.

Let {a, b \in S}. Then we can write {a=xy^{-1}} and {b=zw^{-1}} for {x,y,z,w \in X}. If {y} were equal to {z}, then {ab = xw^{-1} \in X \cdot X^{-1}} and we would be done. Of course, there is no reason why {y} should equal {z}; but we can use the hypothesis {|X^{-1} \cdot X| < \frac{3}{2}|X|} to boost this as follows. Observe that {x^{-1} \cdot X} and {y^{-1} \cdot X} both have cardinality {|X|} and lie inside {X^{-1} \cdot X}, which has cardinality strictly less than {\frac{3}{2} |X|}. By the inclusion-exclusion principle, this forces {x^{-1} \cdot X \cap y^{-1} \cdot X} to have cardinality greater than {\frac{1}{2}|X|}. In other words, there exist more than {\frac{1}{2}|X|} pairs {x',y' \in X} such that {x^{-1} x' = y^{-1} y'}, which implies that {a = x' (y')^{-1}}. Thus there are more than {\frac{1}{2}|X|} elements {y' \in X} such that {a = x' (y')^{-1}} for some {x'\in X} (since {x'} is uniquely determined by {y'}); similarly, there exists more than {\frac{1}{2}|X|} elements {z' \in X} such that {b = z' (w')^{-1}} for some {w' \in X}. Again by inclusion-exclusion, we can thus find {y'=z'} in {X} for which one has simultaneous representations {a = x' (y')^{-1}} and {b = y' (z')^{-1}}, and so {ab = x'(z')^{-1} \in X \cdot X^{-1}}, and the claim follows.

In the course of the above argument we showed that every element of the group {S} has more than {\frac{1}{2}|X|} representations of the form {xy^{-1}} for {x,y \in X}. But there are only {|X|^2} pairs {(x,y)} available, and thus {|S| < 2|X|}.

Now let {x} be any element of {X}. Since {X \cdot x^{-1} \subset S}, we have {X \subset S \cdot x}, and so {X^{-1} \cdot X \subset x^{-1} \cdot S \cdot x}. Conversely, every element of {x^{-1} \cdot S \cdot x} has exactly {|S|} representations of the form {z^{-1} w} where {z, w \in S \cdot x}. Since {X} occupies more than half of {S \cdot x}, we thus see from the inclusion-exclusion principle, there is thus at least one representation {z^{-1} w} for which {z, w} both lie in {X}. In other words, {x^{-1} \cdot S \cdot x = X^{-1} \cdot X}, and the claim follows. \Box

To relate this to the classical doubling constants {|X \cdot X|/|X|}, we first make an easy observation:

Lemma 2 If {|X \cdot X| < 2|X|}, then {X \cdot X^{-1} = X^{-1} \cdot X}.

Again, this is sharp; consider {X} equal to {\{x,y\}} where {x,y} generate a free group.

Proof: Suppose that {xy^{-1}} is an element of {X \cdot X^{-1}} for some {x,y \in X}. Then the sets {X \cdot x} and {X \cdot y} have cardinality {|X|} and lie in {X \cdot X}, so by the inclusion-exclusion principle, the two sets intersect. Thus there exist {z,w \in X} such that {zx=wy}, thus {xy^{-1}=z^{-1}w \in X^{-1} \cdot X}. This shows that {X \cdot X^{-1}} is contained in {X^{-1} \cdot X}. The converse inclusion is proven similarly. \Box

Proposition 3 If {|X \cdot X| < \frac{3}{2} |X|}, then {S := X \cdot X^{-1}} is a finite group of order {|X \cdot X|}, and {X \subset S \cdot x = x \cdot S} for some {x} in the normaliser of {S}.

The factor {\frac{3}{2}} 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 {S = X^{-1} \cdot X = X \cdot X^{-1}} (the two sets being equal by Lemma 2). By the argument used to prove Lemma 2, every element of {S} has more than {\frac{1}{2}|X|} representations of the form {xy^{-1}} for {x,y \in X}. By the argument used to prove Proposition 1, this shows that {S} is a group; also, since there are only {|X|^2} pairs {(x,y)}, we also see that {|S| < 2|X|}.

Pick any {x \in X}; then {x^{-1} \cdot X, X \cdot x^{-1} \subset S}, and so {X \subset x\cdot S, S \cdot x}. Because every element of {x \cdot S \cdot x} has {|S|} representations of the form {yz} with {y \in x \cdot S}, {z \in S \cdot x}, and {X} occupies more than half of {x \cdot S} and of {S \cdot x}, we conclude that each element of {x \cdot S \cdot x} lies in {X \cdot X}, and so {X \cdot X = x \cdot S \cdot x} and {|S| = |X \cdot X|}.

The intersection of the groups {S} and {x \cdot S \cdot x^{-1}} contains {X \cdot x^{-1}}, which is more than half the size of {S}, and so we must have {S = x \cdot S \cdot x^{-1}}, i.e. {x} normalises {S}, and the proposition follows. \Box

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

— 1. Beyond the {3/2} barrier —

It appears that one can push the arguments a bit beyond the {3/2} 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 {3/2=1.5} to the golden ratio {\phi := (1+\sqrt{5})/2 = 1.618\ldots}:

Proposition 4 (Weak non-commutative Kneser theorem) If {|X^{-1} \cdot X|, |X \cdot X^{-1}| \leq K |X|} for some {1 < K < \phi}, then {X \cdot X^{-1} = H \cdot Z} for some finite subgroup {H}, and some finite set {Z} with {|Z| \leq C(K)} for some {C(K)} depending only on {K}.

Proof: Write {S := X \cdot X^{-1}}. Let us say that {h} symmetrises {S} if {h \cdot S = S}, and let {H} be the set of all {h} that symmetrise {S}. It is clear that {H} is a finite group with {H \cdot S = S} and thus {S \cdot H = S} also.

For each {z \in S}, let {r(z)} be the number of representations of {z} of the form {z=xy^{-1}} with {x,y \in X}. Double counting shows that {\sum_{z \in S} r(z) = |X|^2}, while by hypothesis {|S| \leq K|X|}; thus the average value of {r(z)} is at least {|X|/K}. Since {1 < K < \phi}, {1/K > K-1}. Since {r(z) \leq |X|} for all {z}, we conclude that {r(z) > (K-1) |X|} for at least {c(K) |X|} values of {z \in S}, for some explicitly computable {c(K) > 0}.

Suppose {z, w \in S} is such that {r(z) > (K-1)|X|}, thus {z} has more than {(K-1)|X|} representations of the form {xy^{-1}} with {x,y \in X}. On the other hand, the argument used to prove Proposition 1 shows that {w} has at least {(2-K)|X|} representations of the form {x' (y')^{-1}} with {x',y' \in X}. By the inclusion-exclusion formula, we can thus find representations for which {y=x'}, which implies that {zw \in S}. Since {w \in S} was arbitrary, this implies that {z \in H}. Thus {|H| \geq c(K) |X|}. Since {S = H \cdot S} and {|S| \leq K|X|}, this implies that {S} can be covered by at most {C(K)} right-cosets of {S} for some {C(K)} depending only on {K}, and the claim follows. \Box

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

About these ads