Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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 unpublished work of Sanders 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.

share|improve this answer

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$.

share|improve this answer
Thank you for pointing this out, and sorry for being a bit sloppy with explict attribution. I will edit my answer slightly. Just one remark which might be relavant as the OP asks for simple groups specificially: I believe that also in the coset case the subgroup does not have to be normal but only the element needs to be in the normalizer of the subgroup; say, an alternating group will contain nonsimple abelian subgroups (of course nonnormal) and 'everything' can happen 'inside' this abelian subgroup. –  quid Feb 20 '12 at 0:45
Absolutely - but I just serve as a translator here :-) –  Seva Feb 20 '12 at 10:16
Thank you for the clarification. –  quid Feb 20 '12 at 10:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.