Relations between Powers of Dedekind Numbers and Exponential Sums Related to Them

Frank a Campo Seilerwall 33 D-41747 Viersen Germany

                acampo.frank@gmail.com

Abstract

Let D^{2}(Q) denote the downset-lattice of the downset-lattice of the finite poset Q and let d^{2}(Q) denote the cardinality of D^{2}(Q). We investigate relations between the numbers d^{2}(A_{m} + Q) and their powers, where A_{m} is the antichain with m elements and A_{m} + Q the direct sum of A_{m} and Q. In particular, we prove the inequality d^{2}(Q)^{3} < d^{2}(A_{1} + Q)^{2} based on the construction of a one-to-one mapping between sets of homomorphisms. Furthermore, we derive equations and inequalities between the numbers d^{2}(A_{m} + Q) and exponential sums of downset sizes and interval sizes related to D^{2}(A_{m} + Q). We apply these results in a comparison of the computational times of algorithms for the calculation of the Dedekind numbers d^{2}(A_{m}), including a new algorithm.

1 Introduction

In 1897, Richard Dedekind constructed the free distributive lattice with k generators [10]. The cardinality of this universal algebraic object is called “the k^{th} Dedekind number”. Already Dedekind realized that these numbers grow heavily with k [10], and due to the extreme computational complexity of their calculation, their values are known only for 0 ≤ k ≤ 8 (Table 1).

Dedekind knew the numbers for k = 3 and k = 4 [10] (I do not differentiate between the free distributive lattice and its lattice-theoretical completion here). The calculation of

k  k^{th} Dedekind number
0  2
1  3
2  6
3  20
4  168
5  7581
6  7828354
7  2414682040998
8 56130437228687557907788

Table 1: Known Dedekind numbers.

the 5^{th} Dedekind number in 1940 is due to Church [6]. Ward [27] computed the 6^{th} one in 1946 and confirmed Church’s result. The calculation of the 7^{th} Dedekind number in 1965 was done again by Church [7], and later on repeated by Berman and Köhler in 1976 [3], and by Markowsky in 1989 [21]. Finally, Wiedemann computed the 8^{th} one in 1991 [28], and his result was confirmed by Fidytek et al. in 2001 [11]. Also the work of Lunnon in 1971 has to be mentioned [20], even if he did not succeed in calculating the correct value of the 7^{th} Dedekind number. In 1988, Kisielewicz presented a formula in closed form [16], but it is far too complicated to be evaluated even for small values of k. The sequence number of Dedekind numbers in the OEIS [26] is \underline{A000372}.

The Dedekind numbers are also the number of monotone Boolean functions with k variables and the number of antichains (and downsets) of the power set of a k-element set [3, 4, 20, 21]. The problem of calculating Dedekind numbers can therefore also be tackled by counting antichains, and this task is in a natural way broken down into the sub-tasks of counting antichains with exactly ℓ elements. In 1968, Riviere developed formulas for ℓ ≤ 3 [22]. The step to ℓ = 4 was done by Cvetković in 1972 [8], and Arocha solved the cases ℓ = 5, 6 in 1982 [1]. Kilibarda and Jovović developed the method further and presented explicit formulas for 1 ≤ ℓ ≤ 10 in 2003 [15]. Based on the work of Pippenger in 1999 [23] and Kahn in 2002 [14], Carroll et al. extended the enumeration of antichains to more general structures in 2009 [5]. The approach for counting monotone Boolean functions presented by Bakoev in 2012 [2] is still under development.

Because Dedekind numbers are so difficult to calculate, estimates and asymptotic estimates have found their interest, too. The first ones are due to Gilbert in 1954 [12]. Based on the pioneering work of Hansel [13] in 1966, Kleitman [17] and Kleitman and Markowsky [18] developed in 1969 and 1975 better and better estimates by refining the demanding construction of monotone functions on certain collections of chains step by step. Their estimates were improved by Korshunov in 1981 [19], followed by the work of Sapozhenko in 1989 [24].

Historically, the focus was on the calculation of Dedekind numbers and on estimates for them. The present paper deals with relations between powers of a slight generalization of Dedekind numbers and exponential sums related to them. Let D^{2}(Q) denote the downsetlattice of the downset-lattice of the finite poset Q and let d^{2}(Q) denote the cardinality of D^{2}(Q). With A_{m} being the antichain with m elements, the subject of the present paper is the numbers d^{2}(A_{m} + Q), where A_{m} + Q is the direct sum of A_{m} and Q.

Section 2 contains the notational apparatus and the required facts about downsets and downset-lattices. In Section 3.1, we construct in Theorem 5 a one-to-one mapping between sets of homomorphisms, and this mapping is used to prove the relation d^{2}(Q)^{3} < d^{2}(A_{1} +Q)^{2} and other inequalities. In Section 3.2, we investigate the relations between the numbers d^{2}(A_{m}+Q) and the exponential sums ∑_{𝔄∈D^{2}(A_{m}+Q)} δ(𝔄)^{k} and ∑_{𝔄∈D^{2}(A_{m}+Q)} ∑_{𝔅∈↓ 𝔄} ι[𝔅, 𝔄]^{k}, where δ(𝔄) is the cardinality of the downset created by 𝔄 ∈ D^{2}(A_{m} + Q), and ι[𝔅, 𝔄] is the cardinality of the interval [𝔅, 𝔄] ⊆ D^{2}(A_{m} + Q). The results are used in Section 4 to compare the computational times of algorithms for the calculation of the Dedekind numbers d^{2}(A_{m}), including a new algorithm.

2 Preliminaries

2.1 Notation

We are working with finite posets, that is, ordered pairs P = (X, ≤) consisting of a finite set X and a partial order ≤ on X, i.e., a reflexive, antisymmetric, and transitive subset of X × X. We call X the carrier of P and say that P is a poset on X. Due to reflexivity, the diagonal Δ_{X} ≡ {(x, x) | x ∈ X } is always a subset of ≤. As usual, I write x ≤ y for (x, y) ∈ ≤. The symbols <, ≥, and > are used in their conventional meaning, and x ∥ y means “(x, y) ∉ ≤ and (y, x) ∉ ≤”.

Two elementary posets can be defined on any set X: The antichain (X, Δ_{X}) and the chain, of which the latter is characterized by x ≤ y or y ≤ x for all x, y ∈ X. For a finite set X of cardinality k ∈ ℕ_{0}, I write A_{k} for the antichain on X, and C_{k} for the chain on X.

For any poset P = (X, ≤), the dual P^{∂} = (X, ≤^{∂}) is defined by x ≤^{∂} y ⇔ y ≤ x for all x, y ∈ X.

Given posets P and Q, I use H(P, Q) as symbol for the set of homomorphisms from P to Q, and I write h(P, Q) ≡ #H(P, Q) for the cardinality of this set. We equip H(P, Q) with the usual point-wise partial order. Isomorphism between posets is symbolized by “≃” and we write P ≃^{∂} Q iff P ≃ Q^{∂}. The automorphism group of P is denoted by A(P).

For posets P_{1} = (X_{1}, ≤_{1}) and P_{2} = (X_{2}, ≤_{2}) with X_{1} ∩ X_{2} = ∅, their direct sum is the poset P_{1}+P_{2} ≡ (X_{1}∪X_{2}, ≤_{1} ∪ ≤_{2}), and their ordinal sum is the poset P_{1}⊕P_{2} ≡ (X_{1}∪X_{2}, ≤_{1} ∪ ≤_{2} ∪(X_{1} × X_{2})). For k ∈ ℕ, we define

Λ_{k} ≡ A_{k−1} ⊕ A_{1},
M_{k} ≡ A_{1} ⊕ A_{k−2} ⊕ A_{1} for k ≥ 2.

The posets Λ_{4} and M_{5} are illustrated in Figure 1.

Figure 1: Λ_{4} and M_{5}.

Given posets P_{1} = (X_{1}, ≤_{1}) and P_{2} = (X_{2}, ≤_{2}), the component-wise partial order P_{1} × P_{2} ≡ (X_{1} × X_{2}, ⪯) on X_{1} × X_{2} is defined by (x_{1}, x_{2}) ⪯ (y_{1}, y_{2}) iff x_{1} ≤_{1} y_{1} and x_{2} ≤_{2} y_{2}. I write P^{k} for P × ⋯ × P with k factors P. We have H(P, Q^{k}) ≃ H(P, Q)^{k} for all k ∈ ℕ. A binary word is an element of (C_{2})^{k} with 0 < 1 as carrier of C_{2}.

