The Inverse Erdős-Heilbronn Problem
Van H. Vu, Philip Matchett Wood · The Electronic Journal of Combinatorics · 2009
Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.
The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2009
Abstract
The famous Erdős-Heilbronn conjecture (first proved by Dias da Silva and Hamidoune in 1994) asserts that if $A$ is a subset of ${\Bbb Z}/p{\Bbb Z}$, the cyclic group of the integers modulo a prime $p$, then $|A\widehat{+}A| \ge \min\{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 $A\subset {\Bbb Z}/p{\Bbb Z}$ contains at least 5 elements and $|A\widehat{+}A| \le 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 \subset {\Bbb Z}/p{\Bbb Z}$ such that $|A\widehat{+}A| \le (2+\epsilon)|A|$? Our main result is an asymptotically complete answer to this question: there exists a function $\delta(p) = o(1)$ such that if $200 < |A| \le (1-\epsilon')p/2$ and if $|A\widehat{+}A| \le (2+\epsilon)|A|$, where $\epsilon' -\epsilon \ge \delta > 0$, then $A$ is contained in an arithmetic progression of length $|A\widehat{+}A| -|A| + 3$.
With the extra assumption that $|A| \le ({1\over 2}- {1\over\log^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.
Open the resolved locator · 10.37236/189
Metadata licence: OpenAlex metadata (CC0)