Intuition on Lupanov's Upper Bound on Circuit Size

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?
• $\alpha_n$ is $o(1)$ rather than an unbounded function such as $O(n/\log n)$. Perhaps you meant $O((\log n)/n)$? (I'm out of office atm and can't check the sources.) Commented Nov 15, 2023 at 6:53

• For every $$k$$, all $$2^{2^k}$$ functions on $$k$$ variables can be 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)$$
1. The construction matches the lower bound $$\frac{2^n}{n}$$, also due to Shannon (Theorem 1.14 in Jukna's book).