On the "circuit hierarchy" theorem

For a boolean function $f$, let $C(f)$ denote the minimum size of a DeMorgan circuit computing $f$. Thm. 1.19 in the book states that, for every $t=t(n)$ such that $n\leq t(n)\leq 2^n/4n$, there is a boolean function $f$ of $n$ variables such that $t< C(f)\leq 4t$.

In the proof, we were very "generous", we only combined known upper and lower bounds on the complexity of "most complex" functions. Actually, as Luca Trevisan observed here, much easier argument leads to much tighter hierarchy.

Theorem (Luca Trevisan): Let $0\leq t(n)\leq 2^n/2n$. Then there is a boolean function $f$ of $n$ variables such that $t(n)< C(f)\leq t(n)+n$.
Proof: Take a boolean function $g$ of $n$ variables which is not computable by circuits of size $2^n/2n$; by Shannon-Lupanov results we know that such functions exist. Let $g^{-1}(1)=\{a_1,\ldots,a_m\}$ be the set of inputs accepted by $g$. For $i=0,1,\ldots,m$, let $g_i$ be the boolean function which accepts exactly the inputs $a_1,\ldots,a_i$; hence, $g_0= 0$ and $g_m=g$. Having a circuit for $g_i$, we can obtain a circuit for $g_{i+1}$ by just accepting one additional vector $a_{i+1}$, So, $C(g_{i+1})\leq C(g_i)+n$. Since $C(g_0)=0$ and $C(g_m)=C(g)> 2^n/2n\geq t(n)$, there must be an index $i$ such that $C(g_i)\leq t(n)$ but $C(g_{i+1}) > t(n)$. But, as we just observed, $C(g_{i+1})\leq C(g_i)+n\leq t(n)+n$. Thus, the claim holds for $f=g_{i+1}$. $\Box$

Reference:

• [1] L. Trevisan's answer in StackExchange.

S. Jukna, March 2014