匈牙利 Rényi 雷尼研究所的研究人员证实了保罗·埃尔德什 50 多年前的平面着色猜想

luyuanhong

匈牙利 Rényi 雷尼研究所的研究人员证实了 Paul Erdos 保罗·埃尔德什 50 多年前的平面着色猜想

来源：zzllrr小乐



译者注：

本文由两篇文章构成，分别译自雷尼研究所（Alfréd Rényi Institute of Mathematics）[6]、量子杂志（Quanta Magazine）[1]，其中主涉数学家为BME布达佩斯技术与经济大学教授马泰·马托尔西（Máté Matolcsi）。

马托尔西正好也是今年首届国际基础科学大会 ICBS（北京，2023-7-20，参见[3]）科学前沿奖数学部分——组合数学、离散几何和图论的获奖者之一。

其获奖论文为《凸域的 Fuglede 猜想在所有维度上都是正确的》，Acta Mathematica（2022）（与巴伊兰大学 Nir Lev 合作）。

马泰·马托尔西教授，也于当天大会发表了有关 Fuglede 凸体（convex body）猜想的专题报告演讲（参见[4]）

一、《雷尼研究所的研究人员证实了保罗·埃尔德什 50 多年前的猜想》

作者：Márta Szomolányi ，雷尼数学研究所，2023-8-1



匈牙利阿尔弗雷德·雷尼数学研究所（Alfréd Rényi Institute of Mathematics）的研究人员成功地证实了一个半个多世纪以来一直悬而未决的几何猜想。这个问题需要 ELKH Rényi 研究所分析、几何和人工智能部门的研究人员的合作：证明结合了几何、傅里叶分析、线性规划、图论和计算机科学的方法。7 月，国际公认的科普标杆《量子杂志》也报道了这一结果[1]。

平面上有多大比例的地方可以着色，并使得两个着色点彼此间的距离不能恰好是单位距离？这个几何问题是由 Leo Moser（利奥·莫泽，1921 - 1970）在 1960 年代初提出的。根据 Paul Erdos（保罗·埃尔德什，1913 - 1996）的猜想，这个分数必须小于 1/4 。目前最好的下界是 0.2293 ，由可追溯到 1967 年的 Hallard Croft（哈拉德·克罗夫特）的构造给出。一些研究小组已经发表了关于这个问题的部分结果，在过去 60 年中逐渐加强了 0.2857 至 0.2544 的初始密度上限估计。Gergely Ambrus（塞格德大学和雷尼研究所）、Adrián Csiszárik（雷尼研究所和 Eotvos Loránd 大学）、Máté Matolcsi（马泰·马托尔西，BME大学和雷尼研究所）、Dániel Varga（丹尼尔·瓦尔加，雷尼研究所）和 Pál Zsámboki（雷尼研究所）的新结果表明，所讨论的密度不能超过 0.247 。他们的论文被著名的 D 1级期刊《数学规划》（Mathematical Programming）接受。

几十年来，这个猜想一直被各种方法攻击。Ambrus 和 Matolcsi 以前使用的方法建立在 F. Vallentin 和 F. M. Oliveira Filho 的工作基础上，并使用傅里叶分析将原始离散几何问题转换为线性规划问题。这种方法使他们能够证明以前已知的最强估计，但 Erdos 推测的 0.25 下界似乎还有很长的路要走。

基于Dániel Varga的想法，在证明猜想的第一个突破中，研究人员对以前的理论方法进行了共同的推广。这有助于他们将问题简化为搜索任务：为了证明 Erdos 的猜想，在平面上找到一组具有特定属性的点就足够了。所需的属性过于复杂，因此无法使用纸和铅笔找到相应的点集。因此，研究人员采用了人工智能方法。为此，使用了由匈牙利人工智能国家实验室（MILAB）提供给 Rényi 研究所的高性能计算机集群。经过几个月的密集实验和一周的运行，计算机集群终于找到了一个具有所需属性的 23 点集合，Erdos 的猜想得到了解决 [2]。

研究人员继续在机构之间和数学学科之间成功合作，旨在解决与平面着色相关的更多问题。

二、《数学家解决了长期存在的着色问题》

作者：Anna Kramer ，量子杂志特约撰稿人，2023-7-19



多年来，一个简单的问题一直困扰着布达佩斯技术与经济大学教授马泰·马托尔西（Máté Matolcsi）。在确保没有两个着色点正好相距一个单位的距离的情况下，你可以在无限平面上涂多大区域？

这个问题最早是由加拿大数学家利奥·莫泽（Leo Moser）在 1960 年代初提出的。1967 年，剑桥大学的哈拉德·克罗夫特（Hallard Croft）提出了一种似乎做得很好的构造。他的形状，现在被称为“克罗夫特的乌龟”（Croft's tortoise），看起来像一个圆圈，与六边形的饼干切割器相交。每只乌龟内部的每一点与同一只乌龟内的任何其他点的距离都小于一个单位，与相邻乌龟的最近点相距超过一个单位。

在那之后的半个世纪里，没有人能够找到一种形状，可以改进覆盖 22.936% 的平面。但是，在理论上可能存在这种形状吗？1984 年，匈牙利数学家拉斯洛·塞克利（László Székely）证明，不可能找到覆盖平面 27.91% 以上的形状。第二年，多产的猜想家（也是匈牙利同胞）保罗·埃尔德什（Paul Erdos）说，他认为上限不到 25% 。与许多埃尔德什猜想一样，多年来它吸引了许多雄心勃勃的数学家的注意。

