理查德·戴德金 

大名鼎鼎的數(shù)學(xué)家高斯（Carl Friedrich Gauss）有許多杰出的學(xué)生，比如黎曼（Bernhard Riemann）、庫默爾（Ernst Kummer）、莫比烏斯（August M?bius）等等。

今天我們要談?wù)摰闹黝}是戴德金數(shù)，它是由高斯的另一位學(xué)生——理查德·戴德金（Richard Dedekind），于1897年提出的。最近，一組研究人員解開了一個(gè)有關(guān)戴德金數(shù)的長(zhǎng)達(dá)30多年的未決難題。

德國(guó)數(shù)學(xué)家理查德·戴德金（1831-1916）。（圖/Wikipedia）

  增長(zhǎng)快速的整數(shù)序列 

在介紹何為戴德金數(shù)之前，我們先來回顧一個(gè)古老的故事——“棋盤上的米?！保合鄠饔幸粋€(gè)擁有無上財(cái)富的國(guó)王，他詢問發(fā)明了國(guó)際象棋的人想要什么獎(jiǎng)勵(lì)，發(fā)明人向他討要了一份非常特別的賞賜——一些米粒。

具體來說，他要國(guó)王在棋盤上的第一格放上一粒米，第二格放兩粒，第三格放四粒，第四格放八粒，依此類推。每一格上放置的米粒都是前一格上的兩倍。

國(guó)王慷慨地答應(yīng)了這個(gè)“謙卑”的請(qǐng)求。但很快，他就意識(shí)到這是一個(gè)不可能實(shí)現(xiàn)的要求，因?yàn)橐顫M整個(gè)棋盤，需要的米粒數(shù)量將是一個(gè)天文數(shù)字，總數(shù)高達(dá)20位數(shù)……

戴德金數(shù)，D(n)，也是這樣一個(gè)增長(zhǎng)迅速的整數(shù)序列，它與單調(diào)布爾函數(shù)有關(guān)，描述的是有著n個(gè)變量的單調(diào)布爾函數(shù)的個(gè)數(shù)。1897年，戴德金在提出這一問題后，便找到了0≤n≤4所對(duì)應(yīng)的戴德金數(shù)。目前，0≤n≤8所對(duì)應(yīng)的戴德金數(shù)都已經(jīng)找到。其中，D(8)是最后一個(gè)被發(fā)現(xiàn)的戴德金數(shù)。1991年，計(jì)算機(jī)科學(xué)家用當(dāng)時(shí)最強(qiáng)大的超級(jí)計(jì)算機(jī)Cray 2發(fā)現(xiàn)了這一具有23位的數(shù)字，比棋盤上的米粒還要多得多。

0≤n≤8的戴德金數(shù)。

但尋找n=9的戴德金數(shù)卻是一個(gè)困擾了數(shù)學(xué)家30多年的重大挑戰(zhàn)，人們甚至懷疑，計(jì)算出D(9)是否是有可能的。

  一個(gè)n維立方體游戲 

要如何理解戴德金數(shù)呢？簡(jiǎn)單來說，我們可以將二維、三維和無限維的單調(diào)布爾函數(shù)，想象成一個(gè)與n維立方體有關(guān)的游戲：這個(gè)立方體通過一個(gè)角保持平衡，然后剩下的每個(gè)角要么被涂成白色，要么涂成紅色。規(guī)則只有一條——白色的角不能在紅色的角之上。這樣的規(guī)則會(huì)創(chuàng)造一種垂直的紅白交叉，而戴德金數(shù)就對(duì)應(yīng)于不同的切割個(gè)數(shù)。

維度為0、1、2、3的所有可能的切割方式，對(duì)應(yīng)于有0、1、2、3個(gè)變量的單調(diào)布爾函數(shù)的個(gè)數(shù)。（圖/Wikipedia）

