用了30多年,终于找到了这个数
2023-06-28 21:52

用了30多年,终于找到了这个数

本文来自微信公众号:原理 (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),作者:佐佑

本内容为作者独立观点,不代表虎嗅立场。未经允许不得转载,授权事宜请联系hezuo@huxiu.com
如对本稿件有异议或投诉,请联系tougao@huxiu.com
正在改变与想要改变世界的人,都在 虎嗅APP
赞赏
关闭赞赏 开启赞赏

支持一下   修改

确定