Counting Self-Dual Monotone Boolean Functions

Bartłomiej Pawelski and Andrzej Szepietowski Institute of Informatics University of Gdańsk Poland

             bartlomiej.pawelski@ug.edu.pl
            andrzej.szepietowski@ug.edu.pl

Abstract

Let D_{n} denote the set of monotone Boolean functions with n variables. The cardinality of D_{n}, denoted by d_{n}, is known as the n-th Dedekind number. Elements of D_{n} can be represented as strings of bits of length 2^{n}. For each f ∈ D_{n}, we have the dual function f^{∗} ∈ D_{n} which is obtained by reversing and negating all bits. An element f ∈ D_{n} is self-dual if f = f^{∗}. Let Λ_{n} denote the set of all self-dual monotone Boolean functions of n variables and let λ_{n} denote |Λ_{n}|. There is a natural action of the permutation group S_{n} on the set of Boolean functions by permutation of variables. The sets D_{n} and Λ_{n} are closed under this action. We let R_{n} and Q_{n} denote the sets of all equivalence classes in D_{n} and Λ_{n}, respectively. In this paper, we derive several algorithms for counting self-dual monotone Boolean functions and confirm the known result that λ_{9} equals 423,295,099,074,735,261,880. Furthermore, we calculate |Q_{8}| to be 6,001,501.

1 Introduction

Let B denote the set {0, 1} and B^{n} the set of n-element sequences of B. A Boolean function with n variables is a function from B^{n} into B. There is the order relation in B (namely: 0 ≤ 0, 0 ≤ 1, 1 ≤ 1) and the partial order in B^{n}: for any two elements: x = (x_{1}, …, x_{n}), y = (y_{1}, …, y_{n}) in B^{n}, x ≤ y if and only if x_{i} ≤ y_{i} for all 1 ≤ i ≤ n. A function h : B^{n} → B is monotone if x ≤ y implies h(x) ≤ h(y). Let D_{n} denote the set of monotone functions with n variables. The cardinality of D_{n}, denoted by d_{n}, is known as the n-th Dedekind number. We have the partial order in D_{n} defined by:

g ≤ h if and only if g(x) ≤ h(x) for all x ∈ B^{n}.

We represent an element f ∈ D_{n} as a string of bits of length 2^{n} where the values of f(x) are listed in lexicographical order of x. The two elements of D_{0} are represented as 0 and 1. For every n ≥ 1, the set D_{n} can be represented as the set of all concatenations g_{0} · g_{1}, where g_{0}, g_{1} ∈ D_{n−1} and g_{0} ≤ g_{1}. For example, D_{1} = {00, 01, 11} and D_{2} = {0000, 0001, 0011, 0101, 0111, 1111}.

For each f ∈ D_{n}, we have the dual f^{∗} ∈ D_{n}, which is obtained by reversing and negating all bits. Formally, the dual of f ∈ D_{n} is the function f^{∗} : B^{n} → B defined by:

f^{∗}(x) = (f(x^{c}))^{c},

where x^{c} is the negation of x ∈ B^{n} and (f(x^{c}))^{c} is the negation of f(x^{c}) ∈ B. For example, 1111^{∗} = 0000 and 0001^{∗} = 0111. An element f ∈ D_{n} is self-dual if f = f^{∗}. For example, 0101 and 0011 are self-dual in D_{2}.

Let Λ_{n} be the set of all self-dual monotone Boolean functions of n variables, and let λ_{n} denote the cardinality of this set. The value λ_{n} is also known as the n-th Hosten-Morris number (\underline{A001206} in the On-Line Encyclopedia of Integer Sequences).

The first attempt to determine the values of λ_{n} was made in 1968 by Riviere [6], who found all values up to λ_{5}. In 1972, Brouwer and Verbeek provided the values up to λ_{7} [3]. The value of λ_{8} was determined by Mills and Mills [5] in 1978.

The most recent known term, λ_{9}, was obtained by Brouwer, Mills, Mills, and Verbeek [2] in 2013. The value of λ_{n} corresponds to the number of non-dominated coteries on n members [1, Section 1], and also corresponds to the number of maximal linked systems (see Section 2.1 and [2, Section 1]).

Any two Boolean functions are said to be equivalent if one can be transformed into the other by a permutation of the input variables (see Section 2.2). Let Q_{n} denote the set of all equivalence classes in Λ_{n} and let q_{n} denote |Q_{n}|. The values of q_{n} are described by the \underline{A008840} OEIS sequence.

In this paper, we derive several algorithms for counting self-dual monotone Boolean functions and we confirm the result of [2] that λ_{9} equals 423,295,099,074,735,261,880. Furthermore, employing Burnside’s lemma and techniques discussed in [8, 10], we calculate q_{8} to be 6,001,501, which is the first-ever calculation of the value q_{8}. We also show that the two sequences d_{n} and λ_{n} intertwine, or more precisely, we have

λ_{1} ≤ d_{0} ≤ λ_{2} ≤ d_{1} ≤ ⋯ ≤ λ_{n+1} ≤ d_{n} ≤ λ_{n+2} ≤ ⋯

