\(
\def\<#1>{\left<#1\right>}
\newcommand{\c}{\mathsf{c}}
\newcommand{\rk}[1]{\mathrm{rk}(#1)}
\)

## 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$