The Structure of Critical Product Sets

Original · EN

Let G be a multiplicative group, let A,B G be finite and nonempty, and define the product set AB = ab a ∈ A and b ∈ B. Two fundamental problems in combinatorial number theory are to find lower bounds on |AB|, and then to determine structural properties of A and B under the assumption that |AB| is small. We focus on the extreme case when |AB| < |A| + |B|, and call any such pair (A,B) critical. In the case when |G| is prime, the Cauchy-Davenport Theorem asserts that |AB| ≥ |G|, |A| + |B| - 1, and Vosper refined this result by classifying all critical pairs in these groups. For abelian groups, Kneser proved a natural generalization of Cauchy-Davenport by showing that there exists H ≤ G so that |AB| ≥ |A| + |B| - |H| and ABH = AB. Kemperman then proved a result which characterizes the structure of all critical pairs in abelian groups. Our main result gives a classification of all critical pairs in an arbitrary group G. As a consequence of this we derive the following generalization of Kneser's Theorem to arbitrary groups: There exists H ≤ G so that |AB| ≥ |A| + |B| - |H| and so that for every y ∈ AB there exists x ∈ G so that y(x⁻¹ H x) AB.