Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators

Abstract

Let ${\mathbb {F}}[X]$ be the polynomial ring in the variables X = {x₁,x₂,…,x_n} over a field ${\mathbb {F}}$. An ideal I = 〈p₁(x₁),…,p_n(x_n)〉 generated by univariate polynomials $\{p_{i}(x_{i})\}_{i=1}^{n}$ is a univariate ideal. Motivated by Alon’s Combinatorial Nullstellensatz we study the complexity of univariate ideal membership: Given $f\in {\mathbb {F}}[X]$ by a circuit and polynomials p_i the problem is test if f ∈ I. We obtain the following results.

• Suppose f is a degree-d, rank-r polynomial given by an arithmetic circuit where ℓ_i : 1 ≤ i ≤ r are linear forms in X. We give a deterministic time d^O(r) ⋅poly(n) division algorithm for evaluating the (unique) remainder polynomial f(X)modI at any point $\vec {a}\in {\mathbb {F}}^{n}$. This yields a randomized n^O(r) algorithm for minimum vertex cover in graphs with rank-r adjacency matrices. It also yields a new n^O(r) algorithm for evaluating the permanent of a n × n matrix of rank r, over any field $\mathbb {F}$.

• Let f be over rationals with $\deg (f)=k$ treated as fixed parameter. When the ideal $I=\left \langle {x_{1}^{e_{1}}, \ldots , x_{n}^{e_{n}}}\right \rangle$, we can test ideal membership in randomized O^∗((2e)^k). On the other hand, if each p_i has all distinct rational roots we can check if f ∈ I in randomized O^∗(n^k/2) time, improving on the brute-force $\left (\begin {array}{cc}{n+k}\\ k \end {array}\right )$-time search.

• If $I=\left \langle {p_{1}(x_{1}), \ldots , p_{k}(x_{k})}\right \rangle$, with k as fixed parameter, then ideal membership testing is W[2]-hard. The problem is MINI[1]-hard in the special case when $I=\left \langle {x_{1}^{e_{1}}, \ldots , x_{k}^{e_{k}}}\right \rangle$.

1 Introduction

Let X = {x₁,x₂,…,x_n} be a set of n commuting variables and ${\mathbb {F}}$ be a field which is either the field $\mathbb {Q}$ of rationals or a finite field throughout this paper. Let $R={\mathbb {F}}[X]$ be the ring of multivariate polynomials over the variables in X with coefficients from the field $\mathbb {F}$. A subring $I\subseteq R$ is an ideal if I absorbs multiplications by elements of R. That is, $I\cdot R\subseteq I$.

Computationally, an ideal I ⊂ R is given by a set of generator polynomials : $I = \left \langle {f_{1},f_{2},\ldots ,f_{\ell }}\right \rangle$. In other words, I is the smallest ideal containing the polynomials f_i,1 ≤ i ≤ ℓ. Given f ∈ R and $I=\left \langle {f_{1}, \ldots , f_{\ell }}\right \rangle$, the Ideal Membership problem is to decide whether f ∈ I or not. In general, the problem is notoriously intractable. It is EXPSPACE-complete even if f and the generators f_i,i ∈ [ℓ] are given explicitly as sums of monomials [26]. Nevertheless, special cases of ideal membership problem have played important roles in several results in arithmetic complexity. For example, the polynomial identity testing algorithm for depth three ΣπΣ circuits with bounded top fan-in; the structure theorem for ΣπΣ(k,d) identities use ideal membership very crucially [8, 18, 29].

In this paper, our study of ideal membership is motivated by Alon’s Combinatorial Nullstellensatz [1], and we recall one of its formulations.

Theorem 1.1

[1] Let ${\mathbb {F}}$ be any field, and $f(X)\in {\mathbb {F}}[X]$. Define polynomials $g_{i}(x_{i}) = {\prod }_{s\in S_{i}}(x_{i} - s)$ for non-empty subsets S_i,1 ≤ i ≤ n of ${\mathbb {F}}$. If f vanishes on all the common zeros of g₁,…,g_n, then there are polynomials h₁,…,h_n satisfying $\deg (h_{i})\leq \deg (f) - \deg (g_{i})$ such that $f={\sum }_{i=1}^{n} h_{i}g_{i}$.

It can be restated in terms of ideal membership: Let $f(X) \in {\mathbb {F}}[X]$ be a given polynomial, and $I=\left \langle {g_{1}(x_{1}),g_{2}(x_{2}),\ldots ,g_{n}(x_{n})}\right \rangle$ be an ideal generated by univariate polynomials g_i without repeated roots. Let Z(g_i) denote the zero set of g_i,1 ≤ i ≤ n. By Theorem 1.1, if f∉I then there is a $\vec {\alpha }=(\alpha _{1}, \ldots , \alpha _{n})\in Z(g_{1})\times \cdots \times Z(g_{n})$ such that $f(\vec {\alpha })\neq 0$. Of course, if f ∈ I then $f|_{Z(g_{1})\times \cdots \times Z(g_{n})}=0$.

Ideals I generated by univariate polynomials are called univariate ideals. For any univariate ideal I and any polynomial f, by repeated application of the division algorithm, we can write $f({X})={\sum }_{i=1}^{n} h_{i}({X}) g_{i}(x_{i}) + R({X})$ where R is unique and for each $i\in [n] : \deg _{x_{i}}(R) < \deg (g_{i}(x_{i}))$. Since the remainder is unique, it is convenient to write R = f mod I. By Alon’s theorem, if f∉I then there is a $\vec {\alpha }\in Z(g_{1}) \times {\cdots } \times Z(g_{n})$ such that $R(\vec {\alpha })\neq 0$.

Univariate ideal membership is further motivated by its connection with two well-studied problems. Computing the permanent of a n × n matrix over any field $\mathbb {F}$ can be cast in terms of univariate ideal membership. Given a matrix $A=(a_{i,j})_{1\leq i,j\leq n}\in \mathbb {F}^{n\times n}$, consider the product of linear forms $P_{A}({X}) = {\prod }_{i=1}^{n} \left ({\sum }_{j=1}^{n} a_{ij} x_{j}\right )$. The following observation is well known.

Fact 1.2

The permanent of the matrix A is given by the coefficient of the monomial x₁x₂⋯x_n in P_A. In other words, the remainder of the polynomial P_A(x₁,x₂,…,x_n) modulo the univariate ideal $\left \langle {{x_{1}^{2}}, \ldots , {x_{n}^{2}}}\right \rangle$ is precisely Perm(A) ⋅ x₁x₂⋯x_n.

It follows immediately that the remainder $P_{A} \text {mod}{\left \langle {{x_{1}^{2}}, \ldots , {x_{n}^{2}}}\right \rangle }$ evaluates to Perm(A) at the point $\vec {1}\in {\mathbb {F}}^{n}$.

Next, we briefly mention the connection of univariate ideal membership with the multilinear monomial detection problem, a benchmark problem that is useful in designing fast parameterized algorithms for a host of problems [21,22,23, 33].

Notice that, given an arithmetic circuit C computing a polynomial $f\in {\mathbb {F}}[X]$ of degree k, checking if f has a non-zero multilinear monomial of degree k is equivalent to checking if $f \text {mod}{\left \langle {{x_{1}^{2}}, \ldots , {x_{n}^{2}}}\right \rangle }$ is non-zero. Moreover, the constrained multilinear detection problem studied in [10, 22] can also be viewed as a problem of deciding membership in a univariate ideal.

However, even for univariate ideals, the ideal membership problem is hard in general. As an application of Theorem 1.1, Alon and Tarsi [1, 2] show that checking k-colorability of a graph G is polynomial-time equivalent to checking if the corresponding graph polynomial $f_{G}={\prod }_{ij\in E, i<j}(x_{i}-x_{j})$ is in the ideal $\left \langle {{x_{1}^{k}}-1, \ldots , {x_{n}^{k}}-1}\right \rangle$. Hence, univariate ideal membership is coNP-hard when the polynomials have distinct roots. We show that Univariate Ideal Membership over ${\mathbb {Q}}$, in general, is in the third level of the counting hierarchy. For the lower bound, we note that checking if a product of n linear forms is in the ideal $\left \langle {{x_{1}^{2}},{x_{2}^{2}},\ldots ,{x_{n}^{2}}}\right \rangle$ is as hard as checking if the integer permanent is zero, which is C₌P-hard. Univariate Ideal Membership over finite fields of characteristic k is quite tightly classified: the upper bound of coR ⋅Mod_kP nearly matches with the Mod_kP hardness.

1.1 Our Results

In this paper, we study univariate ideal membership problem for different parameters of the input polynomial f and the univariate ideal I. The first parameter we consider is the rank of f. This notion has found applications, for example, in algorithms for depth-3 polynomial identity testing [29].

Definition 1.3

We say $f\in {\mathbb {F}}[X]$ is a rank r polynomial if $f \in {\mathbb {F}}[\ell _{1} , \ell _{2} ,\ldots ,\ell _{r}]$ for linear forms ℓ_j : 1 ≤ j ≤ r.

We give two different algorithms for checking if a rank-r polynomial f is in a univariate ideal I. The first one is essentially an iterative division procedure. It evaluates the remainder polynomial f modI at a given point $\vec {\alpha }\in {\mathbb {F}}^{n}$ in deterministic time O^∗(d^O(r)). Using this evaluation procedure, we can test if the remainder polynomial f modI is nonzero by evaluating it at a randomly chosen point $\vec {\alpha }$ over $\mathbb {F}$ or a suitable extension field. The second algorithm is structural. It expresses the remainder polynomial f modI as an O^∗(d^O(r)) sum of d-products of linear forms. By the Polynomial Identity Lemma [14, 31, 34], we can check if it is nonzero by evaluation at a randomly chosen point $\vec {\alpha }$. We formally state the theorem.

Theorem 1.4

Let C be a polynomial-size arithmetic circuit computing a polynomial f in ${\mathbb {F}}[\ell _{1},\ell _{2},\ldots ,\ell _{r}]$, where ℓ₁,ℓ₂,…,ℓ_r are given linear forms in {x₁,x₂,…,x_n}. Let $I=\left \langle {p_{1}, \dots , p_{n}}\right \rangle$ be a univariate ideal generated by $p_{i}(x_{i})\in {\mathbb {F}}[x_{i}], 1\le i\le n$.

• 1. Given $\vec {\alpha }\in {\mathbb {F}}^{n}$, we can evaluate the remainder f modI at the point $\vec {\alpha }$ in deterministic time d^O(r)poly(n), where $d=\max \limits \{\deg (f),\deg (p_{i}): 1\le i\le n\}$.

• 2. In deterministic time d^O(r)poly(n) we can express the remainder f modI as an O^∗(d^O(r))-sum of d-products of linear forms.

Using either of these algorithms, we can decide in randomized O^∗(d^O(r)) time if f is in I.

We can check if f ∈ I by evaluating the remainder f modI at a randomly chosen point $\vec {\alpha }$, which can be done using any of the above algorithms.

We apply the previous result to obtain an efficient algorithm for minimum vertex cover in low rank graphs. A graph G is said to be of rank r if the rank of the adjacency matrix A_G is of rank r. Graphs of low rank were studied by Lovasz and Kotlov [4, 20] in the context of graph coloring.

Theorem 1.5

Given a graph G = (V,E) on n vertices such that the rank of the adjacency matrix A_G is at most r, and a parameter k, there is a randomized n^O(r) algorithm to decide if the graph G has vertex cover of size k or not.

Theorem 1.4 also yields an n^O(r) algorithm to compute the permanent of rank-r matrices over any field. Barvinok had given [9] an algorithm of same running time for the permanent of low rank matrices (over ${\mathbb {Q}}$) using apolar bilinear forms. By Fact 1.2, if matrix A is rank r then P_A is a rank-r polynomial, and for the univariate ideal $I=\left \langle {{x_{1}^{2}}, \ldots , {x_{n}^{2}}}\right \rangle$ computing P_AmodI at the point ${\vec {1}}$ yields the permanent. Theorem 1.4 works more generally for all univariate ideals. In particular, the ideal in the proof of Theorem 1.5 is generated by polynomials that are not powers of variables. Thus, Theorem 1.4 can potentially have more algorithmic consequences than the technique in [9].

If k is the degree of the input polynomial and the ideal is given by the powers of variables as generators, we have a randomized FPT algorithm for the problem.

Theorem 1.6

Given an arithmetic circuit C computing a polynomial $f(X) \in \mathbb {\mathbb {Q}}[X]$ of degree k and integers e₁,e₂,…,e_n, there is a randomized algorithm to decide whether $f \in \left \langle {x^{e_{1}}_{1},x^{e_{2}}_{2},\ldots ,x^{e_{n}}_{n}}\right \rangle$ in O^∗((2e)^k) time.

The above result generalizes the algorithm for multilinear monomial detection [23] (there the ideal of interest is $I=\left \langle {{x^{2}_{1}},{x^{2}_{2}},\ldots ,{x^{2}_{n}}}\right \rangle$). Brand et al. have given the first FPT algorithm for degree-k multilinear monomial detection in arithmetic circuits [11]. Multilinear monomial detection can also be done, with the same running time, using the Hadamard product [5] of the given polynomial with the elementary symmetric polynomial (and in a different approach using apolar bilinear forms [27]).

When the number of generators in the univariate ideal is treated as fixed parameter, ideal membership is W[2]-hard.

Theorem 1.7

Given a polynomial $f(X) \in \mathbb {F}[X]$ by an arithmetic circuit C and univariate polynomials p₁(x₁),p₂(x₂),…,p_k(x_k), checking if $f \not \in \left \langle {p_{1}(x_{1}),p_{2}(x_{2}),\dots ,p_{k}(x_{k})}\right \rangle$ is W[2]-hard with k as the parameter.

Theorem 1.7 is shown by an efficient reduction from parameterized the dominating set problem to ideal membership parameterized by number of generators. To find an dominating set of size k, the reduction produces an ideal with k univariates and the polynomial created from the graph has k variables.

Unlike Theorem 1.6, even checking if f is in the ideal $\left \langle {{x_{1}}^{e_{1}},{x_{2}}^{e_{2}},\ldots ,{x_{k}}^{e_{k}}}\right \rangle$ remains intractable in the parameterized sense.

Theorem 1.8

Let C be a polynomial-size arithmetic circuit computing a polynomial $f\in {\mathbb {F}}[X]$. Let $I = \left \langle {{x_{1}}^{e_{1}},{x_{2}}^{e_{2}},\ldots ,{x_{k}}^{e_{k}}}\right \rangle$ be the given ideal where e₁,…,e_k are given in unary, checking if f∉I is MINI[1]-hard with k as parameter.

