Restricted sumset

---

title: "Restricted sumset" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["augustin-louis-cauchy", "sumsets", "additive-combinatorics", "additive-number-theory"] description: "Sumset of a field subject to a specific polynomial restriction" topic_path: "science/mathematics" source: "https://en.wikipedia.org/wiki/Restricted_sumset" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Sumset of a field subject to a specific polynomial restriction ::

In additive number theory and combinatorics, a restricted sumset has the form

:S={a_1+\cdots+a_n:\ a_1\in A_1,\ldots,a_n\in A_n \ \mathrm{and}\ P(a_1,\ldots,a_n)\not=0},

where A_1,\ldots,A_n are finite nonempty subsets of a field F and P(x_1,\ldots,x_n) is a polynomial over F.

If P is a constant non-zero function, for example P(x_1,\ldots,x_n)=1 for any x_1,\ldots,x_n, then S is the usual sumset A_1+\cdots+A_n which is denoted by nA if A_1=\cdots=A_n=A.

When

:P(x_1,\ldots,x_n) = \prod_{1 \le i

S is written as A_1\dotplus\cdots\dotplus A_n which is denoted by n^{\wedge} A if A_1=\cdots=A_n=A.

Note that |S| 0 if and only if there exist a_1\in A_1,\ldots,a_n\in A_n with P(a_1,\ldots,a_n)\not=0.

Cauchy–Davenport theorem

The Cauchy–Davenport theorem, named after Augustin Louis Cauchy and Harold Davenport, asserts that for any prime p and nonempty subsets A and B of the prime order cyclic group \mathbb{Z}/p\mathbb{Z} we have the inequality

:|A+B| \ge \min{p,, |A|+|B|-1}

where A+B := {a+b \pmod p \mid a \in A, b \in B}, i.e. using modular arithmetic. It can be generalised to arbitrary (not necessarily abelian) groups using a Dyson transform. If A, B are subsets of a group G, then

:|A+B| \ge \min{p(G),, |A|+|B|-1}

where p(G) is the size of the smallest nontrivial subgroup of G (we set it to 1 if there is no such subgroup).

This can be used to deduce the Erdős–Ginzburg–Ziv theorem: given any sequence of 2n−1 elements in the cyclic group \mathbb{Z}/n\mathbb{Z}, there are n elements that sum to zero modulo n. (Here n does not need to be prime.)

A direct consequence of the Cauchy-Davenport theorem is: Given any sequence S of p−1 or more nonzero elements, not necessarily distinct, of \mathbb{Z}/p\mathbb{Z}, every element of \mathbb{Z}/p\mathbb{Z} can be written as the sum of the elements of some subsequence (possibly empty) of S.

Kneser's theorem generalises this to general abelian groups.

Erdős–Heilbronn conjecture

The Erdős–Heilbronn conjecture posed by Paul Erdős and Hans Heilbronn in 1964 states that |2^\wedge A| \ge \min{p,, 2|A|-3} if p is a prime and A is a nonempty subset of the field Z/pZ. This was first confirmed by J. A. Dias da Silva and Y. O. Hamidoune in 1994{{cite journal |author1=Dias da Silva, J. A. |author2=Hamidoune, Y. O. | title = Cyclic spaces for Grassmann derivatives and additive theory | journal = Bulletin of the London Mathematical Society | volume = 26 | year = 1994 | pages = 140–146 | doi = 10.1112/blms/26.2.140 | issue = 2}} who showed that

:|n^\wedge A| \ge \min{p(F),\ n|A|-n^2+1},

where A is a finite nonempty subset of a field F, and p(F) is a prime p if F is of characteristic p, and p(F) = ∞ if F is of characteristic 0. Various extensions of this result were given by Noga Alon, M. B. Nathanson and I. Ruzsa in 1996, Q. H. Hou and Zhi-Wei Sun in 2002,{{cite journal |author1=Hou, Qing-Hu |author2-link=Zhi-Wei Sun |author2=Sun, Zhi-Wei | title = Restricted sums in a field | journal = Acta Arithmetica | volume = 102 | year = 2002 | issue = 3 | pages = 239–249 | mr = 1884717 | doi = 10.4064/aa102-3-3| bibcode = 2002AcAri.102..239H | doi-access = free and G. Karolyi in 2004.{{cite journal | author = Károlyi, Gyula | title = The Erdős–Heilbronn problem in abelian groups | journal = Israel Journal of Mathematics | volume = 139 | year = 2004 | pages = 349–359 | mr = 2041798 | doi = 10.1007/BF02787556| s2cid = 33387005

Combinatorial Nullstellensatz

A powerful tool in the study of lower bounds for cardinalities of various restricted sumsets is the following fundamental principle: the combinatorial Nullstellensatz.{{cite journal | author = Alon, Noga | url = http://www.math.tau.ac.il/~nogaa/PDFS/null2.pdf | title = Combinatorial Nullstellensatz | journal = Combinatorics, Probability and Computing | volume = 8 | issue = 1–2 | year = 1999 | pages = 7–29 | mr = 1684621 | doi = 10.1017/S0963548398003411| s2cid = 209877602 | author-link = Noga Alon

This tool was rooted in a paper of N. Alon and M. Tarsi in 1989,{{cite journal |author1=Alon, Noga |author2=Tarsi, Michael | title = A nowhere-zero point in linear mappings | journal = Combinatorica | volume = 9 | year = 1989 | pages = 393–395 | mr = 1054015 | doi = 10.1007/BF02125351 | issue = 4|s2cid=8208350 |author1-link=Noga Alon | citeseerx = 10.1.1.163.2348 and developed by Alon, Nathanson and Ruzsa in 1995–1996,{{cite journal |author1=Alon, Noga |author2=Nathanson, Melvyn B. |author3=Ruzsa, Imre | url = http://www.math.tau.ac.il/~nogaa/PDFS/anrf3.pdf | title = The polynomial method and restricted sums of congruence classes | journal = Journal of Number Theory | volume = 56 | issue = 2 | year = 1996 | pages = 404–417 | mr = 1373563 | doi = 10.1006/jnth.1996.0029|author1-link=Noga Alon }} and reformulated by Alon in 1999.

References

References

1. Nathanson (1996) p.44
2. Geroldinger & Ruzsa (2009) pp.141–142
3. (2012). "The Cauchy-Davenport Theorem for Finite Groups".
4. DeVos, Matt. (2016). "On a Generalization of the Cauchy-Davenport Theorem". Integers.
5. Nathanson (1996) p.48
6. Geroldinger & Ruzsa (2009) p.53
7. Wolfram's MathWorld, Cauchy-Davenport Theorem, http://mathworld.wolfram.com/Cauchy-DavenportTheorem.html, accessed 20 June 2012.
8. Geroldinger & Ruzsa (2009) p.143
9. Nathanson (1996) p.77

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::