本文来自微信公众号：原理 （ID：principia1687），作者：佐佑，头图来自：wikimedia


大名鼎鼎的数学家高斯（Carl Friedrich Gauss）有许多杰出的学生，比如黎曼（Bernhard Riemann）、库默尔（Ernst Kummer）、莫比乌斯（August Möbius）等等。


今天我们要谈论的主题是戴德金数，它由高斯的另一位学生——理查德·戴德金（Richard Dedekind）于1897年提出。最近，一组研究人员解开了一个有关戴德金数的长达30多年的未决难题。‍‍‍


德国数学家理查德·戴德金（1831-1916）。（图/Wikipedia）


增长快速的整数序列 


在介绍何为戴德金数之前，我们先来回顾一个古老的故事，“棋盘上的米粒”：相传有一个拥有无上财富的国王，他询问发明了国际象棋的人想要什么奖励，发明人向他讨要了一份非常特别的赏赐——一些米粒。


具体来说，他要国王在棋盘上的第一格放上一粒米，第二格放两粒，第三格放四粒，第四格放八粒，依此类推。每一格上放置的米粒都是前一格上的两倍。


国王慷慨地答应了这个“谦卑”的请求。但很快，他就意识到这是一个不可能实现的要求，因为要填满整个棋盘，需要的米粒数量将是一个天文数字，总数高达20位数……


戴德金数，D(n)，也是这样一个增长迅速的整数序列，它与单调布尔函数有关，描述的是有着n个变量的单调布尔函数的个数。1897年，戴德金在提出这一问题后，便找到了0≤n≤4所对应的戴德金数。目前，0≤n≤8所对应的戴德金数都已经找到。其中，D(8)是最后一个被发现的戴德金数。1991年，计算机科学家用当时最强大的超级计算机Cray 2发现了这一具有23位的数字，比棋盘上的米粒还要多得多。


0≤n≤8的戴德金数。


但寻找n=9的戴德金数却是一个困扰了数学家30多年的重大挑战，人们甚至怀疑，计算出D(9)是否是有可能的。


一个n维立方体游戏 


要如何理解戴德金数呢？简单来说，我们可以将二维、三维和无限维的单调布尔函数，想象成一个与n维立方体有关的游戏：这个立方体通过一个角保持平衡，然后剩下的每个角要么被涂成白色，要么涂成红色。规则只有一条——白色的角不能在红色的角之上。这样的规则会创造一种垂直的红白交叉，而戴德金数就对应于不同的切割个数。


维度为0、1、2、3的所有可能的切割方式，对应于有0、1、2、3个变量的单调布尔函数的个数。（图/Wikipedia）


最近，来自德国帕德博恩大学和比利时鲁汶大学的研究人员，在超级计算机Noctua的帮助下，解开了这个长达数十年的谜题：他们找到了D(9)，并发现这个数字庞大到共有42位。研究结果将于今年9月在挪威举行的布尔函数及其应用国际研讨会（BFA）上发表。


全世界的沙粒 


帕德博恩大学的计算机科学博士生Lenart Van Hirtum是做出了这项突破的主要研究人员之一。当他还在鲁汶大学攻读计算机科学专业的研究生时，他的硕士论文就是如何寻找D(9)。


鉴于D(8)是一个已经高达23位数的庞大数字，Van Hirtum意识到，要找到D(9)，必需要有一种高效的计算方法和一台非常快的计算机。


Van Hirtum的研究生导师Patrick De Causmaecker曾发展过一种被称为“p系数公式”的技术。这种技术可以提供一种无需通过计数，而是通过一个非常大的求和的方法，来计算戴德金数。


在普通电脑上，这种方法可以用8分钟左右的时间就计算出D(8)；但当用它来计算D(9)时，时长瞬间被拉到数十万年。即使专门使用一台大型超级计算机，也需要很多年才能完成计算。


主要的问题就在于这个公式中项的数量增长得非常快。在新的研究中，研究人员利用公式中的对称性，将项的数量减少到5.5×10¹⁸个。虽然这仍然是一个巨大的数字（地球上的沙粒数量约为7.5×10¹⁸），但对于一台现代的超级计算机来说，运算5.5×10¹⁸并非不可实现。


超级计算机 


Van Hirtum意识到，在普通处理器上计算这么多项的速度必然会很慢，而且使用GPU作为目前许多人工智能应用程序中的最快硬件加速器技术，效率并不高。因此，新的解决方法是：使用高度专业化并行运算单元的专用硬件，即所谓的FPGA（现场可编程门阵列）。


Van Hirtum开发了一个硬件加速器的初始原型，并开始寻找适合的超级计算机。在这个过程中，他在帕德伯恩大学发现了Noctua 2计算机，这台计算机是世界上拥有最强大的FPGA系统之一。


经过几年的开发和大约五个月的运行，3月8日，他们终于发现了第9个戴德金数，数值为：


n=9的戴德金数。


他们于今年4月在论文预印网站arXiv上提交了论文。


无独有偶，德国德累斯顿工业大学的Christian Jäkel也于4月在arXiv上提交了一篇论文。在这篇论文中，Jäkel提出了一种利用矩阵乘法和自由分配格的对称性来计算D(9)的新算法，并最终得到了与Van Hirtum相同的数字。


参考来源：

https://www.uni-paderborn.de/en/news-item/123917

10.1109/URTC56832.2022.10002211


本文来自微信公众号：原理 （ID：principia1687），作者：佐佑