Divisibility Properties of Dedekind Numbers

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 We study some divisibility properties of Dedekind numbers. We show that the

ninth Dedekind number is congruent to 6 modulo 210.

1 Introduction

We define D_{n} to be the set of all monotone Boolean functions of n variables. The cardinality of this set, d_{n}, is known as the n-th Dedekind number. Values of d_{n} are described by the OEIS (On-Line Encyclopedia of Integer Sequences) sequence \underline{A000372} (see Table 1).

\begin{matrix}n & d_{n} & r_{n} \\ 0 & 2 & 2 \\ 1 & 3 & 3 \\ 2 & 6 & 5 \\ 3 & 20 & 10 \\ 4 & 168 & 30 \\ 5 & 7,581 & 210 \\ 6 & 7,828,354 & 16,353 \\ 7 & 2,414,682,040,998 & 490,013,148 \\ 8 & 56,130,437,228,687,557,907,788 & 1,392,195,548,889,993,358 \end{matrix}

Table 1: Known values of d_{n} (\underline{A000372}) and r_{n} (\underline{A003182}).

In 1990, Wiedemann calculated d_{8} [11]. His result was confirmed in 2001 by Fidytek, Mostowski, Somla, and Szepietowski [4]. The impulse for writing our paper came from the letter from Wiedemann to Sloane [12] informing about the computation of the eighth Dedekind number, specifically this fragment: “Unfortunately, I don’t see how to test it...”. Wiedemann only knew that d_{8} is even. Despite its obvious importance, there is a lack of studies on the divisibility of Dedekind numbers. As far as we know, the only paper concerning this question is Yamamoto’s paper [13], where he shows that if n is even, then d_{n} is also even; he also states (without proof) that d_{9} is even and d_{11} is odd.

Our research aims to fill this lack by proposing new methods to determine the divisibility of Dedekind numbers. As an application of these methods, we compute remainders of d_{9} divided by one-digit prime numbers, which (we hope) will help to verify the value d_{9} after its first computation.

Our main result is the following system of congruences:

d_{9} ≡ 0 (mod 2),
d_{9} ≡ 0 (mod 3),
d_{9} ≡ 1 (mod 5),
d_{9} ≡ 6 (mod 7).

By the Chinese remainder theorem, we have

d_{9} ≡ 6 (mod 210).

Recently, after the preprint of this paper was published on ArXiv, two independent research teams [5, 7] reported the same value:

d_{9} = 286386577668298411128469151667598498812366,

which confirms our results.

2 Preliminaries

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 any function from B^{n} into B. There are 2^{n} elements in B^{n} and 2^{2^{n}} Boolean functions with n variables. There is the order relation in B (namely: 0 ≤ 0, 0 ≤ 1, 1 ≤ 1) and the following 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 ⟹ h(x) ≤ h(y).

Let D_{n} denote the set of monotone functions with n variables and let d_{n} denote |D_{n}|. 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 shall represent the elements of D_{n} as strings of bits of length 2^{n}. Two elements of D_{0} will be represented as 0 and 1. Any element g ∈ D_{1} can be represented as the concatenation g(0) ∗ g(1), where g(0), g(1) ∈ D_{0} and g(0) ≤ g(1). Hence D_{1} = {00, 01, 11}. Each element of g ∈ D_{2} is the concatenation (string) of four bits: g(00) ∗ g(10) ∗ g(01) ∗ g(11) which can be represented as a concatenation g_{0} ∗ g_{1}, where g_{0}, g_{1} ∈ D_{1} and g_{0} ≤ g_{1}. Hence D_{2} = {0000, 0001, 0011, 0101, 0111, 1111}. Similarly, any element of g ∈ D_{n} can be represented as a concatenation g_{0} ∗ g_{1}, where g_{0}, g_{1} ∈ D_{n−1} and g_{0} ≤ g_{1}. Therefore, we can treat functions in D_{n} as sequences of bits and as integers. We let ⪯ denote the total order in D_{n} induced by the total order in integers.

