# 03 逐次极小值与 Minkowski 定理

适用范围：计算格与格密码中的欧氏几何基础。整理日期：2026-09-27。
前置笔记：[02 基本区域、格行列式与正交化](/knowledge/fundamental-region-and-orthogonalization/)。

本篇讨论如何描述格中短向量的长度，以及如何利用行列式保证短向量存在。考虑满秩格 $\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.
$$

这些量由格本身决定，与选择哪组基无关。[2，PDF 第 9 页，Definition 11]

例如，

$$
\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)$ 保持不变。[2，PDF 第 2—3 页，Theorem 2]

## 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$ 中的非零格点。[1，第 6—7 页，Theorem 8—9]

## 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}$，即可得到上界。[1，第 7—8 页，Corollary 2]

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

## 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},
$$

这个结论也蕴含第一定理的上界。[1，第 8—9 页，Theorem 3]

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

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

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

## 来源与阅读位置

1. Oded Regev，*Lattices in Computer Science*，Lecture 1: *Introduction*，Fall 2004。以 §3—§3.1、第 5—9 页为主；第 6—7 页 Theorem 8—9、第 7—8 页 Corollary 2、第 8—9 页 Theorem 3。[原文](https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/introduction.pdf)
2. Daniele Micciancio，*Minkowski's theorem*，PDF 页首标注 Fall 2017，由 2019 年课程页链接。补充最短向量下界与逐次极小值：PDF 第 2—3 页 Theorem 2、第 9 页 Definition 11。[原文](https://cseweb.ucsd.edu/classes/fa19/cse206A-a/lec2.pdf)

来源于 2026-09-26 核对，正文按已确认的草稿整理。

下一篇计划：《04 基本计算格问题：SVP、CVP 与 SIVP》，讨论如何寻找这些向量，以及如何定义近似解。

## 引用此笔记

- [00 概览与阅读路线](/knowledge/lattices-overview/)
- [04 基本计算格问题：SVP、CVP 与 SIVP](/knowledge/svp-cvp-and-sivp/)
- [08 覆盖半径与转移定理](/knowledge/covering-radius-and-transference/)
- [15 高斯启发式与随机球面模型](/knowledge/gaussian-heuristic-and-random-spheres/)