# proof of Cauchy-Davenport theorem

There is a proof, essentially from here http://www.math.tau.ac.il/ nogaa/PDFS/annr3.pdf(Imre Ruzsa et al.):

Let $|A|=k$ and $|B|=l$ and $|A+B|=n$. If $n\geq k+l-1$, the assertion is true, now assume $n. Form the polynomial $f(x,y)=\prod_{c\in A+B}(x+y-c)=\sum_{i+j\leq n}f_{ij}*x^{i}*y^{j}$. The sum is over $i$,$j$ with $i+j\leq n$, because there are $n$ factors in the product.

Since $Z_{p}$ is a field, there are polynomials $g_{i}$ of degree $ and $h_{j}$ of degree $ such that $g_{i}(x)=x^{i}$ for all $x\in A$ and $h_{j}(y)=y^{j}$ for all $y\in B$. Define a polynomial $p$ by $p(x,y)=\sum_{i.

This polynomial coincides with $f(x,y)$ for all $x$ in $A$ and $y$ in $B$, for these $x$,$y$ we have, however, $f(x,y)=0$. The polynomial $p(x,y)$ is of degree $ in $x$ and of degree $ in $y$. Let $x\in A$, then $p(x,y)=\sum p_{j}(x)*y^{j}$ is zero for all $y\in B$, and all coefficients must be zero. Finally, $p_{j}(x)$ is zero for all $x\in A$, and all coefficients $p_{ij}$ of $p(x,y)=\sum p_{ij}*x^{i}*y^{j}$ must be zero as elements of $Z_{p}$.

Should the assertion of the theorem be false, then there are numbers $u$,$v$ with $u+v=n and $u and $v.

But the monomial $x^{u}*y^{v}$ does not appear in the second and third sum, because for $j=v$ we have $i\leq n-j=u, and for $i=u$ we have $j\leq n-i=v. Then $p_{uv}=0$ is $modulo\hskip 5.690551ptp$ equal to $f_{uv}$, this is equal to the binomial coefficient $n\choose v$, which is not divisible by $p$ for $n, a contradiction. The Cauchy-Davenport theorem is proved.

Title proof of Cauchy-Davenport theorem ProofOfCauchyDavenportTheorem 2013-03-22 14:34:49 2013-03-22 14:34:49 Wolfgang (5320) Wolfgang (5320) 26 Wolfgang (5320) Proof msc 11B05