# On Closure Properties of Read-Once Oblivious Algebraic Branching Programs

Jules Armand, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen, Nutan

Limaye, Srikanth Srinivasan, Sébastien Tavenas

► To cite this version:

Jules Armand, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen, Nutan Limaye, Srikanth Srinivasan, et al.. On Closure Properties of Read-Once Oblivious Algebraic Branching Programs. 2025. [hal-05252464]

HAL Id: hal-05252464

https://hal.science/hal-05252464v1

Preprint submitted on 13 Sep 2025

**HAL** is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire **HAL**, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On Closure Properties of Read-Once Oblivious Algebraic Branching Programs

Jules Armand‡

Prateek Dwivedi*

jules.armand@univ-smb.fr

prdw@itu.dk

Magnus Rahbek Dalgaard Hansen*

Nutan Limaye*

Srikanth Srinivasan†

ramh@itu.dk

nuli@itu.dk

srsr@di.ku.dk

Sébastien Tavenas‡

sebastien.tavenas@univ-smb.fr

## Abstract

We investigate the closure properties of read-once oblivious Algebraic Branching Programs (roABPs) under various natural algebraic operations and prove the following.

* **Non-closure under factoring:** There is a sequence of explicit polynomials $(f_n(x_1, ..., x_n))_n$ that have poly($n$)-sized roABPs such that some irreducible factor of $f_n$ does not have roABPs of superpolynomial size in *any* order.

* **Non-closure under powering:** There is a sequence of polynomials $(f_n(x_1, ..., x_n))_n$ with poly($n$)-sized roABPs such that any super-constant power of $f_n$ does not have roABPs of polynomial size in any order (and $f_n^n$ requires exponential size in any order).

* **Non-closure under symmetric compositions:** There are symmetric polynomials $(f_n(e_1, ..., e_n))_n$ that have roABPs of polynomial size such that $f_n(x_1, ..., x_n)$ do not have roABPs of subexponential size. (Here, $e_1, ..., e_n$ denote the elementary symmetric polynomials in $n$ variables.)

These results should be viewed in light of known results on models such as algebraic circuits, (general) algebraic branching programs, formulas and constant-depth circuits, all of which are known to be closed under these operations.

To prove non-closure under factoring, we construct hard polynomials based on expander graphs using gadgets that lift their hardness from sparse polynomials to roABPs. For symmetric compositions, we show that the *circulant* polynomial requires roABPs of exponential size in every variable order.

<footnote>*IT University of Copenhagen, Denmark. This work was funded by the Independent Research Fund Denmark (grant agreement No. 10.46540/3103-00116B) and is also supported by the Basic Algorithms Research Copenhagen (BARC), funded by VILLUM Foundation Grant 54451.</footnote>

<footnote>†Department of Computer Science, University of Copenhagen, Denmark. This work was funded by the European Research Council (ERC) under grant agreement no. 101125652 (ALBA).</footnote>

<footnote>‡Université Savoie Mont Blanc, CNRS, LAMA. This work was supported by ANR project VONBICA (ANR-22-CE48-0007).</footnote>
# 1 Introduction

Given any computational model, it is natural to study the closure properties of the model with respect to simple operations. In Boolean complexity, these simple operations typically take the form of Boolean operations such as union, intersection, complement etc. In the setting of *algebraic complexity*, the object of computation is a multivariate polynomial $f \in \mathbb{F}[x_1, \dots, x_n]$. Here, it is intuitive to consider closure properties under algebraic operations.

In this paper, we study the closure properties of a very well studied model of algebraic computation, namely *read-once oblivious Algebraic Branching programs* (roABPs). The interest in this model stems from the fact that it is both expressive enough to capture many natural algorithmic paradigms while at the same time possible to analyze using standard ‘complexity measures’ [Nis91].

In particular, roABPs can efficiently compute several polynomials of interest, including elementary symmetric polynomials and iterated matrix multiplication, the latter being provably hard to compute for constant-depth circuits [BDS22; LST25; NW94]. In addition, roABPs subsume well-studied models such as sparse polynomials, set-multilinear and diagonal depth-3 circuits [KNS20], as well as polynomials with large partial derivative dimension [BT24]. On the other hand, this is also one of the few models where we have a perfect characterization of the complexity of any given polynomial (in the form of the rank of an associated matrix) and where we also have a perfect understanding of border complexity [For16]. As a consequence, this model has played a central role in research on lower bounds, polynomial identity testing algorithms and ‘debordering’ results [Blä+20; DDS22; DS22].

We study the closure properties of this model under basic algebraic operations such as factorization, powering, and inversion under composition with an important algebraic map (the elementary symmetric polynomial map). Apart from being natural questions about any computational model, such investigations have played a vital role in understanding hardness-randomness tradeoffs [Bha+25a; CKS19; DSY09; KI04] and the complexity of basic algebraic problems such as the Resultant and GCD [AW24; Bha+25b] in other algebraic models.

## 1.1 Main Results

In contrast with what is known for other models, our results are mostly negative. Specifically, we show the following.

**roABP factor non-closure.** Our first main result shows that there are explicit polynomial sequences that have small roABPs but with an irreducible factor that has roABP complexity superpolynomial in $n$. Specifically, we prove roABP complexity lower bound for a *root*, which is an irreducible factor of the form $x_n - f(x_1, \dots, x_{n-1})$, even when the roABP is allowed to scan the variables in any order. The formal statement is as follows.
**Theorem 1** (roABP factor non-closure). The following holds over any field. Let $n \in \mathbb{N}$ be a parameter and $d \ge n$. There exists an $n$-variate polynomial $f$ of degree $d$ computable by an roABP of width $w := 2^{O(n)}$, such that one of its (irreducible) factors $g$ requires an roABP of width $w^{\Omega(\log d)}$ in every variable order.

Note that, an roABP computing an $n$-variate polynomial by definition has only $n$ layers. Hence, the size and the width of an roABP are polynomially related. Secondly, the size and width parameters in the theorem above are not polynomial in the number of variables, but they can be easily made polynomial by padding with some additional ‘dummy’ variables. In particular, one should think of $n$ above as logarithmic in the number of ‘actual’ variables and $d$ as a growing parameter, up to a polynomial in the number of variables.

This is in contrast to other algebraic models such as algebraic circuits [Kal89; KT90], branching programs [ST21], formulas and constant-depth circuits [Bha+25a], all of which satisfy the property that factors of a polynomial $f$ have complexity comparable to that of $f$. An exception to this rule is the family of sparse polynomials [GK85], and our construction is based on ‘lifting’ this example to the setting of roABP.

**roABP complexity of Symmetric Composition.** We study an analogue of the result of Bläser and Jindal [BJ19] for roABP. More specifically, a classical result in the theory of symmetric functions says that any symmetric polynomial<fnref n="1" /> $f_{\text{sym}}(x_1, \dots, x_n)$ can be written as a unique polynomial combination $f$ of the elementary symmetric polynomials $\text{ESym}_n^1, \dots, \text{ESym}_n^n$, where $\text{ESym}_n^d$ is the $n$-variate elementary symmetric polynomial of degree $d$. Looking for a computational analogue of this theorem, Lipton and Regan [LR09], asked: what is the complexity of $f_{\text{sym}}$ vis-à-vis that of $f$?

Bläser and Jindal [BJ19] showed that the complexity of $f$ and $f_{\text{sym}}$ are polynomially related in the algebraic circuit model. Recently, the work of Bhattacharjee, Kumar, Rai, Ramanathan, Saptharishi and Saraf [Bha+25b] extended this result to formulas and constant-depth circuits to show that fundamental computations such as GCD, resultants and discriminants have efficient constant-depth circuits in any characteristic. This generalizes a similar result of Andrews and Wigderson [AW24] in characteristic 0.

We show in this paper that the roABP complexity of a polynomial $f$ and its symmetric counterpart $f_{\text{sym}}$ can differ significantly. Taking $f_{\text{sym}} = \sum_{d=0}^{n} \text{ESym}_n^d(x_1^k, \dots, x_n^k)$, we can show that $f_{\text{sym}}$ is easy but $f$ is exponentially hard.

**Theorem 2.** The following holds over fields of characteristic zero. Let $n \in \mathbb{N}$ be a parameter. There exists an $n$-variate polynomial $f$ such that the symmetric polynomial $f_{\text{sym}} := f(\text{ESym}_n^1, \dots, \text{ESym}_n^n)$ is computable by an roABP of constant width in every variable order, but any roABP computing $f$ in any variable order must have width $2^{O(n)}$.

<footnote n="1">¹A polynomial is symmetric if it is invariant under any permutation of its variables.</footnote>
In the other direction, our next result shows that even if a polynomial $f$ is easy to compute by roABP, its symmetric counterpart $f_{\text{sym}}$ can still be hard for roABP—once again in sharp contrast to the known results for circuits, formulas, and constant-depth circuits. Specifically, the lower bound for a power of the elementary symmetric polynomial yields an example where $f$ is easy but $f_{\text{sym}}$ is exponentially hard.<fnref n="2" />

