一个硬币解决不了的问题

1947年, 由数学家Erdős抛出一枚硬币, 通过为完全图的每条边按照随机的方式, 分别涂上红色或者蓝色，借此开创了概率组合学。运用这个简单的方法能够证明, 在任何一个足够大的社交网络当中, 必定存在着一群人, 他们要么全部互相认识要么全都互不认识。然而, 他也留下了一个极限, 也就是这个“足够大”的下界底数, 在之后将近80年的时间里, 没有人能够对其进行改动。

下界底数卡在黄金比例

以近对角线数r(k, 2k)为例, Erdős的硬币方法给出一个经典结果, 当红色团和蓝色团大小相差一倍时, 下界底数恰好是黄金比例(1+√5)/2≈1.618。这个数字像一座大山，在组合数学领域压了整整80年。在这期间, 上界一直在进步, 到2023年从≈4压到了3.7992, 然而下界的底数却纹丝不动。

球面给随机性加了结构

在2024年的那个春天, 来自清华的00后博士生申武杰, 读到了一篇和数相关的论文, 然后被深深吸引住了。他紧接着就思考, 可不可以给随机性添加几何方面的内容呢? 随后他提出了“随机球图”这样一个模型, 也就是把n个节点随机地散布在高维球面上, 对于两点距离远的边涂上红色, 而两点距离近的边则涂上蓝色。高维球面存在着一个违背直觉的特性, 那就是一旦维度变高, 几乎所有的点都会挤在赤道附近, 点对间的距离集中在一个非常窄的区间里, 其着色被球面的几何对称性精准调控, 不再是完全随机的了。

收益盖过了代价

具有这样一个权衡的是这个新模型, 若要产生大的红色团, 就得有诸多节点相互之间都距离甚远, 然而球面空间存在限制使得这种情况很难出现, 意想不到的却是蓝色团的概率反倒提高了。马杰、申武杰、谢晟捷这三个人在小规模图上开展了验证工作, 在数以万计的着色方案当中, 无团着色的概率始终大于零。关键之处恰好源自高维球面那些极其违背直觉的几何性质, 收益的确超过了代价。

改进量只有小数点后20个零

最终, 他们将底数从1.618提升到了(1 + √5)/2加上10⁻²¹ , 改进量大概是10⁻²¹ , 即小数点后有20个零, 接着是一个1。然而, 数呈指数增长, 哪怕底数仅加0. , 当k趋向于无穷时, 新下界会把旧下界甩至宇宙尽头。这是自Erdős以来在该方向的首个指数级改进, 也是首次有人给出一条超越硬币的路径。不过, 这条路径存在边界, 仅在蓝色团大于红色团时发挥作用, 对角线情形下收益会消失。

三个人花了一年写满40页

2000年出生的申武杰, 高中阶段获得过CMO三等奖, 于2018年考入北大数院, 本科时拿到全国大学生数学竞赛一等奖。2024年秋天, 他将想法告知到清华访问授课的马杰, 马杰的学生谢晟捷也一同加入。三个人耗费一年时间, 经过40页密集的计算才达成证明。马杰后来讲道: “我们颇具幸运之感, 好似所有努力均获得了回报。”。2025年7月, 论文被挂到arXiv上, 组合数学方面的泰斗Gil Kalai特意发布博文予以称赞, 声称这套模型“具备相当的独立研究价值”。

你认为AI往后能够独自达成这般需要原创剖析的数学进展吗, 欢迎于评论区去分享你的观点, 点赞转发以使更多人瞧见中国数学家的进展。