Functions that only go up

A truth function of $n$ letters is a choice of true or false at each corner of a cube, so there are $2^{2^n}$ of them. There is no mystery about that count. A natural restriction does make a mystery. Call a function monotone if turning a letter from false to true can never turn the output from true to false. Equivalently, the set of corners where the function is true is closed upward: from any true corner, all corners above it are true.

The monotone functions are exactly those that can be written with and and or and no negation, together with the two constants. So they are one of the classes of Post’s lattice that an incomplete set of connectives ran into. They are the formulas that can only say more when more is true. They are also, in another language, the antichains of subsets, the families in which no set contains another: take the minimal true corners, and they determine the function. And they are the ideals of a Boolean lattice, and the free distributive lattices on $n$ generators, which is how Richard Dedekind came across them in 1897.

He counted the free distributive lattice on four generators, finding 168 elements with the constants included, and asked the next question. How many for five? It took 43 years for the answer. The count is now called the Dedekind number $M(n)$, and it has been extended one letter at a time through the twentieth century and into this one.

For three letters they can all be drawn. There are the two constants, and six forms of a single letter or two. Then there are the two forms of “at least two of the three”, which are the majority function and its relatives, and so on. Twenty of 256. They are a small, tidy family, and it is natural to expect a neat count. But there is no formula, and the numbers show why.

Splitting on one letter #

The basic recursion is a beautiful observation. Take a function of $n + 1$ letters and look at the last letter. Setting it false gives a function $f$ of $n$ letters, and setting it true gives another, $g$. The full function is monotone exactly when $f$ and $g$ are monotone and $f \le g$ at every input, since turning the last letter on must not turn anything off. So

$$M(n + 1) = \#\{(f, g) : f \le g\}.$$

The six functions of two letters are 0, $a \wedge b$, $a$, $b$, $a \vee b$ and 1, and the order among them has twenty pairs. So the partial order of the functions at level $n$ gives the count at level $n + 1$. Listing the functions at level $n$ and testing each pair verifies $M(3) = 20$ and $M(4) = 168$.

Two splits at once do much better. A function of $n + 2$ letters is a square of four functions of $n$ letters, with the two middle ones $p$ and $q$ between the bottom $f$ and the top $g$. Choose $p$ and $q$ first; the number of possible $f$ is the count of functions below $p \wedge q$, and the number of possible $g$ is the count of functions above $p \vee q$. So

$$M(n + 2) = \sum_{p, q} \big|\{f \le p \wedge q\}\big| \cdot \big|\{g \ge p \vee q\}\big|.$$

That needs only the table for $n$ letters: for $n = 4$, 168 functions, a table of 28,224 entries, each a quick lookup. It gives 7,828,354, in a fraction of a second, and that is the value that needed a hard computation in 1946. The method for $M(5)$ from pairs gives 7,581. Both agree with their published values, and they check each other because the pair count of 7,581 uses the first method alone. The later records used variants of the same idea, with larger and larger symmetric reductions.

The numbers #

Those are the numbers, and it is clear that they cannot be approached in the same way for very long. Alonzo Church found $M(5)$ in 1940 and Morgan Ward found $M(6)$ in 1946. Church returned for $M(7)$ in 1965, using an electronic computer. Doug Wiedemann found $M(8)$ in 1991, on a large parallel machine of the day, and it took him 200 hours. Then for over thirty years nothing moved. In 2023 two teams independently found $M(9)$, a 42-digit number, in the same month. Christian Jäkel used a large cluster of graphics processors with a method exploiting a formula by Pawelski; Lennart Van Hirtum and collaborators used specially programmed circuits at Paderborn. Their results agreed. It is a striking confirmation, since a machine error in a five-month computation would be very hard to spot otherwise.

$M(10)$ appears to be beyond any method now known. Each further letter squares the size of the function table, roughly, and the sum that gives $M(n + 2)$ from the table of size $M(n)$ has about $M(n)^2$ terms. Symmetry under permuting the letters reduces this by a factor of about $n!^2$, but that has no effect on the exponential growth. Getting $M(9)$ from $M(7)$ required summing over $2.4 \times 10^{12}$ squared, with reduction, and $M(10)$ would be a similar sum over the $5.6 \times 10^{22}$ functions of eight letters.

The same count in four other costumes #

The number has several other descriptions, and each makes a different part of the problem look natural. Dedekind’s was algebraic. Take $n$ letters and form everything that can be written with and and or, identifying two expressions when the distributive law says they are equal. For two letters that gives $a \wedge b$, $a$, $b$ and $a \vee b$, four elements, and adding the two constants makes six. This is the free distributive lattice on $n$ generators, and it has no further elements because any expression can be put into a normal form, which is a list of minimal true corners.

