马克·拉肯比:解开死结的人
“目前还没有已知的系统方法可以判断两个结是否相同。”这是艾伦·图灵 (Alan Turing) 在1954年提出的观点,他指出了数学中最棘手的具体未解问题之一:给定一团两端相连的绳子,如何确定它是否真的是一个结。马克斯·德恩 (Max Dehn) 在1910年提出了这个问题。沃尔夫冈·哈肯 (Wolfgang Haken) 在1961年给出了第一个算法,但在处理复杂问题时速度极慢。2021年2月2日,在加州大学戴维斯分校,马克·拉肯比宣布,该问题可以在 n 的 c log n 次方步内解决——即拟多项式时间,这与计算机科学家认为真正可解问题的效率仅一步之遥。牛津大学的数学家称这是一项戈尔迪之结般的壮举。
剑桥与利科里什学派
拉肯比于1990年进入剑桥大学学习数学,并留在那里攻读博士学位,于1997年在 W. B. R. 利科里什 (W. B. R. Lickorish) 的指导下完成,论文题目为《德恩手术与解结操作》。利科里什是20世纪结理论的核心人物之一,而他论文的主题——德恩手术与解结——在四分之一个世纪后依然是拉肯比的研究课题。很少有数学家能那么早就选定自己的领域,并不断在其中发现新事物。
他在加州大学伯克利分校担任米勒研究员,并在回到剑桥后担任研究员,随后于1999年移居牛津,担任圣凯瑟琳学院的讲师和研究员。他于2006年晋升为教授。他的工作横跨结理论、低维拓扑和群论——这三个在三维空间中被证明是同一个主题的不同侧面。
填补空缺
德恩手术是三维拓扑的核心操作:在结周围切出一个实心管,然后以不同的方式将其粘合回去。几乎所有的三维流形都可以通过这种方式产生,因此理解这种操作意味着理解这些对象。
关键问题是结果何时保持双曲性——双曲几何是使三维流形保持刚性并可分析的结构,而其缺失则意味着荒野的开始。2π定理给出了保证手术保持双曲性的几何判据。拉肯比证明了该定理的加强版。这是他典型的研究成果:不是发现新的领域,而是锐化现有的边界线,其效果足以使更多的领土落在有用的一侧。
交错结与体积
第二条主线将结的图像与几何联系起来。将一个结画在纸上,你就得到了组合学——交叉点、圆弧、区域。考虑结周围的空间,你就得到了几何,并附带一个双曲体积。这些是完全不同种类的信息,将它们联系起来是该领域深奥的项目之一。
拉肯比给出了交错结(即绕结移动时,交叉点交替出现在上方、下方、上方、下方的结类)的结补空间双曲体积的界限,将几何不变量与绘图上可数的东西联系起来。这种成果使得结几何变得可计算,而不仅仅是可推演。
里德迈斯特移动计数
任何结的图都可以通过一系列三次基本操作(即里德迈斯特移动)转化为同一结的任何其他图。这一点自20世纪20年代以来就已为人所知,但其本身并无用处:没有任何东西告诉你需要多少步,而且在简化之前,序列可能必须经过比两个端点都混乱得多的图。这正是解结困难的原因——你往往必须先让绳结变得更乱,它才能变得更好。
拉肯比证明了未解之结的图可以通过与交叉点数量呈多项式关系的里德迈斯特移动次数来解开。这种悲观情绪是错误的。即使找到通往平凡圆的路是另一回事,但总有一条相当短的路径。
拟多项式时间
这就回到了2021年。在哈肯之后,结识别问题积累了许多算法,利用了拓扑和几何学,但几乎所有算法在结变得复杂时都慢得离谱。是否存在多项式时间算法已成为拓扑学和计算机科学边界上著名的未解问题之一。威廉·瑟斯顿 (William Thurston) 在2011年明确表示:“很多人都考虑过这个问题……但这确实是一个非常难解决的问题。”
拉肯比的 n^(c log n) 界限并没有完全解决这个问题。拟多项式比多项式慢。但是,拟多项式与之前所有方法之间的差距是巨大的,而在实际和概念层面上,拟多项式与多项式之间的差距很小。图灵曾将其列为未驯服的问题,现在本质上已被驯服。
为什么马克被称为天才
展现出的品质不是速度,也不是广度。而是一种耐心的深度:在同一组问题——德恩手术、解结、结补空间的几何——上坚持研究25年,积累技术,直到曾经阻碍了几代人的问题变得可以解决。解结的结果是最明显的证据,因为它不是靠聪明的把戏,而是靠一个花费了职业生涯构建所需特定机器的人,他能在别人看不到的地方,看出拓扑和几何工具的哪种组合可以发挥作用。
同行对他的认可是一贯的,而非轰动性的:2003年伦敦数学学会的怀特黑德奖,2006年数学与统计学领域的菲利普·利弗休姆奖,2010年受邀在国际数学家大会上发言——这是该学科最可靠的学术地位信号。2021年的公告引发了最强烈的评价,牛津大学称其为“壮举”。
反面观点也必须陈述。没有资料记录有人称拉肯比为天才,他所属的数学界对这个词非常吝啬。他的工作直接建立在哈肯、瑟斯顿、利科里什和整个正规表面传统之上;拟多项式算法是既定框架内的壮观改进,而不是新框架。它也不是多项式的,这意味着标题问题在技术上仍然悬而未决。而且低维拓扑尽管很美,却是一个专业领域——他的成果在拓扑学家中很有名,但在外部基本上不为人知。毫无争议的是,他攻克了一个困扰了整整一个世纪的问题,并且是通过比任何人都更透彻地了解自己的学科来做到这一点的。
遗产
拉肯比在其所有四个研究方向上所做的,就是使结理论变得有效。通过计算交叉点来确定体积界限,通过计算移动次数来确定解结界限,通过计算步数来确定识别界限——在每种情况下,一个只能被推演的对象都变成了一个可以计算的对象。这种转变是将美妙理论转化为可用理论的原因,也是2021年的研究成果从拓扑学领域扩展到理论计算机科学领域的原因。德恩在1910年提出了这个问题。这花费了111年时间,以及一位拒绝研究其他任何事情的牛津大学教授的努力。


