Conditions for an analogue of Cauchy-Davenport for simple groups

Question

What conditions would be sufficient for a generalization of Cauchy-Davenport for simple groups? I can see two possible difficulties with a generalization for general groups:

1. The sets could both be part of a subgroup of the group.
2. The sets could both be cosets of a normal subgroup. This is impossible for simple groups.

Are these the only ways Cauchy-Davenport can fail, or are there other ways?

In particular, would it be possible to generalize the proof of Cauchy-Davenport given in http://arxiv.org/pdf/math/0308286v6.pdf with a more general version of the uncertainty principle used in that paper?

I haven't used mathoverflow before, so apologies if this question isn't appropriate for this website.

Answer 1

First, a slightly tangential comment regarding what I assume you mean by 'Cauchy--Davenport fails'; I include it for reader potentially unfamiliar with it and since there is also a somewhat common other way to generalize it; cf below.

The Cauchy--Davenport Theorem asserts that for $G$ a prime cyclic group of order $p$ one has for nonempty subsets $A, B$
$$|AB| \ge \min \lbrace |A| + |B| - 1, p \rbrace $$

It seems that you mean with 'Cauchy--Davenport fails' that the inequality does not hold (for certain sets) with $p$ in the displayed formula replaced by the order of the group. This is however not the only thing one could call (the analog of) Cauchy--Davenport. Indeed an other usage is somewhat established: there is a paper by J.P. Wheeler called 'The Cauchy--Davenport Theorem for finite groups' that asserts the displayed equation for finite groups with the understanding that $p$ is the smallest order of a nonidenty element. This was also obtained by Gy. Karolyi (independently).

Now, to the actual question. Yes, there are somewhat other types of sets. For example, take $A=aH$ and $B=bH$ with $b$ in the normalizer of $H$ or $A=aH$ and $B=Hb$, for some (nonnormal) subgroup $H$.

However, there are results classifying sets for which the product set is very small. See the blog post of Tao 'An elementary noncommutaive Freiman--Kneser Theorem'

Containing for example the result (originally due to Freiman, cf Seva's anwer for details): if $|A \cdot A|< 3 |A|/2$ then $S = A \cdot A^{-1}$ is a subgroup of order $|A \cdot A|$ and $A \subset a S$ and $aS =Sa$.

In a more recent blog post ('Hamidoune’s Freiman-Kneser theorem for nonabelian groups') Tao also discusses recent work of the late Hamidoune answering a question raised in the above mentioned blog post, which sort of classifies subsets for which 'Cauchy--Davenport fails' (in part, but not always normal subgroups arise, so in the simple case there are some reductions); roughly one gets unions of cosets. In that blog post also work of Sanders (unpublished at that time, yet meanwhile available) is mentioned related to this problem, which methodologically, using Fourier analytic methods, seems closer than Hamidoune's to the uncertainty principle you mention; yet I do not oversee this in detail.

Answer 2

Not sure whether @David is still around here, but I'd like to add a complement to @quid's answer.

Fix an integer $n \ge 9$, and let $q$ be a prime power and $\mathbb G = (G, \cdot)$ the projective special linear group ${\rm PSL}_n(q)$. It is known, see [4, Section 4], that there exist $a,b \in G$ such that $a^2 = b^{n-1} = 1$ and $G = \langle a, b \rangle$.

Let $I, J \subseteq [\![0,n-2]\!]$ be such that $|I| + |J| > n$. It then follows from an old theorem from the folklore of additive theory, see e.g. [1, Lemma 3.1.2], that $I+J$ covers all residue classes modulo $n-1$.

Therefore, if $X := \{ab^i: i \in I\}$ and $Y := \{b^j: j \in J\}$, then $XY = a\;\!\langle b \rangle$, viz. $|XY| = n-1$, while $|X|+|Y|-1=|I|+|J|-1 > n-1$ and $|G| = \frac{1}{q-1}\prod_{i=0}^{n-1} (q^n-q^i)$.

This is sensibly different from quid's construction, in that $X$ and $Y$ are, roughly speaking, far from being "smooth sets" (in quid's answer, cosets of a subgroup of $\mathbb G$). In addition, we are now really working in $\mathbb G$, in the sense that $\langle X, Y \rangle = G$.

Again, the above shows that a global analogue of the (classical) Cauchy-Davenport theorem for a group $\mathbb G = (G, \cdot)$, either simple or not, pretending that $|XY| \ge \min(|G|,|X|+|Y|-1)$ for all $X,Y \subseteq G$, is pretty much optimistic.

The Hamidoune-Károlyi theorem, referred to by quid in his answer (see Note (i) below), is a possibility, but it gives a bound that is often too pessimistic.

An alternative is then to generalize the Cauchy-Davenport theorem by rather taking into account the local behavior of the ambient group, which can be even done in the broader setting of semigroups.

First, some notation. Suppose $\mathbb A = (A, +)$ is an additively written (but not necessarily commutative) semigroup, that is a set with a binary associative operation on it; we denote by $\mathbb A^\times$ the set of units (or invertible elements) of $\mathbb A$, so that $\mathbb A^\times \ne \emptyset$ iff $\mathbb A$ is a monoid (viz., a unital semigroup).

