On Dedekind’s problem: the number of isotone Boolean functions. II

It is shown that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="psi left-parenthesis n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>ψ<!-- ψ --></mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\psi (n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, the size of the free distributive lattice on <italic>n</italic> generators (which is the number of isotone Boolean functions on subsets of an <italic>n</italic> element set), satisfies <disp-formula content-type="math/mathml"> \[ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="psi left-parenthesis n right-parenthesis less-than-or-slanted-equals 2 Superscript left-parenthesis 1 plus upper O left-parenthesis log n slash n right-parenthesis right-parenthesis StartBinomialOrMatrix n Choose left-bracket n slash 2 right-bracket EndBinomialOrMatrix Baseline period"> <mml:semantics> <mml:mrow> <mml:mi>ψ<!-- ψ --></mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>⩽<!-- ⩽ --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>log</mml:mi> <mml:mspace width="thickmathspace" /> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo stretchy="false">)</mml:mo> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mtable rowspacing="4pt" columnspacing="1em"> <mml:mtr> <mml:mtd> <mml:mi>n</mml:mi> </mml:mtd> </mml:mtr> <mml:mtr> <mml:mtd> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">[</mml:mo> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> <mml:mo stretchy="false">]</mml:mo> </mml:mrow> </mml:mtd> </mml:mtr> </mml:mtable> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:msup> </mml:mrow> <mml:mo>.</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\psi (n) \leqslant {2^{(1 + O(\log \;n/n))\left ( {\begin {array}{*{20}{c}} n \\ {[n/2]} \\ \end {array} } \right )}}.</mml:annotation> </mml:semantics> </mml:math> \] </disp-formula> This result is an improvement by a factor <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartRoot n EndRoot"> <mml:semantics> <mml:msqrt> <mml:mi>n</mml:mi> </mml:msqrt> <mml:annotation encoding="application/x-tex">\sqrt n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> in the 0 term of a previous result of Kleitman. In the course of deriving the main result, we analyze thoroughly the techniques used here and earlier by Kleitman, and show that the result in this paper is “best possible” (up to constant) using these techniques.