# 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\ge k+l-1$, the assertion is true, now assume $$.
Form the polynomial $f(x,y)={\prod}_{c\in A+B}(x+y-c)={\sum}_{i+j\le n}{f}_{ij}*{x}^{i}*{y}^{j}$.
The sum is over $i$,$j$ with $i+j\le 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 $$.

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 $$ and $$ and $$.

But the monomial ${x}^{u}*{y}^{v}$ does not appear in the second and third sum, because for $j=v$ we have $$, and for $i=u$ we have $$.
Then ${p}_{uv}=0$ is $modulop$ equal to ${f}_{uv}$, this is equal to the binomial coefficient^{} $\left(\genfrac{}{}{0pt}{}{n}{v}\right)$, which is not divisible by $p$ for $$, 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 |