Intuition on Lupanov's Upper Bound on Circuit Size

Question

The following result, by Lupanov, is a classic in the theory of Boolean function complexity:

Theorem: For every boolean function $f$ of $n$ variables: $$C(f) \leq (1 + \alpha_n)\frac{2^n}{n}, \text{ with } \alpha_n = O(\frac{n}{\log n})$$ where $C(f)$ denotes the minimum size of a fanin-two circuit computing $f.$

The original proof, which is reproduced e.g. in Jukna's book, uses a rather intricate circuit construction. I have several questions about this result:

1. Is there an easier way to see the looser upper bound of $O(2^n/n)$?
2. I'm having trouble seeing intuitively why we would expect such a bound, and such a construction, a priori. Why would you believe we can do better than a bound of $O(2^n)$ from the DNF?

Answer 1

1. Yes, there is a simpler construction, essentially due to Shannon.

• For every $k$, all $2^{2^k}$ functions on $k$ variables can implemented by a circuit of size $2^{2^k}$ (just take some implementation and then merge gates computing the same function).
• For every $k$, all $2^k$ elementary conjunctions can be implemented by a circuit of size $O(2^k)$ (implement recursively, halving the set of variables on each step)
• Every function $f(x_1, \dots, x_n)$ can be decomposed as $$f(x_1, \dots, x_n) = \bigvee_{a} f(x_1, \dots, x_k, a_{k+1}, \dots, a_n) x_{k + 1}^{a_{k + 1}} \dots x_n^{a_n}$$ where $x_i^1 = x_i$ and $x_i^0 = \neg{x_i}$.
• Thus, to implement any function, it is enough to implement all functions of $k$ variables (which will include all $f(x_1, \dots, x_k, a_{k+1}, \dots, a_n)$), all conjunction of $n-k$ variables $x_{k + 1}, \dots, x_n$, and $2^{n-k}$ disjunctions. In total, we have complexity $$2^{2^k} + O(2^{n - k}),$$ by taking $k = \log(n - \log n)$, we get $O(2^n/n)$

2. The construction matches the lower bound $\frac{2^n}{n}$, also due to Shannon (Theorem 1.14 in Jukna's book).