Given $X \subseteq A$, we define the Cauchy-Davenport constant of $X$ (relative to $\mathbb A$) by $$\gamma(X) := \sup_{x_0 \in X^\times} \inf_{x_0 \ne x \in X} {\rm ord}(x-x_0),$$ where $X^\times := X \cap \mathbb A^\times$, $\inf(\emptyset) := \infty$, $\sup(\emptyset) := 0$, and for an element $z \in A$ we let ${\rm ord}(z)$ be the order of $z$ in $\mathbb A$, namely the cardinality of the subsemigroup of $\mathbb A$ generated by $z$.

Then, for a nonempty $n$-tuple $(X_1, \ldots, X_n)$ of subsets of $A$, we put $$\gamma(X_1, \ldots, X_n) := \max(\gamma(X_1), \ldots, \gamma(X_n)),$$ and call $\gamma(X_1, \ldots, X_n)$ as the Cauchy-Davenport constant of the $n$-tuple $(X_1, \ldots, X_n)$.

With these definitions in mind, it is then possible to prove the following:

Theorem 1. If $\mathbb A$ is a cancellative semigroup, then $|X+Y| \ge \min(\gamma(X+Y), |X|+|Y|-1)$ for all $X,Y \subseteq A$.

Here, the sumset of two subsets of $A$ is defined in the very same way as in the context of groups, and $\mathbb A$ being cancellative means that the functions $A \to A: x \mapsto a+x$ and $A \to A: x \mapsto x+a$ are both injective for all $a \in A$.

Moreover, Theorem 1 can be strengthened to the following:

Theorem 2. If $\mathbb A$ is a cancellative semigroup, then $|X+Y| \ge \min(\gamma(X, Y), |X|+|Y|-1)$ for all $X,Y \subseteq A$ such that at least one of $X$ and $Y$ generates a commutative subsemigroup of $\mathbb A$.

This is really a strengthening of Theorem 1, as we have:

Lemma. If $\mathbb A$ is a cancellative semigroup, then for all $X,Y \subseteq A$, it holds $$\gamma(X,Y) \ge \gamma(X+Y) \ge \mathfrak{p}(\mathbb A),$$ where $\mathfrak{p}(\mathbb A)$ is the infimum of $|S|$ as $S$ ranges over the nontrivial subgroups of $\mathbb A$.

Of course, Theorems 1 and 2 are trivial when $\mathbb A^\times = \emptyset$, but this is not the case, e.g., when $\mathbb A$ is a group, and the lemma above shows that both of them are stronger than, and a generalization of, the Hamidoune-Károlyi theorem.

Added later. It is perhaps worth mentioning that, if $\mathbb G$, $X$, $Y$, $I$, $J$ and $n$ are given as in the first part of this answer, then the bound implied by the Hamidoune-Károlyi theorem is $|XY| \ge 2$, whereas for $n$ prime (I don't know about other cases) the bound implied by Theorem 2 is $|XY| \ge n-1$, because $\langle Y \rangle$ is a commutative subgroup of $\mathbb G$ and at least one between the sets $I$ and $J$ has size (strictly) larger than $\frac{1}{2}(n-1)$, so that [1, Lemma 3.1.2] applies again and yields $\gamma(X, Y) = n-1$. To wit, Theorem 2 gives the correct size of $XY$, which is comparatively much larger than the bound derived from the Hamidoune-Károlyi theorem if $n \gg 2$, and explains, I hope, the reason why I claimed that the Hamidoune-Károlyi theorem is often too pessimsitic.

Notes.

(i) The result is more or less straightforward in the commutative case (by Kneser's theorem), and G. Károlyi proved it for finite groups in 2005 (based on the Feit-Thompson theorem). A proof of the general statement (relying on the isoperimetric method) was then communicated by H. O. Hamidoune to Károlyi during the peer-review process of [2], where it was finally included, see [2, p. 242]. However, Károlyi himself pointed out in a private communication, as recently as July 2013, that a simpler approach comes from a Kneser-type result of J. E. Olson [3, Theorem 2], based on Kemperman's transform. And another argument along the same lines was mentioned by I. Ruzsa in a private communication in June 2013.

(ii) I'm not sure if I should provide a reference for this stuff, as I know that self-advertising is unfair. In any case, the material can be perhaps of interest to some peps here, and seems relevant to the topic, which is why I took the freedom to post it.

References.

[1] Y. O. Hamidoune, "The isoperimetric method", in: A. Geroldinger and I. Z. Ruzsa, Combinatorial Number Theory and Additive Group Theory (Birkhäuser, 2009), 87-210.

[2] G. Károlyi, The Cauchy-Davenport theorem in group extensions, Enseign. Math. 51 (2005) 239-254.

[3] J. E. Olson, On the Sum of Two Sets in a Group, J. Number Th. 18 (1984), 110-120.

[4] M. C. Tamburini and J. S. Wilson, On the Generation of Finite Simple Groups by Pairs of Subgroup, J. Algebra 116 (1988), 316-333.

Answer 3

It is worth stating very explicitly (which is the reason for rendering this comment as an answer) that the structure result for the doubling constant $3/2$ actually originates from a 1973 paper by Freiman "Groups and inverse problems of the additive number theory" [Russian]. The original Freiman's formulation is, essentially, as follows: if $|A\cdot A|<3|A|/2$, then there exists a subgroup $S$ of order $|S|=|A\cdot A|$ such that either $A$ is contained in $S$, or $A$ is contained in a coset of $S$ and $S$ is normal.

Indeed, in the same paper Freiman establishes the structure of $A$ under the weaker assumption $|A\cdot A|<8|A|/5$.