Ninth Dedekind Number Found by Two Independent Groups

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ⁿ 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 Jäkel, 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.

Jäkel 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. Jäkel 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 Jäkel 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 Jäkel’s, and so they hurried to share their own paper a few days later.