Deterministic Shift Equivalence Testing for Sparse Polynomials

Introduction

Shift Equivalence Testing (SET) asks the following seemingly simple question: Given two polynomials $f,g \in\mathbb{Q}[x_1,\ldots,x_n]$, decide whether there is a vector $\mathbf{a}=(a_1,\ldots,a_n) \in\mathbb{Q}^n$ such that

and output such a vector if it exists. The symbol $\equiv$ emphasizes that the equality is an identity of formal polynomials, not merely an equality of functions. Over $\mathbb{Q}$ these two notions coincide. The same is true, and the Taylor expansions used below remain valid, over any field of characteristic zero or characteristic larger than the degree under consideration. Note that shift equivalence is indeed an equivalence relation. It is reflexive, since $f$ can be transformed into itself by the zero shift. When $f(\mathbf{x}+\mathbf{a})=g(\mathbf{x})$, then also $f(\mathbf{x})=g(\mathbf{x}-\mathbf{a})$, so it is symmetric. And if shifting by a transforms $f$ into $g$ and shifting by $\mathbf{b}$ transforms $g$ into $h$, then $\mathbf{a}+\mathbf{b}$ transforms $f$ into $h$, giving transitivity.

The algorithmic problem of Shift Equivalence Testing first appeared in computer algebra and symbolic computation. Grigoriev [26] designed the first polynomial-time algorithms for this problem. He assumes that the polynomials are given in dense representation, as a list of all coefficients including those that are zero. For an $n$-variate polynomial of total degree at most $d$, this list contains $\binom{n+d}{d}$ coefficients. His deterministic characteristic-zero algorithm takes $n^{O(d)}$ time, so zero-padding a sparse input does not give a running time polynomial in the sparse parameters. Grigoriev also gives a randomized algorithm for large enough finite characteristic and a quantum algorithm for characteristic two.

For polynomials with few nonzero coefficients, a running time polynomial in the dense input size may be far larger than polynomial in the sparse input length. Dvir, Oliveira, and Shpilka [16] studied SET for polynomials represented compactly by arithmetic circuits. For instance, the determinant of an $n \times n$ matrix has $n!$ nonzero monomials and an arithmetic circuit of polynomial size. Dvir et al. give a randomized algorithm for SET with running time polynomial in the circuit size and the total degree $d$. Their algorithm also works with black-box access to $f$ and $g$ and bounds on their degree and circuit size. It proceeds by a reduction to polynomial identity testing.

The polynomial identity testing problem (PIT) is a famous problem in complexity theory. Given a polynomial $f \in\mathbb{Q}[x]$ as an arithmetic circuit $C$, is $f$ identically zero? There is a simple randomized polynomial-time algorithm for the problem based on the so-called Schwartz–Zippel lemma [38 Zip79], which essentially inserts a random point from a large enough set and checks whether it evaluates to zero. Derandomizing PIT is a big open problem in complexity theory. In particular, it implies non-uniform circuit lower bounds [31], another major open problem in the field. Note that the algorithm by Dvir et al. shows that SET reduces to PIT under Turing reductions. But also the converse is true. The polynomial $f$ is identically zero iff it is shift-equivalent to the zero polynomial. Therefore, a full derandomization of SET is out of reach of current methods.

Since finding a deterministic algorithm for general PIT is a hard problem, researchers have developed deterministic identity tests for restricted circuit classes; see, e.g., [15]. For read-once oblivious algebraic branching programs (ROABPs), white-box PIT is deterministic polynomial time [37], while deterministic black-box PIT is known in quasipolynomial time [18, 19]. The framework of Dvir, Oliveira, and Shpilka [16] therefore gives the corresponding white-box and black-box SET algorithms for ROABPs.

Their deterministic reduction requires closure properties. Sparse polynomials are not closed under shifts, so it does not apply directly and DOS’14 states no deterministic sparse-class algorithm. Indirectly, however, representing both explicit sparse inputs as ROABPs in one common variable order and using white-box ROABP PIT gives deterministic SET with $\operatorname{poly}(n,s,t,d)$ arithmetic complexity. This is not polynomial in the binary sparse input size when $d$ is exponential.

Our contribution is a deterministic algorithm polynomial in the length of explicit sparse input over $\mathbb{Q}$. We now specify this input model. Each polynomial is given as an explicit list of nonzero terms