The k−Lin-Eq problem, which asks if there is a $\vec {x}\in \{0,1\}^{n}$ satisfying $A\vec {x} = \vec {b}$, where $A\in \mathbb {F}^{k\times n}$ and $\vec {b}\in {\mathbb {F}}^{k}$, is reducible to the complement of univariate ideal membership for an ideal of the form $I = \left \langle {{x_{1}}^{e_{1}},{x_{2}}^{e_{2}},\ldots ,{x_{k}}^{e_{k}}}\right \rangle$. We then show k−Lin-Eq is hard for the parameterized complexity class MINI[1] by reducing the miniature version of 1 − in − 3POSITIVE3 − SAT to it.

As already mentioned, the result of Alon and Tarsi [1, 2] shows that the membership of f_G in $\left \langle {{x_{1}^{k}}-1, \ldots , {x_{n}^{k}}-1}\right \rangle$ is coNP-hard and the proof crucially uses the fact that the roots of the generator polynomials are all distinct. This naturally raises the question if univariate ideal membership is in coNP when each generator polynomial has distinct roots. We show univariate ideal membership is in coNP over rationals when all the generator polynomials have distinct roots. We show that over ${\mathbb {Q}}$ univariate ideal membership, in general, is in the third level of the counting hierarchy. This upper bound is reasonably tight, as checking if a product of n linear forms is in the ideal $\left \langle {{x_{1}^{2}},{x_{2}^{2}},\ldots ,{x_{n}^{2}}}\right \rangle$ is as hard as checking if the integer permanent is zero, which is C₌P-hard.

Theorem 1.9

Let $f\in \mathbb {Q}[X]$ be a polynomial of degree at most d given by a black-box. Let $I=\left \langle {p_{1}(x_{1}), \ldots , p_{n}(x_{n})}\right \rangle$ be an ideal given explicitly by a set of univariate polynomials p₁,p₂,…,p_n as generators of maximum degree bounded by d. Let L be the bit-size upper bound for any coefficient in f,p₁,p₂,…,p_n. Moreover, assume that p_is have distinct roots over $\mathbb {C}$. Then there is a non-deterministic algorithm running in time poly(n,d,L) that decides the non-membership of f in the ideal I.

Remark 1.10

The distinct roots case discussed in Theorem 1.9 is in stark contrast to the complexity of testing membership of P_A(X) in the ideal $\left \langle {{x_{1}^{2}}, \ldots , {x_{n}^{2}}}\right \rangle$. That problem is equivalent to checking if Perm(A) is nonzero for a rational matrix A, which is hard for the exact counting class C₌P. Hence it cannot be in coNP unless the polynomial-time hierarchy collapses. We do not have an analogue of Theorem 1.9 over finite fields.

Recall from Alon’s Nullstellensatz that if f∉I, then there is always a point $\vec {\alpha }\in Z(p_{1})\times \ldots \times Z(p_{n})$ such that $f(\vec \alpha )\neq 0$. Notice that in general the roots $\alpha _{i} \in \mathbb {C}$ and in the standard Turing Machine model the NP machine can not guess the roots directly with only finite precision. But we are able to prove that the NP machine can guess a corresponding tuple of root approximations$\vec {\tilde {\alpha }}\in \mathbb {Q}^{n}$, using only polynomial bits of precision and still can decide the non-membership. The main technical idea is to compute efficiently a parameter M (only from the input parameters) such that

$$ \begin{array}{@{}rcl@{}} |f(\vec{\tilde{\alpha}})| & \leq & M \textrm{ if } f\in I, \textrm{ and}\\ |f(\vec{\tilde{\alpha}})| & \geq & 2M \textrm{ if } f\not\in I. \end{array} $$

The NP machine decides the non-membership according to the final value of $|f(\vec {\tilde {\alpha }})|$.

In this connection, we note that Koiran has considered the weak version of Hilbert Nullstellensatz (HN) problem [19]. The input is a set of multivariate polynomials $f_{1}, f_{2}, \ldots , f_{m} \in \mathbb {Z}[X]$ and the problem is to decide whether $1\in \left \langle {f_{1}, \ldots , f_{m}}\right \rangle$. The result of Koiran shows that $\overline {{\text {HN}}}\in {\text {AM}}$ (under GRH), and it is an outstanding open problem problem to decide whether $\overline {\text {HN}}\in \text {NP}$.

Organization

In Section 2 we present some background material. In Section 3 we show that, in general, univariate ideal membership is in the counting hierarchy. We prove Theorems 1.4 and 1.5 in Section 4. In Section 5, we explore the parameterized complexity of univariate ideal membership. In the first subsection, we prove Theorem 1.6, and in the second subsection we prove Theorems 1.7 and 1.8. Finally, in Section 7, we prove Theorem 1.9.

2 Preliminaries

We recall some basic definitions and results that are background material.

2.1 Basics of Ideal Membership

Let ${\mathbb {F}}[X]$ be the ring of polynomials ${\mathbb {F}}[x_{1},x_{2},\ldots ,x_{n}]$. Let $I\subseteq {\mathbb {F}}[X]$ be an ideal given by a set of generators $I=\left \langle {g_{1}, \ldots , g_{\ell }}\right \rangle$. Then for any polynomial $f\in {\mathbb {F}}[X]$, it is a member of the ideal if and only if $f={\sum }_{i=1}^{\ell } h_{i} g_{i}$ where $\forall i : h_{i}\in {\mathbb {F}}[X]$. Dividing f by the g_i by applying the standard division algorithm does not work in general to check if f ∈ I. Indeed, the remainder is not even uniquely defined. However, if the leading monomials of the generators are already pairwise relatively prime, then we can apply the division algorithm to compute the unique remainder.

Theorem 2.1 (See 12, Theorem 3, proposition 4, pp.101)

Let I be a polynomial ideal given by a basis G = {g₁,g₂,⋯ ,g_s} such that all pairs i≠j LM(g_i) and LM(g_j) are relatively prime. Then G is a Gröbner basis for I.

In particular, if the ideal I is a univariate ideal given by $I=\left \langle {p_{1}(x_{1}), \ldots , p_{n}(x_{n})}\right \rangle$, we can apply the division algorithm to compute the unique remainder f modI. To bound the run time of this procedure we note the following: Let $\bar {p}$ denote the ordered list {p₁,p₂,…,p_n}. Let $\text {Divide}(f ; \bar {p})$ be the procedure that divides f by p₁ to obtain remainder f₁, then divides f₁ by p₂ to obtain remainder f₂, and so on to obtain the final remainder f_n after dividing by p_n. We note the following time bound for $\text {Divide}(f ; \bar {p})$.

Fact 2.2 (See [32], Section 6, pp.5-12)

Let $f\in {\mathbb {F}}[X]$ be given by a size s arithmetic circuit and $p_{i}(x_{i})\in {\mathbb {F}}[x_{i}]$ be given univariate polynomials. The running time of $\text {Divide}(f ; \bar {p})$ is bounded by $O(s\cdot {\prod }_{i=1}^{n} (d_{i} + 1)^{O(1)})$, where $d_{i}=\max \limits \{\deg _{x_{i}}(f),\deg (p_{i}(x_{i}))\}$.

2.2 Some Bounds Concerning Roots of Univariate Polynomials

The following folklore lemma gives a bound on the absolute value of any root of a univariate polynomial in terms of the degree and the coefficients.

Lemma 2.3

For any root α of a univariate degree-d polynomial $f(x) = {\sum }_{i=0}^{d} a_{i} x^{i}\in \mathbb {Q}[x]$ one of the following bounds hold:

$$ \frac{|a_{0}|}{{\sum}_{i=1}^{d} |a_{i}|} \leq |\alpha|<1 ~\mathrm{ or } ~ 1\leq |\alpha| \leq d \cdot \frac{\max_{i} |a_{i}|}{|a_{d}|}. $$

Proof

Since α is a root of f, we have $0=f(\alpha )={\sum }_{i=0}^{d} a_{i} \alpha ^{i}=0$. Hence, ${\sum }_{i=1}^{d} a_{i} \alpha ^{i} = -a_{0}$. By triangle inequality

$$ \sum\limits_{i=1}^{d} |a_{i}| |\alpha|^{i} \geq |a_{0}|. $$

Since f is degree d, a_d≠ 0. We consider two cases. First, suppose |α| < 1. Then, by the above inequality, $|\alpha | \cdot ({\sum }_{i=1}^{d} |a_{i}|) \geq |a_{0}|$. Hence, $|\alpha |\geq \frac {|a_{0}|}{{\sum }_{i=1}^{d} |a_{i}|}$. Next, suppose |α|≥ 1. Since $-a_{d} \alpha ^{d} = {\sum }_{i=0}^{d-1} a_{i} \alpha ^{i}$, by triangle inequality $|a_{d}| |\alpha |^{d} \leq |\alpha |^{d-1} \cdot ({\sum }_{i=0}^{d-1} |a_{i}|)$. Hence, $|\alpha | \leq \frac {{\sum }_{i=0}^{d-1} |a_{i}|} {|a_{d}|}\leq d \cdot \frac {\max \limits _{i} |a_{i}|}{|a_{d}|}$. This completes the proof. □

The next lemma, due to Mahler [25], lower bounds the distance between any two distinct roots of a univariate polynomial in terms of its degree and the size of its coefficients.

Lemma 2.4 (Mahler 25)

Let $g(x) = {\sum }_{i=0}^{d} a_{i} x^{i} \in \mathbb {Q}[x]$ and 2^−L ≤|a_i|≤ 2^L (if a_i≠ 0). Let α,β are two distinct roots of g. Then $|\alpha -\beta | \geq \frac {1}{2^{O(d L)}}$.

Given a univariate polynomial f and a point β that is far from the roots of f, the following lemma lower bounds |f(β)|. The following lemma states that any univariate polynomial can not get a very small value (in absolute sense) on any point which is far from every root.

Lemma 2.5

Let $f= {\sum }_{i=1}^{d} a_{i} x^{i}$ be a univariate degree-d polynomial with 2^−L ≤|a_i|≤ 2^L (if a_i≠ 0). Let $\tilde {\alpha }$ be a point such that $|\tilde {\alpha } - \beta _{i}| \geq \delta$ for every root β_i of f. Then

$$ |f(\tilde{\alpha})| \geq 2^{-L} \delta^{d}. $$

Proof

Since $\deg (f)=d$, a_d≠ 0. We can write $f(\tilde {\alpha }) = a_{d} {\prod }_{i=1}^{d} (\tilde {\alpha } - \beta _{i})$. Since $|\tilde {\alpha } - \beta _{i}| \geq \delta$, $|f(\tilde {\alpha })| = |a_{d}| {\prod }_{i=1}^{d} |\tilde {\alpha } - \beta _{i}| \geq 2^{-L} \delta ^{d}$. □

2.3 Parameterized Complexity Classes

We recall some standard definitions from parameterized complexity [13, ch.1,pp. 7-14]. For a parameterized problem the input instances are pairs (x,k), where x is the actual input and k is a fixed parameter. The parameterized problem is in the class FPT (for fixed parameter tractable) if the problem has an algorithm with run time f(k)|(x,k)|^O(1) for some computable function f.

A parameterized reduction [13, def. 13.1] between two parameterized decision problems P₁ and P₂ is a many-one reduction such that on input instance (x,k) of P₁ the reduction maps it to an instance $(x^{\prime },k^{\prime })$ of P₂ in time f(k)|(x,k)|^O(1), for some computable f, such that (x,k) is a “yes” instance of P₁ if and only if $(x^{\prime },k^{\prime })$ is a “yes” instance of P₂, and $k^{\prime } \leq f(k)$.

A parameterized problem is said to be in the class XP if it has an algorithm with run time |x|^f(k) for some computable function f.

For the purpose of this paper, it suffices to note that a parameterized problem L is in the class W[1] if there is a parameterized reduction from L to some standard W[1]-complete problem like, e.g., the k-Independent set problem and L is in the class W[2] if there is a parameterized reduction from L to some standard W[2]-complete problem like, e.g., the k-dominating set problem (more details can be found in, e.g, [13, def. 13.16]).

The complexity class MINI[1] consists of parameterized problems that are miniature versions of NP problems: For L ∈NP, its miniature version mini(L) has instances of the form (0ⁿ,x), where $|x|\le k\log n$, k is the fixed parameter, and x is an instance of L. Showing mini(L) to be MINI[1]-hard under parameterized reductions is evidence of its parameterized intractability, for it cannot be in FPT assuming the Exponential Time Hypothesis [15].

2.4 Multivariate Polynomials

We recall the definition of Hadamard product of two polynomials.

Definition 2.6

Given two polynomials $f,g \in {\mathbb {F}}[X]$, their Hadamard product is defined as

$$ f \circ g = \sum\limits_{m} [m]f \cdot [m]g \cdot m. $$

We will use a scaled variant of the Hadamard Product [7].

Definition 2.7

[7] Given two polynomials $f,g \in {\mathbb {F}}[X]$, their scaled Hadamard Product f ∘^sg, is defined as

$$ f \circ^{s} g = \sum\limits{m} m! \cdot [m]f \cdot [m]g \cdot m, $$

where $m=x^{e_{1}}_{i_{1}}x^{e_{2}}_{i_{2}} {\ldots } x^{e_{r}}_{i_{r}}$ and m! = e₁! ⋅ e₂!⋯e_r! abusing the notation.

Remark 2.8

If either f or g is multilinear, notice that their scaled Hadamard product coincides with their Hadamard product.

The elementary symmetric polynomial of degree k over n variables {x₁,x₂,…,x_n} is defined as:

$$ S_{n,k}(x_{1},x_{2},{\ldots} , x_{n}) = \sum\limits_{T\subseteq [n],|T| = k} \prod\limits_{i\in T}x_{i}. $$

Notice that, S_n,k contains all the degree k multilinear terms.

3 A Complexity-Theoretic Upper Bound

We show that over $\mathbb {Q}$ univariate ideal membership is in the counting hierarchy. Over finite fields of characteristic k, the problem is in the randomized complexity class coR ⋅Mod_kP.

Let Σ be a finite alphabet (of size at least 2). The class # P consists of functions $h:{\Sigma }^{*}\to {\mathbb {N}}$ defined by an NP machine M such that for all x ∈Σ^∗

$$ h(x)=\mathit{acc}_{M}(x), $$

where acc_M(x) is the number of accepting paths of M on input x. A language $L\subseteq {\Sigma }^{*}$ is in the counting complexity class C_=P if there is an NP machine M such that for all x ∈Σ^∗ x ∈ L if and only if acc_M(x) = rej_M(x). For $A\subseteq {\Sigma }^{*}$ the relativized class $\mathrm {C}_{{=}\mathrm {P}}^{A}$ is defined as above for an NP^A (oracle) machine M. For i ≥ 2, a language L is in the i^th level of the exact counting hierarchy, denoted CH_i, if $L\in \mathrm {C}_{=}\mathrm {P}^{A}$ for some A ∈CH_i− 1.

Theorem 3.1

• 1. Univariate ideal membership over $\mathbb {Q}$ is in the third level of the counting hierarchy.

• 2. Univariate ideal membership over a finite field of characteristic k is in coR ⋅Mod_kP.