**Theorem 3.** The following holds over fields of characteristic zero. Let $n \in \mathbb{N}$ be a parameter. There exists an $n$-variate polynomial $f$ computable by an roABP of constant width such that its respective symmetric polynomial $f_{\text{sym}} = f(\text{ESym}_n^1, \dots, \text{ESym}_n^n)$ requires an roABP of width $2^{\Omega(n)}$ in every variable order.

**roABP non-closure corollaries.** We also investigate the power of roABPs in relation to powering an efficiently computable polynomial. It is well-known that constant powers of such polynomials also have small roABPs (see e.g. [And+18, Lemma 2.5]). However, we show that for larger powers, a superpolynomial blow-up in width is unavoidable.

**Corollary 3.1 (roABP powering non-closure).** The following holds over fields of characteristic zero. There exists an $n$-variate polynomial $f$ computable by an roABP of width $O(n)$ such that for any $d$, any roABP computing $f^d$ requires width at least $\binom{d+n/2}{n/2}$ in every variable order.

*Remark.* We give two example polynomials to prove the hardness of powering for roABP. The first is the elementary symmetric polynomial (this lower bound will also prove Theorem 3) and the second is a quadratic polynomial inspired by the proof of Theorem 1.

Another corollary of Theorem 3 is that computing the resultant and the discriminant is hard for roABP.

**Corollary 3.2 (roABP discriminant non-closure).** The following holds over fields of characteristic zero. For all $n$, there exists an $n$-variate polynomial $f(x, y)$ computable by an roABP of width $O(n)$ such that any roABP computing the discriminant $\text{Disc}_y(f)$ requires width at least $2^{\Omega(n)}$ in every variable order.

*Remark.* As an immediate consequence of the corollary above, we get that roABP is not closed under taking resultants.

**Related Work.** There have been many lines of investigation into roABPs from the point of view of lower bounds [And+18; KNS20; Nis91], PIT algorithms [Agr+15; And+18; BG22; BS21; FSS14; FS13; GG20; Gur+17; RS05; ST24], border complexity [BDI21; Blä+20; DDS22; DS22], algebraic meta-complexity [Bha+24; BT24] and so on.

Our work is closely related to that of Kayal, Nair, and Saha [KNS20], who proved separations between the power of roABPs and multilinear depth-3 circuits. Non-closure results of a similar flavour to ours have also been proved by Saha and Thankey [ST24, Appendix E.1]. They construct explicit families of polynomials that require roABP of exponential size, but arise from applying invertible linear transformations to sparse polynomials $f$ that have linear roABP complexity.

<footnote n="2">²This is an especially strong contrast to the other models where it is trivial to show that if $f$ is easy, then so is $f_{\text{sym}}$.</footnote>
Some of their ideas, such as those involving the use of expander graphs, also appear in our work.

Similar separations between roABPs and other models (such as read-twice ABPs) were also addressed in the work of Anderson, Forbes, Saptharishi, Shpilka and Volk [And+18]. We re-prove a result from this work separating depth-2 algebraic circuits (products of linear polynomials) from roABPs in order to understand the roABP complexity of some explicit symmetric functions. Our lower bound is proved for the specific case of the determinant of a Circulant matrix, which is a naturally occurring mathematical object and hence may be independently interesting.

## 1.2 Proof Techniques

The main technique for understanding the roABP complexity of a polynomial is a characterization due to Nisan [Nis91], who showed that the roABP complexity of a polynomial $f$ (or more precisely the width of the smallest roABP computing $f$) in a given order is captured by the ranks of certain matrices related to $f$, also known as the evaluation dimension of $f$ (formally defined in Definition 2.6). We also heavily rely on this notion in our work.

**Factor non-closure.** To construct our examples of polynomials that are efficiently computable by roABPs but hard to factor, we start with an analogous construction for a weaker setting, that of sparse polynomials. The following is a well-known construction due to [GK85, Example 5.1].

$$f(x_1, \dots, x_n) = \prod_{i=1}^{n} (x_i^d - 1) = \prod_{i=1}^{n} (x_i - 1) \cdot \underbrace{\prod_{i=1}^{n} (1 + x_i + \dots + x_i^{d-1})}_{g(x_1, \dots, x_n)}$$

Note that the polynomial $f$ has $2^n$ monomials while its factor $g$ has $d^n$ monomials. This thus yields an example of a polynomial whose factors have many more monomials than the polynomial itself.

We would like to extend this to the setting of roABP. Unfortunately, the example above does not work as is, as the polynomial $g$ is a product of univariate polynomials and hence has a small roABP. Our idea is to 'lift' this sparsity lower bound to an roABP lower bound.

The basic idea of lifting, which has proven powerful in the area of Boolean complexity [RGR22] and also Algebraic Proof complexity [For+21], is to start with a function $f$ that is hard for a simpler computational model (in this case sparse polynomials) and convert it to a function $g$ that is difficult for a much more powerful model by replacing the variables of $f$ by functions (typically called 'gadgets') in a small number of new variables to obtain $g$. A version of this idea can be used to lift degree lower bounds on the multilinear representation for some functions to lower bounds for algebraic proof systems based on roABPs [For+21].

Inspired by [For+21], we replace the variables of the polynomial $f$ by quadratic multilinear monomials in a new set of variables $y_1, \dots, y_m$ where $m = \Omega(n)$. We can associate this replace-
ment with an undirected graph $G$ on $m$ vertices and $n$ edges. We show that, as long as $G$ is
a sufficiently good constant-degree expander, the corresponding 'lifted' polynomials $f_G$ and $g_G$ are
easy and hard respectively for roABPs with similar parameters to the case of sparse polynomials.

The crucial property of expander graphs that allows us to prove a lower bound on $g_G$ is the Expander Mixing lemma. It can be used to show that given any balanced partition of the vertices of $G$, there is a large induced matching between the two sets in the parts. This allows us to find a large identity matrix as a submatrix of the evaluation matrix of $g_G$, leading to strong bounds on its evaluation dimension.

**The complexity of powering.** We give two examples to demonstrate that roABPs are not closed under powering.

The first is a quadratic polynomial $g$ whose monomials again correspond to a constant-degree
expander graph as in the previous result. The Expander Mixing lemma can again be used to
argue that large powers of $g$ have large evaluation dimension.

The second example is just an elementary symmetric polynomial. Symmetric polynomials
are particularly natural to study in the setting of roABPs, since the polynomials have the same
complexity under any variable ordering. In particular, studying the complexity of a symmetric
polynomial turns into understanding the ranks of combinatorially defined matrices. In the setting
of a power of the elementary symmetric polynomial, we are able to show that this matrix has
large rank.

**No Bläser-Jindal type results for roABPs.** Already the example of the elementary symmet-
ric polynomial above shows that for the simple polynomial $f(y_1, \dots, y_n) = y_i^d$, the symmetric
polynomial $f(ESym_n^1, \dots, ESym_n^n)$ is hard to compute for roABPs.

To prove a converse result, we use the symmetric polynomial $f_{\text{sym}} := \sum_{d=0}^{n} \text{ESym}_n^d(x_1^k, \dots, x_n^k)$.
In this case, we need to understand the complexity of the polynomial $f$ (such as
$f(\text{ESym}_n^1, \dots, \text{ESym}_n^n) = f_{\text{sym}}$). It turns out that the polynomial $f$ in this case is completely under-
stood [hui21] and is closely related to the determinant of the Circulant matrix. To prove the lower
bound, we prove an roABP lower bound on this determinant, which we believe is independently
interesting.

**Outline.** We begin with preliminaries in Section 2. Section 3 contains the proof of Theorem 1. In Section 4, we prove Theorem 2 and Theorem 3. Finally, in Section 5, we prove all the corollaries.

## 2 Notations and Preliminaries

Throughout the paper, we will use a growing parameter $n > 0$ to denote the number of variables
in the polynomial. Let $x = (x_1, \dots, x_n)$ be the set of indeterminates. A monomial of the form
$x_1^{e_1} \cdots x_n^{e_n}$ is denoted as $x^e$, where $e = (e_1, \dots, e_n) \in \mathbb{N}^n$. The degree of a monomial $x^e$ is defined as $\deg(x^e) := e_1 + \cdots + e_n$. The degree of a polynomial $f \in \mathbb{F}[x_1, \dots, x_n]$ is defined as the maximum degree of its constituent monomials. We use $\mathrm{coef}_{x^e}(f)$ to denote the coefficient of the monomial $x^e$ in $f$.

## 2.1 Read-Once Oblivious Algebraic Branching Programs (roABP)

Our model of interest arises as a natural restriction of Algebraic Branching Programs (ABPs), which we describe next. An Algebraic Branching Program (ABP) is a layered and directed graph with a source vertex $s$ and a sink vertex $t$. All edges connect vertices from layer $i$ to $i+1$. Further, the edges are labeled with affine polynomials over the underlying field $\mathbb{F}$. For every path $\gamma$ from $s$ to $t$, $\mathrm{wt}(\gamma)$ is the product of labels on the edges of the path $\gamma$. The polynomial computed by the ABP is defined as