The second is about sets: an antichain, as noted. The third is about shapes. The false inputs of a monotone function are closed downward, and a family of sets closed under taking subsets is exactly an abstract simplicial complex, the combinatorial object underlying a surface’s Euler characteristic. So $M(n)$ counts all the simplicial complexes on $n$ labelled points, including the two degenerate ones. A triangle with its interior, a triangle with just its edges and three isolated points are three of the functions of three letters. The fourth is about games. A monotone function of $n$ letters is a simple game in the sense of voting theory, or nearly so, in which the true inputs are the winning coalitions and adding a member cannot lose. So the count is also the number of possible rules for deciding a vote among $n$ voters in which a new supporter never harms a motion, which is the setting in which weighted voting lives. Each of these subjects has reinvented the count for its own purposes and has had to give up at around the same point.

Why the middle layer #

The logarithm of the count is the informative quantity, and for it there is a real theorem. There is a clear lower bound. Take any family of $\binom{n}{\lfloor n/2 \rfloor}$ corners at the middle layer of the cube: every subset of that layer is an antichain, since no set in a layer can contain another. So there are at least $2^{\binom{n}{n/2}}$ monotone functions.

Daniel Kleitman proved in 1969 that this is nearly the truth: $\log_2 M(n) = (1 + o(1))\binom{n}{\lfloor n/2 \rfloor}$. At nine letters, the logarithm is 137.7, against a middle layer of 126, a ratio of 1.09. At six it is 22.9 against 20, a ratio of 1.15. Georges Hansel had given the first strong upper bound in 1966, using symmetric chain decompositions: split the cube into chains that each cross the middle, and each chain can only flip from false to true once, which at most contributes a factor of 3 for each chain after careful ordering. So $M(n) \le 3^{\binom{n}{n/2}}$. Kleitman improved the 3 towards 2, and Aleksei Korshunov gave in 1981 an exact asymptotic formula in terms of what happens in the layers beside the middle.

The picture behind all this is that a typical monotone function switches from false to true at or about the middle layer, and it behaves almost independently on that layer.

For five letters, this is visible in the exact histogram, computed by combining pairs. The number of functions with $w$ true inputs rises to 621 at $w = 16$ and falls symmetrically. The symmetry comes from a neat duality: swap true and false, and flip the cube upside down, and a monotone function becomes another monotone function. It takes $w$ to $32 - w$. So half of them have fewer than half the cube true, and most have very close to half. That is the reason the middle layer dominates: almost all the freedom is a choice of true or false on one layer, and the rest is determined by monotonicity. As $n$ grows, the histogram becomes more peaked.

The last column of this table measures how much a monotone function saves. An arbitrary function of $n$ letters needs one bit for each input. A monotone one needs 0.54 bits at three letters, 0.36 at six, 0.27 at nine. The trend is the middle layer’s share of the cube, $\binom{n}{n/2}/2^n \approx \sqrt{2/(\pi n)}$, and it falls as one over the square root of $n$. That is a very slow fall, and it means that monotone functions, rare as they are, are still a huge family.

Functions up to renaming the letters #

Much of the recent effort goes into symmetry, and the small cases show how much it can save. Two monotone functions that differ only in the names of their letters are the same in all that matters, so the search can work with one representative of each class. At three letters the 20 functions fall into 10 classes. At four the 168 fall into 30, and at five the 7,581 fall into 210, numbers computed here by renaming letters in every possible way. By the method that counted truth tables up to renaming, that class count could also come from a sum over the permutations of the letters. Since most functions have no symmetry, the factor saved approaches $n!$, and at nine letters that is a saving of $362{,}880$. The record computations use this twice over, once on each side of a sum, and it is the reason a sum with $10^{25}$ terms could be carried out.

A class also gives a good sense of what a typical function looks like. At three letters every class has a short formula, such as the majority of the three, or “$a$ and ($b$ or $c$)”. A typical monotone function of nine letters has no such description. Its minimal true corners form a large antichain near the middle layer, and writing down the formula means writing down most of that antichain. It has about as many terms as the layer has corners, so a typical monotone function is a long list. Only a thin set of them, the ones a person would actually think of, have a formula shorter than the list.

