go-v.orgdoi

The Inverse Erdős-Heilbronn Problem

Van H. Vu, Philip Matchett Wood · The Electronic Journal of Combinatorics · 2009

  • DOI 10.37236/189
  • Publisher Electronic Journal of Combinatorics
  • Type article
  • Issued 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)