Lower bound on number of (different) circuits of given size?

Question

For circuits with $n$ input bits, we know that, for any function $s$, there are at most $O(s(n)^{s(n)}) = O(2^{s(n) \log s(n)})$ circuits with size at most $s(n)$.

Say two circuits $C_1$ and $C_2$ are different if the function they compute is different, that is, there is an $n$-bit string $x$ such that $C_1(x) \neq C_2(x)$. The $O(s(n)^{s(n)})$ bound above is an upper bound on the number of circuits of a given size. Is there a known lower bound on the number of different circuits with size at most $s(n)$ for different values of $s(n)$ (e.g., $s(n) \in \mathsf{poly}(n)$, $s(n) \in n^{\textsf{polylog}(n)}$, or $s(n) = 2^{n^\varepsilon}$)?

Clearly such a bound must be strictly smaller than the $O(s(n)^{s(n)})$ bound since there are pairs of circuits with different structures (and even different number of gates) and which nevertheless compute the same function (i.e., they are not "different" as defined above)—but how smaller can it be?

Answer 1

Let $1000 \leq s \leq 2^n/n$. Every function on $m$ bits can be computed by a circuit of size $O(2^m/m)$ (I believe that even the optimal constant is known). Choose a value of $m$ such that every function on $m$ bits can be computed by a circuit of size $s$, and furthermore $s = \Omega(2^m/m)$. Since there are $2^{2^m} = s^{\Omega(s)}$ different functions on $m$ bits, we see that your upper bound is quite tight.