08 覆盖半径与转移定理 整理日期：2026-10-16。
前置笔记：03 逐次极小值与 Minkowski 定理 、06 Babai 最近平面算法与近似 CVP 、07 对偶格与对偶基 。
设 Λ ⊆ R n \Lambda\subseteq\mathbb R^n Λ ⊆ R n Λ ∗ \Lambda^* Λ ∗
1. 覆盖半径
格的覆盖半径定义为
μ ( Λ ) = max t ∈ R n dist ( t , Λ ) = max t ∈ R n min v ∈ Λ ∥ t − v ∥ . \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\|.
} μ ( Λ ) = t ∈ R n max dist ( t , Λ ) = t ∈ R n max v ∈ Λ min ∥ t − v ∥. 它表示：空间中离格最远的点，到最近格点的距离。
等价地，以所有格点为中心放置同样大小的闭球，能够覆盖整个空间的最小半径就是 μ ( Λ ) \mu(\Lambda) μ ( Λ ) Regev《Lecture 11: Transference Theorems》，Fall 2004，第 2 页，Definition 2 。
固定一个格时，CVP 针对给定目标 t t t CVP 最优距离的最大值 。它是距离参数，并不直接衡量求解 CVP 所需的时间。
2. 与正交化、逐次极小值的联系
设 b 1 ∗ , … , b n ∗ b_1^*,\ldots,b_n^* b 1 ∗ , … , b n ∗ t t t v v v
dist ( t , Λ ) ≤ ∥ t − v ∥ ≤ 1 2 ∑ i = 1 n ∥ b i ∗ ∥ 2 . \operatorname{dist}(t,\Lambda)
\le \|t-v\|
\le
\frac12\sqrt{\sum_{i=1}^n\|b_i^*\|^2}. dist ( t , Λ ) ≤ ∥ t − v ∥ ≤ 2 1 i = 1 ∑ n ∥ b i ∗ ∥ 2 . 因此
μ ( Λ ) ≤ 1 2 ∑ i = 1 n ∥ b i ∗ ∥ 2 . \boxed{
\mu(\Lambda)
\le
\frac12\sqrt{\sum_{i=1}^n\|b_i^*\|^2}.
} μ ( Λ ) ≤ 2 1 i = 1 ∑ n ∥ b i ∗ ∥ 2 . 左侧由格本身决定，右侧随所选的基变化。
覆盖半径与最后一个逐次极小值还满足
1 2 λ n ( Λ ) ≤ μ ( Λ ) ≤ n 2 λ n ( Λ ) . \boxed{
\frac12\lambda_n(\Lambda)
\le
\mu(\Lambda)
\le
\frac{\sqrt n}{2}\lambda_n(\Lambda).
} 2 1 λ n ( Λ ) ≤ μ ( Λ ) ≤ 2 n λ n ( Λ ) . 右侧可以这样理解：选取 n n n λ n ( Λ ) \lambda_n(\Lambda) λ n ( Λ )
这里使用的是一组线性无关向量，不要求它们构成原格的基。双侧界见 Micciancio《The dual lattice》，Winter 2016，§6，PDF 第 8 页 ；下界的几何证明见 Regev，第 2 页，Claim 3 。
3. 对偶短向量给出的覆盖半径下界
取任意非零对偶向量
y ∈ Λ ∗ ∖ { 0 } . y\in\Lambda^*\setminus\{0\}. y ∈ Λ ∗ ∖ { 0 } . 所有格点都满足
⟨ v , y ⟩ ∈ Z . \langle v,y\rangle\in\mathbb Z. ⟨ v , y ⟩ ∈ Z . 选择一个目标 t t t
⟨ t , y ⟩ = 1 2 . \langle t,y\rangle=\frac12. ⟨ t , y ⟩ = 2 1 . 那么对任意 v ∈ Λ v\in\Lambda v ∈ Λ
∥ t − v ∥ ∥ y ∥ ≥ ∣ ⟨ t − v , y ⟩ ∣ ≥ 1 2 . \|t-v\|\,\|y\|
\ge
|\langle t-v,y\rangle|
\ge
\frac12. ∥ t − v ∥ ∥ y ∥ ≥ ∣ ⟨ t − v , y ⟩ ∣ ≥ 2 1 . 所以
μ ( Λ ) ≥ dist ( t , Λ ) ≥ 1 2 ∥ y ∥ . \mu(\Lambda)
\ge
\operatorname{dist}(t,\Lambda)
\ge
\frac1{2\|y\|}. μ ( Λ ) ≥ dist ( t , Λ ) ≥ 2∥ y ∥ 1 . 令 y y y
μ ( Λ ) λ 1 ( Λ ∗ ) ≥ 1 2 . \boxed{
\mu(\Lambda)\lambda_1(\Lambda^*)\ge\frac12.
} μ ( Λ ) λ 1 ( Λ ∗ ) ≥ 2 1 . 几何上，t t t
4. 转移定理
转移定理把原格与对偶格的几何参数联系起来，使一侧的信息能够用于约束另一侧。
Banaszczyk 的逐次极小值转移定理给出
1 ≤ λ i ( Λ ) λ n − i + 1 ( Λ ∗ ) ≤ n , 1 ≤ i ≤ n . \boxed{
1
\le
\lambda_i(\Lambda)\lambda_{n-i+1}(\Lambda^*)
\le
n,
\qquad 1\le i\le n.
} 1 ≤ λ i ( Λ ) λ n − i + 1 ( Λ ∗ ) ≤ n , 1 ≤ i ≤ n . 特别地，
1 ≤ λ n ( Λ ) λ 1 ( Λ ∗ ) ≤ n . 1
\le
\lambda_n(\Lambda)\lambda_1(\Lambda^*)
\le
n. 1 ≤ λ n ( Λ ) λ 1 ( Λ ∗ ) ≤ n . 需要记住的是：原格的第 i i i n − i + 1 n-i+1 n − i + 1 Regev，第 1 页，Theorem 1 与 Remark 1 。
覆盖半径的转移定理为
1 2 ≤ μ ( Λ ) λ 1 ( Λ ∗ ) ≤ n 2 . \boxed{
\frac12
\le
\mu(\Lambda)\lambda_1(\Lambda^*)
\le
\frac n2.
} 2 1 ≤ μ ( Λ ) λ 1 ( Λ ∗ ) ≤ 2 n . 等价地，
1 2 λ 1 ( Λ ∗ ) ≤ μ ( Λ ) ≤ n 2 λ 1 ( Λ ∗ ) . \boxed{
\frac1{2\lambda_1(\Lambda^*)}
\le
\mu(\Lambda)
\le
\frac n{2\lambda_1(\Lambda^*)}.
} 2 λ 1 ( Λ ∗ ) 1 ≤ μ ( Λ ) ≤ 2 λ 1 ( Λ ∗ ) n . 因此，1 / ( 2 λ 1 ( Λ ∗ ) ) 1/(2\lambda_1(\Lambda^*)) 1/ ( 2 λ 1 ( Λ ∗ )) n n n
这里采用 Micciancio，Winter 2016，§6，PDF 第 9 页，Theorem 11 中的 n / 2 n/2 n /2 n n n
下界可以由上一节直接推出；上界需要更深的工具，本篇先记录结论。它们是几何保证，本身没有给出寻找最近格点的算法。
5. 一个二维例子
沿用第三篇的格：
Λ = Z × 3 Z , λ 1 ( Λ ) = 1 , λ 2 ( Λ ) = 3. \Lambda=\mathbb Z\times3\mathbb Z,
\qquad
\lambda_1(\Lambda)=1,
\qquad
\lambda_2(\Lambda)=3. Λ = Z × 3 Z , λ 1 ( Λ ) = 1 , λ 2 ( Λ ) = 3. 其对偶格为
Λ ∗ = Z × 1 3 Z , \Lambda^*=\mathbb Z\times\frac13\mathbb Z, Λ ∗ = Z × 3 1 Z , 因此
λ 1 ( Λ ∗ ) = 1 3 , λ 2 ( Λ ∗ ) = 1. \lambda_1(\Lambda^*)=\frac13,
\qquad
\lambda_2(\Lambda^*)=1. λ 1 ( Λ ∗ ) = 3 1 , λ 2 ( Λ ∗ ) = 1. 每个基本矩形的中心离格最远，例如
t = ( 1 2 , 3 2 ) . t=\left(\frac12,\frac32\right). t = ( 2 1 , 2 3 ) . 于是
μ ( Λ ) = ( 1 2 ) 2 + ( 3 2 ) 2 = 10 2 . \mu(\Lambda)
=
\sqrt{\left(\frac12\right)^2+\left(\frac32\right)^2}
=
\frac{\sqrt{10}}2. μ ( Λ ) = ( 2 1 ) 2 + ( 2 3 ) 2 = 2 10 . 逐次极小值的对应乘积为
λ 1 ( Λ ) λ 2 ( Λ ∗ ) = 1 , λ 2 ( Λ ) λ 1 ( Λ ∗ ) = 1. \lambda_1(\Lambda)\lambda_2(\Lambda^*)=1,
\qquad
\lambda_2(\Lambda)\lambda_1(\Lambda^*)=1. λ 1 ( Λ ) λ 2 ( Λ ∗ ) = 1 , λ 2 ( Λ ) λ 1 ( Λ ∗ ) = 1. 覆盖半径的乘积满足
μ ( Λ ) λ 1 ( Λ ∗ ) = 10 6 ∈ [ 1 2 , 1 ] , \mu(\Lambda)\lambda_1(\Lambda^*)
=
\frac{\sqrt{10}}6
\in
\left[\frac12,1\right], μ ( Λ ) λ 1 ( Λ ∗ ) = 6 10 ∈ [ 2 1 , 1 ] , 与 n = 2 n=2 n = 2
同时，
λ 1 ( Λ ) λ 1 ( Λ ∗ ) = 1 3 < 1 , \lambda_1(\Lambda)\lambda_1(\Lambda^*)=\frac13<1, λ 1 ( Λ ) λ 1 ( Λ ∗ ) = 3 1 < 1 , 说明不能把逐次极小值转移定理的配对误写成两个最短向量长度的乘积。
本篇的核心联系是：覆盖半径描述格点之间最大的空隙，对偶格的短向量通过整数内积约束，帮助控制这些空隙的尺度。
引用此笔记
