适用范围：计算格与格密码中的欧氏几何基础。整理日期：2026-09-27。 前置笔记：02 基本区域、格行列式与正交化。
本篇讨论如何描述格中短向量的长度，以及如何利用行列式保证短向量存在。考虑满秩格 \(\Lambda=\mathcal L(B)\subseteq\mathbb R^n\)，使用欧氏范数 \(\|\cdot\|_2\)。
逐次极小值：找到独立方向需要多大的半径#
记以原点为中心、半径为 \(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]
例如，
此时
虽然 \((2,0)\) 的长度为 \(2\)，但它与 \((1,0)\) 共线。要获得第二个独立方向，必须找到纵坐标非零的格向量，其长度至少为 \(3\)。
因此，\(\lambda_i\) 不是把所有非零格向量按长度排序后得到的第 \(i\) 个长度。
正交化给出的最短向量界#
设 \(b_1^*,\ldots,b_n^*\) 是基 \(B\) 的 Gram–Schmidt 正交化，则
右侧直接来自：每个基向量都是非零格向量。
左侧的关键是整数系数。对任意非零格向量
取最大的满足 \(z_k\ne0\) 的下标 \(k\)。\(v\) 在 \(b_k^*\) 方向上的正交投影为 \(z_kb_k^*\)，故
两端的界随基的选择变化，中间的 \(\lambda_1(\Lambda)\) 保持不变。[2，PDF 第 2—3 页，Theorem 2]
Minkowski 凸体定理：体积足够大就包含非零格点#
设 \(K\subseteq\mathbb R^n\) 是可测凸集，且关于原点中心对称，即 \(K=-K\)。如果
那么
证明思路只需记住两步：
- 由 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 第一定理：控制最短非零向量#
在欧氏范数下，有
这是讲义采用的简化上界。它将行列式描述的体积尺度转化为短向量的长度尺度。
推导可以使用立方体：取 \(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 讲义中的简化上界形式：
等价地，
它控制所有逐次极小值的几何平均值。由于
这个结论也蕴含第一定理的上界。[1，第 8—9 页，Theorem 3]
不能据此断言每个 \(\lambda_i\) 都小于右侧。前面的 \(\mathbb Z\times3\mathbb Z\) 就满足
本篇只记录这一上界形式，暂不展开第二定理的完整双侧形式与证明。
来源与阅读位置#
- 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。原文
- Daniele Micciancio，Minkowski’s theorem，PDF 页首标注 Fall 2017，由 2019 年课程页链接。补充最短向量下界与逐次极小值：PDF 第 2—3 页 Theorem 2、第 9 页 Definition 11。原文
来源于 2026-09-26 核对，正文按已确认的草稿整理。
下一篇计划：《04 基本计算格问题：SVP、CVP 与 SIVP》，讨论如何寻找这些向量，以及如何定义近似解。