请输入您要查询的字词:

 

单词 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 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 byp(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.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 3:13:09