With the so-called ninth Dedekind number, researchers at Paderborn University and KU Leuven have solved a decades-old mathematical mystery, making history with 42 digits.
Since 1991, experts all over the world have been looking for its value. With the help of the Paderborn-based Noctua supercomputer, the scientists were able to determine the exact numbers in the order that they appeared. At the International Workshop on Boolean Functions and Their Applications (BFA) in Norway in September, the findings will be presented.
Lennart Van Hirtum, who was a computer science student at KU Leuven at the time and is now a research associate at the University of Paderborn, started what ended up being a master’s thesis project and is now a huge success. With their work, the scientists join a prestigious group. When mathematician Richard Dedekind defined the problem in 1897, he found earlier numbers in the series. Later, greats of early computer science like Randolph Church and Morgan Ward found them. According to Van Hirtum, “it was doubtful whether it would ever be possible to calculate this number at all, and the calculation of D(9) was an open challenge for 32 years.”
Using a Cray 2, then the most powerful supercomputer, the previous number in the Dedekind sequence, the eighth Dedekind number, was discovered in 1991. “It therefore seemed conceivable to us that it should be possible by now to calculate the ninth number on a large supercomputer,” says Van Hirtum, describing the impetus behind the ambitious project that he initially carried out in collaboration with the advisors of his master’s thesis at KU Leuven.
“The total number of rice grains on the board would be 20 digits—an unfathomable number, but still less than D(8).” When you consider these orders of magnitude, it is evident that finding D(9) would necessitate both an effective computing method and a very fast machine.”
Lennart Van Hirtum,
The so-called monotone Boolean functions are the primary focus of Dedekind numbers, along with grains of sand, chess, and supercomputers. “Essentially, you can think of a monotone Boolean function in two, three, or infinite dimensions as a game with an n-dimensional cube,” states Van Hirtum. The cube is balanced on one corner, and then the remaining corners are colored either red or white. Only one rule applies: White corners should never be placed above red ones. Red and white intersect vertically as a result of this.
The game’s objective is to count the number of distinct cuts. The Dedekind number is defined as their number. Even though it may not appear so, the numbers quickly become enormous. Already, the eighth Dedekind number has 23 digits.
A legend about the game of chess’s inception reveals numbers that are comparable in size but incomparably simpler to calculate. This legend says that the chess game’s creator asked the king for a small amount of rice on each square of the board as a reward: one grain on the first square, two on the second, four on the third, and twice as many on each of the squares that follow. The king quickly realized that this request couldn’t be fulfilled because there wasn’t enough rice in the world.
“There would be 20 digits for the total number of grains of rice on the board, which is unimaginable but still less than D(8).” “It is obvious that both an efficient computational method and a very fast computer would be required to find D(9) when you realize these orders of magnitude,” Van Hirtum stated.
Milestone: The P-coefficient formula, developed by master’s thesis advisor Patrick De Causmaecker, was used by the researchers to convert years into months for D(9) calculations. It provides a method for calculating Dedekind numbers using a very large sum rather than counting. On a standard laptop, this makes it possible to decode D(8) in just eight minutes. However, “What takes D(8) eight minutes becomes D(9) hundreds of thousands of years.” “It would still take many years to complete the calculation even if you used a large supercomputer exclusively for this task,” Van Hirtum points out.
The main issue is that this formula’s number of terms grows extremely quickly. By taking advantage of the formula’s symmetries, we were able to reduce the number of terms in our case to “only” 5.5×1018, which is a huge amount. The computer scientist stated that, in comparison, the number of grains of sand on Earth is approximately 7.5×1018, which is nothing to sneeze at. However, 5.5×1018 operations are quite manageable for a modern supercomputer.
The issue: These terms take a long time to calculate with standard processors, and even though GPUs are currently the fastest hardware accelerator technology for many AI applications, they are not effective for this algorithm.
The remedy: FPGAs—field programmable gate arrays—are application-specific hardware with highly specialized and parallel arithmetic units. Van Hirtum started looking for a supercomputer with the necessary FPGA cards after creating a preliminary prototype for the hardware accelerator. He learned about the Noctua 2 computer at the University of Paderborn’s “Paderborn Center for Parallel Computing (PC2),” which has one of the most powerful FPGA systems in the world.
“When Lennart Van Hirtum and Patrick De Causmaeker contacted us, it was immediately clear to us that we wanted to support this moonshot project,” explains Prof. Dr. Christian Plessl, head of PC2. FPGAs have the potential to be used to solve difficult combinatorial problems, and Noctua 2 is one of the few supercomputers in the world with which the experiment is even possible. Our infrastructure is also put to the test by the extremely high levels of dependability and stability that are required. Lennart and the FPGA expert consulting team collaborated closely to modify and enhance the application for our environment.”
The program was developed for several years before it was put on the supercomputer for about five months. The time had come, then: The scientists discovered the ninth Dedekind number on March 8: 286386577668298411128469151667598498812366.
Van Hirtum is working on his Ph.D. as a fellow of the NHR Graduate School at the Paderborn Center for Parallel Computing, three years after the Dedekind project began. The NHR (National High Performance Computing) Graduate School is the joint graduate school of the NHR centers. On June 27 at 2:00 p.m., he and Patrick De Causmaecker will discuss his extraordinary success in Lecture Hall O2 at the University of Paderborn.
Provided by Universität Paderborn