where the coefficient is given explicitly in binary representation. Furthermore, the exponents are also encoded in binary. We call this an explicit sparse representation. Thus, the natural input parameters are the number of variables $n$, the sparsities $s=\operatorname{sp}(f)$ and $t=\operatorname{sp}(g)$, the height, equivalently bit-size, of the coefficients of $f,g$, and $\log d$, where $d$ bounds the total degrees of $f$ and $g$. (Sometimes, the maximum bit-size of the coefficients is called logarithmic height, but we use the term height for brevity.) While low degree is conventional in algebraic complexity, high degree is natural for sparse or lacunary polynomials: an exponent bounded by $d$ uses only $O(\log d)$ bits. Classical sparse interpolation likewise targets this regime: Ben-Or–Tiwari has algebraic-RAM complexity polynomial in $\log d$ [10], and Garg–Schost obtains such dependence under straight-line-program access [27]. The indirect deterministic ROABP algorithm described above has polynomial dependence on $d$, so it does not give polynomial time in the binary sparse input length.² Our algorithm reduces the degree dependence to $\operatorname{poly}(\log d)$ for explicit sparse inputs and also provides polynomial bit complexity over $\mathbb{Q}$.

More formally, let Sparse SET denote the following problem: given two polynomials $f,g \in\mathbb{Q}[x_1,\ldots,x_n]$ in sparse representation, decide whether there exists a shift $\mathbf{a} \in\mathbb{Q}^n$ such that

As mentioned above, PIT for sparse polynomials is trivial in the sparse representation: one simply compares the monomial list with the zero list. The issue is now that the sparsity is not preserved under shifts. A single monomial can become very large: if we define $\operatorname{supp}(\mathbf{a}) := \{i : a_i \ne0\}$, then

has exactly

nonzero monomials. This number can be exponential in the sparse input length, already for a single monomial and even when the exponents are given in unary. Thus, even if $f$ is sparse, the shifted polynomial $f(\mathbf{x}+\mathbf{a})$ may be dense. Dvir, Oliveira, and Shpilka [16 Section 6] pointed out precisely this obstruction: their methods “almost” give a quasipolynomial-time algorithm for shift equivalence of sparse polynomials, but the direct argument breaks down because sparse polynomials are not closed under shifts. For explicit sparse inputs, the indirect ROABP approach described above gives a deterministic algorithm using $\operatorname{poly}(n,s,t,d)$ arithmetic operations, which is not polynomial in the sparse input length when $d$ is exponential. This leads to the central question addressed in this paper.

In this paper, we answer the question affirmatively. The first key ingredient is a new structural lemma showing that, in yes instances, the witnessing shift is very special, which forces the relevant intermediate polynomials to remain sparse. This addresses the problem that sparse polynomials are not closed under shifts.

The second problem stems from the fact that the algorithm in [16] has running time polynomial in $d$, so there is no easy way of adapting this algorithm to a running time of $\operatorname{poly}(\log d)$. The algorithm of [16] iteratively solves a system of equations yielding certain intermediate polynomials. We modify this approach in a nontrivial manner by showing that it is enough to store and compare all intermediate polynomials in the sparse representation without expanding arbitrary shifts.

There are also further obstacles. Even in yes instances over $\mathbb{Q}$, one must first show that there exists a witnessing shift $\mathbf{a}$ in $\mathbb{Q}^n$, rather than only over an algebraic extension³. One must then prove that such a shift has polynomially bounded bit complexity in the input size, and for the search version, compute and output it within the same bounds.

Our results

Our main theorem is a deterministic algorithm for shift equivalence of explicitly given sparse multivariate polynomials over the rationals, with running time polynomial in the sparse input parameters. We also prove polynomial bit complexity and output a shift of polynomial bit-size.

For an extension field $\mathbb{K} \supseteq\mathbb{Q}$, define

In particular, $S_{f,g}(\overline{\mathbb{Q}})$ denotes the set of shifts over the algebraic closure. The rationality result below shows that if $S_{f,g}(\overline{\mathbb{Q}})$ is nonempty, then it contains a rational point. Thus, for the rational decision problem, we may write

without changing the decision problem.

We state the main results over $\mathbb{Q}$ to keep the notation simple. The structural statements and arithmetic algorithms are purely algebraic and remain valid over any field $\mathbb{K}$ of characteristic zero or characteristic larger than $d$, after replacing $\mathbb{Q}$ by $\mathbb{K}$ and omitting the height and bit-complexity assertions.

The arithmetic algorithm is proved in Theorem 4.3. The bit-complexity analysis over $\mathbb{Q}$ is given in proposition 4.4, and the polynomial-height output guarantee uses the small rational witness theorem, Theorem 1.5. This exponentially improves on the indirect ROABP consequence of the DOS’14 framework described above, whose running time has polynomial dependence on $d$, rather than on $\log d$. In addition, that framework does not by itself address the existence of a rational shift of polynomial bit-size. Thus both the $\operatorname{poly}(n,s,t,\log d)$ arithmetic bound and the bit-complexity guarantee require additional ideas.

