从初等重构通往 Elkies 型格约化的可验证路径

步骤一：基线复述与当前复杂度

1.1 原方程与已知解

丢番图方程为：

x^3+y^3+z^3=42

已知整数解为：

x=-80538738812075974,\quad y=80435758145817515,\quad z=12602123297335631

来源：Booker 与 Sutherland 于 2019 年借助 Charity Engine 分布式计算平台（约 50 万台志愿者 PC，累计超过 130 万小时）获得，论文发表于 PNAS，arXiv:2007.01209。

1.2 模 9 强约束

对任意整数 $n$，有 $n^3 \pmod 9 \in \{0,1,8\}$。三立方和模 9 的可能值为 $\{0,1,2,3,6,7,8\}$，因此 $k \equiv 4,5 \pmod 9$ 时无整数解。42 ≡ 6 ≡ -3 (mod 9)，不被排除。

更强的是：42 ≡ 6 ≡ -3 (mod 9)。由于三立方模 9 只取 {0, ±1}，且三个数的和模 9 等于 -3，唯一可能是三个立方都为 -1。即：

x^3 \equiv y^3 \equiv z^3 \equiv -1 \pmod 9

这意味着 $x,y,z \equiv 2,5,8 \pmod 9$，即 $x,y,z \equiv -1 \pmod 3$。由此立即得到：

s = x+y \equiv 1 \pmod 3,\qquad t = x-y \equiv 0 \pmod 3

1.3 s,t 变换完整推导

令 $s=x+y$，$t=x-y$，则 $x=(s+t)/2$，$y=(s-t)/2$。计算：

x^3+y^3=\frac{(s+t)^3+(s-t)^3}{8}=\frac{2s^3+6st^2}{8}=\frac{s(s^2+3t^2)}{4}

代入原方程：

\frac{s(s^2+3t^2)}{4}+z^3=42

s(s^2+3t^2)+4z^3=168

t^2=\frac{168-s^3-4z^3}{3s}\quad (s\neq 0)

必要条件：$s,t,z\in\mathbb{Z}$；$s\equiv t \pmod 2$；右边为非负整数且为完全平方数；$s\neq 0$。

1.4 当前复杂度与 s 与 d_BS 的关系

基线变换将三变量搜索 $O(N^3)$ 降为固定 $s,z$ 后检查一个平方条件的 $O(N^2)$ 候选复杂度，其中 $N\approx 10^{17}$。

Booker–Sutherland 使用的参数 $d_{BS}=|x+y|$ 与我们的 $s$ 直接对应：$s = x+y$，因此 $|s| = d_{BS}$。区别在于 $s$ 保留符号信息，而 $d_{BS}$ 取绝对值。由于 $x+y$ 的符号影响 $x^3+y^3$ 的符号（$s$ 为负时 $x^3+y^3$ 为负），保留符号是必要的。

1.5 当前候选复杂度的来源

基线变换后，对每个 $(s,z)$ 对，需要检查 $t^2=(168-s^3-4z^3)/(3s)$ 是否为非负完全平方数。$s$ 和 $z$ 的范围均为 $O(N)$，因此候选复杂度为 $O(N^2)$。Booker–Sutherland 在此基础上叠加了模筛、CRT 枚举和 Elkies 格约化，将有效计算量降至约 $10^{15}$ 次操作。

步骤二：从基线到格问题

2.1 固定 s 的方程形式

固定 $s$，令 $A=168-s^3$。方程变为：

4z^3+3st^2=A

这是关于 $z$ 的三次项与关于 $t$ 的二次项的混合方程。

2.2 模 3s 同余

从 $4z^3+3st^2=A$ 模 $3s$：

4z^3 \equiv 168-s^3 \pmod{3s}

即：

4z^3 \equiv A \pmod{3s}

由于 $\gcd(4,3s)$ 取决于 $s$ 与 4 的关系。若 $s$ 为奇数，则 $\gcd(4,3s)=1$；若 $s$ 为偶数，则 $\gcd(4,3s)$ 至少为 2。但模 9 约束给出 $s\equiv 1 \pmod 3$，$s$ 的奇偶性由 $s\equiv t \pmod 2$ 和 $t\equiv 0 \pmod 3$ 共同决定，不强制 $s$ 为奇数。

分析性推测：在实际搜索中，可以按 $s$ 的奇偶性分别处理。若 $\gcd(4,3s)=g$，则同余有解的必要条件是 $g\mid A$，且解给出 $z$ 模 $(3s/g)$ 的若干同余类。每个 $s$ 值对应约 $O(1)$ 个 $z$ 的同余类候选，而非 $O(N)$ 个。

2.3 格构造尝试

目标：寻找整数向量 $(z,t,1)$ 使得 $4z^3+3st^2-A$ 的绝对值较小。

