# 08 覆盖半径与转移定理

整理日期：2026-10-16。
前置笔记：[03 逐次极小值与 Minkowski 定理](/knowledge/successive-minima-and-minkowski/)、[06 Babai 最近平面算法与近似 CVP](/knowledge/babai-nearest-plane/)、[07 对偶格与对偶基](/knowledge/dual-lattices/)。

设 $\Lambda\subseteq\mathbb R^n$ 是满秩格，$\Lambda^*$ 是其对偶格。以下均使用欧氏范数。

## 1. 覆盖半径

格的覆盖半径定义为

$$
\boxed{
\mu(\Lambda)
=
\max_{t\in\mathbb R^n}
\operatorname{dist}(t,\Lambda)
=
\max_{t\in\mathbb R^n}
\min_{v\in\Lambda}\|t-v\|.
}
$$

它表示：空间中离格最远的点，到最近格点的距离。

等价地，以所有格点为中心放置同样大小的闭球，能够覆盖整个空间的最小半径就是 $\mu(\Lambda)$。见 [Regev《Lecture 11: Transference Theorems》，Fall 2004，第 2 页，Definition 2](https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/transference.pdf)。

固定一个格时，CVP 针对给定目标 $t$ 寻找最近格点；覆盖半径则取所有目标的 **CVP 最优距离的最大值**。它是距离参数，并不直接衡量求解 CVP 所需的时间。

## 2. 与正交化、逐次极小值的联系

设 $b_1^*,\ldots,b_n^*$ 是某组格基的正交化向量。由第六篇的最近平面误差界，对任意目标 $t$，都能得到一个格点 $v$，满足

$$
\operatorname{dist}(t,\Lambda)
\le \|t-v\|
\le
\frac12\sqrt{\sum_{i=1}^n\|b_i^*\|^2}.
$$

因此

$$
\boxed{
\mu(\Lambda)
\le
\frac12\sqrt{\sum_{i=1}^n\|b_i^*\|^2}.
}
$$

左侧由格本身决定，右侧随所选的基变化。

覆盖半径与最后一个逐次极小值还满足

$$
\boxed{
\frac12\lambda_n(\Lambda)
\le
\mu(\Lambda)
\le
\frac{\sqrt n}{2}\lambda_n(\Lambda).
}
$$

右侧可以这样理解：选取 $n$ 个长度不超过 $\lambda_n(\Lambda)$ 的线性无关格向量，对它们生成的子格应用最近平面误差界。子格包含在原格中，因此它的覆盖半径不会小于原格的覆盖半径。

这里使用的是一组线性无关向量，不要求它们构成原格的基。双侧界见 [Micciancio《The dual lattice》，Winter 2016，§6，PDF 第 8 页](https://cseweb.ucsd.edu/classes/wi16/cse206A-a/lec3.pdf)；下界的几何证明见 [Regev，第 2 页，Claim 3](https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/transference.pdf)。

## 3. 对偶短向量给出的覆盖半径下界

取任意非零对偶向量

$$
y\in\Lambda^*\setminus\{0\}.
$$

所有格点都满足

$$
\langle v,y\rangle\in\mathbb Z.
$$

选择一个目标 $t$，使

$$
\langle t,y\rangle=\frac12.
$$

那么对任意 $v\in\Lambda$，由整数内积和 Cauchy–Schwarz 不等式，

$$
\|t-v\|\,\|y\|
\ge
|\langle t-v,y\rangle|
\ge
\frac12.
$$

所以

$$
\mu(\Lambda)
\ge
\operatorname{dist}(t,\Lambda)
\ge
\frac1{2\|y\|}.
$$

令 $y$ 为对偶格的最短非零向量，得到

$$
\boxed{
\mu(\Lambda)\lambda_1(\Lambda^*)\ge\frac12.
}
$$

几何上，$t$ 位于两个相邻整数等值平面的中间。对偶向量越短，这些平面之间的距离越大，由此得到的覆盖半径下界也越大。这是第七篇分层解释的直接应用。

## 4. 转移定理

转移定理把原格与对偶格的几何参数联系起来，使一侧的信息能够用于约束另一侧。

Banaszczyk 的逐次极小值转移定理给出

$$
\boxed{
1
\le
\lambda_i(\Lambda)\lambda_{n-i+1}(\Lambda^*)
\le
n,
\qquad 1\le i\le n.
}
$$

特别地，

$$
1
\le
\lambda_n(\Lambda)\lambda_1(\Lambda^*)
\le
n.
$$

需要记住的是：原格的第 $i$ 个逐次极小值，与对偶格的第 $n-i+1$ 个配对。见 [Regev，第 1 页，Theorem 1 与 Remark 1](https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/transference.pdf)。

覆盖半径的转移定理为

$$
\boxed{
\frac12
\le
\mu(\Lambda)\lambda_1(\Lambda^*)
\le
\frac n2.
}
$$

等价地，

$$
\boxed{
\frac1{2\lambda_1(\Lambda^*)}
\le
\mu(\Lambda)
\le
\frac n{2\lambda_1(\Lambda^*)}.
}
$$

因此，$1/(2\lambda_1(\Lambda^*))$ 是覆盖半径的一个下估计，与实际值相差至多 $n$ 倍。

这里采用 [Micciancio，Winter 2016，§6，PDF 第 9 页，Theorem 11](https://cseweb.ucsd.edu/classes/wi16/cse206A-a/lec3.pdf) 中的 $n/2$ 上界。Regev 的 Lecture 11 为简化证明，在 Theorem 4 中证明的是较松的上界 $n$。

下界可以由上一节直接推出；上界需要更深的工具，本篇先记录结论。它们是几何保证，本身没有给出寻找最近格点的算法。

## 5. 一个二维例子

沿用第三篇的格：

$$
\Lambda=\mathbb Z\times3\mathbb Z,
\qquad
\lambda_1(\Lambda)=1,
\qquad
\lambda_2(\Lambda)=3.
$$

其对偶格为

$$
\Lambda^*=\mathbb Z\times\frac13\mathbb Z,
$$

因此

$$
\lambda_1(\Lambda^*)=\frac13,
\qquad
\lambda_2(\Lambda^*)=1.
$$

每个基本矩形的中心离格最远，例如

$$
t=\left(\frac12,\frac32\right).
$$

于是

$$
\mu(\Lambda)
=
\sqrt{\left(\frac12\right)^2+\left(\frac32\right)^2}
=
\frac{\sqrt{10}}2.
$$

逐次极小值的对应乘积为

$$
\lambda_1(\Lambda)\lambda_2(\Lambda^*)=1,
\qquad
\lambda_2(\Lambda)\lambda_1(\Lambda^*)=1.
$$

覆盖半径的乘积满足

$$
\mu(\Lambda)\lambda_1(\Lambda^*)
=
\frac{\sqrt{10}}6
\in
\left[\frac12,1\right],
$$

与 $n=2$ 时的转移界一致。

同时，

$$
\lambda_1(\Lambda)\lambda_1(\Lambda^*)=\frac13<1,
$$

说明不能把逐次极小值转移定理的配对误写成两个最短向量长度的乘积。

本篇的核心联系是：覆盖半径描述格点之间最大的空隙，对偶格的短向量通过整数内积约束，帮助控制这些空隙的尺度。

## 引用此笔记

- [00 概览与阅读路线](/knowledge/lattices-overview/)