资源描述：
《8Dual Lattices.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、TelAvivUniversity,Fall2004Lecture8Lecturer:OdedRegevLatticesinComputerScienceDualLatticesScribe:GillatKolInthislecturewedefinethenotionofthedualofalatticeandseesomeifitsapplications.DEFINITION1Forafull-ranklattice¤wedefineitsduallattice(sometimesknownasthe
2、reciprocallattice)¤¤=fy2Rnj8x2¤;hx;yi2Zg:Ingeneral,wedefine¤¤=fy2span(¤)j8x2¤;hx;yi2Zg:Inwords,thedualof¤isthesetofallpoints(inthespanof¤)whoseinnerproductwithanyofthepointsin¤isinteger.Aswewillshowlater,¤¤isindeedalattice,asthenamesuggests.EXAMPLE1Thelat
3、ticeofintegerpointssatisfies(Zn)¤=Zn(andhencecanbecalledself-dual).Simi-larly,(2Zn)¤=1Zn,andthisgivessomejustificationtothenamereciprocallattice.2Fromtheabovedefinition,wehavethefollowinggeometricalinterpretationoftheduallattice.Foranyvectorx,thesetofallpoi
4、ntswhoseinnerproductwithxisintegerformsasetofhyperplanesperpendiculartoxandseparatedbydistance1=kxk.Hence,anyvectorxinalattice¤imposestheconstraintthatallpointsin¤¤lieinoneofthehyperplanesdefinedbyx.Seethenextfigureforanillustration.1kxk1kykyxΛΛ∗Figure1:Al
5、atticeanditsdualDEFINITION2ForabasisB=(b1;:::;bn)2Rm£n,definethedualbasisD=(d1;:::;dn)2Rm£nastheuniquebasisthatsatisfies²span(D)=span(B)²BTD=IThesecondconditioncanbeinterpretedassayingthathbi;dji=±ijwhere±ij=1ifi=jand0otherwise.ItisnothardtocheckthatDisind
6、eedunique.Infact,forthecaseofafull-ranklattice,Disgivenby(BT)¡1;ingeneral,wegetD=B(BTB)¡1(andwecouldusethisasourdefinitionofadualbasis).Inthenextclaim,weshowthatifBisabasisofalattice¤,thenthedualbasisofBisabasisof¤¤.Inparticular,thisshowsthat¤¤isindeedala
7、ttice.CLAIM1IfDisthedualbasisofBthen(L(B))¤=L(D).1PPROOF:WefirstshowthatL(D)iscontainedin(L(B))¤.Anyx2L(B)canbewrittenasaibiforsomeai2Z.Therefore,foranyjwehaveXhx;dji=aihbi;dji=ai2ZiandwegetDµ(L(B))¤.Itiseasytocheckthat(L(B))¤isclosedunderaddition,hence,L
8、(D)µ(L(B))¤.Tocompletetheproof,weshowthat(L(B))¤iscontainedinL(D).Takeanyy2(L(B))¤.PSincePy2span(B)=span(D),wecanwritey=aidiforsomeai2R.Nowforallj,Z3hy;bji=aihdi;bji=aj.Hence,y2L(D)andtheproofiscomplete.2CLAIM2Foranylattic