and we have the following estimates for the unknown value of λ_{10}

d_{8} ≤ λ_{10} ≤ d_{9}.

2 Preliminaries

A poset (partially ordered set) (S, ≤) consists of a set S (called the carrier) together with a binary relation (partial order) ≤ which is reflexive, transitive, and antisymmetric. For

\begin{matrix}n & λ_{n} & q_{n} \\ 0 & 0 & 0 \\ 1 & 1 & 1 \\ 2 & 2 & 1 \\ 3 & 4 & 2 \\ 4 & 12 & 3 \\ 5 & 81 & 7 \\ 6 & 2,646 & 30 \\ 7 & 1,422,564 & 716 \\ 8 & 229,809,982,112 & 6,001,501 \\ 9 & 423,295,099,074,735,261,880 & – \end{matrix}

Table 1: Known values of λ_{n} (\underline{A001206}) and q_{n} (\underline{A008840}).

example, B, B^{n}, and D_{n} are posets. Given two posets (S, ≤) and (T, ≤), a function f : S → T is monotone, if x ≤ y implies f(x) ≤ f(y). We let T^{S} denote the poset of all monotone functions from S to T with the partial order defined by:

f ≤ g if and only if f(x) ≤ g(x) for all x ∈ S.

Notice that D_{n} = B^{B^{n}} and B^{n} = B^{A_{n}}, where A_{n} is the antichain with the carrier {1, …, n}. A set A is an antichain if any two distinct elements in A are incomparable. In this paper we use the well known lemma [10]:

Lemma 1. The poset D_{n+k} is isomorphic to the poset D_{n}^{B^{k}}—the poset of monotone functions from B^{k} to D_{n}.

By ⊤ we denote the maximal element in D_{n}, that is ⊤ = (1 … 1), and by ⊥ the minimal element in D_{n}, that is ⊥ = (0 … 0). For two elements f, g ∈ D_{n}, by f|g we denote the bitwise or; and by f&g the bitwise and. Furthermore, let re(f, g) denote the number of elements in the interval [f, g], that is |{h ∈ D_{n} : f ≤ h ≤ g}|. Note that re(f, ⊤) = |{h ∈ D_{n} : f ≤ h}| and re(⊥, g) = |{h ∈ D_{n} : h ≤ g}|. For f ∈ D_{n}, by ℓ(f) we denote the number of ones in f, also known as its Hamming weight. For example, ℓ(0000) = 0 and ℓ(0101) = 2. The next result is straightforward.

Lemma 2. For each f, g ∈ D_{n}, we have

1. f^{∗∗} = f

2. if f ≤ g then g^{∗} ≤ f^{∗}

3. (f|g)^{∗} = f^{∗}&g^{∗}

4. (f&g)^{∗} = f^{∗}|g^{∗}

2.1 Maximal linked system

Let X = {1, …, n} and P(X) be the power set of X. A family W ⊆ P(X) is linked if for all A and B in W, A ∩ B is not empty. A family U ⊆ P(X) is a maximal linked system (mls) on X if U is linked and for all W with U ⊆ W ⊆ P(X), either W = U or W is not linked.

If U is linked, then ∅ ∉ U and for each set A ∈ P(X), it is not possible that both A and its complement A^{c} = X − A belong to U.

For n = 0, X = ∅, P(X) = {∅} and we have one mls, namely, the empty family. Notice that the set of self-dual functions Λ_{0} is empty and λ_{0} = 0.

Lemma 3. If n ≥ 1 and a family U ⊂ P(X) is a mls then:

(L1) U is an upset, i.e., if A ⊆ B and A ∈ U, then B ∈ U.

(L2) For every subset A ∈ P(X) exactly one of the two subsets A or A^{c} is in U.

Proof. (L1) For each C ∈ U, A ∩ C ≠ ∅ and B ∩ C ≠ ∅. Hence, either B ∈ U or U is not maximal.

(L2) We have two cases:

Case 1. For every B ∈ U, A ∩ B ≠ ∅. Then either A ∈ U or U is not maximal.

Case 2. There is B ∈ U such that B ∩ A = ∅. In this case we have that B ⊆ A^{c} and, by (L1), A^{c} ∈ U.

Lemma 4. If n ≥ 1 and a family U ⊆ P(X) satisfies conditions (L1) and (L2), then U is an mls.

Proof. First, we prove that U is linked. Suppose, for a contradiction, that there are two subsets A, B ∈ U with A ∩ B = ∅. Then B ⊆ A^{c} and A^{c} ∈ U, a contradiction.

If U satisfies condition (L2), then exactly half of the elements in P(X) belong to U. On the other hand, if |U| > 2^{n−1} then U contains a pair A, A^{c} and U is not linked.

For n = 1, the family {{1}} is the only mls on X = {1}.

For n = 2, we have two mls: {{1}, {1, 2}} and {{2}, {1, 2}}.

