KAIST Discrete Math Seminar

Let A and B be finite nonempty subsets of a multiplicative group G, and consider the product set AB = { ab | a in A and b in B }. When |G| is prime, a famous theorem of Cauchy and Davenport asserts that |AB| is at least the minimum of {|G|, |A| + |B| – 1}. This lower bound was refined by Vosper, who characterized all pairs (A,B) in such a group for which |AB| < |A| + |B|. Kneser generalized the Cauchy-Davenport theorem by providing a natural lower bound on |AB| which holds in every abelian group. Shortly afterward, Kemperman determined the structure of those pairs (A,B) with |AB| < |A| + |B| in abelian groups. Here we present a further generalization of these results to arbitrary groups. Namely we generalize Kneser’s Theorem, and we determine the structure of those pairs with |AB| < |A| + |B| in arbitrary groups.