Mathematicians Have Found The Ninth Dedekind Number, After 32 Years of Searching
Undeterred after three decades of looking, and with some assistance from a supercomputer, mathematicians have finally discovered a new example of a special integer called a Dedekind number.
Only the ninth of its kind, or D(9), it is calculated to equal 286 386 577 668 298 411 128 469 151 667 598 498 812 366, if you're updating your own records. This 42 digit monster follows the 23-digit D(8) discovered in 1991.
Grasping the concept of a Dedekind number is difficult for non-mathematicians, let alone working it out. In fact, the calculations involved are so complex and involve such huge numbers, it wasn't certain that D(9) would ever be discovered.
"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 computer scientist Lennart Van Hirtum, from the University of Paderborn in Germany back in June, when the number was announced.
At the center of a Dedekind number are Boolean functions, or a kind of logic that selects an output from inputs made up of just two states, such as a true and a false, or a 0 and a 1.
Monotone Boolean functions are those that restrict the logic in such a way that swapping a 0 for a 1 in an input only causes the output to change from a 0 to a 1, and not from a 1 to a 0.
The researchers describe it using red and white colors rather than 1s and 0s, but the idea is the same.
"Basically, you can think of a monotone Boolean function in two, three, and infinite dimensions as a game with an n-dimensional cube," said Van Hirtum.
"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."
The first few are pretty straight forward. Mathematicians count D(1) as just 2, then 3, 6, 20, 168 …
Back in 1991, it took a Cray-2 supercomputer (one of the most powerful supercomputers at the time) and mathematician Doug Wiedemann 200 hours to figure out D(8).
D(9) ended up being almost twice the length of D(8), and required a special kind of supercomputer: one that uses specialized units called Field Programmable Gate Arrays (FPGAs) that can crunch through multiple calculations in parallel. That led the team to the Noctua 2 supercomputer at the University of Paderborn.
"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," says computer scientist Christian Plessl, the head of the Paderborn Center for Parallel Computing (PC2) where Noctua 2 is kept.
Further optimizations were required to give Noctua 2 something to work with. Using symmetries in the formula to make the process more efficient, the researchers gave the supercomputer one huge sum to figure out, a sum that involved 5.5*10^18 terms (the number of grains of sand on Earth is estimated at 7.5*10^18, for comparison).
After five months, Noctua 2 came up with an answer, and we now have D(9). The researchers haven't made any reference to D(10) for the time being – but we can imagine it might take another 32 years to find it.
The paper was presented in September at the International Workshop on Boolean Functions and their Applications (BFA) in Norway.
An earlier version of this article was first published in June 2023.
Mathematicians Have Found The Ninth Dedekind Number, After 32 Years of Searching
