步骤一：基线复述与复杂度现状

1.1 原方程与已知解

丢番图方程为 $x^3+y^3+z^3=42$，已知解为：

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

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

1.2 模 9 强约束

对任意整数 $n$，$n^3 \pmod 9 \in \{0,1,8\}$。42 ≡ 6 ≡ -3 (mod 9)，三立方模 9 的唯一可能是三个立方都为 -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 \Longrightarrow s(s^2+3t^2)+4z^3=168

\boxed{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=0$ 无解（$z^3=42$ 无整数解）。

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

基线变换将 $O(N^3)$ 降为 $O(N^2)$。Booker–Sutherland 使用的参数 $d_{BS}=|x+y|$ 与我们的 $s$ 直接对应：$s=x+y$，故 $|s|=d_{BS}$。$s$ 保留符号信息，$d_{BS}$ 取绝对值。根据 MIT 新闻报道，Booker–Sutherland “使用单个整数参数 $d$ 来确定一个相对较小的可能性集合”，与我们的 $s$ 参数在结构上一致。

声明：本方案不预设 $O(N^{1/3})$ 或任何未验证的渐近指数。

步骤二：旗石覆盖定义

2.1 Elkies 原始方法的形式

Elkies 方法的几何本质：用极小的平行四边形（旗石）覆盖曲线 $Y=\sqrt[3]{1-X^3}$，$X\in[0,1/\sqrt[3]{2}]$。算法寻找落在某个旗石内的有理点 $(x/z,y/z)$，$z$ 上界为 $N$。

已知事实：Elsenhans 与 Jahnel 的实现中，旗石长度动态选择——在 $x=0$ 附近约 $8.4\times 10^{-12}$，在 $x=1/\sqrt[3]{2}$ 附近约 $6.6\times 10^{-14}$。旗石面积基本恒定，约 $1.7\times 10^{-40}$。他们的搜索范围 $|x|,|y|,|z|<10^{14}$，整个搜索耗时约 10 个月 CPU 时间，仅 14% 用于格约化，主要时间消耗在 Fincke–Pohst 算法的格点搜索上。

2.2 我们基线中的旗石覆盖

固定 $s$，方程 $4z^3+3st^2=A$（$A=168-s^3$）定义 $(z,t)$ 平面上的一条曲线。将变量无量纲化：

Z = \frac{z}{z_{\max}},\quad T = \frac{t}{t_{\max}}

曲线近似为 $4Z^3 + 3sT^2 = A/z_{\max}^3$ 形式。分析性推测：在 $z$ 的某个区间内，该曲线可以用其切线线性近似，覆盖该区间的平行四边形即为旗石。

旗石尺寸 $\delta$：与曲线局部曲率相关。分析性推测：在 $z$ 接近 $N$ 量级时，曲率较小，$\delta$ 可以较大；在 $z$ 较小时，曲率较大，$\delta$ 必须较小。

旗石数量 $F$：$F \sim O(N/\delta)$。卡点声明：$\delta$ 的精确表达式依赖曲线 $4z^3+3st^2=A$ 的局部几何，无法从公开文献直接反推。

步骤三：单旗石显式格构造

3.1 线性化与格基

在某个旗石内，取基准点 $(z_0, t_0)$ 满足 $4z_0^3+3st_0^2 \approx A$。令 $z=z_0+u$，$t=t_0+v$，展开：

4(z_0+u)^3+3s(t_0+v)^2=A

4z_0^3+12z_0^2u+12z_0u^2+4u^3+3st_0^2+6st_0v+3sv^2=A

忽略三次项 $4u^3$（当 $|u|$ 远小于 $z_0$ 时），得到二次型近似：

12z_0^2u+12z_0u^2+6st_0v+3sv^2 \approx A-4z_0^3-3st_0^2

定义误差 $\Delta = A-4z_0^3-3st_0^2$。构造 3 维格 $\mathcal{L}$，基向量为：

\mathbf{b}_1 = (1, 0, 0),\quad \mathbf{b}_2 = (0, 1, 0),\quad \mathbf{b}_3 = (0, 0, M)

其中 $M$ 是缩放因子，用于平衡各维度的量级。目标向量 $\mathbf{t}=(0, 0, \Delta)$。寻找格向量 $\mathbf{v}=u\mathbf{b}_1+v\mathbf{b}_2+w\mathbf{b}_3$ 使得 $\|\mathbf{v}-\mathbf{t}\|$ 最小。

3.2 卡点声明

关键卡点：上述格构造是近似的，因为忽略了 $4u^3$ 项。Elkies 方法的精妙之处在于旗石足够小，使得线性近似误差可控。但旗石尺寸 $\delta$ 与 $u$ 的上界直接相关，而 $\delta$ 的选择又影响旗石数量 $F$。这一 trade-off 的精确分析需要曲线局部几何的详细计算，无法从公开文献的概要描述中唯一确定。

步骤四：复杂度校准

4.1 单旗石内复杂度

LLL 约化：3 维格的 LLL 约化成本为 $O(\log^3 B)$，$B$ 为基向量位长。已知事实：Elsenhans–Jahnel 实现中仅 14% 时间用于格约化。

Fincke–Pohst 枚举：约化后，在格中搜索短向量。已知事实：Fincke–Pohst 算法的最坏情况复杂度为 $2^{O(n^2)}$，但对随机格模型，复杂度常为多项式（通常三次）。

4.2 全局复杂度

已知事实：Heath-Brown 方法复杂度为 $O(N^{1+\varepsilon})$（$N$ 为搜索上界）。Elkies 方法被描述为“当前已知的最佳算法”，但其精确复杂度指数在公开文献中未被明确给出。

分析性推测：Elkies 方法的全局复杂度约为 $O(N^{1+\varepsilon})$，与 Heath-Brown 同阶但常数因子更小。声明：无法从公开细节唯一确定 Elkies 方法的精确复杂度指数，也无法反推 Booker–Sutherland 2019 年算法的渐近指数。

4.3 与 O(N^2) 的对比

方法 复杂度 来源
基线 $s,t$ 变换 $O(N^2)$ 本重构
Heath-Brown $O(N^{1+\varepsilon})$ 已知事实
Elkies 方法 约 $O(N^{1+\varepsilon})$（推测） 分析性推测
Booker–Sutherland 2019 无法从公开细节唯一确定 卡点声明

步骤五：与 Booker–Sutherland 对接

模筛：模 9 约束 $s\equiv 1 \pmod 3$，$t\equiv 0 \pmod 3$ 作为预处理。Booker–Sutherland 还使用了更精细的模筛。

CRT 枚举：MIT 新闻报道提到“使用单个整数参数 $d$ 来确定一个相对较小的可能性集合”，对应 CRT 枚举对 $z$ 同余类的压缩。

Elkies 格约化：Booker–Sutherland 在 Elkies 方法基础上做了改进。已知事实：他们的搜索使用了 Charity Engine 分布式平台，单处理器需超过 50 年。

立方互反律约束：Cassels 通过立方互反律证明了 $x^3+y^3+z^3=3$ 的整数解满足 $x\equiv y\equiv z \pmod 9$。分析性推测：类似方法可能对 $k=42$ 给出额外约束，但公开文献中未明确给出 $k=42$ 的 Cassels 型结果。

步骤六：小规模验证方案

k=3：已知解 $(1,1,1)$，对应 $s=2,t=0,z=1$。验证 $t^2=(3-s^3-4z^3)/(3s)$ 在 $s=2,z=1$ 时给出 $t^2=0$。

k=30：已知解数量级约 $10^{12}$，远小于 42 问题的 $10^{17}$。可在小范围 $s,z\in[-10^6,10^6]$ 内验证。

旗石覆盖验证：选取小范围 $z\in[1,1000]$，构造旗石覆盖，运行 LLL 约化，检查是否复现已知小解或压缩候选。禁止伪造 LLL 输出。

步骤七：Pareto 评估