Problem 476

Let $A\subseteq \mathbb{F}_p$ . Let

A\hat{+}A = \{ a+b : a\neq b \in A\}.

Is it true that

\lvert A\hat{+}A\rvert \geq \min(2\lvert A\rvert-3,p)?

Source: erdosproblems.com/476

Number theory
Additive combinatorics

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved. The site's status-defining source is the paper of Dias da Silva and Hamidoune [dSHa94] (Bull. London Math. Soc. 26 (1994), no. 2, 140--146, refereed), at its Theorem 4.1 (printed p. 144; result page): for a finite subset $A$ of a field of characteristic $p$ and a positive integer $m$ , the sums of the $m$ -subsets of $A$ number at least $\min\{p,m|A|-m^2+1\}$ , and the remark after its proof states the case $m=2$ for $A\subseteq Z_p$ , $|A\wedge A|\ge\min\{p,2|A|-3\}$ , as the conjecture of Erdős and Heilbronn; its proof uses linear algebra and the representation theory of the symmetric group. The general theorem is also stated and proved in the refereed paper [ANR96], whose Theorem 3.3 (p. 411; result page) states it with the label "([4])" and proves it from that paper's own Theorem 3.2 by the polynomial method. The statement itself is also proved in refereed papers: Theorem 2 of Alon, Nathanson and Ruzsa [ANR95] (Amer. Math. Monthly 102 (1995), 250--255; result page), labeled by them "(Dias da Silva--Hamidoune [3])", states $|2^\wedge A|\ge\min(p,2k-3)$ for $|A|=k\ge2$ and derives it in three lines from their Theorem 1 (Alon and Ruzsa 1995), $|A\hat{+}B|\ge\min(p,k+l-2)$ for $|A|=k\ne l=|B|$ , proved by the polynomial method (the Alon--Tarsi lemma with interpolation); and Theorem 1.3 of [ANR96] (p. 405; result page), labeled "([4])", states $|\{a+a': a,a'\in A,\ a\ne a'\}|\ge\min\{p,2|A|-3\}$ for nonempty $A\subseteq Z_p$ and derives it from the case $k=1$ of that paper's Proposition 1.2, and again as the case $s=2$ of its Theorem 3.3. An external Lean proof following the same method is described under Formalization. The site's label is PROVED (LEAN); its Lean mark is a catalog label explained there. The claim pages are Dias da Silva and Hamidoune (accepted on the refereed publication and the site's credit) and Alon, Nathanson and Ruzsa (the polynomial-method proof; accepted on the refereed publications; the Lean proof in the lean-proofs repository, which declares itself a formalization of their argument, is its formalization link, third-party Lean that gives no formalized evidence).

dSHa94: Dias da Silva, J. A. and Hamidoune, Y. O., Cyclic spaces for Grassmann derivatives and additive theory. Bull. London Math. Soc. 26 (1994), no. 2, 140--146, DOI 10.1112/blms/26.2.140 (March 1994; Crossref record). Theorem 4.1 with its proof, the remark stating the case $m=2$ and Example 4.1, printed p. 144, Corollary 3.3 (p. 144) and Theorem 3.2 (p. 143) are the passages cited, with the introduction (pp. 140--141). Library home: Dias da Silva and Hamidoune 1994; paged at Dias da Silva and Hamidoune 1994, Theorem 4.1.
ANR95: Alon, N., Nathanson, M. B. and Ruzsa, I., Adding distinct congruence classes modulo a prime. Amer. Math. Monthly 102 (1995), no. 3, 250--255, DOI 10.1080/00029890.1995.11990565 (Crossref record); the page numbers are those of the authors' version (7 pp.) on the first author's publication list: Theorem 1 on p. 3, Theorem 2 and the sharpness example on p. 5. Library home: Alon and Ruzsa 1995.
ANR96: Alon, N., Nathanson, M. B. and Ruzsa, I. Z., The polynomial method and restricted sums of congruence classes. J. Number Theory 56 (1996), no. 2, 404--417, DOI 10.1006/jnth.1996.0029; the general polynomial-method paper announced in [ANR95] as "in preparation". Theorem 1.3, printed p. 405 (PDF p. 2 of the publisher's open-archive file); Theorem 3.2, p. 410 (PDF p. 7); Theorem 3.3 with its proof, p. 411 (PDF p. 8). Library home: Alon and Ruzsa 1996; paged at Alon and Ruzsa 1996, Theorem 1.3 (Dias da Silva–Hamidoune) and Alon and Ruzsa 1996, Theorem 3.3 (Dias da Silva–Hamidoune).
Er65b: Erdős, P., Some recent advances and current problems in number theory. Lectures on Modern Mathematics, Vol. III (Wiley, 1965), 196--244; display (73), printed p. 230. Library home: Erdős 1965 and its Erdős 1965, Display (74) page, which records conjecture (73).
ErGr80: Erdős, P. and Graham, R. L., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique 28, Université de Genève (1980); printed p. 95. Library home: Erdős and Graham 1980.
ErHe64: Erdős, P. and Heilbronn, H., On the addition of residue classes mod $p$ . Acta Arith. 9 (1964), no. 2, 149--159, DOI 10.4064/aa-9-2-149-159 (the monograph's [Er-He (64)] and the 1965 lectures' "our paper will appear in Acta Arithmetica"). Theorem I, printed p. 149: " $F(N)>0$ if $k\geq3(6p)^{1/2}$ ", where $F(N)$ counts the subset sums of $k$ distinct nonzero residues congruent to $N$ ; the appendix "Unproved Conjectures", pp. 158--159. The paper does not state this problem's question (Remaining gaps, item 4). Library home: Erdős and Heilbronn 1964 and its Erdős and Heilbronn 1964, Theorem I page.
Gu04: Guy, R. K., Unsolved problems in number theory, 3rd ed., Problem Books in Mathematics, Springer, New York (2004), xviii+437 pp. Section C15 "Maximal zero-sum-free sets", printed pp. 193--194, the section the site cites; the passage on p. 194: after the Erdős--Heilbronn theorem for $k\ge3(6p)^{1/2}$ and Olson's $k>2\sqrt p$ , it reports the conjecture that the pair sums $a_i+a_j$ , $i<j$ , of $k$ distinct residues take at least $\min\{p,2k-3\}$ values, names partial results of Mansfield, of Rødseth and of Freiman, Low and Pitman, credits Dias da Silva and Hamidoune with the complete proof and with the general bound $|A^h|\ge\min\{p,hk-h^2+1\}$ for the sums of $h$ distinct elements of a $k$ -set $A\subseteq\mathbb Z/p\mathbb Z$ , and records Nathanson's simplification of their proof and the Nathanson--Ruzsa bound $\min\{p,k+l-2\}$ for the sums $a+b$ , $a\ne b$ , over sets of sizes $k>l$ ; a report with references and no proof, a further attribution of the [dSHa94] theorem beside those of [ANR95] and [ANR96]. Library home: Guy 2004.
Ya26: Yang, G., Linear algebraic method and the Erdős--Heilbronn conjecture. arXiv:2605.19542v1 (19 May 2026); a new elementary proof of the Alon--Nathanson--Ruzsa theorem by linear algebra, per its abstract (arXiv API). Not held; a reproof of the settled statement that the site does not credit, recorded as context and given no claim page.

Problem 476

Status

Proof claims

Discussion