$$f := \sum_{\text{path } \gamma: s \sim t} \mathrm{wt}(\gamma).$$

The depth of an ABP is defined as the number of layers in the graph, and the width is the maximum number of nodes in a layer across the graph. The number of vertices used in the graph is the size of the ABP. The roABP model is a restriction of ABPs, which we define below.

**Definition 2.1 (roABP).** Let $n \in \mathbb{N}$ be arbitrary and fix a permutation $\pi : [n] \to [n]$. An roABP in the order $\pi$ computing an $n$-variate polynomial $f(x)$ is an ABP where in the $i$-th layer the edge labels are univariate polynomials over $x_{\pi(i)}$.

The size of an roABP is defined as the number of vertices it contains, and the width is defined as the maximum number of vertices in any layer.

In a foundational work, Nisan [Nis91] characterized the complexity of an ABP in the non-commutative setting with the rank of certain matrices. Remarkably, the characterization extends to roABP as well. We define the relevant matrix to formally state this characterization.

**Definition 2.2 (Nisan Matrix).** Consider an $n$-variate polynomial $f(x)$ and a variable partition $Y \sqcup Z = \{x_1, \dots, x_n\}$. The Nisan matrix of $f$ with respect to $Y, Z$, denoted as $M_{Y,Z}(f)$, is the matrix whose rows are indexed by monomials $m_Y$ over $Y$ and whose columns are indexed by monomials $m_Z$ over $Z$. Its entry at $(m_Y, m_Z)$ is defined as

$$M_{Y,Z}(f) [m_Y, m_Z] = \mathrm{coef}_{m_Y \cdot m_Z}(f).$$

Historically, the Nisan Matrix has also been referred to as the coefficient matrix or partial derivative matrix. The width of an roABP computing a polynomial $f$ can be exactly characterized by the rank of the Nisan matrix of $f$ [For14, Lemma 4.5.8].

**Theorem 2.3 (roABP characterization).** Let $f(x)$ be an $n$-variate polynomial, and fix a permutation $\pi$ on variables. For each $i \in [n]$, consider the partition $Y_i := \{\pi(x_1), \dots, \pi(x_i)\}$ and $Z_i = \{\pi(x_{i+1}), \dots, \pi(x_n)\}$, and let $M_{Y_i, Z_i}(f)$ denote the corresponding Nisan matrix.
The width of the smallest roABP computing $f$ in the order $\pi$ is exactly $\max_{i \in [n]} \text{rank}(M_{Y_i, Z_i}(f))$. Moreover, the size of the smallest roABP is exactly $\sum_{i \in [n]} \text{rank}(M_{Y_i, Z_i}(f))$.

We next prove a lemma to demonstrate the usefulness of the roABP characterization, which will be used in our later proofs.

**Observation 2.4.** Consider an $n$-variate polynomial as follows

$$f := \prod_{i \in [n]} (1 + x_i + x_i^2 + \dots + x_i^{d-1}).$$

Let $Y = \{y_1, \dots, y_n\}$ and $Z = \{z_1, \dots, z_n\}$ be disjoint set of variables. Define a $2n$-variate polynomial $\tilde{f} := f(y_1z_1, \dots, y_nz_n)$. The rank of the Nisan matrix $M_{Y,Z}(\tilde{f})$ is $d^n$.

**Remark 2.5.** Note that $f$ itself can be computed by a constant width roABP in any order.

*Proof.* Observe that for every monomial $m_Y$ over $Y$ such that each variable has degree at most $d-1$ in $m_Y$, there is a unique monomial $m_Z$ of the same form over $Z$ such that $\text{coef}_{m_Y \cdot m_Z}(\tilde{f})$ is not zero, and reciprocally, for any monomial $m_Z$ over $Z$ there is a unique monomial $m_Y$. Consequently, the Nisan matrix $M_{Y,Z}(\tilde{f})$ is a permutation matrix, and hence has rank $d^n$. $\square$

**Evaluation Dimension.** An alternative perspective on the Nisan matrix was introduced by Saptharishi [FS13, Section 6]. As we will see in our proofs, this viewpoint often makes it easier to reason about roABP complexity.

**Definition 2.6 (Evaluation Dimension).** Let $f(x)$ be an $n$-variate polynomial on $X = \{x_1, \dots, x_n\}$ over a field $\mathbb{F}$, and a subset of variables $Y$ and $Z := X \setminus Y$. The evaluation dimension of $f$ with respect to the partition $Y \sqcup Z$ is defined as

$$\text{evalDim}_{Y,Z}(f) := \text{rank} \left( \left\{ f(Y, \mathbf{a}) \mid \mathbf{a} \in \mathbb{F}^{|Z|} \right\} \right).$$

Over large fields, the evaluation dimension is equivalent to the rank of the Nisan matrix. However, this equivalence does not hold when restricting the evaluation points, e.g. to the Boolean cube. Nevertheless, the evaluation dimension is always a lower bound of the rank of the Nisan matrix ([Sap21, Lemma 11.9], and see also [For14, Corollary 4.5.12]).

**Theorem 2.7.** Let $f(x)$ be an $n$-variate polynomial, and fix a permutation $\pi$ on variables. For a variable partition $Y \sqcup Z$ with $Y = \{x_{\pi(1)}, \dots, x_{\pi(i)}\}$ and $Z = \{x_{\pi(i+1)}, \dots, x_{\pi(n)}\}$, any roABP that computed $f$ in the order $\pi$ has width at least $\text{evalDim}_{Y,Z}(f)$.

Conversely, if the field $\mathbb{F}$ is infinite, there is a roABP computing $f$ of width $\text{evalDim}_{Y,Z}(f)$.

## 2.2 Elementary Symmetric Polynomials

Symmetric polynomials are those that are invariant under any permutation of the variables. A fundamental and well-studied family within symmetric polynomials is the elementary symmetric
polynomials, which are defined as follows.

**Definition 2.8 (Elementary Symmetric Polynomial).** The elementary symmetric polynomial of degree d, on variables $x_1, \dots, x_n$, is defined as

$$ \mathrm{ESym}_n^d(x_1, \dots, x_n) := \sum_{1 \le i_1 < \dots < i_d \le n} x_{i_1} \dots x_{i_d}. $$

Whenever clear from the context, we write $e_d := \mathrm{ESym}_n^d$ to denote the degree-$d$ elementary symmetric polynomial in $n$ variables. A more convenient way to define these polynomials is via the following generating functions:

$$ \prod_{i \in [n]} (1 + x_i \cdot t) = \sum_{i=0}^{n} \mathrm{ESym}_n^i(\mathbf{x}) \cdot t^i. \qquad (2.9) $$

These polynomials are called *elementary* because they form the fundamental building blocks for all symmetric polynomials. For any $n$-variate polynomial $f(\mathbf{x})$, we define the $n$-variate symmetric polynomial $f_{\mathrm{sym}} := f(e_1, \dots, e_n)$.

**Theorem 2.10 (Fundamental Theorem of Symmetric Polynomials).** Let $R$ be any commutative ring, and let $g \in R[x_1, \dots, x_n]$ be a symmetric polynomial. Then there exists a unique polynomial $f \in R[y_1, \dots, y_n]$ such that

$$ g = f_{\mathrm{sym}} := f(\mathrm{ESym}_n^1, \dots, \mathrm{ESym}_n^n). $$

We refer to [Lan02, Theorem IV.6.1] for the proof of Fundamental Theorem of Symmetric Polynomials (see also [BC17]). We will also need the following variable partitioning lemma, which is a special case of [Mer13, Theorem 1.1].

**Lemma 2.11 (ESym Variable Partition).** Let $Y \sqcup Z$ be a partition of the variables. Then,

$$ \mathrm{ESym}_{|Y \sqcup Z|}^{d}(Y, Z) = \sum_{i=0}^{d} \left( \mathrm{ESym}_{|Y|}^{i}(Y) \cdot \mathrm{ESym}_{|Z|}^{d-i}(Z) \right). $$

*Proof.* Let $Y = \{y_1, \dots, y_m\}$ and $Z = \{z_1, \dots, z_n\}$. Then using Equation 2.9 we can write,

$$ \sum_{i=0}^{m} \mathrm{ESym}_{m}^{i}(Y) \cdot t^{i} = \prod_{i=1}^{m} (1 + y_{i} \cdot t) $$

$$ \sum_{i=0}^{n} \mathrm{ESym}_{n}^{i}(Z) \cdot t^{i} = \prod_{i=1}^{n} (1 + z_{i} \cdot t) $$

Taking the product of the two polynomials above, and comparing the coefficients of $t^d$ on both sides proves the lemma. $\square$

As a direct consequence of extracting the coefficient of $t^d$ from Equation 2.9, Shpilka and Wigderson [SW01] (crediting Ben-Or) presented the following identity for elementary symmetric
polynomials, which yields a near-optimal roABP of width $O(n)$ computing $ESym_n^d$ in any variable order:

