Mathematicians have been waiting 32 years to find out the value of the ninth Dedekind number, part of a series of numbers that was first discovered in the 19th century. This spring twoseparate teams calculated the number in preprint papers released within weeks of each other. “What a coincidence that two different teams do it at the same time after more than 30 years,” says Christian Jäkel of the Dresden University of Technology (TU Dresden) in Germany, who posted his calculation on the preprint server arXiv.org on April 3, three days ahead of the other group.
Each term in the Dedekind sequence is the count of a collection of functions that can analyze a set of variables, such as the set of x and y, or {x, y}, and give an answer of true or false. For example, a function that checks to see if a set contains x would answer true for the {x} and {x, y} but false for {y}. The nth Dedekind number, written as D(n), counts functions that take in sets of up to n variables. So the second Dedekind number only counts functions that can process subsets of {x, y}, the third Dedekind number counts functions on subsets of {x, y, z}, and so on.
To satisfy the Dedekind conditions and count toward the tally of functions, true-false functions must follow certain rules. For instance, if a function is true for {x, y}, it must also be true for {x, y, z} and {x, y, z, w}. In other words, if you add an element to a true set, it has to remain true. Lennart Van Hirtum, a co-author of the solution posted on April 6 and now a Ph.D. student at Paderborn University in Germany, suggests imagining this requirement with a cube that rests precariously on just one corner. Its corners are all colored either white or red, and the nth Dedekind number counts the number of colorings where no white point is topped by a red point. “Any white corner cannot have a red corner above. That’s the only rule,” he says.
On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
That special requirement makes the Dedekind numbers difficult to compute. Otherwise, you could just calculate all the possible ways to assign true-false values to sets, a number that’s around 22^n for subsets of n variables. That’s a huge number—around 4.3 trillion by the time n = 5—but one that is straightforward to calculate. In contrast, there is no simple formula to describe the Dedekind numbers.
Because of the gargantuan numbers involved, calculating Dedekind numbers has historically been closely entwined with technological progress. “It is a test for state-of-the-art computer technology” as well as mathematics, says Patrick De Causmaecker,one of the authors on the calculation published on April 6 and a computer scientist at the Catholic University of Leuven (KU Leuven) in Belgium. In 1897 German mathematician Richard Dedekind introduced the Dedekind numbers and calculated the first four, starting with D(0): 2, 3, 6, 20. Throughout the 20th century, new Dedekind numbers popped up intermittently, usually with decades of waiting in between. The ninth number in the sequence, called the eighth Dedekind number, D(8), was published in 1991 by the late mathematician Doug Wiedemann. It is 56,130,437,228,687,557,907,788, or around 5.6 x 1022.
“Historically, a new Dedekind number has been discovered every 20 to 30 years,”says Bartłomiej Pawelski, a computer scientist at University of Gdansk in Poland. It’s “a computational challenge, which is just fun to discover.”
De Causmaecker began working with Van Hirtum, then a master’s student at KU Leuven, on D(9) in 2021 as part of the latter’s thesis project. “One of the earliest meetings, I asked Patrick if he thought we would do it,” Van Hirtum says. “And he said, ‘Probably not.’” As predicted, Van Hirtum’s thesis did not include a calculation of D(9). The formula he and De Causmaecker had come up with was just too computationally heavy.
Van Hirtum had ideas, however. “He really got bitten by this Dedekind number problem, and he couldn’t get rid of it,” De Causmaecker says. Van Hirtum wanted to try using a type of computer chip called a field-programmable gate array (FPGA), which the researchers could customize to make their program run far more efficiently. He and De Causmaecker identified a supercomputing center at Paderborn University that could help them develop and run their customized hardware, and Van Hirtum spent the next year and a half working on the project unpaid—motivated by pure curiosity about whether his idea would work.
Near the end of 2022, the researchers were finally ready to run their program. Five months later, on March 8, they had a number: 286,386,577,668,298,411,128,469,151,667,598,498,812,366, or around 2.86 x 1041. But they couldn’t be sure that it was correct. Cosmic rays—radiation particles that come from space—can interfere with FPGA chips and change the results of calculations. “We calculated there was a 25 to 30 percent chance that this had happened,” Van Hirtum says. To make sure their computation was right, they gave their program a second go. If they got the same number again, they could be almost certain it was right. They expected to wait another five months, at least, for that assurance.
But on April 3 Jäkel gave them the surprise of their lives when he posted his paper online, sharing his value of D(9)—and confirming theirs in the process. Both teams “found ways to massively parallelize the calculations,” Pawelski says. “It was a great idea.”
Jäkel, a graduate student at TU Dresden with a day job as a software developer, had been working nights and weekends on the problem since 2017. His method couldn’t have been more different than Van Hirtum and De Causmaecker’s. He’d worked out a formula for D(9) that used matrices—arrays of numbers that you can multiply and add together. “This matrix multiplication is something very, very established,” Jäkel says. “It’s the best-studied problem in computer science.”Because his formula was optimized for traditional computer hardware, he didn’t need a supercomputer. His program, which he set running in March 2022, took about a month to come up with a value for D(9).
Jäkel, too, was unsure of his value when he first calculated it. He didn’t need to worry about cosmic rays, but he couldn’t prove that his program didn’t somehow have a bug. “I did everything I could in my power,” he says. “I observed this calculation very carefully.”But short of coming up with a different method, there was no hope of eliminating all doubt. That is, until Van Hirtum, De Causmaecker and their co-authors posted their paper.
“I was shocked, or surprised—happy, also. Because I had this number, and I thought it takes ten years or so to recompute it,” Jäkel says. “Three days later, I had the confirmation.”
It will likely be another long wait for the 10th Dedekind number, which is sure to be many times larger than D(9). “I think it’s pretty safe to say the 10th one will not be calculated soon, and by soon, I mean the next few hundred years,” Van Hirtum says. De Causmaecker, however, is more optimistic. “I hope to live until the 10th is computed,” he says.