最近，來自德國(guó)帕德博恩大學(xué)和比利時(shí)魯汶大學(xué)的研究人員，在超級(jí)計(jì)算機(jī)Noctua的幫助下，解開了這個(gè)長(zhǎng)達(dá)數(shù)十年的謎題：他們找到了D(9)，并發(fā)現(xiàn)這個(gè)數(shù)字龐大到共有42位。研究結(jié)果將于今年9月在挪威舉行的布爾函數(shù)及其應(yīng)用國(guó)際研討會(huì)（BFA）上發(fā)表。

  全世界的沙粒 

帕德博恩大學(xué)的計(jì)算機(jī)科學(xué)博士生Lenart Van Hirtum是做出了這項(xiàng)突破的主要研究人員之一。當(dāng)他還在魯汶大學(xué)攻讀計(jì)算機(jī)科學(xué)專業(yè)的研究生時(shí)，他的碩士論文就是如何尋找D(9)。

鑒于D(8)是一個(gè)已經(jīng)高達(dá)23位數(shù)的龐大數(shù)字，Van Hirtum意識(shí)到，要

找到D(9)，必需要有一種高效的計(jì)算方法和一臺(tái)非常快的計(jì)算機(jī)。

Van Hirtum的研究生導(dǎo)師Patrick De Causmaecker曾發(fā)展過一種被稱為“p系數(shù)公式”的技術(shù)。這種技術(shù)可以提供一種無需通過計(jì)數(shù)，而是通過一個(gè)非常大的求和的方法，來計(jì)算戴德金數(shù)。

在普通電腦上，這種方法可以用8分鐘左右的時(shí)間計(jì)算出D(8)；但當(dāng)用它來計(jì)算D(9)時(shí)，時(shí)長(zhǎng)瞬間被拉到數(shù)十萬年。即使專門使用一臺(tái)大型超級(jí)計(jì)算機(jī)，也需要很多年才能完成計(jì)算。

主要的問題就在于這個(gè)公式中項(xiàng)的數(shù)量增長(zhǎng)得非?？?。在新的研究中，研究人員利用公式中的對(duì)稱性，將項(xiàng)的數(shù)量減少到5.5×101?個(gè)。雖然這仍然是一個(gè)巨大的數(shù)字（地球上的沙粒數(shù)量約為7.5×101?），但對(duì)于一臺(tái)現(xiàn)代的超級(jí)計(jì)算機(jī)來說，運(yùn)算5.5×101?并非不可實(shí)現(xiàn)。

  超級(jí)計(jì)算機(jī) 

Van Hirtum意識(shí)到，在普通處理器上計(jì)算這么多項(xiàng)，速度必然會(huì)很慢，而且使用GPU作為目前許多人工智能應(yīng)用程序中的最快硬件加速器技術(shù)，效率并不高。因此，新的解決方法是：使用高度專業(yè)化并行運(yùn)算單元的專用硬件，即所謂的FPGA（現(xiàn)場(chǎng)可編程門陣列）。

Van Hirtum開發(fā)了一個(gè)硬件加速器的初始原型，并開始尋找適合的超級(jí)計(jì)算機(jī)。在這個(gè)過程中，他在帕德伯恩大學(xué)發(fā)現(xiàn)了Noctua 2計(jì)算機(jī)，這臺(tái)計(jì)算機(jī)是世界上擁有最強(qiáng)大的FPGA系統(tǒng)之一。

經(jīng)過幾年的開發(fā)和大約五個(gè)月的運(yùn)行，3月8日，他們終于發(fā)現(xiàn)了第9個(gè)戴德金數(shù)，數(shù)值為：

n=9的戴德金數(shù)。

他們于今年4月在論文預(yù)印網(wǎng)站arXiv上提交了論文。

無獨(dú)有偶，德國(guó)德累斯頓工業(yè)大學(xué)的Christian J?kel也于4月在arXiv上提交了一篇論文。在這篇論文中，J?kel提出了一種利用矩陣乘法和自由分配格的對(duì)稱性來計(jì)算D(9)的新算法，并最終得到了與Van Hirtum相同的數(shù)字。

參考來源：

https://www./en/news-item/123917

10.1109/URTC56832.2022.10002211