In order to avoid repetitions we agree on the following. The finite poset P has always the carrier X = {x_{1}, …, x_{m}} with m = #X, whereas we are using the carrier Y = {y_{1}, …, y_{n}}, n = #Y, for the poset Q. We keep the notation for the carriers of P and Q even if these partial orders are specified: e.g., in the case P = A_{m}, we write X = {x_{1}, …, x_{m}} for the carrier of A_{m}, whereas in the case Q = A_{n}, we use Y = {y_{1}, …, y_{n}} for the carrier of A_{n}. For the partial orders belonging to P and Q, we use the same symbol “≤” in most cases.

For a mapping f : A → B, the pre-image of B′ ⊆ B is denoted by

\overline{f}^{1}(B′) ≡ \{a ∈ A | f(a) ∈ B′ \};

for b ∈ B we write \overline{f}^{1}(b) ≡ \overline{f}^{1}(\{b\}). We define \underline{0} ≡ ∅ and \underline{ℓ} ≡ \{1, …, ℓ\} for every ℓ ∈ ℕ.

2.2 Downsets and downset-lattices

Downsets are one of the fundamental concepts in order theory. Given a poset P = (X, ≤), a subset D ⊆ X is called a downset or order ideal of P iff x ∈ D holds for every x ∈ X, for which a y ∈ D exists with x ≤ y. The set of downsets of P is denoted by D(P) and its cardinality by d(P) ≡ #D(P). By applying well-known isomorphisms we get for all posets P and Q

H(P, D(Q)) ≃ H(Q, D(P)).  (1)

For x ∈ X we define the downset created by x in P by

↓ x ≡ {y ∈ X | y ≤ x} .

We write δ(x) ≡ #↓ x for the cardinality of ↓ x.

Upsets are the duals of downsets: For a poset P = (X, ≤), a subset U ⊆ X is called an upset or order filter of P iff x ∈ U holds for every x ∈ X for which a y ∈ U exists with x ≥ y. For x ∈ X and A ⊆ X we define

↑ x ≡ {y ∈ X | y ≥ x} ,
⇑ A ≡ ⋃_{a∈A} ↑ a = {y ∈ X | ∃_{a∈A} : a ≤ y } .

For x, y ∈ X we define the interval

[y, x] ≡ (↑ y) ∩ (↓ x) = {z ∈ X | y ≤ z ≤ x} .

For the cardinality of [y, x] we write ι[y, x] ≡ #[y, x].

A finite partial order P = (X, ≤) is called a lattice iff for every subset A ⊆ X the downset ∩_{a∈A}↓ a and the upset ∩_{a∈A}↑ a are non-empty and additionally

inf A ≡ max ⋂_{a∈A} ↓ a and sup A ≡ min ⋂_{a∈A} ↑ a  (2)

both exist. In Section 4.2, we need the following equation:

Lemma 1. Let P be a finite lattice. Then for every k ∈ ℕ

∑_{a∈P} ∑_{b∈↓ a} ι[b, a]^{k} = ∑_{(x_{1},...,x_{k})∈X^{k}} (#↓ inf \{x_{i} | i ∈ \underline{k} \}) · (#↑ sup \{x_{i} | i ∈ \underline{k} \}) .

Proof. For (b, a) ∈ X^{2}

[b, a]^{k} = \{(x_{1}, …, x_{k}) ∈ X^{k} | b ≤ x_{i} ≤ a for all i ∈ \underline{k} \}

= \{(x_{1}, …, x_{k}) ∈ X^{k} | b ∈ ∩_{i∈\underline{k}}↓ x_{i}, a ∈ ∩_{i∈\underline{k}}↑ D_{i} \}

=^{(2)} \{(x_{1}, …, x_{k}) ∈ X^{k} | b ≤ inf \{x_{i} | i ∈ \underline{k} \} , a ≥ sup \{x_{i} | i ∈ \underline{k} \}\} ,

and the lemma is proven because by rearranging the summation we get

∑_{(b,a)∈X^{2}} # \{(x_{1}, …, x_{k}) ∈ X^{k} | b ≤ inf \{x_{i} | i ∈ \underline{k} \} , a ≥ sup \{x_{i} | i ∈ \underline{k} \}\}

= ∑_{(x_{1},...,x_{k})∈X^{k}} (#↓ inf \{x_{i} | i ∈ \underline{k} \}) · (#↑ sup \{x_{i} | i ∈ \underline{k} \}) .

If we equip D(P) with the partial order induced by set inclusion, D(P) becomes itself a partial order. We use D^{2}(P) ≡ D(D(P)) as symbol for the set of the downsets of D(P); the cardinality of this set is denoted by d^{2}(P) ≡ #D^{2}(P). The poset D^{2}(Q) is never an antichain, and we have

D^{2}(P + Q) ≃ H(D(Q), D^{2}(P)).  (3)

Furthermore, inf B = ∩B and sup B = ∪B for all B ⊆ D^{2}(P).

The starting point of this study was the free distributive lattice with k generators which is initially an (universal) algebraic object. But every distributive lattice is isomorphic to a lattice of sets [4, p. 194]. The lattice of sets isomorphic to the completed free distributive lattice with k generators is D^{2}(A_{k}), the downset-lattice of the power set of a k-element set [4, p. 61], and d^{2}(A_{k}) is the k^{th} Dedekind number. The sets D^{2}(A_{k}), 0 ≤ k ≤ 3, are shown in Figure 2. The non-isomorphic elements of D^{2}(A_{4}) and the numbers of their downsets are shown in the appendix.

Figure 2: Free distributive lattices with up to three generators.

3 Powers and exponential sums

3.1 Powers of d^{2}(Q) and d^{2}(A_{1} + Q)

In this section we prove the three inequalities

d^{2}(A_{1} + Q) < d^{2}(Q)^{2} < d^{2}(A_{2} + Q),  (4)
d^{2}(Q)^{3} < d^{2}(A_{1} + Q)^{2}.  (5)

The first inequality in (4) is already mentioned by Wiedemann [28], and its proof is simple. For every poset R we have D(R)^{2} ≃^{∂} H(R, (C_{2})^{2}). The chain C_{3} is a proper sub-poset of the diamond (C_{2})^{2}, hence h(R, C_{3}) ≤ h(R, (C_{2})^{2}), with equality iff R is the empty poset. Now the inequality follows by replacing R by D(Q) ≠ ∅, because (3) delivers D^{2}(A_{1} + Q) ≃ H(D(Q), C_{3}).

The proof of the two remaining inequalities is more involved. We need the following definition:

Definition 2. Let Q be any poset, A ⊆ Y, and x, y ∈ A. We say that x and y are connected in A, iff there are z_{0}, z_{1}, …, z_{L} ∈ A with x = z_{0}, y = z_{L} and z_{ℓ−1} ≤ z_{ℓ} or z_{ℓ} ≤ z_{ℓ−1} for all Figure 3: Illustrations to Theorem 5 and Corollary 6. a) The posets B ≡ (C_{2})^{3} and S with their points represented by binary words. b) Assignment of the sets ⊥, ℓ, r, … to the points of B and S.

ℓ ∈ \underline{L}. We define for all A ⊆ Y, x ∈ A, B ⊆ A

γ_{Q,A}(x) ≡ {y ∈ A | x and y are connected in A} ,
γ_{Q,A}(B) ≡ ⋃_{b∈B} γ_{Q,A}(b).

We write γ_{Q} for γ_{Q,Y}, and if Q is fixed, we write γ_{A} instead of γ_{Q,A}.

Corollary 3. Let A ⊆ Y. The relation “connected in A” is an equivalence relation on A with partition {γ_{A}(a) | a ∈ A}. For x ∈ A ⊆ A′ ⊆ Y and B ⊆ B′ ⊆ A we have

B ⊆ γ_{A}(B),  (6)
γ_{A}(B) ⊆ γ_{A}(B′),  (7)
γ_{A}(B) ⊆ γ_{A′}(B),  (8)
γ_{A}(B) = γ_{γ_{A}(B)}(B).  (9)

Proof. All but (9) are direct consequences from Definition 2. For the proof of “⊆” in (9), let x ∈ γ_{A}(B). There exists a b ∈ B and z_{0}, z_{1}, …, z_{L} ∈ A with x = z_{0}, b = z_{L} and z_{ℓ−1} ≤ z_{ℓ} or z_{ℓ} ≤ z_{ℓ−1} for all ℓ ∈ \underline{L}. We conclude z_{ℓ} ∈ γ_{A}(b) for all ℓ ∈ \underline{L}, and x and b are connected in γ_{γ_{A}(b)}(b), too. Hence x ∈ γ_{γ_{A}(b)}(b) ⊆ γ_{γ_{A}(B)}(B). “⊇” follows with (8).