Proof

For the first part, let $f\in \mathbb {Q}[X]$ be given as input by a degree d arithmetic circuit and $p_{i}(x_{i})\in \mathbb {Q}[x_{i}], i\in [n]$ be the generators of the ideal I. By clearing denominators, we can assume that both f and the p_i have integer coefficients. Writing f as an integer linear combination of monomials we have

$$ f = \sum\limits_{m:\deg(m)\le d} \alpha_{m} m, $$

where $\alpha _{m}\in \mathbb {Z}$ is the integer coefficient of monomial m (note that each α_m is polynomial size in binary). As the generators p_i are univariate we can express the remainder polynomial

$$ f \text{mod} {I} = \sum\limits_{m:\deg(m)\le d} \alpha_{m} (m \text{mod} {I}). $$

In particular, let $m=x_{1}^{e_{1}}\cdot x_{2}^{e_{2}}{\cdots } x_{n}^{e_{n}}$ and $r_{m,i}(x_{i})=x_{i}^{e_{i}}\text {mod}{p_{i}(x_{i})}$. Then, we have $m \text {mod} {I} ={\prod }_{i=1}^{n}r_{m,i}(x_{i})$, where $\deg (r_{m,i})<\deg (p_{i})$ for each i. Thus, the remainder polynomial

$$ f \text{mod} {I} = \sum\limits_{m:\deg(m)\le d} \alpha_{m} \prod\limits_{i=1}^{n}r_{m,i}(x_{i}). $$

In order to check if f modI is nonzero, noting that the degree of the remainder also is bounded by d, by Alon’s Nullstellensatz it suffices to check if there is a point $\vec {a}=(a_{1},a_{2},\ldots ,a_{n})$ in the n-dimensional grid [d + 1]ⁿ where f modI does not vanish.

