【格理论（一）】投影格与格基规约

横看成岭侧成峰，
远近高低各不同。

——苏轼《题西林壁》

Minkowski 第二定理与投影格

Minkowski 第二定理的证明中，我们事实上可以注意到一个事实：

$y\in \text{span}(\tilde{b}_1, \cdots, \tilde{b}_i) \iff y\in \text{span}(b_1, \cdots, b_i)$

记：

$V_{i-1} = \text{span}(b_1, \cdots, b_i) = \text{span}(\tilde{b}_1, \cdots, \tilde{b}_i)$

考虑向量 $x \in \mathbb{R}^n$ ，它在子空间 $V_{i-1}$ 中存在分量：

$x_1 = \sum\limits_{j=1}^{i-1}\dfrac{\langle x, \tilde{b}_j \rangle}{\langle\tilde{b}_j, \tilde{b}_j\rangle} \tilde{b}_j$

顺利成章地，它在 $V_{i-1}$ 中存在分量：

$x_2 = x - x_1 = x - \sum\limits_{j=1}^{i-1}\dfrac{\langle x, \tilde{b}_j \rangle}{\langle\tilde{b}_j, \tilde{b}_j\rangle} \tilde{b}_j$

$x_2 \perp V_{i-1}$

即：每一个 $\mathbb{R}^n$ 中的 $x$ 都可以被拆分成两个部分，一部分恰好在 $V_{i-1}$ 中，另一部分恰好完全与 $V_{i-1}$ 垂直。

下面的一系列定义是自然的：

定义正交补空间：

$V_{i-1}$ 的正交补空间 $V_{i-1}^\perp$ 是 $\mathbb{R}^n$ 中所有与 $V_{i-1}$ 垂直的向量构成的集合：

$V_{i-1}^\perp = \{ y \in \mathbb{R}^n \mid \langle y, v \rangle = 0, \forall v \in V_{i-1} \}$

在当前的 Gram-Schmidt 基下，由于前 $i-1$ 个方向已经被 $b_1, \dots, b_{i-1}$ 占据，剩余的维度构成了这个正交补空间，因此 $V_{i-1}^\perp$ 的维度恰好为 $n - i + 1$。

定义正交投影：

设 $\pi_i: \mathbb{R}^n \to V_{i-1}^\perp$ 为向子空间 $V_{i-1}$ 的正交补空间所作的映射。对于任意的向量 $x \in \mathbb{R}^n$，其正交投影 $\pi_i(x)$ 恰好就是剥离了 $V_{i-1}$ 中的分量 $x_1$ 后剩下的部分 $x_2$：

$\pi_i(x) = x - \sum_{j=1}^{i-1} \frac{\langle x, \tilde{b}_j \rangle}{\langle \tilde{b}_j, \tilde{b}_j \rangle} \tilde{b}_j$

这个操作本质上是将高维空间沿着 $V_{i-1}$ 的方向“压扁”，使得所有与 $V_{i-1}$ 平行的信息被消除，只保留垂直方向的纯粹信息。

定义投影格：

将正交投影 $\pi_i$ 作用于整个格 $\Lambda$ 上得到的新集合 $\pi_i(\Lambda)$ 称为投影格：

$\pi_i(\Lambda) = \{ \pi_i(x) \mid x \in \Lambda \}$

只要 $b_1, \dots, b_n$ 是 $\Lambda$ 的一组基，$\pi_i(\Lambda)$ 必然构成 $V_{i-1}^\perp$ 上的一个全秩离散格（秩为 $n - i + 1$）。由于前 $i-1$ 个基向量的投影均为 $0$，这个投影格完全由剩余基向量的投影张成：

$\pi_i(\Lambda) = \text{span}_{\mathbb{Z}}(\pi_i(b_i), \pi_i(b_{i+1}), \dots, \pi_i(b_n))$

显然：

$\det(\pi_i(\Lambda)) = \prod_{j=i}^n \|\tilde{b}_j\|$

正交投影演化过程演示 \(\pi_i: \Lambda \to V_{i-1}^\perp\)

参数 \(t\): 0.00

\(V_{i-1}\)

\(V_{i-1}^\perp\)

\(b_i\)

\(b_{i+1}\)

描述：调节滑块可观察从原始格点\(\Lambda\)（参数\(t=0\)）沿蓝色虚线 \(V_{i-1}\) 方向正交投影到其正交补空间\(V_{i-1}^\perp\)上的连续演化过程。背景展现了 \(3 \times 3 \times 3\) 的局部空间格点结构，平面上的暗红色固定点及网格为目标投影格\(\pi_i(\Lambda)\)。

注：虽然这里我们让某些格向量和$V_{i-1}$平行了，但这件事情在高维的情况下并不常常存在，请注意甄别。

格基规约算法

