After an arduous search spanning three decades, mathematicians have made a groundbreaking discovery with the aid of a supercomputer – they have finally identified a new Dedekind number. This remarkable finding marks the emergence of only the ninth Dedekind number, known as D(9), which can be expressed as 286 386 577 668 298 411 128 469 151 667 598 498 812 366. Substantially larger than its predecessor, the 23-digit D(8) uncovered in 1991, this 42-digit monster number had remained elusive due to the complexity and enormity of the calculations involved.
The Complexity of Dedekind Numbers
For non-mathematicians, understanding Dedekind numbers is a formidable task, let alone calculating them. These calculations are intricate and involve exceedingly large numbers, which initially raised doubts about the possibility of ever determining D(9). Lennart Van Hirtum, a computer scientist from the University of Paderborn in Germany, emphasized the challenge, stating, “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.”
At the core of Dedekind numbers lie Boolean functions, which are a type of logic that selects an output from inputs consisting of only two states, such as true and false or 0 and 1. Monotone Boolean functions, in particular, restrict the logic in a way that changing a 0 to a 1 in an input only causes the output to transition from 0 to 1, rather than from 1 to 0. Although the researchers describe these functions using red and white colors instead of 1s and 0s, the concept remains the same.
Van Hirtum explains, “Basically, you can think of a monotone Boolean function in two, three, and 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.”
The primary rule of the game is to avoid placing a white corner above a red one, as this creates a vertical red-white intersection. The objective is to count the number of different cuts that can be made. The initial Dedekind numbers are relatively straightforward, with D(1) equating to 2, followed by 3, 6, 20, and 168.
The Role of Supercomputers in Unlocking D(9)
In 1991, the discovery of D(8) required the computational power of a Cray-2 supercomputer, one of the most advanced systems at that time, and the expertise of mathematician Doug Wiedemann. The calculation process for D(8) took a staggering 200 hours to complete.
Given that D(9) is nearly twice the length of D(8), a unique type of supercomputer was necessary for its determination. This involved utilizing Field Programmable Gate Arrays (FPGAs), specialized units capable of performing multiple calculations simultaneously. Consequently, the researchers turned to the Noctua 2 supercomputer at the University of Paderborn.
Christian Plessl, the head of the Paderborn Center for Parallel Computing (PC2), explains the significance of Noctua 2, stating, “Solving hard combinatorial problems with FPGAs is a promising field of application and Noctua 2 is one of the few supercomputers worldwide with which the experiment is feasible at all.”
To provide Noctua 2 with a suitable problem to solve, additional optimizations were necessary. By leveraging symmetries within the formula to enhance efficiency, the researchers presented the supercomputer with an immense sum comprising 5.5 x 10^18 terms. To provide context, the estimated number of grains of sand on Earth is 7.5 x 10^18.
After an extensive five-month period, Noctua 2 produced the answer, leading to the revelation of D(9). While the researchers have not yet addressed the possibility of D(10), one can envision that another 32 years may be required to uncover it. The findings of this remarkable research are scheduled to be presented at the International Workshop on Boolean Functions and their Applications (BFA) in Norway in September.
Leave a Reply