2026 年 5 月，OpenAI 的研究模型首次发现了 Erdős 单位距离猜想的一个反例构造，随后 Bloom、Sawin、Schildkraut 和 Zhelezov 合作完成了 sum-product 猜想的反驳。这两项突破的核心工具并非传统的组合几何方法，而是来自代数数论中的高次数域构造。这一进展为计算几何中的点集距离问题提供了全新的算法复杂度下界分析框架。
Sum-Product 问题与单位距离问题的背景
Erdős 和 Szemerédi 提出的 sum-product 猜想认为：对于任意有限集合 $A \subset \mathbb {R}$，其和集 $A+A = {a+b : a,b \in A}$ 与积集 $A \cdot A = {ab : a,b \in A}$ 中至少有一个的大小必须接近 $|A|^2$。形式化地说，猜想断言 $\max (|A+A|, |A \cdot A|) \geq |A|^{2-o (1)}$。此前最好的下界仅为 $|A|^{4/3+c}$ 量级，与猜想的差距显著。
单位距离问题则关注平面上 $n$ 个点之间单位距离对的最大数量。Erdős 在 1946 年构造了一个达到 $n^{1+c/\log\log n}$ 的实例，而 Spencer、Szemerédi 和 Trotter 证明了上界 $O (n^{4/3})$。这两个问题在组合数学中困扰研究者数十年，直到数域构造的出现才迎来突破性进展。
张量幂技巧：从微小改进到多项式增益
这些新构造的核心思想可以概括为 "张量幂技巧"（tensor power trick）。其基本策略是：首先在低维找到一个仅提供常数因子改进的 "平凡" 构造，然后通过高维类比将其 "放大" 为多项式级别的增益。
以 sum-product 问题为例，考虑算术级数 $P = {1, 2, \ldots, X}$ 和几何级数 $G = {1, 2, 4, \ldots, 2^Y}$。直接计算可得 $|P+P| \approx 2X$ 而 $|G \cdot G| \approx 2Y$。若取 $A = G \cdot P$，则 $|A \cdot A| \leq (2/Y)|A|^2$，实现了对平凡上界 $|A|^2$ 的常数改进。然而问题在于 $|A|$ 的上限约为 $2^{O (Y)}$，无法任意增大。
数域构造的关键在于将这一模式推广到高维。设 $K$ 是一个次数为 $d$ 的全实数域，其整数环 $\mathcal {O}_K$ 在 Minkowski 嵌入下形成 $\mathbb {R}^d$ 中的格点。定义加法球 $B^+(X) = {x \in \mathcal {O}K : |x|\infty \leq X}$，其大小约为 $X^d$。类似地，单位群 $\mathcal {O}_K^\times$ 在对数嵌入下形成超平面中的秩 $d-1$ 格点，定义乘法球 $B^\times (Y)$ 的大小约为 $Y^{d-1}$。
取 $G = B^\times (Y)$ 和 $P = B^+(X)$，令 $A = G \cdot P$，则当 $d \to \infty$ 时，$|A|$ 可以任意大（增长如 $C^d$），同时 $\max (|A+A|, |A \cdot A|) \ll |A|^{2-c}$ 对某个常数 $c > 0$ 成立。
数域构造的关键参数与约束
实现上述构造需要满足严格的数论条件。首先是数域塔的存在性：需要一族次数 $d \to \infty$ 的全实数域，其判别式 $\Delta_K$ 满足 $\Delta_K \leq O (1)^d$。这一条件至关重要 —— 若判别式增长更快（如 $O (d)^d$），则上述估计中的常数将随 $d$ 恶化，无法得到多项式级别的改进。
Martinet 在 1978 年利用 Golod-Shafarevich 定理证明了满足条件的数域塔确实存在。该定理提供了构造无限类域塔的代数工具，其核心在于通过特定的群表示条件保证塔中各层数域的判别式有界增长。
对于单位距离问题，构造需要略有不同。设 $K$ 有 $r_1 \geq 1$ 个实嵌入和 $r_2 \geq 1$ 对复嵌入，令 $L = K (i)$。定义 $U = {u \in \mathcal {O}_L^\times : u\bar {u} = 1}$，这是单位群的子群，在适当嵌入下可视为 $\mathbb {R}^2$ 中的点集。取 $A_X$ 为 $K$ 中大小不超过 $X$ 的代数整数集，则 $P = A_X \times A_X$ 的大小约为 $(X+O (e^Y))^{2d}$，而单位距离对的数量至少为 $X^{2d} Y^{r_2}$。当 $r_2 \geq cd$ 时，这给出 $n^{1+c}$ 量级的下界。
算法复杂度下界的工程化应用
这些数论构造为计算几何算法分析提供了新的下界工具。具体而言，在以下场景中具有直接应用价值：
点集距离查询的下界分析。对于需要计算或枚举点集中特定距离对的算法（如最近邻搜索、距离阈值计数），上述构造表明存在点集配置使得特定距离的出现频率远高于随机情况。这直接影响了基于哈希或空间划分的数据结构的平均情况分析。
几何图算法的复杂度估计。单位距离图的构造与几何图算法（如单位距离图上的独立集、着色问题）的复杂度密切相关。新的下界构造表明，对于某些点集配置，这些问题的精确求解可能需要超多项式时间。
参数化复杂度中的维度依赖。数域构造清晰地展示了算法复杂度如何依赖于底层空间的 "有效维度"。对于嵌入维度 $d$，点集大小可以指数增长而保持特定的组合性质，这对高维几何算法的参数化分析具有指导意义。
可落地的分析框架与检查清单
在实际应用中，可以采用以下框架评估数域构造对特定算法问题的影响：
-
问题归约检查：确认目标问题是否可以归约到 sum-product 或单位距离计数问题。常见的可归约问题包括特定模式的几何匹配、距离约束满足等。
-
数域参数选择：对于需要显式构造的场景，选择适当的数域参数：
- 次数 $d$：控制点集规模的指数增长基数
- 判别式上界：确保构造的有效性
- 实嵌入与复嵌入比例：影响单位距离构造的几何性质
-
复杂度阈值监控：建立基于 $|A|^{2-c}$ 形式的复杂度阈值，用于判断算法在特定输入规模下的可行性边界。
-
构造有效性验证：对于实际实现的构造，验证判别式和调节子是否满足有界增长条件，这是保证构造质量的关键指标。
局限性与开放问题
需要指出的是，这些构造目前仅适用于实数域 $\mathbb {R}$ 上的点集，对于 Erdős 最初关注的整数集 $\mathbb {Z}$ 情况，sum-product 猜想仍然开放。此外，构造依赖于高次数域的存在性，对于低维场景（如固定维度 $d$）的直接应用有限。
从算法工程的角度，这些构造主要提供理论下界，而非实用的最坏情况输入生成方法。如何将数域构造转化为可高效生成的测试用例，仍是一个值得探索的方向。
资料来源
- Thomas Bloom, "Sum-product, unit distances, and number fields", Erdős Problems Blog, 2026
- Bloom, Sawin, Schildkraut, Zhelezov, arXiv:2605.28781 (sum-product 反例)
- OpenAI, "Unit-distance proof" (单位距离反例)
- Martinet (1978), Golod-Shafarevich 定理在数域塔构造中的应用
内容声明：本文无广告投放、无付费植入。
如有事实性问题，欢迎发送勘误至 i@hotdrydog.com。