**Proposition 2.12** ([SW01, Theorem 5.1]). For any $n \in \mathbb{N}$ and $d \le n$, let $\omega$ be a primitive $n$-th root of unity. There exist $\beta_0, \dots, \beta_{n-1} \in \mathbb{C}$ such that

$$ESym_n^d(x_1, \dots, x_n) = \sum_{0 \le j < n} \beta_j (1 + \omega^j x_1) \cdot (1 + \omega^j x_2) \cdots (1 + \omega^j x_n).$$

*Remark 2.13.* $ESym_n^d$ can also be computed by a provably tight roABP of width $\min(d+1, n-d+1)$ in any variable order using only coefficients 0 and 1 (see [CT22, Construction 1.2]).

## 2.3 Resultant and Discriminant

We recall the definitions and properties of resultant and discriminant from factorization literature. We encourage readers to refer to [GG13, Chapter 6] for a more detailed textbook treatment of these concepts.

**Definition 2.14** (Resultant). Consider two $n$-variate polynomials $f, g \in \mathbb{F}[\mathbf{x}][y]$ as follows:

$$f := \sum_{i=0}^{d_1} f_i(\mathbf{x}) \cdot y^i \quad \text{and} \quad g := \sum_{i=0}^{d_2} g_i(\mathbf{x}) \cdot y^i.$$

Define the Sylvester matrix of $f$ and $g$ as the following $(d_1 + d_2) \times (d_1 + d_2)$ matrix:

$$S_y(f,g) = \begin{pmatrix}
f_{d_1} & & & g_{d_2} & & \\
f_{d_1-1} & f_{d_1} & & g_{d_2-1} & g_{d_2} & \\
\vdots & f_{d_1-1} & \ddots & \vdots & g_{d_2-1} & \ddots \\
\vdots & \vdots & \ddots & f_{d_1} & \vdots & \ddots & g_{d_2} \\
f_0 & \vdots & & f_{d_1-1} & g_0 & \vdots & g_{d_2-1} \\
& f_0 & \ddots & \vdots & \vdots & g_0 & \ddots \\
& & \ddots & \vdots & \vdots & \ddots & \vdots \\
& & & f_0 & & & g_0
\end{pmatrix}$$

Then the resultant of the two polynomials with respect to $y$ is defined as the determinant of the Sylvester matrix as:

$$\mathrm{Res}_y(f,g) := \mathrm{Det}(S_y(f,g)).$$

The resultant of two polynomials is non-zero if and only if their $\gcd$ is 1. A well-known case of resultant relevant for factoring algorithms is the discriminant.

**Definition 2.15** (Discriminant). Consider a $n$-variate polynomial $f$. The discriminant with respect to $y$
of f is defined as the resultant, with respect to y, of f and its y-derivative, i.e.,

$$ \mathrm{Disc}_y(f) := \mathrm{Res}_y(f, \partial_y f). $$

The following well-known observation will be useful in the analyses of complexity of the resultant and the discriminant.

**Observation 2.16** (see [CLO05, Chapter 3]). Let $f = \prod_{i \in [n]} (y - \alpha_i)$ and $g = \prod_{i \in [m]} (y - \beta_i)$ be two univariate polynomials. Then the resultant of $f$ and $g$ with respect to $y$ is given by

$$ \mathrm{Res}_y(f,g) = \prod_{i \in [n]} g(\alpha_i). $$

## 3 roABP Factor Non-Closure

To prove Theorem 1, we need a polynomial of low roABP complexity, that has a factor of high roABP complexity. We will use explicit expander graphs for this purpose. The only property we require from the expander graph is that, for any sufficiently large partition of its vertex set into two parts, it contains a large induced matching between the two parts.

**Lemma 3.1** (Induced Matching Lemma). For every $n \in \mathbb{N}$ there exists a constant degree graph $G_n = (V, E)$ on $n$ vertices such that the following holds: for any partition $(S, T)$ of $V$ with $|S| = \epsilon n$ and $|T| = (1 - \epsilon)n$ where $\epsilon \in [\frac{1}{3}, \frac{2}{3}]$, the graph contains $\Omega(n)$ edges between $S$ and $T$ that form an induced matching.

*Proof Sketch.* There exists an absolute constant $\delta \in (0, 1)$ such that, for any $k \in \mathbb{N}$ with $k \ge 1$, we can construct explicit $k$-regular expander graphs $G_n = (V, E)$ whose second-largest eigenvalue is at most $k^\delta$; see [RVW00].

When $k$ is chosen to be sufficiently large such that the second-largest eigenvalue of $G_n$ is strictly smaller than $k/3$, then the lemma follows as an easy consequence of the Expander Mixing Lemma [AC06] (see also [HLW06, Lemma 2.5]). See, for example, [Juk08, Claim 4]. $\square$

Define an $n$-variate polynomial $P_G$ associated with constant degree graph $G_n = (V, E)$ guaranteed by Lemma 3.1 as follows:

$$ P_G := \prod_{(i,j) \in E} ((x_i x_j)^d - 1). \qquad (3.2) $$

Since the degree of the graph is constant, the sparsity of $P_G$ is $2^{|E|} = 2^{O(n)} =: w$. Therefore, $P_G$ can be computed by an roABP of width $w$ in every variable order. To prove the hardness of its factor, consider the following polynomial $Q_G$:

$$ Q_G := \prod_{(i,j) \in E} \left(1 + (x_i x_j) + (x_i x_j)^2 + \dots + (x_i x_j)^{d-1}\right). \qquad (3.3) $$
It is well known that $(1+x+x^2+...+x^{d-1})(x-1) = x^d - 1$. Using the identity, we immediately obtain

$$P_G = Q_G \cdot \prod_{(i,j) \in E} (x_i x_j - 1).$$

**Lemma 3.4.** The polynomial $Q_G$ defined in Equation 3.3 requires an roABP of width $d^{\Omega(n)}$ in every variable order.

*Proof.* Let $\pi$ be any variable order on the variables $X = \{x_1, ..., x_n\}$, and consider the partition $Y = \{x_{\pi(1)}, ..., x_{\pi(n/2)}\}$ and $Z = X \setminus Y$.

Let $Y$ and $Z$ also denote the partition of vertices of $G_n$. Then from Lemma 3.1, we know there exists an induced matching $\mathcal{M}$ between $Y$ and $Z$ of size $\Omega(n)$. Define

$$\begin{aligned} \tilde{f} &:= \prod_{(i,j) \in \mathcal{M}} (1 + (x_i x_j) + (x_i x_j)^2 + \dots + (x_i x_j)^{d-1}) \\ &= \prod_{i \in [t]} (1 + (y_i z_i) + (y_i z_i)^2 + \dots + (y_i z_i)^{d-1}), \end{aligned}$$

where for every $i \in [t]$, $y_i$ is a variable in $Y$ and $z_i$ is a variable in $Z$, and $t = \Omega(n)$. Here we have used the fact that $\mathcal{M}$ is an induced matching. In particular, $\tilde{f}$ is obtained from $Q_G$ by setting to zero the variables which are not in the matching $\mathcal{M}$. Hence, the rank of the Nisan matrix can only decrease. Finally, by Observation 2.4,

$$\mathrm{rank}(M_{Y,Z}(Q_G)) \geq \mathrm{rank}(M_{Y,Z}(\tilde{f})) \geq d^{\Omega(n)}.$$

We obtain the claimed lower bound for width of roABP computing $Q_G$ by Theorem 2.3. $\square$

We will now use the discussion so far to give the complete proof of the factor non-closure result.

**Theorem 1 (roABP factor non-closure).** The following holds over any field. Let $n \in \mathbb{N}$ be a parameter and $d \geq n$. There exists an $n$-variate polynomial $f$ of degree $d$ computable by an roABP of width $w := 2^{O(n)}$, such that one of its (irreducible) factors $g$ requires an roABP of width $w^{\Omega(\log d)}$ in every variable order.

*Proof.* Consider an $n$-variate polynomial $g := Q_{G_{n-1}} + z$, where $z$ is an auxiliary variable and $Q_{G_{n-1}}$ is defined as in Equation 3.3 using a constant-degree graph $G_{n-1}$. We then define

$$f := g \cdot \prod_{(i,j) \in E} (x_i \cdot x_j - 1) = P_G + z \cdot \prod_{(i,j) \in E} (x_i \cdot x_j - 1).$$

As argued after Equation 3.2, both $P_G$ and $\prod_{(i,j) \in E} (x_i \cdot x_j - 1)$ have sparsity $2^{O(n)}$ and hence we can compute them by an roABP of width $w = 2^{O(n)}$ in every variable order. Therefore, $f$ itself admits an roABP of width $w$ in every variable order.
Observe that $g$ is an irreducible polynomial because it is linear in the auxiliary variable $z$.<fnref n="3" />

Further, by Lemma 3.4, any roABP computing $Q_G + z$ must have width at least $d^{\Omega(n)}$ in every variable order. Since $d \ge n$, the claimed width lower bound for roABP computing $g$ follows. □

