(ID: Principia 1687)。作者:佐助，头像来自:卡尔·弗里德里希·高斯(Carl Friedrich Gauss)，维基媒体中著名的数学家，有很多优秀的学生，如波恩哈德·黎曼、库默、奥古斯特·莫比乌斯等。我们今天要讲的题目是戴德金数，它是由高斯的另一个学生戴国安·德金在1897年提出的。最近，一组研究人员解决了一个30年来未解决的关于戴德金数的问题。德国数学家戴国安·德金(1831-1916年)。(图/维基百科)快速增长的整数序列在介绍戴德金数是什么之前，我们先来回顾一个老故事《棋盘上的大米》:据说从前有一个国王，非常富有。他问发明家想要什么奖励，发明家向他要了一个很特别的奖励——一些大米。具体来说，他要求国王在第一格放一粒米，第二格放两粒，第三格放四粒，第四格放八粒，以此类推。每个格子里的米粒是前一个格子的两倍。国王慷慨地同意了这个谦卑的请求。但很快，他意识到这是一个不可能的要求，因为要填满整个棋盘，需要的米粒数量将是天文数字，总共有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的单调布尔函数的数目。(图片/维基百科)近日，来自德国帕德博恩大学和比利时鲁汶大学的研究人员在超级计算机Noctua的帮助下，解决了这个长达数十年的难题:他们找到了D(9)，发现这个数字庞大到42位数。研究成果将于今年九月在挪威举行的布尔函数及其应用国际研讨会(BFA)上发表。世界帕德博恩大学计算机科学博士生Lenart Van Hirtum是取得这一突破的主要研究人员之一。他在鲁汶大学读计算机专业研究生的时候，硕士论文是如何找到D(9)。鉴于D(8)是一个已经达到23位数的巨大数字，Van Hirtum意识到，要找到D(9)，必须有一个高效的计算方法和一台非常快的计算机。范·希尔图姆的研究生导师帕特里克·德·考斯梅克(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系统之一。经过几年的开发和大约5个月的操作，3月8日，他们终于找到了第九个戴德金数，数值为:n=9的戴德金数。今年4月，他们在arXiv(一个预印网站)上提交了他们的论文。无独有偶，德国德累斯顿工业大学的Christian jkel也在4月提交了一篇关于arXiv的论文。kel利用矩阵乘法和自由分配格的对称性，提出了一种计算D(9)的新算法，最终得到了与Van Hirtum相同的数。