Minkowski 定理
题意
给定一个 $n$ 维格 $L(B)=\{\sum_{i=1}^n c_i\mathbf b_i\mid c_i\in\mathbb Z\}$，其中 $B=\begin{bmatrix}\mathbf b_1 & \cdots & \mathbf b_n\end{bmatrix}\in\mathbb R^{n\times n}$ 是满秩矩阵。令 $\lambda_1(L)=\min(\Vert\mathbf v\Vert_2\mid \mathbf v\in L)$，求证：
上面的 bound 在渐进意义下是紧的。即存在常数 $c>0$，对于任意充分大的 $n$，存在 $n$ 维、满秩的格 $L(B)$ 使得
证明
1
引理 1：若可测集 $V\subseteq\mathbb R^n$ 的体积 $\text{Vol}(V)$ 大于 $|\det(B)|$，则其中存在两个点 $\mathbf x,\mathbf y$ 使得 $\mathbf x-\mathbf y\in L(B)$。
证明：为了避免触及繁琐的数学细节，这个证明是直觉式的。令 $L(B)$ 的基本域为 $\mathcal F=\{\mathbf x=\sum_{i=1}^n c_i\mathbf b_i\mid c_i\in\mathbb R\cap [0,1)\}$，则任何向量 $\mathbf x$ 可以写为 $\mathbf x=\mathbf u+\mathbf v (\mathbf u\in L(B), \mathbf v\in\mathcal F)$ 的形式。注意 $\mathcal F$ 的体积即 $|\det(B)|$，小于 $V$ 的体积，因此存在两个 $V$ 中向量在上述分解中对应的 $\mathbf v$ 相等，将它们作为 $\mathbf x,\mathbf y$ 即可。
引理 2（Minkowski）：若关于原点中心对称的凸集 $V\subseteq\mathbb R^n$ 的体积 $\text{Vol}(V)$ 大于 $2^n|\det(B)|$，则其中存在格点 $\mathbf x\in L(B)$。
证明：根据条件，$V/2$ 的体积大于 $|\det(B)|$，故其中存在 $\mathbf x,\mathbf y$ 使得 $\mathbf x-\mathbf y\in L(B)$，由于 $V$ 是对称凸集，知 $-\mathbf y\in V/2$，从而 $\frac{1}{2}(\mathbf x+(-\mathbf y))\in V/2$，从而 $\mathbf x-\mathbf y\in V$，这就是 $V$ 中的一个格点。
回到原题。令 $l=\lambda_1(L)/\sqrt n-\varepsilon$，考虑 $V=[-l,l]^n$，这是一个对称凸集，且内部不存在格点（根据 $\lambda_1(L)$ 的定义）。由引理 2，知道 $\text{Vol}(V)\leq 2^n|\det(B)|$，令 $\varepsilon\to 0$，得
事实上，将 $V$ 改成球可以得到一个常数更优的界。
2
令 $p$ 是大于 $n^2$ 的素数，$k=\lceil n/2\rceil$。考虑：
其中 $A\sim GL_{k,n}(\mathbb F^p)$ 来自于 $\mathbb F^p$ 上秩为 $k$ 的 $k\times n$ 矩阵的均匀采样。
可以证明 $L_A$ 是格且 $|\det(L_A)|=p^k$。
引理 3：若 $\mathbf x\not\equiv\mathbf 0\pmod p$，则 $\Pr_A[A\mathbf x\equiv 0\pmod p]\leq \frac{1}{p^k}$。
证明：令 $U\in GL_n(\mathbf F^p)$ 满足 $U\mathbf x=\mathbf e_1$，则
令 $R=\frac{p^{k/n}\sqrt n}{2\sqrt{8\pi e}}$，根据简单算术可知 $\sqrt n\leq R<p$ 在 $n$ 足够大时成立。令 $B(R)$ 是以原点为心，$R$ 为半径的球，$N(R)$ 是其中整点数量，则
根据 Union Bound，$B(R)$ 内除 $\mathbf 0$ 外不存在格 $L_A$ 中点的概率为
故存在符合这个要求的 $L_A$，在该格中，