Is the Nabla Operator Easy? Circuit Complexity of Macdonald Operators via Closure Theorems

Algebraic combinatorics has a family of operators on symmetric polynomials whose outputs encode delicate statistics of lattice paths. Nabla ($\nabla$), Delta ($\Delta'_{e_k}$) and Theta ($\Theta_F$) are all defined as scalings of the Macdonald basis, a family of symmetric polynomials in $x_1,\dots,x_n$ with two extra parameters $q,t$. Applied to the elementary symmetric polynomial $e_n$, they produce polynomials such as $\nabla e_n$, which the Shuffle Theorem writes as a sum over labeled Dyck paths weighted by $q^{\text{area}}t^{\text{dinv}}$. No one knows whether these polynomials have small arithmetic circuits. An arithmetic circuit is a network of $+$ and $\times$ gates that computes a polynomial. The question is whether $\nabla e_n$ belongs to $\mathsf{VP}$, the algebraic analogue of "efficiently computable," or whether it is as hard as the permanent. Every known way to write it down has exponential size: the combinatorial sum over exponentially many labeled paths, or the expansion in a basis indexed by partitions of $n$.

This note proposes to settle where these operator outputs sit in the algebraic complexity hierarchy. The main tool is the closure theorems of algebraic complexity, which say that small circuits stay small under factoring, projection, and rewriting in the elementary basis. Those theorems cut in both directions here. For upper bounds, they supply a toolkit for simulating the plethystic operations from which the Macdonald operators are built. For lower bounds, they act as hardness-transfer devices: if $\nabla e_n$ were in $\mathsf{VP}$, then every factor of every specialization of it would also be in $\mathsf{VP}$. It would therefore be enough to exhibit one hard factor of one simple specialization.

Core Claim

Membership in $\mathsf{VNP}$, the algebraic analogue of $\mathsf{NP}$, comes for free. The Shuffle Theorem makes each coefficient of $\nabla e_n$ a count of labeled Dyck paths, so Valiant's criterion places the family in $\mathsf{VNP}$. The same holds for $\Delta'_{e_{n-k-1}}e_n$ through the rise version of the Delta conjecture, proved in A proof of the compositional Delta conjecture. The open question is the gap between $\mathsf{VNP}$ and $\mathsf{VP}$.

We claim this question can be attacked with a specific mechanism. The problem reduces to a single, precisely identifiable obstacle in composing operators, and closure-under-factoring results convert partial hardness into full hardness. Concretely, we will prove one of two dichotomy-style statements.

The first possible outcome is an upper bound. The Carlsson–Mellit Dyck path algebra, which the D'Adderio–Mellit proof uses to build $\Delta' e_n$ one path step at a time, can be simulated by circuits in which each step adds only polynomially many gates. That would put $\nabla e_n$ and the rise-Delta polynomials in $\mathsf{VP}$.

The second possible outcome is a lower bound. Some specialization of $q$, $t$ or the $x$-variables has an irreducible factor, or an elementary-basis witness, that is $\mathsf{VNP}$-hard. Closure then forces $\nabla e_n \notin \mathsf{VP}$ unless $\mathsf{VP}=\mathsf{VNP}$.

Either outcome would be new. Neither the factorization literature nor the symmetric-function literature has asked the question.

Relation to Prior Work

The closure machinery supplies our methods. Three papers establish that factors of small circuits have small circuits. Closure Results for Polynomial Factorization does this with Hensel lifting and depth reduction, covering $\mathsf{VP}$, $\mathsf{VNP}$, and bounded-depth circuits with a $d^{O(\sqrt d)}$ loss. Closure of VP under taking factors: a short and simple proof streamlines the argument with Newton iteration. Discovering the Roots extends it to formulas, branching programs, border classes, and factors of high-degree circuits with low-degree radical.

All three treat the input as an unstructured polynomial. We use them for a different purpose: as closure properties that make hardness transfer from a factor to the whole polynomial.

The closest intersecting paper is On the Complexity of Symmetric Polynomials. It shows that a symmetric polynomial's witness in the elementary basis costs at most $\tilde O(d^2 L(f_{\text{Sym}}) + d^2n^2)$, where $L$ is circuit size and $d$ is degree, by running Newton iteration on the roots of $\prod_i (T-x_i)$. We reuse this result twice. In the upper-bound direction, it converts between the $x$-representation and the $e$/power-sum representation, which is what makes plethystic substitutions like $X \mapsto X(1-q)$ circuit-implementable. In the lower-bound direction, it shows that a hard witness implies a hard symmetric polynomial. That paper never considers Macdonald-type operators; that is the gap we fill.

Two papers by Dutta et al., Homogeneous Algebraic Complexity Theory and Algebraic Formulas and Border complexity via elementary symmetric polynomials, use elementary symmetric polynomials as complete or hard gadgets. They show that variants of these polynomials are $\mathsf{VF}$-complete, and that Newton's identities yield obstructions. These papers motivate the lower-bound side: symmetric families can carry completeness. They also constrain it, because the reductions must survive the $S_n$-symmetry that $\nabla e_n$ carries.

The target objects come from the combinatorics side. The rise Delta proof (A proof of the compositional Delta conjecture) provides the step-by-step operator expression that we try to simulate. New identities for theta operators supplies alternative operator identities, possibly with shorter compositions. The degenerate cases give the specializations on which lower-bound attempts start. These are the Schröder case (The Schröder case of the generalized Delta conjecture) and the $t=0$ case, which collapses to ordered multiset partitions (The generalized Delta conjecture at t=0). The valley-version work (Some Consequences of the Valley Delta Conjectures) motivates a secondary application. Any small circuit for a valley enumerator would allow randomized symmetry testing far beyond brute-force sizes, since that paper's authors identify symmetry as the roadblock and On the Complexity of Symmetric Polynomials shows symmetry testing is equivalent to identity testing.

Research Program

The upper-bound track. We will first build a closure calculus for the primitive operations from which the Dyck path algebra operators are assembled. Each primitive gets explicit circuit-size accounting. The primitives are:

  • multiplication by a fixed symmetric function;
  • plethystic substitution $X\mapsto X(1-q)$, implemented by passing to power sums through the witness theorem and replacing $p_k$ by $(1-q^k)p_k$;
  • skewing by $h_k$, implemented as coefficient extraction in an extra variable $z$ of $f(x_1,\dots,x_n,z)$ via interpolation;
  • Demazure-type divided differences $(f - s_i f)/(y_i-y_{i+1})$ in the auxiliary variables $y_1,\dots,y_k$ of the Dyck path algebra, with the division removed by Strassen's method.

Each primitive alone keeps $\mathsf{VP}$ closed. The real difficulty is composition. Building $\Delta' e_n$ takes on the order of $n$ operator applications. Several primitives evaluate their input at two different substitutions, for example $f$ and $s_i f$. A naive composition therefore doubles the circuit at each step and reaches size $2^n$.

We regard this doubling as the crux. It has a direct analogue in factoring: naive root lifting also blows up, and Newton iteration escapes because quadratic convergence needs only $O(\log d)$ rounds. Our specific hypothesis is that the step operators can be regrouped so that the whole path-building product is computed by $O(\log n)$ rounds of repeated squaring on a matrix of polynomials. This is in the spirit of the all-roots Newton recurrence of Discovering the Roots. The state space would be kept small by truncating in the $y$-variables at each round, as closure proofs truncate power series.

The lower-bound track. We will use closure as a reduction tool. $\mathsf{VP}$ is closed under projection (setting variables to constants or linear forms), under taking factors, and, by the witness theorem, under passing to the elementary-basis witness. So $\nabla e_n\in\mathsf{VP}$ would imply that every factor of every specialization lies in $\mathsf{VP}$.

We will search specializations systematically. Candidates are $q$ or $t$ set to roots of unity, $q=-1$, and $x$-variables collapsed to few distinct values. For each specialization we compute factorizations and witnesses, looking for an irreducible piece that matches a known $\mathsf{VNP}$-complete family under projection. The permanent is one target; the parity-alternating elementary symmetric variants of Homogeneous Algebraic Complexity Theory and Algebraic Formulas are another.

Scope. $\nabla e_n$ is the primary target, with $\Delta'_{e_{n-k-1}}e_n$ second. The chromatic symmetric functions of Chromatic symmetric functions and H-free graphs are a stretch target, because the decomposition of $\nabla e_n$ over Dyck paths involves closely related graph-indexed symmetric functions. We will not attempt the $e$-positivity conjectures themselves.

Baselines

The naive reference point is the dense representation that a computer algebra system like SageMath would produce: $\nabla e_n$ expanded in the Schur or monomial basis. Its size grows like the number of partitions of $n$ times the $q,t$-degree range, and in explicit $x$-variables like $\binom{2n-1}{n}$ monomials. Our circuits must grow slower than this. We will measure gate counts from the same symbolic pipeline for $n$ up to the limit at which dense expansion still fits in memory.

The second baseline is direct evaluation of the Shuffle-Theorem sum over labeled Dyck paths, written as a circuit. Its size is roughly $(n+1)^{n-1}$ labelings times path overhead. This is the construction that witnesses $\mathsf{VNP}$ membership, so beating it is the minimum requirement for an interesting upper bound.

The strongest existing method is not a construction for these operators, since none exists. It is the witness-recovery bound of On the Complexity of Symmetric Polynomials, $L(f)\le\tilde O(d^2 L(f_{\text{Sym}})+d^2n^2)$, which we use as the per-primitive cost model for basis changes. No reported result was found on Lacuna for circuit size of $\nabla e_n$, $\Delta' e_n$ or $\Theta_F$ outputs at any $n$.

The ablation that isolates our key ingredient is the upper-bound pipeline run with naive sequential composition of Dyck path algebra operators, without the repeated-squaring regrouping. Its size should grow exponentially. Beating it means a fitted growth exponent that is polynomial in $n$ where the ablation's is exponential.

For fairness, all constructions will be emitted into one circuit format and counted with the same gate accounting. They will use the same field ($\mathbb{Q}(q,t)$ specialized at random rationals for evaluation checks) and receive the same wall-clock budget per $n$.

Why not just…?

Why not just find the combinatorial formula and stop? A combinatorial formula such as the Shuffle Theorem answers "what does it count," not "how hard is it to compute." Such a formula is exactly the $\mathsf{VNP}$ baseline above. Bijective methods also stall on the related symmetry questions, both for valley Delta (Some Consequences of the Valley Delta Conjectures) and for chromatic $e$-positivity (Chromatic symmetric functions and H-free graphs). Complexity classification is an orthogonal kind of information, and the combinatorics feeds it only as input.

Why not just expand in SageMath and read off the answer? Dense expansion measures the size of the output, not of the shortest computation. A polynomial with exponentially many monomials can still lie in $\mathsf{VP}$; $e_n$ itself is the obvious example. Chromatic symmetric functions and H-free graphs already reports that brute-force symbolic checking becomes infeasible for modest cases. We use computer algebra only as the ground-truth checker for our circuits at small $n$.

Why not just write a dynamic program over Dyck path prefixes? This is the real threat. If some prefix-state dynamic program has polynomially many states, it gives a branching-program upper bound directly. The Dyck path algebra would then be unnecessary except as a guide. The obstacle is that dinv is a pairwise, nonlocal statistic, so the naive state must remember labels and diagonal positions of earlier cars. The Dyck path algebra is essentially a compressed version of such a state, in which the auxiliary $y$-variables carry that memory. We will implement the best prefix dynamic program we can design as a separate baseline. If it matches our construction, we report that; the scientific question is answered either way.

Why not just invoke Valiant's criterion and call it $\mathsf{VNP}$? That places the family but says nothing about whether it is easy. Easy families such as $e_n$ and determinants also satisfy the criterion. The contribution is an upper or lower bound relative to $\mathsf{VP}$.

Proposed Experiments

The first decisive check is empirical growth. For $n$ from 2 up to the largest feasible size, we build circuits for $\nabla e_n$ and $\Delta'_{e_{n-k-1}}e_n$ with three methods: the naive-composition pipeline, the regrouped pipeline, and the best prefix dynamic program. We verify each circuit against SageMath expansions at small $n$, and at larger $n$ by random evaluation, as identity testing permits. We then fit growth curves.

Polynomial growth for the regrouped pipeline, alongside exponential growth for the ablation, would be strong evidence for the upper-bound hypothesis and would guide the proof. Exponential growth under every method would redirect effort to the lower-bound track.

The second decisive check is a search for hard factors. For each specialization in our grid, we factor the specialized polynomial and compute its elementary-basis witness. We test whether any irreducible piece projects to the permanent or to the hard symmetric families of Homogeneous Algebraic Complexity Theory and Algebraic Formulas. Any such piece, verified symbolically at several $n$, is a candidate for a general lower-bound proof through the closure theorems.

The third check applies to the valley Delta enumerator. If any small-circuit construction extends to it, we run randomized symmetry tests at values of $n$ beyond those reachable by dense expansion. This yields computational evidence, not proof, on the symmetry roadblock.

The symbolic benchmark ASyMOB (resource) targets calculus-style problems for language models and computer algebra systems, not circuit size. It does not fit this question, and we do not use it. There is no community benchmark here; the ground truth is exact symbolic agreement.