For a set Y ⊆ D_{n}, by Y^{2} we denote the Cartesian power Y^{2} = Y × Y, that is the set of all ordered pairs (x, y) with x, y ∈ Y. Similarly for more than two factors, we write Y^{k} for the set of ordered k-tuples of elements of Y. We let ⊤ denote the maximal element in D_{n}, that is, ⊤ = (1 … 1); and ⊥ denote the minimal element in D_{n}, that is, ⊥ = (0 … 0). For two elements x, y ∈ D_{n}, we let x|y denote the bitwise or; and x&y denote the bitwise and. Furthermore, we let re(x, y) denote |{z ∈ D_{n} : x ≤ z ≤ y}|. Note that re(x, ⊤) = |{z ∈ D_{n} : x ≤ z}| and re(⊥, y) = |{z ∈ D_{n} : z ≤ y}|.

2.1 Posets

A poset (partially ordered set) (S, ≤) consists of a set S together with a binary relation (partial order) ≤ which is reflexive, transitive, and antisymmetric. Given two posets (S, ≤) and (T, ≤) a function f : S → T is monotone, if x ≤ y implies f(x) ≤ f(y). By T^{S} we 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.

In this paper we use the following well-known lemma; see [3, 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}.

3 Divisibility of Dedekind numbers by 2

In 1952, Yamamoto [13] proved that if n is even, then d_{n} is also even; he also stated (without proof) that d_{9} is even and d_{11} is odd. In order to prove that d_{9} is even, we will leverage the duality property of Boolean functions. For each x ∈ D_{n}, we have dual x^{d} which is obtained by reversing and negating all bits. For example, 1111^{d} = 0000 and 0001^{d} = 0111. An element x ∈ D_{n} is self-dual if x = x^{d}. For example, 0101 and 0011 are self-duals in D_{2}. If x is not self-dual, and y = x^{d} ≠ x, then y^{d} = x. Thus, non-self-duals form pairs of the form (x, x^{d}), where x ≠ x^{d}. Let k_{n} denote the number of these pairs and let λ_{n} denote the number of self-dual functions in D_{n}. We have that d_{n} = 2k_{n} + λ_{n}. Hence λ_{n} ≡ d_{n} (mod 2). Values of λ_{n} are described by the OEIS sequence \underline{A001206}; see Table 2. The last known term of this sequence, λ_{9}, was calculated in 2013 by Brouwer et al. [2].

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

Table 2: Known values of λ_{n} (\underline{A001206}).

Corollary 2. We have d_{9} ≡ λ_{9} ≡ 0 (mod 2).

One can directly check that d_{n} ≡ λ_{n} (mod 2) for n ≤ 8.

4 Divisibility of Dedekind numbers by 3

By Lemma 1, the poset D_{n+3} is isomorphic to the poset D_{n}^{B^{3}}—the set of monotone functions from B^{3} = {000, 001, 010, 100, 110, 101, 011, 111} to D_{n}. Now consider the group S_{3}—the permutations on {1, 2, 3}. The group S_{3} is isomorphic to the automorphism group Aut(B^{3}) of the Boolean lattice B^{3}. The automorphism group Aut(B^{3}) acts in a natural way on D_{n}^{B^{3}} by

α(f) = f ∘ α^{−1}

for all α ∈ Aut(B^{3}) and all f ∈ D_{n}^{B^{3}}. Let O(f) = {α(f) ∈ D_{n}^{B^{3}} : α ∈ Aut(B^{3})} denote the orbit of f under this action and by γ(f) = |O(f)| its cardinality. The orbits form a partition of D_{n+3} = D_{n}^{B^{3}}. Each of these orbits has one, three, or six elements. Moreover, an orbit O(f) has one element if and only if f(001) = f(010) = f(100) and f(011) = f(101) = f(110). Such a function f can be identified with a monotone function from the path P_{4} to D_{n}. Hence,

d_{n+3} ≡ |D_{n}^{P_{4}}| (mod 3).

It is well known, see [1, 10], that the number of monotone functions from the path P_{4} = (a < b < c < d) to a poset S is equal to the sum of the elements of the third power of M(S)—the incidence matrix of S. For example, for the poset D_{1} = {00 < 01 < 11}, we have

