\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \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,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \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 Relations between Powers of Dedekind \\ Numbers and Exponential Sums \\ \vskip .08in Related to Them } \vskip 1cm \large Frank a Campo \\ Seilerwall 33 \\ D-41747 Viersen \\ Germany\\ \href{mailto:acampo.frank@gmail.com}{\tt acampo.frank@gmail.com} \end{center} \newcommand{\mytext}[1]{ \: \textrm{#1} \: } \newcommand{\mysetdescr}[2]{\left\{ #1 \: \left| \: #2 \right. \right\} } \newcommand{\mysetdef}[3]{#1 \; \equiv \;\mysetdescr{#2}{#3} } \newcommand{\myfr}[1]{ \mathfrak{#1} } \newcommand{\mydownarrow}{{\downarrow \,}} \newcommand{\myuparrow}{{\uparrow \,}} \newcommand{\myUparrow}{{\Uparrow \,}} \newcommand{\myN}{\mathbb{N}} \newcommand{\myNk}[1]{{\underline #1}} \newcommand\myplus{+} \newcommand\mytimes{\times} \newcommand\myparal{{\|}} \newcommand\myurbild[1]{\overline{#1}^1} \def\A{{\cal A}} \def\B{{\cal B}} \def\D{{\cal D}} \def\H{{\cal H}} \newcommand{\DP}{\D(P)} \newcommand{\DQ}{\D(Q)} \newcommand{\DDP}{\D^2 ( P )} \newcommand{\DDQ}{\D^2 ( Q )} \newcommand{\DDPQ}{\D^2( P \myplus Q )} \newcommand{\dDP}{d^2 ( P )} \newcommand{\dDQ}{d^2 ( Q )} \newcommand{\DDQe}{ \D^2 ( A_1 \myplus Q ) } \newcommand{\dDQe}{ d^2 ( A_1 \myplus Q ) } \newcommand{\dDQz}{ d^2 ( A_2 \myplus Q ) } \newcommand{\DDQk}[1]{ \D^2 ( A_{#1} \myplus Q ) } \newcommand{\dDQk}[1]{ d^2 ( A_{#1} \myplus Q ) } \newcommand{\DDk}[1]{ \D^2 ( A_{#1} ) } \newcommand{\dDk}[1]{ d^2 ( A_{#1} ) } \newcommand{\mf}[1]{\mathfrak{ #1 }} \newcommand{\powersumoN}[1]{ \displaystyle \sum_{ x \in Q } \delta( x )^{#1} } \newcommand{\powersumIoN}[1]{ \displaystyle \sum_{ x \in Q } \sum_{ y \in \mydownarrow x } \iota[ y, x ]^{#1} } \newcommand{\powersumoZ}[1]{ \displaystyle \sum_{ \mf{A} \in \DDQ } \delta( \mf{A} )^{#1} } \newcommand{\powersumkZ}[2]{ \displaystyle \sum_{ \mf{A} \in \DDQk{#1} } \delta( \mf{A} )^{#2} } \newcommand{\powersumIoZ}[1]{ \displaystyle \sum_{ \mf{A} \in \DDQ } \sum_{ \mf{B} \in \mydownarrow \mf{A} } \iota[ \mf{B}, \mf{A} ]^{#1} } \newcommand{\powersumIkZ}[2]{ \displaystyle \sum_{ \mf{A} \in \DDQk{#1} } \sum_{ \mf{B} \in \mydownarrow \mf{A} } \iota[ \mf{B}, \mf{A} ]^{#2} } \newcommand{\TpowersumkZ}[2]{ \sum_{ \mf{A} \in \DDQk{#1} } \delta( \mf{A} )^{#2} } \newcommand{\TpowersumIoZ}[1]{ \sum_{ \mf{A} \in \DDQ } \sum_{ \mf{B} \in \mydownarrow \mf{A} } \iota[ \mf{B}, \mf{A} ]^{#1} } \newcommand{\TpowersumIkZ}[2]{ \sum_{ \mf{A} \in \DDQk{#1} } \sum_{ \mf{B} \in \mydownarrow \mf{A} } \iota[ \mf{B}, \mf{A} ]^{#2} } \def\BP{\begin{proof}} \def\EP{\end{proof}} \begin{abstract} Let $\DDQ$ denote the downset-lattice of the downset-lattice of the finite poset $Q$ and let $\dDQ$ denote the cardinality of $\DDQ$. We investigate relations between the numbers $\dDQk{m}$ and their powers, where $A_m$ is the antichain with $m$ elements and $A_m \myplus Q$ the direct sum of $A_m$ and $Q$. In particular, we prove the inequality $\dDQ^3 < \dDQk{1}^2$ based on the construction of a one-to-one mapping between sets of homomorphisms. Furthermore, we derive equations and inequalities between the numbers $\dDQk{m}$ and exponential sums of downset sizes and interval sizes related to $\DDQk{m}$. 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. \end{abstract} \section{Introduction} \label{sec_introduction} In 1897, Richard Dedekind constructed the free distributive lattice with $k$ generators \cite{Dedekind_1897}. The cardinality of this universal algebraic object is called ``the $k$\textsuperscript{th} Dedekind number''. Already Dedekind realized that these numbers grow heavily with $k$ \cite{Dedekind_1897}, and due to the extreme computational complexity of their calculation, their values are known only for $0 \leq k \leq 8$ (Table \ref{table_Dedekind_Zahlen}). \begin{table} \begin{center} \begin{tabular}{| c | r | } \hline $ k $ & $k$\textsuperscript{th} Dedekind number \\ \hline \hline 0 & 2 \\ 1 & 3 \\ 2 & 6 \\ 3 & 20 \\ 4 & 168 \\ 5 & 7581 \\ 6 & 7828354 \\ 7 & 2414682040998 \\ 8 & 56130437228687557907788 \\ \hline \end{tabular} \caption{\label{table_Dedekind_Zahlen} Known Dedekind numbers.} \end{center} \end{table} Dedekind knew the numbers for $k = 3$ and $k = 4$ \cite{Dedekind_1897} (I do not differentiate between the free distributive lattice and its lattice-theoretical completion here). The calculation of the $5$\textsuperscript{th} Dedekind number in 1940 is due to Church \cite{Church_1940}. Ward \cite{Ward_1946} computed the $6$\textsuperscript{th} one in 1946 and confirmed Church's result. The calculation of the $7$\textsuperscript{th} Dedekind number in 1965 was done again by Church \cite{Church_1965}, and later on repeated by Berman and K\"{o}hler in 1976 \cite{Berman_Koehler_1976}, and by Markowsky in 1989 \cite{Markowsky_1989}. Finally, Wiedemann computed the $8$\textsuperscript{th} one in 1991 \cite{Wiedemann_1991}, and his result was confirmed by Fidytek et al.\ in 2001 \cite{Fidytek_etal_2001}. Also the work of Lunnon in 1971 has to be mentioned \cite{Lunnon_1971}, even if he did not succeed in calculating the correct value of the $7$\textsuperscript{th} Dedekind number. In 1988, Kisielewicz presented a formula in closed form \cite{Kisielewicz_1988}, but it is far too complicated to be evaluated even for small values of $k$. The sequence number of Dedekind numbers in the OEIS \cite{Sloane_DB} is \seqnum{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 \cite{Berman_Koehler_1976, Birkhoff_1967, Lunnon_1971, Markowsky_1989}. 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 $\ell$ elements. In 1968, Riviere developed formulas for $\ell \leq 3$ \cite{Riviere_1968}. The step to $\ell = 4$ was done by Cvetkovi\'{c} in 1972 \cite{Cvetkovic_1972}, and Arocha solved the cases $\ell = 5, 6$ in 1982 \cite{Arocha_1982}. Kilibarda and Jovovi\'{c} developed the method further and presented explicit formulas for $1 \leq \ell \leq 10$ in 2003 \cite{Kilibarda_Jovovic_2003}. Based on the work of Pippenger in 1999 \cite{Pippenger_1999} and Kahn in 2002 \cite{Kahn_2002}, Carroll et al.\ extended the enumeration of antichains to more general structures in 2009 \cite{Carroll_etal_2009}. The approach for counting monotone Boolean functions presented by Bakoev in 2012 \cite{Bakoev_2012} 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 \cite{Gilbert_1954}. Based on the pioneering work of Hansel \cite{Hansel_1966} in 1966, Kleitman \cite{Kleitman_1969_2} and Kleitman and Markowsky \cite{Kleitman_Markowsky_1975} 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 \cite{Korshunov_1981}, followed by the work of Sapozhenko in 1989 \cite{Sapozhenko_1989}. 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 $\DDQ$ denote the downset-lattice of the downset-lattice of the finite poset $Q$ and let $\dDQ$ denote the cardinality of $\DDQ$. With $A_m$ being the antichain with $m$ elements, the subject of the present paper is the numbers $\dDQk{m}$, where $A_m \myplus Q$ is the direct sum of $A_m$ and $Q$. Section \ref{sec_Preliminaries} contains the notational apparatus and the required facts about downsets and downset-lattices. In Section \ref{subsec_powers}, we construct in Theorem \ref{theorem_rho_inj} a one-to-one mapping between sets of homomorphisms, and this mapping is used to prove the relation $\dDQ^3 < \dDQk{1}^2 $ and other inequalities. In Section \ref{subsec_sums}, we investigate the relations between the numbers $\dDQk{m}$ and the exponential sums $ \TpowersumkZ{m}{k} $ and $ \TpowersumIkZ{m}{k} $, where $\delta(\mf{A})$ is the cardinality of the downset created by $\mf{A} \in \D^2( A_m \myplus Q)$, and $\iota[ \mf{B}, \mf{A}]$ is the cardinality of the interval $[ \mf{B}, \mf{A}] \subseteq \D^2( A_m \myplus Q)$. The results are used in Section \ref{sec_calculation} to compare the computational times of algorithms for the calculation of the Dedekind numbers $\dDk{m}$, including a new algorithm. \section{Preliminaries} \label{sec_Preliminaries} \subsection{Notation} \label{subsec_notation} We are working with {\em finite posets}, that is, ordered pairs $P = (X,\leq)$ consisting of a finite set $X$ and a {\em partial order} $\leq$ on $X$, i.e., a reflexive, antisymmetric, and transitive subset of $X \mytimes X$. We call $X$ the {\em carrier} of $P$ and say that $P$ is a poset {\em on} $X$. Due to reflexivity, the {\em diagonal} $\mysetdef{\Delta_X}{(x,x)}{x\in X}$ is always a subset of $\leq$. As usual, I write $x \leq y$ for $(x,y) \in \,\leq$. The symbols $<, \geq$, and $>$ are used in their conventional meaning, and $x \; \| \; y$ means ``$(x, y) \notin \,\leq$ and $(y, x) \notin \,\leq$''. Two elementary posets can be defined on any set $X$: The {\em antichain} $(X, \Delta_X)$ and the {\em chain}, of which the latter is characterized by $x \leq y$ or $y \leq x$ for all $x, y \in X$. For a finite set $X$ of cardinality $k \in \myN_0$, I write $A_k$ for the antichain on $X$, and $C_k$ for the chain on $X$. For any poset $P = (X, \leq)$, the {\em dual} $P^\partial = (X, \leq^\partial )$ is defined by $x \leq^\partial y \Leftrightarrow y \leq x$ for all $x, y \in 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) \equiv \# \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 ``$\simeq$'' and we write $P \simeq^\partial Q$ iff $P \simeq Q^\partial$. The automorphism group of $P$ is denoted by $\A(P)$. For posets $P_1 = (X_1, \leq_1)$ and $P_2 = (X_2, \leq_2)$ with $X_1 \cap X_2 = \emptyset$, their {\em direct sum} is the poset $P_1 + P_2 \equiv (X_1 \cup X_2, \leq_1 \cup \leq_2)$, and their {\em ordinal sum} is the poset $P_1 \oplus P_2 \equiv (X_1 \cup X_2, \leq_1 \cup \leq_2 \cup ( X_1 \mytimes X_2 ))$. For $k \in \myN$, we define \begin{align*} \Lambda_k & \equiv A_{k-1} \oplus A_1, \\ M_k & \equiv A_1 \oplus A_{k-2} \oplus A_1 \;\; \mytext{for} k \geq 2. \end{align*} The posets $\Lambda_4$ and $M_5$ are illustrated in Figure \ref{figure_L4_M5}. \begin{figure} \begin{center} \includegraphics{Abb_Dedekind_1_L4_M5.eps} \caption{\label{figure_L4_M5} $\Lambda_4$ and $M_5$.} \end{center} \end{figure} Given posets $P_1 = (X_1, \leq_1 ) $ and $P_2 = (X_2, \leq_2)$, the component-wise partial order $P_1 \mytimes P_2 \equiv (X_1 \mytimes X_2, \preceq) $ on $X_1 \mytimes X_2$ is defined by $(x_1,x_2) \preceq (y_1, y_2) $ iff $ x_1 \leq_1 y_1$ and $x_2 \leq_2 y_2$. I write $P^k$ for $P \mytimes \cdots \mytimes P$ with $k$ factors $P$. We have $\H(P,Q^k) \simeq \H( P, Q )^k$ for all $ k \in \myN$. A {\em 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 , \ldots , x_m \}$ with $m = \# X$, whereas we are using the carrier $Y = \{ y_1, \ldots, 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 , \ldots , x_m \}$ for the carrier of $A_m$, whereas in the case $Q = A_n$, we use $Y = \{ y_1, \ldots, y_n \}$ for the carrier of $A_n$. For the partial orders belonging to $P$ and $Q$, we use the same symbol ``$\leq$'' in most cases. For a mapping $f : A \rightarrow B$, the {\em pre-image} of $B' \subseteq B$ is denoted by \begin{align*} \myurbild{f}(B') & \equiv \mysetdescr{ a \in A}{ f(a) \in B'}; \end{align*} for $b \in B$ we write $\myurbild{f}(b) \equiv \myurbild{f} (\{ b\} )$. We define $\myNk{0} \equiv \emptyset$ and $\myNk{\ell} \equiv \{ 1, \ldots , \ell \}$ for every $\ell \in \myN$. \subsection{Downsets and downset-lattices} \label{subsec_Downsets} Downsets are one of the fundamental concepts in order theory. Given a poset $P = (X, \leq)$, a subset $D \subseteq X$ is called a {\em downset} or {\em order ideal} of $P$ iff $x \in D$ holds for every $x \in X$, for which a $y \in D$ exists with $x \leq y$. The set of downsets of $P$ is denoted by $\DP$ and its cardinality by $d(P) \equiv \# \DP$. By applying well-known isomorphisms we get for all posets $P$ and $Q$ \begin{align} \H( P, \D(Q) ) & \simeq \H(Q, \D(P)). \label{isom_HPDQ_HQDP} \end{align} For $x \in X$ we define the downset created by $x$ in $P$ by \begin{align*} \mydownarrow x & \equiv \mysetdescr{ y \in X }{ y \leq x }. \end{align*} We write $ \delta(x) \equiv \# \mydownarrow x$ for the cardinality of $ \mydownarrow x$. {\em Upsets} are the duals of downsets: For a poset $P = (X, \leq)$, a subset $U \subseteq X$ is called an {\em upset} or {\em order filter} of $P$ iff $x \in U$ holds for every $x \in X$ for which a $y \in U$ exists with $x \geq y$. For $x \in X$ and $A \subseteq X$ we define \begin{align*} \myuparrow x & \equiv \mysetdescr{ y \in X }{ y \geq x }, \\ \myUparrow A & \equiv \bigcup_{a \in A} \myuparrow a \; = \; \mysetdescr{ y \in X }{ \exists_{a \in A} \mytext{:} a \leq y }. \end{align*} For $x, y \in X$ we define the {\em interval} \begin{align*} [ y, x ] & \equiv ( \myuparrow y ) \cap ( \mydownarrow x ) \; = \; \mysetdescr{ z \in X }{ y \leq z \leq x}. \end{align*} For the cardinality of $[ y, x ]$ we write $\iota[ y, x ] \equiv \# [ y, x ]$. A finite partial order $P = (X, \leq)$ is called a {\em lattice} iff for every subset $A \subseteq X$ the downset $\cap_{a \in A} \mydownarrow a$ and the upset $\cap_{a \in A} \myuparrow a$ are non-empty and additionally \begin{equation} \inf A \; \equiv \; \max \bigcap_{a \in A} \mydownarrow a \quad \mytext{and} \quad \sup A \; \equiv \; \min \bigcap_{a \in A} \myuparrow a \label{formeln_inf_sup} \end{equation} both exist. In Section \ref{subsec_effort}, we need the following equation: \begin{lemma} \label{lemma_intervallpotenzen} Let $P$ be a finite lattice. Then for every $k \in \myN$ \begin{align*} \sum_{a \in P} \sum_{b \in \mydownarrow a} \iota[ b, a ]^k & = \sum_{( x_1, \ldots , x_k) \in X^k} \left( \# \mydownarrow \inf \mysetdescr{ x_i }{ i \in \myNk{k}} \right) \cdot \left( \# \myuparrow \sup \mysetdescr{ x_i }{ i \in \myNk{k}} \right). \end{align*} \end{lemma} \BP For $(b,a) \in X^2$ \begin{align*} [ b, a ]^k & = \mysetdescr{ ( x_1, \ldots , x_k) \in X^k}{ b \leq x_i \leq a \mytext{for all} i \in \myNk{k} } \\ & = \mysetdescr{ ( x_1, \ldots , x_k) \in X^k}{ b \in \cap_{i \in \myNk{k}} \mydownarrow x_i, a \in \cap_{i \in \myNk{k}} \myuparrow D_i} \\ & \stackrel{\eqref{formeln_inf_sup}}{=} \mysetdescr{ ( x_1, \ldots , x_k) \in X^k}{ b \leq \inf \mysetdescr{ x_i }{ i \in \myNk{k}}, a \geq \sup \mysetdescr{ x_i }{ i \in \myNk{k}}}, \end{align*} and the lemma is proven because by rearranging the summation we get \begin{align*} & \sum_{(b,a) \in X^2} \# \mysetdescr{ ( x_1, \ldots , x_k) \in X^k}{ b \leq \inf \mysetdescr{ x_i }{ i \in \myNk{k}}, a \geq \sup \mysetdescr{ x_i }{ i \in \myNk{k}}} \\ & = \sum_{( x_1, \ldots , x_k) \in X^k} \left( \# \mydownarrow \inf \mysetdescr{ x_i }{ i \in \myNk{k}} \right) \cdot \left( \# \myuparrow \sup \mysetdescr{ x_i }{ i \in \myNk{k}} \right). \end{align*} \EP If we equip $\DP$ with the partial order induced by set inclusion, $\D(P)$ becomes itself a partial order. We use $\DDP \equiv \D( \D( P ) )$ as symbol for the set of the downsets of $\DP$; the cardinality of this set is denoted by $\dDP \equiv \# \DDP$. The poset $\DDQ$ is never an antichain, and we have \begin{align} \DDPQ & \simeq \H( \DQ, \DDP) . \label{isom_DDPQ} \end{align} Furthermore, $\inf \B = \cap \B$ and $\sup \B = \cup \B$ for all $\B \subseteq \DDP$. 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 \cite[p.\ 194]{Birkhoff_1967}. The lattice of sets isomorphic to the completed free distributive lattice with $k$ generators is $\DDk{k}$, the downset-lattice of the power set of a $k$-element set \cite[p.\ 61]{Birkhoff_1967}, and $\dDk{k}$ is the $k$\textsuperscript{th} Dedekind number. The sets $\DDk{k}$, $0 \leq k \leq 3$, are shown in Figure \ref{figure_FDLs}. The non-isomorphic elements of $\DDk{4}$ and the numbers of their downsets are shown in the appendix. \begin{figure} \begin{center} \includegraphics{Abb_Dedekind_2_DDAk.eps} \caption{\label{figure_FDLs} Free distributive lattices with up to three generators.} \end{center} \end{figure} \section{Powers and exponential sums} \label{sec_DDQk} \subsection{Powers of $\dDQ$ and $\dDQk{1}$} \label{subsec_powers} In this section we prove the three inequalities \begin{align} \dDQk{1} & < \dDQ^2 < \dDQk{2}, \label{ungl_1_2} \\ \dDQ^3 & < \dDQk{1}^2. \label{ungl_3_2} \end{align} The first inequality in \eqref{ungl_1_2} is already mentioned by Wiedemann \cite{Wiedemann_1991}, and its proof is simple. For every poset $R$ we have $\D(R)^2 \simeq^\partial \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) \leq h(R, (C_2)^2)$, with equality iff $R$ is the empty poset. Now the inequality follows by replacing $R$ by $\D(Q) \not= \emptyset$, because \eqref{isom_DDPQ} delivers $\DDQe \simeq \H(\D(Q), C_3)$. The proof of the two remaining inequalities is more involved. We need the following definition: \begin{definition} \label{def_connected} Let $Q$ be any poset, $A \subseteq Y$, and $x, y \in A $. We say that $x$ and $y$ are {\em connected in $A$}, iff there are $z_0, z_1, \ldots , z_L \in A$ with $x = z_0$, $y = z_L$ and $ z_{\ell-1} \leq z_\ell$ or $z_\ell \leq z_{\ell-1}$ for all $\ell \in \myNk{L}$. We define for all $A \subseteq Y$, $x \in A $, $B \subseteq A$ \begin{align*} \gamma_{Q, A}(x) & \equiv \mysetdescr{ y \in A }{ x \mytext{and} y \mytext{are connected in} A}, \\ \gamma_{Q, A}(B) & \equiv \bigcup_{ b \in B } \gamma_{Q, A}(b). \end{align*} We write $\gamma_Q$ for $\gamma_{Q,Y}$, and if $Q$ is fixed, we write $\gamma_A$ instead of $\gamma_{Q,A}$. \end{definition} \begin{corollary} \label{corr_gamma_def} Let $A \subseteq Y$. The relation ``connected in $A$'' is an equivalence relation on $A$ with partition $\mysetdescr{\gamma_A(a)}{a \in A}$. For $x \in A \subseteq A' \subseteq Y$ and $B \subseteq B' \subseteq A$ we have \begin{align} B & \subseteq \gamma_A(B), \label{gamma_BB} \\ \gamma_A(B) & \subseteq \gamma_A(B'), \label{gamma_BB2} \\ \gamma_A(B) & \subseteq \gamma_{A'}(B), \label{gamma_ABAB} \\ \gamma_A(B) & = \gamma_{\gamma_A(B)}(B). \label{gamma_ggc} \end{align} \end{corollary} \BP All but \eqref{gamma_ggc} are direct consequences from Definition \ref{def_connected}. For the proof of ``$\subseteq$'' in \eqref{gamma_ggc}, let $x \in \gamma_A(B)$. There exists a $b \in B$ and $z_0, z_1, \ldots , z_L \in A$ with $x = z_0$, $b = z_L$ and $ z_{\ell-1} \leq z_\ell$ or $z_\ell \leq z_{\ell-1}$ for all $\ell \in \myNk{L}$. We conclude $z_\ell \in \gamma_A(b)$ for all $\ell \in \myNk{L}$, and $x$ and $b$ are connected in $\gamma_{\gamma_A(b)}(b)$, too. Hence $x \in \gamma_{\gamma_A(b)}(b) \subseteq \gamma_{\gamma_A(B)}(B)$. ``$\supseteq$'' follows with \eqref{gamma_ABAB}. \EP \begin{lemma} \label{lemma_gamma} Let $\xi : Q \rightarrow P$ be a homomorphism. \noindent (a) For $B \subseteq A \subseteq Y$ we have $\xi( \gamma_{Q,A}(B) ) \subseteq \gamma_{P,\xi(A)}(\xi(B))$. \noindent (b) Let $A \subseteq X$ be an antichain of $P$ and $A' \subseteq \myurbild{\xi}(A)$. Then $\xi( \gamma_{Q,A'}(x) ) = \{ \xi(x) \}$ for every $x \in A'$; in particular, for every $x \in A'$, there exists a $y \in A$ with $\gamma_{Q,A'}(x) \subseteq \myurbild{\xi}(y)$. \end{lemma} \BP (a) is a direct consequence of Definition \ref{def_connected}; for the proof of (b), use (a). \EP \begin{figure} \begin{center} \includegraphics{Abb_Dedekind_3_BS.eps} \caption{\label{figure_Proof_Theorem} Illustrations to Theorem \ref{theorem_rho_inj} and Corollary \ref{corr_HPB_HP}. a) The posets $B \equiv (C_2)^3$ and $S$ with their points represented by binary words. b) Assignment of the sets $ \bot, \ell, r, \ldots $ to the points of $B$ and $S$.} \end{center} \end{figure} \begin{theorem} \label{theorem_rho_inj} We define the posets $B \equiv (C_2)^3$ (the cube) and $S$ as shown in Figure \ref{figure_Proof_Theorem}(a) with their points represented by binary words. For every homomorphism $\xi \in \H(Q, B)$, we define the mapping $\rho(\xi) : Q \rightarrow S$ by (cf.\ Figure \ref{figure_Proof_Theorem}(b)) \begin{center} \begin{tabular}{ll} $\quad z \quad \equiv \quad \myurbild{\xi}(010), $& $\quad \quad r \quad \equiv \quad \myurbild{\xi}(001), $\\ $\quad Z \quad \equiv \quad \myurbild{\xi}(101), $& $\quad \quad \Gamma \quad \equiv \quad \gamma_Z( Z \cap \myUparrow r ), $\\ $\quad \myurbild{\rho(\xi)}(0000) \quad \equiv \quad \bot \quad \equiv \quad \myurbild{\xi}(000), $& $\quad \quad \myurbild{\rho(\xi)}(0100) \quad \equiv \quad \ell \quad \equiv \quad \myurbild{\xi}(100), $\\ $\quad \myurbild{\rho(\xi)}(0001) \quad \equiv \quad r, $& $\quad \quad \myurbild{\rho(\xi)}(1100) \quad \equiv \quad Z \setminus \Gamma, $\\ $\quad \myurbild{\rho(\xi)}(0101) \quad \equiv \quad z \cup \Gamma, $& $\quad \quad \myurbild{\rho(\xi)}(1101) \quad \equiv \quad L \quad \equiv \quad \myurbild{\xi}(110), $\\ $\quad \myurbild{\rho(\xi)}(0111) \quad \equiv \quad R \quad \equiv \quad \myurbild{\xi}(011), $& $\quad \quad \myurbild{\rho(\xi)}(1111) \quad \equiv \quad \top \quad \equiv \quad \myurbild{\xi}(111)$. \end{tabular} \end{center} Then $\rho \mytext{:} \H(Q, B) \rightarrow \H(Q, S)$, $\xi \mapsto \rho(\xi)$, is a one-to-one mapping. \end{theorem} \BP {\em $\rho(\xi)$ is well-defined:} $\xi$ is a mapping from $Q$ to $B$. Therefore, the sets $\bot, \ell, z, r, L, Z, R$, and $\top$ are pairwise disjoint, and their union is $Y$. In consequence, also the sets $\bot, \ell, r, Z \setminus \Gamma, z \cup \Gamma, L, R, \top$ are pairwise disjoint with union $Y$, and $\rho(\xi)$ is a well-defined mapping from $Q$ to $S$. {\em $\rho(\xi)$ is a homomorphism:} Let $x, y \in Y$ with $x \leq y$. Looking at Figure \ref{figure_Proof_Theorem}(b), we see that for $x \in \bot \cup \ell \cup z \cup L \cup R \cup \top$ the relation $\rho(\xi)(x) \leq_S \rho(\xi)(y)$ is a direct consequence of $\xi(x) \leq_B \xi(y)$. The cases $x \in r$ and $x \in Z $ remain. For $x \in r$, $001 = \xi(x) \leq_B \xi(y)$ yields $y \in r \cup Z \cup R \cup \top$. For $y \in r \cup R \cup \top$ we get $ \rho(\xi)(y) \in \{ 0001, 0111, 1111 \}$, and thus $\rho(\xi)(x) = 0001 \leq_S \rho(\xi)(y)$. Let $y \in Z$. Because of $x \leq y$, we have $y \in Z \cap \myUparrow r \stackrel{\eqref{gamma_BB}}{\subseteq} \Gamma$, and thus $\rho(\xi)(x) = 0001 <_S 0101 = \rho(\xi)(y)$. For $x \in Z$ we have $\rho(\xi)(x) \in \{ 1100, 0101 \}$. Furthermore, $\xi(x) \leq_B \xi(y)$ yields $y \in Z \cup \top$. In the case $y \in \top$ we have $\rho(\xi)(x) <_S 1111 = \rho(\xi)(y)$. Let $y \in Z$. Then we have $y \in \gamma_Z(x)$, which yields $\gamma_Z(y) = \gamma_Z(x)$ (Corollary \ref{corr_gamma_def}). Because $\Gamma$ is the union of the $\gamma_Z(a)$ over the $a \in Z \cap \myUparrow r$, we have $x \in \Gamma \Leftrightarrow y \in \Gamma$, hence $\rho(\xi)(x) = 0101 = \rho(\xi)(y)$ or $\rho(\xi)(x) = 1100 = \rho(\xi)(y)$, and $\rho(\xi)$ is indeed a homomorphism. {\em $\rho : \H(Q,B) \rightarrow \H(Q,S)$ is one-to-one:} Looking at Figure \ref{figure_Proof_Theorem}(b), we realize that all is proven if we can reconstruct the set $\Gamma$ by means of $\rho(\xi)$. We need the following technical equations: \begin{align} Z \cap \myUparrow r & = ( z \cup \Gamma ) \cap \myUparrow r , \label{eq_Gamma_1} \\ \Gamma & = \gamma_{z \cup \Gamma}( (z \cup \Gamma) \cap \myUparrow r). \label{eq_Gamma_2} \end{align} \eqref{eq_Gamma_1} ``$\subseteq$'': $ Z \cap \myUparrow r = ( Z \cap \myUparrow r ) \cap \myUparrow r \stackrel{\eqref{gamma_BB}}{\subseteq} \Gamma \cap \myUparrow r$. ``$\supseteq$'': Assume $r = \myurbild{\xi}(001) \not= \emptyset$. Then we have $\xi(x) \geq_B 001$ for every $x \in \myUparrow r$, hence $x \notin \myurbild{\xi}(010) = z$ due to $010 \; \|_B \; 001$. We conclude $z \cap \myUparrow r = \emptyset$ (trivial for $r = \emptyset$), hence $ (z \cup \Gamma ) \cap \myUparrow r = \Gamma \cap \myUparrow r \subseteq Z \cap \myUparrow r$. \eqref{eq_Gamma_2}: Due to \eqref{eq_Gamma_1}, we have to show $ \Gamma = \gamma_{z \cup \Gamma}( Z \cap \myUparrow r)$. ``$\subseteq$'' we get by $ \Gamma \stackrel{\eqref{gamma_ggc}}{=} \gamma_\Gamma(Z \cap \myUparrow r) \stackrel{\eqref{gamma_ABAB}}{\subseteq} \gamma_{z \cup \Gamma}(Z \cap \myUparrow r)$. Now let $x \in \gamma_{z \cup \Gamma}(a)$ for an $a \in Z \cap \myUparrow r$. We have $ z \cup \Gamma \subseteq \myurbild{\xi}( \{ 010, 101 \} )$ with $010 \; \|_B \; 101$. From Lemma \ref{lemma_gamma}(b) we get $\gamma_{z \cup \Gamma}(a) \subseteq \myurbild{\xi}(010) = z$ or $\gamma_{z \cup \Gamma}(a) \subseteq \myurbild{\xi}(101) = Z $, and due to $a \in Z$ it is the latter inclusion which holds. We obtain $x \in (z \cup \Gamma) \cap Z = \Gamma$, as required. With \eqref{eq_Gamma_2} we get \begin{align*} \Gamma & = \gamma_{\myurbild{\rho(\xi)}(0101)}(\myurbild{\rho(\xi)}(0101) \cap \myUparrow \myurbild{\rho(\xi)}(0001) ), \end{align*} and the proof is finished. \EP Inequality \eqref{ungl_3_2} and the second inequality in \eqref{ungl_1_2} are proven as part (b) and (c) of the following corollary: \begin{corollary} \label{corr_HPB_HP} For every finite poset $Q$ we have \noindent (a) $h(Q,B) \leq h(Q,S)$ with equality iff $Q$ is an antichain. \noindent (b) $\dDQ^3 \; < \; \dDQe^2$. \noindent (c) $\dDQ^2 \; < \; \dDQk{2}$. \end{corollary} \BP \noindent (a) The inequality is a direct consequence of Theorem \ref{theorem_rho_inj}. For $Q \simeq A_n$, both sets of homomorphisms have cardinality $8^n$. If $Q$ is not an antichain, $x, y \in Y$ exist with $y < x$. We define $\zeta \in \H(Q,S)$ by \begin{align*} \myurbild{\zeta}(1100) & \equiv Y \setminus \myuparrow x, \\ \myurbild{\zeta}(1101) & \equiv \myuparrow x. \end{align*} Then we have $y \in \myurbild{\zeta}(1100)$ and $x \in \myurbild{\zeta}(1101)$. But $\zeta$ is not in the image of $\rho$, because for $\xi \in \H(Q,B)$, $a \in \myurbild{\rho(\xi)}(1100) \subseteq Z = \myurbild{\xi}(101)$, $b \in \myurbild{\rho(\xi)}(1101) = L = \myurbild{\xi}(110)$ it must hold $ a \; \| \, b$ due to $\xi(a) = 101 \; \|_B \; 110 = \xi(b)$. \noindent (b) We have $\DDQ^3 \simeq^\partial \H( \D(Q), B )$, and we have already seen in the proof of the first inequality in \eqref{ungl_1_2} that $\DDQe$ is isomorphic to $\H( \D(Q), C_3) $. Thus, $\DDQe^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). \noindent (c) Applying (b) twice yields $ \dDQ^2 < \dDQk{1}^\frac{4}{3} < \dDQk{2}^\frac{8}{9}$. \EP Corollary \ref{corr_HPB_HP}(a) can be reformulated as follows: \begin{corollary} \label{corr_injektion} Let $R$ be a finite distributive lattice and let $N$ be the poset with N-shaped diagram. Then $h(A_3, R) = (\# R)^3 \leq h(N, R)$ with equality iff $R = \D(A_k)$ for $k \in \myN^0$, i.e., iff $R$ is a power set. \end{corollary} \BP With $Q$ being the poset of the join-irreducible elements of $R$, we have $R \simeq \D(Q)$. \eqref{isom_HPDQ_HQDP} yields $\H( A_3, R) \simeq \H( Q, \D(A_3))$ and $\H( N, R) \simeq \H( Q, \D(N))$, and due to $\D(A_3) \simeq (C_2)^3 = B$ and $\D(N) \simeq S$ the statements follow with Corollary \ref{corr_HPB_HP}(a). \EP 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 \ref{subsec_effort}, we will use the inequalities \eqref{ungl_1_2} and \eqref{ungl_3_2} 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 \eqref{ungl_1_2} and \eqref{ungl_3_2}, we have firstly shown $h(\DQ,T) \leq h(\DQ, 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 $\dDQk{1}$, $\dDQ^2$, and $\dDQk{2}$ on the one hand, and the difference between $\dDQ^3$ and $\dDQk{1}^2$ on the other hand, will be large in most cases, as confirmed by Table \ref{table_Squares_Cubes} for Dedekind numbers. (Here, as in what follows, we avoid calculations involving the $8$\textsuperscript{th} Dedekind number.) \begin{table} \begin{center} \begin{tabular}{| c | r | r | r |} \hline $k$ & $\dDk{k}$ & $\dDk{k}^2$ & $\dDk{k}^3$ \\ \hline \hline 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 \\ \hline \end{tabular} \caption{\label{table_Squares_Cubes} Dedekind numbers and their squares and cubes.} \end{center} \end{table} \subsection{Exponential sums} \label{subsec_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 \begin{align} \powersumoN{k} & = h( \Lambda_{k+1}, Q ), \label{powersum_d} \\ \powersumIoN{k} & = h( M_{k+2}, Q ). \label{powersum_I} \end{align} Furthermore, \eqref{isom_DDPQ} yields \begin{align} \DDQk{m} & \simeq \H( \D( A_m ), \DDQ ), \label{isom_DDQm} \end{align} with the immediate consequences \begin{align} \dDQe & = \powersumoZ{}, \label{formel_dDQe} \\ \dDQz & = \powersumIoZ{2}. \label{formel_dDQz} \end{align} Eq.~\eqref{formel_dDQe} can be found in the papers \cite{Berman_Koehler_1976, Fidytek_etal_2001, Lunnon_1971, Markowsky_1989, Riviere_1968, Yusun_2011}, and \eqref{formel_dDQz} is used by Fidytek et al.\ \cite{Fidytek_etal_2001}. The basis of our investigation in this section is the following lemma: \begin{lemma} \label{lemma_bijHom_Emb} 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$. \noindent (a) Let $\phi : P_1 \rightarrow P_2$ be a bijective homomorphism. Then \begin{align*} \Phi : \H(P_2, Q) & \rightarrow \H(P_1, Q), \\ \xi & \mapsto \xi \circ \phi \end{align*} is a one-to-one homomorphism. If $Q$ is not an antichain, then $\Phi$ is onto (and an isomorphism) iff $\phi$ is an isomorphism. If $Q$ is an antichain, then $\Phi$ is onto iff the induced mapping \begin{align*} \phi' : \mysetdescr{ \gamma_{P_1}(x) }{ x \in X_1 } & \rightarrow \mysetdescr{ \gamma_{P_2}(z) }{ z \in X_2 } \\ \gamma_{P_1}(x) & \mapsto \gamma_{P_2}(\phi(x)) \end{align*} is one-to-one. \noindent (b) Let $\psi : P_1 \rightarrow P_2$ be an embedding, and let $Q$ be a complete lattice. Then \begin{align*} \Psi : \H(P_2, Q) & \rightarrow \H(P_1, Q) \\ \xi & \mapsto \xi \circ \psi \end{align*} is a homomorphism and onto. For $Q \simeq A_1$, $\Psi$ is one-to-one. For $Q \not\simeq A_1$, $\Psi$ is one-to-one (and an isomorphism) iff $\psi$ is an isomorphism. \end{lemma} \BP Obviously, $\Phi$ and $\Psi$ are well defined homomorphisms. \noindent (a) Because $\phi$ is bijective, $\Phi$ is one-to-one. If $Q$ is not an antichain, then there exist elements $a, b \in Y$ with $a < b$. Nothing has to be proven if $\phi$ is an isomorphism. Assume that $\phi$ is not an isomorphism. Then there exist $x, y \in X_1$ with $x \not\leq y$ but $\phi(x) \leq \phi(y)$. We define an homomorphism $\zeta \in \H( P_1, Q)$ by setting for all $z \in X_1$: \begin{align*} \zeta(z) & \equiv \begin{cases} a, & \mytext{if} z \in \mydownarrow y; \\ b, & \mytext{if} z \in X_1 \setminus \mydownarrow y. \end{cases} \end{align*} Then $\zeta(x) = b > a = \zeta(y)$, and $\Phi$ is not onto due to $(\xi \circ \phi)(x) \leq (\xi \circ \phi)(y)$ for all $\xi \in \H(P_2, Q)$. Assume, that $Q$ is an antichain. With the help of Lemma \ref{lemma_gamma} we see that the mapping $\phi'$ is well-defined. Assume, that $\phi'$ is one-to-one. Let $\zeta \in \H(P_1, Q)$, and define $\xi \equiv \zeta \circ \phi^{-1}$. For $x, y \in X_2$ with $x \leq y$, Corollary \ref{corr_gamma_def} yields $\gamma_{P_2}(x) = \gamma_{P_2}(y)$, and thus $\phi'(\gamma_{P_1}(\phi^{-1}(x)) = \gamma_{P_2}(x) = \gamma_{P_2}(y) = \phi'(\gamma_{P_1}(\phi^{-1}(y))$. Because $\phi'$ is one-to-one, $\gamma_{P_1}(\phi^{-1}(x)) = \gamma_{P_1}(\phi^{-1}(y))$, and with Lemma \ref{lemma_gamma}(b) we get the equalities $ \{ \zeta(\phi^{-1}(x)) \} = $ $\zeta( \gamma_{P_1}(\phi^{-1}(x)) ) = \zeta( \gamma_{P_1}(\phi^{-1}(y)) ) = \{ \zeta(\phi^{-1}(y)) \}$. We conclude $\xi(x) = \zeta( \phi^{-1}(x) ) = \zeta( \phi^{-1}(y) ) = \xi(y)$, and $\xi$ is a homomorphism. Thus, $\Phi$ is onto. If $Q$ is an antichain and $\phi'$ not one-to-one, then there exist $x, y \in X_1$ with $\gamma_{P_1}(x) \not= \gamma_{P_1}(y)$ and $\gamma_{P_2}(\phi(x)) = \gamma_{P_2}(\phi(y))$. From $\gamma_{P_1}(x) \not= \gamma_{P_1}(y)$ we conclude $y \notin \gamma_{P_1}(x)$ (Corollary \ref{corr_gamma_def}). With $a, b \in Y, a \not= b$, we define $\zeta : X_1 \rightarrow Y $ by \begin{align*} \zeta(z) & \equiv \begin{cases} a, & \mytext{if} z \in \gamma_{P_1}(x); \\ b, & \mytext{if} z \in X_1 \setminus \gamma_{P_1}(x). \end{cases} \end{align*} For every $z \in \gamma_{P_1}(x)$, we have $ ( \mydownarrow z ) \cup ( \myuparrow z ) \subseteq \gamma_{P_1}(x)$. We conclude $z_1 \myparal z_2$ for all $z_1 \in \gamma_{P_1}(x)$, $z_2 \in X_1 \setminus \gamma_{P_1}(x)$, and $\zeta$ is a well-defined homomorphism with $\zeta(x) = a \not= b = \zeta(y)$. But for every homomorphism $\xi \in \H(P_2, Q)$, Lemma \ref{lemma_gamma}(b) enforces $\{ \xi( \phi(x) ) \} = \xi( \gamma_{P_2}( \phi(x))) = \xi( \gamma_{P_2}( \phi(y))) = \{ \xi( \phi(y) ) \}$, whence $\zeta \notin \Phi( \H(P_2, Q))$. \noindent (b) Let $\zeta \in \H( P_1, Q)$. We have to construct a $\xi \in \H(P_2, Q)$ with $\xi \circ \psi = \zeta$. We define for all $x \in X_2$ \begin{align*} \xi(x) & \equiv \sup \zeta( \myurbild{\psi}(\mydownarrow x ) ). \end{align*} It is easily seen that $\xi$ is an homomorphism with $\xi \circ \psi \geq \zeta$. Let $y \in X_1$. For every $x \in \myurbild{\psi}( \mydownarrow \psi(y))$, the inequality $\psi(x) \leq \psi(y)$ holds, and thus $x \leq y$ because $\psi$ is an embedding. In consequence, $(\xi \circ \psi)(y) = \sup \zeta( \myurbild{\psi} (\mydownarrow \psi(y) ) ) \leq \zeta(y)$. Hence $\xi \circ \psi = \zeta$, and $\Psi$ is onto. The case $Q \simeq A_1$ is trivial, and $\Psi$ is an isomorphism, if $\psi$ is an isomorphism. Let $Q \not\simeq A_1$ and let $a, b \in Y$ with $a \not= b$. With $c \equiv \inf \{ a, b \}$, $d \equiv \sup \{ a, b \}$, we have $c < d$. If $\psi$ is not onto, then there exists a $x_0 \in X_2 \setminus \psi( X_1 )$. Now we define two mappings $\xi_1, \xi_2 : X_2 \rightarrow Y$ by setting \begin{align*} \xi_1(x) & \equiv \begin{cases} c, & \mytext{if} x \in \mydownarrow x_0; \\ d, & \mytext{if} x \in X_2 \setminus \mydownarrow x_0; \end{cases} \\ \xi_2(x) & \equiv \begin{cases} c, & \mytext{if} x \in ( \mydownarrow x_0 ) \setminus \{ x_0 \}; \\ d, & \mytext{if} x \in ( X_2 \setminus \mydownarrow x_0 ) \cup \{ x_0 \}. \end{cases} \end{align*} Then $\xi_1$ and $\xi_2$ are different elements of $\H( P_2, Q )$ with $\Psi(\xi_1) = \Psi(\xi_2)$. \EP In the proof of Lemma \ref{lemma_bijHom_Emb}(b) we have only used the existence of $\sup A$ for every $A \subseteq Y$, but this is equivalent to the completeness of the lattice $Q$ \cite[Thm.\ 2.31]{Davey_Priestley_2012}. The two following corollaries collect relations regarding exponential sums of downset sizes and exponential sums of interval sizes. In the proofs, Lemma \ref{lemma_bijHom_Emb}(b) can always be applied because $\DDQ$ is always a complete lattice. With respect to the ``$<$''-relations, the reader will remember that $\DDQ$ is never an antichain. In the following applications of Lemma \ref{lemma_bijHom_Emb}(a), the resulting homomorphism $\Phi$ is therefore never onto because the constructed homomorphism $\phi$ is not an isomorphism, and in the applications of Lemma \ref{lemma_bijHom_Emb}(b), $\Psi$ is never one-to-one because the respective $\psi$ is not an isomorphism. \begin{figure} \begin{center} \includegraphics{Abb_Dedekind_4_Proof1.eps} \caption{\label{figure_Proof_C1} Illustrations for the proof of Corollary \ref{corr_sumsDS}.} \end{center} \end{figure} \begin{corollary} \label{corr_sumsDS} Let $Q$ be a finite poset. Then for all $k \geq 1$ and $\ell \geq 1$ \begin{align} \dDQz & < \powersumoZ{3}, \label{sum_A2Q_leq_sum3} \\ \powersumoZ{k+\ell} & < \powersumkZ{\ell}{k} \; \leq \; \dDQk{k+\ell}, \label{sumkL_leq_sumLk} \\ \powersumkZ{1}{k} & < \powersumoZ{2k+1}, \label{sum_1k_2k1} \end{align} with ``$=$'' in the second inequality of \eqref{sumkL_leq_sumLk} iff $k = 1$. \end{corollary} \BP \eqref{sum_A2Q_leq_sum3}: In Figure \ref{figure_Proof_C1}(a), a bijective homomorphism from $\Lambda_4$ to $\D(A_2)$ is shown. Now the inequality follows with Lemma \ref{lemma_bijHom_Emb}(a) and \eqref{isom_DDQm}. \eqref{sumkL_leq_sumLk}: Figure \ref{figure_Proof_C1}(b) contains an embedding of $\Lambda_{k+2}$ in $ \Lambda_{k+1} \mytimes C_2 $. Lemma \ref{lemma_bijHom_Emb}(b) delivers $h( \Lambda_{k+2}, \DDQ ) < h( \Lambda_{k+1} \mytimes C_2, \DDQ )$, and $\H( \Lambda_{k+1} \mytimes C_2, \DDQ ) \simeq \H( \Lambda_{k+1}, \H( C_2, \DDQ ) )$ yields together with \eqref{isom_DDQm} the first inequality for $\ell = 1$. The first inequality with arbitrary $\ell$ follows by iteration. For $k > 1$, the first inequality delivers $\TpowersumkZ{\ell}{k} < \TpowersumkZ{k + \ell - 1}{ } = \dDQk{k+\ell}$ due to \eqref{formel_dDQe}. \eqref{sum_1k_2k1}: A bijective homomorphism from $\Lambda_{2k+2}$ to $\Lambda_{k+1} \mytimes C_2$ is easily constructed. With Lemma \ref{lemma_bijHom_Emb}(a) we get $h( \Lambda_{k+1} \mytimes C_2, \DDQ ) < h( \Lambda_{2k+2}, \DDQ )$, and the inequality follows as in the proof of \eqref{sumkL_leq_sumLk}. \EP In Table \ref{table_sum_Ldk}, values of $\sum_{ \mf{A} \in \DDk{n} } \delta(\mf{A})^k$ are shown for small $k$ and $n$. As it can be expected by looking at Figure \ref{figure_Proof_C1}(b) (used in the proof of \eqref{sumkL_leq_sumLk}), the difference between $\sum_{\mf{A} \in \DDk{n}} \delta(\mf{A})^{k+1}$ and $\sum_{\mf{A} \in \DDk{n+1}} \delta(\mf{A})^{k}$ is large in most cases. \begin{table} \begin{center} \begin{tabular}{| c | r | r | r | r | r |} \hline $k \setminus n $ & 0 & 1 & 2 & 3 & 4 \\ \hline \hline 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\\ \hline \end{tabular} \caption{\label{table_sum_Ldk} Values of $\sum_{ \mf{A} \in \DDk{n} } \delta(\mf{A})^k$.} \end{center} \end{table} \begin{figure} \begin{center} \includegraphics{Abb_Dedekind_5_Proof2.eps} \caption{\label{figure_Proof_C2} Illustrations for the proof of Corollary \ref{corr_sumsInt}.} \end{center} \end{figure} \begin{corollary} \label{corr_sumsInt} Let $Q$ be a finite poset. Then for all $k \geq 1$ \begin{align} \dDQk{2} & < \powersumIoZ{3} \; < \; \dDQk{3}, \label{dDQ2_SumI3_dDQ3} \\ \dDQk{3} & < \powersumIoZ{6} \; < \; \dDQk{4}, \label{dDQ3_SumI6_dDQ4} \\ \powersumoZ{k} & < \powersumIoZ{k} \; < \; \powersumoZ{k+1}. \label{dDQk_SumIk_dDQk1} \end{align} Furthermore, \begin{align} \powersumIkZ{1}{k-1} & < \powersumIoZ{2k}. \label{SumIk_SumI2k} \end{align} \end{corollary} \BP \eqref{dDQ2_SumI3_dDQ3}: Of course, $\D(A_2) \simeq M_4$ (the diamond) can be embedded in $M_5$. Lemma \ref{lemma_bijHom_Emb}(b) delivers $ h( \D(A_2), \DDQ) < h( M_5, \DDQ)$, and the first inequality follows with \eqref{isom_DDQm} and \eqref{powersum_I}. An embedding of $M_5$ into $\D(A_3)$ is shown in Figure \ref{figure_Proof_C2}(a) and the second inequality follows in the same way. \eqref{dDQ3_SumI6_dDQ4}: A bijective homomorphism from $M_8$ to $\D(A_3)$ (the cube) is trivial. Lemma \ref{lemma_bijHom_Emb}(a) yields $h( \D(A_3), \DDQ ) < h( M_8, \DDQ)$ and the first inequality follows with \eqref{isom_DDQm} and \eqref{powersum_I}. We embed $M_8$ into $\D(A_4)$ as shown in Figure \ref{figure_Proof_C2}(b), and the second inequality follows as in the proof of \eqref{dDQ2_SumI3_dDQ3}. \eqref{dDQk_SumIk_dDQk1}: The embedding of $\Lambda_{k+1}$ into $M_{k+2} \simeq A_1 \oplus \Lambda_{k+1}$ is trivial and a bijective homomorphism from $\Lambda_{k+2}$ to $M_{k+2}$ is easily constructed. Now the inequalities follow with Lemma \ref{lemma_bijHom_Emb} and the equations used so far in this proof. (The first inequality can also directly be seen by $\delta(\mf{A}) = \iota[\emptyset, \mf{A}]$.) \eqref{SumIk_SumI2k}: Figure \ref{figure_Proof_C2}(c) shows a bijective homomorphism from $M_{2k+2}$ to $M_{k+1} \mytimes C_2$. Now apply Lemma \ref{lemma_bijHom_Emb}(a) and the respective equations. \EP \subsection{Averages} \label{subsec_Averages} The equalities and inequalities proven in the previous sections give raise to the quick calculation of averages. As \eqref{formel_dDQe} and \eqref{formel_dDQz} show: \begin{align*} \frac{1}{\dDQ} \powersumoZ{} & = \frac{\dDQe}{\dDQ} \; \stackrel{\eqref{ungl_1_2}}{<} \; \dDQ, \\ \frac{1}{\dDQe} \powersumIoZ{2} & = \frac{\dDQz}{\dDQe}, \end{align*} which are the average size of $\mydownarrow \mf{A}$ over all $\mf{A} \in \DDQ$ and the average size of $[ \mf{B}, \mf{A} ]^2 $ over all non-empty intervals $[ \mf{B}, \mf{A} ] \subseteq \DDQ$. Also, inequality \eqref{ungl_3_2} has an interpretation with respect to an average. Using \eqref{formel_dDQe} we get \begin{align*} \frac{1}{\dDQ^2} \sum_{ (\mf{A}, \mf{B}) \in \DDQ^2 } \delta(\mf{A}) \cdot \delta(\mf{B}) & = \left( \frac{\dDQe}{\dDQ} \right)^2 \quad > \quad \dDQ. \end{align*} The average of the the product $\delta(\mf{A}) \cdot \delta(\mf{B})$ of arbitrary elements $\mf{A}, \mf{B} \in \DDQ$ is therefore always larger than $\dDQ$. The averages are shown in Table \ref{table_averages} for $Q = A_n$. \begin{table} \begin{center} \begin{tabular}{| c | r | r | r |} \hline $n$ & $ d^2(A_n) $ & $\frac{1}{d^2(A_n)} \displaystyle \sum_{\mf{A} \in \D^2(A_n)} \delta(\mf{A})$ & $\frac{1}{d^2(A_n)^2} \displaystyle \sum_{ (\mf{A}, \mf{B}) \in \D^2(A_n)^2 } \delta(\mf{A}) \cdot \delta(\mf{B})$ \\ \hline \hline 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 \\ \hline \end{tabular} \caption{\label{table_averages} Averages of downset sizes and products of downset sizes.} \end{center} \end{table} \section{Computational time of algorithms for the calculation of Dedekind numbers} \label{sec_calculation} \subsection{Algorithms} \label{subsec_RecForm} The calculation of $\dDQk{m}$ 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 \eqref{isom_DDQm} in the form $\DDQk{m} \simeq \H( \D(A_\ell), \DDQk{m-\ell})$ for some $0 \leq \ell \leq m$. We call $\ell$ the {\em level} of the algorithm. The outermost algorithm runs over the set $\DDQk{m-\ell}$. Therefore, it must construct $\DDQk{m-\ell}$ or to refer to a model of it, which has to be created in advance \cite{Berman_Koehler_1976, Fidytek_etal_2001, Lunnon_1971, Markowsky_1989, Shmulevich_etal_1995, Wiedemann_1991, Yusun_2011}. Algorithms for the calculation of $\dDQk{m}$ in literature focus on the case $Q = A_n$, but we also retain the general notation $\dDQk{m}$ in this section. Even if it has been noticed that a nested algorithm can be written for all values of $m$ \cite{Markowsky_1989, Shmulevich_etal_1995}, 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\textsuperscript{th} century which may be due to the remarks of Lunnon \cite{Lunnon_1971} and Markowsky \cite{Markowsky_1989}, cf.\ \cite{Shmulevich_etal_1995}.) In what follows, we deal with the calculation of $\dDQk{4}$. The descriptions of the level-3-algorithm \eqref{alg_L3} and the level-4-algorithm \eqref{alg_L4} provide a scheme how to construct algorithms for levels higher than 4. For small posets $Q$, $\DDQk{4}$ can be directly constructed and its elements can simply be counted. Formally we can describe this approach as a level-0-algorithm \cite{Church_1940, Lunnon_1971} \begin{align} \dDQk{4} & = \sum_{\mf{A} \in \DDQk{4} } 1. \label{alg_L0} \end{align} A level-1-algorithm has already been presented in Section \ref{subsec_sums} in formula \eqref{formel_dDQe}. It is mentioned or used in many publications \cite{Berman_Koehler_1976, Fidytek_etal_2001, Lunnon_1971, Markowsky_1989, Riviere_1968, Yusun_2011}: \begin{align} \dDQk{4} & = \powersumkZ{3}{} \label{alg_L1} \end{align} Fidytek et al.\ \cite{Fidytek_etal_2001} realized the algorithm in the form \begin{align} \dDQk{4} & = \sum_{ (\mf{A}, \mf{B}) \in \DDQk{3}^2} \zeta( \mf{B}, \mf{A}), \label{alg_L1_Fid} \end{align} where $\zeta$ is the zeta-function with $\zeta( \mf{B}, \mf{A}) = 1$ for $\mf{B} \subseteq \mf{A}$ 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 \cite{Berman_Koehler_1976, Lunnon_1971, Markowsky_1989, Wiedemann_1991, Yusun_2011}. It is in general notated as \begin{align} \dDQk{4} & = \sum_{ (\mf{A}, \mf{B}) \in \DDQk{2}^2} \# \mydownarrow ( \mf{A} \cap \mf{B} ) \cdot \# \myuparrow ( \mf{A} \cup \mf{B} ). \label{alg_L2_BK} \end{align} The summation runs over the images of the left and right corner of $M_4 \simeq \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 \eqref{alg_L2_BK}. The second variant is used by Fidytek et al.\ \cite{Fidytek_etal_2001}: \begin{align} \dDQk{4} & = \sum_{ ( \mf{A}, \mf{B} ) \in \DDQk{2}^2 } \iota[ \mf{B}, \mf{A} ]^2 . \label{alg_L2_Fid1} \end{align} 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 \eqref{alg_L2_Fid1} becomes visible if we write it as \begin{align} \dDQk{4} & = \powersumIkZ{2}{2}. \label{alg_L2_Fid2} \end{align} In \eqref{alg_L2_Fid2} the summation runs over $\TpowersumkZ{2}{} \stackrel{\eqref{formel_dDQe})}{=} \dDQk{3}$ terms, whereas in \eqref{alg_L2_BK} and \eqref{alg_L2_Fid1} the number of terms is $\dDQk{2}^2 \stackrel{\eqref{ungl_1_2}}{>} \dDQk{3}$. Algorithm \eqref{alg_L2_Fid2} therefore provides an algorithmic benefit --- supposing that it is possible to step easily through $\mydownarrow \mf{A}$ for every $\mf{A} \in \DDQk{2}$. And the benefit will be large for sufficiently rich posets $Q$, as our considerations at the end of Section \ref{subsec_powers} and Table \ref{table_noofIntEn_DAk} in Section \ref{subsec_effort} 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): \begin{align} \DDQk{4} & = \sum_{\mf{A} \in \DDQk{1}} \sum_{( \mf{C}_{1}, \mf{C}_{2}, \mf{C}_{3}) \in ( \mydownarrow \mf{A} )^3} f(\mf{A}, \mf{C}_{1}, \mf{C}_{2}, \mf{C}_{3} ) \label{alg_L3} \end{align} with \begin{align*} f(\mf{A}, \mf{C}_{1}, \mf{C}_{2}, \mf{C}_{3} ) & \equiv \,\, \iota[ \mf{C}_{1} \cup \mf{C}_{2}, \mf{A} ] \cdot \iota[ \mf{C}_{1} \cup \mf{C}_{3}, \mf{A} ] \\ & \quad \cdot \iota[ \mf{C}_{2} \cup \mf{C}_{3}, \mf{A} ] \cdot \delta( \mf{C}_{1} \cap \mf{C}_{2} \cap \mf{C}_{3} ). \end{align*} The algorithm uses the isomorphism $\DDQk{4} \simeq \H( \D(A_3), \DDQk{1})$ as illustrated in Figure \ref{figure_Alg3}. Once $\mf{A} \in \DDQk{1}$ and $( \mf{C}_1, \mf{C}_2, \mf{C}_3 ) \in ( \mydownarrow \mf{A} )^3 $ have been selected, $ \mf{B}_{12} \in [ \mf{C}_1 \cup \mf{C}_2, \mf{A} ]$, $ \mf{B}_{13} \in [ \mf{C}_1 \cup \mf{C}_3, \mf{A} ]$, $ \mf{B}_{23} \in [ \mf{C}_2 \cup \mf{C}_3, \mf{A} ]$, and $ \mf{D}_{123} \in \mydownarrow ( \mf{C}_1 \cap \mf{C}_2 \cap \mf{C}_3 )$ can independently be selected. \begin{figure} \begin{center} \includegraphics{Abb_Dedekind_6_Alg_L3.eps} \caption{\label{figure_Alg3} Illustration of algorithm \eqref{alg_L3}.} \end{center} \end{figure} Fidytek et al.\ \cite{Fidytek_etal_2001} use a level-4-algorithm for the calculation of $\dDk{7}$ and $\dDk{8}$. With the notation $\vec{\mf{C}}$ for $( \mf{C}_1, \ldots, \mf{C}_6 ) \in \DDQ^6$ the algorithm is \begin{align} \DDQk{4} & = \sum_{\vec{\mf{C}} \in \DDQ^6 } \left( \sum_{ \mf{B} \leq \inf \mysetdescr{ \mf{C}_i }{ i \in \myNk{6}}} g^-( \mf{B}, \vec{\mf{C}} ) \right) \cdot \left( \sum_{ \mf{A} \geq \sup \mysetdescr{ \mf{C}_i }{ i \in \myNk{6}}} g^+( \vec{\mf{C}}, \mf{A}) \right) \label{alg_L4} \end{align} with \begin{align*} g^-(\mf{B}, \vec{\mf{C}}) & \equiv \,\, \iota[ \mf{B}, \mf{C}_1 \cap \mf{C}_2 \cap \mf{C}_3 ] \cdot \iota[ \mf{B}, \mf{C}_1 \cap \mf{C}_4 \cap \mf{C}_5 ] \\ & \quad \cdot \iota[ \mf{B}, \mf{C}_2 \cap \mf{C}_4 \cap \mf{C}_6 ] \cdot \iota[ \mf{B}, \mf{C}_3 \cap \mf{C}_5 \cap \mf{C}_6 ], \\ g^+(\vec{\mf{C}}, \mf{A}) & \equiv \,\, \iota[ \mf{C}_1 \cup \mf{C}_2 \cup \mf{C}_4, \mf{A} ] \cdot \iota[ \mf{C}_1 \cup \mf{C}_3 \cup \mf{C}_5, \mf{A} ] \\ & \quad \cdot \iota[ \mf{C}_2 \cup \mf{C}_3 \cup \mf{C}_6, \mf{A} ] \cdot \iota[ \mf{C}_4 \cup \mf{C}_5 \cup \mf{C}_6, \mf{A} ]. \end{align*} The six elements of the downset-tuple $\vec{\mf{C}} \in \DDQ^6 $ are the images of the six-element antichain in the middle of $\D(A_4)$ (encircled in Figure \ref{figure_Proof_C2}(b) on the right), $\mf{A}$ and $\mf{B}$ are the images of 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^+$. \subsection{Computational time} \label{subsec_effort} \begin{table} \begin{center} \begin{tabular}{| c | c | l |} \hline Level & Algorithm & $\#$ Calls \\ \hline \hline 0 & \eqref{alg_L0} & $\dDQk{4}$ \\ \hline 1 & \eqref{alg_L1} & $\dDQk{3}$ \\ & \eqref{alg_L1_Fid} & $\dDQk{3}^2$ \\ \hline 2 & \eqref{alg_L2_BK} & $\dDQk{2}^2$ \\ & \eqref{alg_L2_Fid1} & $\dDQk{2}^2$ \\ & \eqref{alg_L2_Fid2} & $\dDQk{3}$ \\ \hline 3 & \eqref{alg_L3} & $ \powersumkZ{1}{3} $ \\ \hline 4 & \eqref{alg_L4} & $ \powersumIoZ{6} $ \\ \hline \end{tabular} \caption{\label{table_noofcalls} Number of calls of the innermost calculation formula.} \end{center} \end{table} Table \ref{table_noofcalls} shows the number of calls of the innermost calculation formula in the algorithms for the calculation of $\dDQk{4}$ described in Section \ref{subsec_RecForm} (for algorithm \eqref{alg_L4}, apply Lemma \ref{lemma_intervallpotenzen}). 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 \cite{Markowsky_1989} for the number of calls of a level-3-algorithm turns out to be quite pessimistic. Due to \eqref{ungl_1_2}, we have $\dDQk{3} < \dDQk{2}^2 < \dDQk{4}$. Furthermore, $\dDQk{3}$ is, according to \eqref{sum_A2Q_leq_sum3} and \eqref{dDQ3_SumI6_dDQ4}, less than $ \TpowersumkZ{1}{3}$ and $\TpowersumIoZ{6}$, and due to \eqref{sumkL_leq_sumLk} and \eqref{dDQ3_SumI6_dDQ4}, these two sums are both less than $\dDQk{4}$. Finally, $\dDQk{4} < \dDQk{3}^2$ according to \eqref{ungl_1_2}. Thus, we get the following ranking of the computational times of the algorithms: \begin{displaymath} \eqref{alg_L1} = \eqref{alg_L2_Fid2} \quad < \quad \eqref{alg_L2_BK} = \eqref{alg_L2_Fid1}, \eqref{alg_L3}, \eqref{alg_L4} \quad < \quad \eqref{alg_L0} \quad < \quad \eqref{alg_L1_Fid}. \end{displaymath} The results of Section \ref{sec_DDQk} tell us nothing about relations between the numbers of calls of \eqref{alg_L2_Fid1}, \eqref{alg_L3}, and \eqref{alg_L4}. 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 \ref{table_noofIntEn_DAk} for the calculation of $\dDk{4+n}$, $0 \leq n \leq 3$. \begin{table} \begin{center} \begin{tabular}{| c | | l | r | r | r | r |} \hline Algorithm & $\#$ Interval enumerations & $n = 0$ & 1 & 2 & 3 \\ \hline \hline \eqref{alg_L1}, \eqref{alg_L2_Fid2} & $d^2(A_{3+n})$ & 20 & 168 & 7581 & 7828354 \\ \hline \eqref{alg_L2_Fid1} & $d^2(A_{2+n})^2$ & 36 & 400 & 28224 & 57471561 \\ \hline \eqref{alg_L2_BK} & $2 \cdot d^2(A_{2+n})^2$ & 72 & 800 & 56448 & 114943122 \\ \hline \eqref{alg_L3} & $ \displaystyle 4 \cdot \sum_{ \mf{A} \in \D^2( A_{1+n} )} \delta(\mf{A})^3 $ &144 & 1616 & 115704 & 249924492 \\ \hline \eqref{alg_L4} & $ 4 \cdot \displaystyle \sum_{ \mf{A} \in \D^2( A_{n} )} \sum_{ \mf{B} \in \mydownarrow \mf{A} } \iota[ \mf{B}, \mf{A} ]^6 $ & 264 & 3440 & 341232 & 1155311364 \\ \hline \eqref{alg_L0} & $d^2(A_{4+n})$ & 168 & 7581 & 7828354 & 2414682040998 \\ \hline \eqref{alg_L1_Fid} & $d^2(A_{3+n})^2$ & 400 & 28224 & 57471561 & 61283126349316 \\ \hline \end{tabular} \caption{\label{table_noofIntEn_DAk} Number of interval enumerations for the calculation of $d^2(A_{4+n})$.} \end{center} \end{table} Some authors calculate parameters in a pre-computational step before the main computation of the Dedekind number itself. Lunnon \cite{Lunnon_1971} calculates and saves $\# \mydownarrow \mf{A}$ and $\# \myuparrow \mf{A}$ for every $\mf{A} \in \DDk{2 + n}$ in advance, and it pays off: in the pre-computation, he invests $2 \cdot \dDk{2 + n}$ enumerations of intervals, causing an exchange of $2 \cdot \dDk{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 $\dDk{7}$ with the algorithms \eqref{alg_L2_Fid1} and \eqref{alg_L4}, Fidytek et al.\ \cite{Fidytek_etal_2001} calculate $\iota[ \mf{B}, \mf{A} ]$ in advance for every $\mf{A}, \mf{B} \in \DDk{7-\ell}$ by calculating the square of the incidence matrix of $\DDk{7-\ell}$. 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 \cite{Church_1940}, the numerous symmetries of $\DDQk{4-\ell}$ 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 $\DDQk{4-\ell}$, and for each representative the number of constructed homomorphisms in $\H( \D(A_\ell), \DDQk{4-\ell})$ is multiplied with the number of the isomorphic copies of the representative in $\DDQk{4-\ell}$. Using the orbit-stabilizer theorem, this number can be calculated without evaluating $\DDQk{4-\ell}$ \cite{Church_1940, Lunnon_1971, Markowsky_1989, Wiedemann_1991}. Additionally, Lunnon \cite{Lunnon_1971} exploits duality. Exploiting the symmetries makes the programming work quite demanding \cite{Markowsky_1989,Wiedemann_1991}, but it pays off: the comparison of the computational times of the calculation of $\dDk{7}$ by means of the level-2-algorithm \eqref{alg_L2_BK} with and without exploitation of symmetries done by Markowsky \cite{Markowsky_1989} shows a speed-up factor around 34 (main computation only). But of course, the pre-computational step to create a list of non-isomorphic elements of $\DDk{m-\ell}$ is time consuming \cite{Markowsky_1989,Wiedemann_1991}. Fidytek et al.\ \cite{Fidytek_etal_2001} 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 \eqref{alg_L2_BK}, even if none of the authors has mentioned it. For the calculation of $\dDQk{m}$, a model of $\DDQk{m-\ell}$ has to be created, stored, and managed. The larger the value of $\ell$, the smaller the model will be. For the calculation of $\dDk{7}$, Church \cite{Church_1965} had to use a memory saving model of $\DDk{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 \cite{Fidytek_etal_2001, Markowsky_1989, Shmulevich_etal_1995}. In the calculation of $\dDQk{m}$, the model of $\DDQk{m-\ell}$ is extremely frequently evaluated. Here, the art of creating suitable data structures and efficient algorithms for their evaluation plays a crucial role \cite{Shmulevich_etal_1995}; the structure used by Church \cite{Church_1965} provides both, memory savings {\em and} quick model evaluation. The differences in the numbers of calls between the three level-2-algorithms \eqref{alg_L2_BK}, \eqref{alg_L2_Fid1}, and \eqref{alg_L2_Fid2} emphasize the critical importance of quick evaluation algorithms. For models allowing an effective evaluation of $\mydownarrow \mf{A}$, we get the quicker algorithm \eqref{alg_L2_Fid2}. Otherwise we work with \eqref{alg_L2_BK} or \eqref{alg_L2_Fid1}. (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.\ \cite{Fidytek_etal_2001} calculated $\dDk{7}$ with the algorithms \eqref{alg_L1_Fid}, \eqref{alg_L2_Fid1}, and \eqref{alg_L4} on the same computer system. \eqref{alg_L4} was clearly the fastest algorithm (3 seconds), followed by \eqref{alg_L2_Fid1} (30 minutes), whereas \eqref{alg_L1_Fid} was definitely the slowest one (estimated 19 months). The inequalities between the numbers of calls and the figures in Table \ref{table_noofIntEn_DAk} show that the low performance of \eqref{alg_L1_Fid} had to be expected, but the empirical calculation times of \eqref{alg_L2_Fid1} and \eqref{alg_L4} are clearly the other way around than the figures in Table \ref{table_noofIntEn_DAk}. However, the measured calculation times include both, the pre-calculation {\em and} the main calculation, of which the former one is more time consuming for \eqref{alg_L2_Fid1}, and the latter one for \eqref{alg_L4}. Additionally, the lower effort for handling the model is in favor of the level-4-algorithm. Under these aspects, the level-3-algorithm \eqref{alg_L3} will show advantages and drawbacks in the calculation of $\DDQk{4}$. The model of $\DDQk{1}$ 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 \eqref{alg_L3} look better than for the level-4-algorithm \eqref{alg_L4}. Thus, \eqref{alg_L3} 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))$. \section{Appendix} \label{sec_appendix} \includegraphics{Abb_Dedekind_A1_A4.eps} 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., $\mf{A}$ and $ \left( \D(A_4) \setminus \mf{A} \right)^\partial$. The last four downsets are self-dual, i.e., $\mf{A} \simeq \left( \D(A_4) \setminus \mf{A} \right)^\partial$. \begin{thebibliography}{xx} \bibitem{Arocha_1982} J. L. Arocha, The number of antichains of the length 5 and 6, {\em VINITI 06.04.82. Reg. {\#}1631-82 Dep.} (1982). In Russian. \bibitem{Bakoev_2012} V. Bakoev, One more way for counting monotone Boolean functions, in {\em Thirteenth International Workshop on Algebraic and Combinatorial Coding Theory}, Pomorie, Bulgaria (2012), pp.\ 47--52. \bibitem{Berman_Koehler_1976} J. Berman and P. K\"{o}hler, Cardinalities of finite distributive lattices, {\em Mitteilungen aus dem mathem. Seminar Gie{\ss}en} {\bf 121} (1976), 103--124. \bibitem{Birkhoff_1967} G. Birkhoff, {\em Lattice Theory}, Proc. Amer. Math. Soc. Coll. Publ. {\bf 25}, 3\textsuperscript{rd} ed., 1967. \bibitem{Carroll_etal_2009} T. Carroll, J. Cooper, and P. Tetali, Counting antichains and linear extensions in generalizations of the Boolean lattice, preprint, 2009. Available at \url{https://people.math.gatech.edu/~tetali/PUBLIS/CCT.pdf}. \bibitem{Church_1940} R. Church, Numerical analysis of certain free distributive structures, {\em Duke Math. J.} {\bf 6} (1940), 732--734. \bibitem{Church_1965} R. Church, Enumeration by rank of the elements of the free distributive lattice with 7 generators, {\em Notices Amer. Math. Soc.} {\bf 12} (1965), 724. \bibitem{Cvetkovic_1972} D. M. Cvetkovi\'{c}, The number of antichains of finite power sets, {\em Publications de l'Institut Math\'{e}matique, Nouvelle s\'{e}rie} {\bf 13} (1972), 5--9. \bibitem{Davey_Priestley_2012} B. A. Davey and H. A. Priestley, {\em Introduction to Lattices and Order}, Cambridge University Press, 2\textsuperscript{nd} ed., 7\textsuperscript{th} printing (2012). \bibitem{Dedekind_1897} R. Dedekind, \"{U}ber Zerlegungen von Zahlen durch ihre gr\"{o}ssten gemeinsamen Theiler, {\em Festschrift Hoch. Braunschweig u. ges. Werke II} (1897), 103--148. \bibitem{Fidytek_etal_2001} R. Fidytek, A. W. Mostowski, R. Somla, and A. Szepietowski, Algorithms counting monotone Boolean functions, {\em Inform. Process. Lett.} {\bf 79} (2001), 203--209. \bibitem{Gilbert_1954} E. N. Gilbert, Lattice theoretic properties of frontal switching functions, {\em J. Math. Phys.} {\bf 33} (1954), 57--67. \bibitem{Hansel_1966} G. Hansel, Sur le nombre des fonctions bool{\'e}ennes monotones de $n$ variables, {\em C. R. Acad. Sci. Paris} {\bf 262} (1966), 1088--1090. \bibitem{Kahn_2002} J. Kahn, Entropy, independent sets and antichains, a new approach to Dedekind's problem, {\em Proc. Amer. Math. Soc.} {\bf 130} (2002), 371--378. \bibitem{Kilibarda_Jovovic_2003} G. Kilibarda and V. Jovovi\'{c}, On the number of monotone Boolean functions with fixed number of lower units, {\em Intellektualnye sistemy} {\bf 7} (2003), 193--217. In Russian. \bibitem{Kisielewicz_1988} A. Kisielewicz, A solution of Dedekind's problem on the number of isotone Boolean functions, {\em J. Reine Angew. Math.} {\bf 386} (1988), 139--144. \bibitem{Kleitman_1969_2} D. Kleitman, On Dedekind's problem: the number of monotone Boolean functions, {\em Proc. Amer. Math. Soc.} {\bf 21} (1969), 677--682. \bibitem{Kleitman_Markowsky_1975} D. Kleitman and G. Markowsky, On Dedekind's problem: The number of isotone Boolean functions II, {\em Trans. Amer. Math. Soc.} {\bf 213} (1975), 373--390. \bibitem{Korshunov_1981} A. D. Korshunov, The number of monotone Boolean functions, {\em Problemy Kibernet.} {\bf 38} (1981), 5--108. In Russian. \bibitem{Lunnon_1971} F. Lunnon, The IU function: The size of a free distributive lattice, in D. J. A. Welsh, ed., {\em Combinatorial Mathematics and its Applications}, Academic Press, 1971, pp.\ 173--181. \bibitem{Markowsky_1989} G. Markowsky, Enumerating free distributive lattices, Technical Report 89-10, Computer Science Department, University of Maine, December 1989. Available at \url{https://tinyurl.com/yd3pep2h}. \bibitem{Riviere_1968} N. M. Riviere, Recursive formulas on free distributive lattices, {\em J. Combin. Theory} {\bf 5} (1968), 229--234. \bibitem{Pippenger_1999} N. Pippenger, Entropy and enumeration of Boolean functions, {\em IEEE Trans. Inform. Theory} {\bf 45} (1999), 2096--2100. \bibitem{Sapozhenko_1989} A. A. Sapozhenko, The number of antichains in ranked partially ordered sets, {\em Diskr. Mat.} {\bf 1} (1989), 74--93. In Russian; English translation in {\em Discr. Math. Appl.} {\bf 1} (1991), 35--58. \bibitem{Shmulevich_etal_1995} I. Shmulevich, T. M. Sellke, M. Gabbouj, and E. J. Coyle, Stack filters and free distributive lattices, in {\em Proceedings of 1995 IEEE Workshop on Nonlinear Signal Processing}, Halkidiki, Greece, 1995, pp.\ 927--930. \bibitem{Sloane_DB} N. J. A. Sloane, {\em On-line Encyclopedia of Integer Sequences}, The OEIS Foundation, available at \url{https://oeis.org/}. \bibitem{Ward_1946} M. Ward, Note on the order of the free distributive lattice, {\em Bull. Amer. Math. Soc.} {\bf 52} (1946), 423. \bibitem{Wiedemann_1991} D. Wiedemann, A computation of the eighth Dedekind number, {\em Order} {\bf 8} (1991), 5--6. \bibitem{Yusun_2011} T. J. Yusun, {\em Dedekind Numbers and Related Sequences}. Master's Thesis, Simon Fraser University, Vancouver, BC, Canada, 2011. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 06A07; Secondary 06A06, 06A11. \noindent \emph{Keywords: } poset, downset, antichain, Dedekind number. \bigskip \hrule \bigskip \noindent (Concerned with sequence \seqnum{A000372}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received January 20 2018; revised versions received May 1 2018; May 2 2018. Published in {\it Journal of Integer Sequences}, May 8 2018. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document} .