Elusive Ninth Dedekind Number Unveiled: Decades-Old Mathematical Enigma Solved

A team of mathematicians from Paderborn University and KU Leuven has accomplished a remarkable feat by calculating the ninth Dedekind number—a sequence of numbers renowned for their immense complexity. Utilizing the formidable Noctua supercomputer and specialized hardware accelerators, the researchers cracked a puzzle that had confounded experts for decades. Previously deemed uncomputable due to its staggering size, the exact value of the ninth Dedekind number has been revealed as 286386577668298411128469151667598498812366.

This groundbreaking achievement comes courtesy of scientists from the Universities of Paderborn and Leuven, who have successfully unraveled a long-standing mathematical mystery. The pursuit of this elusive value had captivated mathematicians worldwide since 1991, and it was believed to be an insurmountable challenge. However, employing the computational prowess of the Noctua supercomputer housed at Paderborn University, the team finally obtained the precise sequence of numbers. The results of their extraordinary endeavor will be unveiled in September at the International Workshop on Boolean Functions and their Applications (BFA) in Norway.

The remarkable journey to the discovery of the ninth Dedekind number began as a master’s thesis project undertaken by Lennart Van Hirtum, a former computer science student at KU Leuven and currently a research associate at the University of Paderborn. Van Hirtum and his colleagues now join the ranks of esteemed mathematicians who have made significant contributions to the series. The original numbers in the sequence were first identified by mathematician Richard Dedekind in 1897, and subsequent breakthroughs were made by luminaries in the early days of computer science, such as Randolph Church and Morgan Ward. “For 32 years, the calculation of D(9) was an open challenge, and it was questionable whether it would ever be possible to calculate this number at all,” commented Van Hirtum.

The previous number in the Dedekind sequence, the eighth Dedekind number, was unveiled in 1991 using the powerful Cray 2 supercomputer, the pinnacle of computing technology at that time. Van Hirtum explained that it seemed plausible to calculate the ninth number using a modern supercomputer of significant capacity. Thus, the ambitious project was initiated in collaboration with Van Hirtum’s master’s thesis advisors at KU Leuven.

The central focus of Dedekind numbers lies in the realm of monotone Boolean functions. Van Hirtum provided an analogy, stating, “Essentially, you can think of a monotone Boolean function in two, three, or infinite dimensions as a game with an n-dimensional cube. You balance the cube on one corner and then color each of the remaining corners either white or red. There is only one rule: you must never place a white corner above a red one. This creates a kind of vertical red-white intersection. The object of the game is to count how many different cuts there are. Their number is what is defined as the Dedekind number. Although it may not seem like it, the numbers grow exponentially throughout the process. For instance, the eighth Dedekind number already contains 23 digits.”

To comprehend the vastness of these numbers, one can draw a comparison to a famous legend surrounding the invention of chess. According to the legend, the game’s creator requested a few grains of rice for each square on the chessboard as a reward: one grain for the first square, two for the second, four for the third, and a doubling of the previous amount for each subsequent square. The king soon realized that fulfilling this request was impossible, as the required quantity of rice exceeded the entire world’s supply. The total number of rice grains on the chessboard would have had 20 digits—an inconceivable amount, yet still smaller than D(8). Understanding the magnitude of these orders of magnitude, it becomes clear that both an efficient computational method and an exceedingly fast computer were imperative to uncover D(9), Van Hirtum emphasized.

To tackle the challenge of computing D(9), the scientists employed a technique known as the P-coefficient formula, developed by Patrick De Causmaecker, Van Hirtum’s master’s thesis advisor. This method offers an alternative approach to calculating Dedekind numbers by means of a massive sum, as opposed to direct enumeration. Consequently, D(8) could be determined within just eight minutes using an ordinary laptop. However, as Van Hirtum pointed out, what takes a mere eight minutes for D(8) translates to hundreds of thousands of years for D(9). Even with the exclusive use of a powerful supercomputer dedicated to this task, the calculation would still require many years to complete. The primary hurdle lies in the exponential growth of terms in the formula. “In our case, by exploiting symmetries in the formula, we managed to reduce the number of terms to a staggering ‘only’ 5.510^18—an enormous quantity. To put it into perspective, the estimated number of grains of sand on Earth is roughly 7.510^18, which is no small figure. Nonetheless, for a modern supercomputer, performing 5.5*10^18 operations is reasonably manageable,” elucidated the computer scientist. The challenge arises from the slow computational speed of these terms on conventional processors, rendering the use of GPUs, which are currently the fastest hardware accelerators for many AI applications, inefficient for this particular algorithm.

To overcome this obstacle, the researchers devised an ingenious solution employing application-specific hardware featuring highly specialized and parallel arithmetic units known as FPGAs (field-programmable gate arrays). Van Hirtum developed an initial prototype for this hardware accelerator and commenced the search for a suitable supercomputer equipped with the required FPGA cards. During this pursuit, he encountered the Noctua 2 computer at the “Paderborn Center for Parallel Computing (PC2)” within the University of Paderborn, home to one of the world’s most potent FPGA systems.

Prof. Dr. Christian Plessl, the head of PC2, explained the university’s enthusiastic support for this ambitious project when Van Hirtum and Patrick De Causmaecker approached them. Recognizing the potential of solving intricate combinatorial problems with FPGAs, they were eager to facilitate the experiment. Noctua 2 stood out as one of the few supercomputers worldwide capable of executing this endeavor. Additionally, the venture posed a challenge for the infrastructure due to the stringent requirements of reliability and stability. A team of FPGA experts collaborated closely with Van Hirtum to tailor and optimize the application for their environment.

After years of development, the program ran on the supercomputer for approximately five months. Finally, on March 8, the scientists achieved their goal and uncovered the ninth Dedekind number: 286386577668298411128469151667598498812366.

Three years after embarking on the Dedekind project, Van Hirtum continues his research as a fellow of the NHR Graduate School at the Paderborn Center for Parallel Computing, where he is actively involved in the development of next-generation hardware tools as part of his Ph.D. The NHR Graduate School serves as the joint graduate school of the NHR centers. Together with Patrick De Causmaecker, Van Hirtum will present their extraordinary success on June 27 at 2 p.m. in Lecture Hall O2 of the University of Paderborn, inviting the interested public to attend this remarkable milestone in mathematics.

Frequently Asked Questions (FAQs) about Mathematics.

More about Mathematics.

• Paderborn University
• KU Leuven
• Noctua supercomputer
• International Workshop on Boolean Functions and their Applications (BFA) (link not available)
• Dedekind number
• Monotone Boolean functions
• Cray 2 supercomputer
• Field-Programmable Gate Arrays (FPGAs)
• Paderborn Center for Parallel Computing (PC2)
• NHR Graduate School