<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage{diagbox}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}

\DeclareMathOperator{\re}{re}
\DeclareMathOperator{\aut}{Aut}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
Divisibility Properties of Dedekind Numbers
}
\vskip 1cm
\large
Bart\l{}omiej Pawelski and Andrzej Szepietowski\\
Institute of Informatics\\
University of Gda\'nsk\\
Poland\\
\href{mailto:bartlomiej.pawelski@ug.edu.pl}{\tt bartlomiej.pawelski@ug.edu.pl} \\
\href{mailto:andrzej.szepietowski@ug.edu.pl}{\tt andrzej.szepietowski@ug.edu.pl} 
\end{center}

\vskip .2in

\begin{abstract}
We study some divisibility properties of Dedekind numbers. We show that the ninth Dedekind number is congruent to 6 modulo 210.
\end{abstract}

\section{Introduction}\label{sec:intro}
  
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 \textit{(On-Line Encyclopedia of Integer Sequences)} sequence
\seqnum{A000372} (see Table \ref{tab:RD}).

\begin{table}[ht]
\centering
\begin{tabular}[h]{|l|l|l|}
\hline
 $n$ &amp; $d_n$ &amp; $r_n$\\
\hline
0 &amp; 2 &amp; 2 \\
1 &amp; 3 &amp; 3 \\
2 &amp; 6 &amp; 5 \\
3 &amp; 20 &amp; 10 \\
4 &amp; 168 &amp; 30 \\
5 &amp; 7,581 &amp; 210 \\
6 &amp; 7,828,354 &amp; 16,353 \\
7 &amp; 2,414,682,040,998 &amp; 490,013,148 \\
8 &amp; 56,130,437,228,687,557,907,788 &amp; 1,392,195,548,889,993,358 \\

\hline
\end{tabular}
\caption{Known values of $d_n$ (\seqnum{A000372}) and $r_n$ (\seqnum{A003182}).}
\label{tab:RD}
\end{table}

In 1990, Wiedemann calculated $d_8$ \cite{Wied1991}. His result was confirmed in 2001 by Fidytek, Mostowski, Somla, and Szepietowski \cite{Fid2001}. The impulse for writing our paper came from the letter from Wiedemann to Sloane \cite{Wiedlet}
 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 \cite{yamamoto}, 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:
\begin{align*}
 d_9 &amp;\equiv 0\;(\bmod\;2), \\
d_9 &amp;\equiv 0\;(\bmod\;3), \\
d_9 &amp;\equiv 1\;(\bmod\;5), \\
d_9 &amp;\equiv 6\;(\bmod\;7). 
\end{align*}
By the Chinese remainder theorem, we have
\[ d_9 \equiv 6\;(\bmod\;210). \]

Recently, after the preprint of this paper was published on ArXiv, two independent research teams \cite{jakel, hirtum2} reported the same value:
$$ d_9 = 286386577668298411128469151667598498812366,$$
which confirms our results.

\section{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\le 0$, $\;0\le1$, $\;1\le1$)
and the following partial order in $B^n$.
For any two elements,
$x=(x_1,\dots,x_n)$, $\;y=(y_1,\dots,y_n)$ in $B^n$,
$$x\le y\quad\hbox{if and only if}\quad x_i\le y_i
\quad \hbox{for all $1\le i\le n$}.$$
A function $h:B^n\to B$ is monotone if
$$x\le y \Longrightarrow h(x)\le 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\le h\quad\hbox{if and only if}\quad g(x)\le h(x)\quad
\hbox{for all } x\in 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\in D_1$ can be represented as 
the concatenation $g(0)*g(1)$, where $g(0), g(1)\in D_0$ and $g(0)\le g(1)$. 
Hence $D_1=\{00, 01, 11\}$. 
Each element of $g\in 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\in D_1$ and $g_0\le g_1$.
Hence $D_2=\{0000, 0001, 0011, 0101, 0111, 1111\}$.
Similarly, any element of $g\in D_n$ can be represented as
a concatenation $g_0*g_1$, where $g_0, g_1\in D_{n-1}$ and $g_0\le g_1$. 
Therefore, we can treat functions in $D_n$ as sequences of bits and as integers. We let $\preceq$ denote the total order in $D_n$ induced by the total order in integers.

For a set $Y\subseteq D_n$, by $Y^2$ we denote the Cartesian power $Y^2=Y\times Y$, that is the set of all ordered pairs $(x,y)$ with $x,y\in Y$. Similarly for more 
than two factors, we write $Y^k$ for the set of ordered $k$-tuples of elements of $Y$.
We let $\top$ denote the maximal element in $D_n$, that is, $\top=(1\ldots 1)$; and $\bot$ denote the minimal element in $D_n$, that is, $\bot=(0\ldots 0)$. For two elements $x,y\in D_n$, we let $x|y$ denote the bitwise or; and $x\&amp;y$ denote the bitwise and. Furthermore,
we let $\re(x,y)$ denote $|\{z\in D_n : x\le z\le y\}|$. Note that $\re(x,\top)=|\{z\in D_n : x\le z\}|$ and $\re(\bot,y)=|\{z\in D_n : z\le y\}|$. 

