The Inverse Erdős-Heilbronn Problem - Vu, Van H.; Wood, Philip Matchett (The Electronic Journal of Combinatorics, 2009)
The famous Erdős-Heilbronn conjecture (first proved by Dias da Silva and Hamidoune in 1994) asserts that if A is a subset of Z/pZ, the cyclic group of the integers modulo a prime p, then |A+A| {2|A| -3,p}. The bound is sharp, as is shown by choosing A to be an arithmetic progression. A natural inverse result was proven by Karolyi in 2005: if AZ/pZ contains at least 5 elements and |A+A| 2|A| -3 < p, then A must be an arithmetic progression. We consider a large prime p and investigate the following more general question: what is the structure of sets A Z/pZ such that |A+A| (2+ε)|A|? Our main result is an asymptotically complete answer to this question: there exists a function δ(p) = o(1) such that if 200 < |A| (1-ε’)p/2 and if |A+A| (2+ε)|A|, where ε’ -ε δ > 0, then A is contained in an arithmetic progression of length |A+A| -|A| + 3. With the extra assumption that |A| (12- 1^c p ) p, our main result has Dias da Silva and Hamidoune’s theorem and Karolyi’s theorem as corollaries, and thus, our main result provides purely combinatorial proofs for the Erdős-Heilbronn conjecture and an inverse Erdős-Heilbronn theorem.