In additive number theory and combinatorics, a restricted sumset has the form
S = { a 1 + ⋯ + a n : a 1 ∈ A 1 , … , a n ∈ A n a n d P ( a 1 , … , a n ) ≠ 0 } , {\displaystyle 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 , … , A n {\displaystyle A_{1},\ldots ,A_{n}} are finite nonempty subsets of a field F and P ( x 1 , … , x n ) {\displaystyle P(x_{1},\ldots ,x_{n})} is a polynomial over F. If P {\displaystyle P} is a constant non-zero function, for example P ( x 1 , … , x n ) = 1 {\displaystyle P(x_{1},\ldots ,x_{n})=1} for any x 1 , … , x n {\displaystyle x_{1},\ldots ,x_{n}} , then S {\displaystyle S} is the usual sumset A 1 + ⋯ + A n {\displaystyle A_{1}+\cdots +A_{n}} which is denoted by n A {\displaystyle nA} if A 1 = ⋯ = A n = A . {\displaystyle A_{1}=\cdots =A_{n}=A.}
When
P ( x 1 , … , x n ) = ∏ 1 ≤ i < j ≤ n ( x j − x i ) , {\displaystyle P(x_{1},\ldots ,x_{n})=\prod _{1\leq i<j\leq n}(x_{j}-x_{i}),}
S is written as A 1 ∔ ⋯ ∔ A n {\displaystyle A_{1}\dotplus \cdots \dotplus A_{n}} which is denoted by n ∧ A {\displaystyle n^{\wedge }A} if A 1 = ⋯ = A n = A . {\displaystyle A_{1}=\cdots =A_{n}=A.}
Note that |S| > 0 if and only if there exist a 1 ∈ A 1 , … , a n ∈ A n {\displaystyle a_{1}\in A_{1},\ldots ,a_{n}\in A_{n}} with P ( a 1 , … , a n ) ≠ 0. {\displaystyle P(a_{1},\ldots ,a_{n})\not =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 / p Z {\displaystyle \mathbb {Z} /p\mathbb {Z} } we have the inequality
| A + B | ≥ min { p , | A | + | B | − 1 } {\displaystyle |A+B|\geq \min\{p,\,|A|+|B|-1\}}
… excerpt ends here. Continue reading the full article.
