restricted sumset

Uses your system voice; voice and rate in settings.

Q859107Snapshot

≈ 4 min read

Names in other languages

  • caSuma restringida de conjunts
  • Françaissomme restreinte d'ensembles
  • myကန့်သတ် ပေါင်းလဒ်အစု
  • Englishrestricted sumset
  • 日本語制限和集合

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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. If P is a constant non-zero function, for example P(x_1,\ldots,x_n)=1 for any x_1,\ldots,x_n , then 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 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.

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. If P is a constant non-zero function, for example P(x_1,\ldots,x_n)=1 for any x_1,\ldots,x_n , then 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 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. where A+B := \{a+b \pmod p \mid a \in A, b \in B\} , i.e. using modular arithmetic. It can be generalised to arbitrary (not necessarily abelian) groups using a Dyson transform. If A, B are subsets of a group G , then |AB| \ge \min\{p(G),\, |A|+|B|-1\} where p(G) is the size of the smallest nontrivial subgroup of G (we set it to \infty if there is no such subgroup). This can be used to deduce the Erdős–Ginzburg–Ziv theorem: given any sequence of 2n−1 elements in the cyclic group \mathbb{Z}/n\mathbb{Z} , 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 \mathbb{Z}/p\mathbb{Z} , every element of \mathbb{Z}/p\mathbb{Z} 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. 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 tool in the study of lower bounds for cardinalities of various restricted sumsets is the following principle: the combinatorial Nullstellensatz. 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 |A_i|>k_i 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) \neq 0 . 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.

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1367303758 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot restricted-sumset-098771-8efd6c4a84f83edd · hash 8efd6c4a84f83edd1ffd70457062dd926989e31f40a5f0b23664baa36dd7276e · captured 1785648219.0 · version history

Cite this page as: encyclopegia.org, “restricted sumset”, snapshot restricted-sumset-098771-8efd6c4a84f83edd. https://encyclopegia.org/a/restricted-sumset

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.