格基规约算法的核心目的是在给定格 $\Lambda$ 的某组基的情况下（可能是任意一组基，可能是满足某种特别结构的基，但是通常是正交性差、向量很长的 “坏基”），将其转化为同一个格子的一组 “好基”。

什么样的基叫做 “好基”？

最直观的对于 “好基” 的数学特征是：

• 短（Shortness）：基向量的长度 $\|b_i\|$ 尽可能接近格的理论连续极小值 $\lambda_i(\Lambda)$
• 正交性（Orthogonality）：基向量之间的夹角尽可能接近 90 度

当我们能够使用规约算法通过输出一组“好基”时，我们就能够直接解决低维情况下的精确 SVP/CVP，或在多项式时间内给出高维情况下的近似解。

还有其他“好基”的指标吗？2003 年，C.P. Schnorr 提出了著名的几何级数假设（GSA）：对于一个随机的高维格，在经过足够强度的块规约达到稳态后，其 Gram-Schmidt 正交化向量的长度会呈现出完美的几何级数衰减，即存在一个衰减因子 $\alpha \in (0, 1)$，使得：

$\|\tilde{b}_i\| \approx \alpha^{i-1} \|\tilde{b}_1\|$

这为我们提供了对于“好基”的另一种描述。

第一种对于“好基”的视角为我们带来了 LLL 算法，BKZ算法；第二种对于“好基”的视角为我们带来了 Flatter 算法。

Gauss 算法

在 LLL 算法诞生以前，最基础的是 1801 年高斯给出的算法，后世称为 Gauss 算法。Gauss 算法解决了$2$维格上的精确 SVP 求解问题，它既可以看作是辗转相除法/欧几里得算法（万法之母） 的$2$维推广，也可以看作是 LLL 算法的前身。

Gauss 算法原理与描述

对于 $\mathbb{R}^2$ 上的 $2$ 维格 $\Lambda$，我们得到了一组基 $(b_1, b_2)$，现在我们想要让这组基尽可能地短且正交。

自然地，我们从正交入手。这时我们发现了第一个重要的事实：

（事实一）如果 $b_1\perp b_2$ 本身成立，则无论 $b_1, b_2$ 怎么进行线性组合，都无法造出更短的向量。

那如果不正交的话，，我们的第一反应自然就是 Gram-Schmidt 正交化（简称 GSO）：

$\begin{cases} \tilde{b}_1 = b_1\\ \tilde{b}_2 = b_2 - \dfrac{\langle b_2, b_1\rangle}{\left\| b_1 \right\|^2}\cdot b_1 \end{cases}$

但是很显然我们这里是在格里进行研究的，而 $\mu = \dfrac{\langle b_2, b_1\rangle}{\left\| b_1 \right\|^2}$ 只是一个有理数，我们并不能保证它是一个整数。

于是聪明的你说：取离 $\mu$ 最近的整数不就好了？
于是就有了下面的优化版方法：

$\begin{cases} b_1' \gets b_1\\ b_2' \gets b_2 - \lfloor\mu\rceil\cdot b_1' \end{cases}$

现在我们来验证一下它是不是真的变成了一组更好的基：

