Alon 1996 polynomial method restricted sums congruence classes

../

proposition_1_2: Alon, Nathanson and Ruzsa's bound for sums of one element from each of k + 1 nonempty subsets of the integers modulo a prime with all summands distinct: when the sets have pairwise distinct sizes and the sizes sum to at most p + C(k+2, 2) - 1, there are at least the sum of the sizes minus C(k+2, 2) plus 1 such sums.

theorem_1_3: The Erdős–Heilbronn conjecture as the paper's Theorem 1.3, attributed to Dias da Silva and Hamidoune: a nonempty subset A of the integers modulo a prime p has at least min(p, 2|A| - 3) sums of two distinct elements, derived from the case k = 1 of Proposition 1.2 and again as the case s = 2 of Theorem 3.3.

theorem_2_1: Alon, Nathanson and Ruzsa's coefficient criterion for restricted sumsets modulo a prime: when |A_i| = c_i + 1 and m is the sum of the c_i minus the degree of h, a nonzero coefficient of the monomial with exponents c_i in (x_0 + ... + x_k)^m h forces at least m + 1 sums a_0 + ... + a_k with a_i in A_i and h(a_0, ..., a_k) nonzero.

theorem_3_2: Alon, Nathanson and Ruzsa's main theorem: for nonempty subsets of the integers modulo a prime with sizes b_0 >= ... >= b_k, the sums of one element from each set with all summands distinct number at least the minimum of p and the sum of the trimmed sizes b'_i minus C(k+2, 2) plus 1, whenever b'_k is positive, and the bound is sharp.

theorem_3_3: The Dias da Silva–Hamidoune theorem as the paper's Theorem 3.3, proved from Theorem 3.2 by the polynomial method: the sums of s distinct elements of a nonempty subset A of the integers modulo a prime p fill at least min(p, s|A| - s^2 + 1) residues.

---

N. Alon, M. B. Nathanson and I. Ruzsa, The Polynomial Method and Restricted Sums of Congruence Classes, J. Number Theory 56 (1996), no. 2, 404--417, article no. 0029, DOI 10.1006/jnth.1996.0029; communicated by Alan C. Woods; received June 1, 1994, revised September 30, 1994 (p. 404); the authors at Tel Aviv University, Lehman College (CUNY) and the Mathematical Institute of the Hungarian Academy of Sciences. Cited as [ANR96] on the problem page. Its reference 1 is the authors' Monthly paper, filed as alon_1995_adding_distinct_congruence_classes_modulo_prime, which announced this paper as "in preparation"; its reference 4 is Dias da Silva and Hamidoune, Cyclic spaces for Grassmann derivatives and additive theory, Bull. London Math. Soc. 26 (1994), 140--146, filed as dias_da_silva_hamidoune_1994_cyclic_spaces_grassmann_derivatives_additive_theory; its reference 5 is the Erdős--Graham monograph, filed as erdos_1980_old_new_problems_results_combinatorial_number_theory.

