对偶格相关

定义: 对一个满秩格L, 定义它的对偶格为
L* = {在R^n空间的向量y | 对于任意的格向量x, 内积(x,y)为整数}

不一定要求格满秩, 一般地, 定义
L* = {在格L张成的向量空间里的y|对于任意的格向量x, 内积(x,y)为整数}

例子:
(Z^n)* = Z^n
(kZ^n)* = (1/k)Z^n

下面说明对偶格确实构成格

• 加群 √
• 离散: 只需说明对偶格里面最短向量的长度>某个正数 或者 对偶格里任二不同向量之差的长度>某正数
  事实上取x∈格-{0}, y1,y2∈对偶格(y1!=y2),有length(y1-y2)>=1/length(x)(常数)
  由转移定理也可以证明离散性, λ1(格)λn(对偶格)>=1, 知道有λ1(对偶格)>=1/λn(格), 对于对于任意一组线性无关向量x1,...,xn, 对偶格里的任意非零向量x, 存在i, 使得xi与x内积不为0, 由内积取绝对值的不等式1<=|(x,xi)|<=len(x)len(xi), 故有len(x)>=1/len(xi)

remark: 先说明一个事实, 如果一个对偶格的向量和格中的向量, 内积都是0的话, 那么这个向量只能是0向量,若这个对偶格向量y不为0, 那么y/|y|^2应该在原格里面, 因为(y/|y|^2,y)=1, 但这时候这个整数值不为0, 矛盾, 也就是说对于对偶格里任一非零向量y, 存在格中的向量, 使得(x,y)不为0.

如果格2是格1的稀疏化, 格1张成的向量空间与格2张成的向量空间相同, 那么就有格2的对偶格包含于格1的对偶格.

定义: 对于基B=(b1,b2,...,bn)∈R[m][n], 这个基的对偶基dual basis D=(d1,d2,...,dn)满足以下两条
i. 两组基张成相同的向量空间
ii. trans(B)D=I iff (bi, dj)=δij

满足这两条的对偶基是唯一的, 由B可以得到D的表达式.
因为都是基, 所以存在一个可逆方阵M使得 BM=D, trans(B) BM=trans(B) D=I, 把M解出来, 得到D的表达式为B(trans(B)B)^(-1)

Claim 基张成的格的对偶格就是该基的对偶基张成的格

• 先证明对偶基张成的格包含于对偶格
  只需证明对偶基包含于对偶格, 也就是说要去证明对偶基di与原格里的每一个向量内积为整数, 设x是原格里的任一向量, 于是有x=a1b1+...+anbn, ai为整数, 于是确实有(x,di)为整数.
• 再证明对偶格包含于对偶基张成的格
  也就去证明, 对偶格里的向量可以用对偶基整线性表出, 设y是对偶格里的任一向量, 则y按照对偶格的定义, 在基张成的向量空间span(B)里, 又对偶基和基张成了相同的向量空间, 所以y在spanD里, 所以y可以由D实线性表出, y=r1d1+...+rndn, 那么(y,di)=ri(di,bi)为整数, 所以实系数应为整系数.

Claim 对偶格的对偶=原格
证明:设出格基, 得到对偶基, 再算对偶格的对偶的格基, 得到原格基.

Claim det(对偶格)=1/det(格)
证明: 用格基算det(格)可得.

Claim (比转移定理强的一个结果)对于秩为n的格, λ1(格)λ1(对偶格)<=n.
证明: 由Minkowski's bound, 由λ1(格)<=sqrt(n)det(格)^(1/n), λ1(对偶格)<=sqrt(n)det(对偶格)^(1/n).

Claim 对于秩为n的格, 有λ1(格)λn(对偶格)>=1.
证明: 设v是格里的最短向量. 取对偶格里的n个线性无关向量x1,...,xn, 存在i使得(xi,v)!=0. 而λn(对偶格)>=len(xi).

πi:R^n-><b1,b2,...,bi-1>的正交补空间
对于不满秩的情形, 应该以spanB为全空间
πi(bi)得到b1,...,bn的正交化

Claim B,D dual bases, then B'=(πi(bi), ..., πi(bn))与D'=(di,...,dn) are also dual bases.
证明: spanB'=span(πi(bi), ..., πi(bn))=span(b1,...,bi-1)的正交补空间
因为di,...,dn orthogonal to b1,...,bi-1 且线性无关
故spanD'=<b1,...,bi-1>的正交补空间
所以这两个基张成了相同的空间
任一j, k>=i, (dj, πi(bk))=(dj, bk-u(k,1)gs(b1)-...-u(k,i-1)gs(bi-1))=(dj,bk)=δjk
Remark: from i to n, 对于dual basis的后面部分, 也可以找出它相应的dual basis

Claim b1,..., bn, its dual basis d1, ..., dn, GS in order dn, dn-1,..,d1, get gs(dn)=dn,
gs(d_n-1)=d_n-1-u(n-1,n)gs(bn),
gs(d_n-2)=d_n-2-u(n-2,n)gs(n)-u(n-2,n-1)gs(d_n-1),
...,
gs(d1)=d1-u(1,n)gs(dn)-...-u(1,2)gs(d2)
then gs(di)=gs(bi)/len(bi)^2
Pf: induction on the number of basis
n=1,
gs(d1) ∈ span(d2,...,dn)的正交补空间=span(b1)
Since span(di,...,dn) = span(b1,...,b_i-1)的正交补空间,
也即是说
di,...,dn与b1,b2,...,bi-1是正交的,
span(di,...,dn)里的元素和span(b1,...,b_i-1)里的元素是正交的,
(d, from i to n, b from 1 to i-1)
(gs(d1), b1)=(d1-u(1,n)gs(dn)-...-u(1,2)gs(d2),b1)
由span(d2,...,dn)里的元素和span(b1)都是正交的
故上式变为(d1, b1)=1. 设gs(d1)=tb1, 则t=1/len(b1)^2, 所以gs(d1)=gs(b1)/len(gs(b1))^2, the formula holds.
Assume the claim holds for lattices of rank n-1 and let us prove for lattices of rank n.