There is a further way of counting by antichains that shows how the size of the middle layer controls things. An antichain in the cube of four letters has at most $\binom{4}{2} = 6$ sets by Sperner’s theorem. The 168 functions correspond to all 168 antichains, one of which is empty, and a single-set antichain gives a simple function such as $a \wedge b$. The six-set antichain on the middle layer gives “at least two of the four”. Between those extremes are the combinations, and most of them are subsets of a layer or nearly so. So the count is really a count of subsets of a layer, with corrections for families that straddle two layers. That is the structure Korshunov’s formula expands, and it is what Kleitman’s theorem says at leading order.

Monotone functions and their circuits #

There is a deep reason to care about them beyond counting. A monotone function can be computed by a formula or a circuit without negation. But does it pay to use negation? Almost every lower bound in complexity theory begins by trying to answer this question for a function of interest, because monotone circuits are simpler to analyse than general ones.

Alexander Razborov showed in 1985 that testing whether a graph has a large clique, which is a monotone function of its edges, needs monotone circuits of a size growing faster than any polynomial. The formula that cannot share touches the same territory. This was a dramatic advance at the time, and many people hoped that it would extend to general circuits. Then Razborov showed that it could not extend directly. For matching in a bipartite graph, a monotone function that has a fast general algorithm, monotone circuits need a superpolynomial size. So negation can give a superpolynomial speed-up on a monotone function. Éva Tardos then gave an example in which the gap is exponential. So the fact that a function is monotone does not imply that the best way to compute it is monotone.

Counting relates to this through Shannon’s argument, in the count of gates a truth table needs. Since there are $2^{2^n}$ functions and few circuits, most functions need large circuits. Applying that to monotone circuits and $M(n)$, most monotone functions need monotone circuits with about $\binom{n}{n/2}/n$ gates, by a count that depends directly on Kleitman’s theorem. The theorem about the count becomes a statement about how hard typical monotone functions are.

There are also links with threshold functions, the monotone functions cut off from the cube by a plane. There are far fewer of them. At $n = 4$ only 150 of the 168 monotone functions are realised with non-negative weights, and as $n$ grows the share drops rapidly to nothing, because $M(n)$ grows doubly exponentially, while the number of threshold functions grows only as $2^{n^2}$. So being monotone says very little about being simple, and threshold functions are vanishingly rare among them.

What has been computed and what quoted #

The values to $M(6)$ were computed exactly in two separate ways, using the formula with pairs and the formula with intervals. The histogram for five letters covers all 7,581 functions and was checked to sum to that total. $M(7)$, $M(8)$ and $M(9)$ are taken from the published papers, as are the methods used to find them and the times they took. Those values have been checked independently of one another by their authors through congruences and by the second team’s agreement.

The asymptotic statements, Kleitman’s theorem, Hansel’s bound, Korshunov’s formula, are cited and were not reproved, though the ratios in the figure are consistent with them, and they say nothing exact at the small sizes shown. The count of threshold functions and the comparison with monotone functions has been stated without computing it, and the circuit results by Razborov and Tardos are quoted without any attempt at a demonstration. It would be easy to read too much into the table of bits per input. It records a ratio, for a sequence with ten known terms.

Still open: the tenth number, and any formula #

What is $M(10)$? The logarithm should be a little above the middle layer’s 252, which suggests a number of around eighty digits, and a direct computation would need a sum over more than $10^{22}$ terms even after symmetric reductions, each needing a difficult count. There is no sign of a qualitatively better method. Congruences are known: $M(n)$ is even apart from the term $M(1) = 3$, and others follow from symmetric group actions, but these only check a computed value and cannot produce one.

Is there any closed expression at all? There are formulae for $M(n)$ as finite sums, due to Kisielewicz and others, which are exact and essentially no help at all, since they have as many terms as the problem has functions. Whether $M(n)$ has a generating function with useful properties is unknown, and given the doubly exponential growth it seems unlikely.

The middle layer decides #

A monotone function of $n + 1$ letters is a pair $f \le g$ of monotone functions of $n$, and a function of $n + 2$ letters is a sum over pairs of counts below and above. This turns 168 functions into 7,828,354 in a fraction of a second, and it took until 2023 to turn it into the ninth number, of 42 digits. Almost all the freedom lies on the middle layer of the cube, so the logarithm of the count is close to $\binom{n}{n/2}$, and the histogram of true inputs piles up at half the cube.

A question this simple has only ten known terms after 126 years, because the same fact that makes monotone functions easy to describe also makes them too many to count. A count that grows doubly exponentially leaves very little room for any method that has to look at each one, and a formula that avoids looking has not been found.