M(D_{1}) = ( \begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix} )

and

M(D_{1})^{3} = ( \begin{matrix}1 & 3 & 6 \\ 0 & 1 & 3 \\ 0 & 0 & 1 \end{matrix} ) .

The sum of the elements of (M(D_{1})^{3}) is equal to 15, which is equal to |D_{1}^{P_{4}}|—the number of monotone functions from P_{4} to D_{1}.

Furthermore, consider D_{2} = {0000, 0001, 0011, 0101, 0111, 1111} and its incidence matrix:

M(D_{2}) = ( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} ) .

Now consider the third power of the incidence matrix of D_{2}:

M(D_{2})^{3} = ( \begin{matrix}1 & 3 & 6 & 6 & 14 & 20 \\ 0 & 1 & 3 & 3 & 9 & 14 \\ 0 & 0 & 1 & 0 & 3 & 6 \\ 0 & 0 & 0 & 1 & 3 & 6 \\ 0 & 0 & 0 & 0 & 1 & 3 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} ) .

The sum of the elements of (M(D_{2})^{3}) is equal to 105, which is equal to |D_{2}^{P_{4}}|—the number of monotone functions from P_{4} to D_{2}. In a similar we can compute |D_{n}^{P_{4}}| for n = 3, 4, 5. Unfortunately, this method cannot be easily applied for n = 6, because M(D_{6}) is too large. However, Pawelski [8] proposed another method: |D_{(n+m)}^{P_{4}}| = |D_{n}^{P_{4}×B^{m}}| = |(D_{n}^{P_{4}})^{B^{m}}| (also see [10]). Using the same program as used in [8] to compute |D_{5}^{P_{4}}| we can calculate |D_{6}^{P_{4}}| and the result (see Table 3) is divisible by 3.

Corollary 3. As |D_{6}^{P_{4}}| = 868329572680304346696 is divisible by 3, the quantity d_{9} is also divisible by 3.

One can directly check that d_{n+3} ≡ |D_{n}^{P_{4}}| (mod 3) for n ≤ 5.

\begin{matrix}n & |D_{n}^{P_{4}}| & |D_{n}^{P_{4}}| mod 3 \\ 0 & 5 & 2 \\ 1 & 15 & 0 \\ 2 & 105 & 0 \\ 3 & 3,490 & 1 \\ 4 & 2,068,224 & 0 \\ 5 & 262,808,891,710 & 1 \\ 6 & 868,329,572,680,304,346,696 & 0 \end{matrix}

Table 3: Known values of |D_{n}^{P_{4}}|. Note that d_{n+3} ≡ |D_{n}^{P_{4}}| (mod 3).

5 Main lemma

In the sequel we shall use another definition of a group acting on D_{n}^{B^{k}}. In order to do this it is convenient to identify the lattice D_{n} = B^{B^{n}} with the isomorphic up-set lattice U_{n} of B^{n}. An isomorphism is given by h : D_{n} → U_{n}, where h(x) = x^{−1}(1) for all x ∈ D_{n}. For β ∈ Aut(B^{n}) and x ∈ D_{n}, we have

h(β(x)) = β(h(x)).

Let P and Q be two posets and let P^{Q} be the poset of monotone functions from Q to P. Now, we can define an action of Aut(P) on P^{Q} by setting

β(f) = β ∘ f

for all β ∈ Aut(P) and f ∈ P^{Q}. We let

O(f) = {β(f) : β ∈ Aut(P)}

denote the orbit of f under this action. Additionally, for p ∈ P, we write

[p] = {β(p) : β ∈ Aut(P)}

for the orbit of p under the natural action of Aut(P) on P.

