# Function that cannot be computed by a Boolean circuit of size $2^n/2n$

Show that, for sufficiently large $n$, there is a function $f\colon\{0,1\}^n \to \{0,1\}$ that cannot be computed by a Boolean circuit with fan-in $2$ with $\frac{2^n}{2n}$ gates. Please give me a hint.

• What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question.
– D.W.
Apr 4, 2017 at 17:33

We need counting argument here. First thing is, there are $2^{2^{n}}$ many boolean functions, second thing is to count the number of boolean circuits for $k$ size boolean circuit. There are $2^{k^2} \times 3^{k}$ many boolean circuits of size $k$ (use adjacency matrix ). In your case value of $k =\frac{ 2^n}{2n}$, now you can easily check that
$$2^{2^{n}} > 2^{k^2} \times 3^{k}$$
So it means there are more number of functions than the total number of boolean circuits. There has to be at least one function that can not be computed by $k$ size circuit ( pigeonhole principle ). One thing to note here that I have proved the existence of such type of boolean circuit but to come up with such type of boolean circuit is quite hard.
Hint: Estimate from above the number of circuits with $2^n/2n$ gates, and compare it to the number of functions.