https://www.quantamagazine.org/ninth-dedekind-number-found-by-two-independent-groups-20230801/ We care about your data, and we'd like to use cookies to give you a smooth browsing experience. Please agree and read more about our privacy policy.Agree * Physics * Mathematics * Biology * Computer Science * Topics * Archive * * * * Ninth Dedekind Number Found by Two Independent Groups Read Later Share Copied! * Comments * Read Later Read Later set theory Ninth Dedekind Number Found by Two Independent Groups By Rachel Crowell August 1, 2023 The numbers count a variety of seemingly unrelated mathematical structures. Read Later [NewDedekin] Allison Li/Quanta Magazine [Crowell_Ra] By Rachel Crowell Contributing Writer --------------------------------------------------------------------- August 1, 2023 --------------------------------------------------------------------- View PDF/Print Mode Abstractions blogcombinatoricslogicmathematicsset theoryAll topics Give the gifts of science and math this holiday season.Give the gifts of science and math this holiday season. Introduction Richard Dedekind was a 19th-century mathematical giant, responsible for reshaping the field right down to its foundations. He was the first to give a rigorous definition of infinity; he also came up with the definition of the real numbers that form the basis of much of modern mathematics. In 1897, he published an investigation into a certain numerical pattern. That work led him to define a sequence now called the Dedekind numbers, which count structures in a variety of seemingly unrelated mathematical fields. He ended his paper with the observation that "the number of elements contained in these groups seems to grow very rapidly." He was correct about their rapid growth. In that paper, he figured out the first four terms before giving up. He wasn't even sure if his calculation for the fourth term in the sequence -- 166 -- was correct. (He had it right, even though the number is now usually given as 168, taking into account a couple of trivial examples that Dedekind didn't bother with.) The 5th and 6th terms were calculated in the 1940s, and the 7th in 1965. In 1991, Doug Wiedemann, who worked for the Thinking Machines Corporation, one of the leading supercomputer companies of the time, ran a 200-hour computation to figure out that the eighth Dedekind number, d(8), is 56,130,437,228,687,557,907,788. Rapid growth indeed. That's where things stood until April of this year, when two sets of researchers independently posted their calculations of the ninth Dedekind number, d(9), which is 42 digits long. They used different techniques, and each was unaware of the other. The two papers were posted within three days of each other. The Fear of All Sums There are three main ways to define the Dedekind numbers: as the colors of the corners of an n-dimensional cube; in the language of set theory; and using logic. Lennart Van Hirtum, a graduate student at Paderborn University in Germany and the lead author of one of the April papers, says he prefers the cube explanation, which is the most visual one. You are given two colors, say blue and white. Balance the cube on a corner and assign a color to each corner, following the rule that a blue corner can never appear lower than a white one (though they can be on the same level). How many different colorings are possible? For an n -dimensional cube, that number is the nth Dedekind number d(n). Another way of thinking of the Dedekind number is in set-theoretic terms. Think of a set with n elements, say the numbers {1, 2, 3, 4, 5, ... n}. That set has 2^n different subsets, which form a mathematical structure called a lattice. Now collect those subsets according to the following rule: No subset in your collection can be a part of another subset in the collection. Such a collection is called an anti-chain, because it combines points on the lattice in a way that doesn't form a chain. (For example, {{1}, {2, 3}, {3, 4, 5}} forms an anti-chain.) The number of anti-chains for a given n is, again, the Dedekind number. The last common way of defining Dedekind numbers is in terms of Boolean functions. These take in a number of logical bits -- each either 0 or 1 -- and then give a simple one-bit output. Imagine you have a four-bit Boolean function and you start out by inputting all zeros: 0000. Your function returns either a 0 or a 1. Now start flipping your input bits, one at a time, from 0 to 1. At some point, your output may flip from 0 to 1. A monotone Boolean function is one whose output, once it switches to 1, never goes back to 0, no matter what order the inputs are flipped in. The number of such functions for n input variables is, you guessed it, the Dedekind number d(n). Regardless of which definition you use, the combinations quickly grow unmanageable. If you were to try to figure out d(9) by brute force, you would use more computer memory than exists on Earth, noted Christian Jakel, a graduate student at the Dresden University of Technology, who wrote the other April paper. The Hunt for Dedekind Numbers The authors of the two papers used different methods to simplify their calculations. Jakel considered a mathematical object called the free distributive lattice, which can be used to organize all the anti-chains of a set with n elements. (There are d(n) of them.) These lattices display certain symmetries. Jakel used those symmetries to define particular matrices (square arrays of numbers) which he could then multiply and add together to calculate not only d(n), but also d(n + 1), d(n + 2), d(n + 3) and d(n + 4). This let him leapfrog ahead. By performing his calculations on the 168 different anti-chains of a four-element set, he could calculate d(4 + 4), or d(8). And he could do it in just three seconds. He used the same trick to calculate d(5 + 4), or d(9), based on the 7,581 antichains of the five-element set. Even though he used an array of Nvidia graphics processing units which are particularly effective at matrix multiplication, the calculation took 28 days. After Jakel posted his preprint with a 42-digit answer for d(9), Van Hirtum, some 200 miles to the west in Paderborn, realized it was time to stop double-checking his work. Van Hirtum and his colleagues had calculated d(9) in March but were running their algorithm a second time, just in case a stray cosmic ray had thrown off their sums. But their number was the same as Jakel's, and so they hurried to share their own paper a few days later. Share this article Copied! --------------------------------------------------------------------- Newsletter Get Quanta Magazine delivered to your inbox Subscribe now Recent newsletters [JaekelHirt] Christian Jakel (left) independently figured out the 9th Dedekind number at almost the exact same time as Lennart Van Hirtum (center) and Patrick De Causmaecker. From left: Mitsuki Noma; Frank Korsch/Paderborn University; Anneleen De Causmaecker Introduction Back in 2014, Patrick De Causmaecker, a professor at KU Leuven University in Belgium, together with his collaborator Stefan De Wannemacker, had come up with a formula for counting anti-chains. That formula grows very quickly. Van Hirtum, while studying under De Causmaecker, figured out how to simplify it for his master's thesis. This still left a daunting calculation. After letting the calculations run on the Paderborn supercomputer for three months, Van Hirtum, De Causmaecker and their colleagues also had an answer. Both papers concluded that d(9) = 286,386,577,668,298,411,128,469,151,667,598,498,812,366. De Causmaecker said he thinks exponential growth in computing power will make it possible to calculate d(10) within the next few decades. But Jakel said, "I think it's very unlikely this will happen soon. You need something new. I have no idea how this would be possible. New hardware, new algorithms." Jakel and Van Hirtum both say they are, for now, giving up the chase and turning back to their doctoral dissertations. Van Hirtum's is on hardware design, while Jakel's is on optimization problems in algebraic structures. Jakel said he would have written up his thesis two years ago if not for the distraction of d(9). "I think I need a break," he said. [Crowell_Ra] By Rachel Crowell Contributing Writer --------------------------------------------------------------------- August 1, 2023 --------------------------------------------------------------------- View PDF/Print Mode Abstractions blogcombinatoricslogicmathematicsset theoryAll topics Give the gifts of science and math this holiday season.Give the gifts of science and math this holiday season. Share this article Copied! --------------------------------------------------------------------- Newsletter Get Quanta Magazine delivered to your inbox Subscribe now Recent newsletters The Quanta Newsletter Get highlights of the most important news delivered to your email inbox Email[ ] Subscribe Recent newsletters Comment on this article Quanta Magazine moderates comments to facilitate an informed, substantive, civil conversation. Abusive, profane, self-promotional, misleading, incoherent or off-topic comments will be rejected. Moderators are staffed during regular business hours (New York time) and can only accept comments written in English. Show comments [Epistasis-] Next article How Genetic Surprises Complicate the Old Doctrine of DNA * About Quanta * Archive * Contact Us * Terms & Conditions * Privacy Policy --------------------------------------------------------------------- All Rights Reserved (c) 2023 An editorially independent publication supported by the Simons Foundation.