We use ∼ to denote an equivalence relation on D_{n}. Namely, two functions p, r ∈ D_{n} are equivalent, p ∼ r, if there is an automorphism α ∈ Aut(D_{n}) such that p = α(r). For a function p ∈ D_{n} its equivalence class is the set [p] = {r ∈ D_{n} : r ∼ p}. We let γ(f) denote |[f]|. For m > 1, let E_{n,m} = {p ∈ D_{n} : γ(f) ≡ 0 (mod m)} and E_{n,m}^{c} = D_{n} − E_{n,m}. For the class [p], we define its canonical representative as the one element in [p] chosen to represent the class. One of the possible approaches is to choose its minimal (according to the total order ⪯) element [11]. Sometimes we shall identify the class [p] with its canonical representative and treat [p] as an element in D_{n}. We let R_{n} denote the set of equivalence classes and r_{n} the number of equivalence classes; that is, r_{n} = |R_{n}|. Values of r_{n} are described by \underline{A003182} OEIS sequence; see Table 1.

Lemma 4. For every q ∈ Q and every f ∈ P^{Q}, the integer |[f(q)]| divides |O(f)|.

Proof. For every p ∈ [f(q)] we define

G(p) := {g ∈ O(f) : g(q) = p}.

The sets G(p), p ∈ [f(q)] form a partition of O(f) and the sets G(p) have the same cardinality. Indeed, for every β ∈ Aut(P),

g ∈ G(f(q)) ⟺ β(g) ∈ G(β(f(q))).

Lemma 5. For arbitrary subset W ⊆ Q, the cardinality of P^{Q} is congruent modulo m to the cardinality of

{f ∈ P^{Q} : f(W) ⊆ E_{n,m}^{c}}.

Proof. For each automorphism α ∈ Aut(P) and for each p ∈ P, we have [p] = [α(p)]. Hence,

p ∈ E_{n,m}^{c} ⟺ α(p) ∈ E_{n,m}^{c}

and for every function f ∈ P^{Q}, we have

f(W) ⊆ E_{n,m}^{c} ⟺ α ∘ f(W) ⊂ E_{n,m}^{c}

Orbits O(f) form a partition of P^{Q}. If f ∼ g (or in other words if f ∈ O(g)), then there exists automorphism α ∈ Aut(P), such that g = α ∘ f and

f(W) ⊆ E_{n,m}^{c} ⟺ g(W) ⊆ E_{n,m}^{c}.

So we have two kinds of orbits:

• orbits O(f), where g(W) ⊆ E_{n,m}^{c} for all g ∈ O(f),

• orbits O(f), where g(W) ⊈ E_{n,m}^{c} for all g ∈ O(f).

Moreover, if f(W) ⊈ E_{n,m}^{c}, then there exists w ∈ W such that f(w) ∈ E_{n,m}, hence, m divides |[f(w)]| and by Lemma 4, m divides |O(f)|.

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

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 the function G that, for every pair (x, y) ∈ D_{n}^{2}, takes the value

G(x, y) = re(x|y, ⊤) · re(⊥, x&y).

Observe that G(x, y) is equal to the number of functions f ∈ D_{n}^{B^{2}} with f(01) = x and f(10) = y. Function G is well-known, as it is discussed in [3, 4, 11].

For A ⊆ D_{n} × D_{n} let G(A) denote ∑_{(x,y)∈A} G(x, y). By Lemma 1, we have

d_{n+2} = G(D_{n} × D_{n}) = ∑_{x∈D_{n}} ∑_{y∈D_{n}} G(x, y).

Consider the set W_{2} = {01, 10}. By Lemma 5, we have

d_{n+2} ≡ G(D_{n} × D_{n}) ≡ G(E_{n,m}^{c} × E_{n,m}^{c}) (mod m).

Observe that, for every automorphism π ∈ Aut(B^{n}) and every x, y ∈ D_{n}, we have G(x, y) = G(π(x), π(y)).

