To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Added in 24 Hours
Show all languages
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.

Restricted sumset

From Wikipedia, the free encyclopedia

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

where are finite nonempty subsets of a field F and is a polynomial over F.

When , S is the usual sumset which is denoted by nA if ; when

S is written as which is denoted by if . Note that |S| > 0 if and only if there exist with .

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 Z/pZ we have the inequality[1][2]

We may use this to deduce the Erdős–Ginzburg–Ziv theorem: given any sequence of 2n−1 elements in Z/n, there are n elements that sums to zero modulo n. (Here n does not need to be prime.)[3][4]

A direct consequence of the Cauchy-Davenport theorem is: Given any set S of p−1 or more nonzero elements, not necessarily distinct, of Z/pZ, every element of Z/pZ can be written as the sum of the elements of some subset (possibly empty) of S.[5]

Kneser's theorem generalises this to general abelian groups.[6]

Erdős–Heilbronn conjecture

The Erdős–Heilbronn conjecture posed by Paul Erdős and Hans Heilbronn in 1964 states that if p is a prime and A is a nonempty subset of the field Z/pZ.[7] This was first confirmed by J. A. Dias da Silva and Y. O. Hamidoune in 1994[8] who showed that

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,[9] Q. H. Hou and Zhi-Wei Sun in 2002,[10] and G. Karolyi in 2004.[11]

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.[12] Let be a polynomial over a field F. Suppose that the coefficient of the monomial in is nonzero and is the total degree of . If are finite subsets of F with for , then there are such that .

The method using the combinatorial Nullstellensatz is also called the polynomial method. This tool was rooted in a paper of N. Alon and M. Tarsi in 1989,[13] and developed by Alon, Nathanson and Ruzsa in 1995-1996,[9] and reformulated by Alon in 1999.[12]

See also


  1. ^ Nathanson (1996) p.44
  2. ^ Geroldinger & Ruzsa (2009) pp.141–142
  3. ^ Nathanson (1996) p.48
  4. ^ Geroldinger & Ruzsa (2009) p.53
  5. ^ Wolfram's MathWorld, Cauchy-Davenport Theorem,, accessed 20 June 2012.
  6. ^ Geroldinger & Ruzsa (2009) p.143
  7. ^ Nathanson (1996) p.77
  8. ^ 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.
  9. ^ 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.
  10. ^ 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.
  11. ^ 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.
  12. ^ a b Alon, Noga (1999). "Combinatorial Nullstellensatz" (PDF). Combinatorics, Probability and Computing. 8 (1–2): 7–29. doi:10.1017/S0963548398003411. MR 1684621.
  13. ^ Alon, Noga; Tarsi, Michael (1989). "A nowhere-zero point in linear mappings". Combinatorica. 9 (4): 393–395. doi:10.1007/BF02125351. MR 1054015.
  • 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. 165. Springer-Verlag. ISBN 0-387-94655-1. Zbl 0859.11003.

External links

This page was last edited on 12 April 2020, at 10:24
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.