The copy read for this card is the publisher's production PDF of the printed article: 14 pages, printed pp. 404--417 = PDF pp. 1--14 (printed p. $n$ is PDF p. $n-403$), distilled in April 1996 from the journal's typesetting (its metadata names Acrobat Distiller 2.0 and a creation date of 16 April 1996; each page carries the typesetter's file line in its footer), with a text layer that reads the prose cleanly and drops or substitutes the mathematical symbols (inequality signs vanish, minus signs come out as ampersands, $\ne$ as a brace, summation limits scatter). Provenance: read free of charge from the publisher's open archive, the DOI https://doi.org/10.1006/jnth.1996.0029 resolving to the article's PDF on the publisher's site (PII S0022314X96900293); 366,904 bytes. That copy prints "Copyright © 1996 by Academic Press, Inc. All rights of reproduction in any form reserved." in the footer of its first page (printed p. 404), every other right reserved.

Read status: claims checked for the title page and abstract (p. 404), Theorem 1.1, Proposition 1.2, the remark deriving the Erdős--Heilbronn bound from it and Theorem 1.3 (p. 405), Theorem 3.2 (p. 410) and Theorem 3.3 with its proof and the closing remark of § 3 (p. 411), each read clause by clause on the page images of PDF pp. 1, 2, 7 and 8 on 2026-09-22. The proof of Theorem 3.3 (p. 411, eight lines) was read in full on the page image and its arithmetic checked; the proofs of Theorem 2.1 (pp. 406--407), Lemma 3.1 (pp. 408--409), Proposition 1.2 (pp. 409--410) and Theorem 3.2 (pp. 410--411) were read in the text layer for structure only; § 4 and § 5 (pp. 411--416) and the references (pp. 416--417) were read in the text layer for their statements. On 2026-10-08 the whole article was read on the page images: Theorem 2.1 and its proof with Lemma 2.2 (pp. 406--407), the statement of Lemma 3.1 (p. 408), the restatement and proof of Proposition 1.2 (pp. 409--410) and Theorem 3.2 with its proof and sharpness example (pp. 410--411) clause by clause for the statements and for structure in the proofs, and § 4, § 5 and the references for their statements. Nothing here is independently reviewed.

Contents

• Abstract and § 1, Introduction (pp. 404--405, page images). The abstract announces "a simple and general algebraic technique for obtaining results in Additive Number Theory" and lists its applications as new extensions of the Cauchy--Davenport theorem, the main one being a tight lower bound, in terms of the cardinalities $|A_i|$ alone, on the number of sums $a_0+a_1+\cdots+a_k$ with $a_i\in A_i\subseteq Z_p$ and the summands pairwise distinct. Theorem 1.1 is the Cauchy--Davenport theorem, $|A+B|\ge\min\{p,|A|+|B|-1\}$, cited to Davenport 1935 and proved in [1] by the method described here. Proposition 1.2 (p. 405, quoted): "Let $p$ be a prime, and let $A_0,A_1,\ldots,A_k$ be nonempty subsets of the cyclic group $Z_p$. If $|A_i|\ne|A_j|$ for all $0\le i<j\le k$ and $\sum_{i=0}^k|A_i|\le p+\binom{k+2}2-1$ then $|{a_0+a_1+\cdots+a_k: a_i\in A_i,\ a_i\ne a_j\text{ for all }i\ne j}| \ge\sum_{i=0}^k|A_i|-\binom{k+2}2+1$." The remark after it specializes to $k=1$, $A_0=A$ and $A_1=A-\{a\}$ for any $a\in A$: when $A\subset Z_p$ and $2|A|-1\le p+2$, the sums $a_1+a_2$ with $a_1,a_2\in A$ and $a_1\ne a_2$ number at least $2|A|-3$, from which the paper says Theorem 1.3 follows easily. The same remark dates the conjecture to Erdős and Heilbronn in 1964, cites [5] for it, and credits its recent proof to Dias da Silva and Hamidoune [4] by linear-algebraic and representation-theoretic tools. Theorem 1.3 ([4]) (p. 405, quoted): "If $p$ is a prime, and $A$ is a nonempty subset of $Z_p$, then $|\{a+a': a,a'\in A,\ a\ne a'\}|\ge\min\{p,2|A|-3\}$." Paged at theorem_1_3.
• § 2, The General Theorem (pp. 406--408). For a polynomial $h$ over $Z_p$ in $k+1$ variables, $\bigoplus_h\sum_{i=0}^kA_i$ is the set of sums $a_0+\cdots+a_k$ with $a_i\in A_i$ and $h(a_0,\ldots,a_k)\ne0$. Theorem 2.1: with $|A_i|=c_i+1$ and $m=\sum_{i=0}^kc_i-\deg(h)$, whenever the coefficient of $\prod_{i=0}^kx_i^{c_i}$ in $(x_0+\cdots+x_k)^mh(x_0,\ldots,x_k)$ does not vanish in $Z_p$, the restricted sumset has at least $m+1$ elements, $|\bigoplus_h\sum_{i=0}^kA_i|\ge m+1$, so that $m<p$. Lemma 2.2 is the vanishing lemma for polynomials of bounded degree in each variable on a product of sets (cited to Alon--Tarsi [2], reproved in half a page), and the proof of Theorem 2.1 multiplies $h$ by $\prod_{e\in E}(x_0+\cdots+x_k-e)$ over a multiset $E$ of $m$ elements covering the sumset, reduces each $x_i^{c_i+1}$ through $\prod_{a\in A_i}(x_i-a)$ and reads off the surviving top coefficient. The section closes with the derivation of the Cauchy--Davenport theorem ($h\equiv1$, $k=1$, coefficient $\binom m{c_0}$). Paged at theorem_2_1.
• § 3, Adding Distinct Residues (pp. 408--411). Lemma 3.1: if $\sum_{i=0}^kc_i=m+\binom{k+1}2$, the coefficient of $\prod_ix_i^{c_i}$ in $(x_0+\cdots+x_k)^m\prod_{k\ge i>j\ge0}(x_i-x_j)$ is $\frac{m!}{c_0!\cdots c_k!}\prod_{k\ge i>j\ge0}(c_i-c_j)$, proved from the Vandermonde determinant. $\bigoplus_{i=0}^kA_i$ denotes the sums $a_0+\cdots+a_k$ with $a_i\in A_i$ and all $a_i$ distinct, the case $h=\prod_{i>j}(x_i-x_j)$; Proposition 1.2 follows from Lemma 3.1 and Theorem 2.1 since $m<p$ and the $c_i$ are pairwise distinct (paged at proposition_1_2). Theorem 3.2 (p. 410, quoted): "Let $p$ be a prime, and let $A_0,\ldots,A_k$ be nonempty subsets of $Z_p$, where $|A_i|=b_i$, and suppose $b_0\ge b_1\cdots\ge b_k$. Define $b'_0,\ldots,b'_k$ by $b'_0=b_0$ and $b'_i=\min\{b'_{i-1}-1,b_i\}$, for $1\le i\le k$. (2) If $b'_k>0$ then $|\bigoplus_{i=0}^kA_i|\ge\min\{p,\sum_{i=0}^kb'_i-\binom{k+2}2+1\}$. Moreover, the above estimate is sharp for all possible values of $p\ge b_0\ge\cdots\ge b_k$." (The print omits the $\ge$ after $b_1$ in the hypothesis.) Its proof passes to subsets $A'_i\subseteq A_i$ of the pairwise distinct sizes $b'_i$, applies Proposition 1.2 when $\sum b'_i\le p+\binom{k+2}2-1$ and otherwise trims the sizes by an operator $T$ to a sequence $b''_0>\cdots>b''_k\ge1$ with $\sum b''_i=p+\binom{k+2}2-1$; sharpness is the intervals $A_i=\{1,2,\ldots,b_i\}$, whose distinct-summand sums lie in $\{\binom{k+2}2,\ldots,\sum b'_i\}$ (paged at theorem_3_2). The paper then derives the theorem of Dias da Silva and Hamidoune [4] from a special case of Theorem 3.2. Theorem 3.3 ([4]) (p. 411, quoted): "Let $p$ be a prime and let $A$ be a nonempty subset of $Z_p$. Let $s^\wedge A$ denote the set of all sums of $s$ distinct elements of $A$. Then $|s^\wedge A|\ge\min\{p,s|A|-s^2+1\}$." The proof takes $A_i=A$ for $s=k+1$ sets, so $b'_i=|A|-i$, and computes $\sum_{i=0}^k(|A|-i)-\binom{k+2}2+1=(k+1)|A|-(k+1)^2+1$. The section ends with the sentence "The case $s=2$ of the last theorem settles a problem of Erdős and Heilbronn" and a list of the earlier partial results on the conjecture, [12], [9], [13], [11] and [6] (Rickert's 1976 thesis, Mansfield 1981, Rødseth 1994, Pyber's personal communication and the Freiman--Low--Pitman preprint of 1992). Paged at theorem_3_3.
• § 4, Further Examples (pp. 411--414). Proposition 4.1 (from [1]): $|\{a+b: a\in A,\,b\in B,\,ab\ne1\}|\ge\min\{p,|A|+|B|-3\}$. Proposition 4.2: sums $a_0+\cdots+a_k$ with $\prod a_i\ne g$ number at least $\min\{p,\sum|A_i|-2k-1\}$ (the print's sum in that minimum runs to $p$, a misprint for $k$). Proposition 4.3: sums with $a_ia_j\ne1$ for all $i<j$ number at least $\min\{p,\sum|A_i|-(k+1)^2+1\}$ when every $|A_i|\ge k+1$, not sharp; Proposition 4.4 (a probabilistic argument): the set is nonempty when the $A_i\subseteq Z_p-\{1,-1\}$ each have $s>\log_2(k+1)$ elements, tight for $s\le(p-3)/2$. Proposition 4.5: for $|A|>|B|$ and any $e$, $|\{a+b: a\in A,\,b\in B,\,ab\ne e,\,a\ne b\}|\ge\min\{p,|A|+|B|-4\}$, tight for $|A|>|B|>1$ by an arithmetic-progression example.
• § 5, Concluding Remarks and Open Problems (pp. 414--416). 1. All results hold over any field of characteristic $p$. 2. Theorem 3.3 gives $s^\wedge A=Z_p$ when $|A|\ge(p+s^2-1)/s$, which the paper uses for an explicit scheme for write-once memories (a notion of Rivest and Shamir [14]; $w(\langle v\rangle^t)$ is the fewest write-once bits that can hold one of $v$ values through $t$ updates) that improves one of their schemes and gives $w(\langle p\rangle^{0.35p})\le p-1$ for every prime $p$; the conjectured asymptotic $w(\langle v\rangle^t)=(1+o(1))\max\{t,t\log v/\log t\}$ as $t,v\to\infty$ is refuted separately, by a counting argument giving $w(\langle v\rangle^{\varepsilon v})\ge2\varepsilon v$ for every fixed $0<\varepsilon<0.5$ (p. 415). 3. The difficulty in further applications of Theorem 2.1 is computing the coefficient; for sums with $a_i-a_j\notin E$ the relevant coefficients connect to Dyson's conjecture. 4. Vosper's characterization of equality in Cauchy--Davenport; the analogous problem for Proposition 1.2, Theorem 1.3 and § 4 is posed. 5. Non-prime analogs are posed.
• References (pp. 416--417), nineteen items, including [1] the authors' 1995 Monthly paper, [2] Alon and Tarsi 1992, [3] Davenport 1935, [4] Dias da Silva and Hamidoune 1994, [5] Erdős and Graham 1980, [6] Freiman, Low and Pitman 1992 (preprint), [13] Rødseth 1994, [14] Rivest and Shamir 1982 and [16], [17] Vosper 1956.

Compiled scope

The paper is compiled at statement depth for its main results and the results Problem 476 consumes, each with a result page: Theorem 2.1 (p. 406), the general coefficient criterion; Proposition 1.2 (p. 405) and Theorem 3.2 (p. 410), the bounds for sums with distinct summands; and Theorem 1.3 (p. 405) and Theorem 3.3 (p. 411), the results Problem 476 consumes. All were read on the page images; their proofs were followed for structure, except that of Theorem 3.3, read in full. Lemmas 2.2 and 3.1 and § 4 are mapped above without pages of their own. Nothing here is independently reviewed.

Bears on. #476: Theorem 1.3 (printed p. 405, PDF p. 2), "If $p$ is a prime, and $A$ is a nonempty subset of $Z_p$, then $|\{a+a': a,a'\in A,\ a\ne a'\}|\ge\min\{p,2|A|-3\}$", is the problem's displayed inequality $|A\hat{+}A|\ge\min(2|A|-3,p)$ (the problem's $A\hat{+}A$ is the paper's set of sums of two distinct elements, its $2^\wedge A$; for $|A|\le1$ both sides are trivial). The paper labels it "([4])", Dias da Silva and Hamidoune, and gives two derivations by the polynomial method: from the case $k=1$ of Proposition 1.2 (p. 405), and as the case $s=2$ of Theorem 3.3 (p. 411), "The case $s=2$ of the last theorem settles a problem of Erdős and Heilbronn." Theorem 3.3 (printed p. 411, PDF p. 8), $|s^\wedge A|\ge\min\{p,s|A|-s^2+1\}$ for the sums of $s$ distinct elements, is the general theorem of Dias da Silva and Hamidoune, here stated and proved in a refereed paper from Theorem 3.2; in the form "sums of exactly $s$ distinct elements" it also gives the general conjecture (73) of Erdős's 1965 lectures, $\min(p,rk-r^2+1)$ distinct sums of at most $r$ distinct residues out of $k$, since every sum of exactly $r$ distinct elements is a sum of at most $r$ (a filing observation, not a claim the paper makes). The original paper of Dias da Silva and Hamidoune is filed separately (reference 4 above), and this paper's proofs of Theorems 1.3 and 3.3 are its own, not that paper's. The paper's own results behind those proofs bear on the problem only through them: Proposition 1.2 (p. 405) with $k=1$, $A_0=A$, $A_1=A-\{a\}$ gives the problem's bound $2|A|-3$ when $2|A|-1\le p+2$, the paper's first route to Theorem 1.3; Theorem 3.2 (p. 410) with $k=1$ and $A_0=A_1=A$, $|A|\ge2$, gives $\min(p,2|A|-3)$, the route through Theorem 3.3, and its sharpness example $\{1,\ldots,b\}$ attains the problem's bound; Theorem 2.1 (p. 406) is the criterion from which both are derived and does not mention the problem.

Results.

• Proposition 1.2 (p. 405): at least $\sum_i|A_i|-\binom{k+2}2+1$ sums of pairwise distinct summands $a_i\in A_i$, for nonempty $A_i\subseteq Z_p$, when the $|A_i|$ are pairwise distinct and $\sum_i|A_i|\le p+\binom{k+2}2-1$.
• Theorem 1.3 (p. 405): $|\{a+a': a,a'\in A,\ a\ne a'\}|\ge\min\{p,2|A|-3\}$ for a nonempty $A\subseteq Z_p$; the Erdős--Heilbronn conjecture, from the case $k=1$ of Proposition 1.2.
• Theorem 2.1 (p. 406): a nonzero coefficient of $\prod_ix_i^{c_i}$ in $(x_0+\cdots+x_k)^mh$, with $|A_i|=c_i+1$ and $m=\sum_ic_i-\deg(h)$, gives $|\bigoplus_h\sum_{i=0}^kA_i|\ge m+1$.
• Theorem 3.2 (p. 410): $|\bigoplus_{i=0}^kA_i|\ge\min\{p,\sum_ib'_i-\binom{k+2}2+1\}$ for the trimmed sizes $b'_i$ when $b'_k>0$, sharp for all $p\ge b_0\ge\cdots\ge b_k$.
• Theorem 3.3 (p. 411): $|s^\wedge A|\ge\min\{p,s|A|-s^2+1\}$ for the sums of $s$ distinct elements of a nonempty $A\subseteq Z_p$, from Theorem 3.2 with $A_i=A$.

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.