Explore relationships

Restricted sumset

In additive number theory and combinatorics, a restricted sumset has the form S={a1+⋯+an:a1∈A1,…,an∈AnandP(a1,…,an)≠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}) ot =0\},}where A1,…,An{\displaystyle A_{1},\ldots ,A_{n}} are finite nonemptysubsets of a fieldF and P(x1,…,xn){\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(x1,…,xn)=1{\displaystyle P(x_{1},\ldots ,x_{n})=1} for any x1,…,xn{\displaystyle x_{1},\ldots ,x_{n}}, then S{\displaystyle S} is the usual sumsetA1+⋯+An{\displaystyle A_{1}+\cdots +A_{n}} which is denoted by nA{\displaystyle nA} if A1=⋯=An=A.{\displaystyle A_{1}=\cdots =A_{n}=A.}When P(x1,…,xn)=∏1≤i<j≤n(xj−xi),{\displaystyle P(x_{1},\ldots ,x_{n})=\prod _{1\leq i<j\leq n}(x_{j}-x_{i}),}S is written as A1∔⋯∔An{\displaystyle A_{1}\dotplus \cdots \dotplus A_{n}} which is denoted by n∧A{\displaystyle n^{\wedge }A} if A1=⋯=An=A.{\displaystyle A_{1}=\cdots =A_{n}=A.}Note that |S| > 0 if and only if there exist a1∈A1,…,an∈An{\displaystyle a_{1}\in A_{1},\ldots ,a_{n}\in A_{n}} with P(a1,…,an)≠0.{\displaystyle P(a_{1},\ldots ,a_{n}) ot =0.}Cauchy–Davenport theoremThe Cauchy–Davenport theorem, named after Augustin Louis Cauchy and Harold Davenport, asserts that for any primep and nonempty subsets A and B of the prime-ordercyclic groupZ/pZ{\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\}}where A+B:={a+b(modp)∣a∈A,b∈B}{\displaystyle A+B:=\{a+b{\pmod {p}}\mid a\in A,b\in B\}}, i.e. using modular arithmetic.

Use + to expand a branch. Click a topic name to open its summary.