Lemma 6. Let Y be a subset Y ⊆ D_{n} and suppose that π(Y) = Y for every automorphism π ∈ Aut(B^{n}; and let x and y be two equivalent, x ∼ y, elements in D_{n}. Then

1. G({x} × Y) = G({y} × Y).

2. G([x] × Y) = γ(x) · G({x} × Y).

Proof. Notice that condition π(Y) = Y implies that π is a bijection on Y, or in other words, π permutes the elements of Y.

For (1), observe that

G({x} × Y) = ∑_{s∈Y} G(x, s) = ∑_{s∈Y} G(π(x), π(s))

= ∑_{t∈π(Y)} G(π(x), t) = ∑_{t∈Y} G(π(x), t) = G({π(x)} × Y).

We use the fact that π(Y) = Y.

Observe that for every automorphism π ∈ Aut(b^{n}), we have and π(E_{n,m}^{c}) = E_{n,m}^{c}. Hence, by Lemma 6, we get

Theorem 7.

d_{n+2} ≡ ∑_{x∈R_{n}∩E_{n,m}^{c}} ∑_{y∈E_{n,m}^{c}} γ(x) · G(x, y) (mod m).

Here we identify each class [x] ∈ R_{n} with its canonical representative.

Example 8. Consider the poset D_{2} = {0000, 0001, 0011, 0101, 0111, 1111}. There are five equivalence classes: namely, R_{2} = {{0000}, {0001}, {0011, 0101}, {0111}, {1111}}. Two elements: 0101 and 0011 are equivalent. For m = 2, we have E_{2,2} = {0011, 0101} and E_{2,2}^{c} = {0000, 0001, 0111, 1111}. Table 4 presents values of G(x, y) for x, y ∈ D_{2}. Let Y = [0011] = {0011, 0101}. For every permutation π ∈ S_{2}, we have π(Y) = Y. Furthermore, G({0011} × Y) = G({0101} × Y) = 9 + 4 = 13; and G([0011] × Y) = 2 · 13 = 26, which is divisible by 2.

Similarly, for Z = [0001] = {0001}, we have that π(Z) = Z for every permutation π ∈ S_{2}. Furthermore, G({0011} × Z) = G({0101} × Z) = 6; and G([0011] × Z) = 2 · 6 = 12, which is divisible by 2. By summing up all values in Table 4 we obtain G(D_{2} × D_{2}) = 168 = d_{4}.

\begin{matrix}x y & 0000 & 0001 & 0011 & 0101 & 0111 & 1111 \\ 0000 & 6 & 5 & 3 & 3 & 2 & 1 \\ 0001 & 5 & 10 & 6 & 6 & 4 & 2 \\ 0011 & 3 & 6 & 9 & 4 & 6 & 3 \\ 0101 & 3 & 6 & 4 & 9 & 6 & 3 \\ 0111 & 2 & 4 & 6 & 6 & 10 & 5 \\ 1111 & 1 & 2 & 3 & 3 & 5 & 6 \end{matrix}

Table 4: Values of G(x, y) for x, y ∈ D_{2}.

Example 9 (Continuation of Example 8). By summing the relevant values listed in Table 4, we obtain G(E_{2,2}^{c} ×E_{2,2}^{c}) = 6+5+2+1+5+10+4+2+2+4+10+5+1+2+5+6 = 70. By Theorem 7, we have d_{4} ≡ 70 (mod 2). Indeed, d_{4} = 168, which is even.

7 Counting functions from B^{3} to D_{n}

In the next two sections, we show that similar techniques can be also applied to functions in D_{n}^{B^{3}} and D_{n}^{B^{4}}. Consider the function H which for every triple (x, y, z) ∈ D_{n}^{3} returns the value

H(x, y, z) = re(⊥, x&y&z) · ∑_{s≥x|y|z} re(x|y, s) · re(x|z, s) · re(y|z, s).

Observe that H(x, y, z) is equal to the number of monotone functions f ∈ D_{n}^{B^{3}} with f(001) = x, f(010) = y and f(100) = z. Thus, we have

d_{n+3} = H(D_{n}^{3}) = ∑_{x∈D_{n}} ∑_{y∈D_{n}} ∑_{z∈D_{n}} H(x, y, z).

Function H is discussed in [3]. Consider the set W_{3} = {001, 010, 100}. By Lemma 5, we have

d_{n+3} ≡ G(D_{n} × D_{n} × D_{n}) ≡ G(E_{n,m}^{c} × E_{n,m}^{c} × E_{n,m}^{c}) (mod m).

Observe that for every automorphism π ∈ Aut(B^{n}) and every x, y, z ∈ D_{n}, we have H(x, y, z) = H(π(x), π(y), π(z)).

Lemma 10. Let Y and Z be subsets Y, Z ⊆ D_{n} and suppose that π(Y) = Y and π(Z) = Z for every automorphism π ∈ Aut(B^{n}); and let x and y be two equivalent, x ∼ y, elements in D_{n}. Then

1. H({x} × Y × Z) = H({y} × Y × Z).

2. H([x] × Y × Z) = γ(x) · H({x} × Y × Z).

Proof. (1) H({x} × Y × Z) = ∑_{s∈Y} ∑_{t∈Z} H(x, s, t) = ∑_{s∈Y} ∑_{t∈Z} H(π(x), π(s), π(t)) = ∑_{u∈π(Y)} ∑_{v∈π(Z)} H(π(x), u, v) = ∑_{u∈Y} ∑_{v∈Z} H(π(x), u, v) = H({π(x)} × Y × Z). We use the fact that π is a bijection on Y × Z and permutes the elements of Y × Z.

As an immediate corollary, we have the following:

Theorem 11.

d_{n+3} ≡ ∑_{x∈R_{n}∩E_{n,m}^{c}} ∑_{y∈E_{n,m}^{c}} ∑_{z∈E_{n,m}^{c}} γ(x) · H(x, y, z) (mod m).

Here, again, we identify each class [x] ∈ R_{n} with its canonical representative.

Example 12. Consider D_{4}. There are 168 elements in D_{4} and 30 equivalence classes in R_{4}. The distribution of these equivalence classes based on their γ value is presented in Table 5. For instance, there are six equivalence classes [x] with γ(x) = 1, two equivalence classes with γ(x) = 3, and so forth. For m = 2, the set E_{4,2}^{c} contains only twelve elements and R_{4} ∩ E_{4,2}^{c} contains eight elements. Similarly, for m = 3, the set E_{4,3}^{c} contains 42 elements and R_{4} ∩E_{4,3}^{c} consists of 15 elements.

Example 13. We employed a Java implementation of the Theorem 11. For n = 4 and m = 2, 3, 4, 6, 12 we have

d_{7} ≡ 2320978352 (mod 2), and therefore d_{7} mod 2 = 0, d_{7} ≡ 74128573428 (mod 3), and therefore d_{7} mod 3 = 0, d_{7} ≡ 128268820802 (mod 4), and therefore d_{7} mod 4 = 2, d_{7} ≡ 89637133284 (mod 6), and therefore d_{7} mod 6 = 0, d_{7} ≡ 566167187562 (mod 12), and therefore d_{7} mod 12 = 6.

One can check these values directly by dividing d_{7} by 2, 3, 4, 6, and 12.

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

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} to D_{n}. Consider the function F (also discussed in [3, 4]), which for every six elements a, b, c, d, e, f ∈ D_{n}, counts how many functions g ∈ D_{n}^{B^{4}} satisfy the following equations: g(0011) = a, g(0101) = b, g(1001) = c, g(0110) = d, g(1010) = e, g(1100) = f.

