浮点 LLL 的精度与正确性#

在格基约化与 LLL 算法的二维例子中，第一步算出 $\mu_{2,1}=8/5$，取最近整数 $q=2$，把第二列更新为 $b_2-2b_1$。这一步可以分开执行：用浮点数估计 $\mu_{2,1}$，选定整数 $q$，再用精确整数运算更新基。

这种分工有一个重要后果。即使 $q$ 选错，减去整数倍的另一列仍是幺模换基，输出仍生成原格。但更新后的投影系数是 $\mu_{2,1}-q$，它可能落在 $[-1/2,1/2]$ 之外。保持原格取决于怎样执行换基，达到约化条件还取决于怎样选择换基。

#取整和交换各有一条判定边界

先沿用上一篇的严格尺寸条件 $|\mu_{i,j}|\le 1/2$。尺寸约化要判断 $\mu_{i,j}$ 最接近哪个整数，相邻两个选择的分界在半整数处。例如 $8/5=1.6$ 距离最近的分界 $1.5$ 有 $0.1$。只要近似值的绝对误差严格小于 $0.1$，这一步仍会取到 $q=2$。

交换则取决于另一个量。沿用前缀正交投影 $\pi_{k-1}$，记 $g_i=\|b_i^*\|_2$。将 Lovász 条件的右侧减去左侧，定义

当 $\Delta_k<0$ 时交换，当 $\Delta_k\ge 0$ 时通过检查。上一篇图 1 中，$\pi_1$ 是恒等映射，尺寸约化后的两列是 $(2,1)^T$ 和 $(-1,0)^T$，所以 $\Delta_2=1-15/4=-11/4$。端点落在圆内，差值为负，两种表述给出同一个决定。

这个符号也关系到终止性。若交换相邻两列，上一篇的势函数公式给出

因此，真实的 $\Delta_k<0$ 才保证这次交换把势函数降到原来的 $\delta$ 倍以下。错过一次应做的交换，可能让程序过早接受当前基。做了一次不满足该判据的交换，则失去了精确 LLL 证明所用的下降保证 [1, sec. 3.1]。

#在同一张平面图上制造两次误判

固定第一列 $b_1=(1000,0)^T$，令第二列为 $p=(x,y)^T$，仍取 $\delta=3/4$。这时 $\mu_{2,1}=x/1000$，尺寸约化条带的边界是 $x=\pm500$，Lovász 圆的半径平方是 $750000$。下面有意将判定量先四舍五入到两位小数，再作决定，以便直接看见误差的影响。

在条带边缘。 取 $p=(499,1)^T$ 或 $p=(501,1)^T$，精确投影系数分别为 $0.499$ 和 $0.501$。前者应取 $q=0$，后者应取 $q=1$。两者舍入后都变成 $0.50$。若统一取 $q=0$，第二个输入的系数仍是 $0.501$。若统一取 $q=1$，第一个输入的系数变成 $-0.501$。无论怎样处理这个表面上的平局，总有一个输入未完成严格尺寸约化，而两次整数操作都保持原格。

在圆周附近。 取 $p=(0,866)^T$，它已经在条带内。检查平方长度之比，有

端点在圆内，应当交换。若先将比值舍入为 $0.75$，程序就会按等号接受当前基。这个例子说明，判定需要的精度取决于真实值离边界有多远。

#为什么不大的整数也会丢失投影高度

工作精度指浮点数保留的有效位数。把整组基乘同一个 $2^k$，整数条目会变长，但 $\mu_{i,j}$ 和 Lovász 判据中的长度比保持不变。反过来，两列几乎平行时，即使整数条目不大，第二列在第一列正交补上的高度也可能很小。

取整数 $N\ge 2$，令 $b_1=(N,1)^T$、$b_2=(N+1,1)^T$。两列围成的平行四边形面积为 $1$。以第一列为底，第二个正交高度的平方为

记 $G=B^TB$。若从 Gram 矩阵计算同一个量，先算 $T=G_{12}^2/G_{11}$，再算 $s=G_{22}-T$。这里

相减的两项都是 $N^2$ 量级，留下的差只有 $N^{-2}$ 量级。究竟会损失多少位，可以沿着这两步运算计算。

设二进制有效精度为 $w$ 位（含首位），采用就近舍入，单位舍入误差为 $u=2^{-w}$。先假定三个 Gram 元素均已精确读入，运算无上溢或下溢。在这个模型中，每次乘法、除法或减法的计算结果可写成精确结果乘以 $1+e$，其中 $|e|\le u$ [2, sec. 2]。计算 $T$ 要做一次乘法和一次除法，所以