卡点：$4z^3$ 是三次项，无法直接嵌入格的标准二次型框架。Elkies 方法的原始形式处理的是 $|x^3+y^3-z^3|$ 的“近 Fermat”问题，本质上是寻找有理点 $(x/z,y/z)$ 靠近 Fermat 曲线 $X^3+Y^3=1$。其格构造依赖于对曲线局部的线性近似——在旗石（flagstone）内，曲线可以被其切线近似，从而将问题转化为格上的最近向量问题。

在我们的基线中，固定 $s$ 后方程 $4z^3+3st^2=A$ 定义了一条平面曲线。对该曲线在旗石内做线性近似，可以构造格，但线性近似的有效性依赖于旗石足够小——这意味着 $z$ 的步长必须足够小，而 $z$ 的范围是 $O(N)$，旗石数量为 $O(N)$ 或更多。

分析性推测：直接对标 Elkies 的旗石方法需要处理 $O(N)$ 个旗石，每个旗石的 LLL 约化成本为 $O(\log^3 N)$，总成本为 $O(N\log^3 N)$，这相比 $O(N^2)$ 是 $O(N)$ 的改进，但尚未达到 $O(N^{1/3})$。

2.4 更现实的格构造路径：二次型嵌入

将 $t^2=(168-s^3-4z^3)/(3s)$ 改写为：

3st^2+4z^3=168-s^3

对固定的 $s$，定义关于 $z$ 的函数 $f(z)=168-s^3-4z^3$。条件为 $f(z)/(3s)$ 是完全平方数。

这可以重写为：存在整数 $t$ 使得

3st^2+4z^3=A

将 $z$ 在某个基准点 $z_0$ 附近展开：$z=z_0+u$，则

z^3=z_0^3+3z_0^2u+3z_0u^2+u^3

方程变为关于 $(u,t)$ 的混合三次-二次方程。忽略 $u^3$（当 $u$ 较小时），得到二次型近似：

3st^2+12z_0^2u+12z_0u^2 \approx A-4z_0^3

这个二次型可以对应一个 3 维格，目标向量与 $(t,u,1)$ 相关。但这只是一个近似，精确性需要额外验证。

卡点声明：精确的格构造需要将三次项 $4u^3$ 也纳入，这超出了标准二次型格约化的范围。Elkies 方法通过旗石覆盖来处理非线性，但旗石数量与 $z$ 的范围成正比。

步骤三：LLL 约化与复杂度

3.1 若采用旗石覆盖方案

假设我们按照 Elkies 原始方法，用旗石覆盖曲线 $4z^3+3st^2=A$。每个旗石对应一个局部线性化，产生一个 3 维格。LLL 约化每个格的复杂度为 $O(\log^3 B)$，其中 $B$ 是格基向量的位长。旗石数量 $F$ 的量级取决于旗石尺寸 $\delta$：$F\sim O(N/\delta)$。

总复杂度：$O((N/\delta)\cdot \log^3 N)$。选择 $\delta$ 使得 LLL 成本与 Fincke–Pohst 枚举成本平衡，得到最优总复杂度约为 $O(N^{1+\varepsilon})$ 量级。

这仍然是 $O(N)$ 量级，不是 $O(N^{1/3})$。

3.2 $O(N^{1/3})$ 的来源：Booker–Sutherland 的实际算法

Booker–Sutherland 在 Elkies 方法基础上做了关键改进：他们不直接搜索 $z$ 的整个范围，而是利用 CRT 枚举在模 $M$ 的多个同余类中同时搜索，将 $z$ 的有效枚举范围压缩。根据论文，他们使用 $d_{BS}=|x+y|$ 参数，将搜索空间组织为关于 $d_{BS}$ 的 $O(N)$ 量级，然后对每个 $d_{BS}$ 值，$z$ 的候选被压缩到 $O(1)$ 个同余类。

分析性推测：$O(N^{1/3})$ 的来源可能与以下事实有关：在 Booker–Sutherland 的算法中，$d_{BS}$ 的搜索范围本身被限制在一个较小的区间内（通过模筛和立方互反律约束），使得 $d_{BS}$ 的有效候选数为 $O(N^{1/3})$，而 $z$ 的枚举对每个 $d_{BS}$ 为 $O(N^{1/3})$，联合复杂度为 $O(N^{2/3})$，再通过格约化进一步压缩到接近 $O(N^{1/3})$。

关键声明：这一复杂度指数的精确推导需要访问 Booker–Sutherland 论文的完整技术细节，而论文中并未明确给出 $O(N^{1/3})$ 的显式推导。分析性推测：$O(N^{1/3})$ 是论文中隐含的渐近复杂度，而非论文明确声明的结果。

步骤四：与 Booker–Sutherland 算法对接

4.1 模筛步骤

模 9、模 7、模 13 等小素数筛法在 Booker–Sutherland 中作为预处理，排除不满足局部障碍的候选。这些筛法贡献 $O(1)$ 量级的常数因子改进。