proof of Cauchy-Davenport theorem

There is a proof, essentially from here nogaa/PDFS/annr3.pdf(Imre Ruzsa et al.):

Let |A|=k and |B|=l and |A+B|=n. If nk+l-1, the assertion is true, now assume n<k+l-1. Form the polynomial f(x,y)=cA+B(x+y-c)=i+jnfij*xi*yj. The sum is over i,j with i+jn, because there are n factors in the productPlanetmathPlanetmath.

Since Zp is a field, there are polynomials gi of degree <k and hj of degree <l such that gi(x)=xi for all xA and hj(y)=yj for all yB. Define a polynomial p by p(x,y)=i<k,j<lfij*xi*yj+ik,jn-ifij*gi(x)*yj+jl,in-jfij*xi*hj(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 xA, then p(x,y)=pj(x)*yj is zero for all yB, and all coefficients must be zero. Finally, pj(x) is zero for all xA, and all coefficients pij of p(x,y)=pij*xi*yj must be zero as elements of Zp.

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 xu*yv does not appear in the second and third sum, because for j=v we have in-j=u<k, and for i=u we have jn-i=v<l. Then puv=0 is modulop equal to fuv, this is equal to the binomial coefficientDlmfDlmfMathworldPlanetmath (nv), which is not divisible by p for n<p, a contradictionMathworldPlanetmathPlanetmath. The Cauchy-Davenport theoremMathworldPlanetmath 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