Monotone arithmetic circuit complexity of elementary symmetric polynomials?

Question

The $k$-th elementary symmetric polynomial $S_k^n(x_1,\ldots,x_n)$ is the sum of all $\binom{n}{k}$ products of $k$ distinct variables. I am interested in the monotone arithmetic $(+,\times)$ circuit complexity of this polynomial. A simple dynamic programming algorithm (as well as Fig. 1 below) gives a $(+,\times)$ circuit with $O(kn)$ gates.

Question: Is a lower bound of $\Omega(kn)$ known?

A $(+,\times)$ circuit is skew if at least one of the two inputs of each product gate is a variable. Such a circuit is actually the same as switching-and-rectifying network (a directed acyclic graph with some edges labeled by variables; each s-t path gives the product of its labels, and the output is the sum of over all s-t paths). Already 40 years ago, Markov proved a surprisingly tight result: a minimal monotone arithmetic skew circuit for $S_k^n$ has exactly $k(n-k+1)$ product gates. The upper bound follows from Fig. 1:

But I haven't seen any attempt to prove such a lower bound for non-skew circuits. Is this just our "arrogance", or are there some inherent difficulties observed along the way?

P.S. I know that $\Omega(n\log n)$ gates are necessary to simultaneously compute all $S_1^n,\ldots,S_n^n$. This follows from the lower bound on the size of monotone boolean circuits sorting the 0-1 input; see page 158 of Ingo Wegener's book. The AKS sorting network also implies that $O(n\log n)$ gates are sufficient in this (boolean) case. Actually, Baur and Strassen have proved a tight bound $\Theta(n\log n)$ on the size of non-monotone arithmetic circuit for $S_{n/2}^n$. But what about monotone arithmetic circuits?

Answer 1

One challenge is that if you remove the "monotone" restriction, we do know how to compute such things efficiently. You can compute the value of all $S_0^n,\dots,S_n^n$ (evaluate all $n+1$ elementary symmetric polynomials) in $O(n \log^2 n)$ time, using FFT-based polynomial multiplication. So, proving a $\Omega(nk)$ lower bound in the monotone circuit model would require proving a $\Omega(n^2)$ lower bound on polynomial multiplication.

Here's how. Introduce a formal unknown $y$, and consider the polynomial

$$P(y) = \prod_{i=1}^n (1 + x_i y).$$

Note that since the $x_i$'s are known constants, this is a univariate polynomial with unknown $y$ and with degree $n$. Now you can note that the coefficient of $y^k$ in $P(y)$ is exactly $S_k^n$, so to evaluate all the $S_0^n,\dots,S_n^n$, it suffices to compute $P(y)$.

This makes it possible to compute $P(y)$ in $O(n \lg^2 n)$ time: build a balanced binary tree of polynomials with the $(1+x_i y)$'s at the leaves, and multiply the polynomials. Multiplying two polynomials of degree $d$ takes $O(d \lg d)$ time using FFT techniques, so we get the recurrence $T(n) = 2 T(n/2) + O(n \lg n)$, which solves to $T(n) = O(n \lg^2 n)$. For convenience, I am ignoring $\text{poly}(\lg \lg n)$ factors.

If you care about the case where $k$ is very small, you can compute $S_0^n,\dots,S_k^n$ in $O(n \lg^2 k)$ time using similar tricks, keeping in mind that you only care about $P(x) \bmod y^{k+1}$ (i.e., throwing away all terms of $y^{k+1}$ or higher powers of $y$).

Of course, the FFT uses subtraction, so naively it's not expressible in a monotone circuit. I don't know whether there's some other way to multiply polynomials efficiently with monotone arithmetic circuits, but any efficient monotone method for polynomial multiplication immediately leads to an algorithm for your problem as well. So, lower bounds on your problem require/imply lower bounds for polynomial multiplication.