\subsection{Posets}
A {\it poset (partially ordered set)} $(S,\le)$ consists of a set $S$ together with a binary relation (partial order) $\le$ which is reflexive, transitive, and antisymmetric.
 Given two posets $(S,\le)$ and $(T,\le)$ a function $f:S \to T$ is {\it monotone}, if  $x \le y$ implies $f(x)\le f(y)$.
By $T^S$ we denote the poset of all monotone functions from $S$ to $T$ with the partial order defined by
$$f\le g\quad\hbox{ if and only if}\quad f(x)\le g(x)\hbox{ for all }x\in S.$$
In this paper we use the following well-known lemma; see \cite{campo, szepietowski}:
\begin{lemma}\label{L1} 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$.
\end{lemma}


\section{Divisibility of Dedekind numbers by 2}

 In 1952, Yamamoto \cite{yamamoto} 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\in D_n$, we have {\it dual} $x^d$ which is obtained by reversing and negating all bits. For example, $1111^d=0000$ and $0001^d=0111$. An element $x\in D_n$ is {\it 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\ne x$, then $y^d=x$. Thus, non-self-duals form pairs of the form $(x,x^d)$, where $x\ne x^d$. Let $k_n$ denote the number of these pairs and let $\lambda_n$ denote the number of self-dual functions in $D_n$.
We have that $d_n=2k_n + \lambda_n$. Hence $\lambda_n \equiv d_n\pmod2$. Values of $\lambda_n$ are described by the OEIS sequence \seqnum{A001206}; see Table~\ref{tab:SD}. The last known term of this sequence, $\lambda_9$, was calculated in 2013 by Brouwer et al.~\cite{brouwer}.

\begin{table}[ht]
\centering
\begin{tabular}[h]{|l|l|}
\hline
 $n$ &amp; $\lambda_n$\\
\hline
0 &amp; 0 \\
1 &amp; 1 \\
2 &amp; 2 \\
3 &amp; 4 \\
4 &amp; 12 \\
5 &amp; 81 \\
6 &amp; 2,646 \\
7 &amp; 1,422,564 \\
8 &amp; 229,809,982,112 \\
9 &amp; 423,295,099,074,735,261,880 \\

\hline
\end{tabular}
\caption{Known values of $\lambda_n$ (\seqnum{A001206}).}
\label{tab:SD}
\end{table}

\begin{corollary}\label{corollary1}
We have $d_9 \equiv \lambda_9 \equiv 0 \pmod2$.
\end{corollary}

One can directly check that $d_n \equiv \lambda_n\pmod 2$ for $n \le 8$.

\section{Divisibility of Dedekind numbers by 3}\label{sec:Sec4}
By Lemma~\ref{L1}, 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
$$\alpha(f)=f\circ \alpha^{-1}$$
for all $\alpha\in \aut(B^3)$ and all $f\in D_n^{B^3}$.
Let ${\cal O}(f)=\{\alpha(f)\in D_n^{B^3}:\alpha\in \aut(B^3) \}$ denote the orbit of $f$ under this action and by 
$\gamma(f)=|{\cal 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 ${\cal 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}\equiv |D_n^{P_4}|\pmod3.$$

It is well known, see \cite{aigner, szepietowski}, that the number of monotone functions from the path $P_4=(a&lt;b&lt;c&lt;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&lt;01&lt;11\}$, we have
$$
M(D_1)=\left(
\begin{array}{ccc}
1 &amp; 1&amp; 1\\
0 &amp; 1&amp; 1\\
0 &amp; 0&amp;1
\end{array}
\right)
$$
and
$$
M(D_1)^3=\left(
\begin{array}{ccc}
1 &amp; 3&amp; 6\\
0 &amp; 1&amp; 3\\
0 &amp; 0&amp;1
\end{array}
\right).
$$
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)=\left(
\begin{array}{cc|cc|cc}
1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1 \\
0&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1 \\
\hline
0&amp; 0&amp; 1&amp; 0&amp; 1&amp; 1 \\
0&amp; 0&amp; 0&amp; 1&amp; 1&amp; 1 \\
\hline
0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 1 \\
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1
\end{array}
\right).
$$
Now consider the third power of the incidence matrix of $D_2$:

$$
M(D_2)^3=\left(
\begin{array}{cc|cc|cc}
1&amp; 3&amp; 6&amp; 6&amp; 14&amp; 20 \\
0&amp; 1&amp; 3&amp; 3&amp; 9&amp; 14 \\
\hline
0&amp; 0&amp; 1&amp; 0&amp; 3&amp; 6 \\
0&amp; 0&amp; 0&amp; 1&amp; 3&amp; 6 \\
\hline
0&amp; 0&amp; 0&amp; 0&amp; 1&amp; 3 \\
0&amp; 0&amp; 0&amp; 0&amp; 0&amp; 1
\end{array}
\right).
$$
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~\cite{pawelski} proposed another method: $|D_{(n+m)}^{P_4}| = |D_n^{ P_4\times B^m}| = |(D_n^{ P_4})^{B^m}|$ (also see \cite{szepietowski}).
Using the same program as used in \cite{pawelski} to compute $|D_5^{P_4}|$ we can calculate $|D_6^{P_4}|$ and the result (see Table \ref{tab:FP3}) is divisible by 3.

\begin{corollary}\label{corollary3-1}
As $|D_6^{P_4}| = 868329572680304346696$ is divisible by 3, the
quantity $d_9$ is also divisible by 3.
\end{corollary}

\begin{table}[ht]
\centering
\begin{tabular}[h]{|l|l|c|}
\hline
 $n$ &amp; $|D_n^{P_4}|$ &amp; $|D_n^{P_4}| \bmod 3$\\
\hline
0 &amp; 5 &amp; 2 \\
1 &amp; 15 &amp; 0 \\
2 &amp; 105 &amp; 0\\
3 &amp; 3,490 &amp; 1\\
4 &amp; 2,068,224 &amp; 0 \\
5 &amp; 262,808,891,710 &amp; 1\\
6 &amp; 868,329,572,680,304,346,696 &amp; 0\\

\hline
\end{tabular}
\caption{Known values of $|D_n^{P_4}|$. Note that $d_{n+3}\equiv |D_n^{P_4}| \pmod3$.}
\label{tab:FP3}
\end{table}

One can directly check that $d_{n+3} \equiv |D_n^{P_4}|\pmod 3$ for $n \le 5$.

\section{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 ${\cal U}_n$ of $B^n$.   An isomorphism is given by $h:D_n\to{\cal  U}_n$, where $h(x)=x^{-1}(1)$ for all $x\in D_n$.
For $\beta\in \aut(B^n)$ and $x\in D_n$, we have 
$$h(\beta(x))=\beta(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
$$\beta(f)=\beta\circ f$$
for all $\beta\in \aut(P)$ and $f\in P^Q$.
We let 
$${\cal O}(f)=\{\beta(f):\beta \in \aut(P)\}$$ 
denote the orbit of $f$ under this action.
Additionally, for $p\in P$, we write
$$[p]=\{\beta(p):\beta \in \aut(P)\}$$ 
for the orbit of $p$ under the natural action of $\aut(P)$ on $P$.

We use $\sim$ to denote an equivalence relation on $D_n$. Namely,
two functions $p,r\in D_n$ are {\it equivalent}, $p\sim r$, if there is an automorphism
$\alpha \in \aut( D_n)$ such that $p=\alpha(r)$.
For a function $p\in D_n$ its {\it equivalence class}
is the set $[p]=\{r\in D_n : r \sim p\}$. We let $\gamma(f)$ denote $|[f]|$.
For $m&gt;1$, let $E_{n,m}= \{p\in D_n:\gamma(f)\equiv 0\pmod m\}$
and $E_{n,m}^c=D_n-E_{n,m}$.
For the class $[p]$, we define its {\it 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 $\preceq$) element \cite{Wied1991}. 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 \seqnum{A003182} OEIS sequence; see Table~\ref{tab:RD}.


\begin{lemma} \label{ML1}
For every $q\in Q$ and every $f\in P^Q$, the integer
$|[f(q)]|$ divides $|{\cal O}(f)|$.
\end{lemma}
\begin{proof}
    
For every $p\in [f(q)]$ we define
$${\cal G}(p):=\{g\in{\cal O}(f):g(q)=p\}.$$
The sets ${\cal G}(p)$, $p\in[f(q)]$ form a partition of ${\cal O}(f)$ and the sets ${\cal G}(p)$ have the same cardinality.
Indeed, for every $\beta\in \aut(P)$, 
$$g\in{\cal G} (f(q))\quad \iff\quad \beta(g)\in{\cal G} (\beta(f(q))).$$

\end{proof}

\begin{lemma}\label{ML2}
For arbitrary subset $W\subseteq Q$, the cardinality of $P^Q$ is congruent modulo $m$ to the cardinality of
$$\{f\in P^Q: f(W)\subseteq E_{n,m}^c\}.$$
\end{lemma}


\begin{proof}

For each automorphism $\alpha\in \aut(P)$ and for each $p\in P$, we have
$[p]=[\alpha(p)]$. Hence,
$$p\in  E_{n,m}^c \quad \iff \quad \alpha(p)\in  E_{n,m}^c$$
and for every function $f\in P^Q$, we have 
$$ f(W)\subseteq E_{n,m}^c\quad \iff \alpha \circ f(W)\subset E_{n,m}^c$$
Orbits ${\cal O}(f)$ form a partition of $P^Q$. If $f\sim g$ (or in other words if $f\in {\cal O}(g)$), then 
there exists automorphism $\alpha\in \aut(P)$, such that $g=\alpha\circ f$ and
$$f(W)\subseteq E_{n,m}^c\quad \iff \quad g(W)\subseteq E_{n,m}^c.$$
So we have two kinds of orbits:
\begin{itemize}
\item orbits ${\cal O}(f)$, where $g(W)\subseteq E_{n,m}^c$ for all $g\in {\cal O}(f)$,
\item orbits ${\cal O}(f)$, where $g(W)\not\subseteq E_{n,m}^c$ for all $g\in {\cal O}(f)$.
\end{itemize}
 Moreover, if   $f(W)\not\subseteq E_{n,m}^c$, then there exists $w\in W$ such that $f(w)\in E_{n,m}$, hence,  $m$ divides $|[f(w)]|$ and by Lemma~\ref{ML1},
$m$ divides $|{\cal O}(f)|$.

\end{proof}

\section{Counting functions from \texorpdfstring{$B^2$}{B2} to \texorpdfstring{$D_n$}{D(n)}}\label{sec:b2sec}
By Lemma~\ref{L1}, 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)\in D_n^2$, takes the value
$$G(x,y)=\re(x|y,\top)\cdot \re(\bot,x\&amp;y).$$ 

Observe that $G(x,y)$ is equal to the number of functions $f\in D_n^{B^2}$ with
$f(01)=x$ and $f(10)=y$. Function $G$ is well-known, as it is discussed in \cite{campo, Fid2001, Wied1991}.

For $A\subseteq D_n\times D_n$ let $G(A)$ denote $\sum_{(x,y)\in A}G(x,y)$.
By Lemma~\ref{L1}, we have 
 $$d_{n+2}=G(D_n\times D_n)=\sum_{x\in D_n}\sum_{y\in D_n}G(x,y).$$
 Consider the set $W_2=\{01,10\}$. By Lemma~\ref{ML2}, we have
 $$d_{n+2}\equiv G(D_n\times D_n)\equiv 
G(E_{n,m}^c\times E_{n,m}^c)\pmod m.$$

 Observe that, for every automorphism $\pi\in \aut(B^n)$ and every $x, y\in D_n$, we have
$G(x,y)=G(\pi(x),\pi(y))$.
\begin{lemma}\label{L2}
Let $Y$ be a subset $Y\subseteq D_n$ and suppose that $\pi(Y)=Y$ for every automorphism $\pi\in \aut(B^n$;
and let $x$ and $y$ be two equivalent, $x\sim y$, elements in $D_n$. Then
\begin{enumerate}
\item $G(\{x\}\times Y)=G(\{y\}\times Y)$.
\item $G([x]\times Y)=\gamma(x)\cdot G(\{x\}\times Y)$.
\end{enumerate}
\end{lemma}

\begin{proof}
Notice that condition $\pi(Y)=Y$ implies that $\pi$ is a bijection on $Y$, or in other words, $\pi$ permutes the elements of $Y$.

For (1), observe that
\begin{align*}
G(\{x\}\times Y) &amp;=\sum_{s\in Y}G(x,s)=\sum_{s\in Y}G(\pi(x),\pi(s))  \\
&amp; = \sum_{t\in \pi(Y)}G(\pi(x),t) = \sum_{t\in Y}G(\pi(x),t)=G(\{\pi(x)\}\times Y).
\end{align*}
We use the fact that $\pi(Y)=Y$.
\end{proof}

Observe that for every automorphism $\pi\in \aut(b^n)$, we have 
and $\pi(E_{n,m}^c)=E_{n,m}^c$. Hence,  by Lemma~\ref{L2}, we get
\begin{theorem}\label{T3}
$$ d_{n+2}\equiv 
\sum_{x\in R_n\cap E_{n,m}^c}\sum_{y\in E_{n,m}^c} \gamma(x)\cdot G(x,y)\pmod m.$$
Here we identify each class $[x]\in R_n$ with 
its canonical representative.
\end{theorem}

\begin{example}\label{exd2}
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^c_{2,2}=\{0000,0001,0111,1111\}.$
Table \ref{tab:xy1} presents values of $G(x,y)$ for $x,y\in D_2$.
Let $Y=[0011]=\{0011,0101\}$.  For every permutation $\pi\in S_2$, we have $\pi(Y)=Y$.
Furthermore, $G(\{0011\}\times Y)=G(\{0101\}\times Y)=9+4=13$; and $G([0011]\times Y) = 2 \cdot 13 = 26$, which is divisible by 2.

Similarly, for $Z=[0001]=\{0001\}$, we have that $\pi(Z)=Z$ for every permutation $\pi\in S_2$.
Furthermore, $G(\{0011\}\times Z)=G(\{0101\}\times Z)=6$; and $G([0011]\times Z) = 2 \cdot 6 = 12$, which is divisible by 2. By summing up all values in Table~\ref{tab:xy1} we obtain $G(D_2\times D_2)=168=d_4$.
\end{example}


\begin{table}[ht]
\centering
\begin{tabular}[h]{|c|c|c|c c|c|c|}
\hline
 \diagbox{$x$}{$y$} &amp; 0000 &amp; 0001 &amp; 0011 &amp; 0101 &amp; 0111 &amp; 1111 \\
\hline
0000 &amp; 6 &amp; 5 &amp; 3 &amp; 3 &amp; 2 &amp; 1 \\
\hline
0001 &amp; 5 &amp; 10 &amp; 6 &amp; 6 &amp; 4 &amp; 2 \\
\hline
0011 &amp; 3 &amp; 6 &amp; 9 &amp; 4 &amp; 6 &amp; 3\\
0101 &amp; 3 &amp; 6 &amp; 4 &amp; 9 &amp; 6 &amp; 3\\
\hline
0111 &amp; 2 &amp; 4 &amp; 6 &amp; 6 &amp; 10 &amp; 5 \\
\hline
1111 &amp; 1 &amp; 2 &amp; 3 &amp; 3 &amp; 5 &amp; 6\\

\hline
\end{tabular}
\caption{Values of $G(x,y)$ for $x,y\in D_2$.}
\label{tab:xy1}
\end{table}

\begin{example}[Continuation of Example \ref{exd2}]
  By summing the relevant values listed in Table \ref{tab:xy1}, we obtain 
  $G(E_{2,2}^c\times E_{2,2}^c)=6+5+2+1+5+10+4+2+2+4+10+5+1+2+5+6=70$. By Theorem \ref{T3}, we have $d_4 \equiv 70 \pmod 2$. Indeed, $d_4 = 168$, which is even.
\end{example}

\section{Counting functions from \texorpdfstring{$B^3$}{B3} to \texorpdfstring{$D_n$}{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}$.
\begin{def}\label{def1}
Consider the function $H$ which for every triple $(x,y,z)\in D_n^3$ returns the value
$$H(x,y,z)=\re(\bot,x\&amp;y\&amp;z)\cdot\sum_{s\ge x|y|z} \re(x|y,s)\cdot \re(x|z,s)\cdot \re(y|z,s).$$
\end{def}
Observe that $H(x,y,z)$ is equal to the number of monotone functions $f\in 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)=\sum_{x\in D_n}\sum_{y\in D_n}
\sum_{z\in D_n}H(x,y,z).$$
Function $H$ is discussed in \cite{campo}.
 Consider the set $W_3=\{001,010,100\}$. By Lemma~\ref{ML2}, we have
 $$d_{n+3}\equiv G(D_n\times D_n\times D_n)\equiv 
G(E_{n,m}^c\times E_{n,m}^c\times E_{n,m}^c)\pmod m.$$

Observe that for every automorphism $\pi\in \aut(B^n)$ and every $x, y,z\in D_n$, we have
$H(x,y,z)=H(\pi(x),\pi(y),\pi(z))$.
\begin{lemma}\label{L4}
Let $Y$ and $Z$ be subsets $Y,Z\subseteq D_n$ and suppose that $\pi(Y)=Y$ and $\pi(Z)=Z$ for every 
automorphism  $\pi\in \aut(B^n)$; and let $x$ and $y$ be two equivalent, $x\sim y$, elements in $D_n$. Then
\begin{enumerate}
\item $H(\{x\}\times Y\times Z)=H(\{y\}\times Y\times Z)$.
\item $H([x]\times Y\times Z)=\gamma(x)\cdot H(\{x\}\times Y\times Z)$.
\end{enumerate}
\end{lemma}
\begin{proof}
(1) $H(\{x\}\times Y\times Z)=\sum_{s\in Y}\sum_{t\in Z}H(x,s,t)=\sum_{s\in Y}\sum_{t\in Z}H(\pi(x),\pi(s),\pi(t))=
\sum_{u\in \pi(Y)}\sum_{v\in \pi(Z)}H(\pi(x),u,v)=\sum_{u\in Y}\sum_{v\in  Z}H(\pi(x),u,v)=H(\{\pi(x)\}\times Y\times Z)$. 
We use the fact that $\pi$ is a bijection on $Y\times Z$ and permutes the elements of $Y\times Z$.
\end{proof}

As an immediate corollary, we have the following:
\begin{theorem}\label{T5}
$$ d_{n+3}\equiv 
\sum_{x\in R_n\cap E_{n,m}^c}\sum_{y\in E_{n,m}^c}\sum_{z\in E_{n,m}^c} \gamma(x)\cdot
H(x,y,z)\pmod m.$$
Here, again, we identify each class $[x]\in R_n$ with 
its canonical representative.
\end{theorem}

\begin{example}
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 $\gamma$ value is presented in Table \ref{tab:r4gamma}.
For instance, there are six equivalence classes $[x]$ with $\gamma(x)=1$, two equivalence classes with $\gamma(x)=3$, and so forth. For $m=2$, the set $E^c_{4,2}$ contains only twelve elements
and $R_4\cap E^c_{4,2}$ contains eight elements. Similarly, for $m=3$, the set $E^c_{4,3}$ contains 42 elements and $R_4\cap E^c_{4,3}$ consists of 15 elements.
\end{example}

\begin{example}
We employed a Java implementation of the Theorem \ref{T5}. For $n=4$ and $m=2,3,4,6,12$ we have

$ d_7 \equiv 2320978352 \pmod 2$, and therefore $d_7 \bmod 2 = 0$,

$ d_7 \equiv 74128573428 \pmod 3$, and therefore $d_7 \bmod 3 = 0$,

$ d_7 \equiv 128268820802 \pmod 4$, and  therefore $d_7 \bmod 4 = 2$,

$ d_7 \equiv 89637133284 \pmod 6$, and therefore $d_7 \bmod 6 = 0$,

$ d_7 \equiv 566167187562 \pmod {12}$, and therefore $d_7 \bmod {12} = 6$.

\noindent One can check these values directly by dividing $d_7$ by 2, 3, 4, 6, and 12.
\end{example}

\begin{table}[ht]
\centering
\begin{tabular}[h]{| c | c |}
\hline
 $k$ &amp; $|\{f\in R_4:\gamma(f) = k\}|$ \\
\hline
1 &amp; 6 \\
3 &amp; 2 \\
4 &amp; 9 \\
6 &amp; 6 \\
12 &amp; 7 \\
\hline
\end{tabular}
\caption{Number of $f \in R_4$ with $\gamma(f) = k$.}
\label{tab:r4gamma}
\end{table}

\section{Counting functions from \texorpdfstring{$B^4$}{B4} to \texorpdfstring{$D_n$}{D(n)}}
By Lemma~\ref{L1}, 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 \cite{campo, Fid2001}), which for every six elements $a,b,c,d,e,f\in D_{n}$, counts how many functions $g\in 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$.

For $A\subseteq (D_n)^6$ let $F(A)$ denote $\sum_{(a,b,c,d,e,f)\in A}F(a,b,c,d,e,f)$.
By Lemma~\ref{L1}, we have
 $$d_{n+4}=F(D_n^6)=
\sum_{a\in D_n}\sum_{b\in D_n}\sum_{c\in D_n}
\sum_{d\in D_n}\sum_{e\in D_n}\sum_{f\in D_n}
F(a,b,c,d,e,f).$$

Consider the set $W_4=\{0011,0101,1001,0110,1010,1100\}$. By Lemma~\ref{ML2},
we have
$$d_{n+4}\equiv F(D_n^6)\equiv 
F((E_{n,m}^c)^6)\pmod m$$

Observe that for every automorphism  $\pi\in \aut(B^n)$ and every $a,b,c,d,e,f\in D_n$, we have
$F(a,b,c,d,e,f)=F(\pi(a),\pi(b),\pi(c),\pi(d),\pi(e),\pi(f))$.
Consider Cartesian product $Y=Y_1\times Y_2\times Y_3\times Y_4\times Y_5$ 
and let $\pi(y_1,\ldots,y_5)=(\pi(y_1),\ldots, \pi(y_5))$. Observe that, if $\pi(Y_i)=Y_i$ for every $i$, then $\pi(Y)=Y$ and $\pi$ permutes the elements of $Y$.

\begin{lemma}\label{L6}
Let $Y$ be a subset $Y\subseteq D_n^5$ and suppose that $\pi(Y)=Y$ for every automorphism  $\pi\in \aut(B^n)$; and let $x$ and $y$ be two equivalent, $x\sim y$, elements in $D_n$. Then
\begin{enumerate}
\item $F(\{x\}\times Y)=F(\{y\}\times Y)$.
\item $F([x]\times Y)=\gamma(x)\cdot F(\{x\}\times Y)$.
\end{enumerate}
\end{lemma}

\begin{proof}
(1) $F(\{x\}\times Y)=\sum_{s\in Y}F(x,s)=\sum_{s\in Y}F(\pi(x),\pi(s))=
\sum_{u\in \pi(Y)}F(\pi(x),u)=\sum_{u\in Y}F(\pi(x),u)=F(\{\pi(x)\}\times Y)$. 
We use the fact that $\pi$ is a bijection on $Y$ and permutes the elements of $Y$.
\end{proof}

As a corollary we get the following result.
\begin{theorem}\label{T7}
$$ d_{n+4}\equiv 
\sum_{a\in R_n\cap E_{n,m}^c}\sum_{b\in E_{n,m}^c}\sum_{c\in E_{n,m}^c}
\sum_{d\in E_{n,m}^c}\sum_{e\in E_{n,m}^c}\sum_{f\in E_{n,m}^c}
 \gamma(a)\cdot F(a,b,c,d,e,f)\pmod m.$$
\end{theorem}

 \begin{example}
We utilized a Java implementation of the Theorem \ref{T7}. For $n=4$ and $m=2,3,4,6,12$ we get

$ d_8 \equiv 53336702474849828 $, and therefore $d_8 \bmod 2 = 0$;

$ d_8 \equiv 3019662424037271148 \pmod 3$,  and therefore $d_8 \bmod 3 = 1$;

$ d_8 \equiv 25754060568741983624 \pmod 4$, and therefore $d_8 \bmod 4 = 0$;

$ d_8 \equiv 14729824485525634108 \pmod 6$, and therefore $d_8 \bmod 6 = 4$;

$ d_8 \equiv 15054599294580333880 \pmod {12}$, and therefore $d_8 \bmod {12} = 4$.

\noindent One can check these values directly by dividing $d_8$ by 2, 3, 4, 6, and 12.

\end{example}

\section{Application}\label{application}
To compute remainders of $d_9$ divided by 5 and 7, we chose the algorithm described in Section \ref{sec:b2sec}.
Our implementation lists all 490,013,148 elements of $R_7$ and calculates $\gamma(x)$ and $\re(\bot,x)$ for each element $x \in R_7$. This feat was previously accomplished only by Van Hirtum in 2021 \cite{hirtum}. It is worth noting that the number of elements $x$ in $R_n$ with $\gamma(x) = n!$ for $n &gt; 1$ can be found in the OEIS sequence \seqnum{A220879} (see Table \ref{tab:a220879}). Using the available precalculated sets, we can efficiently determine the $7$th term of the sequence, which was not recorded in the OEIS before.

\begin{table}[ht]
\centering
\begin{tabular}[h]{|p{0.25cm}|p{2.2cm}|}
\hline
 $n$ &amp; $\seqnum{A220879} \hspace{0.5mm}$$(n)$\\
\hline
1 &amp; 0 \\
2 &amp; 1 \\
3 &amp; 0 \\
4 &amp; 0 \\
5 &amp; 7 \\
6 &amp; 7281 \\
7 &amp; 468822749 \\
\hline
\end{tabular}
\caption{Inequivalent monotone Boolean functions of $n$ variables with no symmetries.}
\label{tab:a220879}
\end{table}

\begin{table}[ht]
\centering
\begin{tabular}[h]{| c | c |}
\hline
 $k$ &amp; $|\{f\in R_7:\gamma(f) = k\}|$ \\
\hline
1 &amp; 9 \\
7 &amp; 27 \\
21 &amp; 75 \\
30 &amp; 5 \\
35 &amp; 117 \\
42 &amp; 99 \\
70 &amp; 90 \\
84 &amp; 9 \\
105 &amp; 1206 \\
120 &amp; 4 \\
140 &amp; 702 \\
210 &amp; 3255 \\
252 &amp; 114 \\
315 &amp; 2742 \\
360 &amp; 18 \\
420 &amp; 26739 \\
504 &amp; 237 \\
630 &amp; 47242 \\
720 &amp; 4 \\
840 &amp; 75024 \\
1260 &amp; 1024050 \\
1680 &amp; 3128 \\
2520 &amp; 20005503 \\
5040 &amp; 468822749 \\
\hline
\end{tabular}
\caption{Number of $f \in R_7$ with the given $\gamma(f)$.}\label{tab:fr7}
\end{table}

Our program's most critical part, the Boolean function canonization procedure,
is based on Van Hirtum's fast approach \cite[Section 5.2.9]{hirtum} 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 \ref{tab:fr7}.
Note that

$$|E_{7,m}^c| = \sum_{\substack{x \in R_{7} \\ \gamma(x) \bmod m \neq 0}} \gamma(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.

\subsection{Remainder of \texorpdfstring{$d_9$}{d(9)} divided by 5}

$$\sum_{x\in R_7\cap E_{7,5}^c}\sum_{y\in E_{7,5}^c} \gamma(x)\cdot G(x,y) = 1404812111893131438640857806,$$
therefore, by Theorem \ref{T3}, we have $d_9 \bmod 5 = 1$. We calculated this number in approximately 7 hours.
Moreover, using Theorem \ref{T7} we have $d_9 \equiv 157853570524864492086 \pmod 5$, which confirms that $d_9 \bmod 5 = 1$.

\subsection{Remainder of \texorpdfstring{$d_9$}{d(9)} divided by 7}

$$\sum_{x\in R_7\cap E_{7,7}^c}\sum_{y\in E_{7,7}^c} \gamma(x)\cdot G(x,y) = 29989517764506682537562623,$$
therefore, by Theorem \ref{T3}, we have $d_9 \bmod 7 = 6$. We calculated this number in approximately half an hour.

\section{Acknowledgments}

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

\begin{thebibliography}{99}

  \bibitem{aigner} M. Aigner.
  \newblock {\it Combinatorial Theory.} 
  \newblock Springer, 1979.

  \bibitem{brouwer}
  A. E. Brouwer, C. F. Mills, W. H. Mills, and A. Verbeek.
  \newblock Counting families of mutually intersecting sets.
  \newblock {\em Electron. J. Comb.} {\bf 20} (2013).
  
  \bibitem{campo}
  F. a Campo.
  \newblock Relations between powers of Dedekind numbers and exponential sums related to them.
  \newblock \emph{J. Integer Sequences} {\bf 21} (2018), \href{https://cs.uwaterloo.ca/journals/JIS/VOL21/Campo/campo3.html}{Article 18.4.4}.

  \bibitem{Fid2001}
  R. Fidytek, A. W. Mostowski, R. Somla, and A. Szepietowski.
  \newblock Algorithms counting monotone Boolean functions.
  \newblock \emph{Inform. Process. Lett.}
  {\bf 79} (2001), 203--209.

  \bibitem{jakel}
  C. J\"akel.
  \newblock A computation of the ninth Dedekind number, arxiv preprint arXiv:2304.00895 [math.CO], 2023.
  \\ Available at \url{https://arxiv.org/abs/2304.00895}.

  \bibitem{hirtum}
  L. Van Hirtum.
  \newblock A path to compute the 9th Dedekind
  number using FPGA supercomputing (2021).
  \newblock Master's thesis, available at {\url{https://hirtum.com/thesis.pdf}}.

  \bibitem{hirtum2}
  L. Van Hirtum, P. De Causmaecker, J. Goemaere, T. Kenter, H. Riebler, M. Lass, and C. Plessl.
  \newblock A computation of D(9) using FPGA supercomputing, preprint, 2023. \\ Available at \url{https://arxiv.org/abs/2304.03039}.
  
  \bibitem{pawelski}
  B. Pawelski.
  \newblock On the number of inequivalent monotone Boolean functions of 8 variables.
  \newblock \emph{J. Integer Sequences} {\bf 25} (2022),
  \href{https://cs.uwaterloo.ca/journals/JIS/VOL25/Pawelski/pawelski7.html}{Article 25.7.7}.

  \bibitem{oeis}
  N. J. A. Sloane.
  \newblock The On-line Encyclopedia of Integer Sequences.
  \newblock Available at {\url{https://oeis.org}}.

  \bibitem{szepietowski}
  A. Szepietowski.
  \newblock Fixes of permutations acting on monotone Boolean functions.
  \emph{J. Integer Sequences} {\bf 25} (2022),
  \href{https://cs.uwaterloo.ca/journals/JIS/VOL25/Szepietowski/szep7.html}{Article 25.9.6}.

  \bibitem{Wied1991} D. Wiedemann.
  \newblock A computation of the eighth Dedekind number.
  \newblock {\em Order} {\bf 8} (1991), 5--6.

  \bibitem{Wiedlet}
  D. Wiedemann.
  \newblock Letter to N. J. A. Sloane (1990). Available at {\url{https://oeis.org/A000372/a000372.pdf}}.

  \bibitem{yamamoto}
  K. Yamamoto.
  \newblock Note on the order of free distributive lattices.
  \newblock {\em Sci. Rep. Kanazawa Univ.} {\bf 2} (1953), 5--6.
  \end{thebibliography}
  
  \bigskip
  \hrule
  \bigskip
  
  \noindent 
  2020 \emph{Mathematics Subject Classification}:~Primary 06E30.
  
  \medskip
  
  \noindent 
  \emph{Keywords}:~Dedekind number,
  monotone Boolean function,
  ninth Dedekind number,
  congruence modulo,
  Chinese remainder theorem.
  
  \bigskip
  \hrule
  \bigskip
  
  \noindent 
  (Concerned with sequences \seqnum{A000372}, \seqnum{A001206}, \seqnum{A003182} and \seqnum{A220879}.)
  
\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received March 15 2023;
revised versions received   March 16 2023; May 17 2023; June 13 2023; 
June 14 2023.
Published in {\it Journal of Integer Sequences}, August 16 2023.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                

</pre></body></html>