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.

单词	ProofOfCauchyDavenportTheorem
释义	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.
随便看	NthRootFormulas nth root formulas NTopologicalSpaces N-Topological Spaces Ntorus n-torus NuclearCalgebra nuclear C*-algebra NuclearSpace nuclear space Nucleus Nucleus nucleus Nucleus1 Nullcline nullcline NullGraph null graph NullhomotopicMap nullhomotopic map Nullity nullity NullSemigroup null semigroup NullTree