在这个数列面前，人类算力可能不够了
在这个数列面前，人类算力可能不够了从 1897 年德国数学家戴德金给出了“戴德金数”的定义，数学家到 2023 年才找到了 9 个戴德金数。该数字长达 42 位，耗尽了现在最强的算力，我们何时才能找到第 10 个戴德金数？
撰文 | 张和持
戴德金数是一串增长非常迅速的数列，以德国数学家戴德金（Richard Dedekind，1831-1916）命名，最初于 1897 年给出定义。1991 年，数学家找到了第 8 个戴德金数，数字长达 23 位。30 多年后的 2023 年，数学家终于计算出了序列的第 9 个，其数字长达 42 位。对戴德金数的计算很大程度上反映了当今计算机的算力，因此何时能迎来第 10 个戴德金数仍未可知，似乎遥遥无期。
何谓戴德金数
在给出戴德金数的定义之前，我们先来看一看目前已经得到的计算结果。我们把第 n 个戴德金数记作 M(n) ，那么从 0 到 9 的十个戴德金数如下：
图片来自维基百科
为什么要关心单调布尔函数呢？我们把所有单调布尔函数的集合记做 L ，可以证明，L 在 ∨,∧ 两个运算下是封闭的，并且满足分配律。这样的代数结构称为（分配）格（lattice），而最早研究这一结构的戴德金也被认为是格论的先驱。格论在抽象代数、逻辑学、理论计算机科学等领域中扮演着相当重要的角色。戴德金的格论研究却在他死后无人问津。直到上世纪 30 年代，美国数学家伯克霍夫（George David Birkhoff）在研究泛代数等过程中重新发现了戴德金的工作，从此格论才正式走向历史的舞台。戴德金本人未曾找到的第五个戴德金数也是在这一时期由美国数学家邱奇（Alonzo Church）找到。
从 M(5) 到 M(8)
寻找 M(9) 的长跑
现在，我们看看 M(9) 是如何找到的。故事的起点在比利时的鲁汶天主教大学，当时还是计算机科学硕士生的范·赫图姆（Lennart Van Hirtum）正跟随考斯马克（Patrick De Causmaecker）教授研究毕业课题。考斯马克在 2014 年的一篇论文中提出了一种新的通过 M(n-2) 中函数表计算 M(n) 的方法，称为 P-系数公式。有了这个公式，就算是普通的家用笔记本电脑，也能在 8 分钟内计算出 M(8) 。在考斯马克的指导下，范·赫图姆开始尝试用 P-系数公式计算 M(9) 。
当然事情没有那么简单。虽然用同样的方法可以在 8 分钟内计算出 M(8) ，但是到了 M(9) 这，即便是粗略估计，按一般计算机也得运行数十万年。范·赫图姆在他的毕业论文中改进了公式，但最重要的，仍然是需要一台超级计算机。与深度学习不同，目前的 GPU 是对于计算 P-系数并没有什么优势，而 CPU 的算力也无法指望。这时，他们想到了 FPGA 。
FPGA 全称 Field Programmable Gate Arrays ，中文翻译为现场可编程逻辑门阵列。简单来说，这是一种半定制的集成电路，可以利用逻辑合成等工具快速把逻辑电路刻录上去，这样就能实现自己设计的并行算法。范·赫图姆一边进行着论文的理论设计，一边寻找着拥有 FPGA 的超级计算机。最终伸出援手的，是德国的帕德博恩大学。
超级计算机 Noctua 2 坐落于帕德博恩大学下属的帕德博恩并行计算中心。这台电脑拥有着世界上数一数二的大规模 FPGA 系统，而并行计算中心的负责人在了解范·赫图姆和考斯马克的意图后，欣然接受了他们的使用请求。对于他们来说，要用超级计算机来解决这样复杂的组合问题也是一项极具挑战性的任务，对于系统稳定性与可靠性提出了不小的要求，同时也是测试设备的绝佳机会。经过数年的开发，程序终于在去年开始运行。范·赫图姆也从鲁汶毕业，进入帕德博恩大学攻取博士学位。
程序运行了 5 个月，在 2023 年 3 月 8 日，终于得到了最终结果
M(9)=286386577668298411128469151667598498812366 。
同时到达终点
同样在计算 M(9) 的，并不只有帕德博恩大学的这组人。德国德累斯顿工业大学的耶克尔（Christian Jäkel）也几乎在同一时间得到了相同的结果。耶克尔的计算基于 M(n-4) 的函數表。他将问题转换为矩阵乘法，多台 Nvidia A100 GPU 总共花了 5311 小时，总计进行了 4257682565 次矩阵乘法计算之后，得到了与范·赫图姆等人完全相同的结果。耶克尔于 4 月 5 日将自己的论文挂上了预印本网站，仅仅比帕德博恩的团队早了一天。因此，发现的殊荣将同时归于以上两组人，并且他们使用的不同方法更加证实了结论的正确性。不过他们都提到，目前的方法对于 M(10) 还是不管用的。很难想象，当下一次的突破来临时，算力的发展将达到怎样惊人的程度。
参考文献
Jakel, Christian (2023-04-05). "A computation of the ninth Dedekind Number". arXiv:2304.00895
Van Hirtum, Lennart (2023-04-06). "A computation of D(9) using FPGA Supercomputing". arXiv:2304.03039 .
Patrick De Causmaecker and Stefan De Wannemacker. On the number of antichains of sets in a finite universe, 2014.
Yusun, T.J.: Dedekind numbers and related sequences (2008)
Ninth Dedekind number discovered: Scientists solve long-known problem in mathematics, https://phys.org/news/2023-06-ninth-dedekind-scientists-long-known-problem.html
原创 张和持 返朴 2023-09-04 08:02 发表于北京
页:
[1]