Scientists from KU Leuven and Paderborn University have successfully tackled a mathematical puzzle that had remained unsolved for 32 years. The puzzle involved determining the value of the ninth Dedekind number, which was discovered to have 42 digits. This achievement marks a significant breakthrough in the field of mathematics.
The Dedekind numbers, named after Richard Dedekind, have intrigued mathematicians since their discovery in the 19th century. These numbers form a series of integers that exhibit rapid growth and are closely connected to monotone functions—mathematical functions that generate a binary output based on a binary input. Monotone functions maintain the order of inputs, meaning that if the inputs increase, the output also increases.
To comprehend the nature of Dedekind numbers and their relationship with monotone functions, consider a game involving an n-dimensional cube. Imagine balancing the cube on one corner and assigning the remaining corners either white or red colors.
The game’s rule dictates that a white corner cannot be placed over a red one, resulting in a vertical red-white intersection. The objective of the game is to count the maximum number of intersections or cuts that can be made while adhering to this rule. This count represents the Dedekind number for that specific cube dimension.
For instance, the eighth Dedekind number comprises 23 digits and represents the maximum number of different cuts that can be made in an eight-dimensional cube while following the aforementioned rule. As the dimension of the cube increases, the Dedekind numbers grow exponentially, leading to complex and challenging calculations. These numbers serve as a measure of the structural complexity of monotone Boolean functions in higher dimensions.
Lennart Van Hirtum embarked on the pursuit of deciphering the ninth Dedekind number during his tenure as a computer science master’s student at KU Leuven. Presently, he serves as a research associate at the University of Paderborn.
In 1991, researchers used a Cray 2, one of the most powerful computers at the time, to find the eighth Dedekind number. Encouraged by this previous success, the team aimed to compute the ninth Dedekind number using a supercomputer.
Due to the computational complexity involved in determining the ninth Dedekind number, the team employed the P-coefficient formula, developed by Patrick De Causmaecker, Lennart Van Hirtum’s master’s thesis advisor. This formula enabled the team to calculate the ninth Dedekind number through a large sum instead of individually 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.5×1018—an enormous amount. By comparison, the number of grains of sand on Earth is about 7.5×1018, which is nothing to sneeze at, but for a modern supercomputer, 5.5×1018 operations are quite manageable,” added Van Hirtum.
To enhance computational efficiency, the team developed a specialized hardware accelerator using field programmable gate arrays (FPGAs). These FPGAs are parallel arithmetic units specifically designed for complex mathematical calculations, offering faster processing capabilities.
The computation took place on the Noctua 2 supercomputer, equipped with FPGA systems, at the Paderborn Center for Parallel Computing. Over a period of approximately five months, the team ran the computation, ultimately unveiling the ninth Dedekind number on March 8, 2023: 286386577668298411128469151667598498812366.
Thus, the team was able to calculate the ninth Dedekind number, which has 42 digits, and solve a long-standing mathematical puzzle.
Image Credit: Shutterstock