The Structure of Critical Product Sets

Let $G$ be a multiplicative group, let $A,B\subseteq G$ be finite and nonempty, and define the product set AB = {ab \mida \in A$and$b \in B}. Two fundamental problems in combinatorial number theory are to find lower bounds on $\mathrm{\mid }AB\mathrm{\mid }$, and then to determine structural properties of $A$ and $B$ under the assumption that $\mathrm{\mid }AB\mathrm{\mid }$ is small. We focus on the extreme case when $\mathrm{\mid }AB\mathrm{\mid }<\mathrm{\mid }A\mathrm{\mid }+\mathrm{\mid }B\mathrm{\mid }$, and call any such pair $(A,B)$ \emph{critical}. In the case when $\mathrm{\mid }G\mathrm{\mid }$ is prime, the Cauchy-Davenport Theorem asserts that $\mathrm{\mid }AB\mathrm{\mid }\ge \min \mathrm{\mid }G\mathrm{\mid },\mathrm{\mid }A\mathrm{\mid }+\mathrm{\mid }B\mathrm{\mid }-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\le G$ so that $\mathrm{\mid }AB\mathrm{\mid }\ge \mathrm{\mid }A\mathrm{\mid }+\mathrm{\mid }B\mathrm{\mid }-\mathrm{\mid }H\mathrm{\mid }$ 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\le G$ so that $|AB| \ge |A| + |B| - |H|$andsothatforevery$y \in AB$thereexists$x \in G$ so that $y(x^{-1}Hx)\subseteq AB$.