# Counting circuits with constraints

Please forgive me if this question is trivial, I couldn’t come up with an answer (nor finding one).

In order to show that there are boolean functions $$f : \{0,1\}^n \rightarrow \{0,1\}$$ which can be computed only using circuits of size $$\Omega(2^n/n)$$, we use a counting argument: there are at most $$O(2^{k \log k})$$ circuits of size $$k$$, and $$2^{2^n}$$ such functions.

Suppose that I am interested in counting circuits of size $$k$$ that compute different functions. The "simple" counting argument won't work since it may be possible that two "syntactically" different circuits actually compute the same function. In other words, I want to bound the size of the set: $$F = \{ f: \{0,1\}^n \rightarrow \{0,1\} | f \text{ can be computed using a circuit of size }k \}$$

Then $$|F| <$$ the number of circuits of size $$k$$ (since any circuit computes one function), but how can I bound $$|F|$$ from below? (i.e. $$x <|F|$$)

In order to bound the number of functions computed by circuits of size $$k$$, you have at least two options:
• Construct a large number of circuits of size $$k$$, which by construction compute different functions.
• Consider a natural probability distribution on circuits of size $$k$$, and estimate the probability that two random circuits compute the same function.
As an example, it is known that every function on $$m$$ variables can be computed by a circuit of size $$O(2^m/m)$$. By considering functions of the form $$f_1(x_1,\ldots,x_m) \lor \cdots \lor f_{n/m}(x_{n-m+1},\ldots,x_n)$$, this shows that there are at least $$(2^{2^m})^{n/m}$$ different functions computed by circuits of size $$k = O(n2^m/m^2)$$. In terms of $$k$$, the number of functions is roughly exponential in $$k\log k$$, for $$m \gg \log n$$.