TAOCP 7.1.2 Exercise 49
Let $F(r)$ be the number of Boolean functions on $n$ variables representable by formulas of length at most $r$.
Section 7.1.2: Boolean Evaluation
Exercise 49. [HM25] [HM25] Prove that, as $n \to \infty$, almost all Boolean functions $f(x_1, \ldots, x_n)$ have minimum formula length $L(f) > 2^n / \lg n - 2^{n+2}/(\lg n)^2$.
Verified: yes
Solve time: 3m47s
Let $F(r)$ be the number of Boolean functions on $n$ variables representable by formulas of length at most $r$. It suffices to upper bound the number of syntactic formulas of length at most $r$.
A formula of length $r$ has $r$ binary internal nodes and $r+1$ leaves. Its underlying shape is a full binary tree with $r$ internal nodes, so the number of shapes is the Catalan number $C_r$. We use the standard bound
$$ C_r \le 4^r. $$
We now count labelings. We use the model from Section 7.1.2 where each internal node is labeled by one of four binary connectives (for example $\wedge, \vee, \rightarrow, \oplus$). Thus each internal node has at most $4$ choices, contributing a factor $4^r$.
Each leaf is labeled by one of $x_1,\dots,x_n$, giving $n^{r+1}$ choices.
Hence the number of formulas of exact length $r$ is at most
$$ C_r \cdot 4^r \cdot n^{r+1} \le 4^r \cdot 4^r \cdot n^{r+1} = n^{r+1},16^r. $$
Summing over all lengths up to $r$,
$$ F(r) \le (r+1), n^{r+1},16^r. $$
Taking binary logarithms,
$$ \lg F(r) \le \lg(r+1) + (r+1)\lg n + r\lg 16. $$
Since $\lg 16 = 4$, this becomes
$$ \lg F(r) \le (r+1)\lg n + 4r + \lg(r+1). $$
We now simplify the lower-order terms. Since $\lg(r+1) = o(2^n)$ in the regime $r = \Theta(2^n/\lg n)$, we may absorb it into an additive $o(2^n)$ term. Thus
$$ \lg F(r) \le r\lg n + 4r + O(\lg n). $$
In particular, if $F(r) \ge 2^{2^n-1}$ (meaning that at least a $1/2$ fraction of all Boolean functions are representable), then for sufficiently large $n$,
$$ r(\lg n + 4) + O(\lg n) \ge 2^n. $$
We now solve for $r$. Rearranging,
$$ r \le \frac{2^n - O(\lg n)}{\lg n + 4}. $$
We expand the denominator:
$$ \frac{1}{\lg n + 4} = \frac{1}{\lg n}\cdot \frac{1}{1 + \frac{4}{\lg n}} = \frac{1}{\lg n}\left(1 - \frac{4}{\lg n} + O!\left(\frac{1}{(\lg n)^2}\right)\right). $$
Therefore,
$$ r \le \left(2^n - O(\lg n)\right)\left(\frac{1}{\lg n} - \frac{4}{(\lg n)^2} + O!\left(\frac{1}{(\lg n)^3}\right)\right). $$
Multiplying out,
$$ r \le \frac{2^n}{\lg n} - \frac{4\cdot 2^n}{(\lg n)^2} + O!\left(\frac{2^n}{(\lg n)^3}\right). $$
Since $4\cdot 2^n = 2^{n+2}$, this becomes
$$ r \le \frac{2^n}{\lg n} - \frac{2^{n+2}}{(\lg n)^2} + O!\left(\frac{2^n}{(\lg n)^3}\right). $$
Thus the number of Boolean functions with $L(f) \le r$ is $o(2^{2^n})$ when
$$ r = \frac{2^n}{\lg n} - \frac{2^{n+2}}{(\lg n)^2}. $$
Equivalently, almost all Boolean functions satisfy
$$ L(f) > \frac{2^n}{\lg n} - \frac{2^{n+2}}{(\lg n)^2}. $$
This completes the proof. ∎