Black-box access. Over $\mathbb{Q}$, given separate evaluation oracles for $f,g$ promised to be sparse, Ben-Or–Tiwari interpolation [10] recovers their explicit representations using $\operatorname{poly}(n,s,t,\log d)$ queries and algebraic-RAM operations. This model permits unit-cost integer remainder operations in addition to arithmetic, and oracle calls are counted at unit cost. Applying Theorem 1.2 to the reconstructed representations gives the same bound in this model. This does not imply the same bit bound: evaluating $x^d$ at $2$ already returns a $(d+1)$-bit integer. For integer coefficients of magnitude at most $H$, the modular oracle of Bläser–Jindal [BJ14] yields deterministic $\operatorname{poly}(n,s,t,\log d,\log H)$ bit-complexity interpolation. Division-free integer circuits simulate this oracle by evaluating each gate modulo the queried modulus; the cost of this simulation also depends on the circuit description size.

The first key technical ingredient is the following sparsity bound. It rules out the possibility that, in a yes instance, the sparse output is obtained only by cancellations among large shifted monomial expansions.

In fact, the theorem we prove is much stronger than the statement above. It applies already when $g(\mathbf{x})$ and $f(\mathbf{x}+\mathbf{a})$ agree only in degrees at least some threshold $r$. In that case, for every monomial of $f$ of degree at least $r$, the part of its shifted expansion that can contribute to degrees at least $r$ has sparsity at most $st$. This truncated form is what is used during the degree-by-degree descent in the proof of Theorem 1.2; see Lemma 3.2. The stronger version is needed for our analysis to work.

Remark 1.4. The inequality in Theorem 1.3 does not bound the total degree of $f$ or $g$. It only bounds the exponents in the coordinates in which the shift is nonzero. This is the relevant restriction for sparse representation: variables outside $\operatorname{supp}(\mathbf{a})$ do not create binomial expansions, while a monomial $\mathbf{x}^{\boldsymbol{\gamma}}$ expands into

terms in the shifted coordinates. Thus, the theorem does not say anything about how large the exponents in variables outside the support of the shift could be; it rules out a large binomial expansion in the shifted coordinates.

The second ingredient, needed for bit complexity over $\mathbb{Q}$, is that a small rational witness always exists. This is not automatic from the existence of an arbitrary shift: a priori, the solution set could contain only shifts over an algebraic extension, or contain rational shifts only with very large coordinates. We prove that neither obstruction occurs for sparse SET.

The proof of Theorem 1.5 is deferred to Appendix § 7. It uses the structural sparsity bound again. Once a shift exists, the structural theorem restricts the derivatives of $f$ in the shifted coordinates to a polynomial-dimensional space. Inside this space, the translation from $f$ to $g$ can be represented by a rational differential operator of polynomial height. Taking a finite logarithm of this operator and solving one linear system gives a rational shift of polynomial bit-size.

As a further corollary of the structural bound, we obtain a sparse-time white-box PIT algorithm for shifted-sparse expressions. Here the shifts are given explicitly.

The proof is given after Lemma 3.2 in § 3.2.

Remark 1.7. Without the structural theorem, the immediate deterministic approach gives only a bound that depends polynomially on $d$. Indeed, $f(\mathbf{x}+\mathbf{a})-g(\mathbf{x}+\mathbf{b})$ can be represented as a sum of products of univariate polynomials, and hence as a read-once oblivious algebraic branching program. Applying the white-box PIT algorithm of Raz and Shpilka [37] gives a deterministic verification algorithm using $\operatorname{poly}(n,s,t,d)$ arithmetic operations. The corollary above improves this to $\operatorname{poly}(n,s,t,\log d)$ by using the structural bound to keep the computation in sparse representation.

Proof Overview

We describe the main ideas behind the algorithm and the analysis. The algorithm is based on the homogeneous descent of [16]. Their framework gives efficient algorithms for low-degree arithmetic circuits, and in particular, its running time is polynomial in the degree bound. For sparse polynomials, however, the degree can be exponentially larger than its binary encoding, so polynomial dependence on $d$ is not sufficient.

Two additional issues have to be handled in the sparse setting. First, a sparse polynomial need not remain sparse after a shift: even $(x+a)^d$ has $d+1$ monomials, which is exponential in $\log d$. In several variables the blow-up can be $(d+1)^n$. Thus we cannot simply expand shifted monomials during the descent. Second, over $\mathbb{Q}$, an arithmetic algorithm is not enough: one must prove that a polynomial-height rational shift exists and that the algorithm can output such a small witness.

The [16] descent. Write $f_i:=H^i(f)$ and $g_i:=H^i(g)$ for the homogeneous components of degree $i$. For a vector $\mathbf{v}\in\mathbb{Q}^n$, let