Restricted sumset

Restricted sumset

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.

When P(x_1,\ldots,x_n)=1, 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<j\le n}(x_j-x_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.

Contents

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 field \Bbb Z/p\Bbb Z we have the inequality

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

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 \Bbb Z/p\Bbb Z. This was first confirmed by J. A. Dias da Silva and Y. O. Hamidoune in 1994[1] 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)=\infty if F is of characteristic 0. Various extensions of this result were given by Noga Alon, M. B. Nathanson and I. Ruzsa in 1996,[2] Q. H. Hou and Zhi-Wei Sun in 2002,[3] and G. Karolyi in 2004.[4]

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.[5] Let f(x_1,\ldots,x_n) be a polynomial over a field F. Suppose that the coefficient of the monomial x_1^{k_1}\cdots x_n^{k_n} in f(x_1,\ldots,x_n) is nonzero and k_1+\cdots+k_n is the total degree of f(x_1,\ldots,x_n). If A_1,\ldots,A_n are finite subsets of F with | Ai | > ki for i=1,\ldots,n, then there are a_1\in A_1,\ldots,a_n\in A_n such that f(a_1,\ldots,a_n)\not=0.

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,[6] and developed by Alon, Nathanson and Ruzsa in 1995-1996,[2] and reformulated by Alon in 1999.[5]

References

  1. ^ Dias da Silva, J. A.; Hamidoune, Y. O. (1994). "Cyclic spaces for Grassman derivatives and additive theory". Bulletin of the London Mathematical Society 26 (2): 140–146. doi:10.1112/blms/26.2.140. 
  2. ^ a b Alon, Noga; Nathanson, Melvyn B.; Ruzsa, Imre (1996). "The polynomial method and restricted sums of congruence classes". Journal of Number Theory 56 (2): 404–417. doi:10.1006/jnth.1996.0029. MR1373563. http://www.math.tau.ac.il/~nogaa/PDFS/anrf3.pdf. 
  3. ^ Hou, Qing-Hu; Sun, Zhi-Wei (2002). "Restricted sums in a field". Acta Arithmetica 102 (3): 239–249. doi:10.4064/aa102-3-3. MR1884717. 
  4. ^ Károlyi, Gyula (2004). "The Erdős–Heilbronn problem in abelian groups". Israel Journal of Mathematics 139: 349–359. doi:10.1007/BF02787556. MR2041798. 
  5. ^ a b Alon, Noga (1999). "Combinatorial Nullstellensatz". Combinatorics, Probability and Computing 8 (1–2): 7–29. doi:10.1017/S0963548398003411. MR1684621. http://www.math.tau.ac.il/~nogaa/PDFS/null2.pdf. 
  6. ^ Alon, Noga; Tarsi, Michael (1989). "A nowhere-zero point in linear mappings". Combinatorica 9 (4): 393–395. doi:10.1007/BF02125351. MR1054015. 

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Международная математическая олимпиада — Логотип олимпиады Международная математическая олимпиада (ММО, англ. IMO, International Mathematical Olympiad)  ежегодное соревнование по математике для школьников. Это …   Википедия

  • List of mathematics articles (R) — NOTOC R R. A. Fisher Lectureship Rabdology Rabin automaton Rabin signature algorithm Rabinovich Fabrikant equations Rabinowitsch trick Racah polynomials Racah W coefficient Racetrack (game) Racks and quandles Radar chart Rademacher complexity… …   Wikipedia

  • Sun Zhiwei — (zh cpw|c=孙智伟|p=Sūn Zhìwěi|w=Sun Chihwei, b. October 16, 1965) is a Chinese mathematician, working primarily on number theory, combinatorics, and group theory. Born in Huai an, Jiangsu, Sun and his twin brother Sun Zhihong proved a theorem about… …   Wikipedia

  • Barycentric-sum problem — Combinatorial number theory deals with number theoretic problems which involve combinatorial ideas in their formulations or solutions. Paul Erdős is the main founder of this branch of number theory. Typical topics include covering system, zero… …   Wikipedia

  • Международная Математическая олимпиада — (ММО, англ. IMO, International Mathematical Olympiad)  ежегодное соревнование по математике для школьников. Это старейшая из международных научных олимпиад школьников. Первая ММО была проведена в 1959 в Румынии. С тех пор она проводится каждый… …   Википедия

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”