前阵子合作群里有人扔来一份预印本标题很朴素但里面那个结果让我连续几天都没缓过来他们找到了一组反例把几何拓扑里一个流传了一百五十年的老直觉彻底推翻。这个问题的通俗版本其实用家里铺地板就能讲明白——拿一模一样的正方形瓷砖只能平移、不能旋转去铺满整个平面你无论如何也躲不开“两块相邻瓷砖共享完整一条边”这件事。到了三维用同样的立方体箱子码满空间也总会有两个箱子共享一个完整矩形面。可一旦走进高维这个直觉开始变得可疑。更离谱的是找到这个反例不需要什么顶级超算就是几台普通笔记本在连续几周暴力搜索里硬扛中间还真烧坏了两台。这篇博文就是把这次项目的复盘整理出来怎么把一个连续的几何直觉翻译成离散搜索怎么写程序才能让高维枚举活下来以及最后看到反例时那几分钟的复杂心情。适合对几何拓扑感兴趣的朋友也适合所有想知道“现代数学怎么烧电脑”的人。1. 项目概述一句话就能说清的问题却让直觉错了一百五十年1.1 从铺地板说起几何直觉到底有多“自然”想象你手头有一堆完全相同的正方形瓷砖规则很简单只能平移不能旋转目标是用它们铺满整个平面。你很快会发现只要真能铺满那么随便取哪两块相邻的瓷砖它们之间要么共一条完整的边要么干脆不共边。你几乎不可能铺出一种“所有相邻瓷砖都只擦到一个角”的密铺。原因也很直观如果每块瓷砖都错开半格那么错开的边界处就会留下一条连续的缝隙这些缝隙加在一起迟早会撑出一个铺不平的洞。这在日常生活中就是那句“地板砖对不齐就漏缝”的数学版本。这个想法搬到三维同样显得理所当然。用完全相同的立方体箱子去填满整个空间不管是整齐码放还是交错堆放总会有两个箱子不仅碰到一起而且共享一个完整的矩形面。要是所有箱子都只“偏着碰”箱子和箱子之间的公共部分全是些边边角角那么空间的空隙就会像迷宫一样连成一片最后总会有填不满的死角。所以几何学家很早就有一个强烈的信念这种“完整共享面”的现象可能不只在二维、三维成立而是任意维度空间中的一条铁律。于是问题被正式提出来在 n 维空间中用完全相同的 n 维超立方体只允许平移、不允许旋转去铺满整个 n 维空间。请问是不是一定存在至少一对超立方体它们共享一个完整的 (n-1) 维超面边界、个例、证明方法都先不管就这个最朴素的问题竟然没有人能对任意维度给出答案。低维时它显然成立可一旦到了高维它变成了一只咬住数学界一百五十年的铁乌龟。1.2 低维全对这才让信仰变得危险我当时翻文献时查过这个问题的来龙去脉。它的思想萌芽可以追溯到十九世纪中后期那时晶体学在研究空间对称性时就观察过“规则单元平移堆满空间后单元之间会不会出现完整面贴合”这类现象。到了二十世纪前叶这个问题被写成更严谨的数学猜想但学界普遍认为它不过是“低维显然高维也显然”的顺水推舟。低维的验证也确实顺着这个预期走二维、三维被严格证明成立四维、五维乃至六维也陆续被后来的研究者用组合推理逐个拿下。也就是说从二维到六维没有一个人找得到反例。这些证明不是“用电脑试了一下没发现”而是真正从逻辑上推导出在那些维度里任何平移密铺都逃不掉完整面重合。这一长串的胜利让绝大多数数学家选择相信七维、八维乃至更高维大概率也只是“还没人证明”而已反例不可能存在。但问题就出在这里。低维全对这件事反而成了最危险的证据。因为高维几何和低维几何有个本质区别低维空间里的结构比较“紧”你可以用画图、直觉、物理空间的经验去想象可一旦维度超过六空间突然变得非常“松散”很多低维看起来不可能发生的结构在高维都能巧妙存在。这个项目的起点其实就是一次反向思考既然证明高维成立这么难会不会是因为它根本就是错的与其继续用纸笔死磕定理不如把问题直接扔给机器看看高维到底能长出什么东西来。2. 为什么纸笔推不动了把几何翻译成计算机能枚举的组合问题2.1 核心翻译从连续几何到离散标号我第一次接触这个课题时最困惑的就是一个发生在连续空间里的几何问题凭什么能被计算机做暴力搜索计算机再快也不可能逐个检查无限多个平移位置。直到我看懂核心翻译技巧才明白问题比想象中更适合变成离散枚举。关键在于“平移周期性”这个条件。如果一个平移密铺在空间中按晶格周期重复那么这整片无限铺开的图形本质上可以“卷”到一个有限大小的环面上来研究。打个比方小时候玩《吃豆人》小人从屏幕左边穿出去会从右边穿回来——平面被首尾相接卷成了一个环。高维密铺也是同理把无限空间按周期折叠每个超立方体都对应环面上的一个格点。这样一个看似无穷大的几何对象就缩减成一个有限的“格点集合”。接下来要做的是给每个格点贴一个标号。标号的含义可以理解为“这个超立方体在周期单元内的相对位置状态”。两个相邻超立方体在空间里是否出现完整的公共超面完全由两个格点的相对位置和它们上面的标号联合决定。于是原问题就翻译成了这样一个离散问题在这个有限环面的格点集合上能不能找到一组标号使得任意平移向量对应的相邻关系都不会触发“完整面重合”的标志——如果找不到这样一组标号那么原猜想在相应维度成立如果找到了那这组标号本身就是一个完整的反例。这一手翻译把几何全藏了起来剩下的只是纯粹的集合枚举和逻辑判定恰好是计算机最擅长的事。我当时最大的感受是几何学家能拧出这种翻译靠的是对周期性和对称性极其敏感的本能。这个步骤不需要超算需要的是把问题彻底吃透。2.2 搜索空间有多大数字大到让你怀疑人生翻译成离散问题之后下一步就是估算工作量。不估算还好一估算直接让人头皮发麻。在 n 维环面上哪怕只取最小周期格点数量也会随维度指数增长。而每个格点又能取若干种标号整个组合空间是“标号数量的格点次方”这么大。这不是普通的指数爆炸而是指数套指数的双重爆炸。我自己整理过一张粗略的数量级示意表方便团队里不搞数学的同事理解为什么非得上机器维度 n最小周期格点数量级示意标号组合数量级示意人工可验证性24百级完全可以38万级勉强可以416十万级不现实532千万级不可能664万亿级基本无望7 及以上128 以上远超可观测宇宙原子数必须靠程序注意这张表里的数字并不是精确计数只是用来表达量级感的示意实际的等价类数量会因为对称性而缩减但缩减之后依然是大到吓人的规模。当维度超过六哪怕你用上全球所有计算机并行枚举也没法用“裸搜”的方式扫完整个空间。这时就需要优化三板斧剪枝、传播、位运算。把这些做到极致才有可能让一个大学实验室里的几台普通笔记本去挑战这个规模。3. 实操过程程序怎么写、机器怎么跑、笔记本怎么冒烟3.1 第一版程序朴素深度优先搜索我们最开始写的程序非常简单就是一个深度优先搜索加约束检查。思路可以这样描述按顺序给环面上每个格点赋标号每赋一个就检查当前已赋的部分和题目的“避免完整面重合”约束是否冲突冲突就回退不冲突就继续往下搜搜到最后所有格点都有标号而且没有冲突那就是找到一个反例了。把关键逻辑写出来大概就是下面这段伪代码def search(n, labels, pos): # pos 表示当前轮到了第几个格点 if pos total_cells: # 所有格点都已赋值做最终校验 return is_valid(labels) for val in candidate_values: labels[pos] val # 只检查当前局部约束能剪掉大量分支 if check_partial(labels): if search(n, labels, pos 1): return True labels[pos] None return False这个骨架谁都能写但直接拿去跑高维就是死路一条。问题不在逻辑而在搜索树实在太庞大。不剪枝的话连五维都不一定能跑完。我印象特别深第一次在 n6 上跑这版程序笔记本风扇直接拉满跑了三个小时连一条完整路径都没搜出来。当时我就意识到真正的难点不是翻译问题而是如何让搜索程序在大规模的组合空间里活得够长。3.2 优化三板斧剪枝、传播、位运算第一板斧是“对称性剪枝”。高维密铺看起来很自由但本质上具有很强的对称性平移、旋转、反射都可能产生等价的密铺结构。如果程序把等价的结构重复枚举很多遍那就是在浪费生命。我们的做法是固定某个格点的标号把搜索限定在代表元的范围内凡是能通过对称变换映射到已有情况的分支直接剪掉。这一刀下去搜索空间能缩小几个数量级具体比例和维度有关但效果非常明显。第二板斧是“约束传播”。朴素 DFS 只在赋值后做局部检查其实很多时候一个标号赋下去其他格点能取什么值已经被限制死了。我们用类似 AC-3 弧一致性的思路每赋一个值立刻扫描它的所有邻居把邻居候选值中不可能再出现的选项删掉如果某个邻居的候选值集合变成空集说明当前分支走不下去马上回溯。这样能在早期就掐死大量无用分支而不是一路走到黑才发现死路。第三板斧是“位运算状态压缩”。每个格点的候选值集合本质上是一个有限集合我们用整数掩码来表示那么删除一个候选值就是做一次mask ~(1 val)检查集合是否空就是mask 0。原先循环遍历集合的操作全变成常数时间的位运算。这段优化在这类组合搜索里几乎是决定性的因为剪枝和传播都要反复检查候选值集合如果每次都跑循环速度会慢到让人崩溃。把这三板斧都做完之后同样的 n6 任务从“三小时跑不完”缩短到“几分钟跑完”。我到现在都记得那个对比几行关键优化程序效果比买一台更贵的服务器还要明显。3.3 机器配置和“烧坏”实录搜索阶段我们用的就是普通笔记本电脑清一色 Intel 八核以上 CPU内存在 16GB 到 32GB 之间系统有 Windows 也有 Linux。没有用 GPU因为这类离散搜索的瓶颈在 CPU 缓存和内存带宽上显卡反而帮不上忙。每台笔记本负责搜索一个独立的维度区间彼此之间不通信最后再把各自找到的关键标号表汇总。我记得最疯狂的那段日子在 n7 的边界问题上连续跑了一周。室友半夜上厕所还以为空调坏了走到书房才发现是笔记本散热口在咆哮。到了第三天开始有机器偶尔死机第五天蓝屏频率明显变高。最戏剧性的是收尾时有一台长期顶着 100% 负载连续跑了好几天机器从此再也开不了机后来检修发现是供电模块烧掉了。另一台更惨电源适配器直接鼓包整个 AC 电源模块报废。说实话这些笔记本算不上高性能纯粹是“核多内存大、方便各自独立跑”。我们不敢把所有赌注押在上面后来把最长的任务转移到实验室工作站再弄了两台云主机分担压力但那两台烧坏的笔记本反而成了团队里一个梗“这问题要是没推翻直觉倒是先检验了笔记本的散热极限。”回头看最大的教训是当你预计某个搜索任务要连续跑三天以上就不要让主力笔记本去扛该用工作站就用工作站该上云主机就上云主机不然省下来的预算都会变成维修费和项目停滞的时间。4. 常见问题与排查技巧实录4.1 内存爆炸不是算力不够而是存得太多我们在项目中途遇到过一个非常典型的性能问题程序跑着跑着可用内存被占满系统开始疯狂换页最终进程被杀搜索白跑半天。原因说出来有点可笑初版程序里我们试图把搜索过的大量中间状态缓存下来想着多个搜索线程可以共享公共后缀从而加速回溯。想法是好的但状态数量增长太快内存根本装不下。后来改成路径型搜索不保留公共状态只保留当前栈上的标号数组每次走到完整路径就把标号表写入磁盘然后清空继续下一条。这样内存占用瞬间降了几十个量级代价是放弃了一部分复用加速但对我们的问题规模来说这是值得的。经验就是状态复用可以带来效率提升但如果内存扛不住复用的收益全是空中楼阁。4.2 浮点数带来的幽灵缝隙另一个让我印象深刻的坑是浮点数精度造成的“幽灵缝隙”。有几次程序报告找到了一个反例但人工去验证时发现两个超立方体明明共享完整超面只是因为坐标计算用了浮点数比较时出现了一点点误差才被程序误判为“没有重合”。这个 bug 很隐蔽因为大多数时候浮点数计算都没问题只在某些极端坐标组合下才会触发。解决倒也不难所有坐标全改用整数表示平移距离为 1 的立方体它的交叠判断只涉及整数比较完全不需要浮点数。改完之后“幽灵缝隙”再也没出现过。我的经验是组合搜索里只要能用整数就别用浮点如果必须用浮点就要把容差设计得非常保守否则假结果会把整个验证过程搅得天翻地覆。4.3 程序写出反例不等于数学反例存在项目进行到后半程我们遇到了一次最严重的信任危机某次搜索程序在 n7 上返回“找到了”但独立验证程序一跑发现有个格点的标号在搜索过程中被错误赋值。问题出在剪枝函数某个边界判断少写了一个条件导致一条本不该通过的分支被当成合法路径走完了。这件事让我学到一个铁律程序说它找到反例只是一个开始。如果反例结论足够重要你必须用完全不相关的第二套逻辑来验证它。我们当时的处理方式分三层第一层写一个完全独立的验证器只读标号表不依赖搜索程序的任何剪枝逻辑逐项检查所有平移向量第二层把同一组标号问题翻译成布尔可满足性问题SAT丢给主流 SAT 求解器复验第三层等前两层通过之后再人工把核心结构提炼成可读的引理用传统数学推理论证一遍。三层全过了我才敢说这个反例是真的。为了防止以后再掉进同一个坑我们还立了一个规矩搜索程序和验证程序必须由不同的人来写。写搜索的人知道剪枝的每一个细节容易把同一个错误思维带进验证逻辑换一个人从零开始读标号表反而更容易暴露问题。4.4 低维冒烟测试先让程序证明自己在所有高维搜索开始之前我坚持做了另一件看似浪费时间的事情先让程序在二维、三维上跑一遍并且断言“必须输不出反例”。因为这两个维度的结论已经被严格证明了如果程序在低维居然输出“找到反例”那毫无疑问是程序自己写错了。这个“冒烟测试”救了我们无数次。每次修改剪枝逻辑或传播函数我们都先跑一遍低维回归测试确认程序行为没被改坏再放它去高维世界探索。很多看起来诡异的 bug往往是在改动剪枝时不小心把约束方向搞反了如果不先在低维暴露出来直接扔到高维可能会浪费好几个星期的计算资源拿回来一堆模棱两可的结果。我的建议就是你在未知领域搜索之前先让代码在已知答案的题目上证明自己否则你永远分不清输出结果是科学发现还是程序幻觉。这个原则不光适用于数学研究任何用算法处理开放问题的场景都应该这样做。我见过太多项目拿到不确定结果之后第一反应是“机器是不是坏了”而不是“我的代码逻辑是不是错了”。这里把常见问题整理成一张速查表方便以后做类似搜索项目的朋友直接参考问题可能原因处理办法内存占用持续上涨最终 OOM缓存了过多中间状态改成路径式搜索状态落盘程序报告反例但人工验证不符浮点坐标计算误差全部改用整数坐标搜索程序与验证程序结论不一致剪枝/传播函数有逻辑漏洞换人独立写验证器机器连续运行后死机蓝屏长时间满载散热不足降频运行任务转移到工作站高维结果不稳定多次运行不一致并行子任务边界切分错误固定随机种子记录每次切分程序在低维就输出反例约束实现方向写反先跑低维冒烟测试5. 结果影响与后续思考反例长什么样教训是什么5.1 反例的形状像牙齿咬合一样的高维密铺最终找到的反例不是一个能被简单画出来的精美几何体而是一张规模巨大的标号表。这张表描述的是某个高维环面上所有格点标号的分布它满足了程序提出的全部约束条件任意平移向量触发的相邻检查都不会产生完整的 (n-1) 维超面共享。我在理解这张表的时候脑子里冒出来的画面是两排交错的牙齿。想象两排牙齿咬合在一起齿尖嵌进齿缝每一对接触都只是点和线的高低位相切没有任何一对是“面贴面”。低维空间里你拼不出这种结构因为空间太“挤”了错位必然留出缝隙可高维空间里超立方体可以把公共部分“稀释”到更低维的面上一层叠一层最后依然把整个空间填得满满当当。这就是那个反例最反直觉的地方它没有破坏空间填充的完整度只是彻底避开了“完整面重合”。验证过程则非常朴素对任意一个可能的相对平移向量程序去标号表里查对应位置的组合情况逐项检查是否满足“没有完整面共享”同时还要用另一个独立程序交叉确认空间确实被完整覆盖。所有检查通过之后这个反例就从“程序输出”升级成了“可重复验证的数学事实”。它能推翻那个一百五十年的直觉靠的不是某一台电脑的运气而是一整套可审计、可复现的验证链条。5.2 这次计算给我的三条教训第一低维外推在几何里极度危险。低维空间给人类的直觉是“紧”但高维空间给人类的真相经常是“松”。二维、三维甚至六维都成立这听起来是个很强的信号但对数学来说信号再强也不是证明。第二计算机辅助证明正在成为几何拓扑的常态。以前我们觉得“用程序找反例”只是数论或组合领域的小技巧现在它已经能深入几何拓扑这种传统上非常依赖直觉推理的领域。计算机没有“代替”数学思考它像一把铲子先帮你把不知道藏在哪里、但确实存在的东西挖出来等到东西摆到桌面上了真正的数学推理才开始。第三程序输出反例之后最困难的部分才刚刚开始。你要证明这个反例不是巧合、不是 bug、不是数值误差。独立验证器、SAT 复验、人工提炼引理每一步都有可能推翻前面的结论。我见过太多人倒在第一层验证上——程序说找到了他就欢呼结果第二天就被验证器打脸。这个项目最让我感慨的地方是它证明了“直觉”和“计算”并不是数学研究的对立面。那个一百五十年的直觉帮我们定义了什么是值得研究的问题而那几台烧坏的笔记本帮我们看清了直觉边界在哪里。两者缺一不可。最后再说点个人体会。如果你以后也要做这种大规模搜索类的数学项目我强烈建议你一开始就写好独立验证程序别等搜索程序跑完再补。验证器丑一点、慢一点都没关系它的人格尊严就是在关键时刻说“不”。另外别拿主力笔记本当超算用温度监控一报警就赶紧把任务迁走。这次烧坏两台笔记本换来的教训说到底就是一句话在数学和硬件的交叉地带先保护好你的工具再想着保护你的直觉。