Recall that P(X) is isomorphic to B^{n} by identifying a subset of X with its characteristic vector and any subset of P(X) can be represented by a function from B^{n} to B. For n = 1, the mls {{1}} can be represented as the string 01, which is the only self-dual function in Λ_{1}. For n = 2, the two mls can be represented as 0101 and 0011, and they form the set Λ_{2}. For n ≥ 1, the set of mls on {1, …, n} can be represented as the set of self-dual functions Λ_{n} [2, Section 1.1].

2.2 Permutations and equivalence relation

Let S_{n} denote the set of permutations on {1, …, n}. Every permutation π ∈ S_{n} defines a permutation on B^{n} by: for every x = (x_{1}, …, x_{n}) ∈ B^{n} let π(x) = (x_{π(1)}, …, x_{π(n)}).

The permutation π also defines the function f ∘π : B^{n} → B for every function f : B^{n} → B by:

(f ∘ π)(x) = f(π(x)) for x ∈ B^{n}.

By ∼ we denote an equivalence relation on D_{n}. Namely, two functions f, g ∈ D_{n} are equivalent, f ∼ g, if there is a permutation π ∈ S_{n} such that f = g ∘ π. For a function f ∈ D_{n}, its equivalence class is the set [f] = {g ∈ D_{n} : g ∼ f}. By R_{n} we denote the set of equivalence classes in D_{n} and by r_{n} we denote |R_{n}|. By γ(f) we denote |[f]|. For the class [f], its representative is its minimal element (according to the lexicographical order in D_{n}). Sometimes, we identify the class [f] ∈ R_{n} with its representative and treat [f] as an element in D_{n}. Let Q_{n} denote the set of all equivalence classes in Λ_{n}, and let q_{n} denote |Q_{n}|.

The following lemma is straightforward.

Lemma 5. For every function f : B^{n} → B and for every permutation π ∈ S_{n}

1. The function f ∘ π is monotone if f is monotone.

2. If f ∈ D_{n}, then f^{∗} ∘ π = (f ∘ π)^{∗}.

3. If f ∈ Λ_{n}, then for every equivalent g ∈ [f] we have g ∈ Λ_{n}.

For n = 2, we have d_{2} = 6 monotone functions,

D_{2} = {0000, 0001, 0011, 0101, 0111, 1111}

and r_{2} = 5 equivalence classes in D_{2}, namely

R_{2} = {{0000}, {0001}, {0011, 0101}, {0111}, {1111}}.

Furthermore, there are two self-dual functions Λ_{2} = {0011, 0101} and they form one equivalence class. Hence λ_{2} = 2 and q_{2} = 1.

For n = 3, we have d_{3} = 20 monotone functions and r_{3} = 10 equivalence classes in D_{3}. There are four self-dual functions

Λ_{3} = {01010101, 00110011, 00001111, 00010111}

and they form two equivalence classes:

Q_{3} = {{01010101, 00110011, 00001111}, {00010111}}.

Hence, λ_{3} = 4 and q_{3} = 2.

3 Counting functions from B to D_{n}

Let n ≥ 0. By Lemma 1, the poset D_{n+1} is isomorphic to the poset D_{n}^{B}—the poset of monotone functions from B = {0, 1} to D_{n}. Consider a monotone function H : B → D_{n}. It can be represented as the concatenation:

H = H(0) · H(1)

with H(0), H(1) ∈ D_{n} and H(0) ≤ H(1). The dual of H is

H^{∗} = H(1)^{∗} · H(0)^{∗}.

Recall that we identify each function in D_{n} with the sequence of bits. If H ∈ D_{n+1} is self-dual then it is of the form b · b^{∗} with b ∈ D_{n} and b ≤ b^{∗}. And vice versa, if b ∈ D_{n} and b ≤ b^{∗}, then the concatenation b · b^{∗} is self-dual in D_{n+1}. Therefore, we have proved the following theorem. Theorem 6. For every n ≥ 0, the number of self-dual functions λ_{n+1} is equal to the number of elements b ∈ D_{n} that satisfy b ≤ b^{∗}. In other words

λ_{n+1} = ∑_{\begin{matrix}b∈D_{n} \\ b≤b^{∗} \end{matrix}} 1.

Furthermore,

λ_{n+1} = ∑_{\begin{matrix}b∈R_{n} \\ b≤b^{∗} \end{matrix}} γ(b).

Here we identify each class b ∈ R_{n} with its representative.

The following corollary is presented, in a different form, in [11] Corollary 7. For every n ≥ 0, we have λ_{n+1} ≤ d_{n}.

The next result is straightforward. Lemma 8. Let b be a function in D_{n}. Then

• b ≤ b^{∗}, only if ℓ(b) ≤ 2^{n−1}.

• if ℓ(b) = 2^{n−1} and b ≤ b^{∗}, then b = b^{∗}, and b is self-dual in D_{n}.

• if b is self-dual, then ℓ(b) = 2^{n−1}.

