restricted sumset
A sumset of a field subject to a specific polynomial restriction
≈ 7 min read
restricted sumset. encyclopegia.org, snapshot restricted-sumset-098771-8efd6c4a84f83edd. /a/restricted-sumset
Names in other languages
- caSuma restringida de conjunts
- Françaissomme restreinte d'ensemblesNullstellensatz combinatoire
- myကန့်သတ် ပေါင်းလဒ်အစု
- Englishrestricted sumset
- 日本語制限和集合
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In additive number theory and combinatorics, a restricted sumset has the form
- S={a1+⋯+an: a1∈A1,…,an∈An and P(a1,…,an)≠0},
where A1,…,An are finite nonempty subsets of a field F and P(x1,…,xn) is a polynomial over F.
If P is a constant non-zero function, for example P(x1,…,xn)=1 for any x1,…,xn, then S is the usual sumset A1+⋯+An which is denoted by nA if A1=⋯=An=A.
When
- P(x1,…,xn)=∏1≤i<j≤n(xj−xi),
S is written as A1∔⋯∔An which is denoted by n∧A if A1=⋯=An=A.
Note that |S| > 0 if and only if there exist a1∈A1,…,an∈An with P(a1,…,an)≠0.
Cauchy–Davenport theorem
edit edit sourceThe 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 ℤ/pℤ we have the inequality[1][2][3]
- |A+B|≥min{p,|A|+|B|−1}
where A+B:={a+b(modp)∣a∈A,b∈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[4]
- |AB|≥min{p(G),|A|+|B|−1}
where p(G) is the size of the smallest nontrivial subgroup of G (we set it to ∞ 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 ℤ/nℤ, there are n elements that sum to zero modulo n. (Here n does not need to be prime.)[5][6]
A direct consequence of the Cauchy-Davenport theorem is: Given any sequence S of p−1 or more nonzero elements, not necessarily distinct, of ℤ/pℤ, every element of ℤ/pℤ can be written as the sum of the elements of some subsequence (possibly empty) of S.[7]
Kneser's theorem generalises this to general abelian groups.[8]
Erdős–Heilbronn conjecture
edit edit sourceThe Erdős–Heilbronn conjecture posed by Paul Erdős and Hans Heilbronn in 1964 states that |2∧A|≥min{p,2|A|−3} if p is a prime and A is a nonempty subset of the field Z/pZ.[9] This was first confirmed by J. A. Dias da Silva and Y. O. Hamidoune in 1994[10] who showed that
- |n∧A|≥min{p(F), n|A|−n2+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,[11] Q. H. Hou and Zhi-Wei Sun in 2002,[12] and G. Karolyi in 2004.[13]
Combinatorial Nullstellensatz
edit edit sourceA tool in the study of lower bounds for cardinalities of various restricted sumsets is the following principle: the combinatorial Nullstellensatz.[14] Let f(x1,…,xn) be a polynomial over a field F. Suppose that the coefficient of the monomial x1k1⋯xnkn in f(x1,…,xn) is nonzero and k1+⋯+kn is the total degree of f(x1,…,xn). If A1,…,An are finite subsets of F with |Ai|>ki for i=1,…,n, then there are a1∈A1,…,an∈An such that f(a1,…,an)≠0.
This result was rooted in a paper of N. Alon and M. Tarsi in 1989,[15] and developed by Alon, Nathanson and Ruzsa in 1995–1996,[11] and reformulated by Alon in 1999.[14]
See also
edit edit sourceReferences
edit edit source- ^ Nathanson (1996) p.44 Wikipedia revision 1367303758, retrieved 2026-11-18
- ^ Geroldinger & Ruzsa (2009) pp.141–142 Wikipedia revision 1367303758, retrieved 2026-11-18
- ^ Jeffrey Paul Wheeler (2012). "The Cauchy-Davenport Theorem for Finite Groups". arXiv:1202.1816 [math.CO]. Wikipedia revision 1367303758, retrieved 2026-11-18
- ^ DeVos, Matt (2016). "On a Generalization of the Cauchy-Davenport Theorem". Integers. 16. Wikipedia revision 1367303758, retrieved 2026-11-18
- ^ Nathanson (1996) p.48 Wikipedia revision 1367303758, retrieved 2026-11-18
- ^ Geroldinger & Ruzsa (2009) p.53 Wikipedia revision 1367303758, retrieved 2026-11-18
- ^ Wolfram's MathWorld, Cauchy-Davenport Theorem, http://mathworld.wolfram.com/Cauchy-DavenportTheorem.html, accessed 20 June 2012. Wikipedia revision 1367303758, retrieved 2026-11-18
- ^ Geroldinger & Ruzsa (2009) p.143 Wikipedia revision 1367303758, retrieved 2026-11-18
- ^ Nathanson (1996) p.77 Wikipedia revision 1367303758, retrieved 2026-11-18
- ^ Dias da Silva, J. A.; Hamidoune, Y. O. (1994). "Cyclic spaces for Grassmann derivatives and additive theory". Bulletin of the London Mathematical Society. 26 (2): 140–146. doi:10.1112/blms/26.2.140. Wikipedia revision 1367303758, retrieved 2026-11-18
- ^ a b Alon, Noga; Nathanson, Melvyn B.; Ruzsa, Imre (1996). "The polynomial method and restricted sums of congruence classes" (PDF). Journal of Number Theory. 56 (2): 404–417. doi:10.1006/jnth.1996.0029. MR 1373563. Wikipedia revision 1367303758, retrieved 2026-11-18
- ^ Hou, Qing-Hu; Sun, Zhi-Wei (2002). "Restricted sums in a field". Acta Arithmetica. 102 (3): 239–249. Bibcode:2002AcAri.102..239H. doi:10.4064/aa102-3-3. MR 1884717. Wikipedia revision 1367303758, retrieved 2026-11-18
- ^ Károlyi, Gyula (2004). "The Erdős–Heilbronn problem in abelian groups". Israel Journal of Mathematics. 139: 349–359. doi:10.1007/BF02787556. MR 2041798. S2CID 33387005. Wikipedia revision 1367303758, retrieved 2026-11-18
- ^ a b Alon, Noga (1999). "Combinatorial Nullstellensatz" (PDF). Combinatorics, Probability and Computing. 8 (1–2): 7–29. doi:10.1017/S0963548398003411. MR 1684621. S2CID 209877602. Wikipedia revision 1367303758, retrieved 2026-11-18
- ^ Alon, Noga; Tarsi, Michael (1989). "A nowhere-zero point in linear mappings". Combinatorica. 9 (4): 393–395. CiteSeerX 10.1.1.163.2348. doi:10.1007/BF02125351. MR 1054015. S2CID 8208350.
{{cite journal}}: Cite uses deprecated parameter|citeseerx=(help) Wikipedia revision 1367303758, retrieved 2026-11-18
- Geroldinger, Alfred; Ruzsa, Imre Z., eds. (2009). Combinatorial number theory and additive group theory. Advanced Courses in Mathematics CRM Barcelona. Elsholtz, C.; Freiman, G.; Hamidoune, Y. O.; Hegyvári, N.; Károlyi, G.; Nathanson, M.; Solymosi, J.; Stanchescu, Y. With a foreword by Javier Cilleruelo, Marc Noy and Oriol Serra (Coordinators of the DocCourse). Basel: Birkhäuser. ISBN 978-3-7643-8961-1. Zbl 1177.11005.
- Nathanson, Melvyn B. (1996). Additive Number Theory: Inverse Problems and the Geometry of Sumsets. Graduate Texts in Mathematics. Vol. 165. Springer-Verlag. ISBN 0-387-94655-1. Zbl 0859.11003.
External links
edit edit sourceText derived from https://en.wikipedia.org/w/index.php?oldid=1367303758 under CC BY-SA 4.0; modifications have been made.