单位距离问题

声明： AI能够做出科学突破。

证据： OpenAI的内部模型解决了离散几何中最著名的猜想——即网格在单位距离问题中是否最优。自80年前提出以来，尽管人们对这一问题兴趣浓厚，但一直毫无进展。（不过，其相关领域确实取得了许多活动和进展！）

让我用这个帖子具体解释发生了什么。你也可以在我们的博文、由世界顶尖数学家撰写的配套论文（今天晚些时候将发表在arXiv上）、原始的AI证明报告以及模型解决该问题的（重写版）推理链中找到不同复杂程度的解释。

那么，我们在讨论什么呢？这个问题简单得令人难以置信：如果我在平面上放置n个点，这些点之间有多少距离可以相等？（通过缩放，你也可以问有多少距离可以等于1，因此得名“单位距离”问题）。当然，你可以把一个点放在圆心，把所有其他点放在以该点为圆心的圆上，这样就会有n-1个距离相等。显然，最多有n^2/2个距离。那么真相是什么？最优结果是n阶还是n^2阶？

当Erdős在1946年提出这个问题时，他分析了这个问题最自然的构造：将点放在一个简单的网格上。现在，一个点在这个网格上有4个邻居，因此至少大约有2n个距离相等（是2n而不是4n，因为重复计数）。但让我们稍微聪明一点：与其看距离为1的点（假设网格的边长为单位长度），不如看距离为sqrt(5) = sqrt(1+2^2)的点。画个图你就会发现，有8个点在那个距离上！实际上，你基本上是沿着L形移动，可以任意方向（有8种方式）。Erdős证明的是（我将在下面给出证明）：你可以继续这样，按2的幂次增长，直到大约u(n) = 2^{log(n)/loglog(n)}。这意味着网格至少有大约u(n)*n个相等距离，而且实际上这个计算对于网格来说是最优的。注意，u(n)*n = n^{1+o(1)}（具体来说是n^{1+cst/loglog(n)}）。

Erdős猜想的是，网格基本上是最优的：任何点集配置最多有n^{1+o(1}}个相等距离。这就是过去80年来毫无进展的问题，尽管由于这个问题的基础性和自然性而备受关注。我的理解是，Erdős坚信网格是最优的，事实上，在密切相关的问题（同一篇1946年论文中提出的！）——不同距离问题——中，他得到了证实。不同距离问题只是这个问题的反面，问的是n个点最多能形成多少种不同的距离？网格给出了n/sqrt(log(n))种不同距离，而10年前Guth和Katz的一篇突破性论文表明，这基本上是最优的，下界为n/log(n)。换句话说：一切都表明网格也是单位距离问题的最优候选。

这就是OpenAI内部模型介入的地方。它实际上强烈否定了这个长期以来的信念，并发现了一个令人震惊的新构造，其相等距离的数量达到n^{1+delta}阶，其中delta>0。要简单说说这个突破是如何由模型实现的，我首先需要告诉你更多关于Erdős的证明，以及2^{log(n)/loglog(n)}从何而来。原来素数在其中潜伏着！

我们假设关于素数的两件事：第一，素数定理说小于n的素数大约有n/log(n)个（实际上我们需要一个稍微精细的版本，但对这个解释的层次来说没关系）。第二，如果素数等于1模4，那么它在高斯整数（即a+ib形式的整数，其中a和b是整数）中可以分解为p = z * conj(z)。例如，5=(1+2i)(1-2i)，这应该让你想起上面我们数出8个点距离为sqrt(5) = sqrt(1+2^2)的情况。好了，现在取前k个等于1模4的素数，p_1, …, p_k，并考虑数R = p_1…p_k = z_1 * conj(z_1) * … * z_k * conj(z_k)。关键点是，我们从中得到2^k个高斯整数，其模等于sqrt(R)，方法是对于每个素数p_i，要么取z_i，要么取conj(z_i)，然后取它们的乘积（关键是，我们利用模的乘积性，且共轭保持模不变）。换句话说，我们在网格上找到了2^k个点，它们到原点的距离为sqrt(R)！（准确地说，我们还需要证明这些点是不同的，这时Z[i]中的唯一分解性质变得重要，而且在新证明中也将是关键，但这里我们先忽略这个问题。）现在，我们只需要看看在保持sqrt(R) < sqrt(n)（后者是包含n个点的网格的边长）的情况下，k能取多大。我们有log(R) = sum_{i=1}^k log(p_i)，根据素数定理，这大约等于sum_{i=1}^k log(ilog(i))，基本上就是klog(k)。所以我们需要k*log(k)小于log(n)，因此k应该大约为log(n)/loglog(n)，于是得到所声称的2^k = 2^{log(n)/loglog(n)}。

上面这段仅仅一段的论证（我得承认这是聪明的论证）保持了80年的最优水平。现在，AI所做的在我看来相当疯狂。首先，从推理链中可以看出，它几乎立即决定尝试改进网格构造，这与大多数数学家迄今为止所尝试的方向相反。根据我有限的理解，它最终得出的策略（并且完美执行了）大致如下：如果能有更多拆分素数的方式，那不是很好吗？也许如果我们考虑另一个域，而不是Q，一个更高次数的域，那么用该域整数环代替整数Z，这可能会奏效？也许不是2^k，而是2^{f k}，其中f是域的次数？第一个猜测是看分圆扩张，但模型在其推理链中首先尝试了这个，并很快意识到这行不通。它继续努力，最终引入了理想的语言，在那里，非唯一分解可以由类群处理。现在你需要开始思考如何构造高次域，同时控制所有参数（首先是类数，而且这将是一个高维格，所以需要投影回复平面，而投影会引发一些坍缩，需要控制，等等）。这就是模型使用类域论中的重锤——Golod-Shafarevich无穷塔的所在。此时，你最好去查阅实际专家们撰写的配套论文，以了解进一步细节！

好了，让我退后一步：基本上，AI所做的是，利用其广博的数学知识，看到了离散几何与代数数论之间的联系，然后关键的是，它能够巧妙地串联起论证，每一步都有专家级的计算。这确实是一个突破性的结果，但同时，模型并没有“发明”任何“新数学”（比如，它没有发明某种替代的类域论，不管那意味着什么）。但关键点在于：仅仅能够深入了解某个科学领域的所有结果，并且能够熟练地使用所有已知论证，以恰到好处的参数选择来应用，这本身就足以带来大量突破，而这不仅仅限于数学，这种（极其）扎实的专家级执行是许多许多科学进步的基石。

最后，谈谈这对未来数学的意义。配套论文中有许多顶尖数学家对此的反思，所以最好直接去读他们写的内容。但有一件有趣的事情需要注意：我们并没有将模型的证明提交到arXiv。确实，没有任何人类作者能以传统意义上声称做出了贡献（尽管这当然是OpenAI所有人类研究人员创造这个惊人模型的成果，也是人类数千年来发展数学的成果……）。另一方面，由人类撰写的配套论文不仅仅是对这一时刻重要性的反思，它还消化了证明，将其置于更广泛的背景中，甚至做了些许简化。尽管社区还有很多工作要做，以完全适应这些新发展，但我们相信，将AI证明与人类对其理解相分离的这一原则，将是拼图中的重要一块。