• ℓ(b^{∗}) = 2^{n} − ℓ(b), hence, |{f ∈ D_{n} : ℓ(f) < 2^{n−1}}| = |{f ∈ D_{n} : ℓ(f) > 2^{n−1}}|.

As a corollary we have the following theorem.

Theorem 9.

λ_{n+1} = λ_{n} + ∑_{\begin{matrix}b∈R_{n} \\ ℓ(b)<2^{n−1} \\ b≤b^{∗} \end{matrix}} γ(b).

λ_{n+1} ≤ λ_{n} + \frac{1}{2}(d_{n} − λ_{n}) = \frac{1}{2}(d_{n} + λ_{n}).

The second part of the theorem is presented, in a different form, in [11]. Notice that λ_{n+1} = \frac{1}{2}(d_{n} + λ_{n}) for each n ≤ 3.

4 Counting functions from B^{2} to D_{n}

Let n ≥ 0. By Lemma 1, the poset D_{n+2} is isomorphic to the poset D_{n}^{B^{2}}—the poset of monotone functions from B^{2} = {00, 01, 10, 11} to D_{n}. Consider a monotone function H : B^{2} → D_{n}. It can be represented as the concatenation:

H(00) · H(01) · H(10) · H(11)

and as the graph:

\begin{matrix}H(00) \\ H(01) \\ H(10) \\ H(11) \end{matrix}

where the vertices represent the set of values H(B^{2}) and the edges represent the partial order:

H(00) ≤ H(01) ≤ H(11) and H(00) ≤ H(10) ≤ H(11).

Recall that we identify each function in D_{n} with the sequence of bits. The dual of H is represented by

H(11)^{∗} · H(10)^{∗} · H(01)^{∗} · H(00)^{∗}.

If H is self-dual then H(00) = H(11)^{∗}, H(01) = H(10)^{∗}, H(10) = H(01)^{∗}, and H(11) = H(00)^{∗} and we can represent H as the graph

d^{∗} bb^{∗} d

where d denotes H(11) and b denotes H(01). Furthermore, d^{∗} denotes H(00) and b^{∗} denotes H(10). If H is self-dual then it is of the form d^{∗} · b · b^{∗} · d with b, d ∈ D_{n} and d ≥ b|b^{∗}. And vice versa, if b, d ∈ D_{n}, and d ≥ b|b^{∗}, then, by Lemma 2, d^{∗} ≤ b&b^{∗} and the concatenation d^{∗} · b · b^{∗} · d is self-dual in D_{n+2}. Hence, we have proved the following theorem.

Theorem 10. For every n ≥ 0, the number of self-dual functions λ_{n+2} is equal to the number of pairs b, d ∈ D_{n} which satisfy condition d ≥ b|b^{∗}. In other words

λ_{n+2} = ∑_{b∈D_{n}} re(b|b^{∗}, ⊤).

Furthermore, Lemma 5 implies

λ_{n+2} = ∑_{b∈R_{n}} γ(b) · re(b|b^{∗}, ⊤).

Here we identify each class b ∈ R_{n} with its representative.

Corollary 11. For every n ≥ 0, we have λ_{n+2} ≥ d_{n}.

By Colloraries 7 and 11, we have that

λ_{1} ≤ d_{0} ≤ λ_{2} ≤ d_{1} ≤ ⋯ ≤ λ_{n+1} ≤ d_{n} ≤ λ_{n+2} ≤ ⋯

and we have the following estimates for the unknown value of λ_{10}

d_{8} ≤ λ_{10} ≤ d_{9}.

5 Counting functions from B^{4} to D_{n}

Let n ≥ 0. By Lemma 1, the poset D_{n+4} is isomorphic to the poset D_{n}^{B^{4}}—the set of monotone functions from B^{4} = {0000, 0001, …, 1111} to D_{n}. Consider a monotone function H: B^{4} → D_{n}. It can be represented as the concatenation

H(0000) · H(0001) · H(0010) · H(0011) · H(0100) · H(0101) · H(0110) · H(0111) · H(1000) · H(1001) · H(1010) · H(1011) · H(1100) · H(1101) · H(1110) · H(1111). and its dual as

H(1111)^{∗} · H(1110)^{∗} · H(1101)^{∗} · H(1100)^{∗} · H(1011)^{∗} · H(1010)^{∗} · H(1001)^{∗} · H(1000)^{∗} · H(0111)^{∗} · H(0110)^{∗} · H(0101)^{∗} · H(0100)^{∗} · H(0011)^{∗} · H(0010)^{∗} · H(0001)^{∗} · H(0000)^{∗}.

If H is self-dual, then

H(0000) = H(1111)^{∗},  H(0001) = H(1110)^{∗},
H(0010) = H(1101)^{∗},  H(0011) = H(1100)^{∗},
H(0100) = H(1011)^{∗},  H(0101) = H(1010)^{∗},
H(0110) = H(1001)^{∗},  H(0111) = H(1000)^{∗}.

Recall that we identify each function in D_{n} with the sequence of bits. Similarly, as in Section 4 we can represent H as the graph, see Figure 1 where h represents H(1111), d represents H(0111), e represents H(1011), f represents H(1101), g represents H(1110), …, and h^{∗} represents H(0000).

