Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR25-128 | 9th February 2026 13:26

Computing the Elementary Symmetric Polynomials in Positive Characteristics

RSS-Feed




Revision #2
Authors: Ian Orzel
Accepted on: 9th February 2026 13:26
Downloads: 49
Keywords: 


Abstract:

We first extend the results of Chatterjee, Kumar, Shi, Volk (Computational Complexity 2022)
by showing that the degree $d$ elementary symmetric polynomials in $n$ variables have formula lower bounds of $\Omega(d(n-d))$ over fields of positive characteristic. Then, we show that the results of the universality of linear projections of elementary symmetric polynomials from Shpilka (Journal of Computer and System Sciences 2002) and of border fan-in two $\Sigma\Pi\Sigma$ circuits from Kumar (ACM Trans. Comput. Theory 2020) over zero characteristic fields do not extend to fields of positive characteristic. In particular, we show that
* There are polynomials that cannot be represented as linear projections of the elementary symmetric polynomials (in fact, we show linear lower bounds over the size of the sum of such linear projections) and
* There are polynomials that cannot be computed by border depth-$3$ circuits of top fan-in $k$, called $\overline{\Sigma^{[k]}\Pi\Sigma}$, for $k = o(n)$.

To prove the first result, we consider a geometric property of the elementary symmetric polynomials, namely, the set of all points in which the polynomial and all of its first-order partial derivatives vanish. It was previously shown that the dimension of this space was exactly $d-2$ for fields of zero characteristic.
We extend this to fields of positive characteristic by showing that this dimension must be between $d-2$ and $d-1$. In fact, we provide some criterion where it is $d-2$ and others where it is $d-1$.

Then, to consider the border top fan-in of linear projections of the elementary symmetric polynomials and border depth-$3$ circuits (sometimes called border affine Chow rank), we show that it is sufficient to consider the border top fan-in of the sum of such linear projections of the elementary symmetric polynomials. This is done by an explicit construction of a 'metapolynomial,' meaning that this result also applies in the border setting.


Revision #1 to TR25-128 | 9th September 2025 14:14

Computing the Elementary Symmetric Polynomials in Positive Characteristics





Revision #1
Authors: Ian Orzel
Accepted on: 9th September 2025 14:14
Downloads: 553
Keywords: 


Abstract:

We first extend the results of Chatterjee, Kumar, Shi, Volk (Computational Complexity 2022) by showing that the degree $d$ elementary symmetric polynomials in $n$ variables have formula lower bounds of $\Omega(d(n-d))$ over fields of positive characteristic. Then, we show that the results of the universality of the symmetric model from Shpilka (Journal of Computer and System Sciences 2002) and the results about border fan-in two $\Sigma\Pi\Sigma$ circuits from Kumar (ACM Trans. Comput. Theory 2020) over zero characteristic fields do not extend to fields of positive characteristic. In particular, we show that
* There are polynomials that cannot be represented as linear projections of the elementary symmetric polynomials (in fact, we show that they cannot be represented as the sum of $k$ such projections for a fixed $k$) and
* There are polynomials that cannot be computed by border depth-$3$ circuits of top fan-in $k$, called $\overline{\Sigma^{[k]}\Pi\Sigma}$, for $k = o(n)$.

To prove the first result, we consider a geometric property of the elementary symmetric polynomials, namely, the set of all points in which the polynomial and all of its first-order partial derivatives vanish. It was shown in Meckler, Zaimi and Limaye, Mittal, Pareek that the dimension of this space was exactly $d-2$ for fields of zero characteristic. We extend this to fields of positive characteristic by showing that this dimension must be between $d-2$ and $d-1$. In fact, we show this bound is tight, in the sense that there are (infinitely many) polynomials where each of these bounds is exact.

Then, to consider the border top fan-in of the symmetric model and depth-$3$ circuits (sometimes called border affine Chow rank), we show that it is sufficient to consider the border top fan-in of the sum of linear projections of the elementary symmetric polynomials. This is done by constructing an explicit metapolynomial to check the condition, meaning that this result also applies in the border setting.



Changes to previous version:

Added funding and fixed abstract.


Paper:

TR25-128 | 5th September 2025 13:38

Computing the Elementary Symmetric Polynomials in Positive Characteristics


Abstract:

We first extend the results of CKSV22 by showing that the degree $d$ elementary symmetric polynomials in $n$ variables have formula lower bounds of $\Omega(d(n-d))$ over fields of positive characteristic.
Then, we show that the results of the universality of the symmetric model from Shp02 and the results about border fan-in two $\Sigma\Pi\Sigma$ circuits from Kum20 over zero characteristic fields do not extend to fields of positive characteristic.
In particular, we show that
\begin{enumerate}
\item There are polynomials that cannot be represented as linear projections of the elementary symmetric polynomials (in fact, we show that they cannot be represented as the sum of $k$ such projections for a fixed $k$) and
\item There are polynomials that cannot be computed by border depth-$3$ circuits of top fan-in $k$, called $\overline{\Sigma^{[k]}\Pi\Sigma}$, for $k = o(n)$.
\end{enumerate}

To prove the first result, we consider a geometric property of the elementary symmetric polynomials, namely, the set of all points in which the polynomial and all of its first-order partial derivatives vanish.
It was shown in MZ17 and LMP19 that the dimension of this space was exactly $d-2$ for fields of zero characteristic.
We extend this to fields of positive characteristic by showing that this dimension must be between $d-2$ and $d-1$.
In fact, we show this bound is tight, in the sense that there are (infinitely many) polynomials where each of these bounds is exact.

Then, to consider the border top fan-in of the symmetric model and depth-$3$ circuits (sometimes called border affine Chow rank), we show that it is sufficient to consider the border top fan-in of the sum of linear projections of the elementary symmetric polynomials.
This is done by constructing an explicit metapolynomial to check the condition, meaning that this result also applies in the border setting.



ISSN 1433-8092 | Imprint