What’s so striking about this to me is that if I hadn’t been told the history of the problem, I’d have assumed that something so structured would have an easy solution, as a sum of 2^n terms, or a recurrence relation.
@gregeganSF - here are the 2, 3, 6 and 20 monotone functions of 0, 1, 2, and 3 boolean variables, respectively, as drawn by Tilman Piesk. The functions themselves, ordered by ≤ in the usual way, can themselves be organized into distributive lattices, and that's what we see here!
I hadn't realized that "isotone" meant "monotone", and that these monotone functions correspond to antichains in free boolean lattices (though that's easy to see).
but one cool thing it mentions near the start is that you can count d(n+1) as the number of “intervals” in d(n) as a lattice, as in the image you show here.
For example, you get d(1)=3 by counting the intervals in d(0):
[⊤,⊤], [⊥,⊥], [⊥,⊤]
and d(2)=6 by counting the intervals in d(1):
[⊤,⊤], [⊥,⊥], [⊥,⊤],
[A,⊤], [⊥,A], [A,A]
Jäkel then goes on to define an equivalence relationship on the set of intervals, so you can sum the sizes of those equivalence classes. But I haven’t got much further than that yet ...
@irving@gregeganSF - so maybe the interesting thing Kisielovich did is give a nice formula for whether a boolean function is monotone or not. (Though I don't know if this true, i.e. whether the terms in his sum run through all the boolean functions and equal 1 if they're monotone, 0 otherwise.)
@gregeganSF generally for any poset P, and any number m we can ask how many monotone functions there are from P to the numbers [0, ... m-1], call this M(P, m). The dedekind numbers are M(𝟚ⁿ, 2) where 𝟚 is the 2-element poset.
I think (but don't have a proof!) that M(P, m) is always a polynomial in m with rational coefficients. For example, when P is 𝟚², M(P, m) seems to be (1/12)(m⁴ + 4m³ + 5m² + 2m). Plugging in m=2 gives the dedekind number 6.
@gregeganSF@QuantaMagazine Though I still don’t really understand why it doesn’t have such a recurrence. And indeed the successful computations work by something like sqrt splitting, and I don’t know why there isn’t a way to carry that further and split more.
Add comment