三论格LATTICE_3
[TOC]
1. Lattices
Lattices定义
给定n个线性无关向量$b_1,b_2,…,b_n \in R^m$，由它们产生的格被定义为
$$
L(b_1,b_2,…,b_n)={\sum{x_i}b_i|x_i \in Z}
$$
这n个向量$b_i,i=1,2,…,n$就是格的基。
等价地，也可以把向量作为列连成矩阵，把X作为一个n维列向量。
$$
L(B)={Bx|x\in Z^n}
$$
n为格的秩，m为格的维数，n=m为满格。我们暂时只考虑满格。
事实上，B的列向量线性无关，因此其列秩为n，因此秩为n。
SPAN
格基向量张成的空间
$$
span(L(B))=span(B)={By|y\in R^n}
$$
Basic Parallelepiped基础区域
$$
P(B)={Bx|0<=x<1}
$$
Tiling Span
在每一个格点放置一个P(B)副本，得到整个tiling span
Lemma1
基础区域不应包含除了远点外的任何格点（x的左闭右开式一个细节）
设$\Lambda$为秩n的格，设$b_i\in \Lambda,i=1,2,…,n$为n个线性无关的格向量。则$b_i,i=1,2,…,n$表示为格的基，当且仅当$P(b_1,b_2,…,b_n)\cap\Lambda=0$事实上这个0应指代零向量。
幺模矩阵
设U为n阶方阵，行列式绝对值为1，则称为幺模矩阵。
Lemma2
幺模矩阵的逆也是幺模矩阵，而且求逆元对$Z^n$封闭。
Lemma3
两组基B1B2等价，当且仅当B2=B1U，其中U为某个幺模矩阵。
Lemma4
两组基等价，当且仅当一组基可以通过对列向量进行一下操作从另一组基获得：
- $b_i\leftarrow b_i+kb_j,k\in Z$
- $b_i \leftrightarrow b_j$
- $b_i\leftarrow -b_i$
Determinant行列式
$\Lambda=L(B)$为秩n的格，定义行列式$det(\Lambda)=\sqrt{det(B^TB)}$
在格中行列式与基的选取无关。行列式越小，格的密度越大。如果我们在格中取一个很大的球体K，那么K中的个点数接近于$vol(K)/det(\Lambda)$。其意义可以近似理解为是求体积除以单位体积。
2. Gram-Schmidt Orthogonalization(GSO)
施密特正交化
对于n个线性无关向量$b_1,b_2,…,b_n$序列（不是集合），我们将它们的GSO设为$\tilde{b}_1,\tilde{b}_2,…,\tilde{b}n$序列。
$$
\tilde{b}i=b_i-\sum^{i-1}{j-1}\mu{i,j}\tilde{b}j,where;\mu{i,j}=\frac{\langle b_i,\tilde{b}_j\rangle}{\langle \tilde{b}_j,\tilde{b}_j\rangle}
$$
这部分是高等代数的知识，有一些简单的特性：
- 任意$i\neq j$，有$\langle \tilde{b}_i,\tilde{b}_j\rangle=0$
- 两个序列张成的空间等价
- GSO序列不需要是格的基，一般甚至不包括在格中
- 顺序很重要，因此是序列不是集合。
3. Successive minima逐次最小长度
范数与长度
长度指的是欧几里得范数，或者$l_2$范数，定义为$||x||_2=\sqrt{\sum x_i^2}$。关于范数，可能会用到$l_1$范数$||x||_1={\sum |x_i|}$或者$l_\infty$范数$||x||_\infty=max|x_i|$
格有一个基本参数$\lambda_1$是格中最短非零向量的长度。
第i个逐次最小长度
设$\Lambda$为秩n的格，对于$i=1,2,…,n$，可以定义第i个逐次最小长度为
$$
\lambda_i(\Lambda)=inf{r|dim(span(\Lambda\cap\bar{B}(0,r)))\geq i}
$$
其中$\bar{B}(0,r)={x\in rm|;||x||\leq r}$是半径r原点O左右的close ball。
theorem 5
格的最短非零向量长度必不小于GSO之后的最短向量。
$$
|\langle Bx,\tilde{b}j\rangle|=|\langle\sum{i=1}^jx_ib_i,\tilde{b}_j\rangle|=|x_j|\langle\tilde{b}_j,\tilde{b}_j\rangle=|x_j||\tilde{b}_j|^2
$$
其中$\text{for all }i<j,\langle b_i,\tilde{b}_j\rangle=0$且$\langle b_j,\tilde{b}_j\rangle=\langle\tilde{b}_j,\tilde{b}_j\rangle $
而且由绝对值不等式可知：$|\langle Bx,\tilde{b}_j\rangle|\leq||Bx||\cdot||\tilde{b}_j||$
这样就导出了结论
$$
|Bx|\geq|x_j||\tilde{b}_j|\geq|\tilde{b}_j|\geq\min|\tilde{b}_i|
$$
corollary 6
对于任一格，存在$\epsilon > 0$使得任意两个格点距离大于它$||x-y||>\epsilon$
证明：取theorem 5中提到的GSO后最短向量。
claim 7
格的逐次最小长度必定能被取得。
Upper bounds on the successive minima
Minkowski 逐次最小长度的上界 (Minkowski’s Upper bounds on the successive minima)。
只考虑满格。
Theorem 8 Blichfeld
对于任意实数系上的满秩格$\Lambda$和可测度的实数上集合S（$vol(S)>det(\Lambda)$），S上存在两个不相等的点，向量差属于格$\Lambda$
看不懂思密达
Theorem 9 Minkowski’s convex body theorem
满秩格$\Lambda$的秩为n，对于任何中心对称凸集S，如果$vol(S)>2^ndet(\Lambda)$则S包含一个非零格点。
Claim 10
$$
vol(B(0,r))\geq (\frac{2r}{\sqrt{n}})^n
$$
证明：这个n维球里面包含了长度为$\frac{2r}{\sqrt{n}}$的超立方体
Corollary 11 Minkowski’s First Theorem
$$
\lambda_1(\Lambda)\leq\sqrt{n}(det\Lambda)^{\frac{1}{n}}
$$
Claim 12
$$
\left(\frac{2\lambda_1(\Lambda)}{\sqrt{n}}\right)^n\leq\mathrm{vol}(\mathrm{B}(0,\lambda_1(\Lambda)))\leq2^n\det\Lambda
$$
4. Computational Problems
闵可夫斯基第一定理说明了秩n的格$\Lambda $至少包含一个非零向量，其长度小于等于右式。但是这不具有建设性，因为没有一个找到这个向量的算法。事实上，没有已知的有效算法可以保证找到这样的短向量。
这就是格的计算难题SVP：最短向量问题。准确来说是给出一个格，需要找到最短的非零格点。
更准确的说，SVP有三个变体，决定了我们是否需要找到这个向量，或者只需要长度，或者确定它小于某个数字。
- Search SVP：给定格基$B \in Z^{m\times n}$，求$v\in L(B),st.||v||=\lambda_1(L(b))$
- Optimization SVP：给定格基$B \in Z^{m\times n}$，找到$\lambda_1(L(b))$
- Decisional SVP：给定格基$B \in Z^{m\times n}$和有理数r，判断$\lambda_1(L(b))\leq r$是否成立
在这里我们限制格基由整数向量组成，目的是使输入是有限多位的。事实上，我们还可以允许格基是有理向量，这和整数向量是等价的，因为可以通过缩放使所有有理数坐标都是整数。
三个问题变体的难度是等价的。
另一个基本格难题是最近向量问题CVP，目标是找到最接近给定空间点的格点。对于任意的近似因子$\gamma \geq 1$，定义有三个等价的变体：
