Supercomputer reveals ninth Dedekind number, solving decades-old maths problem

Lennart Van Hirtum started working on the ninth Dedekind number as a master's student in computer science at KU Leuven. He is currently a research associate at the University of Paderborn. "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," said Van Hirtum in a press release. 

Dedekind numbers & monotone functions

Dedekind numbers are a rapidly growing series of integers. They are closely related to monotone functions, which are mathematical functions that take a binary input (0 or 1) and produce a binary output. 

Montone functions are so called because they preserve the order in the inputs, meaning that if the inputs increase, so will the output. 

To understand what Dedekind numbers are and how they relate to monotone functions, let us consider a game with an n-dimensional cube. Imagine balancing the cube on one corner and coloring each of the remaining corners with white or red. 

One rule needs to be followed: A white corner cannot be placed over a red one. This rule creates a vertical red-white intersection. Now, the game's objective is to count the number of intersections or cuts that can be made. And this is the Dedekind number. 

The Dedekind number represents the maximum possible cuts or intersections that can be made in an n-dimensional cube while satisfying the rule. Here the n-dimensions of the cube correspond to the nth Dedekind number. 

For example, the eighth Dedekind number has 23 digits, which is the maximum number of different cuts that be made in an eight-dimensional cube while following the rule. 

The Dedekind numbers grow quickly as the dimension of the cube increases, making the calculations complex and challenging. They quantify the complexity of the structure of monotone Boolean functions in higher dimensions.

Calculating the ninth Dedekind number

The eighth Dedekind number was found in 1991, using the most powerful computer of that time—a Cray 2. This motivated the team to calculate the ninth Dedekind number on a supercomputer. 

Given the computational complexity of calculating the ninth Dedekind number of D(9), the team used the P-coefficient formula developed by Van Hirtum's master's thesis advisor, Patrick De Causmaecker. The P-coefficient procedure allowed the team to calculate the ninth Dedekind number through a large sum instead of counting each term in the series. 

"In our case, by exploiting symmetries in the formula, we were able to reduce the number of terms to 'only' 5.5x10¹⁸—an enormous amount. By comparison, the number of grains of sand on Earth is about 7.5x10¹⁸, which is nothing to sneeze at, but for a modern supercomputer, 5.5x10¹⁸ operations are quite manageable," said Van Hirtum.

The team developed an application-specific hardware accelerator using field programmable gate arrays (FPGAs) to increase computational efficiency. FPGAs are highly specialized and parallel arithmetic units that can perform computations in parallel. They offer faster processing and are particularly suited for complex mathematical calculations.

The computation was performed on the Noctua 2 supercomputer, equipped with FPGA systems, at the Paderborn Center for Parallel Computing. 

The team ran the computation on this supercomputer for approximately five months. On March 8, 2023, the team found the ninth Dedekind number: 286386577668298411128469151667598498812366.

Thus, the team was able to solve a long-remained mathematical mystery and compute the ninth Dedekind number having 42 digits.

This article was written and edited by a human, with the assistance of Generative AI tools. Find out more about our policy on AI-powered writing here.