# Why do most 0/1 matrices need linear arithmetic circuits of size $\Omega(n^2/\log(n))$?

I am reading Alon et al.'s paper Linear Circuits over $$GF(2)$$ and I am having trouble seeing the counting argument showing that most matrices need a circuit of size $$\Omega(n^2/\log n)$$. This result is also mentioned in Chazelle's book at the start of chapter 6. He gives the following hint: "Compare the number of possible sequences mod 2 and the number of matrices." and I am not really sure how to use it.

I tried to reformulate a slightly weaker statement but could not prove it. Let us have a circuit with $$x_1, \dots, x_n$$ as inputs and each gate computes $$g_1 \pm g_2$$ where the $$g_i$$'s are two previously computed gates. The circuit computes $$Ax$$ if there are $$n$$ nodes with values $$Ax_i$$ for any $$x \in \mathbb{R}^n$$. The size of the circuit is the number of edges and the complexity of $$A$$ is the size of the smallest circuit computing $$A$$. The proposition I want to show is that most matrices of this form have complexity in $$\Omega(n^2/\log n)$$.

Here is my attempt at a counting argument. We count the number of circuits: If we order the gates topologically, we see that the gate at step $$k$$ needs to choose 2 gates $$g_1$$ and $$g_2$$ from the ones previously computed and 1 from 3 ways to combine them ($$g_1 + g_2$$, $$g_1 -g_2$$, $$g_2-g_1$$, this yields $$3\binom{k-1}{2}$$ possibilities. We can bound this by above with $$\frac{3k^2}{2}$$. Now, if a circuit has size $$s$$, then there is going to be that much choice for each $$k \in \{n+1, \dots, s\}$$ and the product of all these terms is bounded above by $$\frac{3^s}{2^s}(s!)^2 \leq \frac{3^s}{2^s}\left(\frac{s^s}{2^s}\right)^2$$. Putting $$s = n^2/\log n$$ yields at most $$\left(\frac{3n^4}{8\log^2n}\right)^{n^2/\log n}$$ possible circuits, but we can write the number of matrices as $$2^{n^2} = n^{n^2/\log n}$$, and we clearly see that this is smaller than the number of circuits we computed before. I know that I am clearly over counting because some circuits might compute the same matrices and I use non-tight bounds, but I don't see the actual argument that gives this result.

Thanks for any help.

• You are making the counting unnecessarily complicated, but anyway, take $s=\frac14n^2/\log n$ in the final step. Nov 16 '18 at 21:20