Computing the Elementary Symmetric Polynomials in Positive Characteristics

Ian Orzel · 2025

Read Computing the Elementary Symmetric Polynomials in Positive Characteristics by Ian Orzel (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-05009.txt.

Introduction

Elementary symmetric polynomials behave in new ways when arithmetic happens in positive characteristic. Ian Orzel studies formula size and forms for those polynomials in a solo 2025 computer science paper. He first extends earlier work by proving formula lower bounds for the degree-d elementary symmetric polynomial over such fields.

Orzel then shows two zero-characteristic results fail in positive characteristic. Some polynomials cannot be written as linear projections of the elementary symmetric ones. The gap comes with quantitative lower bounds. Others cannot be computed by certain shallow border circuits with small top fan-in. The proofs use the geometry of points where the polynomial and its derivatives vanish. Those vanishing points carry the key structural clue.

Catalog record

CREATORIan Orzel
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE63 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-05009

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Computing the Elementary Symmetric Polynomials in Positive Characteristics Ian Orzel Abstract We first extend the results of Chatterjee, Kumar, Shi, Volk (Computational Complexity 2022) by showing that the degree d d elementary symmetric polynomials in n n variables have formula lower bounds of Ω ⁡ ( d ⁡ ( n − d ) ) \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 1. 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 k such projections for a fixed k k ) and 2. There are polynomials that cannot be computed by border depth- 3 3 circuits of top fan-in k k , called Σ [ k ] ​ Π ​ Σ ¯ \overline{\Sigma^{[k]}\Pi\Sigma} , for k = o ⁡ ( n ) 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 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 d-2 and d − 1 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 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. 1 Introduction Given n independent variables x_{1},\ldots,x_{n} and a degree d\leq n , we define the elementary symmetric polynomial of degree d (over an arbitrary field \mathbb{F} of characteristic denoted by \operatorname{char}(\mathbb{F}) ) to be the sum of all degree d multilinear monomials in these indeterminants, i.e., e_{n}^{d}=\sum_{S\in{[n]\choose d}}\prod_{i\in S}x_{i}. This polynomial naturally appears in many problems, for instance, if we consider the product of affine, constant-free polynomials, we can express such a product by \prod_{i=1}^{n}(x_{i}+y)=\sum_{k=0}^{n}y^{n-k}e_{k}^{n}(x_{1},\ldots,x_{n}). (1) We say that these polynomials are symmetric because they are invariant under permutations of the variables, and we say that they are elementary because they are the basic building blocks of symmetric polynomials, namely, the set of symmetric polynomials can be written by \mathbb{F}[e_{0}^{n},\ldots,e_{n}^{n}] . We include more fundamental properties in the appendix, Section A . Motivation. In algebraic complexity, computation of the elementary symmetric polynomials appear very naturally in many contexts. Algebraically, we commonly define computation through algebraic circuits , which we model using acyclic directed graphs, where certain nodes represent operations, addition and multiplication, and other nodes represent inputs, which are given as independent variables and field constants. We can then restrict this to so-called algebraic formulas , which require that the underlying graph be a tree. We can then further restrict the depth of a tree and force layers to alternate in operations, creating, for example, depth-three \Sigma\Pi\Sigma formulas , where the root node is an addition node. We may further restrict this model to \Sigma^{[k]}\Pi\Sigma formulas , where the root node may only have at most k children. The earliest-known motivation for studying the complexity of the elementary symmetric polynomials came from boolean circuit complexity, where circuits compute boolean functions using a graph labeled with and-gates, or-gates, and not-gates. When considering boolean formulas of constant depth, it was shown in [ FSS84 ] that the majority function had super-polynomial lower bounds, where the majority function is given by \bigvee_{I\in{[n]\choose n/2}}\bigwedge_{i\in I}x_{i} . Clearly, e_{n,n/2} looks like an algebraic analogue of the majority function, so it was believed to be a good candidate for a polynomial that would have constant-depth formulas with super-polynomial lower bounds. Unfortunately, due to a construction of Ben-Or (see Theorem 3.1 of [ Shp02 ] ), e_{n,d} was shown to have \Sigma\Pi\Sigma formulas of size O(n^{2}) (but the problem of super-polynomial \Sigma\Pi\Sigma lower bounds has since been solved, see [ LST24 ] ). In [ SW01 ] and [ Shp02 ] , it was shown that this upper bound is tight for \Sigma\Pi\Sigma formulas of certain elementary symmetric polynomials over fields of characteristic zero. This was further extended in [ CKSV22 ] to be tight over general algebraic formulas, also over fields of characteristic zero. We further have that [ HY11 ] found super-polynomial lower bounds for certain elementary symmetric polynomials for homogeneous multilinear formulas, where each node computes a homogeneous multilinear polynomial (the result of which is independent of field characteristic). Another motivation was explored in [ LST24 ] and [ FLST24 ] , where we can view the computation of the elementary symmetric polynomials as naturally related to constant-depth arithmetic formulas. For example, we can consider \Sigma\Pi\Sigma formulas and explore how they can be converted into homogeneous \Sigma\Pi\Sigma formulas, where each node computes a homogeneous polynomial. One idea is to apply ( 1 ) to each product gate and then compute each resulting elementary symmetric polynomial using homogeneous circuits (for instance, we could use the upper bound of [ SW01 ] for homogeneous computation of e_{d}^{n} by \Pi\Sigma\Pi\Sigma of size n2^{O(\sqrt{d})} , but this only works for characteristic zero fields). This idea can be extended to work for deeper constant-depth circuits. In [ Shp02 ] , the elementary symmetric polynomials were used to define an algebraic computational model, which was called the symmetric model . It was defined by taking a series of linear polynomials L_{1},\ldots,L_{m}\in\mathbb{F}[x_{1},\ldots,x_{n}] and a degree d\leq m and defining the computation by e_{d}^{m}(L_{1},\ldots,L_{m}) . [ Shp02 ] then showed that the symmetric model is universal over fields of characteristic zero, meaning that it can compute any (homogeneous) polynomial. This was done using Fischer’s identity (see [ Fis94 ] and [ Shp02 ] ), which tells us that we can write any degree d homogeneous polynomial f\in\mathbb{F}[x_{1},\ldots,x_{n}] as f=L_{1}^{d}+\dots+L_{m}^{d} , for some linear polynomials L_{1},\ldots,L_{m}\in\mathbb{F}[x_{1},\ldots,x_{n}] , and it was then shown that polynomials written in this form can be expressed in the symmetric model. We observe that this only works over fields of characteristic zero, as there are many polynomials in positive characteristic that cannot be written in this way, as, for example, (x+y)^{p}=x^{p}+y^{p} when \operatorname{char}(\mathbb{F})=p . Then, in [ Kum20 ] , the results around the symmetric model were used to study the border “affine Chow rank” of a polynomial, where this name selected based on [ Dut25 ] . We say that the affine Chow rank of a polynomial f\in\mathbb{F}[x_{1},\ldots,x_{n}] is the smallest k such that f can be computed

Read the complete text