For AI agents: the complete documentation index is available at https://shijin.space/llms.txt, the full documentation bundle is available at https://shijin.space/llms-full.txt, and this page is available as Markdown at https://shijin.space/knowledge/babai-nearest-plane/index.md.
ShiJin

    06 Babai 最近平面算法与近似 CVP

    整理日期：2026-10-16。 前置笔记：02 基本区域、格行列式与正交化、04 基本计算格问题：SVP、CVP 与 SIVP、05 格基约化与 LLL 算法。

    本篇使用欧氏范数，先讨论满秩情形：

    B=(b1,…,bn)∈Zn×n,Λ=L(B),t∈Qn.B=(b_1,\ldots,b_n)\in\mathbb Z^{n\times n}, \qquad \Lambda=\mathcal L(B), \qquad t\in\mathbb Q^n.

    记 b1∗,…,bn∗b_1^*,\ldots,b_n^* 为 Gram–Schmidt 正交化向量。

    目标是找到 v∈Λv\in\Lambda，使 ∥t−v∥\|t-v\| 尽可能接近

    dist⁡(t,Λ)=min⁡x∈Λ∥t−x∥.\operatorname{dist}(t,\Lambda) =\min_{x\in\Lambda}\|t-x\|.

    1. 为什么叫“最近平面”

    固定最后一个基向量的整数系数，可以把格分成若干层：

    Λ=⋃c∈Z(cbn+L(b1,…,bn−1)).\Lambda = \bigcup_{c\in\mathbb Z} \left( c b_n+\mathcal L(b_1,\ldots,b_{n-1}) \right).

    每一层位于一个仿射超平面

    Hc=cbn+span⁡(b1,…,bn−1).H_c=c b_n+\operatorname{span}(b_1,\ldots,b_{n-1}).

    这些超平面互相平行，法向量为 bn∗b_n^*，相邻平面的距离为 ∥bn∗∥\|b_n^*\|。因此，离 tt 最近的平面对应

    cn=round⁡(⟨t,bn∗⟩∥bn∗∥2).c_n = \operatorname{round} \left( \frac{\langle t,b_n^*\rangle}{\|b_n^*\|^2} \right).

    算法先选这一层，再在该层中处理剩余的基向量，逐步把问题降到一维。

    这里采用的是贪心选择：最近的平面不一定包含最近的格点，所以一般只能得到近似解。

    2. 算法步骤

    NearestPlane(B, t):
    计算 B 的正交化向量 b₁*, …, bₙ*
    r ← t
    v ← 0

    对 i = n, n−1, …, 1:
        c ← round(〈r, bᵢ*〉 / ||bᵢ*||²)
        v ← v + c bᵢ
        r ← r − c bᵢ

    返回 v

    其中 round 表示取最近整数；恰好位于中点时，固定采用一种取整规则即可。

    理解算法时，需要区分两个操作：

    • 计算系数使用 bi∗b_i^*：利用正交方向判断当前目标离哪一层最近。
    • 更新残差使用 bib_i：每次减去原格中的向量，保证最终输出仍属于 Λ\Lambda。

    每轮都对当前残差 rr 计算系数。按下标从大到小处理，是因为后续使用的 b1,…,bi−1b_1,\ldots,b_{i-1} 都与 bi∗b_i^* 正交，不会改变已经处理好的这个方向。

    最终

    v=∑i=1ncibi∈Λ,r=t−v.v=\sum_{i=1}^n c_i b_i\in\Lambda, \qquad r=t-v.

    3. 任意基下的误差上界

    每个正交方向都进行了一次最近整数取整，因此最终误差可以写成

    t−v=∑i=1nεibi∗,∣εi∣≤12.t-v=\sum_{i=1}^n\varepsilon_i b_i^*, \qquad |\varepsilon_i|\le\frac12.

    由正交性，

    ∥t−v∥2≤14∑i=1n∥bi∗∥2.\boxed{ \|t-v\|^2 \le \frac14\sum_{i=1}^n\|b_i^*\|^2 }.

    这个结论对任意格基成立，但它给出的是由当前基决定的绝对误差上界，还没有说明误差相对最优距离有多大。相关几何解释和残差性质见 Micciancio《Basis Reduction》，Fall 2017，§2，第 3–5 页，尤其 Lemma 5。

    4. 配合 LLL 得到近似 CVP 算法

    先使用第五篇的 LLL 算法约化输入基，再运行最近平面算法：

    B′←LLL⁡3/4(B),v←NearestPlane⁡(B′,t).B'\leftarrow \operatorname{LLL}_{3/4}(B), \qquad v\leftarrow\operatorname{NearestPlane}(B',t).

    得到

    ∥t−v∥≤2n/2dist⁡(t,Λ).\boxed{ \|t-v\| \le 2^{n/2}\operatorname{dist}(t,\Lambda) }.

    因此，这一组合是一个多项式时间的 2n/22^{n/2}-近似 CVP 算法。这里固定 LLL 参数 δ=3/4\delta=3/4，复杂度按整数基和有理目标的输入位长计算。见 Regev《Lecture 3: CVP Algorithm》，Fall 2004，第 1 页算法及第 3–4 页 Lemma 6。

    近似保证的证明只需记住两个要点。

    首先，LLL 条件给出

    ∥bi∗∥2≤2n−i∥bn∗∥2,\|b_i^*\|^2\le 2^{n-i}\|b_n^*\|^2,

    于是

    ∑i=1n∥bi∗∥2≤(2n−1)∥bn∗∥2.\sum_{i=1}^n\|b_i^*\|^2 \le (2^n-1)\|b_n^*\|^2.

    其次，比较算法选中的层与一个最近格点所在的层：

    • 如果处于同一层，就在这一层中递归分析。
    • 如果处于不同层，最优距离至少为半个层间距，即 ∥bn∗∥/2\|b_n^*\|/2。结合上面的误差上界，就能控制相对误差。

    LLL 控制正交化长度之间的关系，使逐层取整的误差能够与最优距离建立联系。

    5. 一个二维例子

    沿用第二篇的基：

    b1=(2,0),b2=(1,2).b_1=(2,0),\qquad b_2=(1,2).

    其正交化向量为

    b1∗=(2,0),b2∗=(0,2).b_1^*=(2,0),\qquad b_2^*=(0,2).

    这组基本身已经满足 δ=3/4\delta=3/4 的 LLL 条件。

    取目标

    t=(65,910).t=\left(\frac65,\frac9{10}\right).

    先处理第二个方向：

    c2=round⁡(⟨t,b2∗⟩∥b2∗∥2)=round⁡(920)=0.c_2 = \operatorname{round} \left( \frac{\langle t,b_2^*\rangle}{\|b_2^*\|^2} \right) = \operatorname{round}\left(\frac9{20}\right) =0.

    因此选中 y=0y=0 这一层，残差仍为 tt。

    再处理第一个方向：

    c1=round⁡(35)=1.c_1 = \operatorname{round}\left(\frac35\right) =1.

    算法输出

    v=b1=(2,0),∥t−v∥2=2920.v=b_1=(2,0), \qquad \|t-v\|^2=\frac{29}{20}.

    但另一层中的格点 b2=(1,2)b_2=(1,2) 满足

    ∥t−b2∥2=54<2920.\|t-b_2\|^2=\frac54<\frac{29}{20}.

    这说明：即使输入基已经经过 LLL 约化，最近平面算法仍可能错过真正的最近格点。

    另外，若直接对原基坐标取整，

    B−1t=(3/89/20),B round⁡(B−1t)=(0,0).B^{-1}t = \begin{pmatrix} 3/8\\ 9/20 \end{pmatrix}, \qquad B\,\operatorname{round}(B^{-1}t)=(0,0).

    它与最近平面算法的输出不同。两者的区别在于：直接坐标取整一次性处理原基坐标；最近平面算法沿正交方向，依据当前残差逐层取整。

    LLL 提供基的质量保证，Babai 算法利用这组基逐层选取格点；二者结合，得到具有明确近似因子的 CVP 算法。

    引用此笔记