Theorem 12. For each a, b, c ∈ D_{n}, for each h ∈ D_{n} such that h ≥ a|b|c|a^{∗}|b^{∗}|c^{∗}, for each d, e, f, g ∈ D_{n} such that

a|b|c ≤ d ≤ h,
a|b^{∗}|c^{∗} ≤ e ≤ h,
b|a^{∗}|c^{∗} ≤ f ≤ h,
c|a^{∗}|b^{∗} ≤ g ≤ h,

the concatenation

h^{∗} · g^{∗} · f^{∗} · a · e^{∗} · b · c · d · d^{∗} · c^{∗} · b^{∗} · e · a^{∗} · f · g · h

represents a self-dual function in D_{n+4}; see Figure 1. And vice versa, each self-dual function in D_{n+4} is of the above form.

The proof is straightforward.

h^{∗} g^{∗} f^{∗} e^{∗} a bcd d^{∗} c^{∗} b^{∗} a^{∗} efgh

Figure 1: Structure of H : B^{4} → D_{n} if H is self-dual. The graph represents the hypercube B^{4}. The label at a vertex x represents the value H(x) ∈ D_{n}.

Theorem 13. The number of self-dual functions

λ_{n+4} = ∑_{a,b,c∈D_{n}} ∑_{\begin{matrix}h∈D_{n} \\ h≥(a|b|c|a^{∗}|b^{∗}|c^{∗}) \end{matrix}} re(a|b|c, h) · re(a|b^{∗}|c^{∗}, h) · re(b|a^{∗}|c^{∗}, h) · re(c|a^{∗}|b^{∗}, h).

Theorem 14. For each h ∈ D_{n} such that h ≥ h^{∗}, for each a, b, c ∈ D_{n}, h^{∗} ≤ a, b, c ≤ h, for each d, e, f, g ∈ D_{n} such that

a|b|c ≤ d ≤ h,
a|b^{∗}|c^{∗} ≤ e ≤ h,
b|a^{∗}|c^{∗} ≤ f ≤ h,
c|a^{∗}|b^{∗} ≤ g ≤ h,

the concatenation

h^{∗} · g^{∗} · f^{∗} · a · e^{∗} · b · c · d · d^{∗} · c^{∗} · b^{∗} · e · a^{∗} · f · g · h

represents a self-dual function in D_{n+4}; see Figure 1. And vice versa, each self-dual function in D_{n+4} is of the above form.

Let

F (h) = ∑_{\begin{matrix}a,b,c∈D_{n} \\ h≥a,b,c≥h^{∗} \end{matrix}} re(a|b|c, h) · re(a|b^{∗}|c^{∗}, h) · re(b|a^{∗}|c^{∗}, h) · re(c|a^{∗}|b^{∗}, h).

Observe that F (h) is the number of self-dual functions H ∈ D_{n}^{B^{4}}, with H(0000) = h^{∗} and H(1111) = h. Therefore,

λ_{n+4} = ∑_{\begin{matrix}h∈D_{n} \\ h^{∗}≤h \end{matrix}} F (h).

Furthermore, Lemma 5 implies that for any two elements h_{1} ∼ h_{2} we have F (h_{1}) = F (h_{2}). Hence, we have

λ_{n+4} = ∑_{\begin{matrix}h∈R_{n} \\ h≥h^{∗} \end{matrix}} γ(h) · F (h).

Here again we identify the class h ∈ R_{n} with its representative. Similarly as in Lemma 8 we can observe that h ≥ h^{∗}, only if ℓ(h) ≥ 2^{n−1}. Furthermore, if ℓ(h) = 2^{n−1} and h ≥ h^{∗}, then h = h^{∗}, and we have only one self-dual function H ∈ D_{n}^{B^{4}} with H(0000) = H(1111) = h. Hence,

λ_{n+4} = λ_{n} + ∑_{\begin{matrix}h∈R_{n} \\ h^{∗}≤h \\ ℓ(h)>2^{n−1} \end{matrix}} γ(h) · F (h).  (1)

6 Implementation

In this section we present three algorithms based on results from the previous sections. We implemented the algorithms in Rust and ran them on a 32-thread Xeon CPU.

Algorithm 1 Calculation of λ_{n+2}

Input: R_{n} (each class is represented by its minimal element) with re(x, ⊤) for all x ∈ R_{n} Output: s = λ_{n+2}

1: Initialize s = 0, 2: for all b ∈ R_{n} do 3: s = s + re(b|b^{∗}, ⊤) · γ(b) 4: end for

Algorithm 1 is based on Theorem 10. After loading the preprocessed data into main memory, λ_{9} was computed in 15 seconds. However, preprocessing (the calculation of R_{7} and its intervals) took approximately 2.5 hours.

Algorithm 2 Calculation of λ_{n+4} based on Theorem 13

Input: D_{n}; R_{n} (each class is represented by its minimal element); re(x, y) for all (x, y) ∈ D_{n} × D_{n}