\begin{matrix}k & |\{f ∈ R_{4} : γ(f) = k\}| \\ 1 & 6 \\ 3 & 2 \\ 4 & 9 \\ 6 & 6 \\ 12 & 7 \end{matrix}

Table 5: Number of f ∈ R_{4} with γ(f) = k.

For A ⊆ (D_{n})^{6} let F (A) denote ∑_{(a,b,c,d,e,f)∈A} F (a, b, c, d, e, f). By Lemma 1, we have

d_{n+4} = F (D_{n}^{6}) = ∑_{a∈D_{n}} ∑_{b∈D_{n}} ∑_{c∈D_{n}} ∑_{d∈D_{n}} ∑_{e∈D_{n}} ∑_{f∈D_{n}} F (a, b, c, d, e, f).

Consider the set W_{4} = {0011, 0101, 1001, 0110, 1010, 1100}. By Lemma 5, we have

d_{n+4} ≡ F (D_{n}^{6}) ≡ F ((E_{n,m}^{c})^{6}) (mod m)

Observe that for every automorphism π ∈ Aut(B^{n}) and every a, b, c, d, e, f ∈ D_{n}, we have F (a, b, c, d, e, f) = F (π(a), π(b), π(c), π(d), π(e), π(f)). Consider Cartesian product Y = Y_{1} × Y_{2} × Y_{3} × Y_{4} × Y_{5} and let π(y_{1}, …, y_{5}) = (π(y_{1}), …, π(y_{5})). Observe that, if π(Y_{i}) = Y_{i} for every i, then π(Y) = Y and π permutes the elements of Y.

