逐次极小值与 Minkowski 定理#

前置笔记：基本区域、格行列式与正交化。

本篇讨论如何描述格中短向量的长度，以及如何利用行列式保证短向量存在。考虑满秩格 $\Lambda=\mathcal L(B)\subseteq\mathbb R^n$，使用欧氏范数 $\|\cdot\|_2$。

#逐次极小值：找到独立方向需要多大的半径

记以原点为中心、半径为 $r$ 的闭球为

$$\overline{\mathbb B}(0,r)=\{x\in\mathbb R^n:\|x\|_2\le r\}.$$

第 $i$ 个逐次极小值定义为

$$\lambda_i(\Lambda) = \min\left\{ r>0: \dim\operatorname{span}\bigl(\Lambda\cap\overline{\mathbb B}(0,r)\bigr)\ge i \right\}.$$

它表示：找到 $i$ 个线性无关格向量所需的最小半径。 格在有界区域内只有有限个点，因此这里的最小值可以取到。

特别地，

$$\lambda_1(\Lambda) = \min_{v\in\Lambda\setminus\{0\}}\|v\|_2, \qquad 0<\lambda_1\le\lambda_2\le\cdots\le\lambda_n.$$

这些量由格本身决定，与选择哪组基无关 [1, p. 9]。

例如，

$$\Lambda=\mathbb Z\times3\mathbb Z =\mathcal L\left( \begin{bmatrix} 1&0\\ 0&3 \end{bmatrix} \right).$$

此时

$$\lambda_1=1,\qquad \lambda_2=3.$$

虽然 $(2,0)$ 的长度为 $2$，但它与 $(1,0)$ 共线。要获得第二个独立方向，必须找到纵坐标非零的格向量，其长度至少为 $3$。

因此，$\lambda_i$ 不是把所有非零格向量按长度排序后得到的第 $i$ 个长度。

#正交化给出的最短向量界

设 $b_1^*,\ldots,b_n^*$ 是基 $B$ 的 Gram–Schmidt 正交化，则

$$\boxed{ \min_i\|b_i^*\|_2 \le \lambda_1(\Lambda) \le \min_i\|b_i\|_2 }.$$

右侧直接来自：每个基向量都是非零格向量。

左侧的关键是整数系数。对任意非零格向量

$$v=\sum_i z_i b_i,\qquad z_i\in\mathbb Z,$$

取最大的满足 $z_k\ne0$ 的下标 $k$。$v$ 在 $b_k^*$ 方向上的正交投影为 $z_kb_k^*$，故

$$\|v\|_2\ge |z_k|\|b_k^*\|_2 \ge\|b_k^*\|_2.$$

两端的界随基的选择变化，中间的 $\lambda_1(\Lambda)$ 保持不变 [1, pp. 2–3]。

#Minkowski 凸体定理：体积足够大就包含非零格点

设 $K\subseteq\mathbb R^n$ 是可测凸集，且关于原点中心对称，即 $K=-K$。如果

$$\operatorname{vol}(K)>2^n\det(\Lambda),$$

那么

$$K\cap(\Lambda\setminus\{0\})\ne\varnothing.$$

证明思路只需记住两步：

• 由 Blichfeldt 定理，$\operatorname{vol}(K/2)>\det(\Lambda)$ 保证存在不同的 $x,y\in K/2$，使 $x-y\in\Lambda$。
• 对称性与凸性保证 $x-y=\frac{2x+(-2y)}2\in K$。

于是 $x-y$ 就是 $K$ 中的非零格点 [2, pp. 6–7]。

#Minkowski 第一定理：控制最短非零向量

在欧氏范数下，有

$$\boxed{ \lambda_1(\Lambda) \le \sqrt n\,\det(\Lambda)^{1/n} }.$$

这是讲义采用的简化上界。它将行列式描述的体积尺度转化为短向量的长度尺度。

推导可以使用立方体：取 $a>\det(\Lambda)^{1/n}$，则 $[-a,a]^n$ 的体积超过 $2^n\det(\Lambda)$，其中存在非零格向量，长度至多为 $\sqrt n\,a$。令 $a$ 趋近于 $\det(\Lambda)^{1/n}$，即可得到上界 [2, pp. 7–8]。

注意：这个结论保证短向量存在，证明本身没有给出寻找它的算法。

#Minkowski 第二定理：控制逐次极小值的乘积

沿用 Regev 讲义中的简化上界形式：

$$\boxed{ \left(\prod_{i=1}^{n}\lambda_i(\Lambda)\right)^{1/n} \le \sqrt n\,\det(\Lambda)^{1/n} }.$$

等价地，

$$\prod_{i=1}^{n}\lambda_i(\Lambda) \le n^{n/2}\det(\Lambda).$$

它控制所有逐次极小值的几何平均值。由于

$$\lambda_1\le \left(\prod_i\lambda_i\right)^{1/n},$$

这个结论也蕴含第一定理的上界 [2, pp. 8–9]。

不能据此断言每个 $\lambda_i$ 都小于右侧。前面的 $\mathbb Z\times3\mathbb Z$ 就满足

$$\det(\Lambda)=3,\qquad \lambda_2=3>\sqrt2\sqrt3=\sqrt6.$$

本篇只记录这一上界形式，暂不展开第二定理的完整双侧形式与证明。

#阅读位置

• Minkowski 定理在原点对称凸体的体积超过相应阈值时，保证其中存在非零格点 [2, pp. 5–9]。
• 逐次极小值描述线性无关短向量的长度尺度，而格基的正交分量可以给出最短向量长度的下界 [1, pp. 2–3, 9]。

接下来阅读基本计算格问题：SVP、CVP 与 SIVP，讨论如何寻找这些向量，以及如何定义近似解。

#参考文献