Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Restricted sumset
Summary
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.
If is a constant non-zero function, for example for any , then is the usual sumset which is denoted by if
When
S is written as which is denoted by if
Note that |S| > 0 if and only if there exist with
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
where , i.e. we're using modular arithmetic. It can be generalised to arbitrary (not necessarily abelian) groups using a Dyson transform. If are subsets of a group , then
where is the size of the smallest nontrivial subgroup of (we set it to if there is no such subgroup).
We may use this to deduce the Erdős–Ginzburg–Ziv theorem: given any sequence of 2n−1 elements in the cyclic group , 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−1 or more nonzero elements, not necessarily distinct, of , every element of 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.
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. 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.
A powerful tool in the study of lower bounds for cardinalities of various restricted sumsets is the following fundamental principle: the combinatorial Nullstellensatz.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.