Lemma 4. Let ξ : Q → P be a homomorphism.

(a) For B ⊆ A ⊆ Y we have ξ(γ_{Q,A}(B)) ⊆ γ_{P,ξ(A)}(ξ(B)).

(b) Let A ⊆ X be an antichain of P and A′ ⊆ \overline{ξ}^{1}(A). Then ξ(γ_{Q,A′}(x)) = \{ξ(x)\} for every x ∈ A′; in particular, for every x ∈ A′, there exists a y ∈ A with γ_{Q,A′}(x) ⊆ \overline{ξ}^{1}(y).

Proof. (a) is a direct consequence of Definition 2; for the proof of (b), use (a).

Theorem 5. We define the posets B ≡ (C_{2})^{3} (the cube) and S as shown in Figure 3(a) with their points represented by binary words. For every homomorphism ξ ∈ H(Q, B), we define the mapping ρ(ξ) : Q → S by (cf. Figure 3(b))

\begin{matrix}z ≡ \overline{ξ}^{1}(010), & r ≡ \overline{ξ}^{1}(001), \\ Z ≡ \overline{ξ}^{1}(101), & Γ ≡ γ_{Z}(Z ∩ ⇑ r), \\ \overline{ρ(ξ)}^{1}(0000) ≡ ⊥ ≡ \overline{ξ}^{1}(000), & \overline{ρ(ξ)}^{1}(0100) ≡ ℓ ≡ \overline{ξ}^{1}(100), \\ \overline{ρ(ξ)}^{1}(0001) ≡ r, & \overline{ρ(ξ)}^{1}(1100) ≡ Z \ Γ, \\ \overline{ρ(ξ)}^{1}(0101) ≡ z ∪ Γ, & \overline{ρ(ξ)}^{1}(1101) ≡ L ≡ \overline{ξ}^{1}(110), \\ \overline{ρ(ξ)}^{1}(0111) ≡ R ≡ \overline{ξ}^{1}(011), & \overline{ρ(ξ)}^{1}(1111) ≡ ⊤ ≡ \overline{ξ}^{1}(111). \end{matrix}

Then ρ: H(Q, B) → H(Q, S), ξ ↦ ρ(ξ), is a one-to-one mapping.

Proof. ρ(ξ) is well-defined: ξ is a mapping from Q to B. Therefore, the sets ⊥, ℓ, z, r, L, Z, R, and ⊤ are pairwise disjoint, and their union is Y. In consequence, also the sets ⊥, ℓ, r, Z \ Γ, z ∪ Γ, L, R, ⊤ are pairwise disjoint with union Y, and ρ(ξ) is a well-defined mapping from Q to S.

ρ(ξ) is a homomorphism: Let x, y ∈ Y with x ≤ y. Looking at Figure 3(b), we see that for x ∈ ⊥ ∪ ℓ ∪ z ∪ L ∪ R ∪ ⊤ the relation ρ(ξ)(x) ≤_{S} ρ(ξ)(y) is a direct consequence of ξ(x) ≤_{B} ξ(y). The cases x ∈ r and x ∈ Z remain.

For x ∈ r, 001 = ξ(x) ≤_{B} ξ(y) yields y ∈ r ∪ Z ∪ R ∪ ⊤. For y ∈ r ∪ R ∪ ⊤ we get ρ(ξ)(y) ∈ {0001, 0111, 1111}, and thus ρ(ξ)(x) = 0001 ≤_{S} ρ(ξ)(y). Let y ∈ Z. Because of

x ≤ y, we have y ∈ Z ∩ ⇑ r ⊆^{(6)} Γ, and thus ρ(ξ)(x) = 0001 <_{S} 0101 = ρ(ξ)(y).

For x ∈ Z we have ρ(ξ)(x) ∈ {1100, 0101}. Furthermore, ξ(x) ≤_{B} ξ(y) yields y ∈ Z ∪ ⊤. In the case y ∈ ⊤ we have ρ(ξ)(x) <_{S} 1111 = ρ(ξ)(y). Let y ∈ Z. Then we have y ∈ γ_{Z}(x), which yields γ_{Z}(y) = γ_{Z}(x) (Corollary 3). Because Γ is the union of the γ_{Z}(a) over the a ∈ Z ∩ ⇑ r, we have x ∈ Γ ⇔ y ∈ Γ, hence ρ(ξ)(x) = 0101 = ρ(ξ)(y) or ρ(ξ)(x) = 1100 = ρ(ξ)(y), and ρ(ξ) is indeed a homomorphism.

ρ : H(Q, B) → H(Q, S) is one-to-one: Looking at Figure 3(b), we realize that all is proven if we can reconstruct the set Γ by means of ρ(ξ). We need the following technical equations:

Z ∩ ⇑ r = (z ∪ Γ) ∩ ⇑ r,  (10)
Γ = γ_{z∪Γ}((z ∪ Γ) ∩ ⇑ r).  (11)

(10) “⊆”: Z ∩ ⇑ r = (Z ∩ ⇑ r) ∩ ⇑ r ⊆^{(6)} Γ ∩ ⇑ r. “⊇”: Assume r = \overline{ξ}^{1}(001) ≠ ∅. Then we have ξ(x) ≥_{B} 001 for every x ∈ ⇑ r, hence x ∉ \overline{ξ}^{1}(010) = z due to 010 ∥_{B} 001. We conclude z ∩ ⇑ r = ∅ (trivial for r = ∅), hence (z ∪ Γ) ∩ ⇑ r = Γ ∩ ⇑ r ⊆ Z ∩ ⇑ r.

(11): Due to (10), we have to show Γ = γ_{z∪Γ}(Z ∩ ⇑ r). “⊆” we get by Γ =^{(9)} γ_{Γ}(Z ∩ ⇑ r) ⊆^{(8)} γ_{z∪Γ}(Z ∩ ⇑ r). Now let x ∈ γ_{z∪Γ}(a) for an a ∈ Z ∩ ⇑ r. We have z ∪ Γ ⊆ \overline{ξ}^{1}(\{010, 101\}) with 010 ∥_{B} 101. From Lemma 4(b) we get γ_{z∪Γ}(a) ⊆ \overline{ξ}^{1}(010) = z or γ_{z∪Γ}(a) ⊆ \overline{ξ}^{1}(101) = Z, and due to a ∈ Z it is the latter inclusion which holds. We obtain x ∈ (z ∪ Γ) ∩ Z = Γ, as required.

With (11) we get

Γ = γ_{\overline{ρ(ξ)}^{1}(0101)}(\overline{ρ(ξ)}^{1}(0101) ∩ ⇑ \overline{ρ(ξ)}^{1}(0001)),

and the proof is finished.

Inequality (5) and the second inequality in (4) are proven as part (b) and (c) of the following corollary:

Corollary 6. For every finite poset Q we have

(a) h(Q, B) ≤ h(Q, S) with equality iff Q is an antichain.

(b) d^{2}(Q)^{3} < d^{2}(A_{1} + Q)^{2}.

(c) d^{2}(Q)^{2} < d^{2}(A_{2} + Q).

Proof. (a) The inequality is a direct consequence of Theorem 5. For Q ≃ A_{n}, both sets of homomorphisms have cardinality 8^{n}. If Q is not an antichain, x, y ∈ Y exist with y < x. We define ζ ∈ H(Q, S) by

\overline{ζ}^{1}(1100) ≡ Y \ ↑ x,
\overline{ζ}^{1}(1101) ≡ ↑ x.

Then we have y ∈ \overline{ζ}^{1}(1100) and x ∈ \overline{ζ}^{1}(1101). But ζ is not in the image of ρ, because for ξ ∈ H(Q, B), a ∈ \overline{ρ(ξ)}^{1}(1100) ⊆ Z = \overline{ξ}^{1}(101), b ∈ \overline{ρ(ξ)}^{1}(1101) = L = \overline{ξ}^{1}(110) it must hold a ∥ b due to ξ(a) = 101 ∥_{B} 110 = ξ(b).

(b) We have D^{2}(Q)^{3} ≃^{∂} H(D(Q), B), and we have already seen in the proof of the first inequality in (4) that D^{2}(A_{1} + Q) is isomorphic to H(D(Q), C_{3}). Thus, D^{2}(A_{1} + Q)^{2} is isomorphic to H(D(Q), (C_{3})^{2}), and because S is a proper sub-poset of (C_{3})^{2} and D(Q) is not empty, (b) follows with (a).