We will be using the simple fact that we can compute in P^{# P} the coefficient of any monomial of degree at most d in f.

Let $L=\{(f,\{p_{i}\}_{i\in [n]},\vec {a})\mid f\in \mathbb {Z}[X], p_{i}(x_{i})\in \mathbb {Z}[X], \vec {a}\in [d+1]^{n}\ f \text {mod} {I}(\vec {a})\ne 0\}$. Checking if f∉I is clearly in NP^L: we guess the point $\vec {a}$ and verify that $(f,I,\vec {a})\in L$ by querying the oracle. We now show that $\overline {L}$ is in CH₂ and that completes the proof of the first part. To do so, we define an oracle NP machine M as follows:

• M guesses the monomials of degree at most d along its computation paths (each path corresponds to a unique monomial).

• On the computational path that guesses monomial m, M uses a # P oracle to compute its (integer) coefficient α_m in the polynomial f.

• Compute the remainder polynomial $m \text {mod} {I} ={\prod }_{i=1}^{n}r_{m,i}(x_{i})$. This computation path contributes $\alpha _{m}{\prod }_{i=1}^{n}r_{m,i}(x_{i})$ to the overall remainder.

• Compute $val(m)=\alpha _{m}{\prod }_{i=1}^{n}r_{m,i}(a_{i})$. If val(m) is negative then M produces |val(m)| many rejecting paths. Otherwise, M produces |val(m)| many accepting paths.

Notice that the overall remainder is $f \text {mod} {I} ={\sum }_{m} \alpha _{m} {\prod }_{i=1}^{n}r_{m,i}(x_{i})$. Clearly, $f \text {mod} {I}(\vec {a})=0$ if and only if the number of accepting paths equals the number of rejecting paths. Hence, $\overline {L}\in {\mathrm {C}_{=}\mathrm {P}}^{\#\mathrm {P}}$. Since $\mathrm {P}^{\#\mathrm {P}}\subseteq \text {coNP}^{\mathrm {C}_{=}\mathrm {P}}$, it follows that $\overline {L}\in \text {CH}_{2}$.

For the second part, the proof is along the same lines using the additional facts that $\text {Mod}_{k}\mathrm {P}^{\text {Mod}_{k}\mathrm {P}}=\text {Mod}_{k}\mathrm {P}$ for prime k, and $\text {NP}\subseteq \text {coR}\cdot \text {Mod}_{k}\mathrm {P}$ by the Valiant-Vazirani lemma. □

Remark 3.2

It is interesting to note that we have the lower bound (of C₌P for ${\mathbb {F}}=\mathbb {Q}$ and Mod_kP for ${\text {char}}({\mathbb {F}})=k, k>2$) for the simple case of checking if a product of linear forms is in the ideal $\left \langle {{x_{1}^{2}},{x_{2}^{2}},\ldots ,{x_{n}^{2}}}\right \rangle$, by virtue of the hardness of checking if the permanent is zero (over ${\mathbb {Q}}$ and ${\text {char}}(\mathbb {F})\ne 2$). We now observe a hardness result over ${\text {char}}(\mathbb {F})=2$ for the same ideal. Consider a graph G = (V,E). For each vertex v ∈ V define the monomial $star(v) = y_{v}{\prod }_{v\in e}x_{e}$, where x_e and y_v are edge and vertex variables. Now, we define the polynomial

$$ P=\prod\limits_{u=1}^{n}(1+ t\cdot star(u)), $$

where t is a new variable. Writing $P={\sum }_{d=0}^{n} P_{d}\cdot t^{d}$, consider the polynomial P_n/2 (for which we can find a small circuit from P). Then $P_{n/2}\text {mod}{\left \langle {\{{x_{e}^{2}}\mid e\in E\}}\right \rangle }$ is nonzero if and only if G has an independent set of size n/2. This holds over all fields ${\mathbb {F}}$ including ${\mathbb {F}}_{2}$.

4 Ideal Membership for Low Rank Polynomials

We first recall the notion rank of a polynomial in ${\mathbb {F}}[X]$.

Definition 4.1

A polynomial $f(X)\in {\mathbb {F}}[X]$ is a rank-r polynomial if there are linear forms ℓ₁,ℓ₂,…,ℓ_r in the variables X and an r-variate polynomial $g(z_{1},z_{2},\ldots ,z_{r})\in {\mathbb {F}}[z_{1},z_{2}\ldots ,z_{r}]$ such that

$$ f(X) = g(\ell_{1},\ell_{2},\ldots,\ell_{r}). $$

For an (unspecified) fixed parameter r, we refer to rank-r polynomials as low rank polynomials.

In this section we prove Theorem 1.4: Let $f(X){\mathbb {F}}[X]$ be a rank-r degree d polynomial given by an r-variate arithmetic circuit C and linear forms ℓ_i,i ∈ [r] such that f = C(ℓ₁,ℓ₂,…,ℓ_r), along with a univariate ideal I, and a point $\vec {\alpha }\in {\mathbb {F}}^{n}$ as inputs. We give a deterministic O^∗(d^O(r)) time algorithm to evaluate the remainder polynomial f modI at $\vec {\alpha }$ where d is the degree of the polynomial f. As corollary, this yields an O^∗(d^O(r))-time randomized algorithm for testing if f is in the ideal I.

Remark 4.2

Kayal [17] has shown a randomized polynomial-time algorithm for testing if a given polynomial $f(X)\in \mathbb {F}[X]$ is of a given rank r and, if so, to compute the linear forms ℓ₁,ℓ₂,…,ℓ_r and the polynomial g such that f(X) = g(ℓ₁,ℓ₂,…,ℓ_r). Combined with Theorem 1.4, we can obtain a randomized O^∗(d^O(r)) time algorithm with f and I given as input, with the promise that f has rank r.

We present two different algorithms as proofs for Theorem 1.4. The first is essentially a division algorithm. The second gives a circuit construction for the remainder polynomial f modI. Both algorithms have O^∗(d^O(r)) running time.

4.1 A Division Algorithm

Given $\vec {\alpha }\in {\mathbb {F}}^{n}$, a univariate ideal $I=\left \langle {p_{1}(x_{1}), \ldots , p_{n}(x_{n})}\right \rangle$, and a rank r polynomial f(ℓ₁,…,ℓ_r) we show how to efficiently evaluate the remainder polynomial f(ℓ₁,…,ℓ_r)modI at $\vec \alpha$ using a recursive procedure $\text {REM}(f(\ell _{1}, \ldots , \ell _{r}), I, \vec \alpha )$. We introduce the following notation. For $S\subseteq [n]$, let I_S denote the ideal $\left \langle {p_{i}(x_{i}) : i\in [S]}\right \rangle$ generated by the polynomials p_i(x_i),i ∈ S.

Let $g\in {\mathbb {F}}[X]$ be an n-variate polynomial. For an n × n invertible matrix T over ${\mathbb {F}}$, we define the polynomial

$$ T(g(X))=g(T(x_{1}),T(x_{2}),\ldots,T(x_{n})), $$

where $T(x_{i})={\sum }_{j=1}^{n} T_{ij}x_{j}, i\in [n]$.

The following lemma shows how to remove the redundant variables from a low rank polynomial. Let ℓ₁,ℓ₂,…,ℓ_r be homogeneous linear forms in X = {x₁,x₂,…,x_n}, f be an r-variate degree-d polynomial over $\mathbb {F}$, and consider f(ℓ₁,ℓ₂,…,ℓ_r). For an n × n invertible matrix T over ${\mathbb {F}}$, let T(f) denote the polynomial

$$ T(f)(X) = f(T(\ell_{1}),T(\ell_{2}),\ldots,T(\ell_{r})), $$

where $T(x_{i})={\sum }_{j=1}^{n} T_{ij}x_{j}, i\in [n]$, and each T(ℓ_j),j ∈ [r] is defined by linearity.

Lemma 4.3

Given as input a polynomial f(ℓ₁,…,ℓ_r) where ℓ₁,…,ℓ_r are given homogeneous linear forms in ${\mathbb {F}}[X]$, there is an invertible matrix $T\in {\mathbb {F}}^{n\times n}$ such that T(x_i) = x_i,1 ≤ i ≤ r and T(f) is defined on the 2r variables x₁,x₂,…,x_2r.

Proof

Write each linear form ℓ_i in two parts: ℓ_i = ℓ_i,1 + ℓ_i,2, where ℓ_i,1 is the part over variables x₁,…,x_r and ℓ_i,2 is over variables x_r+ 1,…,x_n. W.l.o.g, assume that $\{\ell _{i,2}\}^{r^{\prime }}_{i=1}$ is a maximum linearly independent subset of linear forms in $\{\ell _{i,2}\}^{r}_{i=1}$. Let T be the invertible linear map that fixes x₁,…,x_r, maps the independent linear forms $\{\ell _{i,2} \}^{r^{\prime }}_{i=1}$ to variables $x_{r+1},\ldots ,x_{r+r^{\prime }}$, and suitably extended to the remaining variables to form an invertible map. Clearly, T can be computed in polynomial time, given the ℓ_i. This completes the proof. □

The following lemma shows that evaluating the remainder of a polynomial f modulo a univariate ideal $I = \left \langle {p_{1}(x_{1}), \ldots , p_{n}(x_{n})}\right \rangle$ at a point in ${\mathbb {F}}^{n}$ can be done incrementally, by computing and evaluating the remainder modulo the smaller ideals I_[ℓ],1 ≤ ℓ ≤ n.

Lemma 4.4

Let $f(X)\in {\mathbb {F}}[X]$ and $I = \left \langle {p_{1}(x_{1}), \ldots , p_{n}(x_{n})}\right \rangle$ be a univariate ideal. Let R(X) be the unique remainder f modI. Let $\vec {\alpha }\in {\mathbb {F}}^{r}, r\leq n$ and R_r(X) = f modI_[r]. Then R(α₁,…,α_r,x_r+ 1,…,x_n) = R_r(α₁,…,α_r,x_r+ 1,…,x_n)modI_[n]∖[r].

Proof

By uniqueness of remainders modulo univariate ideals, it follows that R(X) = R_r(X)modI_[n]∖[r]. Since the ideal I_[n]∖[r] does not involve x₁,x₂,…,x_r, substituting x_i = α_i,1 ≤ i ≤ r we have

$$ R(\alpha_{1},\alpha_{2},\ldots,\alpha_{r},x_{r+1},\ldots,x_{n}) = R_{r}(\alpha_{1},\alpha_{2},\ldots,\alpha_{r},x_{r+1},\ldots,x_{n}) \text{mod} {I_{[n]\setminus[r]}}. $$

□

The next lemma is crucial for the proof of Theorem 1.4.

Lemma 4.5

Let $f\in {\mathbb {F}}[X]$, and $T : {\mathbb {F}}^{n}\rightarrow {\mathbb {F}}^{n}$ be an invertible linear transformation fixing x₁,…,x_r and mapping x_r+ 1,…,x_n to linearly independent linear forms over x_r+ 1,…,x_n. Write R = f modI_[r] and $R^{\prime } = T(f) \text {mod} {I_{[r]}}$. Then $R^{\prime } = T(R)$.

Proof

Let $f = {\sum }_{i=1}^{r} h_{i}(X) \cdot p_{i}(x_{i}) + R(X)$ and $T(f) = {\sum }_{i=1}^{r} h^{\prime }_{i}(X) \cdot p_{i}(x_{i}) + R^{\prime }(X)$. Note that for both remainder polynomials R and $R^{\prime }$, we have $\deg _{x_{i}}R < \deg _{x_{i}}(p_{i})$ and $\deg _{x_{i}}R^{\prime }< \deg (p_{i})$ for 1 ≤ i ≤ r. Now, as T is invertible and it fixes x₁,…,x_r, we can write $f = {\sum }_{i=1}^{r} T^{-1}(h^{\prime }_{i}({X})) \cdot p_{i}(x_{i}) + T^{-1}(R^{\prime }({X}))$. As T fixes each x_i,i ∈ [r] it follows that $\deg _{x_{i}}(T^{-1}(R^{\prime }(X))) < \deg (p_{i}(x_{i}))$ for 1 ≤ i ≤ r. Combining the two expressions for f, we obtain that

$$ (R - T^{-1}(R^{\prime})) = 0 \text{mod} {I_{[r]}} $$

which forces $R = T^{-1}(R^{\prime })$ by the degree bounds on x_i,i ∈ [r]. □

Proof of Theorem 1.4

We now describe the algorithm, prove its correctness and analyze its running time. The input to the algorithm is an arithmetic circuit computing the r-variate degree-d polynomial f, the linear forms ℓ₁,ℓ₂,…,ℓ_r, and the univariate polynomials p_i(x_i),i ∈ [n]. Let the positive integer L bound the encoding lengths of the coefficients of the linear forms and polynomials p_i as well as any scalar inputs to the circuit defining f. □

The algorithm can be seen as a recursive procedure REM: the initial call to it is $\text {REM}(f(\ell _{1}, \ldots , \ell _{r}), I_{[n]},\vec \alpha )$.

• As the first step, we apply the invertible linear transformation obtained in Lemma 4.3 to f and obtain the polynomial T(f) over the variables $x_{1}, \ldots , x_{r}, x_{r+1}, \ldots , x_{r+r^{\prime }}$ where $r^{\prime }\leq r$.¹

• The polynomial T(f) can be explicitly computed as a linear combination of degree d monomials in variables $x_{1},x_{2},\ldots ,x_{r+r^{\prime }}$ in time poly(L,s,n,d^O(r)).

• Then we compute the remainder polynomial $f^{\prime }(x_{1}, \ldots , x_{r + r^{\prime }}) = T(f) \text {mod} {I_{[r]}}$ by applying the division algorithm: it essentially amounts to replacing ${x_{i}^{e}}$ by ${x_{i}^{e}} \text {mod} p_{i}(x_{i})$ when $e\ge \deg (p_{i}(x_{i}))$ for any ${x_{i}^{e}}$ occurring in a monomial of T(f).

• Next we compute the polynomial $g(x_{r+1},\ldots ,x_{r+r^{\prime }})=f^{\prime }(\alpha _{1}, \ldots ,$ $\alpha _{r}, x_{r+1}, \ldots , x_{r+r^{\prime }})$. By Lemma 4.3, we have T^− 1(x_r+i) = ℓ_i,2 for $1\leq i\leq r^{\prime }$. Hence, $T^{-1}(f^{\prime })=g(\ell _{1,2},\ell _{2,2},\ldots ,\ell _{r^{\prime },2})$.

• We next consider the polynomial $g(\ell _{1,2},\ell _{2,2},\ldots ,\ell _{r^{\prime },2})$ and recursively compute $\text {REM}(g(\ell _{1,2}, \ldots , \ell _{r^{\prime },2}), I_{[n]\setminus [r]},\vec \alpha ^{\prime })$ where $\vec \alpha ^{\prime } = (\alpha _{r+1},\ldots ,\alpha _{n})$.

Correctness

Let R(X) = f modI_[n] be the unique remainder polynomial. Let R_r(X) = f modI_[r]. Then, by Lemma 4.4, we know that R_rmodI_[n]∖[r] = R, and that it suffices to show $g(\ell _{1,2}, \ldots , \ell _{r^{\prime },2}) = R_{r}(\alpha _{1}, \ldots , \alpha _{r}, x_{r+1}, \ldots , x_{n})$ as that would imply

$$ \text{REM}(g(\ell_{1,2}, \ldots, \ell_{r^{\prime},2}), I_{[n]\setminus[r]},\vec\alpha^{\prime}) = \text{REM}(f(\ell_{1},\ldots,\ell_{r},I_{[n]},\vec\alpha)= R(\alpha_{1},\alpha_{2},\ldots,\alpha_{n}), $$

showing the correctness of the recursion.

Let $R^{\prime }(x_{1},\ldots , x_{r}, x_{r+1}, \ldots , x_{n}) = T(f) \text {mod} {I_{[r]}}$. By Lemma 4.5 we have $R^{\prime } = T(R_{r})$ and hence $R_{r}= T^{-1}(R^{\prime })(x_{1},\ldots , x_{r}, T^{-1}(x_{r+1}), \ldots , T^{-1}(x_{n}))$. By definition of the linear map T, and substituting x_i = α_i,i ∈ [r], we have

$$ \begin{array}{@{}rcl@{}} g(\ell_{1,2}, \ldots, \ell_{r^{\prime},2}) & = & T^{-1}(R^{\prime})(\alpha_{1}, \ldots, \alpha_{r},T^{-1}(x_{r+1}), \ldots, T^{-1}(x_{r+r^{\prime}}))\\ &=& R_{r}(\alpha_{1}, \ldots, \alpha_{r}, x_{r+1}, \ldots, x_{n}). \end{array} $$

Running Time

In order to bound the running time of the above algorithm, we need to bound the total number of scalar arithmetic operations and the size of the scalars involved in the computations. We will bound the total number of arithmetic operations by poly(L,s,n,d^O(r)), where L bounds the encoding lengths of the scalars in the input and s is the size the input circuit for f.

First consider the case when ${\mathbb {F}}$ is a finite field. In that case, we can let L bound encodings of all elements of $\mathbb {F}$. We only need to bound the size of the polynomial $g(\ell _{1,2}, \ldots , \ell _{r^{\prime },2})$ and analyze the total number of operations.

Firstly, the polynomial T(f) can be explicitly computed from the input arithmetic circuit deterministically in time poly(L,s,n,d^O(r)), because it has at most $\left (\begin {array}{cc}{d+2r}\\ {2r} \end {array}\right )$ many monomials (as the number of variables is $r+r^{\prime }\le 2r$).

Next, notice that the polynomial $g(x_{r+1},\ldots ,x_{r+r^{\prime }})$ can also be written as a linear combination of at most $\left (\begin {array}{cc}{d+2r}\\ {2r} \end {array}\right )$ many degree-d monomials in $x_{r+1},\ldots ,x_{r+r^{\prime }}$. Thus, the polynomial $g(\ell _{1,2},\ell _{2,2},\ldots ,\ell _{r^{\prime },2})$ can be seen as a ΣπΣ circuit. In other words, it is a sum of at most $\left (\begin {array}{cc}{d+2r}\\ {2r} \end {array}\right )$ products of the linear forms ℓ_i,2, and the products are at most d-fold.

Further, notice that the number of divisions (by the univariate polynomials p_i(x_i),i ∈ [r]) performed in Step 3 is r per monomial of T(f). Since T(f) has at most $\left (\begin {array}{cc}{d+2r}\\ {2r} \end {array}\right )$ monomials the number of univariate polynomial divisions, and hence number of scalar operations, is bounded by poly(L,s,n,d^O(r)). All other steps require poly(s,n,d,L) operations.

Now, in each recursive application the number of generators in the ideal is reduced by at least one, and there is only one recursive call made.

Thus, the overall number of scalar (i.e., ${\mathbb {F}}$) operations involved in the algorithm is bounded by poly(L,s,n,d^O(r)).

The above analysis bounding the total number of operations also applies for ${\mathbb {F}}=\mathbb {Q}$. For $\mathbb {Q}$, we additionally need to bound the sizes of the numbers during the computation.

Bit-size Growth Over $\mathbb {Q}$

It suffices to argue that the size of coefficients in the polynomial $g(\ell _{1,2},\ell _{2,2},\ldots ,\ell _{r^{\prime },2})$ increase by a fixed additive value bounded by poly(n,d,L). As the total number of recursive calls is at most n, this would polynomially bound all scalars involved in the entire computation.

Let $\tilde {L}$ bound the coefficients of polynomial f(z₁,z₂,…,z_r). As $2^{\tilde {L}}\le 2^{Ld}\cdot {\left (\begin {array}{cc}{d+r}\\ r \end {array}\right )}$, we have $\tilde {L}\le dL+r\log (r+d)$.

We will show that the $\sum \prod \sum$ circuit that we use for g in the next recursive step has coefficients of bit size at most $\tilde {L} + \text {poly}(n,d,L)$.

For $h\in \mathbb {Q}[X]$, let c(h) denote the maximum coefficient (in absolute value) of a nonzero monomial of h. By direct expansion

$$ |c(f(\ell_{1},\ldots, \ell_{r}))| \leq 2^{\tilde{L} + \text{poly}(n,d,L)}. $$

Also the matrix T of Lemma 4.3, and its inverse, require poly(n,L) size entries.

Therefore, $c(T(f(\ell _{1},\ldots ,\ell _{r})) \leq 2^{\tilde {L} +\text {poly}(n,d,L)}$. Next, the algorithm expands T(f) explicitly as a sum of d^O(r) monomials. Dividing T(f) by the polynomials p₁(x₁),…,p_r(x_r) one by one, and substituting x₁ = α₁,…,x_r = α_r giving us the remainder polynomial $g(x_{r+1},\ldots ,x_{r+r^{\prime }})$. Each such division involves computing a remainder polynomial of the form ${x_{i}^{e}} \text {mod} p_{i}(x_{i})$ for some e ≤ d, which does not involve intermediate computations. Each such remainder ${x_{i}^{e}} \text {mod} p_{i}(x_{i})$ obtained has poly(n,d,L) size coefficients and degree at most $\deg (p_{i})-1$. Putting it together, it follows that $|c(g)| \leq 2^{\tilde {L} + \text {poly}(n,d,L)}$.

Now the algorithm passes the d^O(r) size ΣπΣ circuit $g(\ell _{1,2},\ldots ,\ell _{r^{\prime } , 2})$ (We note that $T^{-1}(x_{r+1})=\ell _{1,2},\ldots ,T^{-1}(x_{r+r^{\prime }})=\ell _{r^{\prime } , 2}$), univariates p_r+ 1(x_r+ 1),…, p_n(x_n) and the point (α_r+ 1,…,α_n) for the next recursive call.

In the recursive call $\text {REM}(g(\ell _{1,2}, \ldots , \ell _{r^{\prime },2}), I_{[n]\setminus [r]},\vec \alpha ^{\prime })$, notice that the only change in the input size is in the size of g (which, as shown above, is of O^∗(d^O(r)) size with L + poly(n,d,L) size coefficients).

As there are at most n recursive calls overall, all coefficients involved at intermediate stages are bounded by poly(n,d,L) for a fixed polynomial p.

Remark 4.6

Given a rank r polynomial f(ℓ₁,…,ℓ_r) and a univariate ideal $I = \left \langle {p_{1}(x_{1}),\ldots ,p_{n}(x_{n})}\right \rangle$, we can decide the membership of f in I by testing if the remainder polynomial f modI is identically zero by evaluating it at a randomly chosen α over ${\mathbb {F}}$ or a suitable extension field [14, 31, 34]. Hence, univariate ideal membership of degree-d rank-r polynomials can be decided in randomized d^O(r) ⋅poly(n) time where $d = \max \limits \{\deg (f),\deg (p_{i}): 1\le i\le n\}$ by Theorem 1.4.

As mentioned in Section 1, an application of our result yields an n^O(r) time algorithm for computing the permanent of rank-r matrices over ${\mathbb {Q}}$ or any finite field. Barvinok [9], via a different method, had obtained an n^O(r) time algorithm for this problem over $\mathbb {Q}$.

Corollary 4.7

• There is an n^O(r) time algorithm to compute the permanent of n × n matrices of rank at most r over the field of rationals or any finite field.

• For finite fields ${\mathbb {F}}$ the algorithm has running time bounded by $O^{*}(|{\mathbb {F}}|^{O(r^{2})})$. In particular, over constant size fields this is an FPT algorithm for computing Perm(A) (with r as fixed parameter).

Proof

The n^O(r) time algorithm is a direct application of the algorithm of Theorem 1.4 to the product of linear forms polynomial and univariate ideal described in Fact 1.2.

For the second part, suppose ${\mathbb {F}}$ is a finite field of size p^s, where ${\text {char}}({\mathbb {F}})=p$ (a prime). Let $A\in \mathbb {F}^{n\times n}$ be a rank r matrix and let $\ell _{i}={\sum }_{j=1}^{n} a_{ij}x_{j}, 1\le i\le n$. Then there are exactly $N=|\mathbb {F}|^{r}-1$ many distinct nonzero $\mathbb {F}$-linear forms spanned by ℓ_i,i ∈ [n]. We denote them by $\ell ^{\prime }_{1},\ell ^{\prime }_{2},\ldots ,\ell ^{\prime }_{N}$. Then the product ${\prod }_{i=1}^{n} \ell _{i}$ can be expressed as

$$ \prod\limits_{i=1}^{n} \ell_{i} = \prod\limits_{j=1}^{N} {\ell^{\prime}}_{j}^{d_{j}}, $$

where $d_{1}+d_{2}+{\dots } + d_{N}=n$ is the degree of the product. Therefore, by Fact 1.2 we have

$$ {\text{Perm}}(A) = \prod\limits_{j=1}^{N} {\ell^{\prime}}_{j}^{d_{j}} \text{mod}\left\langle{{x_{1}^{2}},{x_{2}^{2}},\ldots,{x_{n}^{2}}}\right\rangle. $$

Now, suppose d_j ≥ p for some j. Let $\ell ^{\prime }_{j} = {\sum }_{k=1}^{n} \alpha _{jk}x_{k}$. Then writing d_j = pq_j + r_j,r_j < p we have

$$ \begin{array}{@{}rcl@{}} {\ell^{\prime}}_{j}^{d_{j}} &=& \left( \sum\limits_{k=1}^{n}\alpha_{jk}x_{k}\right)^{pq_{j}+r_{j}}\\ &=& (\sum\limits_{k=1}^{n}\alpha_{jk}^{p}{x_{k}^{p}})^{q_{j}}\dot (\sum\limits_{k=1}^{n}\alpha_{jk}x_{k})^{r_{j}}\\ &=& 0 \text{mod}\left\langle{{x_{1}^{2}},{x_{2}^{2}},\ldots,{x_{n}^{2}}}\right\rangle. \end{array} $$

The last equality holds because ${x_{k}^{p}}=0 \text {mod} {{x_{k}^{2}}}$ for any p ≥ 2. Consequently, if $n>(p-1)\dot (|{\mathbb {F}}|^{r}-1)$ then d_j ≥ p for some j, and by Fact 1.2 we have Perm(A) = 0. For $n\le (p-1)\dot |{\mathbb {F}}|^{r}$ the n^O(r)-time algorithm is an $O^{*}(p^{r}\dot |{\mathbb {F}}|^{O(r^{2})})$ time algorithm, which completes the proof. □

4.2 Small Circuit for the Remainder Polynomial

The first algorithm is based on repeated division and partial evaluation. As such, it does not directly yield a small circuit for f modI.

We now show that f modI has an arithmetic circuit of size O^∗(d^O(r)), where $d=\deg (f)$. The circuit has a nice form: it is a d^O(r)-sum of products of univariate polynomials, each of degree at most d. Moreover, this circuit can be constructed in time O^∗(d^O(r)) from the input f and I. This also yields another proof of Theorem 1.4, since evaluation of the circuit obtained at a given scalar point can be done in O^∗(d^O(r)) time.

Some notation for the sequel: For $q\in {\mathbb {F}}[t_{1},t_{2},\ldots ,t_{r},X]$, let $[t_{1}^{d_{1}}t_{2}^{d_{2}}{\cdots } t_{r}^{d_{r}}](q)$ denote the coefficient of $t_{1}^{d_{1}}t_{2}^{d_{2}}{\cdots } t_{r}^{d_{r}}$ in q, noting that $[t_{1}^{d_{1}}t_{2}^{d_{2}}{\cdots } t_{r}^{d_{r}}](f)\in {\mathbb {F}}[X]$.

Now, we can write f = g(ℓ₁,ℓ₂,…,ℓ_r) as a sum of d^O(r) d-products of the r linear forms. Thus, it suffices to give a small circuit, of the above form, for a remainder $\ell _{1}^{d_{1}}\ell _{2}^{d_{2}}{\cdots } \ell _{r}^{d_{r}} \text {mod} I$, where $I=\left \langle {p_{1}(x_{1}),p_{2}(x_{2}),\ldots ,p_{n}(x_{n})}\right \rangle$. A + -gate summing up all these remainder circuits would be a circuit of the claimed form for f modI.

We first consider a single power ℓ^dmodI, where $\ell ={\sum }_{i=1}^{n} a_{i}x_{i}$ is a homogeneous linear form in ${\mathbb {F}}[X]$. By the multinomial theorem

$$ \left( \sum\limits_{i=1}^{n} a_{i}x_{i}t\right)^{d} = \sum\limits_{j_{1}+j_{2}+\dots+j_{n}=d} {\left( \begin{array}{cc}d\\{j_{1},j_{2},\ldots,j_{n}} \end{array}\right)} \prod\limits_{i=1}^{n} (a_{i}x_{i}t)^{j_{i}}. $$

For fields ${\mathbb {F}}$ of characteristic zero, we can write:

$$ \left( \sum\limits_{i=1}^{n} a_{i}x_{i}\right)^{d} = d! [t^{d}]\left( \prod\limits_{i=1}^{n}\left( \sum\limits_{j=0}^{d} {\frac{1}{j!}}(a_{i}x_{i}t)^{j}\right)\right). $$

(1)

Equation 1 is combinatorially verified by noting that the term ${\prod }_{i=1}^{n} (a_{i}x_{i}t)^{j_{i}}$, for $j_{1}+j_{2}+{\dots } j_{n}=d$ occurs precisely ${\left (\begin {array}{cc}d\\{j_{1},j_{2},\ldots ,j_{n}} \end {array}\right )}$ times on the right side, matching the multinomial expansion of the left side. This identity was first used in arithmetic circuit complexity by Saxena [28],² and has found many applications.

Remark 4.8

Observe that, the right hand side expression of (1) can be viewed as a univariate polynomial in t of degree nd. Therefore, by interpolation, we can find $\alpha _{1},\ldots , \alpha _{nd+1}\in {\mathbb {F}}$ (or a suitable extension field of ${\mathbb {F}}$) and $\beta _{1},\ldots , \beta _{nd+1}\in \mathbb {F}$ such that,

$$ \left( \sum\limits_{i=1}^{n} a_{i}x_{i}\right)^{d} = \sum\limits_{\ell=1}^{nd+1} \beta_{\ell}\left( \prod\limits_{i=1}^{n}\left( \sum\limits_{j=0}^{d} {\frac{1}{j!}}(a_{i}x_{i}\alpha_{\ell})^{j}\right)\right). $$

(2)

Therefore, a power of a linear form can be expressed as a small sum of product of univariates.

This can be generalized to the finite fields setting [16]. We give a self-contained description of this, as it is required for the circuit construction for f modI. First, for ${\text {char}}(\mathbb {F})=p$, (1) only holds for d < p, as each k! occurring in it is invertible in $\mathbb {F}_{p}$ precisely if d < p. To obtain a suitable form of the equation for d ≥ p, we first write $d={\sum }_{k=0}^{s} e_{k}p^{k}$, for $s\le \log _{p}(d)-1$ and each e_k < p. Since ${\text {char}}({\mathbb {F}})=p$ for each k ≤ s, letting $a_{i}^{p^{k}}=a_{k,i}\in {\mathbb {F}}$ we have:

$$ \left( \sum\limits_{i=1}^{n} a_{i}x_{i}t\right)^{e_{k}p^{k}} = \left( \sum\limits_{i=1}^{n} a_{k,i}x_{i}^{p^{k}}t^{p^{k}}\right)^{e_{k}}. $$

Combined with (1) we get for 0 ≤ k ≤ s:

$$ \ell^{e_{k}p^{k}} = \left[t^{e_{k}p^{k}}\right]\left( \sum\limits_{i=1}^{n} a_{k,i}x_{i}^{p^{k}}t^{p^{k}}\right)^{e_{k}} = (e_{k})!\left[t^{e_{k}p^{k}}\right]\left( \prod\limits_{i=1}^{n}\left( \sum\limits_{j=0}^{e_{k}} {\frac{1}{j!}}\left( a_{k,i}x_{i}^{p^{k}}t^{p^{k}}\right)^{j}\right)\right). $$

As $d={\sum }_{k=0}^{s} e_{k}p^{k}$, multiplying over all k gives

$$ \begin{array}{@{}rcl@{}} \ell^{d} & = & \prod\limits_{k=0}^{s} \left[t^{e_{k}p^{k}}\right]\left( \sum\limits_{i=1}^{n} a_{k,i}x_{i}^{p^{k}}t^{p^{k}}\right)^{e_{k}}\\ & = & {\prod}_{k=0}^{s} (e_{k})!\left[t^{e_{k}p^{k}}\right]\left( \prod\limits_{i=1}^{n}\left( \sum\limits_{j=0}^{e_{k}} {\frac{1}{j!}}\left( a_{k,i}x_{i}^{p^{k}}t^{p^{k}}\right)^{j}\right)\right)\\ \end{array} $$

Let t₀,t₁,…,t_s be new variables. Replacing $t^{p^{k}}$ by t_k for each 0 ≤ k ≤ s in the above equations we get:

$$ \ell^{d} = \left[t_{0}^{e_{0}}t_{1}^{e_{1}}{\dots} t_{s}^{e_{s}}\right] \prod\limits_{k=0}^{s} (e_{k})! \left( \prod\limits_{i=1}^{n}\left( \sum\limits_{j=0}^{e_{k}} {\frac{1}{j!}}\left( a_{k,i}x_{i}^{p^{k}}t_{k}\right)^{j}\right)\right). $$

(3)

Thus, $\ell ^{d}= [t_{0}^{e_{0}}t_{1}^{e_{1}}{\dots } t_{s}^{e_{s}}] Q_{\ell ,d}$, where Q_ℓ,d is a product of the sn many polynomials as above (each of which is a bivariate polynomial in x_i,t_k,i ∈ [n],k ∈ [s]). This equation generalizes to express the product $\ell _{1}^{d_{1}}\cdot \ell _{2}^{d_{2}}{\cdots } \ell _{r}^{d_{r}}$ in the following form:

$$ \ell_{1}^{d_{1}}\cdot \ell_{2}^{d_{2}}{\cdots} \ell_{r}^{d_{r}} = \left[t_{1}^{\nu_{1}}t_{2}^{\nu_{2}}{\dots} t_{D}^{\nu_{D}}\right] \prod\limits_{k=1}^{D}\prod\limits_{i=1}^{n} q_{k,i}, $$

(4)

where D = (s + 1)r, and ν_k < p for each k ∈ [D] such that $d_{j}={\sum }_{k=(s+1)(j-1)+1}{(s+1)j} \nu _{k}p^{k-(s+1)(j-1)-1}, j\in [r]$. It is obtained simply by applying (3) to each $\ell _{j}^{d_{j}}$ with a different set of s + 1 many variables t_i and multiplying these equations for 1 ≤ j ≤ r. We note that each $q_{k,i}\in {\mathbb {F}}[x_{i},t_{k}]$ is a polynomial of individual variable degree at most $d={\sum }_{j=1}^{r} d_{j}$, as is clear from (3). The next claim will complete the proof of Theorem 1.4.

Claim 4.9

$\ell _{1}^{d_{1}}\cdot \ell _{2}^{d_{2}}{\cdots } \ell _{r}^{d_{r}} \text {mod} I$ has an arithmetic circuit which is a d^O(r)-sum of products of univariate polynomials, where each univariate polynomial in x_i involved in a product has degree at most $\deg (p_{i}(x_{i}))-1$.

For the proof, we first consider the following subexpression in (4)

$$ \left[t_{1}^{\nu_{1}}t_{2}^{\nu_{2}}{\dots} t_{D}^{\nu_{D}}\right]\prod\limits_{k=1}^{D} q_{k,i}, $$

which we will evaluate modulo p_i(x_i). Note that the number of monomials of the form ${\prod }_{k=1}^{D} t_{k}^{\mu _{k}}, \mu _{k}\le \nu _{k}<p$ is bounded by p^D = (p^s+ 1)^r = d^O(r). Thus, in O^∗(d^O(r)) time we can expand the product ${\prod }_{k=1}^{D} q_{k,i}$ by multiplying out the polynomials, one by one, from left to right. After each multiplication, we replace ${x_{i}^{a}}$ by its remainder ${x_{i}^{a}}\text {mod} p_{i}$ and drop any term with a factor ${t_{k}^{p}}, k\in [D]$. This will result in a polynomial expression of the form

$$ Q_{i} = \sum\limits_{\bar{\mu}}r_{\bar{\mu}}(x_{i})\prod\limits_{k=1}^{D}t_{k}^{\mu_{k}}, $$

where the sum runs over the d^O(r) many tuples $\bar {\mu }=(\mu _{1},\mu _{2},\ldots ,\mu _{k})$ such that μ_k ≤ ν_k for each k. Thus, each $r_{\bar {\mu }}(x_{i})$ is a univariate in x_i of degree at most $\deg (p_{i})-1$. We can now evaluate the product Q₁Q₂⋯Q_n modulo the ideal $\left \langle {{t_{1}^{p}},{t_{2}^{p}},\ldots ,{t_{D}^{p}}}\right \rangle$ by multiplying out adjacent pairs and dropping any terms with a factor ${t_{k}^{p}}, k\in [D]$. This will given an expression for Q₁Q₂⋯Q_n modulo $\left \langle {{t_{1}^{p}},{t_{2}^{p}},\ldots ,{t_{D}^{p}}}\right \rangle$ of the form ${\sum }_{\bar {\mu }}R_{\bar {\mu }}{\prod }_{k=1}^{D}t_{k}^{\mu _{k}}$, where each $R_{\bar {\mu }}$ is a d^O(r)-sum of products of n univariate polynomials (and in each product the i^th is a polynomial in x_i of degree $\deg (p_{i})-1$). Finally, we note that $R_{\bar {\nu }}$ is the desired polynomial expression for ${\prod }_{j=1}^{r}\ell _{j}^{d_{j}} \text {mod} I$, completing the proof of the claim.

4.3 Vertex Cover Detection in Low Rank Graphs

In the Vertex Cover problem, the input instances are pairs (G,k), where G = (V,E) is a graph and k is an integer. The problem is to decide whether or not G has a vertex cover of size k. This is a classical NP-complete problem.

A graph G is said to be of rank r if the rank of the adjacency matrix A_G is of rank r. Graphs of low rank were studied by Lovasz and Kotlov [4, 20]. As an application of Theorem 1.4, we obtain an n^O(r) time algorithm to compute a minimum vertex cover in an n-vertex graph of rank r.

Remark 4.10

A pair of vertices x,y in a graph G are twins if they have identical neighborhoods in G. Lovasz and Kotlov [4] have shown that a rank r graph G that is twin-free has at most O(2^r/2) vertices. Clearly, a minimal vertex cover S of G does not contain twins. Therefore, in order to search for a minimum vertex cover for G, it suffices to search for it in a maximal twin-free subgraph H of G, which is easy to find in poly(n) time. Now, H will have at most O(2^r/2) vertices as its rank is also bounded by r. A brute-force search for the minimum vertex cover in V (H) yields an $O^{*}(2^{2^{r/2}})$ algorithm. For n that is double exponential in r, this brute-force search is faster than the n^O(r) algorithm of this section.

Proof of Theorem 1.5

We give a polynomial-time reduction from Vertex Cover to Univariate Ideal Membership. Let (G,k) be a Vertex Cover instance. Let $I=\left \langle {{x^{2}_{1}} - x_{1},{x^{2}_{2}} - x_{2},\ldots , {x^{2}_{n}} - x_{n}}\right \rangle$ and

$$ f = \prod\limits^{\left( \begin{array}{ll}{n}\\{2} \end{array}\right)}_{s=1} (\vec{x} A_{G} \vec{x}^{T} - s) \cdot \prod\limits^{n-k-1}_{t=0}\left( \sum\limits^{n}_{i=1} x_{i} - t\right), $$

where A_G is the adjacency matrix of the graph G and $\vec {x}=(x_{1},x_{2},\ldots ,x_{n})$ is row-vector.

Claim 4.11

The rank of the polynomial f is at most r + 1.

Proof

We note that A_G is symmetric since it encodes an undirected graph. Let Q be an invertible n × n matrix that diagonalizes A_G. So we have QA_GQ^T = D where D is a diagonal matrix with only the first r diagonal elements being non-zero. Let $\vec {y}=(y_{1},y_{2},\ldots ,y_{n})$ be another row-vector of variables. Now, we show the effect of the transform $\vec {x}\mapsto \vec {y}Q$ on the polynomial $\vec {x}A_{G} \vec {x}^{T}$. Clearly, $\vec {y}Q A_{G} Q^{T} \vec {y}^{T} = \vec {y}D\vec {y}^{T}$ and since there are only r non-zero entries on the diagonal, the polynomial $\vec {y}D\vec {y}^{T}$ is over the variables y₁,y₂,…,y_r. Thus $g = {\prod }^{\left (\begin {array}{ll}{n}\\{2} \end {array}\right )}_{s=1} (\vec {x}A_{G} \vec {x}^{T} - s)$ is a rank r polynomial. Also $h={\prod }^{n-k-1}_{t=0}({\sum }^{n}_{i=1} x_{i} - t)$ is a rank 1 polynomial as there is only one linear form ${\sum }^{n}_{i=1} x_{i}$. Since f = gh, we conclude that f is a rank r + 1 polynomial. □

Now the proof of Theorem 1.5 follows from the next claim.

Claim 4.12

The graph G has a Vertex Cover of size k if and only if f∉I.

Proof

First, observe that the set of common zeroes of the generators of the ideal I is the set {0,1}ⁿ. Let S be a vertex cover in G such that |S|≤ k. We will exhibit a point $\vec {\alpha }\in \{0,1\}^{n}$ such that $f(\vec {\alpha })\neq 0$. This will imply that f∉I. Identify the vertices of G with {1,2,…,n}. Define $\vec {\alpha }(i)=0$ if and only if i ∈ S. Since $\vec {x} A_{G} \vec {x}^{T} = {\sum }_{(i,j)\in E_{G}} x_{i} x_{j}$ and S is a vertex cover for G, it is clear that $\vec {x} A_{G} \vec {x}^{T}(\vec {\alpha })=0$. Also $({\sum }_{i=1}^{n} x_{i})(\vec {\alpha })\geq n-k$. Then clearly $f(\vec {\alpha })\neq 0$.

For the other direction, suppose that f∉I. Then by Theorem 1.1, there exists $\vec {\alpha }\in \{0,1\}^{n}$ such that $f(\vec {\alpha })\neq 0$. Define the set $S\subseteq [n]$ as follows. Include i ∈ S if and only if $\vec {\alpha }(i)=0$. Since $f(\vec {\alpha })\neq 0$, and the range of values that $\vec {x} A_{G} \vec {x}^{T}$ can take is {0,1,…,|E|}, it must be the case that $\vec {x} A_{G} \vec {x}^{T}(\vec {\alpha })=0$. It implies that the set S is a vertex cover for G. Moreover, ${\prod }^{n-k-1}_{t=0}({\sum }^{n}_{i=1} x_{i} - t)(\vec {\alpha })\neq 0$ implies that |S|≤ k. □

The degree of the polynomial f is bounded by n² + n and from Claim 4.12 we know that f modI is a non-zero polynomial if and only if G has a vertex cover of size k. By the Polynomial Identity lemma [14, 31, 34], $(f \text {mod} I)(\vec {\beta })$ is non-zero with high probability when $\vec {\beta }$ is chosen randomly from a small domain. Now, we need to just compute $(f \text {mod} I)(\vec {\beta })$ where f is a rank r + 1 polynomial with $\ell _{i} = (\vec {x}Q^{-1})_{i}$ for each 1 ≤ i ≤ r and $\ell _{r+1} ={\sum }_{i=1}^{n} x_{i}$ which can be performed in (n,k)^O(r) time using Theorem 1.4. □

5 Univariate Ideal Membership Parameterized by Degree

In this section, we consider the degree of the input polynomial as the fixed parameter. Consider $I=\left \langle {\{p_{i}(x_{i})\}_{i=1}^{n}}\right \rangle$ be a univariate ideal and $f\in \mathbb {F}[{X}]$ be a degree k polynomial given by an arithmetic circuit. Clearly, there is a simple O^∗(n^O(k)) algorithm for it: we can write $f={\sum }_{m}\alpha _{m} m$ as a linear combination of $\left (\begin {array}{cc}{n+k}\\ k \end {array}\right )$ many monomials m. We can then compute the remainder $f \text {mod} I={\sum }_{m}\alpha _{m} (m \text {mod} I)$ as a linear combination of monomials.

We first prove Theorem 1.6 showing a randomized O^∗((2e)^k) time algorithm for the special case where ${\mathbb {F}}=\mathbb {Q}$ and the ideal $I=\left \langle {x_{1}^{e_{1}},x_{2}^{e_{2}},\ldots ,x_{n}^{e_{n}}}\right \rangle$.

5.1 Proof of Theorem 1.6

Proof

The main step is the following reduction of checking if f ∈ I (where f is degree-k and $I=\left \langle {x_{1}^{e_{1}},x_{2}^{e_{2}},\ldots ,x_{n}^{e_{n}}}\right \rangle$) to the problem of checking if the polynomial f ∘^sg is identically zero, where g is chosen as a polynomial weakly equivalent³ to the elementary symmetric polynomial. The claimed algorithm then follows by applying a recent result of [7].

Recall that S_m,ℓ denotes the elementary symmetric polynomial of degree ℓ over m variables. Set $m = {\sum }_{i=1}^{n} (e_{i} - 1)$ and define S_m,ℓ on the m variables $z_{1,1},\ldots ,z_{1,e_{1}-1},\ldots ,z_{n,1},\ldots ,z_{n,e_{n}-1}$. Now, for 0 ≤ ℓ ≤ k define g_ℓ(X) as the polynomial obtained from S_m,ℓ by replacing each z_i,j by x_i,1 ≤ i ≤ n.

Claim 5.1

Given integers e₁,e₂,…,e_n, and a homogeneous polynomial f(X) of degree k, $f\in \left \langle {x^{e_{1}}_{1},x^{e_{2}}_{2},\ldots ,x^{e_{n}}_{n}}\right \rangle$ if and only if f ∘^sg_ℓ ≡ 0 for 0 ≤ ℓ ≤ k.

Proof

Clearly $f\not \in \left \langle {x^{e_{1}}_{1},x^{e_{2}}_{2},\ldots ,x^{e_{n}}_{n}}\right \rangle$ if and only if f has a nonzero degree ℓ monomial $M = x^{f_{1}}_{1} x^{f_{2}}_{2}{\ldots } x^{f_{n}}_{n}$, for some ℓ ≤ k, such that f_i < e_i for each 1 ≤ i ≤ n. Hence, the scaled Hadamard product polynomial f ∘^sg_ℓ is not identically zero for some ℓ ≤ k if and only if $f\not \in \left \langle {x^{e_{1}}_{1},x^{e_{2}}_{2},\ldots ,x^{e_{n}}_{n}}\right \rangle$. □

The proof now follows from the recent work of [7] as explained below:

For checking if f ∘^sg_ℓ (as defined in Lemma 5.1) is identically zero, it suffices to check for some polynomial $\tilde {g_{\ell }}$ weakly equivalent to g_ℓ that $f\circ ^{s} \tilde {g_{\ell }}$ is identically zero. By color coding [3], we can construct a homogeneous depth-three circuit of size e^kpoly(n) that computes a polynomial weakly equivalent to S_n,k with high probability (see [7] for details). Replacing each z_i,j by x_i,1 ≤ i ≤ n, we obtain a homogeneous depth-three circuit of the same size for a polynomial $\tilde {g_{\ell }}$ weakly equivalent to g defined in Lemma 5.1.

Now, it is shown in [7] that we can compute the scaled Hadamard product of a circuit of size s₁ with a degree-k homogeneous depth three circuit of size s₂ in deterministic O^∗(2^k ⋅ s₁s₂) time. Therefore, f ∘^sg_ℓ can be computed in O^∗((2e)^k) time. We can check if f ∘^sg_ℓ is identically zero by evaluating at a randomly chosen point [14, 31, 34]. Overall, this gives a randomized O^∗((2e)^k) time algorithm. □

Remark 5.2

• 1. The above proof fails for ${\text {char}}({\mathbb {F}})<k$ because f ∘^sg might vanish because the scaling factor m! for each monomial might be divisible by ${\text {char}}(\mathbb {F})$.

• 2. Over rationals, we can apply a recent work [27] to obtain an O^∗(4.08^k) time algorithm to test identity of scaled Hadamard product with elementary symmetric polynomial. This improves the algorithm of Theorem 1.6 to a randomized O^∗(4.08^k) algorithm.

We now consider deciding the membership for the general case of univariate ideal. We first make the following observation.

Observation 5.3

Let $I=\left \langle {\{p_{i}(x_{i})\}_{i=1}^{n}}\right \rangle$ be a univariate ideal and $f\in {\mathbb {F}}[X]$ be a degree k polynomial of Waring rank r. Then f can be expressed as an r-sum of k^th powers of linear forms i.e. $f = {\sum }_{i=1}^{r} \ell ^{k}$ for some affine linear forms ℓ_i. Then, there is a deterministic poly(r,k,n) algorithm to decide whether f ∈ I.

The proof follows easily from (2) that allows us to write f as a small sum of product of univariates.

Remark 5.4

As an application, motivated by the permanent lemma [1, Lemma 8.1], consider the following constrained linear inequations problem: given $A\in {\mathbb {F}}^{k\times n}$, $(b_{1},b_{2},\ldots ,b_{k})^{T}\in {\mathbb {F}}^{k}$, and a family of subsets S₁,S₂,…,S_n of the field ${\mathbb {F}}$ the problem is to find an assignment $\vec {x}=\vec {a}\in S_{1}\times S_{2}\times {\dots } \times S_{n}$ such that ${\sum }_{j}a_{ij}x_{j}\ne b_{i}, 1\le i\le k$. We define the degree-k polynomial

$$ f = \prod\limits_{i=1}^{k} \left( \sum\limits_{j=1}^{n} a_{ij}x_{j} - b_{j}\right). $$

Clearly, a solution to the above inequation system exists if and only if there exists $\vec {a} \in S_{1} \times {\cdots } S_{n}$ such that $f(\vec {a})$ is non-zero. By the Combinatorial Nullstellensatz [1] (Theorem 1.1), it can be expressed as a univariate ideal membership problem. As f is a product of k linear forms, its the Waring rank is bounded by O^∗(2^k). By Observation 5.3, we obtain a deterministic O^∗(2^k) algorithm to solve this constrained inequation system.

For degree-k, n-variate polynomials f, we do not have an algorithm with running time better than $O^{*}{\left (\left (\begin {array}{cc}n+k\\ k \end {array}\right )\right )}$ for univariate ideal membership in general. However, if each generator polynomial p_i has distinct roots we obtain a faster algorithm.

Theorem 5.5

Let $I = \left \langle {p_{1}(x_{1}), \ldots , p_{n}(x_{n})}\right \rangle$ be a univariate ideal given explicitly by a set of univariate polynomials p₁,…,p_n such that for each i ∈ [n], p_i(x_i) has distinct roots over ${\mathbb {Q}}$. Given a polynomial $f(X)\in {\mathbb {C}}[X]$ of degree k and I as input, we can decide whether f ∈ I or not in randomized O^∗(n^k/2) time.

Proof

W.l.o.g. we can assume the degree of each p_i is at most k. Otherwise, we can drop p_i from I. For i ∈ [n], let $S_{i}\subset \mathbb {Q}$ be the set of all roots of p_i. By Alon’s Combinatorial Nullstellensatz (Theorem 1.1), Theorem 5.4 can be restated as the following.

Claim 5.6

Given a polynomial $f(X)\in \mathbb {C}[X]$ of degree k and S₁,…,S_n such that for each i ∈ [n], $S_{i}\subset \mathbb {C}$ as inputs, we can decide whether S₁ ×⋯ × S_n contains a nonzero of f in in randomized O^∗(n^k/2) time.

For a degree-k polynomial $f\in {\mathbb {F}}[X]$ let

$$ \tilde{f}=x_{n+1}^{k}\cdot f\left( \frac{x_{1}}{x_{n+1}},\frac{x_{2}}{x_{n+1}},\ldots,\frac{x_{n}}{x_{n+1}}\right), $$

be its homogenization. Thus, $\tilde {f}$ is homogeneous of degree k and $\tilde {f}(x_{1},x_{2},\ldots ,$ x_n,1) = f(x₁,…,x_n). Clearly, f is nonzero on the n-dimensional grid S₁ ×⋯ × S_n if and only if $\tilde {f}$ is nonzero on the n + 1 -dimensional grid S₁ ×⋯ × S_n ×{1}. Hence, without loss of generality we can assume f is homogeneous degree k.

Observation 5.7

For a homogeneous polynomial f of degree k,

$$ f\circ^{s} (a_{1} x_{1}+\ldots+a_{n} x_{n})^{k}\mid_{\vec{1}} = k!\cdot f(a_{1},\ldots,a_{n}). $$

We need to decide whether there exists a point $\vec {a} \in S_{1}\times \cdots \times S_{n}$ such that $f(\vec {a})\neq 0$.

For each (a₁,…,a_n) ∈ S₁ ×… × S_n, by (2) we can write,

$$ \frac{1}{k!}\cdot (a_{1} x_{1}+\ldots+a_{n} x_{n})^{k} = \sum\limits_{\ell=1}^{nk+1} \beta_{\ell}\cdot \prod\limits_{i=1}^{n} p_{i}(a_{i}\alpha_{\ell} x_{i}). $$

where $\alpha _{1},\ldots ,\alpha _{n}\in \mathbb {Q}$ are some distinct points, $\beta _{\ell }\in \mathbb {Q}$, and each p_i is univariate.

Now, we define the “grid” polynomial

$$ \begin{array}{@{}rcl@{}} g & = & \sum\limits_{\ell=1}^{nk+1} \beta_{\ell} \cdot\prod\limits_{i=1}^{n}\left( \sum\limits_{a_{i}\in S_{i}}\xi_{i,a_{i}} p_{i}(a_{i}\alpha_{\ell} x_{i})\right) \end{array} $$

(5)

$$ \begin{array}{@{}rcl@{}} & = & \sum\limits_{(a_{1},\ldots,a_{n}) \in S_{1}\times{\ldots} \times S_{n}}\prod\limits_{i=1}^{n}\xi_{i,a_{i}}\left( \sum\limits_{\ell=1}^{nk+1} \beta_{\ell}\cdot \prod\limits_{i=1}^{n} p_{i}(a_{i}\alpha_{\ell} x_{i})\right), \end{array} $$

(6)

where $\xi _{i,a_{i}}, i\in [n], a_{i}\in S_{i}$ are new variables. Hence,

$$ \begin{array}{@{}rcl@{}} f\circ^{s} g\mid_{\vec{1}} &=& \sum\limits_{(a_{1},\ldots,a_{n}) \in S_{1}\times{\ldots} \times S_{n}}\prod\limits_{i=1}^{n}\xi_{i,a_{i}}f\circ^{s} \left( \sum\limits_{\ell=1}^{nk+1} \beta_{\ell}\cdot {\prod}_{i=1}^{n} p_{i}(a_{i}\alpha_{\ell} x_{i})\right)\mid_{\vec{1}} \end{array} $$

(7)

$$ \begin{array}{@{}rcl@{}} &= & \sum\limits_{(a_{1},\ldots,a_{n}) \in S_{1}\times{\ldots} \times S_{n}}\prod\limits_{i=1}^{n} \xi_{i,a_{i}} f(a_{1},a_{2},\ldots,a_{n}) \end{array} $$

(8)

Thus, $f\circ ^{s} g\mid _{\vec {1}}$ is a nonzero polynomial (in the $\xi _{i,a_{i}}$ variables) of degree n iff f ∘^s(a₁x₁ + ⋯a_nx_n)^k is nonzero for some $(a_{1},\ldots ,a_{n})\in S_{1}\times {\dots } S_{n}$. By the Polynomial Identity Lemma [14, 31, 34], we can independently randomly assign values for the $\xi _{i,a_{i}}$ variables from [n²], and the evaluation is nonzero with probability at least 1 − 1/n iff f nonzero on a grid point in $S_{1}\times \dots \times S_{n}$. Furthermore, from (7) we note that we can clear the denominators of all the β_ℓ and the polynomials p_i(a_iα_ix_i) and the polynomial f (given by input circuit) and take out a common factor $\frac {1}{D}$ (where D is a polynomially many bits long integer) to write (7) as

$$ f\circ^{s} g\mid_{\vec{1}} =\frac{1}{D} \sum\limits_{(a_{1},\ldots,a_{n}) \in S_{1}\times{\ldots} \times S_{n}}\prod\limits_{i=1}^{n}\xi_{i,a_{i}}\hat{f}\circ^{s} \left( \sum\limits_{\ell=1}^{nk+1} \gamma_{\ell}\cdot \prod\limits_{i=1}^{n} \hat{p}_{i}(a_{i}\alpha_{\ell} x_{i})\right)\mid_{\vec{1}}, $$

where $\hat {f}$ and $\hat {p}_{i}(a_{i}\alpha _{\ell } x_{i})$ have integer coefficients. Thus, when $f\circ ^{s} g\mid _{\vec {1}}$ is nonzero at a choice of the $\xi _{i,a_{i}}$ then it is of absolute value at least 1/D.

Therefore, after randomly choosing $\xi _{i,a_{i}}\in _{R}[n^{2}]$, it is clear from (5) that the problem reduces to efficiently computing the scaled Hadamard product $f\circ ^{s} h\mid _{\vec {1}}$ evaluated at $\vec {1}$, where $h={\prod }_{i=1}^{n} q_{i}(x_{i})$ and each q_i is of degree k. We now show that $f\circ ^{s} h\mid _{\vec {1}}$ can be computed in O^∗(n^k/2) time which suffices to detect if $f\circ ^{s} g\mid _{\vec {1}}$ is nonzero in O^∗(n^k/2) time.

Claim 5.8

$f\circ ^{s} {\prod }_{i=1}^{n} q_{i}(x_{i})\mid _{\vec {1}}$ can be computed in O^∗(n^k/2) time.

Notice that the above claim completes the proof, because the summation over ℓ has nk + 1 terms. Let $\beta = \max \limits _{\ell }\{|\beta _{\ell }|\}$. Then the overall error in $f\circ ^{s} g\mid _{\vec {1}}$ is bounded by the precision error of the claim multiplied by (nk + 1)β which can be made smaller than 1/D by choosing the precision error of the claim.

We now prove the claim. We need approximations because we will need to approximately compute the roots of the univariate polynomials q_i. Let R_i denote the nonzero roots of q_i. Then we can write

$$ \prod\limits_{i} q_{i} = \prod\limits_{i=1}^{n} x_{i}^{\mu_{i}}\prod\limits_{i=1}^{n}\prod\limits_{-\beta\in R_{i}}(x_{i}+\beta)^{\nu_{i,\beta}}, $$

where ν_i,β is the multiplicity of root − β in q_i. If ${\sum }_{i} \mu _{i} > k$ then clearly $f\circ ^{s} {\prod }_{i} q_{i} = 0$. Otherwise, let ${\sum }_{i} \mu _{i} = s$ and let r = k − s. Let ${\prod }_{i}{\prod }_{\beta \in R_{i}} \beta ^{\nu _{i,\beta }}={\Gamma }$. Write ${\prod }_{i=1}^{n}{\prod }_{-\beta \in R_{i}}(x_{i}+\beta )^{\nu _{i,\beta }}$ as ${\Gamma } {\prod }_{i=1}^{n}{\prod }_{-\beta \in R_{i}}(x_{i}/\beta +1)^{\nu _{i,\beta }}$. Let $m={\sum }_{i}\deg (q_{i})-s$ and consider the elementary symmetric polynomial S_m,r in variables y₁,y₂,…,y_m. By Lee’s result [24], S_m,r can be expressed as O^∗(m^r/2) sum of powers of linear forms. In the polynomial S_m,r we replace the m variables y₁,y₂,…,y_m by the m nonzero roots (of the form x_i/β, as explained above) of ${\prod }_{j} q_{j}$. Let the product of the resulting polynomial (which is still a O^∗(m^r/2)-sum of r-power of linear forms) with ${\Gamma }\cdot {\prod }_{i=1}^{n} x_{i}^{\mu _{i}}$ be denoted by Q. Clearly, $f\circ ^{s} {\prod }_{i} q_{i} = f\circ ^{s} Q$. Since Q is a sum of power of linear forms using Observation 5.7, we can evaluate $f\circ ^{s} Q\mid _{\vec {1}}$ with O^∗(n^k/2) arithmetic operations.

Now, replacing each root β by a rational approximation $\beta ^{\prime }$ such that $|\beta -\beta ^{\prime }|\le 1/2^{L}$ for a suitably chosen polynomial bit number L, the overall error in the approximation to $f\circ ^{s} Q\mid _{\vec {1}}$ will be bounded. It can be made smaller than ε by choosing L suitably large. We can use any efficient root approximation algorithm for univariate polynomials to find all such root approximations $\beta ^{\prime }$.

This completes the proof of the claim and the theorem. □

Remark 5.9

Observe that Claim 5.8 can be restated as follows: given univariate polynomials p_i(x_i),1 ≤ i ≤ n, the Waring rank of the degree-k part of their product ${\prod }_{i=1}^{n} p_{i}(x_{i})$ is bounded by O^∗(n^k/2). Then the proof of Theorem 5.4 follows as an application of Observation 5.3.

6 Univariate Ideal Membership Parameterized by Number of Generators

In this section, we consider the univariate ideal membership parameterized on the number of generators of the univariate ideal. More precisely, we consider univariate ideal membership for input f(X) by a circuit of size s and univariate ideal $I=\left \langle {p_{1}(x_{1}), \ldots , p_{k}(x_{k})}\right \rangle$ (with k as fixed parameter).

We show that the nonmembership problem is W[2]-hard by giving an efficient reduction from the k-dominating set problem which is W[2]-complete [13].

Moreover, in contrast to the problem parameterized by $\deg (f)$, even for the special case of the ideal $I=\left \langle {x_{1}^{e_{1}},x_{2}^{e_{2}},\ldots ,x_{k}^{e_{k}}}\right \rangle$ we show the problem remains hard. We are able to show it is MINI[1]-hard. Hence, even in this special case the problem cannot have an algorithm of run time O^∗(s^o(k)) assuming the exponential time hypothesis. On the other hand, the problem has an easy O^∗(s^k) time randomized algorithm.

Proof of Theorem 1.7

Let (G,k) be an instance of the k-dominating set problem, where G = (V,E) is an n-vertex graph and the fixed parameter k is the size of the independent set. Let V (G) = {1,2,…,n}. For 1 ≤ i ≤ k, we define polynomials

$$ p_{i}(x_{i}) = \prod\limits^{n}_{j=1}(x_{i} - j). $$

The W[2]-hardness proof is an application of Alon’s Combinatorial Nullstellensatz (Theorem 1.1): By definition, for each p_i its zero set is Z(p_i) = [n]. Therefore, a polynomial $g\in \mathbb {Q}[x_{1},x_{2},\ldots ,x_{k}]$ is in the ideal 〈p₁,p₂,…,p_k〉 if and only if g is zero on every point in the k-dimensional grid $[n] \times [n]\times {\dots } \times [n]$.

For each u ∈ V, let N_u = {u}∪{v ∈ V ∣uv ∈ E} denote its closed neighborhood in G. Define polynomials q_u,u ∈ V

$$ q_{u} = \sum\limits_{i=1}^{k} \prod\limits_{v\in\overline{N_{u}}} (x_{i}-v)^{2}. $$

Notice that q_u is nonzero at a grid point x_i = v_i,1 ≤ i ≤ k if and only if there is a v_i ∈ N_u. That is, q_u is nonzero at (v₁,v₂,…,v_k) if and only if some v_i dominates u. Now, letting

$$ q_{G}(x_{1},x_{2},\ldots,x_{k}) = \prod\limits_{u=1}^{n} q_{u}, $$

it follows that q_G is nonzero at a grid point x_i = v_i,1 ≤ i ≤ k if and only if {v₁,v₂,…,v_k} is a dominating set for G.

Hence, by Theorem 1.1 we have the following claim which completes the proof. □

Claim 6.1

The polynomial q_G is not in the univariate ideal 〈p₁,p₂,…,p_n〉 if and only if the graph G has a dominating set of size k.

6.1 Proof of Theorem 1.8

We first relate our univariate ideal membership problem with a linear algebraic problem k−Lin-Eq. It turns that k−Lin-Eq problem is more amenable to the MINI[1]-hardness proof. Finally we show a reduction from MINI − 1 − in − 3POSITIVE3 − SAT to k−Lin-Eq to complete the proof.

Definition 6.2 (k-Lin-Eq)

Input: Integers k,n in unary, a k × n matrix A with all the entries given in unary and a k dimensional vector $\vec {b}$ with all entries in unary.

Parameter: k.

Question: Does there exist an $\vec {x}\in \{0,1\}^{n}$ such that $A\vec {x} = \vec {b}$?

Lemma 6.3

There is a parameterized reduction from k−Lin-Eq to the univariate ideal membership problem when the ideal is given by the powers of variables as generators.

Proof

We introduce 2k variables $x_{1},x_{2},\dots ,x_{k},y_{1},y_{2},\dots ,y_{k}$ where two variables will be used for each row. For each i ∈ [n], let $\mu _{i} = {\sum }_{j=1}^{n} a_{ij}$. For each column $c_{i} = (a_{1i},a_{2i},\dots ,a_{ki})$ we construct the polynomial $P_{i} = ({y_{1}}^{a_{1i}}{y_{2}}^{a_{2i}}{\dots } {y_{k}}^{a_{ki}} + {x_{1}}^{a_{1i}}{x_{2}}^{a_{2i}}{\dots } {x_{k}}^{a_{ki}})$. We let $P_{A} = {\prod }_{i=1}^{n} P_{i}$ and we choose the ideal to be $\langle x_{1}^{b_{1} + 1},y_{1}^{\mu _{1} - b_{1} +1},$ $\dots ,x_{k}^{b_{k} + 1},y_{1}^{\mu _{k} - b_{k} +1}\rangle$. Notice that P_A has a small arithmetic circuit which is polynomial time computable. □

Claim 6.4

An instance $(A,\vec {b})$ is an YES instance for k−Lin-Eq iff $P_{A} \not \in \left \langle x_{1}^{b_{1} + 1},y_{1}^{\mu _{1} - b_{1} +1},\dots ,x_{k}^{b_{k} + 1},y_{k}^{\mu _{k} - b_{k} +1}\right \rangle$.

Proof of Claim

Suppose $(A,\vec {b})$ is an YES instance. Then there is an $\vec {x}\in \{0,1\}^{n}$ such that $A\vec {x}=\vec {b}$. Define $S:=\{i\in [n] : \vec {x}_{i}=1\}$ where x_i is the i th co-ordinate of $\vec { x}$. Think of the monomial where ${x_{1}}^{a_{1i}}{x_{2}}^{a_{2i}}\dots {x_{k}}^{a_{ki}}$ is picked from P_i for each i ∈ S and ${y_{1}}^{a_{1i}}{y_{2}}^{a_{2i}}{\dots } {y_{k}}^{a_{ki}}$ is picked from reaming P_j’s where $j\in \bar {S}$. This gives us the monomial $x_{1}^{b_{1}} y_{1}^{\mu _{1} - b_{1}} {\ldots } x_{k}^{b_{k}} y_{1}^{\mu _{k} - b_{k}}$ in the polynomial P_A. Thus $P_{A} \not \in \left \langle {x_{1}^{b_{1} + 1},y_{1}^{\mu _{1} - b_{1} +1},\ldots ,x_{k}^{b_{k} + 1},y_{k}^{\mu _{k} - b_{k} +1}}\right \rangle$.

Now we show the other direction. Now suppose $P_{A} \not \in \left \langle x_{1}^{b_{1} + 1},y_{1}^{\mu _{1} - b_{1} +1},\dots ,x_{k}^{b_{k} + 1},y_{k}^{\mu _{k} - b_{k} +1}\right \rangle$. Let $S := \{ i\in [n] : {x_{1}}^{a_{1i}}{x_{2}}^{a_{2i}}\dots {x_{k}}^{a_{ki}}$ is picked from P_i}. There must be a monomial ${x_{1}}^{c_{1}}{x_{2}}^{c_{2}}\dots {x_{k}}^{c_{k}} {y_{1}}^{d_{1}}{y_{2}}^{d_{2}}\dots {y_{k}}^{d_{k}}$ in P_A such that for each i, ${\sum }_{j\in S}a_{ij}=c_{i} \leq b_{i}$, ${\sum }_{j\not \in S}a_{ij} = d_{i} \leq (\mu _{i} - b_{i})$. As, $\mu _{i} = {\sum }_{j\in S} a_{ij} + {\sum }_{i\not \in S}a_{ij}$, we get $b_{i} \leq {\sum }_{j\in S}a_{ij}$. Hence, ${\sum }_{j \in S}a_{ij} = b_{i}$ for each i. Define $\vec {x}\in \{0,1\}^{n}$ where $\vec {x}_{i} = 1$ if i ∈ S else $\vec {x}_{i}=0$. This shows $(A,\vec {b})$ is an YES instance. □

Before we prove the MINI[1]-hardness of k−Lin-Eq, we show that the following problem is MINI[1]-hard.

Definition 6.5

MINI − 1 − in − 3POSITIVE3 − SAT

Input: Integers k,n in unary, a 3-SAT instance $\mathcal {E}$ consisting of only positive literals where $\mathcal {E}$ has at most $k\log n$ variables and at most $k\log n$ clauses.

Parameter: k.

Question: Does there exist a satisfiable assignment for $\mathcal {E}$ such that every clause has exactly one literal?

Claim 6.6

MINI − 1 − in − 3POSITIVE3 − SAT is MINI[1]-hard.

To prove the claim we only need to observe that the standard Schaefer Reduction [30] from 3-SAT to 1 − in − 3POSITIVE3 − SAT is in fact a linear size reduction, that directly gives us an FPT reduction from MINI− 3SAT to MINI − 1 − in − 3POSITIVE3 − SAT.

Proof of Theorem 1.8

Given a MINI − 1 − in − 3POSITIVE3 − SAT instance $\mathcal {E}$, order the variables $v_{1},\dots ,v_{k\log n}$ and the clauses $C_{1},\dots ,C_{k\log n}$. Construct the following $k\log n\times k\log n$ matrix M where the rows are indexed by the clauses and the columns are indexed by the variables. M[i][j] is set to 1 if v_j appears in C_i, otherwise set it to 0. Make M a $2k\log n\times n$ matrix by adding an all zero row between every rows and appending all zero columns at the end. Now, define $\vec {e}$ as a $2k\log n$ dimensional vector where i th co-ordinate of e, e_i = 1 when i is odd and e_i = 0 when i is even. We want to find $\vec {y}\in \{0,1\}^{n}$ such that $M\vec {y}=\vec {e}$.

However this is not an instance of k−Lin-Eq. To make it so, we observe that M is a bit matrix and $\vec {e}$ is a bit vector, hence we can modify them to a k × n matrix A and k dimensional vector $\vec {b}$ in the following way. For each column j, think of the i th consecutive $2\log n$ bits as the binary expansion of a single entry, call it N and set A[i][j] to N. Similarly, we modify $\vec {e}$ to a k dimensional vector $\vec {b}$ by considering $2\log n$ bits as a binary expansion of a single entry. Now the proof follows from the following claim. □

Claim 6.7

$\mathcal {E}$ is an YES instance for MINI − 1 − in − 3POSITIVE3 − SAT if and only if there exists an $\vec {x}\in \{0,1\}^{n}$ such that $A\vec {x} = \vec {b}$.

Proof

Suppose there is such a satisfiable assignment for $\mathcal {E}$. Define $S:=\{j\in [k\log n]\mid v_{j}=\text {TRUE}\}$. Define $\vec {z}\in \{0,1\}^{n}$ such that z_j = 1 where j ∈ S else z_j = 0. For each i, as C_i contains exactly one literal, hence $e_{2i+1} = {\sum }_{j=1}^{n} M[i][j]\cdot z_{j} = 1$ and e_2i = 0. Therefore $\vec {z}$ is a solution for $M\vec {y} = \vec {e}$. As every integer has a unique binary expansion, hence $\vec {z}$ is also a solution for $A\vec {x} = \vec {b}$.

Now we prove the other direction. Suppose $A\vec {z} = \vec {b}$ for some $\vec {z}\in \{0,1\}^{n}$. From the construction of the matrix M, it is sufficient to show that $\vec {z}$ is a satisfying assignment for $M\vec {y} = \vec {e}$. First we note that the numbers A[i][j],b[i] in their binary expansion have bits 1 in the odd location and 0 in the even locations. Let $A[i][j] = {\sum }^{2\log n}_{t=1} a_{ijt} 2^{t-1}$ and $b[i]={\sum }^{2\log n}_{t=1} e_{t} 2^{t-1}$. Since $A\vec {z} = \vec {b}$ we have ${\sum }_{j=1}^{n} A[i][j]\cdot z_{j} = b[i]$. This shows that

$$ \sum\limits_{j=1}^{n} A[i][j]\cdot z_{j} = \sum\limits_{j=1}^{n} \left( \sum\limits^{2\log n}_{t=1} a_{ijt} 2^{t-1}\right) \cdot z_{j} =\sum\limits^{2\log n}_{t=1} \left( \sum\limits_{j=1}^{n} a_{ijt} \cdot z_{j}\right) 2^{t-1}. $$

Since $\mathcal {E}$ is a 3-CNF formula we have $({\sum }_{j=1}^{n} a_{ijt} \cdot z_{j}) \in \{0,1,2,3\}$. Now we compare $({\sum }_{j=1}^{n} a_{ijt} \cdot z_{j})$ with the binary expansion of b[i]. When t is odd the bit e_t is 1 and so there must be a 1 in the corresponding bit of $({\sum }_{j=1}^{n} a_{ijt} \cdot z_{j})$. This shows that $({\sum }_{j=1}^{n} a_{ijt} \cdot z_{j}) \neq 0$ when t is odd. Now if $({\sum }_{j=1}^{n} a_{ijt} \cdot z_{j}) \in \{ 2,3 \}$ for any odd t then the term 2^t+ 1 will be produced and this will not match the expansion of b[i] as the e_t+ 1 = 0. Thus by the uniqueness of binary expansion we conclude that $({\sum }_{j=1}^{n} a_{ijt} \cdot z_{j}) = 1$ if t is odd and 0 otherwise. Thus $M\vec {y} = \vec {e}$ has a solution with y_i = z_i. □

7 Non-deterministic Algorithm for Univariate Ideal Membership

In this section we prove Theorem 1.9. Given a polynomial $f(X)\in \mathbb {Q}[X]$ and a univariate ideal I = 〈p₁(x₁),…,p_n(x_n)〉 where the generators are p₁,…,p_n have no repeated roots, we show that deciding nonmembership of f in I is in NP. By Theorem 1.1, it suffices to check in NP if there is a grid point (α₁,α₂,…,α_n) in the n-dimensional grid $Z(p_{1})\times Z(p_{2})\times {\dots } \times Z(p_{n})$ where f does not vanish. Since the roots of p_i could be irrational (even complex), it is not immediately clear how to guess a polynomial size witness for such a grid point and efficiently verify. However, we show that for the NP machine it suffices to guess a grid point $\vec {\alpha }$ approximately, upto polynomially many bits of precision. Recall that

$$ f(X)= \sum\limits_{i=1}^{n} h_{i}(X) ~p_{i}(x_{i}) + R(X), $$

where the remainder R is unique and $\deg _{x_{i}} (R) < \deg (p_{i})$ for all i. For a polynomial $g\in {\mathbb {F}}[X]$, let |c(g)| denote be the maximum coefficient (in absolute value) of a monomial in g. We obtain simple estimates for the coefficients of the polynomials h₁,…,h_n,R in terms of n, $\deg (f)$, and the coefficients of f and the p_i.

Lemma 7.1

Let 2^−L ≤|c(f)|,|c(p_i)|≤ 2^L. Then 2^{−poly(L,n,d)} ≤|c(h_i)|,|c(R)|≤ 2^poly(L,n,d) where d is the degree upper bound for f, and {p_i : 1 ≤ i ≤ n}.

Proof

Write f as a linear combination of at most $\left (\begin {array}{cc}{d+n}\\ n \end {array}\right )$ many monomials $f={\sum }_{m}\alpha _{m} m$. Each monomial m occurring in it is of the form $m=x_{1}^{e_{1}}x_{2}^{e_{2}}{\dots } x_{n}^{e_{n}}, {\sum }_{i} e_{i}\le d$. By univariate division, we can write each m as:

$$ m = \prod\limits_{i=1}^{n} (h_{m,i}p_{i} + r_{m,i}), $$

where $h_{m,i},r_{m,i}\in \mathbb {Q}[x_{i}]$ such that $x^{e_{i}}= h_{m,i}p_{i}+r_{m,i}$, and $\deg (r_{m,i})<\deg (p_{i})$. Moreover, by the properties of univariate polynomial division, the absolute value of the coefficients of each h_m,i and r_m,i lie in an interval of the form [2^{−poly(L,n,d)},2^poly(L,n,d)]. We note that $R={\sum }_{m}{\prod }_{i=1}^{n} r_{m,i}$, and each h_i is a 2^poly(n,d) sum of n-fold products of the h_m,i and the p_i. Therefore, the coefficients of R and of each h_i, in absolute value, also lie in an interval of the form [2^{−poly(L,n,d)},2^poly(L,n,d)], as claimed. □

Let $\vec \alpha = (\alpha _{1}, \ldots , \alpha _{n}) \in \mathbb {C}^{n}$ be such that p_i(α_i) = 0, 1 ≤ i ≤ n. By Lemma 2.3, $2^{-\hat {L}} \le |\alpha _{i}|\leq 2^{\hat {L}}$ where $\hat {L}= \text {poly}(L,d)$. For each i, let $\tilde {\alpha }_{i}\in \mathbb {Q}[i]$ be an 𝜖-approximation of α_i. That is, $|\alpha _{i}-\tilde {\alpha }_{i}|\leq \epsilon$. Let $\tilde {\alpha }=(\tilde {\alpha }_{1},\ldots ,\tilde {\alpha }_{n})$. Then we can bound the absolute value of $p_{i}(\tilde {\alpha }_{i})$ and ${\sum }_{i=1}^{n}h_{i}(\tilde {\alpha })p_{i}(\tilde {\alpha })$.

Observation 7.2

• For 1 ≤ i ≤ n we have that $|p_{i}(\tilde {\alpha }_{i})|\leq \epsilon \cdot 2^{(d L)^{c}}$.

• $|{\sum }_{i=1}^{n}h_{i}(\tilde {\alpha })p_{i}(\tilde {\alpha })|\le \epsilon 2^{(ndL)^{c}}$.

Here c > 0 is a constant that is independent of 𝜖.

Proof

Let $p_{i}(x_{i}) = c\cdot {\prod }_{j=1}^{d} (x_{i} - \beta _{i,j})$. Without loss of generality, suppose $\tilde {\alpha }_{i}$𝜖-approximates β_i,1 for each i. Then

$$ \begin{array}{@{}rcl@{}} |p_{i}(\tilde{\alpha}_{i})| & \leq & \epsilon \cdot |c|\cdot \prod\limits_{j=2}^{d} |\tilde{\alpha}_{i} - \beta_{i,j}| \\ & \le & \epsilon \cdot |c|\cdot \prod\limits_{j=2}^{d} (|\beta_{i,1} - \beta_{i,j}| + \epsilon)\\ & \le & \epsilon \cdot 2^{\text{poly}(d, L)}, \end{array} $$

where the last inequality follows from the bound on the distance between the roots of a univariate polynomial shown in Lemma 2.3. For the second part, note that $|\tilde {\alpha }_{i}|\le |\alpha _{i}|+1\le 2^{\tilde {L}+1}$ by Lemma 2.3. Each h_i has at most ${\left (\begin {array}{cc}{n+d}\\ d \end {array}\right )}$ monomials, and, by Lemma 7.1, the coefficients of each h_i is bounded by 2^poly(n,d,L). Putting it together, $|h_{i}(\tilde {\alpha })|\le 2^{\text {poly}(n,d,L)}$ for all i. Hence, by the first part, $|{\sum }_{i=1}^{n}h_{i}(\tilde {\alpha })p_{i}(\tilde {\alpha })|\le \epsilon 2^{(ndL)^{O(1)}}$. □

We now prove Theorem 1.9.

Proof

If f is not in the ideal I then, by Theorem 1.1, there exists a grid point $\vec \alpha = (\alpha _{1}, \ldots , \alpha _{n}) \in Z(p_{1}) \times {\ldots } \times Z(p_{n})$ such that $R(\vec \alpha ) \neq 0$.

The NP Machine guesses an 𝜖-approximation $\vec {\tilde {\alpha }}=(\tilde {\alpha }_{1}, \ldots , \tilde {\alpha }_{n})$ of $\vec \alpha$, where 𝜖 will be chosen later in the analysis. Using the circuit (or black-box) for f, we obtain the value for $f(\vec {\tilde {\alpha }})$.

Next, we show that the value $|f(\vec {\tilde {\alpha }})|$ distinguishes between the cases f ∈ I and f∉I.

Case 1

f ∈ I $|f(\tilde {\alpha })| = |{\sum }_{i=1}^{n} h_{i}(\vec {\tilde {\alpha }}) p_{i}(\tilde {\alpha _{i}})|\le \epsilon \cdot 2^{(n d L)^{c}}$ by Observation 7.2. We can verify this from the value returned by the circuit (or black-box) for f. Note: the inequality may be satisfied even for a $\tilde {\alpha }$ that is not an 𝜖-approximation of $\vec {\alpha }$. However, the analysis and choice of 𝜖 will guarantee correctness.

Case 2

f∉I We have $f(\tilde {\alpha }) = {\sum }_{i=1}^{n} h_{i}(\tilde {\alpha })p_{i}(\tilde {\alpha }) + R(\tilde {\alpha })$. Hence,

$$ |f(\tilde{\alpha}) - R(\tilde{\alpha})| \le \epsilon 2^{(ndL)^{c}}. $$

Our aim is to show that $|f(\tilde {\alpha })|\ge 2\epsilon 2^{(ndL)^{c}}$. We have from above that $|f(\tilde {\alpha })|\ge R(\tilde {\alpha })-\epsilon 2^{(ndL)^{c}}$.

By triangle inequality, $|R(\tilde {\alpha })| \geq |R(\vec \alpha )| - |R(\tilde {\alpha }) - R(\vec \alpha )|$. We now show a lower bound on $|R(\vec \alpha )|$ and an upper bound for $|R(\tilde {\alpha }) - R(\vec \alpha )|$.

Claim 7.3

$|R(\vec \alpha )|\geq \frac {1}{2^{(ndL)^{c_{1}}}}$ for some constant c₁.

Proof

Let $\hat {R}(x_{n}) = R(\alpha _{1}, \ldots , \alpha _{n-1}, x_{n} ) = a \cdot {\prod }_{j=1}^{d^{\prime }} (x_{n}-\beta _{j})$, where a is some nonzero scalar and $d^{\prime }\leq d$. Note that α_n is not a zero for $\hat {R}(x_{n})$. Consider the polynomial $Q(x_{n}) = p_{n}(x_{n}) \hat {R}(x_{n})$. The set $\{\alpha _{n}, \beta _{1}, \ldots , \beta _{d^{\prime }}\}$ are roots of Q(x_n) and $\alpha _{n} \neq \beta _{j} : 1\leq j\leq d^{\prime }$. By the root separation bound of Lemma 2.4 for |α_n − β_j|, it follows that $|\hat {R}(\alpha _{n})| \geq \frac {1}{2^{(n d L)^{c_{1}}}}$ for some c₁ > 0. □

Claim 7.4

$|R(\vec {\tilde {\alpha }}) - R(\vec \alpha )|\leq \epsilon 2^{(n d L)^{c_{2}}}$ for some constant c₂.

Proof

Define $R^{0}(\vec {\tilde {\alpha }})=R(\vec \alpha )$ and $R^{i}(\vec {\tilde {\alpha }}) = R(\tilde {\alpha }_{1}, \ldots , \tilde {\alpha }_{i}, \alpha _{i+1}, \ldots , \alpha _{n})$. By triangle inequality, $|R(\vec \alpha ) - R(\vec {\tilde {\alpha }})|\leq {\sum }_{i=1}^{n} |R^{i-1}(\vec {\tilde {\alpha }}) - R^{i}(\vec {\tilde {\alpha }})|$. Writing explicitly, we have $R^{i-1}(\vec {\tilde {\alpha }}) - R^{i}(\vec {\tilde {\alpha }}) = {\sum }_{\vec {e}} c_{\vec {e}} \tilde {\alpha }_{1}^{e_{1}}\ldots \tilde {\alpha }_{i-1}^{e_{i-1}} (\alpha _{i}^{e_{i}} - \tilde {\alpha }_{i}^{e_{i}}) \alpha _{i}^{e_{i+1}}\ldots \alpha _{n}^{e_{n}}$. Now, the bounds $|\alpha _{i}| \leq 2^{(ndL)^{O(1)}}$, and $|\alpha _{i} - \tilde {\alpha }_{i}|\leq \epsilon$, combined with the number of summands being bounded by ${d+n}\choose d$ implies by triangle inequality that $|R(\vec {\tilde {\alpha }}) - R(\vec \alpha )| \leq \epsilon \cdot 2^{(n d L)^{c_{2}}}$ for some constant c₂ > 0 (independent of 𝜖). □

Combined with the inequalities in Claims 7.3 and 7.4, we have $|f(\vec {\tilde {\alpha }})| \geq \frac {1}{2^{(n d L)^{c_{1}}}} - \epsilon \cdot \left (2^{(n d L)^{c_{2}}} + 2^{(n d L)^{c}}\right )$.

To make the calculation precise, let $3M = \frac {1}{2^{(n d L)^{c_{1}}}}$ and choose 𝜖 such that $\epsilon \cdot (2^{(n d L)^{c_{2}}} + 2^{(n d L)^{c}}) \leq M$. We note that the number M can be efficiently pre-computed from the input.

Summarizing the test, notice that f ∈ I implies that there is a guessed point $\tilde {\alpha }$ of polynomial size such that $|f(\tilde {\alpha })|\leq M$. On the other hand, as argued in Case 2 above, if f∉I then for any guessed point $\tilde {\alpha }$ we have $|f(\tilde {\alpha })|\geq 2M$. □