# 4 roABP Complexity of Symmetric Polynomials

In the following two sections we prove Theorem 2 and Theorem 3 along with their corollaries.

## 4.1 $f_{\text{sym}}$ is easy, but $f$ is hard

In this section, we work over fields of characteristic zero. For the proof of Theorem 2, we consider $f_{\text{sym}} = \sum_{d=0}^{n} \text{ESym}_n^d(x_1^k, \dots, x_n^k)$ for a suitable choice of $k \in [n]$ to be fixed later.

Let us consider the polynomial

$$g(y_1, \dots, y_n, t, z_0, \dots, z_{k-1}) := \prod_{j=0}^{k-1} \left( 1 + \sum_{i \in [n]} y_i \cdot (t \cdot z_j)^i \right).$$

The polynomial $g$ is symmetric in the variables $z_0, \dots, z_{k-1}$. So by Theorem 2.10, there exists a polynomial $\tilde{g} \in \mathbb{Z}[y_1, \dots, y_n, t, z_0, \dots, z_{k-1}]$ such that $g(\mathbf{y}, t, \mathbf{z}) = \tilde{g}(\mathbf{y}, t, e_1(\mathbf{z}), \dots, e_k(\mathbf{z}))$. Notice that if $\omega$ is a $k$-th primitive root of the unity, Equation 2.9 implies

$$\begin{cases} e_i(\omega^0, \dots, \omega^{k-1}) = 0 & \text{for } 1 \le i < k, \\ e_k(\omega^0, \dots, \omega^{k-1}) = 1. \end{cases}$$

Let us define

$$f(y_1, \dots, y_n) := \tilde{g}(\mathbf{y}, 1, 0, \dots, 0, 1) \in \mathbb{Z}[\mathbf{y}]. \quad (4.1)$$

The previous paragraph ensures that for any $k$-th primitive root of the unity $\omega$, we have

$$f(y_1, \dots, y_n) = \prod_{j=0}^{k-1} \left( 1 + \sum_{i \in [n]} y_i \cdot \omega^{j \cdot i} \right). \quad (4.2)$$

The following lemma shows that $f$ is indeed the unique polynomial inducing the symmetric polynomial $\sum_{d=0}^{n} \text{ESym}_n^d(x_1^k, \dots, x_n^k)$. The following is an argument in [hui21], which we reproduce here for completeness.

**Lemma (Circulant Polynomial).** For any $n \in \mathbb{N}$ and odd positive integer $k \le n$,

$$f_{\text{sym}}(\mathbf{x}) := f(e_1(\mathbf{x}), \dots, e_n(\mathbf{x})) = \sum_{d=0}^{n} \text{ESym}_n^d(x_1^k, \dots, x_n^k).$$

<footnote n="3">³See [GK85, Example 5.1] where the hardness is lifted to irreducible factor by considering $g = Q_G + n$.</footnote>
Proof. Let $\omega$ be a k-th primitive root of the unity. Using the factorization identity $(1 - t^k) = \prod_j(1 - \omega^j \cdot t)$ together with Equation 2.9 we obtain the following:

$$ \prod_{i \in [n]} (1 - x_i^k \cdot (-t)^k) = \prod_{i=1}^{n} \prod_{j=0}^{k-1} (1 + \omega^j \cdot x_i \cdot t) \\ = \prod_{j=0}^{k-1} \left( 1 + \sum_{i=1}^{n} e_i(\mathbf{x}) \cdot (\omega^j \cdot t)^i \right). $$

By Equation 4.2 and instantiating $t$ by 1, we obtain

$$ \prod_{i \in [n]} (1 + x_i^k) = f(e_1(\mathbf{x}), \dots, e_n(\mathbf{x})). \quad \square $$

We call the polynomial $f$ a circulant polynomial because it is closely related to the determinant of a Circulant matrix.<fnref n="4" />

In the following lemma, we show that the polynomial $f$ is hard for roABP in every variable order over any field $\mathbb{F}$ of characteristic 0.

**Lemma 4.3.** For any prime $k$ with $2 \le k \le n$, the $n$-variate polynomial $f$ defined in Equation 4.1 requires roABP width at least $2^{(k-1)/2}$ in any variable order.

Proof. By instantiating a variable, the roABP width can only decrease. So it is sufficient to consider $f'(y_1, \dots, y_k) := f(y_1, \dots, y_k, 0, \dots, 0)$.

By the standard evaluation-dimension lower bound for roABP, it suffices to show the following. For any variable order $\pi$ and the variable partition $(U, V)$ where $U = \{y_{\pi(1)}, \dots, y_{\pi((k-1)/2)}\}$ and $V = \{y_{\pi((k-1)/2+1)}, \dots, y_{\pi(k)}\}$ we have

$$ \mathrm{evalDim}_{U,V}(f') = \mathrm{rank} \left( \left\{ f'(\mathbf{u}, \mathbf{a}) \mid \mathbf{a} \in \mathbb{F}^{|V|} \right\} \right) \ge 2^{\Omega(k)}. $$

Re-writing Equation 4.2 in terms of variable partition $(U, V)$, we have

$$ f'(\mathbf{u}, \mathbf{a}) = \prod_{j=0}^{k-1} \left( \ell_j(\mathbf{u}) + \ell'_j(\mathbf{a}) + 1 \right), \quad (4.4) $$

where $\ell_j(\mathbf{u})$ and $\ell'_j(\mathbf{v})$ are linear polynomials in $U$ and $V$, respectively.

Arranging the coefficients in the linear forms $\{\ell_j(\mathbf{u}) + \ell'_j(\mathbf{v})\}_j$ as the rows of a $k \times k$ matrix yields a matrix $M$ whose $(j, i)$-th entry is $\omega^{j \cdot \pi(i)}$ for $j \in \{0, \dots, k-1\}$ and $i \in [k]$. Note that $M$ can be obtained from the standard $k \times k$ DFT matrix $(\omega^{j \cdot i})_{i,j \in [k]}$ by permuting columns.

When $k$ is prime, Chebotarev's theorem on roots of unity [SL96] states that every square submatrix of the DFT matrix (and hence also $M$) is nonsingular; see also [Tao04, Lemma1.3] and

<footnote n="4">⁴Specifically, in the case $k = n$, the homogeneous component of degree $k$ of the polynomial $f$ is exactly the determinant of the circulant matrix of first row $(x_1, \dots, x_n)$.</footnote>
<figure><img src="image_2.png" /><figcaption>Figure 1: The matrix M with $(j,i)$-th entry $\omega^{j\pi^{(i)}}$, corresponding to the natural variable order. The highlighted submatrices $M_A$ and $M_B$ are used in the analysis of evaluation dimension.</figcaption></figure>

[Fre04]. Since $|U| = (k-1)/2$, we can fix a subset $A \subseteq \{0, \dots, k-1\}$ of size $(k-1)/2$ such that the set $\{\ell_j(\mathbf{u})\}_{j \in A}$ corresponds to a square submatrix $M_A$ of $M$. Such a submatrix $M_A$ is non-singular due to Chebotarev's theorem. Consequently, the set $\{\ell_j(\mathbf{u})\}_{j \in A}$ is linearly independent. We can assume that $\ell_i(\mathbf{u}) = u_i$ for $i \in A$, since an invertible linear transformation on the variables in $U$ does not change the evaluation dimension $\mathrm{evalDim}_{U,V}(f')$.

Consider any $B \subseteq A$. By Chebotarev's theorem, the submatrix $M_B$ with rows indexed by $B$ and columns $v_2, \dots, v_{|B|+1}$ is invertible (the choice $|A| = (k-1)/2$ ensures that $V$ contains enough variables). So, for any $b \in \mathbb{F}$, there is a unique point $\beta_{B,b} \in \mathbb{F}^{|B|}$ such that for any $j$ in $B$, $\ell'_j(b, \beta_{B,b}, 0, \dots, 0) + 1 = 0$. Similarly, for any other row index $\tilde{j} \in \{0, \dots, k-1\} \setminus B$, there exists a unique point $\gamma_{B,\tilde{j}} \in \mathbb{F}^{|B|+1}$ such that for any $j$ in $B \cup \{\tilde{j}\}$, we have $\ell'_j(\gamma_{B,\tilde{j}}, 0, \dots, 0) + 1 = 0$. It follows that $\gamma_{B,\tilde{j}}$ is of the form $(b_{\tilde{j}}, \beta_{B,b_{\tilde{j}}})$ for a particular $b_{\tilde{j}} \in \mathbb{F}$.

Since $\mathbb{F}$ is infinite, we can choose $b$ in $\mathbb{F}$ outside of $\{b_{\tilde{j}} \mid \tilde{j} \in \{0, \dots, k-1\} \setminus B\}$, and define $\alpha_B := (b, \beta_{B,b}, 0, \dots, 0)$. For any $j$ in $\{0, \dots, k-1\}$:

$$ \ell'_j(\alpha_B) + 1 = 0 \iff j \in B. $$

