Samiksha Jaiswal (Editor)

Restricted sumset

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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

Contents

S = { a 1 + ⋯ + a n :   a 1 ∈ A 1 , … , a n ∈ A n   a n d   P ( a 1 , … , a n ) ≠ 0 } ,

where A 1 , … , A n are finite nonempty subsets of a field F and P ( x 1 , … , x n ) is a polynomial over F.

When P ( x 1 , … , x n ) = 1 , S is the usual sumset A 1 + ⋯ + A n which is denoted by nA if A 1 = ⋯ = A n = A ; when

P ( x 1 , … , x n ) = ∏ 1 ≤ i < j ≤ n ( x j − x i ) ,

S is written as A 1 ∔ ⋯ ∔ A n which is denoted by n ∧ A if A 1 = ⋯ = A n = A . Note that |S| > 0 if and only if there exist a 1 ∈ A 1 , … , a n ∈ A n with P ( a 1 , … , a n ) ≠ 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 Z/pZ we have the inequality

| A + B | ≥ min { p ,   | A | + | B | − 1 } .

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.)

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.

Kneser's theorem generalises this to finite abelian groups.

Erdős–Heilbronn conjecture

The 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. This was first confirmed by J. A. Dias da Silva and Y. O. Hamidoune in 1994 who showed that

| n ∧ A | ≥ 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, and G. Karolyi in 2004.

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. Let f ( x 1 , … , x n ) be a polynomial over a field F. Suppose that the coefficient of the monomial x 1 k 1 ⋯ x n k n in f ( x 1 , … , x n ) is nonzero and k 1 + ⋯ + k n is the total degree of f ( x 1 , … , x n ) . If A 1 , … , A n are finite subsets of F with | A i | > k i for i = 1 , … , n , then there are a 1 ∈ A 1 , … , a n ∈ A n such that f ( a 1 , … , a n ) ≠ 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, and developed by Alon, Nathanson and Ruzsa in 1995-1996, and reformulated by Alon in 1999.

References

Restricted sumset Wikipedia
(Text) CC BY-SA