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<k+l-1$ . 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 $<k$ and $h_{j}$ of degree $<l$ 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<k,\hskip 5.690551ptj<l}f_{ij}*x^{i}*y^{j}+\sum_{i\geq k,\hskip 5% .690551ptj\leq n-i}f_{ij}*g_{i}(x)*y^{j}+\sum_{j\geq l,\hskip 5.690551pti\leq n% -j}f_{ij}*x^{i}*h_{j}(y)$ .

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 $<k$ in $x$ and of degree $<l$ 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<p$ and $u<k$ and $v<l$ .

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<k$ , and for $i=u$ we have $j\leq n-i=v<l$ . 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<p$ , a contradiction. The Cauchy-Davenport theorem is proved.

Title	proof of Cauchy-Davenport theorem
Canonical name	ProofOfCauchyDavenportTheorem
Date of creation	2013-03-22 14:34:49
Last modified on	2013-03-22 14:34:49
Owner	Wolfgang (5320)
Last modified by	Wolfgang (5320)
Numerical id	26
Author	Wolfgang (5320)
Entry type	Proof
Classification	msc 11B05