Consequently $f'(\mathbf{u}, \alpha_B) = (\prod_{j \in B} u_j) \cdot (\prod_{j \in [k] \setminus B} (\ell_j(U) + c_{B,j}))$ where the $(c_{B,j})_{j \notin B}$ are non-zero constants. Since for each $B$, $f'(\mathbf{u}, \alpha_B)$ has a distinct lowest degree monomial $(\prod_{j \in B} u_j)$, the set $\{f'(\mathbf{u}, \alpha_B) \mid B \subseteq A\}$ is linearly independent. Therefore,

$$ \mathrm{evalDim}_{U,V}(f') \ge \dim \{f'(\mathbf{u}, \alpha_B) \mid B \subseteq A\} = 2^{(k-1)/2}. $$

By the evaluation-dimension lower bound of Theorem 2.7, any roABP computing $f$ (in any order) must have width at least $2^{(k-1)/2}$. $\square$

*Remark 4.5.* A close look at the above proof reveals that the lower bound also applies to the
circulant polynomial $\prod_{j=0}^{k-1} (\sum_{i=1}^{n} y_i \omega^{ij})$ which is exactly the determinant of the circulant matrix.

The lower bound established in Lemma 4.3 serves as the key technical ingredient needed to prove Theorem 2.

**Theorem 2.** The following holds over fields of characteristic zero. Let $n \in \mathbb{N}$ be a parameter. There exists an $n$-variate polynomial $f$ such that the symmetric polynomial $f_{\text{sym}} := f(\text{ESym}_n^1, \dots, \text{ESym}_n^n)$ is computable by an roABP of constant width in every variable order, but any roABP computing $f$ in any variable order must have width $2^{\Omega(n)}$.

*Proof.* Fix $k$ to be a prime number between $n/2$ and $n$. We consider the symmetric polynomial $f_{\text{sym}} := \sum_{d=0}^{n} \text{ESym}_n^d(x_1^k, \dots, x_n^k)$. By applying Equation 2.9 with each $x_i$ replaced by $x_i^k$, we obtain that $f_{\text{sym}}$ admits an roABP of constant width in every variable order. Moreover, by Lemma 4.3, the width of any roABP computing $f$ is at least $2^{(k-1)/2} = 2^{\Omega(n)}$. $\square$

## 4.2 $f$ is easy, but $f_{\text{sym}}$ is hard

To prove Theorem 3, it suffices to show the following technical lemma, which shows that taking powers of elementary symmetric polynomials is hard for roABPs. This lemma also implies Corollary 3.1 from the introduction. In Section 5.1, we will present an alternative proof of Theorem 3 using a quadratic polynomial based on graph-based polynomial from Section 3.

**Lemma 4.6 (Powers of ESym).** Let $k \le n/2$. Any roABP computing $(\text{ESym}_n^k)^d$ in any variable order requires width at least $(k+d)/2$.

**Theorem 3.** The following holds over fields of characteristic zero. Let $n \in \mathbb{N}$ be a parameter. There exists an $n$-variate polynomial $f$ computable by an roABP of constant width such that its respective symmetric polynomial $f_{\text{sym}} = f(\text{ESym}_n^1, \dots, \text{ESym}_n^n)$ requires an roABP of width $2^{\Omega(n)}$ in every variable order.

*Proof.* Let $k = \lfloor n/2 \rfloor$. Consider the polynomial $f(x_1, \dots, x_n) = x_k^k$. It is easy to see that $f$ can be computed by an roABP of constant width. However, by Lemma 4.6, any roABP computing the symmetrisation

$$f_{\text{sym}} = f(\text{ESym}_n^1, \dots, \text{ESym}_n^n) = (\text{ESym}_n^k)^k$$

must have width at least

$$\binom{2\lfloor n/2 \rfloor}{\lfloor n/2 \rfloor} = \Omega(2^n/\sqrt{n}). \quad \square$$

**Remark 4.7.** We recall that $\text{ESym}_n^{\lfloor n/2 \rfloor}$ can be expressed as a sum of $n$ many products of univariate polynomials (see Proposition 2.12). Consequently, using the multinomial theorem, it follows that $(\text{ESym}_n^{\lfloor n/2 \rfloor})^{\lfloor n/2 \rfloor}$ can be expressed as a sum of at most $O(2^{1.5n})$ many products of univariate polynomials. Hence, the bound we obtain in Theorem 3 is almost optimal.
Proof of Lemma 4.6. Assume that $(e_k)^d$ is computed by an roABP of width $w$ and variable order $\pi$. Let $Y = \{x_{\pi(1)}, \dots, x_{\pi(k)}\}$ and $Z = X \setminus Y$ be a partition of the variables $X$. By Theorem 2.7, we know that

$$w \geq \mathrm{evalDim}_{Y,Z}((e_k)^d).$$

Using Lemma 2.11, and the multinomial theorem, we can write the powers of the elementary symmetric polynomial $e_k$ as follows:

$$ \begin{aligned} (e_k(X))^d &= \left( \sum_{t=0}^{k} e_t(Y) \cdot e_{k-t}(Z) \right)^d \\ &= \sum_{\substack{t_0+\dots+t_k=d \\ t_i \ge 0}} \binom{d}{t_0, \dots, t_k} (e_0^{t_0}(Y) \cdots e_k^{t_k}(Y)) \cdot (e_{k-0}^{t_0}(Z) \cdots e_{k-k}^{t_k}(Z)). \end{aligned} \quad (4.8) $$

To argue about the evaluation dimension of $(e_k(X))^d$, we will need the following elementary fact from linear algebra.

**Fact 4.9.** If a matrix $M = \sum_{i=1}^r u_i v_i^T$ where $\{u_1, \dots, u_r\}$ and $\{v_1, \dots, v_r\}$ are linearly independent sets of vectors, then $M$ has rank exactly $r$.

To use the above fact, we note that the algebraic independence of the elementary symmetric polynomials (a consequence of Theorem 2.10) implies that the sets

$$E = \{e_0^{t_0}(Y) \cdots e_k^{t_k}(Y) : t_0 + \cdots + t_k = d\} \text{ and } \tilde{E} = \{e_{k-0}^{t_0}(Z) \cdots e_{k-k}^{t_k}(Z) : t_0 + \cdots + t_k = d\}$$

are both linearly independent sets of polynomials. Further, each term on the right-hand side of Equation 4.8 (corresponding to a tuple $(t_0, \dots, t_k)$ summing to $d$) has an evaluation matrix that is the outer product of the coefficient vectors of the corresponding polynomials in $E$ and $\tilde{E}$, scaled by a suitable multinomial coefficient (which is non-zero because we have assumed that the characteristic of the underlying field is 0). This implies that the evaluation matrix of $(e_k(X))^d$ has rank exactly the number of terms which is $\binom{k+d}{k}$. $\square$

# 5 Non-closure corollaries for roABP

We will now give the proofs of corollaries stated in Section 1.1. We use observations from the earlier sections to show that operations such as powering, computing resultant, and discriminant can be hard for roABP.

## 5.1 Hardness of Powering: a second example

In this section, we give a second proof of (a slightly weaker form of) Corollary 3.1. Note that we already proved this in the form of Lemma 4.6. By Proposition 2.12 and the following remark, we
know that $ESym_{2n}^n$ admits a roABP of width $O(n)$ in any variable order. On the other hand, any roABP that computes $(ESym_{2n}^n)^d$ must have width at least $\binom{n+d}{n}$.

Inspired by the graph-based polynomial which was used to prove factor non-closure in Section 3, we can even define a quadratic polynomial $Q$ and prove that powering $Q$ is hard for this polynomial roABP. The lower bound we obtain is slightly weaker, but the example is even simpler since $Q$ is just a quadratic polynomial, as opposed to the high-degree and high-sparsity elementary symmetric polynomial.

**Corollary 5.1 (Variant of Corollary 3.1).** The following holds over fields of characteristic zero. There exists an $n$-variate quadratic polynomial $Q$ computable by a roABP of width $O(n)$ such that for any $d$, any roABP computing $Q^d$ requires width at least $\binom{d+m}{m}$ in every variable order where $m = \Omega(n)$.

*Proof.* Let $G = (V, E)$ be a constant degree graph on $n$ vertices such that Lemma 3.1 holds. Define the quadratic polynomial:

$$Q_G = \sum_{(i,j) \in E} x_i x_j \qquad (5.2)$$

where variables $x_i$ correspond to the vertices of $G$. It is easy to observe that $Q_G$ can be computed by a roABP of width $|E| = O(n)$ in any variable order. We will prove that any roABP computing $Q_G^d$ must have large width.

Let $\pi$ be any variable order on the variables $X = \{x_1, \dots, x_n\}$, and consider the partition $Y = \{x_{\pi(1)}, \dots, x_{\pi(n/2)}\}$ and $Z = X \setminus Y$. Let $Y$ and $Z$ also denote the partition of vertices on $G$. By Lemma 3.1, there exists an induced matching $\mathcal{M}$ between $Y$ and $Z$ of size $\Omega(n)$. By renaming the variables if necessary we assume that the matching is between the vertices corresponding to $y_i$ and $z_i$ where $i \in [t]$ and $t = \Omega(n)$.

Define the polynomial:

$$\tilde{Q}^d = \left( \sum_{(i,j) \in \mathcal{M}} x_i \cdot x_j \right)^d = \left( \sum_{i \in [t]} y_i \cdot z_i \right)^d.$$

In particular, $\tilde{Q}^d$ is obtained from $Q_G^d$ by setting to zero the variables which are not in the matching $\mathcal{M}$. Hence, the rank of the Nisan matrix corresponding to $\tilde{Q}$ is a lower bound on the evaluation dimension of $Q$ w.r.t. the partition $(Y, Z)$.

By construction, for every monomial $m_Y$ of degree exactly $d$ over $Y$, there exists a unique monomial $m_Z$ over $Z$ such that the coefficient of $m_Y \cdot m_Z$ in $\tilde{Q}^d$ is nonzero (cf. Observation 2.4). Therefore,

$$\mathrm{rank}(M_{Y,Z}(Q_G^d)) \geq \mathrm{rank}(M_{Y,Z}(\tilde{Q}^d)) \geq \binom{d+t-1}{t-1}.$$

Applying Theorem 2.3, we obtain the desired lower bound on the width of any roABP computing $Q_G^d$. $\square$
## 5.2 Hardness of computing resultant and discriminant

We design a polynomial that is simple for roABP, but which turns out to be difficult for roABP when one computes its discriminant. This, in turn, immediately implies that computing resultant is also hard for roABP.

**Corollary 3.2 (roABP discriminant non-closure).** The following holds over fields of characteristic zero. For all $n$, there exists an $n$-variate polynomial $f(x, y)$ computable by an roABP of width $O(n)$ such that any roABP computing the discriminant $Disc_y(f)$ requires width at least $2^{\Omega(n)}$ in every variable order.

*Proof.* Let $g$ be an $(n-1)$-variate polynomial to which the lower bound in Corollary 3.1 is applicable. Fix any $d = \Omega(n)$. Define

$$f := y^d - g(x) \cdot y.$$

Then we have $\partial_y f = d \cdot y^{d-1} - g$. It is easy to see that the roots of $f$ are $\alpha_0 = 0$ and $\alpha_i = \omega^i \cdot g^{1/(d-1)}$ for $1 \le i \le d-1$, where $\omega$ is a primitive $(d-1)$-th root of unity. Here we work over a suitable field extension of the base field $\mathbb{F}$ to ensure that we have an $(d-1)$-th root of unity.

The discriminant of $f$ is defined as the resultant of $f$ and $\partial_y f$ with respect to $y$, i.e., $Disc_y(f) = \text{Res}_y(f, \partial_y f)$. Then using Observation 2.16 we can compute:

$$ \begin{aligned} \text{Disc}_y(f) &= \prod_{i=0}^{d-1} \partial_y f(\alpha_i) = -g \cdot \prod_{i=1}^{d-1} (d-1) \cdot g \\ &= -(d-1)^{d-1} g^d. \end{aligned} $$

Thus, computing the discriminant of $f$ amounts to powering the polynomial $g$, for which we have the required lower bound by Corollary 3.1. The upper bound on the roABP complexity of $f$ follows from the one for $g$. $\square$

## 6 Conclusions and Open Problems

In this work, we proved that a width-$w$ roABP computes a polynomial whose irreducible factor requires roABPs of width at least $w^{\log^d}$, yielding a quasipolyomial separation. This showed that roABPs are not closed under factoring (see Section 3). A natural next step is to search for polynomials that exhibit an exponential separation between the roABP complexity of a polynomial and that of its factor.

Our non-factor closure proof relied on the idea that polynomials that are hard for the simpler sparse model but easy for roABPs can be transformed, using simple gadgets, into polynomials that are hard even for roABPs. This raises an intriguing question about the scope of such hardness lifting. Specifically, given a polynomial $f(x)$ of sparsity $s$, can we always lift using a gadget $\phi$ such that the composed polynomial $f(\phi \circ x)$ requires an roABP of size $\Omega(s)$?
One consequence of our study of graph-based polynomials and symmetric compositions is the proof that powering is hard for roABPs (see Section 5.1). This naturally raises the question in the other direction: does there exist a polynomial $f := g^d$ that is easy to compute by an roABP, while $g$ is hard for roABP? An affirmative answer would, once again, stand in sharp contrast to other models such as circuits, algebraic branching programs, and formulas, where low complexity of $f$ leads to low complexity of $g$. Interestingly, the analogous question for sparse polynomials was answered affirmatively for $d = 2$ in classical works by Rényi [Rén47] and Erdős [Erd49], and was subsequently extended to arbitrary $d$ in later works [CD91; Ver49].

**Acknowledgments.** The research in this paper was carried out during a visit of some of the authors to Université Savoie Mont Blanc. The authors thank the Laboratoire de Mathématiques (LAMA) at Université Savoie Mont Blanc, which is supported by the AAP GAFA project, for their hospitality and the conducive environment for research.

## References

[Agr+15] Manindra Agrawal, Rohit Gurjar, Arpita Korwar, and Nitin Saxena. "Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits". In: SIAM J. Comput. 44.3 (2015), pp. 669-697 (cited on page 4).

[AC06] Noga Alon and Fan R. K. Chung. "Explicit construction of linear sized tolerant networks". In: Discret. Math. 306.10-11 (2006), pp. 1068-1071 (cited on page 11).

[And+18] Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, and Ben Lee Volk. "Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs". In: ACM Trans. Comput. Theory 10.1 (2018), 3:1-3:30. arXiv: 1511.07136 (cited on pages 4, 5).

[AW24] Robert Andrews and Avi Wigderson. "Constant-Depth Arithmetic Circuits for Linear Algebra Problems". In: 2024 IEEE 65th Annual Symposium on Foundations of Computer Science—FOCS 2024. IEEE Computer Society, 2024, pp. 2367-2386 (cited on pages 2, 3).

[BDS22] C. S. Bhargav, Sagnik Dutta, and Nitin Saxena. "Improved Lower Bound, and Proof Barrier, for Constant Depth Algebraic Circuits". In: 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022, August 22-26, 2022, Vienna, Austria. Vol. 241. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, 18:1-18:16 (cited on page 2).

[Bha+24] Vishwas Bhargava, Pranjal Dutta, Sumanta Ghosh, and Anamay Tengse. "The Complexity of Order-Finding for ROABPs". In: CoRR abs/2411.18981 (2024). arXiv: 2411.18981 (cited on page 4).
[BG22] Vishwas Bhargava and Sumanta Ghosh. "Improved Hitting Set for Orbit of ROABPs". In: *Comput. Complex*. 31.2 (2022), p. 15 (cited on page 4).

[BT24] Vishwas Bhargava and Anamay Tengse. "Explicit Commutative ROABPs from Partial Derivatives". In: *44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2024, December 16-18, 2024, Gandhinagar, Gujarat, India*. Vol. 323. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, 10:1–10:15. arXiv: 2407.10143 (cited on pages 2, 4).

[Bha+25a] Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, and Shubhangi Saraf. "Closure under factorization from a result of Furstenberg". In: *CoRR abs/2506.23214* (2025). arXiv: 2506.23214 (cited on pages 2, 3).

[Bha+25b] Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, and Shubhangi Saraf. "Constant-depth circuits for polynomial GCD over any characteristic". In: *CoRR abs/2506.23220* (2025). arXiv: 2506.23220 (cited on pages 2, 3).

[BS21] Pranav Bisht and Nitin Saxena. "Blackbox identity testing for sum of special ROABPs and its border class". In: *Comput. Complex*. 30.1 (2021), p. 8 (cited on page 4).

[BDI21] Markus Bläser, Julian Dörfler, and Christian Ikenmeyer. "On the Complexity of Evaluating Highest Weight Vectors". In: *36th Computational Complexity Conference, CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (Virtual Conference)*. Vol. 200. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, 29:1–29:36 (cited on page 4).

[Blä+20] Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, and Nitin Saurabh. "Algebraic Branching Programs, Border Complexity, and Tangent Spaces". In: *35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbrücken, Germany (Virtual Conference)*. Vol. 169. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, 21:1–21:24 (cited on pages 2, 4).

[BJ19] Markus Bläser and Gorav Jindal. "On the Complexity of Symmetric Polynomials". In: *10th Innovations in Theoretical Computer Science Conference (ITCS 2019)*. Vol. 124. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019, 47:1–47:14 (cited on page 3).

[BC17] Ben Blum-Smith and Samuel Coskey. "The Fundamental Theorem on Symmetric Polynomials: History's First Whiff of Galois Theory". In: *College Mathematics Journal* 48.1 (2017), pp. 18–29. arXiv: 1301.7116 [math.HO] (cited on page 9).
[CT22] C. Ramya and Anamay Tengse. "On Finer Separations Between Subclasses of Read-Once Oblivious ABPs". In: 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Vol. 219. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, 53:1-53:23. arXiv: 2201.06432 [cs.CC] (cited on page 10).

[CKS19] Chi-Ning Chou, Mrinal Kumar, and Noam Solomon. "Closure Results for Polynomial Factorization". In: Theory Comput. 15 (2019), Paper No. 13, 34 (cited on page 2).

[CD91] Don Coppersmith and James Davenport. "Polynomials whose powers are sparse". In: Acta Arith. 58 (1991), pp. 79-87 (cited on page 20).

[CLO05] David A. Cox, John Little, and Donal O'Shea. Using Algebraic Geometry. 2nd ed. Vol. 185. Graduate Texts in Mathematics. New York, NY: Springer, 2005 (cited on page 11).

[DDS22] Pranjal Dutta, Prateek Dwivedi, and Nitin Saxena. "Demystifying the Border of Depth-3 Algebraic Circuits". In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). 2022, pp. 92-103 (cited on pages 2, 4).