• 正交性：$\dfrac{\langle b_2', b_1' \rangle}{\|b_1'\|^2} = \left|\dfrac{\langle b_2, b_1 \rangle}{\|b_1\|^2} - \left\lfloor\dfrac{\langle b_2, b_1 \rangle}{\|b_1\|^2}\right\rceil\right| \leqslant \dfrac{1}{2}$，即一直被控制在 $\dfrac{1}{2}$ 以内；
• 向量变短：知道 $b_2 = \tilde{b}_2 + \mu\cdot \tilde{b}_1$，然后带入 $b_2' = \tilde{b}_2 + \left(\mu - \lfloor\mu\rceil\right)\cdot \tilde{b}_1$。下面将两式的模长相减，进行比较：

$\|b_2\|^2 - \|b_2'\|^2 = \left(\mu^2 - \left(\mu - \lfloor\mu\rceil\right)^2\right)\cdot \|\tilde{b}_1\|^2$

注意到 $\left(\mu - \lfloor\mu\rceil\right)^2 \leqslant \dfrac{1}{4}$，此时，就需要分两种情况进行讨论。

• 当 $|\mu| > \dfrac{1}{2}$ 时，$\|b_2\|^2 - \|b_2'\|^2 > 0$ 严格成立，这说明我们的确得到了更短的 $b_2$（即 $b_2'$）；
• 当 $|\mu| < \dfrac{1}{2}$ 时，显然 $\lfloor \mu\rceil = 0$，此时 $\|b_2\|^2 = \|b_2'\|^2$；
• 当 $|\mu| = \dfrac{1}{2}$ 时，显然 $\mu^2 - \left(\mu - \lfloor\mu\rceil\right)^2 = 0$，此时 $\|b_2\|^2 = \|b_2'\|^2$。

上述讨论告诉了我们另外一个极其重要的事实：

（事实二）当 $\mu\leqslant \dfrac{1}{2}$，即 $\langle b_1, b_2 \rangle \leqslant \dfrac{1}{2}\|b_1\|^2$ 时，我们做 $b_2 \gets b_2 - \left\lfloor\dfrac{\langle b_2, b_1 \rangle}{\|b_1\|^2}\right\rceil\cdot b_1$ 的操作不会让 $b_2$ 变得更短，也不会让它变得更长。

回到 Gauss 算法本身的目的：想要求得真正最短的向量，这意味着最好直接获取最短的向量，因此考虑直接指定 尺寸约化条件：

$\|b_1\| \leqslant \|b_2\|$

这个规定的意义就是：我们期望最终得到的 $b_1$ 就恰好是最短的。

此时算法呼之欲出：

1. 尺寸约化 (Size Reduction)：利用当前较短的基向量 $b_1$ 去“削减”较长的基向量 $b_2$。

   • 计算系数 $\mu = \dfrac{\langle b_2, b_1 \rangle}{\|b_1\|^2}$，更新 $b_2 \gets b_2 - \lfloor \mu \rceil \cdot b_1$，其中 $\lfloor \mu \rceil$ 表示四舍五入。
   • 目的：通过减去 $b_1$ 的整数倍尽可能地缩短 $b_2$，使其在 $b_1$ 方向上的投影分量长度减半。

2. 长度检验与交换 (Swap)：在尺寸约化后，需要重新检查条件一（$\|b_1\| \leqslant \|b_2\|$）是否成立。

   • 情况一 (交换)：若经过削减后，新的 $b_2$ 比 $b_1$ 更短（即 $\|b_2\| < \|b_1\|$），这意味着找到了一个比当前 $b_1$ 更优秀的最短向量候选人。为维护条件一，必须交换 $b_1$ 和 $b_2$，并用这个更短的、新的 $b_1$ 重新去约化新的 $b_2$。
   • 情况二 (终止)：若经过削减后，$\|b_2\| \geqslant \|b_1\|$ 依然成立，说明 $b_1$ 已经无法再让 $b_2$ 变得更短，系统达到了稳定状态，算法终止。

\begin{algorithm}
\caption{Gauss Lattice Reduction Algorithm (While-Loop Variant)}
\begin{algorithmic}
\Require Basis $(b_1, b_2)$ for a 2-dimensional lattice $\Lambda \subset \mathbb{R}^2$
\Ensure Gauss-reduced basis $(b_1, b_2)$ where $b_1$ is the shortest vector
\State \Comment{Phase 1: Initial Sorting}
\If{$\|b_2\| < \|b_1\|$}
\State $\texttt{SWAP}(b_1, b_2)$;
\EndIf
\State \Comment{Phase 2: Initial Size Reduction}
\State $\mu \gets \dfrac{\langle b_2, b_1 \rangle}{\|b_1\|^2}$;
\State $b_2 \gets b_2 - \lfloor \mu \rceil \cdot b_1$;
\State \Comment{Phase 3: Main Evaluation Loop}
\While{$\|b_2\| < \|b_1\|$}
\State $\texttt{SWAP}(b_1, b_2)$; \Comment{Adopt the new shortest vector as $b_1$}
\State $\mu \gets \dfrac{\langle b_2, b_1 \rangle}{\|b_1\|^2}$;
\State $b_2 \gets b_2 - \lfloor \mu \rceil \cdot b_1$; \Comment{Reduce the new $b_2$}
\EndWhile
\State \Comment{Phase 4: Return Result}
\State \Return $(b_1, b_2)$;
\end{algorithmic}
\end{algorithm}

Gauss 算法会为我们带来一个十分优异的效果：精确求解 SVP。综合事实一，事实二和尺寸约化条件，我们可以受到启发，得到一个十分重要的结论：

$\begin{cases} \|b_1\|\leqslant \|b_2\|\\ |\langle b_1, b_2 \rangle| \leqslant \frac{1}{2}\|b_1\|^2 \end{cases} \implies \|b_1\| = \lambda_1(\Lambda)$

该结论的论述十分简单，设 $v = xb_1+yb_2\in \Lambda$，其中 $x, y\in \mathbb{Z}$，则：

$\dfrac{\|v\|^2}{\|b_1\|^2} = x^2 + y^2 \dfrac{\|b_2\|^2}{\|b_1\|^2} + 2|xy|\dfrac{\langle b_1, b_2 \rangle}{\|b_1\|^2} \geqslant x^2 + y^2 - |xy|$

而由于 $x$，$y$ 均为整数且不同时为 $0$，因此：

$\dfrac{\|v\|^2}{\|b_1\|^2} \geqslant x^2 + y^2 - |xy| = \dfrac{x^2 + y^2}{2} + \dfrac{(|x| - |y|)^2}{2}\geqslant 1$

即证。

Gauss 算法的最优化视角

事实上，我们在 $2$ 维格上求解 SVP 问题，可以看作一个最优化求解问题：

设线性无关非零向量 $b_1, b_2\in\mathbb{R}^2$。求 $\min\limits_{x\in \mathbb{Z}, y\in\mathbb{Z}\text{ 且 } (x, y)\neq (0, 0)}\|xb_1 + yb_2\|$。

下面按照最优化的经典方法对上述问题进行求解。

定义目标函数 $f: \mathbb{Z}^2 \setminus \{(0,0)\} \to \mathbb{R}_{\ge 0}$：

$f(x, y) = \|x b_1 + y b_2\|^2 = x^2\|b_1\|^2 + 2xy\langle b_1, b_2 \rangle + y^2\|b_2\|^2$

因为上述二次方程一定有解/Cauchy-Schwartz不等式，因此必定有 $\|b_1\|^2\cdot \|b_2\|^2 \geqslant \langle b_1, b_2 \rangle^2$，从而对上式进行配方：

$f(x, y) = \|b_1\|^2\left(x + \dfrac{\langle b_1, b_2 \rangle}{\|b_1\|^2}\cdot y\right)^2 + \dfrac{\|b_1\|^2\cdot \|b_2\|^2 - \langle b_1, b_2 \rangle^2}{\|b_1\|^2}\cdot y^2$

记 $L = \|b_1\|^2$，$\mu = \dfrac{\langle b_1, b_2 \rangle}{\|b_1\|^2}$，$\delta = \dfrac{\|b_1\|^2\cdot \|b_2\|^2 - \langle b_1, b_2 \rangle^2}{\|b_1\|^2}$，带入得：

$f(x, y) = L\left(x + \mu y\right)^2 + \delta\cdot y^2$

进而就有：

$\nabla f(x, y) = (2L(x + \mu y), 2(L\mu^2 + \delta)y + 2L\mu x)$

这里的 $\mu$ 正是对应了 GSO 中的 $\mu$。

根据梯度下降的经典思路，得到多个相关求解思路：

• 固定 $y$，优化 $x$：令 $\frac{\partial f}{\partial x} = 2L(x + \mu y) = 0$，解得连续最优解为 $x = -\mu y$。为了满足整数约束，我们直接取最近的整数：$x^*(y) = \lfloor -\mu y \rceil = \left\lfloor - \frac{\langle b_1, b_2 \rangle}{\|b_1\|^2} y\right\rceil$。
• 固定 $x$，优化 $y$：令 $\frac{\partial f}{\partial y} = 0$，解得 $y = -\frac{L\mu}{L\mu^2 + \delta}x$。
  取整得到 $y^*(x) = \left\lfloor -\frac{L\mu}{L\mu^2 + \delta}x \right\rceil = \left\lfloor - \frac{\langle b_1, b_2 \rangle}{\|b_2\|^2} y\right\rceil$。
• 离散梯度下降：本质上等价于 Gauss 算法
  • 选定一个合法的起始点，比如 $P_0 = (1, 0)$。
  • 计算当前点 $P_k$ 的梯度 $g = \nabla f(P_k)$。这个向量指出了目标函数值增加最快的连续方向。
  • 检查 $P_k$ 周围的“整数邻居”（例如 $(x\pm 1, y), (x, y\pm 1), (x\pm 1, y\pm 1)$）。（不能像连续函数那样走一小步 $-\eta g$）
  • 计算哪个邻居在 $-\nabla f(x, y)$ 方向上的投影最大（即哪个邻居能让目标函数下降最多），并且满足该点不是 $(0,0)$。移动到那个邻居。（离散梯度下降在单一坐标轴上的一系列循环试探（$v \to v-u \to v-2u \dots \to v-qu$），在代数结果上等价于 Gauss 算法中的 $v \leftarrow v - \lfloor \mu \rceil u$ 这一单步操作。）
  • 当所有整数邻居的函数值都大于当前点时，达到局部极小值。由于目标函数是严格凸的二次型，在这个二维整数格上，这个“局部极小值”大概率就是全局极小值。

这里笔者就省略更多的讨论了，事实上在此处对这个问题进行讨论，意义不太大。

LLL 算法

LLL 算法于 1982 年由 A.K.Lenstra, H.W.Lenstra, Jr. 和 L.Lovasz 在论文 Factoring Polynomials with Rational Coefficients 中首次提出。

高维的 SVP 问题是一个非凸优化的问题。

BKZ 算法