Lemma 14. Let Y be a subset Y ⊆ D_{n}^{5} and suppose that π(Y) = Y for every automorphism π ∈ Aut(B^{n}); and let x and y be two equivalent, x ∼ y, elements in D_{n}. Then

1. F ({x} × Y) = F ({y} × Y).

2. F ([x] × Y) = γ(x) · F ({x} × Y).

Proof. (1) F ({x} × Y) = ∑_{s∈Y} F (x, s) = ∑_{s∈Y} F (π(x), π(s)) = ∑_{u∈π(Y)} F (π(x), u) = ∑_{u∈Y} F (π(x), u) = F ({π(x)} × Y). We use the fact that π is a bijection on Y and permutes the elements of Y.

As a corollary we get the following result.

Theorem 15.

d_{n+4} ≡ ∑_{a∈R_{n}∩E_{n,m}^{c}} ∑_{b∈E_{n,m}^{c}} ∑_{c∈E_{n,m}^{c}} ∑_{d∈E_{n,m}^{c}} ∑_{e∈E_{n,m}^{c}} ∑_{f∈E_{n,m}^{c}} γ(a) · F (a, b, c, d, e, f) (mod m).

Example 16. We utilized a Java implementation of the Theorem 15. For n = 4 and m = 2, 3, 4, 6, 12 we get

d_{8} ≡ 53336702474849828, and therefore d_{8} mod 2 = 0;

d_{8} ≡ 3019662424037271148 (mod 3), and therefore d_{8} mod 3 = 1;

d_{8} ≡ 25754060568741983624 (mod 4), and therefore d_{8} mod 4 = 0;

d_{8} ≡ 14729824485525634108 (mod 6), and therefore d_{8} mod 6 = 4;

d_{8} ≡ 15054599294580333880 (mod 12), and therefore d_{8} mod 12 = 4. One can check these values directly by dividing d_{8} by 2, 3, 4, 6, and 12.

9 Application

To compute remainders of d_{9} divided by 5 and 7, we chose the algorithm described in Section 6. Our implementation lists all 490,013,148 elements of R_{7} and calculates γ(x) and re(⊥, x) for each element x ∈ R_{7}. This feat was previously accomplished only by Van Hirtum in 2021 [6]. It is worth noting that the number of elements x in R_{n} with γ(x) = n! for n > 1 can be found in the OEIS sequence \underline{A220879} (see Table 6). Using the available precalculated sets, we can efficiently determine the 7th term of the sequence, which was not recorded in the OEIS before.

\begin{matrix}n & \underline{A220879}(n) \\ 1 & 0 \\ 2 & 1 \\ 3 & 0 \\ 4 & 0 \\ 5 & 7 \\ 6 & 7281 \\ 7 & 468822749 \end{matrix}

Table 6: Inequivalent monotone Boolean functions of n variables with no symmetries.

Our program’s most critical part, the Boolean function canonization procedure, is based on Van Hirtum’s fast approach [6, Section 5.2.9] and implemented in Rust. Our program is running on a 32-thread machine with Xeon cores.

After the preprocessed data has been loaded into the main memory, the test was performed and the value of d_{8} was recomputed in just 16 seconds. However, using this method to check the divisibility of d_{9} for any value of m is significantly more challenging.

In order to determine which remainders can be computed by our methods, we can use the information in Table 7. Note that