[DS22] Pranjal Dutta and Nitin Saxena. "Separated borders: Exponential-gap fanin-hierarchy theorem for approximative depth-3 circuits". In: 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022. IEEE, 2022, pp. 200-211 (cited on pages 2, 4).

[DSY09] Zeev Dvir, Amir Shpilka, and Amir Yehudayoff. "Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits". In: SIAM J. Comput. 39.4 (2009), pp. 1279-1293 (cited on page 2).

[Erd49] Paul Erdős. "On the number of terms of the square of a polynomial". In: Nieuw Arch. Wiskunde (2) 23 (1949), pp. 63-65 (cited on page 20).

[For16] Michael Forbes. Some Concrete Questions on the Border Complexity of Polynomials. Video lecture, Workshop on Algebraic Complexity Theory (WACT), Tel Aviv. 2016 (cited on page 2).

[FSS14] Michael A. Forbes, Ramprasad Saptharishi, and Amir Shpilka. "Hitting sets for multilinear read-once algebraic branching programs, in any order". In: Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014. ACM, 2014, pp. 867-875 (cited on page 4).

[FS13] Michael A. Forbes and Amir Shpilka. "Quasip polynomial-Time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs". In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science—FOCS 2013. IEEE Computer Soc., Los Alamitos, CA, 2013, pp. 243-252. arXiv: 1209.2408 (cited on pages 4, 8).
[For+21] Michael A. Forbes, Amir Shpilka, Iddo Tzameret, and Avi Wigderson. "*Proof Complexity Lower Bounds from Algebraic Circuit Complexity*". In: *Theory Comput. 17* (2021), Paper No. 10, 88 (cited on page 5).

