Shiksha Nation
Skip to content

Restricted sumset

  • 2 min read
  • 3 chapters

Related on Lably

Through Subset, Polynomial and Prime number

S={a1+⋯+an:a1∈A1,…,an∈AnandP(a1,…,an)≠0},

where A1,…,An are finite nonempty subsets of a field F and P(x1,…,xn) is a polynomial over F.

If P is a constant non-zero function, for example P(x1,…,xn)=1 for any x1,…,xn, then S is the usual sumset A1+⋯+An which is denoted by nA if A1=⋯=An=A.

When

P(x1,…,xn)=∏1≤i<j≤n(xj−xi),

S is written as A1∔⋯∔An which is denoted by n∧A if A1=⋯=An=A.

Note that |S| > 0 if and only if there exist a1∈A1,…,an∈An with P(a1,…,an)≠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/pZ we have the inequality

|A+B|≥min{p,|A|+|B|−1}

where A+B:={a+b(modp)∣a∈A,b∈B}, i.e. we're 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

|A+B|≥min{p(G),|A|+|B|−1}

where p(G) is the size of the smallest nontrivial subgroup of G (we set it to 1 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 Z/nZ, 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 Z/pZ, every element of Z/pZ 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.

Sign up free to read the rest

2 more chapters are free with a Lably account.

Already have an account?

More in Topics in mathematics