TAOCP 7.1.2 Exercise 46

Let $s=\lfloor 2^n/n\rfloor$.

taocpmathematicsalgorithmsvolume-4hm-medium

Section 7.1.2: Boolean Evaluation

Exercise 46. ▶ [HM21] Let $\alpha(n) = c(n, \lfloor 2^n/n \rfloor)/2^{2^n}$ be the fraction of $n$-variable Boolean functions $f(x_1, \ldots, x_n)$ for which $C(f) \le 2^n/n$. Prove that $\alpha(n) \to 0$ rapidly as $n \to \infty$.

Verified: no
Solve time: 4m59s

Let $s=\lfloor 2^n/n\rfloor$. We bound $c(n,s)$, the number of $n$-variable Boolean functions computable by circuits of size at most $s$, by counting circuits.

1. Encoding and counting circuits

Fix a standard finite basis of Boolean gates with bounded fan-in (as in TAOCP 7.1.2). Each circuit of size $s$ consists of $s$ gates, and gates are numbered in topological order.

For each gate:

  • choose its type from a fixed constant set of size $K$;
  • choose its inputs from among the $n$ variables and the outputs of previous gates.

At the $i$-th gate, there are at most $n+i \le n+s$ available sources for each input wire. Since fan-in is bounded by a constant (say at most 2), each gate has at most

$$ O\bigl((n+s)^2\bigr) $$

choices for its wiring, and $O(1)$ choices for its type. Hence there exists a constant $A>1$ such that the number of possibilities for each gate is at most

$$ A (n+s)^2. $$

Therefore,

$$ c(n,s) \le \bigl(A (n+s)^2\bigr)^s. $$

Taking binary logarithms,

$$ \log_2 c(n,s) \le s \log_2 A + 2s \log_2(n+s). $$

2. Substitute $s = \lfloor 2^n/n \rfloor$

We use $n+s \sim s$, so

$$ \log_2(n+s) = \log_2 s + O(1). $$

Now compute $s \log_2 s$:

$$ \log_2 s = \log_2\left(\frac{2^n}{n}(1+o(1))\right) = n - \log_2 n + O(1), $$

so

$$ s \log_2 s = \frac{2^n}{n}\bigl(n - \log_2 n + O(1)\bigr) = 2^n - \frac{2^n \log_2 n}{n} + O!\left(\frac{2^n}{n}\right). $$

Hence,

$$ 2s \log_2(n+s) = 2s \log_2 s + O(s) = 2\cdot 2^n - 2\frac{2^n \log_2 n}{n} + O!\left(\frac{2^n}{n}\right). $$

Adding the $s \log_2 A = O(2^n/n)$ term gives

$$ \log_2 c(n,s) \le 2\cdot 2^n - 2\frac{2^n \log_2 n}{n} + O!\left(\frac{2^n}{n}\right). $$

In particular,

$$ \log_2 c(n,s) \le 2\cdot 2^n - \Omega!\left(\frac{2^n \log n}{n}\right). $$

3. Compare with all Boolean functions

The total number of Boolean functions on $n$ variables is

$$ 2^{2^n}. $$

Thus

$$ \alpha(n) = \frac{c(n,s)}{2^{2^n}} \le \frac{2^{,2\cdot 2^n - \Omega(2^n \log n / n)}}{2^{2^n}} = 2^{,2^n - \Omega(2^n \log n / n)}. $$

Since the exponent is

$$ 2^n - \Omega!\left(\frac{2^n \log n}{n}\right) = -\Omega!\left(\frac{2^n \log n}{n}\right) + 2^n, $$

we rewrite the ratio directly as

$$ \alpha(n) \le 2^{-\Omega!\left(\frac{2^n \log n}{n}\right)}. $$

4. Conclusion

Because $\frac{2^n \log n}{n} \to \infty$, we obtain

$$ \alpha(n) \to 0 \quad \text{extremely rapidly, namely } \alpha(n)=2^{-\Omega(2^n \log n / n)}. $$

This completes the proof.