[For14] Michael Andrew Forbes. "*Polynomial Identity Testing of Read-Once Oblivious Algebraic Branching Programs*". PhD thesis. Massachusetts Institute of Technology, 2014 (cited on pages 7, 8).

[Fre04] P. E. Frenkel. "*Simple proof of Chebotarev's theorem on roots of unity*". In: (2004). arXiv: math/0312398 [math.AC] (cited on page 15).

[GG13] Joachim von zur Gathen and Jürgen Gerhard. *Modern Computer Algebra*. Third. Cambridge University Press, Cambridge, 2013 (cited on page 10).

[GK85] Joachim von zur Gathen and Erich L. Kaltofen. "*Factoring Sparse Multivariate Polynomials*". In: *J. Comput. Syst. Sci.* 31.2 (1985), pp. 265-287 (cited on pages 3, 5, 13).

[GG20] Zeyu Guo and Rohit Gurjar. "*Improved Explicit Hitting-Sets for ROABPs*". In: *Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020, August 17-19, 2020, Virtual Conference*. Vol. 176. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, 4:1-4:16 (cited on page 4).

[Gur+17] Rohit Gurjar, Arpita Korwar, Nitin Saxena, and Thomas Thierauf. "*Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs*". In: *Comput. Complex.* 26.4 (2017), pp. 835-880 (cited on page 4).

[HLW06] Shlomo Hoory, Nathan Linial, and Avi Wigderson. "*Expander graphs and their applications*". In: *Bulletin of the American Mathematical Society* 43.4 (2006), pp. 439-561 (cited on page 11).

[hui21] Achille hui. *Evaluating elementary symmetric polynomial at $n^{th}$ powers*. Mathematics Stack Exchange. 2021 (cited on pages 6, 13).

[Juk08] Stasys Jukna. "*Expanders and time-restricted branching programs*". In: *Theoretical computer science* 409.3 (2008), pp. 471-476 (cited on page 11).

[KI04] Valentine Kabanets and Russell Impagliazzo. "*Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds*". In: *Comput. Complexity* 13.1-2 (2004), pp. 1-46 (cited on page 2).

[Kal89] Erich Kaltofen. "*Factorization of Polynomials given by Straight-Line Programs*". In: *Adv. Comput. Res.* 5 (1989), pp. 375-412 (cited on page 3).

[KT90] Erich Kaltofen and Barry M. Trager. "*Computing with Polynomials given by Black Boxes for Their Evaluations: Greatest Common Divisors, Factorization, Separation of Numerators and Denominators*". In: *J. Symbolic Comput.* 9.3 (1990), pp. 301-320 (cited on page 3).
[KNS20] Neeraj Kayal, Vineet Nair, and Chandan Saha. "Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth-three Circuits". In: *ACM Trans. Comput. Theory* 12.1 (2020), 2:1–2:27 (cited on pages 2, 4).

[Lan02] Serge Lang. *Algebra*. Revised 3rd. Vol. 211. Graduate Texts in Mathematics. Springer, New York, NY, 2002 (cited on page 9).

[LST25] Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. "Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits". In: *Journal of the ACM* 72.4 (2025), pp. 1–35. ECCC: TR21-081 (cited on page 2).

[LR09] Richard J. Lipton and Ken W. Regan. *Arithmetic Complexity and Symmetry*. Blog post, Gödel’s Lost Letter and P=NP. 2009 (cited on page 3).

[Mer13] Mircea Merca. "A Convolution for Complete and Elementary Symmetric Functions". In: *Aequationes Mathematicae* 86.3 (2013), pp. 217–229 (cited on page 9).

[Nis91] Noam Nisan. "Lower Bounds for Non-Commutative Computation (Extended Abstract)". In: *Proceedings of the 23rd Annual ACM Symposium on Theory of Computing*, May 5-8, 1991, New Orleans, Louisiana, USA. ACM, 1991, pp. 410–418 (cited on pages 2, 4, 5, 7).

[NW94] Noam Nisan and Avi Wigderson. "Hardness vs. Randomness". In: *J. Comput. System Sci.* 49.2 (1994), pp. 149–167 (cited on page 2).

[RS05] Ran Raz and Amir Shpilka. "Deterministic polynomial identity testing in non-commutative models". In: *Comput. Complex.* 14.1 (2005), pp. 1–19 (cited on page 4).

[RVW00] Omer Reingold, Salil P. Vadhan, and Avi Wigderson. "Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors". In: *41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA*. IEEE Computer Society, 2000, pp. 3–13 (cited on page 11).

[Rén47] Alfréd Rényi. "On the minimal number of terms of the square of a polynomial". In: *Hungarica Acta Math* 1 (1947), pp. 30–34 (cited on page 20).

[RGR22] Susanna F. de Rezende, Mika Göös, and Robert Robere. "Guest Column: Proofs, Circuits, and Communication". In: *SIGACT News* 53.1 (2022), pp. 59–82. arXiv: 2202.08909 (cited on page 5).

[ST24] Chandan Saha and Bhargav Thankey. "Hitting Sets for Orbits of Circuit Classes and Polynomial Families". In: *ACM Trans. Comput. Theory* 16.3 (2024), 14:1–14:50. ECCC: TR21-015 (cited on page 4).

[Sap21] Ramprasad Saptharishi. *A Survey of Lower Bounds in Arithmetic Circuit Complexity*. GitHub repository, version 9.0.3. A community curated survey. 2021 (cited on page 8).
[SW01] Amir Shpilka and Avi Wigderson. "Depth-3 arithmetic circuits over fields of characteristic zero". In: *Comput. Complex*. 10.1 (2001), pp. 1–27 (cited on pages 9, 10).

[ST21] Amit Sinhababu and Thomas Thierauf. "Factorization of Polynomials given by Arithmetic Branching Programs". In: *Comput. Complexity*. 30.2 (2021), Paper No. 15, 47 (cited on page 3).

[SL96] P. Stevenhagen and H. W. Lenstra. "Chebotarëv and His Density Theorem". In: *The Mathematical Intelligencer*. 18.2 (1996), pp. 26–37 (cited on page 14).

[Tao04] Terence Tao. "An uncertainty principle for cyclic groups of prime order". In: (2004). arXiv: math/0308286 [math.CA] (cited on page 14).

[Ver49] W. Verdenius. "On the number of terms of the square and the cube of polynomials". In: *Indag. Math*. 11 (1949), pp. 459–465 (cited on page 20).