Matolcsi 在 2010 年代初开始解决这个问题。他正在从事傅里叶分析——将三角学中的正弦函数加在一起来表示更复杂的函数——并认为这些技术可以用来证明埃尔德什的猜想。

“我做不到，”他说。“我们非常接近 25% ，但并不低于 25% 。我有点失望；我们为此付出了很多努力。我在匈牙利科学院做过博士答辩，我对委员会说，'看，我甚至不确定这是否正确。我们为此付出了很多努力，这个血腥的数字不会低于 25 ’。”

他花了将近十年的时间来证明自己是错的。

乌龟，一根头发

已知最密集的避免单位距离的密铺（unit-distance-avoiding tiling）由 Hallard Croft 于 1967 年发现，几乎覆盖了平面的 23%，其中没有两个褐红色点恰好相距一个单位（参见下图）。

下图每个瓷砖瓦片（即乌龟）都是通过正六边形和圆（不包括圆的边缘）相交形成的。



其他数学家继续削减这个数字。到 2010 年，现在在科隆大学的弗兰克·瓦伦廷（Frank Vallentin）和现在在代尔夫特理工大学（Delft University of Technology）的费尔南多·奥利维拉（Fernando Oliveira）将这一界限推到了 27% 以下。Matolcsi 也坚持了下来，2014 年，他和同事们一起达到 26% 。到 2018 年，他与 Gergely Ambrus 一起将界限降至 25.442% ，非常接近 Erdos 的猜测—— 25% 。

然后他放弃了。

在 2018 年的论文发表后，Matolcsi 回忆道：“我说，‘我再也不会碰这个问题了。因为它根本行不通。’我做了我能做的。”

事实证明他没有。在一些研究人员在生日派对上找到他后，Matolcsi 同意最后一次尝试解决这个问题。阿尔弗雷德·雷尼数学研究所（Alfréd Rényi Institute of Mathematics）的丹尼尔·瓦尔加（Dániel Varga）、阿德里安·西萨里克（Adrián Csiszárik）和帕尔·兹萨姆博基（Pál Zsámboki）认为，像 AlphaGo 和 AlphaFold 这样的机器学习模型可以帮助识别解决问题所需的复杂点集。

自 1984 年的结果以来，一种被证明为卓有成效的技术是使用一种称为自相关函数（autocorrelation function）的东西来观察候选点集与自身移动副本的重叠量。对于给定的移动（例如，向上一个单位和向右一个单位），该函数给出一个数字，该数字是重叠大小的度量。如果一个集合是“避免单位距离”的（unit-distance-avoiding），那么每当它向任何方向移动一个单位时，它的自相关函数都将为零。

Matolcsi 、Ambrus 和他们的新合作者研究了该函数的傅里叶变换，将其转化为巨大的正弦波总和。所有单位长度偏移的函数均为零的要求限制了傅里叶和元素的可能值。他们想出了如何将这一需求表示为线性优化问题的方法，并建立在 Vallentin 和 Oliveira 设计的技术之上。

“我们必须找到一组具有非常微妙、非常罕见的特性的点，我们不知道该怎么做。因此，我们要求计算机搜索这些对象，” Varga 说。

这个过程比他们预期的要简单得多。虽然 Varga 和 Csiszárik 尝试了更复杂的人工智能模型来试图识别这些点——并且比他们预期的更困难——但 Zsámboki 却使用了 1980 年代开发的旧搜索策略。

“非常奇怪的是，高级的东西效果不佳。我决定使用较旧的方法，”Zsámboki说，“而这恰好效果更好。”（Zsámboki 补充说，Varga 建议使用一种称为树搜索 tree search 的特殊技术。）

一旦他们确定了要使用的算法，他们就有一个大问题需要解决：有 6099 个约束条件的 25552 个变量。他们在 128 个 CPU 上进行了一周的搜索。在周末，他们得到了结果。

2022 年 10 月，该团队发布了一篇论文[2] https://arxiv.org/abs/2207.14179 ，显示没有单位距离点对的情况下，可以给不超过 24.7% 的平面着色，最终打破了 Erdos 的界限。

“我不得不说，这真的是一个非常令人满意的时刻，”Matolcsi 说。“这是一个非常整洁和漂亮的结果。”

“我很高兴他们现在做到了，因为我曾认为，以目前的计算机能力，低于 25% 是不可能的，”Vallentin 说。

尽管如此，没有人能想出比克罗夫特 1967 年的更完整的着色，它覆盖了不到 23% 的平面。但是，几位作者现在并没有试图继续降低乌龟的上限，而是专注于一个相关的问题：弄清楚需要多少种颜色才能完全覆盖平面，同时确保每种颜色都避免单位距离。

这个数字称为平面的染色数（chromatic number of the plane）。



2018 年，业余数学家（和长寿布道者，因为他曾声称：现在人类可以活到 1000 岁，zzllrr小乐译注）奥布里·德·格雷 （Aubrey de Grey） 证明[5]它必须至少为 5 。已知它小于或等于 7 。这篇新论文暗示，使用与 de Grey 不同的方法，至少需要 5 种颜色。“我们能证明它至少是 6 吗？”Ambrus 问道。“这是可能有机会的事情。我们现在正在研究它，我们的方法可能有机会。”

原创 Rényi 研究所等 zzllrr小乐 2023-10-30 14:55 发表于江苏