给空间涂色需要几种颜色？对于“典型”的尺子，不超过2d种

取一个平面上的每个点，并给每个点涂上一种颜色。规则只有一条：距离恰好为一个单位的两个点绝不能同色。最少需要多少种颜色？

这就是Hadwiger–Nelson问题，可追溯到1950年，用作者的话说，它是离散几何中最著名的未解难题之一。长期以来，人们只知道答案在4到7之间。最近的一项突破将下界提高到了5。确切答案至今仍是未知数。

换一把尺子

距离不一定非要用普通的尺子来量。数学家定义了许多其他的范数——度量长度的方式——每种范数都由它的“单位球”来描述，即与中心距离不超过1的所有点构成的集合。对于通常的距离，它是一个圆球；对于其他范数，它可以是任何关于中心对称的凸形状。

对于平面上的任何范数，这道染色难题的答案都在4到7之间。在d维空间中，对任何范数而言，答案至多是d的指数量级；而对于许多自然的范数——包括通常的欧几里得范数——它也至少是指数量级的：颜色数量随维度增长而急剧膨胀。

这种膨胀是普遍规律吗？Noga Alon（普林斯顿大学和特拉维夫大学）、Matija Bucić（维也纳大学）和James Davies（莱比锡大学）研究了典型范数。“随机”选取一个范数并没有自然的方法，因此他们采用了一个拓扑学概念：如果例外情况构成一个可忽略的（“贫乏”的）集合，那么就说某个性质对典型范数成立。Alon、Bucić和Lisa Sauermann此前的工作已经证明，典型范数至多需要2ᵈ种颜色，并提出了这个界与真实答案有多接近的问题。

线性，而非指数

答案是：相差甚远。这篇新论文证明了：

• 对于d维空间上的典型范数，2d种颜色总是够用；
• 这已是最佳结果：存在一个开的范数集合，至少需要2d种颜色。因此有些范数恰好需要2d种。

在十维空间中，典型范数至多需要二十种颜色，而通常的距离所需的颜色数则呈指数增长。据作者介绍，这也是首次在任意维度d下，为一个“严格凸”范数精确确定染色数。

下界的证明用了一个巧妙的陷阱。找出2d个点，它们彼此之间的距离都恰好是一个单位，只有两个点a和b例外，它们相距半个单位。再加上整个构型关于a的镜像。如果颜色少于2d种，b和它的镜像都将被迫取a的颜色——但它们相距恰好一个单位。矛盾。一个稳定性引理表明，这个构型在范数发生任何微小变化时都依然成立。

高维中的孤独跑者

上界的证明根据每个点经过精心选择的投影落在何处来给它涂色，切片宽度为1/(2d)。要让这一方法奏效，需要一个关键要素，作者将其描述为著名的孤独跑者猜想（lonely runner conjecture）的高维矩阵版本：

对x取上确界的 minᵢ ‖aᵢ · x − bᵢ‖ ≥ k / (2n)

其中‖t‖表示t到最近整数的距离，适用于k维空间中任意n个向量aᵢ，只要其中任意k个线性无关。这一命题还解决了I. J. Schoenberg于1978年提出的一个关于“视线遮挡”的猜想——该问题是：周期性排列的板块要多厚，才能挡住所有通向无穷远的视线——作者称之为该领域最经典的未解难题之一；它还解决了Henze和Malikiosis提出的一个相关猜想。

致谢中的机器

作者说得很明确：“经过长时间的讨论，ChatGPT 6 Pro为我们提供了定理1证明中所需的最后一个要素的证明，即引理7的证明”，在讨论中，他们分享了自己的观察——包括归纳的想法和总体策略。“下界的论证也是在ChatGPT 6 Pro的协助下找到的。”

问题依然存在。精确值2d是在一个开的范数集合上证明的，而不是对所有典型范数。至于普通的欧几里得距离，作者预计在每个维度上都需要严格多于2d种颜色——这在2、4、7、8维以及9维及以上已经得到证实，但在3、5和6维仍是未解之谜。