|E_{7,m}^{c}| = ∑_{\begin{matrix}x∈R_{7} \\ γ(x) mod m≠0 \end{matrix}} γ(x).

The four smallest E_{7,m}^{c} are E_{7,7}^{c} with 9999 elements, E_{7,3}^{c} with 108873 elements, E_{7,21}^{c} with 118863 elements, and E_{7,5}^{c} with 154863 elements. Since d_{9} is already known to be divisible by 3, the next step is to compute the remainders of d_{9} divided by 5 and 7.

9.1 Remainder of d_{9} divided by 5

∑_{x∈R_{7}∩E_{7,5}^{c}} ∑_{y∈E_{7,5}^{c}} γ(x) · G(x, y) = 1404812111893131438640857806,

\begin{matrix}k & |\{f ∈ R_{7} : γ(f) = k\}| \\ 1 & 9 \\ 7 & 27 \\ 21 & 75 \\ 30 & 5 \\ 35 & 117 \\ 42 & 99 \\ 70 & 90 \\ 84 & 9 \\ 105 & 1206 \\ 120 & 4 \\ 140 & 702 \\ 210 & 3255 \\ 252 & 114 \\ 315 & 2742 \\ 360 & 18 \\ 420 & 26739 \\ 504 & 237 \\ 630 & 47242 \\ 720 & 4 \\ 840 & 75024 \\ 1260 & 1024050 \\ 1680 & 3128 \\ 2520 & 20005503 \\ 5040 & 468822749 \end{matrix}

Table 7: Number of f ∈ R_{7} with the given γ(f).

therefore, by Theorem 7, we have d_{9} mod 5 = 1. We calculated this number in approximately 7 hours. Moreover, using Theorem 15 we have d_{9} ≡ 157853570524864492086 (mod 5), which confirms that d_{9} mod 5 = 1.

9.2 Remainder of d_{9} divided by 7

∑_{x∈R_{7}∩E_{7,7}^{c}} ∑_{y∈E_{7,7}^{c}} γ(x) · G(x, y) = 29989517764506682537562623,

therefore, by Theorem 7, we have d_{9} mod 7 = 6. We calculated this number in approximately half an hour.

10 Acknowledgments

We would like to thank the anonymous referee for his useful suggestions and references.

References

[1] M. Aigner. Combinatorial Theory. Springer, 1979.

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

[3] F. a Campo. Relations between powers of Dedekind numbers and exponential sums related to them. J. Integer Sequences 21 (2018), Article 18.4.4.

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

[5] C. Jäkel. A computation of the ninth Dedekind number, arxiv preprint arXiv:2304.00895 [math.CO], 2023.

Available at https://arxiv.org/abs/2304.00895.

[6] L. Van Hirtum. A path to compute the 9th Dedekind number using FPGA supercomputing (2021). Master’s thesis, available at https://hirtum.com/thesis.pdf.

[7] L. Van Hirtum, P. De Causmaecker, J. Goemaere, T. Kenter, H. Riebler, M. Lass, and C. Plessl. A computation of D(9) using FPGA supercomputing, preprint, 2023.

Available at https://arxiv.org/abs/2304.03039.

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

[9] N. J. A. Sloane. The On-line Encyclopedia of Integer Sequences. Available at https://

oeis.org.

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

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

[12] D. Wiedemann. Letter to N. J. A. Sloane (1990). Available at https://oeis.org/

A000372/a000372.pdf.

[13] K. Yamamoto. Note on the order of free distributive lattices. Sci. Rep. Kanazawa Univ. 2 (1953), 5–6.

2020 Mathematics Subject Classification: Primary 06E30.

Keywords: Dedekind number, monotone Boolean function, ninth Dedekind number, congruence modulo, Chinese remainder theorem.

(Concerned with sequences \underline{A000372}, \underline{A001206}, \underline{A003182} and \underline{A220879}.)

Received March 15 2023; revised versions received March 16 2023; May 17 2023; June 13 2023; June 14 2023. Published in Journal of Integer Sequences, August 16 2023.

Return to Journal of Integer Sequences home page.