Output: s = λ_{n+4} 1: Initialize s = 0, 2: for all a ∈ R_{n} do 3: for all b ∈ D_{n} do 4: for all c ∈ D_{n} do 5: for all h ∈ D_{n}, h ≥ (a|b|c|a^{∗}|b^{∗}|c^{∗}) do 6: s = s + re(a|b|c, h) · re(a|b^{∗}|c^{∗}, h) · re(b|a^{∗}|c^{∗}, h) · re(c|a^{∗}|b^{∗}, h) · γ(a) 7: end for 8: end for 9: end for 10: end for

Using our implementation of the algorithm, we calculated λ_{9} in 76 seconds, and the preprocessing was almost instantaneous.

Algorithm 3 Calculation of λ_{n+4} based on Equation 1

Input: D_{n}; R_{n} (each class is represented by its minimal element); re(x, y) for all (x, y) ∈ D_{n} × D_{n}

Output: s = λ_{n+4} 1: Initialize s = λ_{n}, 2: for all h ∈ R_{n}, h^{∗} ≤ h, ℓ(h) > 2^{n−1} do 3: for all a ∈ D_{n}, h^{∗} ≤ a ≤ h do 4: for all b ∈ D_{n}, h^{∗} ≤ b ≤ h do 5: for all c ∈ D_{n}, h^{∗} ≤ c ≤ h do 6: s = s + re(a|b|c, h) · re(a|b^{∗}|c^{∗}, h) · re(b|a^{∗}|c^{∗}, h) · re(c|a^{∗}|b^{∗}, h) · γ(h) 7: end for 8: end for 9: end for 10: end for

The calculation of λ_{9} using our implementation of the algorithm lasted approximately 25 minutes. In all cases, we have obtained the following value:

λ_{9} = 423295099074735261880,

which confirms the result of Brouwer et al. [2].

Algorithms 2 and 3 differ in the order in which values of the functions are chosen. It should be noted that Algorithm 2 works much faster than Algorithm 3 due to a significantly smaller number of iterations, requiring only 76 seconds compared to 25 minutes of computation time.

7 Calculation of q_{n}

The number of inequivalent self-dual monotone Boolean functions (q_{n}) is listed on the OEIS \underline{A008840} sequence. In order to calculate q_{n} for n ≤ 7, we can use the following simple approach:

q_{n} = ∑_{\begin{matrix}a∈R_{n} \\ a=a^{∗} \end{matrix}} 1.

For n = 8, this direct approach becomes computationally infeasible. Instead, we apply Burnside’s lemma to our specific problem. Recall that each permutation π ∈ S_{n} can be represented as a product of disjoint cycles. The cycle type of π is defined as the tuple of lengths of its disjoint cycles arranged in increasing order. For example, the type of permutation π = (12)(34)(567) is (2, 2, 3), and its total length is 7. In the sequel, we use a list of cycle types in S_{n} and we represent each cycle type by its index in the list, see the tables in Section 7.2.

To calculate q_{8} we use the approach developed in [8, 9, 10].

q_{n} = \frac{1}{n!} ∑_{i=1}^{k} μ_{i} · |Φ(π_{i}, Λ_{n})|  (2)

where:

• q_{n} is the number of equivalence classes in Λ_{n},

• k is the number of different cycle types in S_{n},

• π_{i} is a representative permutation of cycle type i,

• Φ(π_{i}, Λ_{n}) is the set of all elements in Λ_{n} which are fixed under π_{i},

• μ_{i} number of permutations π ∈ S_{n} with cycle type i.

For n = 1, we have λ_{1} = q_{1} = 1. For n = 2, we have two permutations: the identity e with |Φ(e, Λ_{2})| = |Λ_{2}| = 2, and the inversion π = (12) with three cycles when acting on B^{2} namely: C_{1} = (00), C_{2} = (01, 10), and C_{3} = (11). The two elements 01 and 10 form a cycle, hence, if a function f ∈ D_{n} is a fixed point of π, then f(01) = f(10). On the other hand, if f is self-dual, then it represents an mls on {1, 2}, and f(01) ≠ f(10), because 01 and 10 represent subsets {1} and {2} in {1, 2} which are the complements of each other. Thus, the set of fixed points Φ((12), Λ_{2}) = ∅. By Burnside’s lemma, we have

q_{2} = \frac{1}{2}(|Φ(e, Λ_{2})| + |Φ((12), Λ_{2})|) = \frac{1}{2}(2 + 0) = 1.

Indeed, there is one equivalence class in Λ_{2}, namely {0101, 0011}. We have just shown that Φ((12), Λ_{2}) = ∅. Similarly, we can show that Φ(π, Λ_{8}) = ∅, if π = (12)(34)(56)(78). Indeed, for π, the two elements 01010101, 10101010 ∈ B^{8} form a cycle. Hence, if f ∈ D_{8} is a fixed point of π, then f(01010101) = f(10101010). On the other side, if f is self-dual, then f(01010101) ≠ f(10101010), because 101010101 and 01010101 represent subsets of {1, …, 8} which are the complements of each other. Lemma 15. Suppose that n is even, and a permutation π, when acting on {1, …, n}, is a product of disjoint cycles of even length. Then Φ(π, Λ_{n}) = ∅. Proof. If the permutation π is a product of disjoint cycles of even length, then there exist two elements x, y ∈ B^{n} such that:

