Implications of the $\Omega(\frac{2^n}{n})$ circuit lower bound being tight

Question

There is a basic result in circuit complexity that says:

There exists a language that cannot be solved with circuits of size $o(\frac{2^n}{n})$.

The argument is a simple counting argument on the number of boolean functions and the number of distinct circuits. See, for example, these lecture notes.

I believe it is unknown whether or not this bound is tight. That is, we don't know if the following statement is true:

Every language can be solved with circuits of size $O(\frac{2^n}{n})$.

If this statement were true, would it have any interesting implications for complexity theory?

Answer 1

This has been proved by Muller as early as 1956. Here is the construction. Let $k$ be a parameter. We first compute all possible functions on the first $k$ inputs in size $O(2^{2^k})$ (see below). We then construct a decision tree for the other $n-k$ variables, connecting it to the correct function on the remaining variables. This takes $O(2^{n-k})$ (see below), for a total of $O(2^{2^k}) + O(2^{n-k})$. Choosing $k = \log (n - \log n)$, we obtain the desired bound.

We compute all possible functions on $k$ inputs inductively. Let $Z_k$ be the size of a circuit computing all possible functions on $k$ inputs. There are two functions on zero inputs, so $Z_0 = 2$. Every function $f(x_1,\ldots,x_k)$ on $k$ inputs can be written as $x_k f(x_1,\ldots,x_{k-1},1) + \overline{x_k} f(x_1,\ldots,x_{k-1},0)$, so $Z_k = Z_{k-1} + 2^{2^k} \cdot O(1)$. The solution of this recurrence is $Z_k = O(2^{2^k})$.

In order to compute the decision tree, we use a similar construction: given a tree $T$ for the first $k-1$ variables, we can construct a tree for the first $k$ variables of the form $x_k T + \overline{x_k} T$. The recurrence we get is $W_k = 2W_{k-1} + O(1)$, whose solution is $W_k = O(2^k)$.