于是最后一次相减在舍入前已经变成 $G_{22}-\widehat T=s-T\theta$。再计入这次减法自身的舍入，得到

关键是式中的 $T/s$。本例恰有 $s=1/G_{11}$，所以 $T/s=G_{12}^2$，随 $N$ 按 $N^4$ 的量级增长。乘除步骤带来的绝对误差至多为 $O(uN^2)$，换算成小差值 $s$ 的相对误差，上界就成为 $O(uN^4)$。要由这个界保证相对误差至多为 $2^{-t}$，取 $w=4\log_2 N+t+O(1)$ 位足够，其中加法常数取足。对这条求值公式，$N$ 每翻一倍，维持同一误差保证大约多需 4 位。这是充分精度的估计，具体输入的舍入误差可以更小。

from fractions import Fraction

N = 2**14
g11 = N*N + 1
g12 = N*(N + 1) + 1
g22 = (N + 1)**2 + 1

exact = g22 - Fraction(g12*g12, g11)
a, b, c = map(float, (g11, g12, g22))
term = b*b/a
print(exact, term == c, c - term)  # 1/268435457 True 0.0

双精度有 $53$ 位有效精度。此时 $uN^4=8$，上述界已经无法保证小的相对误差。三个 Gram 元素本身都能精确表示，但乘除所得的 term 已经舍入到与 c 相同的浮点数。最后的减法准确地返回了零，而真实的 $s>0$，实际相对误差为 $1$。如果改在整数上先求 $G_{11}G_{22}-G_{12}^2=1$，再除以 $G_{11}$，两大数抵消时那一个单位的差就保留下来了。

#L² 与 H-LLL 怎样保证输出

L² 保留精确的 Gram 矩阵。 Nguyen 和 Stehlé 随整数换基更新 $G=B^TB$，从精确内积出发，用浮点 Cholesky 型递推得到 GSO 近似。处理当前列时，可以先减去一组较早列的整数倍，再依据更新后的精确数据重算近似系数，逐次完成尺寸约化。这样，大系数的整数部分可以分几次消去 [2, secs. 3.2–3.3]。

其保证有明确的参数范围。固定 $1/4<\delta<1$ 和 $1/2<\eta<\sqrt{\delta}$，在论文的算术模型中，选择随格秩线性增长的足够工作精度，L² 会在多项式时间内输出满足 Lovász 条件及 $|\mu_{i,j}|\le\eta$ 的基。这里 $\eta-1/2$ 给浮点判定留出了余量。例如，$0.501$ 满足 $\eta=0.51$ 的尺寸界，却超出了上一篇的严格尺寸界。沿用上一篇的长度推导时，相邻高度界也相应变为 $g_k^2\ge(\delta-\eta^2)g_{k-1}^2$ [2, secs. 2.2, 3.4]。

H-LLL 直接对基做 Householder QR。 写 $B=QR$，取 $R$ 的对角元为正，则 $R_{jj}=g_j$，且对 $j<i$ 有 $R_{ji}=g_j\mu_{i,j}$。算法用 Householder 反射计算 $R$ 的近似，再对原整数基执行列操作。其误差分析允许非对角元的误差还与当前列的尺度有关，论文相应采用弱尺寸条件

在论文规定的参数与精度下，算法输出满足这条弱尺寸条件和 Lovász 条件的原格基。比较两种算法的输出时，要连同 $\eta$、$\theta$ 和所检验的不等式一起比较 [3, secs. 2, 4]。

#什么时候提高精度，怎样检查结果

对小规模实现，可以把“这一步能否相信”写成区间判断。假设已有可靠的误差上界，能够保证真实值落在所算区间内。

• 取整。 若 $\mu_{i,j}$ 的整个区间落在 $(q-1/2,q+1/2)$ 内，就采用整数 $q$。若区间碰到半整数边界，就提高精度或用精确分数复核。真实值恰为半整数时，按约定选择任一最近整数。
• 交换。 若 $\Delta_k$ 区间的上端点小于 $0$，就交换。若下端点大于等于 $0$，就接受。其余情况应重算。恰好等于 $0$ 时，精确 Lovász 条件成立。

最后把两个问题分别验算。先用精确整数检查 $U\in\mathbb Z^{n\times n}$、$|\det U|=1$ 和 $B_{\rm out}=B_{\rm in}U$，验证输出生成原格。再从 $B_{\rm out}$ 独立重算 GSO，按任务要求检查全部尺寸条件和每个相邻位置的 Lovász 条件。若要求上一篇的严格 LLL，就用 $1/2$ 作为尺寸阈值。这样即使浮点程序走出了与手算不同的换基路径，也能直接判断它交出的基是否合格。

#参考文献