Number of non-XOR gates needed to implement an n-bit boolean function

There are $2^{2^n}$ possible functions that have $n$ boolean inputs and a single boolean output. Some of these functions have very short boolean logic circuits. Some have longer circuits.

A classic result in circuit complexity is that, if you count the total number of gates needed to implement $f$, most $f$s take $\Theta(2^n/n)$ 2-to-1 boolean gates. I'm interested in a slightly different metric, where you can use as many XOR gates as you want but you don't count them (ditto for NOT gates, which are just a XOR with one input constant). So your circuit could have $n$ AND gates plus $2^n$ XOR gates, and I'd call that a circuit of non-XOR-size $n$.

I've figured out that it's possible to implement any $n$-input function $f$ using at most $2^{n/2+1}$ gates that aren't XOR or NOT. The strategy works by using $2^{n/2}$ AND gates (with XOR gates interspersed) to prepare a set of $2^{n/2}$ indicator bits that can be XOR'd together to make any function of $n/2$ bits. I then pretend the top $n/2$ bits of the input index register are "choosing" the sub-function to apply with the bottom $n/2$ bits, and use my indicator bits to prepare the $2^{n/2}$ possible sub-function outputs. I then use $2^{n/2}$ AND gates to mux out the desired sub-function output (selected by the top $n/2$ bits of the input index register).

I'm interested in knowing is it possible to do better than $2^{n/2+1}$ AND gates, or is that asymptotically optimal.

By counting circuits, $2^{n/2 + 1}$ appears to be close to asymptotically optimal.

Let $C_{n,k}$ be the number of distinct circuits with $n$ bits and $k$ AND gates.

We lower bound $C_{n,k}$ by noting that we need to choose $k$ such that there is at least as many possible circuits as possible functions, i.e. $2^{2^n} \leq C_{n,k}$.

We upper bound $C_{n,k}$ by noting that every AND gate takes as input a bit which may have had each initial input and each output of a previous AND gate and possibly the constant 1 XOR'd into it. For the first AND gate there are $n + 1$ bits that may or may not be xored into each input of rht AND gate. For the second AND gate there are $n + 2$ bits, for the third $n+3$, and so forth. Then there's $n+k+1$ choices for what to xor into our output bit. Thus $C_{n,k} \leq 4^{n+1} 4^{n+2} \ldots 4^{n+k} \cdot 2^{n+k+1}$.

Now we know $2^{2^n} \leq C_{n,k} \leq 4^{n+1} 4^{n+2} \ldots 4^{n+k} \cdot 2^{n+k+1}$. By omitting the $C_{n,k}$ in the center we get an inequality in terms of $k$ and $n$ that we can use to bound $k$ in terms of $n$ as follows:

$$\begin{align}
2^{2^n}
&\leq 4^{n+1} 4^{n+2} \ldots 4^{n+k} \cdot 2^{n+k+1}
\\
&= 2^{n+k+1} \prod_{i=1}^k 4^{n+i}
\\
&= 2^{n+k+1} 4^{\sum_{i=1}^k n+i}
\\
&= 2^{n+k+1} 4^{kn + k(k+1)/2}
\\
&= 2^{2kn + k^2 + 2k + n + 1}
\end{align}$$

Now we start manipulating both sides:

$$\begin{align}
2^{2^n} &\leq 2^{2kn + k^2 + 2k + n + 1}
\\
2^n &\leq 2kn + k^2 + 2k + n + 1
\\
0 &\leq k^2 + k(2n + 2) + (n + 1 - 2^n)
\end{align}$$

Finally, find the quadratic roots where the inequality switches, and focus down to the asymptotically dominant term of the positive root:

$$\begin{align}
k &= \frac{-2n -2 \pm \sqrt{(2n+2)^2 + 4 \cdot (2^n - n - 1)}}{2}
\\
&= -n - 1 \pm \sqrt{n^2 + 2n + 1 + 2^n - n - 1}
\\
&= -n - 1 \pm \sqrt{n^2 + n + 2^n}
\\
&\in \Omega \left(-n -\frac{1}{2} + \sqrt{n^2 + n + 2^n} \right)
\\
&= \Omega \left(\sqrt{2^n} \right)
\\
\end{align}$$

So it appears that $k$ must be asymptotically at least $\Omega(\sqrt{2^n})$ in order for there to be enough circuits to cover all of the possible functions.

StackExchange Computer Science Q#88444, answer score: 3