↑ arvau

Wikipedia / Restricted sumset

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

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

is the usual sumset

When

S

Note that |S

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 we have the inequality

, i.e. using modular arithmetic. It can be generalised to arbitrary (not necessarily abelian) groups using a Dyson transform, then

if there is no such subgroup).

This can be used to deduce the Erdős–Ginzburg–Ziv theorem: given any sequence of 2n, 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 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 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

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 tool in the study of lower bounds for cardinalities of various restricted sumsets is the following principle: the combinatorial Nullstellensatz.. Suppose that the coefficient of the monomial is the total degree.

This result 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.

See also

References