• x and y represent subsets of {1, …, n} which are the complements of each other.

• π(x) = y and π(y) = x, so x, y form a cycle in B^{n}. Hence, if f ∈ D_{n} is a fixed point of π, then f(x) = f(y). On the other side, if f is self-dual, then f(x) ≠ f(y). Corollary 16. We have Φ(π, Λ_{8}) = ∅ for each of the following permutations: (12345678), (12)(345678), (1234)(5678), (12)(34)(5678), and (12)(34)(56)(78).

For n = 3, we have three cycle types:

• the identity e with |Φ(e, Λ_{3})| = |Λ_{3}| = 4

• three inversions, with |Φ((12), Λ_{3})| = 2

• two cycles of length 3 with |Φ((123), Λ_{3})| = 1 By Burnside’s lemma, we have

q_{3} = \frac{1}{6}(4 + 3 · 2 + 2 · 1) = 2.

Notice, that the element MAJ = 00010111 ∈ D_{3} is self-dual, and is a fixed point for every permutation π ∈ S_{3}. Hence, for every π ∈ S_{3}, Φ(π, Λ_{3}) ≠ ∅. Similarly, we can show the following lemma: Lemma 17. For each odd n and each permutation π ∈ S_{n}, we have Φ(π, Λ_{n}) ≠ ∅. Proof. Consider the function MAJ ∈ D_{n}, which returns MAJ(x) = 1 if and only if ℓ(x) > n/2. The function MAJ is self-dual, and is a fixed point for every permutation π ∈ S_{n}.

7.1 Algorithms counting fixed points in Λ_{n}

In order to count or generate fixed points of permutations in Λ_{n} we use Lemma 15 and two algorithms.

Algorithm 4 Generation of Φ(π, Λ_{n})

Input: Φ(π, D_{n})

Output: S = Φ(π, Λ_{n}) 1: Initialize S = ∅ 2: for all b ∈ Φ(π, D_{n}) do 3: if b = b^{∗} then 4: Add b to S 5: end if 6: end for

Algorithm 4 simply runs through the set of fixed points Φ(π, D_{n}) and selects self-dual functions. For example, there are five fixed points in

Φ((123), D_{3}) = {00000000, 00000001, 00010111, 01111111, 11111111}

and only one of them is self-dual, namely 00010111, so |Φ((123), Λ_{3})| = 1.

Algorithm 5 Calculation of |Φ(π, Λ_{n+2})|

Input: Φ(π, D_{n})

Output: s = |Φ(π, Λ_{n+2})| 1: Initialize s = 0, 2: for all b ∈ Φ(π, D_{n}) do 3: Calculate up = |{h ∈ Φ(π, D_{n}) : h ≥ (b|b^{∗})}| 4: s = s + up 5: end for

Algorithm 5 is based on the following facts. Consider a permutation π acting on B^{n} and on D_{n}. We can say that π also acts on B^{n+2} and on D_{n+2}. By [10, Lemma 6], Φ(π, D_{n+2}) = Φ(π, D_{n})^{B^{2}}. Every function F ∈ Φ(π, D_{n})^{B^{2}} can be represented as the concatenation

F = F (00) · F (01) · F (10) · F (11),

where F (00), F (01), F (10), F (11) ∈ Φ(π, D_{n}), and

F (00) ≤ F (01), F (10) ≤ F (11).

The dual of F can be represented as

F^{∗} = F (11)^{∗} · F (10)^{∗} · F (01)^{∗} · F (00)^{∗}.

If F is self-dual, then it is of the form

dbb^{∗}d^{∗},

where b, d ∈ Φ(π, D_{n}) and d^{∗} ≥ b|b^{∗}. Notice that this implies that d ≤ b&b^{∗}. On the other hand, if b, d ∈ Φ(π, D_{n}) and d^{∗} ≥ b|b^{∗}, then dbb^{∗}d^{∗} ∈ Φ(π, Λ_{n+2}).

7.2 Result tables

In this section we present three tables which contain the values of |Φ(π_{i}, Λ_{n})|, for n ∈ {6, 7, 8} and all permutations.

\begin{matrix}i & π_{i} & μ_{i} & |Φ(π_{i}, Λ_{6})| \\ 1 & (1) & 1 & 2646 \\ 2 & (12) & 15 & 372 \\ 3 & (123) & 40 & 54 \\ 4 & (1234) & 90 & 18 \\ 5 & (12345) & 144 & 6 \\ 6 & (123456) & 120 & 0 \\ 7 & (12)(34) & 45 & 130 \\ 8 & (12)(345) & 120 & 18 \\ 9 & (12)(3456) & 90 & 0 \\ 10 & (123)(456) & 40 & 18 \\ 11 & (12)(34)(56) & 15 & 0 \end{matrix}