(c) Applying (b) twice yields d^{2}(Q)^{2} < d^{2}(A_{1} + Q)^{\frac{4}{3}} < d^{2}(A_{2} + Q)^{\frac{8}{9}} .

Corollary 6(a) can be reformulated as follows:

Corollary 7. Let R be a finite distributive lattice and let N be the poset with N-shaped diagram. Then h(A_{3}, R) = (#R)^{3} ≤ h(N, R) with equality iff R = D(A_{k}) for k ∈ ℕ^{0}, i.e., iff R is a power set.

Proof. With Q being the poset of the join-irreducible elements of R, we have R ≃ D(Q). (1) yields H(A_{3}, R) ≃ H(Q, D(A_{3})) and H(N, R) ≃ H(Q, D(N)), and due to D(A_{3}) ≃ (C_{2})^{3} = B and D(N) ≃ S the statements follow with Corollary 6(a).

\begin{matrix}k & d^{2}(A_{k}) & d^{2}(A_{k})^{2} & d^{2}(A_{k})^{3} \\ 0 & 2 & 4 & 8 \\ 1 & 3 & 9 & 27 \\ 2 & 6 & 36 & 216 \\ 3 & 20 & 400 & 8000 \\ 4 & 168 & 28224 & 4741632 \\ 5 & 7581 & 57471561 & 4.35692E+11 \\ 6 & 7828354 & 6.12831E+13 & 4.79746E+20 \\ 7 & 2414682040998 & 5.83069E+24 & 1.40793E+37 \end{matrix}

Table 2: Dedekind numbers and their squares and cubes.

In H(A_{3}, R), all three points of A_{3} can independently be mapped to R, whereas in H(N, R) this holds only for two points, and the images of the two remaining ones get squeezed by the images of the first two ones. At least for me it was a surprise that nevertheless the number of homomorphisms in H(N, R) is greater than or equal to the number of homomorphisms in H(A_{3}, R) for all distributive lattices R.

In Section 4.2, we will use the inequalities (4) and (5) in a comparison of the calculation times of algorithms for the calculation of Dedekind numbers. It makes sense to ask if a difference between calculation times is “really large” (then take the algorithm with the lower calculation time) or if it is “not so large” (then look first, if the algorithm with the higher effort provides benefits which balance the larger calculation time). Without specifying the exact meaning of “large”, we can state the following: in the proofs of the inequalities (4) and (5), we have firstly shown h(D(Q), T) ≤ h(D(Q), T′) for posets T and T′, and afterwards enforced “<” by “adding a right corner” to T′ (step from T′ = C_{3} to (C_{2})^{2} and from T′ = S to (C_{3})^{2}). It is obvious that the latter step increases considerably the amount of homomorphisms for a poset Q which provides sufficiently rich order combinatorics. The differences between d^{2}(A_{1} + Q), d^{2}(Q)^{2}, and d^{2}(A_{2} + Q) on the one hand, and the difference between d^{2}(Q)^{3} and d^{2}(A_{1} + Q)^{2} on the other hand, will be large in most cases, as confirmed by Table 2 for Dedekind numbers. (Here, as in what follows, we avoid calculations involving the 8^{th} Dedekind number.)

3.2 Exponential sums

In this section, we prove relations regarding exponential sums of downset sizes and of interval sizes. They can be written as cardinalities of sets of homomorphisms: for every finite poset Q we have

∑_{x∈Q} δ(x)^{k} = h(Λ_{k+1}, Q),  (12)
∑_{x∈Q} ∑_{y∈↓ x} ι[y, x]^{k} = h(M_{k+2}, Q).  (13)

Furthermore, (3) yields

D^{2}(A_{m} + Q) ≃ H(D(A_{m}), D^{2}(Q)),  (14)

with the immediate consequences

d^{2}(A_{1} + Q) = ∑_{𝔄∈D^{2}(Q)} δ(𝔄),  (15)
d^{2}(A_{2} + Q) = ∑_{𝔄∈D^{2}(Q)} ∑_{𝔅∈↓ 𝔄} ι[𝔅, 𝔄]^{2}.  (16)

Eq. (15) can be found in the papers [3, 11, 20, 21, 22, 29], and (16) is used by Fidytek et al. [11].

The basis of our investigation in this section is the following lemma:

Lemma 8. Let P_{1}, P_{2}, and Q be non-empty finite or infinite posets, X_{1} the carrier of P_{1}, X_{2} the carrier of P_{2}.

(a) Let ϕ : P_{1} → P_{2} be a bijective homomorphism. Then

Φ : H(P_{2}, Q) → H(P_{1}, Q),
ξ ↦ ξ ∘ ϕ

is a one-to-one homomorphism. If Q is not an antichain, then Φ is onto (and an isomorphism) iff ϕ is an isomorphism. If Q is an antichain, then Φ is onto iff the induced mapping

ϕ′ : {γ_{P_{1}}(x) | x ∈ X_{1} } → {γ_{P_{2}}(z) | z ∈ X_{2} }
γ_{P_{1}}(x) ↦ γ_{P_{2}}(ϕ(x))

is one-to-one.

(b) Let ψ : P_{1} → P_{2} be an embedding, and let Q be a complete lattice. Then

Ψ : H(P_{2}, Q) → H(P_{1}, Q)
ξ ↦ ξ ∘ ψ

is a homomorphism and onto. For Q ≃ A_{1}, Ψ is one-to-one. For Q ≄ A_{1}, Ψ is one-to-one (and an isomorphism) iff ψ is an isomorphism.

Proof. Obviously, Φ and Ψ are well defined homomorphisms.

(a) Because ϕ is bijective, Φ is one-to-one. If Q is not an antichain, then there exist elements a, b ∈ Y with a < b. Nothing has to be proven if ϕ is an isomorphism. Assume that ϕ is not an isomorphism. Then there exist x, y ∈ X_{1} with x ≰ y but ϕ(x) ≤ ϕ(y). We define an homomorphism ζ ∈ H(P_{1}, Q) by setting for all z ∈ X_{1}:

ζ(z) ≡ \begin{cases}a, & if z ∈ ↓ y; \\ b, & if z ∈ X_{1} \ ↓ y. \end{cases}

Then ζ(x) = b > a = ζ(y), and Φ is not onto due to (ξ∘ϕ)(x) ≤ (ξ∘ϕ)(y) for all ξ ∈ H(P_{2}, Q).

Assume, that Q is an antichain. With the help of Lemma 4 we see that the mapping ϕ′ is well-defined. Assume, that ϕ′ is one-to-one. Let ζ ∈ H(P_{1}, Q), and define ξ ≡ ζ ∘ ϕ^{−1}. For x, y ∈ X_{2} with x ≤ y, Corollary 3 yields γ_{P_{2}}(x) = γ_{P_{2}}(y), and thus ϕ′(γ_{P_{1}}(ϕ^{−1}(x)) = γ_{P_{2}}(x) = γ_{P_{2}}(y) = ϕ′(γ_{P_{1}}(ϕ^{−1}(y)). Because ϕ′ is one-to-one, γ_{P_{1}}(ϕ^{−1}(x)) = γ_{P_{1}}(ϕ^{−1}(y)), and with Lemma 4(b) we get the equalities {ζ(ϕ^{−1}(x))} = ζ(γ_{P_{1}}(ϕ^{−1}(x))) = ζ(γ_{P_{1}}(ϕ^{−1}(y))) = {ζ(ϕ^{−1}(y))}. We conclude ξ(x) = ζ(ϕ^{−1}(x)) = ζ(ϕ^{−1}(y)) = ξ(y), and ξ is a homomorphism. Thus, Φ is onto.

If Q is an antichain and ϕ′ not one-to-one, then there exist x, y ∈ X_{1} with γ_{P_{1}}(x) ≠ γ_{P_{1}}(y) and γ_{P_{2}}(ϕ(x)) = γ_{P_{2}}(ϕ(y)). From γ_{P_{1}}(x) ≠ γ_{P_{1}}(y) we conclude y ∉ γ_{P_{1}}(x) (Corollary 3). With a, b ∈ Y, a ≠ b, we define ζ : X_{1} → Y by

ζ(z) ≡ \begin{cases}a, & if z ∈ γ_{P_{1}}(x); \\ b, & if z ∈ X_{1} \ γ_{P_{1}}(x). \end{cases}

For every z ∈ γ_{P_{1}}(x), we have (↓ z) ∪ (↑ z) ⊆ γ_{P_{1}}(x). We conclude z_{1}∥z_{2} for all z_{1} ∈ γ_{P_{1}}(x), z_{2} ∈ X_{1} \ γ_{P_{1}}(x), and ζ is a well-defined homomorphism with ζ(x) = a ≠ b = ζ(y). But for every homomorphism ξ ∈ H(P_{2}, Q), Lemma 4(b) enforces {ξ(ϕ(x))} = ξ(γ_{P_{2}}(ϕ(x))) = ξ(γ_{P_{2}}(ϕ(y))) = {ξ(ϕ(y))}, whence ζ ∉ Φ(H(P_{2}, Q)).

(b) Let ζ ∈ H(P_{1}, Q). We have to construct a ξ ∈ H(P_{2}, Q) with ξ ∘ ψ = ζ. We define for all x ∈ X_{2}

ξ(x) ≡ sup ζ(\overline{ψ}^{1}(↓ x)).

It is easily seen that ξ is an homomorphism with ξ ∘ ψ ≥ ζ. Let y ∈ X_{1}. For every x ∈ \overline{ψ}^{1}(↓ ψ(y)), the inequality ψ(x) ≤ ψ(y) holds, and thus x ≤ y because ψ is an embedding. In consequence, (ξ ∘ ψ)(y) = sup ζ(\overline{ψ}^{1}(↓ ψ(y))) ≤ ζ(y). Hence ξ ∘ ψ = ζ, and Ψ is onto.

The case Q ≃ A_{1} is trivial, and Ψ is an isomorphism, if ψ is an isomorphism. Let Q ≄ A_{1} and let a, b ∈ Y with a ≠ b. With c ≡ inf{a, b}, d ≡ sup{a, b}, we have c < d. If ψ is not onto, then there exists a x_{0} ∈ X_{2} \ ψ(X_{1}). Now we define two mappings ξ_{1}, ξ_{2} : X_{2} → Y by

Figure 4: Illustrations for the proof of Corollary 9.

setting

ξ_{1}(x) ≡ \begin{cases}c, & if x ∈ ↓ x_{0}; \\ d, & if x ∈ X_{2} \ ↓ x_{0}; \end{cases}

ξ_{2}(x) ≡ \begin{cases}c, & if x ∈ (↓ x_{0}) \ \{x_{0}\}; \\ d, & if x ∈ (X_{2} \ ↓ x_{0}) ∪ \{x_{0}\}. \end{cases}

Then ξ_{1} and ξ_{2} are different elements of H(P_{2}, Q) with Ψ(ξ_{1}) = Ψ(ξ_{2}).

In the proof of Lemma 8(b) we have only used the existence of sup A for every A ⊆ Y, but this is equivalent to the completeness of the lattice Q [9, Thm. 2.31].

The two following corollaries collect relations regarding exponential sums of downset sizes and exponential sums of interval sizes. In the proofs, Lemma 8(b) can always be applied because D^{2}(Q) is always a complete lattice. With respect to the “<”-relations, the reader will remember that D^{2}(Q) is never an antichain. In the following applications of Lemma 8(a), the resulting homomorphism Φ is therefore never onto because the constructed homomorphism ϕ is not an isomorphism, and in the applications of Lemma 8(b), Ψ is never one-to-one because the respective ψ is not an isomorphism.

Corollary 9. Let Q be a finite poset. Then for all k ≥ 1 and ℓ ≥ 1

d^{2}(A_{2} + Q) < ∑_{𝔄∈D^{2}(Q)} δ(𝔄)^{3},  (17)
∑_{𝔄∈D^{2}(Q)} δ(𝔄)^{k+ℓ} < ∑_{𝔄∈D^{2}(A_{ℓ}+Q)} δ(𝔄)^{k} ≤ d^{2}(A_{k+ℓ} + Q),  (18)
∑_{𝔄∈D^{2}(A_{1}+Q)} δ(𝔄)^{k} < ∑_{𝔄∈D^{2}(Q)} δ(𝔄)^{2k+1},  (19)

with “=” in the second inequality of (18) iff k = 1.

Proof. (17): In Figure 4(a), a bijective homomorphism from Λ_{4} to D(A_{2}) is shown. Now the inequality follows with Lemma 8(a) and (14).

\begin{matrix}k \ n & 0 & 1 & 2 & 3 & 4 \\ 0 & 2 & 3 & 6 & 20 & 168 \\ 1 & 3 & 6 & 20 & 168 & 7581 \\ 2 & 5 & 14 & 84 & 2008 & 595649 \\ 3 & 9 & 36 & 404 & 28926 & 62534979 \\ 4 & 17 & 98 & 2100 & 462076 & 7663696589 \\ 5 & 33 & 276 & 11420 & 7865238 & 1,02233E+12 \\ 6 & 65 & 794 & 63804 & 139669708 & 1,43264E+14 \\ 7 & 129 & 2316 & 362564 & 2554437606 & 2,07113E+16 \end{matrix}

Table 3: Values of ∑_{𝔄∈D^{2}(A_{n})} δ(𝔄)^{k}.

Figure 5: Illustrations for the proof of Corollary 10.

(18): Figure 4(b) contains an embedding of Λ_{k+2} in Λ_{k+1} × C_{2}. Lemma 8(b) delivers h(Λ_{k+2}, D^{2}(Q)) < h(Λ_{k+1} × C_{2}, D^{2}(Q)), and H(Λ_{k+1} × C_{2}, D^{2}(Q)) ≃ H(Λ_{k+1}, H(C_{2}, D^{2}(Q))) yields together with (14) the first inequality for ℓ = 1. The first inequality with arbitrary ℓ follows by iteration. For k > 1, the first inequality delivers ∑_{𝔄∈D^{2}(A_{ℓ}+Q)} δ(𝔄)^{k} < ∑_{𝔄∈D^{2}(A_{k+ℓ−1}+Q)} δ(𝔄) = d^{2}(A_{k+ℓ} + Q) due to (15).

(19): A bijective homomorphism from Λ_{2k+2} to Λ_{k+1} × C_{2} is easily constructed. With Lemma 8(a) we get h(Λ_{k+1} × C_{2}, D^{2}(Q)) < h(Λ_{2k+2}, D^{2}(Q)), and the inequality follows as in the proof of (18).

In Table 3, values of ∑_{𝔄∈D^{2}(A_{n})} δ(𝔄)^{k} are shown for small k and n. As it can be expected by looking at Figure 4(b) (used in the proof of (18)), the difference between ∑_{𝔄∈D^{2}(A_{n})} δ(𝔄)^{k+1} and ∑_{𝔄∈D^{2}(A_{n+1})} δ(𝔄)^{k} is large in most cases.

Corollary 10. Let Q be a finite poset. Then for all k ≥ 1

d^{2}(A_{2} + Q) < ∑_{𝔄∈D^{2}(Q)} ∑_{𝔅∈↓ 𝔄} ι[𝔅, 𝔄]^{3} < d^{2}(A_{3} + Q),  (20)
d^{2}(A_{3} + Q) < ∑_{𝔄∈D^{2}(Q)} ∑_{𝔅∈↓ 𝔄} ι[𝔅, 𝔄]^{6} < d^{2}(A_{4} + Q),  (21)
∑_{𝔄∈D^{2}(Q)} δ(𝔄)^{k} < ∑_{𝔄∈D^{2}(Q)} ∑_{𝔅∈↓ 𝔄} ι[𝔅, 𝔄]^{k} < ∑_{𝔄∈D^{2}(Q)} δ(𝔄)^{k+1}.  (22)

Furthermore,

∑_{𝔄∈D^{2}(A_{1}+Q)} ∑_{𝔅∈↓ 𝔄} ι[𝔅, 𝔄]^{k−1} < ∑_{𝔄∈D^{2}(Q)} ∑_{𝔅∈↓ 𝔄} ι[𝔅, 𝔄]^{2k}.  (23)

Proof. (20): Of course, D(A_{2}) ≃ M_{4} (the diamond) can be embedded in M_{5}. Lemma 8(b) delivers h(D(A_{2}), D^{2}(Q)) < h(M_{5}, D^{2}(Q)), and the first inequality follows with (14) and (13). An embedding of M_{5} into D(A_{3}) is shown in Figure 5(a) and the second inequality follows in the same way.

(21): A bijective homomorphism from M_{8} to D(A_{3}) (the cube) is trivial. Lemma 8(a) yields h(D(A_{3}), D^{2}(Q)) < h(M_{8}, D^{2}(Q)) and the first inequality follows with (14) and (13). We embed M_{8} into D(A_{4}) as shown in Figure 5(b), and the second inequality follows as in the proof of (20).

(22): The embedding of Λ_{k+1} into M_{k+2} ≃ A_{1} ⊕ Λ_{k+1} is trivial and a bijective homomorphism from Λ_{k+2} to M_{k+2} is easily constructed. Now the inequalities follow with Lemma 8 and the equations used so far in this proof. (The first inequality can also directly be seen by δ(𝔄) = ι[∅, 𝔄].)

(23): Figure 5(c) shows a bijective homomorphism from M_{2k+2} to M_{k+1} ×C_{2}. Now apply Lemma 8(a) and the respective equations.

3.3 Averages

The equalities and inequalities proven in the previous sections give raise to the quick calculation of averages. As (15) and (16) show:

\frac{1}{d^{2}(Q)} ∑_{𝔄∈D^{2}(Q)} δ(𝔄) = \frac{d^{2}(A_{1} + Q)}{d^{2}(Q)} <^{(4)} d^{2}(Q),

\frac{1}{d^{2}(A_{1} + Q)} ∑_{𝔄∈D^{2}(Q)} ∑_{𝔅∈↓ 𝔄} ι[𝔅, 𝔄]^{2} = \frac{d^{2}(A_{2} + Q)}{d^{2}(A_{1} + Q)},

which are the average size of ↓ 𝔄 over all 𝔄 ∈ D^{2}(Q) and the average size of [𝔅, 𝔄]^{2} over all non-empty intervals [𝔅, 𝔄] ⊆ D^{2}(Q).

\begin{matrix}n & d^{2}(A_{n}) & \frac{1}{d^{2}(A_{n})} ∑_{𝔄∈D^{2}(A_{n})} δ(𝔄) & \frac{1}{d^{2}(A_{n})^{2}} ∑_{(𝔄,𝔅)∈D^{2}(A_{n})^{2}} δ(𝔄) · δ(𝔅) \\ 0 & 2 & 1.5 & 2.3 \\ 1 & 3 & 2.0 & 4.0 \\ 2 & 6 & 3.3 & 11.1 \\ 3 & 20 & 8.4 & 70.6 \\ 4 & 168 & 45.1 & 2036.3 \\ 5 & 7581 & 1032.6 & 1066320.9 \\ 6 & 7828354 & 308453.4 & 95143471073.6 \end{matrix}

Table 4: Averages of downset sizes and products of downset sizes.

Also, inequality (5) has an interpretation with respect to an average. Using (15) we get

\frac{1}{d^{2}(Q)^{2}} ∑_{(𝔄,𝔅)∈D^{2}(Q)^{2}} δ(𝔄) · δ(𝔅) = (\frac{d^{2}(A_{1} + Q)}{d^{2}(Q)})^{2} > d^{2}(Q).

The average of the the product δ(𝔄) · δ(𝔅) of arbitrary elements 𝔄, 𝔅 ∈ D^{2}(Q) is therefore always larger than d^{2}(Q). The averages are shown in Table 4 for Q = A_{n}.

4 Computational time of algorithms for the calculation of Dedekind numbers

4.1 Algorithms

The calculation of d^{2}(A_{m}+Q) can in general be done with nested algorithms. Each algorithm except the innermost one transfers a structure to the next lower level algorithm which itself refines the structure by adding additional elements to it. In the innermost algorithm, a calculation formula counts the number of relevant elements in the final structure, and these numbers are summed up. (The final structure has of course to be unique — the algorithm is not allowed to produce duplicates.)

All algorithms described in literature use the isomorphism (14) in the form D^{2}(A_{m}+Q) ≃ H(D(A_{ℓ}), D^{2}(A_{m−ℓ} + Q)) for some 0 ≤ ℓ ≤ m. We call ℓ the level of the algorithm. The outermost algorithm runs over the set D^{2}(A_{m−ℓ}+Q). Therefore, it must construct D^{2}(A_{m−ℓ}+ Q) or to refer to a model of it, which has to be created in advance [3, 11, 20, 21, 25, 28, 29].

Algorithms for the calculation of d^{2}(A_{m} + Q) in literature focus on the case Q = A_{n}, but we also retain the general notation d^{2}(A_{m} + Q) in this section. Even if it has been noticed that a nested algorithm can be written for all values of m [21, 25], the algorithms in literature use m = 0, 1, 2, 4 only. (In fact, the algorithms were restricted to m = 0, 1, 2 even in the fourth quarter of the 20^{th} century which may be due to the remarks of Lunnon [20] and Markowsky [21], cf. [25].) In what follows, we deal with the calculation of d^{2}(A_{4} + Q). The descriptions of the level-3-algorithm (30) and the level-4-algorithm (31) provide a scheme how to construct algorithms for levels higher than 4.

For small posets Q, D^{2}(A_{4} + Q) can be directly constructed and its elements can simply be counted. Formally we can describe this approach as a level-0-algorithm [6, 20]

d^{2}(A_{4} + Q) = ∑_{𝔄∈D^{2}(A_{4}+Q)} 1.  (24)

A level-1-algorithm has already been presented in Section 3.2 in formula (15). It is mentioned or used in many publications [3, 11, 20, 21, 22, 29]:

d^{2}(A_{4} + Q) = ∑_{𝔄∈D^{2}(A_{3}+Q)} δ(𝔄)  (25)

Fidytek et al. [11] realized the algorithm in the form

d^{2}(A_{4} + Q) = ∑_{(𝔄,𝔅)∈D^{2}(A_{3}+Q)^{2}} ζ(𝔅, 𝔄),  (26)

where ζ is the zeta-function with ζ(𝔅, 𝔄) = 1 for 𝔅 ⊆ 𝔄 and = 0 otherwise.

Level-2-algorithms exist in literature in two variants. The first one is the algorithm which has been used in most of the calculations of Dedekind numbers [3, 20, 21, 28, 29]. It is in general notated as

d^{2}(A_{4} + Q) = ∑_{(𝔄,𝔅)∈D^{2}(A_{2}+Q)^{2}} #↓ (𝔄 ∩ 𝔅) · #↑ (𝔄 ∪ 𝔅).  (27)

The summation runs over the images of the left and right corner of M_{4} ≃ D(A_{2}), and if they are fixed, the images of its minimum and maximum are independently selected from the respective downset and upset in (27).

The second variant is used by Fidytek et al. [11]:

d^{2}(A_{4} + Q) = ∑_{(𝔄,𝔅)∈D^{2}(A_{2}+Q)^{2}} ι[𝔅, 𝔄]^{2}.  (28)

Now the summation runs over the images of the maximum and minimum of M_{4}, and the images of the corners are independently selected from the interval spanned up by those.

The potential of algorithm (28) becomes visible if we write it as

d^{2}(A_{4} + Q) = ∑_{𝔄∈D^{2}(A_{2}+Q)} ∑_{𝔅∈↓ 𝔄} ι[𝔅, 𝔄]^{2}.  (29)

In (29) the summation runs over ∑_{𝔄∈D^{2}(A_{2}+Q)} δ(𝔄) =^{(15))} d^{2}(A_{3} + Q) terms, whereas in (27)

and (28) the number of terms is d^{2}(A_{2} + Q)^{2} >^{(4)} d^{2}(A_{3} + Q). Algorithm (29) therefore

Figure 6: Illustration of algorithm (30).

provides an algorithmic benefit — supposing that it is possible to step easily through ↓ 𝔄 for every 𝔄 ∈ D^{2}(A_{2} + Q). And the benefit will be large for sufficiently rich posets Q, as our considerations at the end of Section 3.1 and Table 6 in Section 4.2 show.

I did not find a level-3-algorithm in the literature, but it is not difficult to construct an example (however, I did not test it):

D^{2}(A_{4} + Q) = ∑_{𝔄∈D^{2}(A_{1}+Q)} ∑_{(ℭ_{1},ℭ_{2},ℭ_{3})∈(↓ 𝔄)^{3}} f(𝔄, ℭ_{1}, ℭ_{2}, ℭ_{3})  (30)

with

f(𝔄, ℭ_{1}, ℭ_{2}, ℭ_{3}) ≡ ι[ℭ_{1} ∪ ℭ_{2}, 𝔄] · ι[ℭ_{1} ∪ ℭ_{3}, 𝔄]
· ι[ℭ_{2} ∪ ℭ_{3}, 𝔄] · δ(ℭ_{1} ∩ ℭ_{2} ∩ ℭ_{3}).

The algorithm uses the isomorphism D^{2}(A_{4} + Q) ≃ H(D(A_{3}), D^{2}(A_{1} + Q)) as illustrated in Figure 6. Once 𝔄 ∈ D^{2}(A_{1} + Q) and (ℭ_{1}, ℭ_{2}, ℭ_{3}) ∈ (↓ 𝔄)^{3} have been selected, 𝔅_{12} ∈ [ℭ_{1} ∪ ℭ_{2}, 𝔄], 𝔅_{13} ∈ [ℭ_{1} ∪ ℭ_{3}, 𝔄], 𝔅_{23} ∈ [ℭ_{2} ∪ ℭ_{3}, 𝔄], and 𝔇_{123} ∈ ↓ (ℭ_{1} ∩ ℭ_{2} ∩ ℭ_{3}) can independently be selected.

Fidytek et al. [11] use a level-4-algorithm for the calculation of d^{2}(A_{7}) and d^{2}(A_{8}). With the notation ℭ⃗ for (ℭ_{1}, …, ℭ_{6}) ∈ D^{2}(Q)^{6} the algorithm is

D^{2}(A_{4} + Q) = ∑_{ℭ⃗∈D^{2}(Q)^{6}} ( ∑_{𝔅≤inf\{ℭ_{i} | i∈\underline{6} \}} g^{−}(𝔅, ℭ⃗)) · ( ∑_{𝔄≥sup\{ℭ_{i} | i∈\underline{6} \}} g^{+}(ℭ⃗, 𝔄)) (31)

with

g^{−}(𝔅, ℭ⃗) ≡ ι[𝔅, ℭ_{1} ∩ ℭ_{2} ∩ ℭ_{3}] · ι[𝔅, ℭ_{1} ∩ ℭ_{4} ∩ ℭ_{5}]
· ι[𝔅, ℭ_{2} ∩ ℭ_{4} ∩ ℭ_{6}] · ι[𝔅, ℭ_{3} ∩ ℭ_{5} ∩ ℭ_{6}],
g^{+}(ℭ⃗, 𝔄) ≡ ι[ℭ_{1} ∪ ℭ_{2} ∪ ℭ_{4}, 𝔄] · ι[ℭ_{1} ∪ ℭ_{3} ∪ ℭ_{5}, 𝔄]
· ι[ℭ_{2} ∪ ℭ_{3} ∪ ℭ_{6}, 𝔄] · ι[ℭ_{4} ∪ ℭ_{5} ∪ ℭ_{6}, 𝔄].

The six elements of the downset-tuple ℭ⃗ ∈ D^{2}(Q)^{6} are the images of the six-element antichain in the middle of D(A_{4}) (encircled in Figure 5(b) on the right), 𝔄 and 𝔅 are the images of

Level Algorithm # Calls
0  (24)  d^{2}(A_{4} + Q)
1  (25)  d^{2}(A_{3} + Q)
(26)  d^{2}(A_{3} + Q)^{2}
2 (27) d^{2}(A_{2} + Q)^{2}
(28)  d^{2}(A_{2} + Q)^{2}
(29)  d^{2}(A_{3} + Q)
3  (30)  ∑_{𝔄∈D^{2}(A_{1}+Q)} δ(𝔄)^{3}
4  (31)  ∑_{𝔄∈D^{2}(Q)} ∑_{𝔅∈↓ 𝔄} ι[𝔅, 𝔄]^{6}

Table 5: Number of calls of the innermost calculation formula.

the maximum and the minimum of D(A_{4}), respectively, and the eight remaining images of the elements in the second and fourth layer of D(A_{4}) can independently be chosen from the intervals evaluated in the formulas of g^{−} and g^{+}.

4.2 Computational time

Table 5 shows the number of calls of the innermost calculation formula in the algorithms for the calculation of d^{2}(A_{4} + Q) described in Section 4.1 (for algorithm (31), apply Lemma 1). This number can be regarded as a measure for the computational time of an algorithm, and the numbers can be compared as long as the different innermost calculation formulas cause roughly the same calculation effort. The estimate d^{2}(A_{1+n})^{4} presented by Markowsky [21] for the number of calls of a level-3-algorithm turns out to be quite pessimistic.

Due to (4), we have d^{2}(A_{3} +Q) < d^{2}(A_{2} +Q)^{2} < d^{2}(A_{4} +Q). Furthermore, d^{2}(A_{3} +Q) is, according to (17) and (21), less than ∑_{𝔄∈D^{2}(A_{1}+Q)} δ(𝔄)^{3} and ∑_{𝔄∈D^{2}(Q)} ∑_{𝔅∈↓ 𝔄} ι[𝔅, 𝔄]^{6}, and due to (18) and (21), these two sums are both less than d^{2}(A_{4} + Q). Finally, d^{2}(A_{4} + Q) < d^{2}(A_{3} + Q)^{2} according to (4). Thus, we get the following ranking of the computational times of the algorithms:

(25) = (29) < (27) = (28), (30), (31) < (24) < (26).

The results of Section 3 tell us nothing about relations between the numbers of calls of (28), (30), and (31).

However, the number of calls covers only one aspect of the computational time because the innermost calculation formulas of the algorithms are quite different. Another measure is the number of enumerations of intervals. These figures are shown in Table 6 for the calculation of d^{2}(A_{4+n}), 0 ≤ n ≤ 3.

Some authors calculate parameters in a pre-computational step before the main computation of the Dedekind number itself. Lunnon [20] calculates and saves #↓ 𝔄 and #↑ 𝔄

Algorithm # Interval enumerations n = 0  1  2  3
(25), (29) d^{2}(A_{3+n})  20 168  7581  7828354
(28)  d^{2}(A_{2+n})^{2}  36 400  28224  57471561
(27)  2 · d^{2}(A_{2+n})^{2}  72 800  56448  114943122
(30)  4 · ∑_{𝔄∈D^{2}(A_{1+n})} δ(𝔄)^{3}  144 1616 115704  249924492
(31)  4 · ∑_{𝔄∈D^{2}(A_{n})} ∑_{𝔅∈↓ 𝔄} ι[𝔅, 𝔄]^{6}  264 3440 341232  1155311364
(24)  d^{2}(A_{4+n})  168 7581 7828354 2414682040998
(26)  d^{2}(A_{3+n})^{2}  400 28224 57471561 61283126349316

Table 6: Number of interval enumerations for the calculation of d^{2}(A_{4+n}).

for every 𝔄 ∈ D^{2}(A_{2+n}) in advance, and it pays off: in the pre-computation, he invests 2 · d^{2}(A_{2+n}) enumerations of intervals, causing an exchange of 2 · d^{2}(A_{2+n})^{2} enumerations of intervals in the main computation against simple operations consisting of two fetches from a table and one multiplication.

For the calculation of d^{2}(A_{7}) with the algorithms (28) and (31), Fidytek et al. [11] calculate ι[𝔅, 𝔄] in advance for every 𝔄, 𝔅 ∈ D^{2}(A_{7−ℓ}) by calculating the square of the incidence matrix of D^{2}(A_{7−ℓ}). By means of these pre-calculated interval sizes, they exchange all interval enumerations in the main computation against simple operations with two (four) fetches from a table and one (three) multiplications each. The numbers of entries to be pre-calculated for the level-2-algorithm is by a factor of around 140000 larger than for the level-4-algorithm.

Starting with Church [6], the numerous symmetries of D^{2}(A_{4−ℓ} + Q) have been used to speed-up the main computation. In doing so, the outermost algorithm runs over a representation system of the non-isomorphic downsets of D^{2}(A_{4−ℓ} + Q), and for each representative the number of constructed homomorphisms in H(D(A_{ℓ}), D^{2}(A_{4−ℓ} + Q)) is multiplied with the number of the isomorphic copies of the representative in D^{2}(A_{4−ℓ} + Q). Using the orbit-stabilizer theorem, this number can be calculated without evaluating D^{2}(A_{4−ℓ} + Q) [6, 20, 21, 28]. Additionally, Lunnon [20] exploits duality.

Exploiting the symmetries makes the programming work quite demanding [21, 28], but it pays off: the comparison of the computational times of the calculation of d^{2}(A_{7}) by means of the level-2-algorithm (27) with and without exploitation of symmetries done by Markowsky [21] shows a speed-up factor around 34 (main computation only). But of course, the precomputational step to create a list of non-isomorphic elements of D^{2}(A_{m−ℓ}) is time consuming [21, 28].

Fidytek et al. [11] did not exploit this type of symmetry, but instead used the symmetries provided by A(D(A_{4})). I assume that the trivial symmetry provided by A(D(A_{2})) has been used in all calculations with algorithm (27), even if none of the authors has mentioned it.

For the calculation of d^{2}(A_{m} + Q), a model of D^{2}(A_{m−ℓ} + Q) has to be created, stored, and managed. The larger the value of ℓ, the smaller the model will be. For the calculation of d^{2}(A_{7}), Church [7] had to use a memory saving model of D^{2}(A_{5}) in 1965, but all later authors could keep the model and all pre-calculated parameters in main memory. But it is not only the required memory space which matters: the pure management of data structures of such a huge size and complexity slows down the total computation. On modern computer systems, parallel computing is a natural choice [11, 21, 25].

In the calculation of d^{2}(A_{m} + Q), the model of D^{2}(A_{m−ℓ} + Q) is extremely frequently evaluated. Here, the art of creating suitable data structures and efficient algorithms for their evaluation plays a crucial role [25]; the structure used by Church [7] provides both, memory savings and quick model evaluation. The differences in the numbers of calls between the three level-2-algorithms (27), (28), and (29) emphasize the critical importance of quick evaluation algorithms. For models allowing an effective evaluation of ↓ 𝔄, we get the quicker algorithm (29). Otherwise we work with (27) or (28). (For algorithms at the same level, I assume that the relations between the computational times will be of the same order of magnitude without and with exploitation of symmetries)

Fidytek et al. [11] calculated d^{2}(A_{7}) with the algorithms (26), (28), and (31) on the same computer system. (31) was clearly the fastest algorithm (3 seconds), followed by (28) (30 minutes), whereas (26) was definitely the slowest one (estimated 19 months). The inequalities between the numbers of calls and the figures in Table 6 show that the low performance of (26) had to be expected, but the empirical calculation times of (28) and (31) are clearly the other way around than the figures in Table 6. However, the measured calculation times include both, the pre-calculation and the main calculation, of which the former one is more time consuming for (28), and the latter one for (31). Additionally, the lower effort for handling the model is in favor of the level-4-algorithm.

Under these aspects, the level-3-algorithm (30) will show advantages and drawbacks in the calculation of D^{2}(A_{4}+Q). The model of D^{2}(A_{1}+Q) required by it is clearly simpler than the model used by level-2-algorithms, and the number of calls and the number of interval enumerations of (30) look better than for the level-4-algorithm (31). Thus, (30) may show a good performance. The drawback of a level-3-algorithm is of course, that the model of D(A_{1} + Q) and the pre-computational effort are clearly larger than for a level-4-algorithm; furthermore, A(D(A_{3})) provides fewer symmetries than A(D(A_{4})).

5 Appendix

The non-isomorphic downsets of D(A_{4}) together with the number of their isomorphic copies (left number) and the number of their downsets (right number). The downsets are grouped in pairs of duals, i.e., 𝔄 and (D(A_{4}) \ 𝔄)^{∂}. The last four downsets are self-dual, i.e., 𝔄 ≃ (D(A_{4}) \ 𝔄)^{∂}.

References

[1] J. L. Arocha, The number of antichains of the length 5 and 6, VINITI 06.04.82. Reg. #1631-82 Dep. (1982). In Russian.

[2] V. Bakoev, One more way for counting monotone Boolean functions, in Thirteenth International Workshop on Algebraic and Combinatorial Coding Theory, Pomorie, Bulgaria (2012), pp. 47–52.

[3] J. Berman and P. Köhler, Cardinalities of finite distributive lattices, Mitteilungen aus dem mathem. Seminar Gießen 121 (1976), 103–124.

[4] G. Birkhoff, Lattice Theory, Proc. Amer. Math. Soc. Coll. Publ. 25, 3^{rd} ed., 1967.

[5] T. Carroll, J. Cooper, and P. Tetali, Counting antichains and linear extensions in generalizations of the Boolean lattice, preprint, 2009. Available at

https://people.math.gatech.edu/~tetali/PUBLIS/CCT.pdf.

[6] R. Church, Numerical analysis of certain free distributive structures, Duke Math. J. 6 (1940), 732–734.

[7] R. Church, Enumeration by rank of the elements of the free distributive lattice with 7 generators, Notices Amer. Math. Soc. 12 (1965), 724.

[8] D. M. Cvetković, The number of antichains of finite power sets, Publications de l’Institut Mathématique, Nouvelle série 13 (1972), 5–9.

[9] B. A. Davey and H. A. Priestley, Introduction to Lattices and Order, Cambridge University Press, 2^{nd} ed., 7^{th} printing (2012).

[10] R. Dedekind, Über Zerlegungen von Zahlen durch ihre grössten gemeinsamen Theiler, Festschrift Hoch. Braunschweig u. ges. Werke II (1897), 103–148.

[11] R. Fidytek, A. W. Mostowski, R. Somla, and A. Szepietowski, Algorithms counting monotone Boolean functions, Inform. Process. Lett. 79 (2001), 203–209.

[12] E. N. Gilbert, Lattice theoretic properties of frontal switching functions, J. Math. Phys. 33 (1954), 57–67.

[13] G. Hansel, Sur le nombre des fonctions booléennes monotones de n variables, C. R. Acad. Sci. Paris 262 (1966), 1088–1090.

[14] J. Kahn, Entropy, independent sets and antichains, a new approach to Dedekind’s problem, Proc. Amer. Math. Soc. 130 (2002), 371–378.

[15] G. Kilibarda and V. Jovović, On the number of monotone Boolean functions with fixed number of lower units, Intellektualnye sistemy 7 (2003), 193–217. In Russian.

[16] A. Kisielewicz, A solution of Dedekind’s problem on the number of isotone Boolean functions, J. Reine Angew. Math. 386 (1988), 139–144.

[17] D. Kleitman, On Dedekind’s problem: the number of monotone Boolean functions, Proc. Amer. Math. Soc. 21 (1969), 677–682.

[18] D. Kleitman and G. Markowsky, On Dedekind’s problem: The number of isotone Boolean functions II, Trans. Amer. Math. Soc. 213 (1975), 373–390.

[19] A. D. Korshunov, The number of monotone Boolean functions, Problemy Kibernet. 38 (1981), 5–108. In Russian.

[20] F. Lunnon, The IU function: The size of a free distributive lattice, in D. J. A. Welsh, ed., Combinatorial Mathematics and its Applications, Academic Press, 1971, pp. 173–181.

[21] G. Markowsky, Enumerating free distributive lattices, Technical Report 89-10, Computer Science Department, University of Maine, December 1989. Available at

https://tinyurl.com/yd3pep2h.

[22] N. M. Riviere, Recursive formulas on free distributive lattices, J. Combin. Theory 5 (1968), 229–234.

[23] N. Pippenger, Entropy and enumeration of Boolean functions, IEEE Trans. Inform. Theory 45 (1999), 2096–2100.

[24] A. A. Sapozhenko, The number of antichains in ranked partially ordered sets, Diskr. Mat. 1 (1989), 74–93. In Russian; English translation in Discr. Math. Appl. 1 (1991), 35–58.

[25] I. Shmulevich, T. M. Sellke, M. Gabbouj, and E. J. Coyle, Stack filters and free distributive lattices, in Proceedings of 1995 IEEE Workshop on Nonlinear Signal Processing, Halkidiki, Greece, 1995, pp. 927–930.

[26] N. J. A. Sloane, On-line Encyclopedia of Integer Sequences, The OEIS Foundation,

available at https://oeis.org/.

[27] M. Ward, Note on the order of the free distributive lattice, Bull. Amer. Math. Soc. 52 (1946), 423.

[28] D. Wiedemann, A computation of the eighth Dedekind number, Order 8 (1991), 5–6.

[29] T. J. Yusun, Dedekind Numbers and Related Sequences. Master’s Thesis, Simon Fraser University, Vancouver, BC, Canada, 2011.

2010 Mathematics Subject Classification: Primary 06A07; Secondary 06A06, 06A11. Keywords: poset, downset, antichain, Dedekind number.

(Concerned with sequence \underline{A000372}.)

Received January 20 2018; revised versions received May 1 2018; May 2 2018. Published in Journal of Integer Sequences, May 8 2018.

Return to Journal of Integer Sequences home page.