從1897年德國數(shù)學(xué)家戴德金給出了“戴德金數(shù)”的定義，數(shù)學(xué)家到2023年才找到了9個戴德金數(shù)。該數(shù)字長達42位，耗盡了現(xiàn)在最強的算力，我們何時才能找到第10個戴德金數(shù)？

?

撰文 | 張和持

?

戴德金數(shù)是一串增長非常迅速的數(shù)列，以德國數(shù)學(xué)家戴德金（Richard Dedekind，1831-1916）命名，最初于1897年給出定義。1991年，數(shù)學(xué)家找到了第8個戴德金數(shù)，數(shù)字長達23位。30多年后的2023年，數(shù)學(xué)家終于計算出了序列的第9個，其數(shù)字長達42位。對戴德金數(shù)的計算很大程度上反映了當(dāng)今計算機的算力，因此何時能迎來第10個戴德金數(shù)仍未可知，似乎遙遙無期。

?

何謂戴德金數(shù)

?

?

圖片來自維基百科

?

兩個運算下是封閉的，并且滿足分配律。這樣的代數(shù)結(jié)構(gòu)稱為（分配）格（lattice），而最早研究這一結(jié)構(gòu)的戴德金也被認為是格論的先驅(qū)。格論在抽象代數(shù)、邏輯學(xué)、理論計算機科學(xué)等領(lǐng)域中扮演著相當(dāng)重要的角色。戴德金的格論研究卻在他死后無人問津。直到上世紀30年代，美國數(shù)學(xué)家伯克霍夫（George David Birkhoff）在研究泛代數(shù)等過程中重新發(fā)現(xiàn)了戴德金的工作，從此格論才正式走向歷史的舞臺。戴德金本人未曾找到的第五個戴德金數(shù)也是在這一時期由美國數(shù)學(xué)家邱奇（Alonzo Church）找到。

?

從M(5)到M(8)

?

?

尋找M(9)的長跑

?

FPGA全稱Field Programmable Gate Arrays，中文翻譯為現(xiàn)場可編程邏輯門陣列。簡單來說，這是一種半定制的集成電路，可以利用邏輯合成等工具快速把邏輯電路刻錄上去，這樣就能實現(xiàn)自己設(shè)計的并行算法。范·赫圖姆一邊進行著論文的理論設(shè)計，一邊尋找著擁有FPGA的超級計算機。最終伸出援手的，是德國的帕德博恩大學(xué)。

?

超級計算機Noctua 2坐落于帕德博恩大學(xué)下屬的帕德博恩并行計算中心。這臺電腦擁有著世界上數(shù)一數(shù)二的大規(guī)模FPGA系統(tǒng)，而并行計算中心的負責(zé)人在了解范·赫圖姆和考斯馬克的意圖后，欣然接受了他們的使用請求。對于他們來說，要用超級計算機來解決這樣復(fù)雜的組合問題也是一項極具挑戰(zhàn)性的任務(wù)，對于系統(tǒng)穩(wěn)定性與可靠性提出了不小的要求，同時也是測試設(shè)備的絕佳機會。經(jīng)過數(shù)年的開發(fā)，程序終于在去年開始運行。范·赫圖姆也從魯汶畢業(yè)，進入帕德博恩大學(xué)攻取博士學(xué)位。

?

程序運行了5個月，在2023年3月8日，終于得到了最終結(jié)果

?

?

同時到達終點

?

參考文獻

[1] J?kel, Christian (2023-04-05). "A computation of the ninth Dedekind Number". arXiv:2304.00895 [math.CO]

[2] Van Hirtum, Lennart (2023-04-06). "A computation of D(9) using FPGA Supercomputing". arXiv:2304.03039 [cs.DM].

[3] Patrick De Causmaecker and Stefan De Wannemacker. On the number of antichains of sets in a finite universe, 2014.

[4] Yusun, T.J.: Dedekind numbers and related sequences (2008)

[5] Ninth Dedekind number discovered: Scientists solve long-known problem in mathematics, https://phys.org/news/2023-06-ninth-dedekind-scientists-long-known-problem.html

?

本文受科普中國·星空計劃項目扶持

出品：中國科協(xié)科普部

監(jiān)制：中國科學(xué)技術(shù)出版社有限公司、北京中科星河文化傳媒有限公司