q_{6} = \frac{1}{720} ∑_{i=1}^{11} μ_{i} · |Φ(π_{i}, Λ_{6})| = \frac{21600}{720} = 30.

Table 2: Values of |Φ(π_{i}, Λ_{6})| and calculation of q_{6}.

\begin{matrix}i & π_{i} & μ_{i} & |Φ(π_{i}, Λ_{7})| \\ 1 & (1) & 1 & 1422564 \\ 2 & (12) & 21 & 43556 \\ 3 & (123) & 70 & 1332 \\ 4 & (1234) & 210 & 216 \\ 5 & (12345) & 504 & 34 \\ 6 & (123456) & 840 & 12 \\ 7 & (1234567) & 720 & 3 \\ 8 & (12)(34) & 105 & 7212 \\ 9 & (12)(345) & 420 & 218 \\ 10 & (12)(3456) & 630 & 76 \\ 11 & (12)(34567) & 504 & 6 \\ 12 & (123)(456) & 280 & 210 \\ 13 & (123)(4567) & 420 & 6 \\ 14 & (12)(34)(56) & 105 & 1284 \\ 15 & (12)(34)(567) & 210 & 36 \end{matrix}

q_{7} = \frac{1}{5040} ∑_{i=1}^{15} μ_{i} · |Φ(π_{i}, Λ_{7})| = \frac{3608640}{5040} = 716.

Table 3: Values of |Φ(π_{i}, Λ_{7})| and calculation of q_{7}.

\begin{matrix}i & π_{i} & μ_{i} & |Φ(π_{i}, Λ_{8})| \\ 1 & (1) & 1 & 229809982112 \\ 2 & (12) & 28 & 300991356 \\ 3 & (123) & 112 & 476120 \\ 4 & (1234) & 420 & 18984 \\ 5 & (12345) & 1344 & 662 \\ 6 & (123456) & 3360 & 296 \\ 7 & (1234567) & 5760 & 46 \\ 8 & (12345678) & 5040 & 0 \\ 9 & (12)(34) & 210 & 12716048 \\ 10 & (12)(345) & 1120 & 18384 \\ 11 & (12)(3456) & 2520 & 7952 \\ 12 & (12)(34567) & 4032 & 116 \\ 13 & (12)(345678) & 3360 & 0 \\ 14 & (123)(456) & 1120 & 21020 \\ 15 & (123)(4567) & 3360 & 120 \\ 16 & (123)(45678) & 2688 & 20 \\ 17 & (1234)(5678) & 1260 & 0 \\ 18 & (12)(34)(56) & 420 & 2230724 \\ 19 & (12)(34)(567) & 1680 & 3152 \\ 20 & (12)(34)(5678) & 1260 & 0 \\ 21 & (12)(345)(678) & 1120 & 1488 \\ 22 & (12)(34)(56)(78) & 105 & 0 \end{matrix}

q_{8} = \frac{1}{40320} ∑_{i=1}^{22} μ_{i} · |Φ(π_{i}, Λ_{8})| = \frac{241980137280}{40320} = 6001501.

Table 4: Values of |Φ(π_{i}, Λ_{8})| and calculation of q_{8}.

References

[1] J. C. Bioch and T. Ibaraki, Generating and approximating nondominated coteries, IEEE Trans. Parallel Distrib. Syst. 6 (1995), 905–914.

[2] A. E. Brouwer, C. F. Mills, W. H. Mills, and A. Verbeek, Counting families of mutually intersecting sets, Electron. J. Combin. 20 (2013), Article P8.

[3] A. E. Brouwer and A. Verbeek, Counting families of mutually intersecting sets, Report ZN 41, Mathematical Centre, Amsterdam, 1972.

[4] D. E. Loeb and A. R. Conway, Voting fairly: transitive maximal intersecting families of sets, J. Combin. Theory Ser. A 91 (2000), 386–410.

[5] C. F. Mills and W. H. Mills, The calculation of λ(8), preprint, 1979.

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

[7] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Available at

https://oeis.org.

[8] B. Pawelski, On the number of inequivalent monotone Boolean functions of 8 variables, J. Integer Sequences 25 (2022), Article 22.7.7.

[9] B. Pawelski, On the number of inequivalent monotone Boolean functions of 9 variables, IEEE Trans. Inform. Theory 70 (2024), 5358–5364.

[10] A. Szepietowski, Fixes of permutations acting on monotone Boolean functions, J. Integer Sequences 25 (2022), Article 22.9.6.

[11] M. Timotijević, Note on combinatorial structure of self-dual simplicial complexes, Mat. Vesnik 71 (2019), 104–122.

2020 Mathematics Subject Classification: Primary 06E30.

Keywords: monotone Boolean function, self-dual monotone Boolean function, Dedekind number, Hosten-Morris number.

(Concerned with sequences \underline{A001206} and \underline{A008840}.)