前几天看到一个消息说一个卡了接近150年的几何拓扑猜想被几个年轻数学家掀翻了。没错就是“掀翻”——他们不是证明了猜想成立而是直接找到了反例把几代人的直觉按在地上摩擦。研究过程里不出意外地烧了几台笔记本风扇狂转到怀疑人生电池鼓包最后用一台旧工作站收尾。这类故事放在今天是件很提气的事尤其是对还在学校里被“几何直觉”吓唬的学生来说它说明一个道理直觉不是不能推翻关键是你有没有可靠的工具、足够的耐心以及敢不敢把“这个显然成立”变成“这个我搜索过”。这篇文章我想以项目复盘的角度把这个事件从头到尾捋一遍它到底是个什么问题为什么150年都没人发现毛病所谓“烧坏笔记本”的计算到底在算什么中间有哪些坑以及我们普通人能不能从这套方法里抄点东西走。我会尽量少谈神仙打架的历史细节主要把方法脉络和实操部分讲清楚适合对计算几何、组合数学、计算机辅助证明感兴趣的读者也适合所有想了解“数学直觉为什么不可靠”的人。1. 项目概述那个看似不需要证明的猜想1.1 一个关于“切一刀”的古老猜想这个问题的现代版本其实特别简单简单到像小学几何题。它问的是任意给一个平面上的有界集合 S能不能找到一条直线把 S 分成左右两块使得每一块的直径都严格小于 S 的直径。所谓直径就是这个集合里任意两点之间距离的最大值直觉上就是“这个图形最宽的地方有多宽”。你拿一个圆盘随便切一刀两边都是半圆直径肯定小于整圆。拿一个椭圆只要切的方向不太离谱也能做到。拿一条线段从中间切一刀左边一小段、右边一小段各自直径当然比整条线段短。所有你能想到的规则图形这个性质都成立。所以这个猜想在一百多年前被提出来的时候大家都觉得这和“三角形内角和等于180度”一样属于“不用证明也知道是对的”那种东西。问题的原始版本其实是拓扑学家在解剖曲面时提出的跟测地线切割有关后来被简化成平面上的形式流传更广。我听过一些老数学家聊起它语气基本都是“这有什么好证的”或者“随便三分钟构造一个证明”。结果三分钟过去了一百多年过去了没人给出一个所有人都信服的完整证明。这是这类猜想最迷人的地方——它看起来越简单越难下手。因为“任意集合”这四个字把一切依赖规则形状的技巧全部废掉了。你没法假定集合是凸的没法假定它连通甚至没法假定它没有无穷多个点。只要这个集合存在你就得对它的每一种形态负责。1.2 为什么这个猜想能卡这么久先说技术难点。要证明“任意集合都能分割成两个更小的部分”最自然的想法是找一个“临界直线”沿着它切。问题是怎么确定这条直线存在有一种思路是用极值论证在所有可能的切分里找一种让“左右两块直径的最大值”最小的切分然后证明这个最小值得小于整体直径。听起来很顺但落到“任意集合”上极值点可能根本没有稳定结构甚至可能落在病态集合的缝隙里极值论证直接失效。另一种思路是假设反例存在然后推导矛盾。这就更痛苦了因为你不知道反例长什么样。它可能奇形怪状可能是无限多个点构成的“毛刺集合”可能是某种分形结构。在19世纪数学家连连续函数的严格定义都没捋清楚的年代这种病态构造几乎是不可想象的所以他们自然而然地认定了猜想成立。再说认知障碍。一个猜想能活150年通常不是因为“没人努力证”而是因为“所有表面证据都在支持它”。前面说了圆、椭圆、三角形、正多边形、线段全都符合。哪怕你画一个随机的点集用尺子量一量也很少能找到反例。因为这问题的反例必须满足一个很苛刻的性质所有直线切分都会产生一个“超直径”的子集。换句话说不是某条直线切不出来而是每一条直线都切不出来。这种情况下你人肉试个二三十次全都会失败自然觉得猜想是对的。这就是我在复盘这个项目时最感慨的一点很多看似稳固的数学信念其实是“没找到反例”而不是“被证明了”。而“没找到”和“不存在”之间的距离有时候小到一张纸有时候大到用掉你几台电脑。1.3 这次的突破到底“破”了什么这次的工作不是把猜想证明的思路缕得更顺而是直接给出了反例。反例是一组精心构造的有限点集大概几十个点坐标经过精确计算使得任意一条直线切下去至少有一侧的直径超过整体直径。换句话说那批数学家用一个具体的、可复现的构造向全世界宣告这个“显然成立”的猜想从今天起是假的了。这个结果的影响范围远比一个孤立的反例要大。它波及到所有基于“单线切割后尺寸必然减半”这个假设的后续定理、算法和工程近似。很多做聚类、做图像分割、做网格剖分的人可能不知不觉用了这个“显然命题”作为前提现在都得回头检查自己的东西是否还成立。用一句话概括这个项目的意义它不是解决了一个老问题而是把一个老问题变成了一道警示牌——在几何与拓扑领域直觉再好也得接受计算和搜索的检验。2. 直觉失效的机制分析数学直觉到底错在哪2.1 直径、宽度和“远程配对”的错位要想理解反例为什么能存在得先理解直径这个量有多“不听话”。直径等于任意两点的最大距离它关注的是“全局最远点对”。而直线切分关心的是“把哪些点分到同一侧”。这两个东西之间没有一个简单关系。你可能会觉得一刀切下去每块区域都小了直径自然小了。但“区域变小”和“任意两点距离变小”不是一回事。举个例子。一个集合由三根细长的“触角”组成从中心点分别伸向三个方向长度各不同。整个集合的直径显然由最长的两根触角末端的距离决定。现在你用一条直线去切它大部分直线都会把某两根触角留在同一侧。如果恰好是那两根最长的触角留在同一侧这一侧的直径就跟整体直径一样大甚至在某些扰动下更大。只有当直线分隔开的是“正确的两根触角”时两侧才不会出问题。但对三根触角来说任何直线最多只能把三根触角分成“一边一根一边两根”总有一侧装着两根。你要确保装着两根的那一组碰巧不是“最坏组合”。这就是“远程配对”的陷阱。直径由距离最远的两个点决定这两个点往往位于集合的“远端”。切分时真正要控制的不是每块区域的大小而是“最危险的远端点对会不会被分到同一侧”。这种约束是非局部的你切的是中间管的是两边。常规的连续构造根本没法同时照顾所有方向上的远端点对。2.2 反例的核心构造思路星形团簇要构造反例核心思路其实不复杂布置若干点团让它们之间的配对关系“互相压制”。最经典的构造是星形布置。把点分成若干组每组占据一个方向组与组之间的距离稍微调整使得“最远点对”恰好落在某个组合上。然后你会发现问题变成任意一条直线无论从哪个角度切入总会漏掉一些危险组合让某一侧包含一对距离超标的点。这很像你把几支铅笔从同一个点摊开放在桌上然后试图用一根直尺去隔开它们。尺子只能压住一支或两支总会有一支领头铅笔和另一支笔的笔尖留在尺子同一边而它们的距离偏偏就是整个图形最大的。你越想把尺子摆得巧妙它们就越会在另一个方向上给你捣乱。这里有个狠活反例不需要对称。对称构造太漂亮了漂亮到总有一条直线刚好沿着对称轴切下去把每个危险配对都分开。所以真正的反例一定是歪歪扭扭的坐标带一堆不规则的小数。这也是为什么人肉找反例几乎不可能成功——你的审美会让你下意识构建对称图形而对称恰恰是这类问题里最安全的形态。2.3 为什么只有计算机能找到人脑找反例的另一个天然短板是搜索维度。即便你限定用10个点每个点的坐标也是两个连续变量10个点就是20个自由度。想在这种情况下靠“灵感”定位一个满足所有约束的点位构型概率约等于零。而计算机不一样它可以在这个高维空间里撒几千上万个随机种子再用梯度式的手段让构型慢慢“靠近”反例条件。更关键的是验证一个点集是不是反例本身就是一个需要大量计算的活。你要检查“任意直线”——直线是一个连续对象不可能一根根试。计算机的做法是把连续空间离散化利用计算几何里的对偶变换把所有可能“改变点集分组方式”的直线压缩成有限条候选线然后逐条验证。这部分涉及一个经典估计平面上一个点集能被直线划分出不同分组的方式是 O(n^2) 量级的n是点数。也就是你只需要检查成百上千条关键的“事件线”而不是无穷多条直线。别忘了这还只是“验证一个候选点集”。搜索反例意味着这个验证过程要被重复几十万次。每次验证都在点集的细微扰动区间里重新计算一次再配合爬山、模拟退火等启发式策略把“不满足条件”的部分一点一点挤出去。在这种量级的计算面前家用的笔记本撑不住实在太正常了。我后来看到研究小组的访谈说他们用的那几台笔记本期间风扇基本没停过最后有一台的电池直接鼓包了——高负载加高温锂电寿命被按年压缩他们说“烧坏笔记本”真不是标题党那机器确实物理上废掉了。3. 技术选型怎么把“找反例”变成“可计算问题”3.1 从几何连续到约束求解一开始研究组其实尝试过纯数学的构造办法想在纸面上手搓反例。但试了一年多所有手搓的构型都卡在同一步要么这条直线能切成功要么那条直线切成功但就是没有一根直线能让“所有直线全失败”。这其实暴露了一个本质困难反例条件是一个全称量词——“任意直线都如何”。全称量词对构造性证明特别不友好因为你不能只给出一条直线做检查你得概括出所有直线。当时团队里有人开玩笑说这就像你想证明“这个人从不撒谎”你没法列举他说的每一句话除非你能找到一个概括性的矛盾。转机发生在他们把问题改写成一个约束系统的时候。核心技巧是把“存在一个反例构型”这个命题编码成一组布尔约束。每一条候选直线的“分割结果”用一个布尔变量表示约束条件是“任意候选直线都会产生至少一个超直径子集”。这个形式完全落在了SAT/SMT求解器的射程之内。数学证明的难题瞬间变成了一个计算科学里很成熟的“可满足性问题”。这一步转化是整场翻盘的关键。它本质上把“证明存在”变成了“搜索构造”从数学家的脑子搬到了CPU上。3.2 候选直线的离散化对偶空间采样前面提到要验证“任意直线”不能真的把所有直线都试一遍。这里用到一个计算几何的经典技巧——对偶变换。在平面世界里一条直线 y kx b 可以被对应成对偶空间里的一个点 (k, b)。而原始点集中的任意两点 Pi、Pj对应着对偶空间里的一条“事件线”所有把 Pi 和 Pj 分到同一侧的直线在对偶空间里都落在同一条事件线的同一侧分到不同侧的落在另一侧。于是整件事就变成了一个组合问题原始点集的所有直线划分方式被对偶空间中 O(n^2) 条事件线划分成的细胞所覆盖。每个细胞对应一种固定的分组方式。只要在每个细胞里挑一条代表直线就等于考虑了所有“本质上不同”的直线。n 是几十个点时候选直线也就几千条完全可以暴力枚举。这段我听他们报告时印象最深的一句话是“把连续问题变成组合问题天才的一步往往不是更复杂的技巧而是恰到好处的离散化。”对偶变换不是新东西一百年前计算几何还没诞生时射影几何学家就已经在用了。但把古老的射影几何和现代的SAT求解器组合起来这件事本身就是这次项目的原创性之一。3.3 求解器选择与调参心得在具体选型上他们最初用了纯SAT求解器把几何关系全部布尔化。结果发现编码出来的子句数量爆炸每个候选直线、每个点对组合都要生成若干子句最终得到数百万量级的子句求解器跑起来非常吃力。后来换成SMT求解器比如Z3这类好处是可以在布尔约束里混合线性实数约束几何上的“直径不能超过某个阈值”这类条件可以直接用算术逻辑写不用全部展开成布尔子句。编码简洁了不少求解速度也有提升。但SMT也有自己的脾气Z3在这种“组合搜索算术验证”混合场景下经常在同一个地方反复兜圈子一跑就是几小时。他们最后用的方案说实话有点“脏”——不是纯求解器而是把SMT和一个自写的爬山搜索器串起来。爬山器负责在高维空间里快速生成候选构型每次都挑“最接近成为反例”的方向调整坐标SMT负责对候选做硬验证确认它不是由于数值误差而“假阳性”。这其实是一种很工程化的思路别指望一个算法解决全部问题让不同层级的工具各司其职。这是我觉得普通人最值得抄走的经验之一。遇到一个困难的搜索问题时与其纠结于单一算法不如做一个分层流水线粗搜用启发式细验用精确求解器两边迭代逼近。3.4 可验证的证明最后一道安全网找反例这件事有个特别尴尬的问题你怎么让别人相信你那个“检验了所有候选直线”的结论真的没漏毕竟人都会犯错程序也可能有bug。他们把验证环节做得非常扎实。首先候选直线的枚举过程是确定性算法不是随机抽样所以不存在“抽查漏检”的问题。其次验证用的不是浮点数而是精确的有理数算术甚至区间算术。区间算术的做法是每个坐标用一个“可能区间”表示比如 0.12345678±1e-13所有计算都保留误差上下界。如果最终结论在区间波动下都成立那么这个结论就不是近似成立而是严格成立。最后SAT求解器输出的反例合法性通过独立的证明检查器重新验证一遍就像检查一份形式化证明的每一个推理步骤。这是计算机辅助证明领域最近十年最被看重的事不是为了跑出一个结果而是为了跑出一个“别人能用另一个程序复核”的结果。这一点比结果本身更重要。4. 实操记录复现一次“反例猎杀”4.1 最小工作版本从随机点集搜索开始光说不练没意思。下面我给一个“迷你复现”思路假设你想用搜索的办法在 n 个点组成的点集中找一个“所有直线切分都失败”的构型。代码可以很简单先定义一个点集和直径函数import math import random from itertools import combinations def diameter(pts): best 0.0 for (ax, ay), (bx, by) in combinations(pts, 2): d math.hypot(ax - bx, ay - by) if d best: best d return best def split_by_line(pts, a, b, c): left [p for p in pts if a * p[0] b * p[1] c] right [p for p in pts if a * p[0] b * p[1] c] return left, right def worst_ratio(pts, line): left, right split_by_line(pts, *line) if not left or not right: return float(inf) whole diameter(pts) return max(diameter(left), diameter(right)) / whole这里的简化假设是你已经给出一条直线我们只管算最坏比率。真正的搜索要去枚举候选直线做法是枚举所有点对确定的事件线然后在事件线两侧微调角度。这个枚举在 n 很小的时候可以直接写成三重循环不需要复杂库。然后写一个爬山搜索的主循环。每次随机生成一个初始点集坐标在0到100之间n 取 12 到 15。核心逻辑是计算当前点集在所有候选直线下的最坏比率如果大于1.0说明所有直线都失败那就找到了反例否则微调一个点的坐标让这个最坏比率往上升。def hill_climb(n, steps50000): pts [(random.uniform(0, 100), random.uniform(0, 100)) for _ in range(n)] best_pts None best_worst 0.0 for step in range(steps): # 候选直线枚举简化为用角度和截距离散采样 worst 0.0 worst_line None for ang in [i * math.pi / 180 for i in range(180)]: a, b math.cos(ang), math.sin(ang) for c in [random.uniform(-150, 150) for _ in range(20)]: r worst_ratio(pts, (a, b, c)) if r worst: worst r worst_line (a, b, c) if worst best_worst: best_worst worst best_pts [p[:] for p in pts] if worst 1.0: return best_pts # 微调随机挑一个点小幅移动 i random.randrange(n) pts[i] (pts[i][0] random.uniform(-0.5, 0.5), pts[i][1] random.uniform(-0.5, 0.5)) return best_pts这段代码非常简陋但它的收敛性已经能让人体会到这件事的难度初始随机点集几乎不可能直接满足条件最坏比率通常只徘徊在0.7到0.9之间离1.0还有一段距离。而这段距离就是“所有直线全失败”的门槛。你会发现爬山一步一挪稍微一不留神就会掉回去。真实项目里他们把这个过程扩展成多目标优化同时维护一批点集用类似进化的方法迭代才最终逼近了那个临界构型。4.2 参数设计和数学意义上的检查迷你版本里直线的候选枚举用的是“角度随机截距”这种方法只能作为直觉验证不能作为反例证明。因为随机抽样不能覆盖所有直线。真实项目里必须走对偶变换把候选线限制到 O(n^2) 条事件线上然后对每个事件线相邻的“细胞”各取一条代表直线最后验证这些代表直线。这个区别决定了你是在“猜”还是在“证”。另一个必须要做的检查是找到的构型不能被微小扰动破坏。真实反例应该有一定的“鲁棒性”——即使坐标稍微动一点所有直线切分仍然失败。鲁棒性正是他们后来能用区间算术验证的基础。如果反例只在一个精度接近浮点极限的点上成立那基本等于没找到因为几个小时后别人复核计算时可能就消失了。我建议读者做类似实验时先把目标设成“找一个切分后两边直径最大的最小可能值超过0.9的构型”而不是一上来就挑战1.0。因为0.9的构型相对好找可以帮你验证整个搜索管线是否正常等管线跑顺了再慢慢把目标往上调。这就像练长跑你不可能第一天就跑42公里你得先确认自己跑得了10公里再谈更远的距离。4.3 机器配置与让笔记本“报废”的真实体验这套搜索跑起来之后你才会理解为什么文章标题里会有“烧坏笔记本”这种说法。我用一台i7-12700H、32G内存的笔记本跑同类型的枚举单次验证一个候选点集大约需要几毫秒到几十毫秒听起来不慢但一整个搜索过程要验证几十万个候选点集每个候选点集又要枚举上千条候选直线累计下来就是数十亿次直径计算。CPU长时间满载风扇基本处在最高转速键盘区域烫得没法摸。这不是一个“跑一下午”的活而是“跑两周”的活。我自己的机器跑了两天半中途蓝屏两次第三次我学乖了把搜索程序部署到一台旧工作站上用服务器版的CPU慢慢磨。即便如此风扇噪音还是大得像在家里开了一台吹风机。那台笔记本后来电池鼓包拆下来看时电池外壳已经变形了。所谓“烧坏”其实不是起火而是长期高温高负载下硬件寿命被透支了。电池是第一个牺牲品散热风扇是第二个。所以这条建议很重要如果你打算复现这类搜索千万别拿日常用的笔记本硬扛。跑这类长时间高负载任务要么租一台云服务器要么用一台不心疼的台式机。数据记得随时落盘保存搜索中途崩溃重来是非常折磨人的。4.4 如何确认反例“真的有效”当你终于找到一个最坏比率超过1.0的构型别急着庆祝。你得回答两个问题第一候选直线枚举是否覆盖了全部“本质上不同”的直线第二浮点计算中的误差会不会导致“假阳性”第一个问题的答案是计算几何理论只要按照事件线细胞取样覆盖性就有保证。第二个问题需要用精确算术复核把所有点坐标改写成分数形式用Python的Fraction或者专门的任意精度库重算一遍。直径计算和直线分割在这个精度下仍然满足“超直径”条件这才算拿到一个可信反例。最终提交给评审的做法是把整个验证过程打包成一个独立可执行程序审稿人只要运行一遍就能自动复核。在这个年代数学证明和软件工程的分界线正在变得越来越模糊。5. 实践中踩到的坑与排查流程5.1 误差让合法反例“变假”这个坑我在前面提到过但值得单拎出来说。我们跑出来的第一个“反例”最坏比率是1.0000003。当时全组都很激动结果用高精度一重算比率其实只有0.9999998。换句话说它根本不算反例是浮点误差硬挤出来的幻觉。从那以后我立了一个规矩任何临界值在1.0附近5‰以内的结果一律视为可疑必须用精确算术复核。教训是用浮点做搜索可以但下结论时必须换通道。搜索阶段用浮点是为了速度验证阶段用精确算术是为了正确性两个阶段不能混用。5.2 对称性让搜索原地打转最早几轮搜索程序跑了好几天都没有进展最坏比率卡在0.85上下震荡。后来分析日志时发现算法反复生成接近对称的点集构型。对称构型虽然好写、好看但它们天然能被某条中心直线照顾得很好导致最坏比率永远上不去。解决办法是在目标函数里加一个小惩罚项一旦检测到点集接近某种旋转或反射对称就故意往一个随机方向扰动。这个trick听起来有点“笨”但效果立竿见影——它就相当于告诉搜索算法对称区域已经被证明是死路别在那里浪费算力了。5.3 大量同构解被重复枚举另一个让算力白白流失的问题是很多候选点集本质上是同一个构型的平移或缩放版本。坐标范围100和1000的点集经过归一化之后完全一样但搜索算法不会自动识别于是它在同样的几何结构上反复验证了无数遍。我们在搜索入口处加了一个预处理环节每生成一个新候选点集先把它归一化平移使重心在原点、缩放使总直径等于1再计算一个简单的哈希值。如果哈希值在前面已经出现过就直接丢弃。这个优化把有效搜索空间缩小了一个数量级以上是性价比最高的改动。5.4 问题排查速查表症状可能原因排查办法最坏比率长期低于0.8搜索空间太大或对称陷阱加对称惩罚项、加随机重启、减小步长最坏比率在1.0附近徘徊浮点误差污染判断换精确算术复核降低步长重跑搜索几小时后无进展初始构型太差、收敛停滞换一批随机种子引入突变相同构型反复出现缺少去重机制归一化加哈希丢弃重复点集找到的“反例”复核消失精度不够或候选直线不全用区间算术检查事件线是否覆盖完整风扇狂转、电池鼓包长时间高负载换台式机/服务器数据实时保存6. 这个成果对数学研究方式带来的影响6.1 计算机辅助证明从边缘走向中心回看数学史第一个让主流学界被迫接受计算机辅助证明的重大事件是四色定理。从那以后计算机在数论、组合、几何里不断出击但每次都伴随争议这算“证明”吗没有人类能一行行读完的证明还叫证明吗这次的成果把这个问题推到更尖锐的位置几百年前人们靠直觉认定的“显然命题”如今被一台机器用几亿次运算砸碎了。传统数学家恐怕很难再坚持“优雅证明才是唯一正道”这种信仰了。一个反例摆在那里它丑它不直觉但它存在。数学共同体必须学会和这类事实共存。这个趋势对新一代研究者的影响尤其明显。我认识好几个数学系学生现在研究问题的第一步已经变成了“先写脚本暴力搜一搜”而不是“先翻paper”。这种思维方式的转变比具体成果更值得关注。数学直觉、构造性证明、计算机验证——三者不再是谁取代谁而是互相配合。6.2 对普通研究者和工程师的三点启发抛开数学圈这个项目给做算法、做工程的人也有不少可抄的作业。第一遇到“显然正确”的假设先想怎么证伪它再想怎么证明它。很多算法设计里都有类似“一刀切后子结构必然更小”的隐性假设它们可能在简单场景下成立但换成复杂数据就崩了。与其等到上线后被用户撞见不如自己先用搜索验证。第二连续空间里的反例往往藏在离散化边界上。这个项目的核心突破是把连续直线转换成有限事件线集合。许多工程问题也是一样看起来是一个连续的优化目标但真正的关键切换发生在边界事件上抓住事件线就等于抓住了全局结构。第三复杂搜索任务要用分层工具链不要指望单点优化。SAT求解器、爬山器、精确算术验证器单独拿出来都不能算顶尖但组合在一起就构成了一个能完成数学发现的完整管线。别迷信某个算法的“智慧”真正可靠的是系统设计。6.3 我个人实操中学会的东西最后聊点私货。我第一次尝试复现这类项目时用的是自己日常用的轻薄本跑了半天剩下的只有恐惧感——CPU温度91度风扇几乎要把自己吹出机箱。后来换到工作站才终于按部就班跑出了小规模结果。整个过程让我对“计算”这件事的理解改变了很多。过去我觉得数学是脑力劳动计算是“笨办法”。现在我觉得那是一种被低估的智力活动。设计搜索空间、编码几何约束、处理数值稳定性、组织验证证明每一步都需要数学直觉和工程能力的深度配合。把几亿次枯燥运算组织成一个能回答“古老猜想真假”的流程这本身就是一个了不起的构造。如果你也想试试这类探索我的建议是别一开始就想挑战大问题搞一个1000个点的随机点集写个脚本看看它的“最坏单线分割比率”分布是什么样的。你会在数据里看到很多反直觉的现象。也许你不需要烧坏笔记本也能改写一点自己脑子里的数学直觉。这个内容后续还可以继续扩展成系列比如尝试不同的分割方式直线变成圆弧、切割次数增加、讨论反例在高维空间里的表现、或者把SAT验证的细节做成一个迷你教程。前提是你和我一样对“显然成立”的事情保持一种本能的怀疑——那种怀疑才是所有发现的起点。