{
  "id": "restricted-sumset-098771-8efd6c4a84f83edd",
  "slug": "restricted-sumset",
  "title": "restricted sumset",
  "qid": "Q859107",
  "lead": "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.",
  "body": "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==",
  "categories": [
    "23118434",
    "23603337",
    "29176143",
    "29176655",
    "29264783",
    "29264810",
    "7692542"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1367303758",
  "content_hash": "8efd6c4a84f83edd1ffd70457062dd926989e31f40a5f0b23664baa36dd7276e",
  "created_at": 1792308956.6106539,
  "updated_at": 1785648219.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "restricted-sumset-098771-8efd6c4a84f83edd",
    "type": "webpage",
    "title": "restricted sumset",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/restricted-sumset",
    "issued": {
      "date-parts": [
        [
          2026,
          10,
          18
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          21
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:restricted-sumset-098771-8efd6c4a84f83edd",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1367303758",
    "note": "Immutable snapshot restricted-sumset-098771-8efd6c4a84f83edd, content root 8efd6c4a84f83edd…"
  }
}