Geometric Complexity Theory V: Efficient algorithms for Noether Normalization

Introduction

Noether’s Normalization Lemma (NNL), proved by Hilbert , is the basis of a large number of foundational results in algebraic geometry, such as Hilbert’s Nullstellensatz. It also lies at the heart of the foundational classification problem of algebraic geometry. For any projective variety $W\subseteq P(K^{l})$, where $K$ is an algebraically closed field and $P(K^{l})$ is the projective space associated with $K^{l}$, the lemma says that any homogeneous, generic linear map $\psi:K^{l}\rightarrow K^{k}$, for any $k\geq\dim(W)+1$, induces a regular (well defined) map on $W$ (this means $\psi$ does not vanish identically on the line through the origin in $K^{l}$ corresponding to any point in $W$). Furthermore, for any such $\psi$, (1) $\psi(W)\subseteq P(K^{k})$, the image of $W$, is closed in $P(K^{k})$, and (2) the fiber $\psi^{-1}(p)$, for any point $p\in\psi(W)$, is a finite set. Accordingly, we call a homogeneous linear map $\psi:K^{l}\rightarrow K^{k}$, $k\geq\dim(W)+1$, that induces a regular map on $W$ a normalizing map for $W$. In the context of the main results of this paper, $l$ here will be exponential in $\dim(W)$, and $k$ will be polynomial in $\dim(W)$. In this case, Noether’s Normalization Lemma expresses the variety $W$, embedded in the ambient space $P(K^{l})$ of exponential dimension, as a finite cover of the variety $\psi(W)$, embedded in the ambient space $P(K^{k})$ of polynomial dimension. This is its main significance from the complexity-theoretic perspective. We also refer to the problem of constructing a normalizing map $\psi$, with $k={\mbox{poly}}(\dim(W))$, as NNL in short. This is the problem that is studied in this article for the varieties $W$ that are given explicitly in a sense that will be made precise. We do not require $k=\dim(W)+1$ here, and allow a polynomial slack, for the reasons explained in Section 1.2.

In algebraic geometry, the phrase “explicitly” is used informally. In this article, it is interpreted formally, from the complexity-theoretic perspective, to mean “using algebraic circuits that can be computed in deterministic polynomial time”. Thus, we formally introduce in this article the notion of an explicit family $\{W_{n}\}$ of varieties (Definition 5.1) of ${\mbox{poly}}(n)$ dimension that can be specified succinctly and uniformly by ${\mbox{poly}}(n)$-time-computable algebraic circuits (cf. Section 2.1) of ${\mbox{poly}}(n)$ degree having a specification of ${\mbox{poly}}(n)$ bit-length, even though the dimension $l_{n}$ of the ambient space containing $W_{n}$ can be exponential in $n$. If $W_{n}$ is projective, we let $l_{n}$ be one plus the dimension of the ambient space. If the family $\{W_{n}\}$ is explicit, we also say that the variety $W_{n}$ is explicit, with the understanding that $n\rightarrow\infty$ in all complexity bounds. It turns out that (cf. Section 5.1) a large class of varieties that arise in practice are explicit in this formal complexity-theoretic sense.

The problem NNL for such explicit varieties $W_{n}$ (cf. Definition 5.6) is the problem of constructing a specific kind (cf. Sections 1.2 and 5.3) of a normalizing map $\psi_{n}:K^{l_{n}}\rightarrow K^{k_{n}}$ for $W_{n}$, with $k_{n}={\mbox{poly}}(n)$, having a succinct specification of ${\mbox{poly}}(n)$ bit-length.

For general explicit varieties $W_{n}$, the standard algorithm for NNL (cf. Section 5.6), based on Gröbner basis theory , takes in the worst case work-space that is polynomial in $l_{n}$, and time that is exponential in $l_{n}$. In our context $l_{n}$, in general, is exponential in $n$, and hence, this work-space bound is exponential in $n$, i.e., $O(2^{{\mbox{poly}}(n)})$, and the time bound is double exponential in $n$. This shows that NNL for explicit varieties is in EXPSPACE. Assuming the Generalized Riemann Hypothesis, it can be shown to be in EXPH (cf. Section 5.6). Here EXPSPACE denotes the complexity class of problems that can be solved using exponential work-space in double exponential time, and EXPH denotes the exponential hierarchy . Informally, these stand for the classes of problems that are computationally highly intractable (far more intractable than the problems in the class NP, which can be solved in exponential time and polynomial space). Thus, on the basis of the existing literature in computational algebraic geometry, it may appear that NNL for explicit varieties is highly intractable, and perhaps, even inherently so.

The algorithmic results in this article indicate that this is not the case.

First, it is shown in this article (cf. Theorem 1.2) that NNL for any explicit variety $W_{n}$ can be solved by a ${\mbox{poly}}(n)$-time randomized Monte Carlo algorithm, whose output is correct with a high probability. This means, in practice, NNL for explicit varieties can be solved efficiently and correctly with a high probability. But this does not show that NNL for explicit varieties is in $\mbox{BPP}\subseteq\mbox{PSPACE}$, for the reasons explained in Section 1.3. Hence, it does not affect the current EXPSPACE-status of NNL, or the EXPH status assuming the Generalized Riemann Hypothesis.

So we ask if NNL for any explicit variety can be solved deterministically in polynomial time, thereby bringing it down from EXPSPACE to P. We say that NNL for an explicit variety has an explicit solution, in the complexity-theoretic sense, if it can be solved in deterministic polynomial time. The motivation for such an explicit solution comes from the foundational classification problem of algebraic geometry (cf. Section 1.8 in ). Its goal is to classify a given algebraic variety by transforming it regularly into some canonical normal form. Without any relaxation, this goal may be infeasible, since it is not even known at present if the isomorphism problem for algebraic varieties is decidable . Hence, our goal is to do the best that we can from the complexity-theoretic perspective. As a first step in this direction, one would like an “explicit” normalizing map for an “explicitly” given variety. A random normalizing map is not enough in this context, since randomness is the opposite of canonicity. Solving NNL in deterministic polynomial time is this first step towards the classification problem of algebraic geometry, interpreted from the complexity-theoretic perspective. For the reasons explained in Section 11, this turns out to be far harder than solving NNL in randomized polynomial time by a Monte Carlo algorithm. We turn to this harder problem next.

It is shown in this article that, for some interesting cases of explicit varieties $W_{n}$, NNL can indeed be solved deterministically in quasi-${\mbox{poly}}(n)$-time, i.e., in $O(2^{(\log n)^{c}})$ time, for some constant $c>1$. (Here it is assumed that the dimension $k_{n}$ of the target space of the constructed normalization map $\psi_{n}:K^{l_{n}}\rightarrow K^{k_{n}}$ is also quasi-polynomial in $n$.) Thus, for these explicit varieties, NNL can be brought down from EXPSPACE to quasi-P, the class of problems that can be solved deterministically in quasi-polynomial time.

The first such case of an explicit variety is the categorical quotient $V/G$ associated with any finite dimensional (rational) representation $V$ of $G=SL_{m}$, with constant $m$, in characteristic zero. (By a rational representation, we mean that the entries of the representation matrix are rational functions of the coordinates of $G$. We will only be concerned with such representations in this article.) Here $V/G={\mbox{spec}}(K[V]^{G})$ By abuse of notation, spec in this article really means max-spec; cf. (page 54). is the variety whose coordinate ring is $K[V]^{G}\subseteq K[V]$, where $K[V]$ denotes the coordinate ring of $V$, and $K[V]^{G}$ its subring of $G$-invariants. Explicitness of this variety is by itself a key result in this article. It means (cf. Theorem 1.5) that a succinct encoding, in the form of a symbolic determinant, of a set of (exponentially many) generators for this invariant ring can be constructed in ${\mbox{poly}}(n)$ time, where $n$ is the dimension of $V$.

This succinct and efficient encoding of generators is in the spirit of the encodings that were used in the so-called symbolic method of classical invariant theory (cf. Chapter 8 A in ). For example, the First Fundamental Theorem for the ring of vector invariants proved by Weyl (cf. Theorem 2.6 A therein) implies such a polynomial-time-computable succinct encoding, in the form of a symbolic determinant, of a set of (exponentially many) generators for this invariant ring. The problem of proving similar First Fundamental Theorems for invariant rings has been studied intensively in the last century; cf. Section 9 in for a survey. This classical problem is interpreted in this article (cf. Definition 5.2 (d)), from the complexity-theoretic perspective, as the problem of constructing an explicit encoding, in the form of a symbolic determinant or a circuit, of a set of generators of the invariant ring, where explicit means polynomial-time-computable. Classical invariant theory did not specify formally what “explicit” means.

For the variety $V/G$ associated with any $n$-dimensional representation $V$ of $G=SL_{m}$, with constant $m$, in characteristic zero, it is shown in this article that NNL can be solved deterministically in $O(n^{O(\log\log n)})$ time; cf. Theorem 1.6.

Noether’s Normalization Lemma was, in fact, proved by Hilbert to give an algorithm for constructing a finite set of generators for the invariant ring $K[V]^{G}$ in this context. Hilbert did not prove any explicit upper bound on its running time, or on the degrees of the generators. Such a bound on the degrees was proved in Popov a century later, and improved significantly in Derksen . This improved analysis yields an exponential-time algorithm for computing a set of generators for the ring $K[V]^{G}$ of invariants for any finite dimensional representation $V$ of $G=SL_{m}$ and, in conjunction with Gröbner basis theory , an EXPSPACE-algorithm for NNL for this invariant ring. This algorithm for constructing a set of generators requires time that is exponential in the dimension of $V$, and the algorithm for NNL requires exponential work-space and double exponential time, even when $m$ is constant. Hilbert’s paper focused mainly on the case when $m$ is three, since an algorithm to construct a finite set of generators was not known before even in this case; cf. Section 1.5.

Explicitness for constant $m$ of the categorical quotient associated with this invariant ring $K[V]^{G}$ (Theorem 1.5) implies that the problem of computing an encoding, in the form of a symbolic determinant, of a set of generators for this invariant ring is in P. Thus there has been a rather remarkable change in the status of this fundamental problem of invariant theory over the course of a century from a problem that was not even known to be computable before Hilbert to a problem that is now in P, as shown in this article; cf. Section 1.5.

The quasi-polynomial-time deterministic algorithm in this article for NNL for this invariant ring (cf. Theorem 1.6), for constant $m$, brings the original instance of NNL in Hilbert’s paper in this case from EXPSPACE to quasi-P. Analogous results hold for any connected, reductive, algebraic group of constant dimension (cf. Theorem 9.9).

The second case of an explicit variety that we consider is the categorical quotient $V/G$ associated with the space $V=M_{m}(K)^{r}$ of $r$-tuples of $m\times m$ matrices over $K$, with the simultaneous conjugation-action of $G=SL_{m}$ (without any restriction on $m$ this time). It is shown in this article that this variety is explicit in characteristic zero, and is explicit in a relaxed sense in positive characteristic (cf. Theorem 1.3).

Furthermore (cf. Theorem 1.4), NNL for this variety can be solved deterministically in quasi-${\mbox{poly}}(m,r)$ time in any characteristic $p\not\in[2,{\lfloor m/2\rfloor}]$, thereby bringing NNL in this case too from EXPSPACE to quasi-P. This extends the same result in characteristic zero that is implied, as pointed out by Forbes and Shpilka , by a variant of a conditional result in the preliminary version of this article, in conjunction with their earlier work on arithmetic circuits; cf. Remark 1 in Section 1.7.

More generally (cf. Theorems 1.8, 5.11, and Section 10.5), NNL for any explicit variety in zero or large enough characteristic can be solved deterministically in quasi-polynomial time, thereby bringing it from EXPSPACE to quasi-P, assuming the hardness hypothesis for the permanent in geometric complexity theory. This hypothesis proposed in (or rather its stronger variant) is that the permanent of $n\times n$ matrices cannot be approximated infinitesimally closely by symbolic determinants over $K$ of $O(2^{n^{\epsilon}})$ size, for some constant $\epsilon>0$, as $n\rightarrow\infty$. It is an algebraic geometric strengthening of the fundamental $\mbox{VP}\not=\mbox{VNP}$ conjecture in the work of Valiant .

In Bürgisser , some other consequences of this hardness hypothesis have been derived, which also crucially rely on the fundamental result of Kaltofen , as in this paper. Consulting (and especially Section 9.3 in that explains in detail the precise relationship of the work in with the earlier work in ) may help the reader to understand this hypothesis better.

The results described above lead to the following geometric complexity theory approach to the basic algorithmic problems of algebraic geometry and invariant theory under consideration, namely, (1) the problem NNL, and (2) the problem of constructing a set of generators for the ring of invariants of a reductive group. Both these problems are motivated by Hilbert .

The goal of the approach in the context of the first problem is to show that it is in P for every explicit variety. The approach is to (1) first prove the hardness hypothesis for the permanent in geometric complexity theory (or its weaker form, cf. Theorem 1.9), then (2) use the results in this article to show that NNL for every explicit variety is in quasi-P, in zero or large enough characteristic (cf. Theorem 5.11 and Section 10.5), and (3) finally, remove the quasi-prefix and the characteristic restriction by proving a stronger form of the hardness hypothesis (cf. Sections 5.5 and 10.5). An approach to prove the required hardness hypothesis in geometric complexity theory will be given in the sequel to this article (the revised version of ).

(N.B. The current version of on the arxiv has become outdated in view of the recent result that the occurrence-based obstructions in , based on the vanishing of the rectangular Kronecker coefficients, cannot be used to prove superpolynomial lower bounds for the permanent. The approach in the revised version of will be based on the far more powerful multiplicity-based obstructions, to which this negative result does not apply.)

To put NNL in quasi-P, one does not need the hardness hypothesis in geometric complexity theory, or even its weaker form, in full strength for all explicit varieties. For explicit varieties of intermediate difficulty, such as explicit categorical quotients, one only needs weaker complexity-theoretic hypotheses for the classes of circuits depending on the varieties. Thus one can approach this goal step by step, increasing the hardness of the varieties in tandem with the strength of the circuits; cf. Sections 5 and 10.

If the goals for both the problems (1) and (2) are achieved in a stronger form, it would follow that NNL for every categorical quotient $V/G$ is in P, and moreover, that the closed $G$-orbits in $V$ have an explicit (polynomial-time-computable) parametrization, for any finite dimensional representation $V$ of a reductive group $G$ in any characteristic; cf. Sections 9.6 and 10.3.

There is a fundamental difference between this approach to the basic algorithmic problems of algebraic geometry and invariant theory and the standard approaches in computational algebraic geometry and computational invariant theory . The difference lies in how the basic objects of algebraic geometry–namely, the varieties–are specified in the computer. Computational algebraic geometry, based on Gröbner basis theory and the theory of solving polynomial equations , and computational invariant theory use the standard specification of the varieties in terms of their defining equations. If one uses this standard specification, then the basic algorithmic problems of algebraic geometry and invariant theory are inherently intractable. For example, Gröbner basis computation is EXPSPACE-hard , solving polynomial equations (Hilbert’s Nullstellensatz) is NP-hard , NNL is NP-hard (cf. Section 3), the problem of constructing a finite set of generators for the ring $K[V]^{G}$ of invariants is inherently intractable, because the number of generators of this ring can be exponential in $\dim(V)$ even when $\dim(G)$ is constant (cf. the proof of Proposition 9.3), and hence, the standard parametrization of the closed $G$-orbits in $V$ by the points of the categorical quotient $V/G$ is also inherently intractable.

But this article illustrates that a large class of algebraic varieties that arise in practice can be specified explicitly using circuits, the basic objects of complexity theory. If one uses instead this explicit complexity-theoretic specification of the basic geometric objects (varieties), as in the approach here, then the results in this article indicate that the basic algorithmic problems (1) and (2) in algebraic geometry and invariant theory, along with the basic problem in geometric invariant theory of parametrizing closed orbits in representations of reductive groups, which are inherently intractable in the standard specification, are tractable in the explicit specification. The formal notion of explicitness introduced in this article (Definition 5.1), which is thus the fundamental difference between the geometric complexity theory approach to these basic problems and the standard approaches, is the driving theme of this article.

This article belongs to a series of articles on geometric complexity theory. See for an overview of the earlier articles in this series, and for an overview of the mathematical issues therein. Preliminary versions of the results here were announced in .

We now state the main results of this article in more detail.

Notation: Till Section 10, $K$ will henceforth denote an algebraically closed base field of characteristic zero, unless mentioned otherwise. We use the standard notation for the complexity classes, such as P (the class of problems that can be solved in polynomial time), BPP (the class of decision problems that can be solved by polynomial time Monte Carlo algorithms), NC (the class of problems that can be solved in poly-logarithmic parallel time using polynomial number of processors), DET (the class of problems LOGSPACE-reducible to computation of the determinant of integer matrices), EXP (the class of problems that can be solved in exponential time), EXPSPACE (the class of problems that can be solved in exponential work-space), PSPACE (the class of problems that can be solved in polynomial work-space), $AC^{0}$ (the class of problems that can be solved by constant depth Boolean circuits of polynomial size), PH (the polynomial hierarchy), EXPH (the exponential hierarchy), and so on. See for their formal definitions.

2 The problem NNL

We now define the problem NNL for the explicit variety associated with the determinant in the first article in this series.

It has to be stressed here that $\Delta[\det,m]$ is not specified by giving its equations in the ambient space $P({\cal X})$. This is not even possible using ${\mbox{poly}}(m)$ bits, since the dimension of $P({\cal X})$ is exponential in $m$. All complexity bounds for the results below for $\Delta[\det,m]$ are in terms of the $O({\mbox{poly}}(m))$ bit-length of its succinct specification. Thus an EXPSPACE-algorithm means an algorithm that takes work-space that is exponential in $m$, a P-algorithm means an algorithm that takes time that is polynomial in $m$, and so on.

Let $\hat{\Delta}[\det,m]\subseteq{\cal X}$ denote the affine cone of $\Delta[\det,m]$. This is defined to be the union of all lines through the origin in ${\cal X}$ that correspond to the points of $\Delta[\det,m]\subseteq P({\cal X})$. Let $R(\det,m)$ denote the homogeneous coordinate ring of $\Delta[\det,m]$. This is the same as the coordinate ring of $\hat{\Delta}[\det,m]$.

By Noether’s Normalization Lemma (Lemma 3.1), there exists a homogeneous linear map $\psi:{\cal X}\rightarrow K^{k}$, for any $k>\dim(\Delta[\det,m])$, such that $\psi$ does not vanish on any nonzero point in $\hat{\Delta}[\det,m]\subseteq{\cal X}$. Hence, $\psi$ yields a regular (well-defined) map from $\Delta[\det,m]$ to $P(K^{k})$, which we denote by $\psi$ again. We call such a $\psi$ a normalizing map (for $\Delta[\det,m]$). Any generic $\psi$ for such $k$ is a normalizing map. But deterministic construction or even verification of a normalizing map, as we shall see below, is very difficult.

Let $x_{i}$, $1\leq i\leq k$, denote the coordinates of $K^{k}$, and given a normalizing map $\psi$, let $\psi^{*}(x_{i}):{\cal X}\rightarrow K$ denote the pullback of $x_{i}$ via $\psi$. We also denote its restriction to $\hat{\Delta}[\det,m]$ by $\psi^{*}(x_{i})$. If $k=\dim(\Delta[\det,m])+1$, the minimum possible value, then we call the subset $\{\psi^{*}(x_{i})\ |\ 1\leq i\leq k\}\subseteq R(\det,m)$ an h.s.o.p. (homogeneous system of parameters) for $\Delta[\det,m]$. Existence of such an h.s.o.p. is a classical fact that holds for any variety; cf. Section 3.

An h.s.o.p. for $\Delta[\det,m]$ can be constructed in work-space that is exponential in $m$, and in time that is double exponential in $m$ (cf. Theorem 4.1), by first computing the equations of $\Delta[\det,m]$ as a subvariety of $P({\cal X})$ using Gröbner basis theory . This space requirement is exponential in $m$, because the number of variables in the equations of $\Delta[\det,m]$ as a subvariety of $P({\cal X})$ is equal to the dimension of ${\cal X}$, which is exponential in $m$, and Gröbner basis computation takes work-space that is at least polynomial in the number of variables. If we insist on an h.s.o.p., then this is the best that can be done at present. However, if we do not insist on the optimal $k=\dim(\Delta[\det,m])+1\leq m^{4}$, but allow a slack, and only require that $k$ be ${\mbox{poly}}(m)$, then we can do much better.

Accordingly, we define the problem NNL for $\Delta[\det,m]$ as the problem of constructing a normalizing map $\psi$ for $k={\mbox{poly}}(m)$, not necessarily optimal, with a succinct specification of ${\mbox{poly}}(m)$ bit-length. Thus we let go of optimality but insist on succinctness. We have to now explain what we mean by succinct. Obviously, the standard specification of $\psi$ as a linear map from ${\cal X}\to K^{k}$ is not succinct, since the dimension of ${\cal X}$ is exponential in $m$. Hence, we confine ourselves to normalizing maps which have a succinct specification as follows.

For any $m\times m$ matrix $B$ with rational entries, let $\psi_{B}$ denote the homogeneous, linear, evaluation map on ${\cal X}$, which maps a polynomial $p(X)\in{\cal X}$ to $p(B)$. We denote its restriction to $\hat{\Delta}[\det,m]$ by $\psi_{B}$ again. Given any set ${\cal B}=\{B_{1},\ldots,B_{k}\}$ of $m\times m$ matrices with rational entries, let $\psi_{{\cal B}}:{\cal X}\rightarrow K^{k}$ denote the homogeneous linear map that maps $p=p(X)\in{\cal X}$ to $(\psi_{B_{1}}(p),\ldots,\psi_{B_{k}}(p))$. Let $S({\cal B})=\{\psi_{B_{i}}\ |\ 1\leq i\leq k\}\subseteq R(\det,m)$.

We call $S({\cal B})$ an s.s.o.p. (small system of parameters)Such an s.s.o.p. is later called a strict s.s.o.p., as per the terminology in Section 5.3, wherein we introduce a more general definition of an s.s.o.p. But we shall not worry about this issue in this section. for $\Delta[\det,m]$ if (1) the total bit-length of $B_{i}$’s is ${\mbox{poly}}(m)$, and (2) the homogeneous linear map $\psi_{{\cal B}}$ does not vanish on any non-zero point in $\hat{\Delta}[\det,m]\subseteq{\cal X}$. Hence, $\psi_{{\cal B}}$ yields a regular (well-defined) map from $\Delta[\det,m]$ to $P(K^{k})$, which we denote by $\psi_{{\cal B}}$ again. We specify the s.s.o.p. $S({\cal B})$ succinctly by giving the matrices in ${\cal B}$. We call $\psi_{{\cal B}}$ the succinct normalizing map corresponding to this s.s.o.p.

It can be shown that an s.s.o.p. exists (Corollary 4.4). However, an s.s.o.p. with the optimal cardinality equal to $\dim(\Delta[\det,m])+1$ may not exist. This is why we allowed the slack above.

A ${\mbox{poly}}(m)$-time-constructible s.s.o.p. is called an e.s.o.p. (explicit system of parameters), where explicit means ${\mbox{poly}}(m)$-time-constructible. Quasi-s.s.o.p. and quasi-e.s.o.p. are defined by replacing ${\mbox{poly}}(m)$ by $\mbox{quasi-poly}(m):=2^{{\mbox{polylog}}(m)}$ throughout in the definitions.

The problem NNL for $\Delta[\det,m]$ is to construct an s.s.o.p. for $\Delta[\det,m]$, given the succinct specification of $\Delta[\det,m]$ in the form a circuit for computing $\det(X)$. We say that NNL for $\Delta[\det,m]$ has an explicit solution if $\Delta[\det,m]$ has an e.s.o.p.

The current best, unconditional, deterministic algorithm for constructing an s.s.o.p. for $\Delta[\det,m]$, based on Gröbner basis theory , also takes work-space that is exponential in $m$, and time that is double exponential in $m$ (cf. Theorem 4.10), as in the case of an h.s.o.p., again because the dimension of the ambient space $P({\cal X})$ containing $\Delta[\det,m]$ is exponential in $m$.

3 A Monte Carlo algorithm

The following result shows that, if we are satisfied with Monte Carlo algorithms, then an s.s.o.p. for $\Delta[\det,m]$ can be constructed efficiently and correctly, with a high probability.

An s.s.o.p. for $\Delta[\det,m]$ can be constructed by a ${\mbox{poly}}(m)$-time randomized Monte Carlo algorithm, whose output is correct with a high probability.

Hilbert’s original paper itself gives a randomized Monte Carlo algorithm to construct a normalizing map for any variety. For $\Delta[\det,m]$, the algorithm is the following: Just choose a random, homogeneous, linear map from $P({\cal X})$ to $P(K^{k})$, with $k>\dim(\Delta[\det,m])$. It can be shown using Gröbner basis theory (cf. the proof of Theorem 4.1) that it is a normalizing map with a high probability, if the entries of the matrix specifying this map are large enough randomly chosen integers of bit-length exponential in $\dim({\cal X})$. Since $\dim({\cal X})$ is exponential in $m$ in our context, the number of random bits used by this algorithm and its running time are thus double exponential in $m$. In contrast, the randomized algorithm in Theorem 1.1 uses only ${\mbox{poly}}(m)$ random bits and ${\mbox{poly}}(m)$ time. This is possible because the normalizing map constructed by this algorithm has a succinct specification. Obviously, the usual matrix representation of a linear map from ${\cal X}$ to $K^{k}$ is not succinct, since $\dim({\cal X})$ is exponential in $m$.

The Monte Carlo algorithm in Theorem 1.1 is not a BPP-algorithm, since NNL is not a decision problem, but rather a construction problem, whose output is not uniquely defined. More importantly, BPP is known to be in $\mbox{PH}\subseteq\mbox{PSPACE}$ . In contrast, Theorem 1.1 does not imply that NNL for $\Delta[\det,m]$ is in PSPACE. As already mentioned, at present we can only show unconditionally that it is in EXPSPACE. This is because the problem of verifying correctness of the output of the Monte Carlo algorithm in Theorem 1.1, a potential s.s.o.p., turns out to be very difficult. If the problem of verifying an s.s.o.p. were in PSPACE, then it would have followed from Theorem 1.1 that NNL for $\Delta[\det,m]$ is in PSPACE. But the current best algorithm for this verification requires exponential work-space (cf. Theorem 4.10).

Further results on NNL for $\Delta[\det,m]$ will be given in Section 1.6.

Theorem 1.1 holds with any explicit variety (cf. Definition 5.1) in place of $\Delta[\det,m]$.

Theorems 1.1 and 1.2 hold in arbitrary characteristic; cf. Section 10.5.

We next turn to some exceptional instances of explicit varieties for which NNL can be solved deterministically in quasi-polynomial time using the existing techniques.

4 The ring of matrix invariants

The first such instance is the categorical quotient associated with the ring of matrix invariants.

Let $M_{m}(K)$ be the space of $m\times m$ matrices over $K$. Let $V=M_{m}(K)^{r}$, the direct sum of $r$ copies of $M_{m}(K)$, with the adjoint (simultaneous conjugate) action of $G=SL_{m}(K)$.

Let $U=(U_{1},\ldots,U_{r})$ be an $r$-tuple of variable $m\times m$ matrices. The variable entries of $U_{i}$’s can be thought of as the coordinates of $V$, and the coordinate ring $K[V]$ of $V$ can be identified with the ring $K[U_{1},\ldots,U_{r}]$ generated by the variable entries of $U_{i}$’s. An invariant in $K[V]$ is a polynomial $f(U_{1},\ldots,U_{r})$ in the variable entries of $U_{i}$’s such that

for all $P\in G$. Let $n=\dim(V)=rm^{2}$. Let $K[V]^{G}\subseteq K[V]$ be the subring of invariants. It is finitely generated . Hence, by a general construction of algebraic geometry, one can associate with it the variety $V/G={\mbox{spec}}(K[V]^{G})$, called the categorical quotient .

We say that $V/G$ is strongly explicit if, given $m$ and $r$, one can construct in ${\mbox{poly}}(n)$ time a symbolic matrix $A(U,y)$ of ${\mbox{poly}}(n)$ size such that: (1) each entry of $A(U,y)$ is a (possibly non-homogeneous) linear function, with rational coefficients, of the entries of $U_{i}$’s and auxiliary variables $y=(y_{1},\ldots,y_{k})$, $k={\mbox{poly}}(n)$, and (2) the coefficients of $\det(A(U,y))$, considered as a polynomial in $y$, belong to and generate $K[V]^{G}$.

The categorical quotient $V/G$ is strongly explicit. It is strongly explicit in a relaxed sense (cf. Definition 5.2) if $K$ is an algebraically closed field of positive characteristic.

We specify $V/G$ and $K[V]^{G}$ succinctly by simply specifying $V$ and $G$, which can be done by giving $m$ and $r$ in unary. This succinct specification is polynomial-time-equivalent to the succinct specification of $V/G$ as an explicit variety in terms of the circuit for $\det(A(U,y))$, since, by Theorem 1.3, this circuit can be computed in ${\mbox{poly}}(n)$ time, given $m$ and $r$. The pair $(m,r)$ in unary will thus be the input in all the problems for $V/G$ and $K[V]^{G}$ described below. The bit-length of this succinct specification of $V/G$ is $O(m+r)=O(n)$, even though the dimension of the ambient space containing $V/G$ (cf. Section 6.2) is exponential in $m$. All space and time bounds for the algorithms below with this input will be in terms of $n$.

By Noether’s Normalization Lemma (Lemma 3.2), there exists a set $S\subseteq K[V]^{G}$ of ${\mbox{poly}}(n)$ homogeneous invariants such that $K[V]^{G}$ is integral over the subring generated by $S$.A ring $R$ is said to be integral over its subring $T$ if every $r\in R$ satisfies a monic polynomial equation of the form $r^{l}+b_{l-1}r^{l-1}+\ldots+b_{1}r+b_{0}=0$, where each $b_{i}\in T$. (This statement of Noether’s Normalization Lemma is equivalent to the one given in the beginning of this introduction.) In fact, there even exists such an $S$ of optimal cardinality equal to $\dim(K[V]^{G})$ (which is less than $n$). It is known that any generically chosen $S$ of this cardinality has the required property. Such an $S$ of optimal cardinality is called an h.s.o.p. (homogeneous system of parameters) of $K[V]^{G}$. (Existence of such an h.s.o.p. is again a classical fact, cf. Section 3, that holds for any finitely generated $K$-algebra.) It is shown here (cf. Theorem 7.3) that the problem of constructing an h.s.o.p. for $V/G$ is in EXPH (the exponential hierarchy), assuming the Generalized Riemann Hypothesis. The hierarchy is exponential, and not polynomial, because the dimension of the ambient space containing $V/G$ is exponential in $m$, and hence the current best PH-algorithm for Hilbert’s Nullstellensatz in Koiran becomes an EXPH-algorithm in our context. If we insist on an h.s.o.p., then this is the best that we can do at present. However, we can do much better if, as in Section 1.2, we relax the optimality constraint on the cardinality, but insist on succinctness of specification in exchange. We are thus led to the following notion of an s.s.o.p.

We call a set $S\subseteq K[V]^{G}$ an s.s.o.p. (small system of parameters) for $K[V]^{G}$ if (1) $S$ contains ${\mbox{poly}}(n)$ homogeneous invariants of ${\mbox{poly}}(n)$ degree, (2) $K[V]^{G}$ is integral over the subring generated by $S$, and (3) each invariant $s=s(U_{1},\ldots,U_{r})$ in $S$ can be expressed as a symbolic determinant of $O({\mbox{poly}}(n))$ size, i.e., as the determinant of a symbolic matrix $M_{s}$ of $O({\mbox{poly}}(n))$ size, whose entries are linear (possibly non-homogeneous) functions, with rational coefficients, of the variable entries of $U_{i}$’s, and (4) for each $s\in S$, the total bit-size of the specification of the symbolic matrix $M_{s}$ (including the total bit-size of the constants therein) is $O({\mbox{poly}}(n))$.

We call $S$ an e.s.o.p.(explicit system of parameters) if, in addition, given $m$ and $r$, the specification of $S$, consisting of a symbolic matrix $M_{s}$ as above for each $s\in S$, can be computed in ${\mbox{poly}}(n)$ time. This is a specialization to $V/G$ of the general definition of an e.s.o.p. for strongly explicit varieties (Definition 5.6) given later. Quasi-s.s.o.p. and quasi-e.s.o.p. are defined by replacing ${\mbox{poly}}(n)$ by quasi-${\mbox{poly}}(n)$ throughout in the definitions.

It can be shown that an s.s.o.p. exists (cf. Corollary 5.10).

By the problem NNL for $K[V]^{G}$ or $V/G$, we mean the problem of constructing an s.s.o.p. for $K[V]^{G}$, given the succinct specification of $K[V]^{G}$ in terms of the unary pair $(m,r)$. This definition of NNL is a specialization and simplification of the general definition of NNL for explicit varieties (Definition 5.6) given later. We say that NNL for $K[V]^{G}$ has an explicit solution if $K[V]^{G}$ has an e.s.o.p.

(For characteristic zero, see , , and Remark 1 in Section 1.7) Let $V=M_{m}(K)^{r}$, and $G=SL_{m}(K)$ as above. Then $K[V]^{G}$ has a quasi-e.s.o.p., assuming that $K$ is an algebraically closed field of characteristic $p\not\in[2,{\lfloor m/2\rfloor}]$.

A stronger form of this result (Theorem 10.1) implies quasi-explicit (i.e., quasi-polynomial-time computable) parametrization of the closed $G$-orbits in $V$ for any characteristic $p\not\in[2,{\lfloor m/2\rfloor}]$; cf. Theorem 10.15. Analogous results hold for the invariant ring associated with any quiver; cf. Theorem 10.8.

5 The general ring of invariants

We now describe another exceptional explicit variety for which NNL can be solved deterministically in quasi-polynomial time with the existing techniques. This is the categorical quotient associated with any invariant ring of $SL_{m}(K)$, with constant $m$, in characteristic zero.

Let $V$ be any finite dimensional representation of $G=SL_{m}(K)$, with arbitrary $m$ for the moment. Since $G$ is reductive , $V$ can be decomposed as a direct sum of irreducible representations of $G$:

Here $\lambda:\lambda_{1}\geq\ldots\geq\lambda_{l}$, $l<m$, is a partition, i.e., a non-increasing sequence of non-negative integers, $V_{\lambda}(G)$ is the irreducible representation of $G$ (Weyl module ) labelled by $\lambda$, and $m(\lambda)$ is its multiplicity. Fix the standard monomial basis for each $V_{\lambda}(G)$, and thus a standard monomial basis for $V$. Let $v=(v_{1},\ldots,v_{n})$, $n=\dim(V)$, be the coordinates of $V$ in this basis. Let $K[V]=K[v_{1},\ldots,v_{n}]$ be the coordinate ring of $V$. Let $K[V]^{G}$ be its subring of $G$-invariants. We call a polynomial $f(v)\in K[V]$ a $G$-invariant if $f(\sigma^{-1}v)=f(v)$ for all $\sigma\in G$. By Hilbert , $K[V]^{G}$ is finitely generated. Hence, one can associate with it the categorical quotient $V/G={\mbox{spec}}(K[V]^{G})$. We specify $V/G$ and $K[V]^{G}$ succinctly by just giving the specification $\langle V,G\rangle$ of $V$ and $G$, consisting of $n$ and $m$ (in unary), and the multiplicities $m(\lambda)$’s (in unary) for all $\lambda$’s that occur with nonzero multiplicity in the decomposition (1). The bit-length of this succinct specification is $O(n+m)$, though the dimension of the ambient space containing $V/G$ is exponential in $n$, even when $m$ is constant; cf. the proof of Proposition 9.3.

We call $V/G$ strongly explicit if, given $\langle V,G\rangle$, one can compute in ${\mbox{poly}}(n,m)$ time a symbolic matrix $A(v,y)$ such that: (1) each entry in $A(v,y)$ is a (possibly non-homogeneous) linear function, with rational coefficients, of the coordinates $v=(v_{1},\ldots,v_{n})$ and auxiliary variables $y=(y_{1},\ldots,y_{k})$, $k={\mbox{poly}}(n,m)$, and (2) the coefficients of $\det(A(v,y))$, considered as a polynomial in $y$, belong to and generate $K[V]^{G}$.

Let $V$ be a finite dimensional representation of $G=SL_{m}(K)$, with constant $m$, as above. Then $V/G$ is strongly explicit.

S.s.o.p., e.s.o.p., quasi-s.s.o.p., quasi-e.s.o.p. for strongly explicit $V/G$ are defined just as for the ring of matrix invariants in Section 1.4, except that we use the coordinates $v_{1},\ldots,v_{n}$ of $V$ in place of the coordinates for $M_{m}(K)^{r}$ used earlier, and the succinct specification $\langle V,G\rangle$ of $K[V]^{G}$ in place of the succinct specification of the ring of matrix invariants by the pair $(m,r)$ earlier; cf. Definition 9.1 for details.

For constant $m$, we define a near-e.s.o.p. for $K[V]^{G}$ by replacing ${\mbox{poly}}(n,m)$ in the definition of an e.s.o.p. by $O(n^{O(\log\log n)})$ throughout.

By the problem NNL for $K[V]^{G}$ or $V/G$, we mean the problem of constructing an s.s.o.p. for $K[V]^{G}$, given $\langle V,G\rangle$ as above. We say that NNL for $K[V]^{G}$ has an explicit solution if $K[V]^{G}$ has an e.s.o.p.

Let $V$ be a finite dimensional representation of $G=SL_{m}(K)$, with constant $m$, as above. Then $K[V]^{G}$ has a near-e.s.o.p.

Analogues of Theorems 1.5 and 1.6 hold for any connected, reductive, algebraic group of constant dimension (cf. Theorem 9.9).

By Theorems 9.7 and 2.1, the ring $K[V]^{G}$ has a quasi-e.s.o.p., without any restriction on $m$, if (1) the permanent of an $n\times n$ variable matrix $X$ cannot be computed by symbolic determinants over $X$ of $O(2^{n^{\epsilon}})$ sizeHere the entries of the symbolic matrices are possibly non-homogeneous linear functions of $X$., for some constant $\epsilon>0$, as $n\rightarrow\infty$ (cf. Valiant ), and (2) $V/G$ is explicit (cf. Conjecture 5.3 and the remark thereafter). Analogous results hold for any reductive, algebraic group (possibly disconnected) in zero or large enough characteristic (cf. Sections 9.6 and 10.5).

Classical invariant theory mainly studied the invariant ring $K[V]^{G}$ for constant $m$, as in Theorem 1.6, because of Gordan’s seminal work (cf. and Section 3.7 in ) that gave an algorithm for constructing a finite set of generators for the ring of invariants of binary forms. In this case, $V$ is the space of binary forms with the natural action of $SL_{2}(K)$, and $m=2$. In the modern terminology, Gordan showed that the problem of constructing finitely many generators for the ring invariants of binary forms is computable, though the formal notion of computability was developed much later. It was not known before Hilbert if this holds for general $m$, or even for $m=3$. It was not even known that finitely many generators exist when $m=3$. This was shown by Hilbert in his first paper for any $m$. But this proof was non-constructive. It was severely criticized by Gordan (cf. Section 3.7 in for this story), since it did not give an algorithm for constructing a set of generators. In the modern terminology, it did not yield a proof, as Gordan sought, for computability of the problem of constructing a set of generators for $K[V]^{G}$. Such a proof was given by Hilbert in his second paper , as a response to Gordan’s criticism. For these reasons, the second paper mainly focused on the case when $m=3$. Theorem 1.5, or rather its stronger form (Theorem 8.5), implies that the problem of constructing a set of generators for $K[V]^{G}$ for constant $m$ is, in fact, in $\mbox{DET}\subseteq\mbox{NC}\subseteq\mbox{P}$, allowing encoding of the set by a symbolic determinant. Theorem 1.6 shows that the original instance of NNL in Hilbert , with constant $m$, is in quasi-P.

6 Noether normalization vs. hardness

Next we ask if NNL for $\Delta[\det,m]$ can be solved deterministically in ${\mbox{poly}}(m)$ time. For the reasons explained later in Section 11, this turns out to be a much harder problem than the analogous problems for the special cases of explicit varieties addressed in Theorems 1.4 and 1.6. At present, we only have a conditional result:

The variety $\Delta[\det,m]$ has a quasi-e.s.o.p., if the permanent of an $n\times n$ variable matrix $X$ cannot be approximated infinitesimally closely by symbolic determinants over $X$ of size $\leq 2^{n^{\epsilon}}$, for some constant $\epsilon>0$, as $n\rightarrow\infty$.

The lower bound assumption for the permanent in the result above is a stronger form of the hardness hypothesis for the permanent in geometric complexity theory (cf. Conjecture 4.3 in ), with $\Omega(2^{n^{\epsilon}})$ lower bound in place of the superpolynomial lower bound.

Actually, we prove a stronger result (Theorem 4.7) that, under this lower bound assumption, NNL for $\Delta[\det,m]$ can even be solved fast in parallel.

Theorem 1.7 holds with any explicit variety (cf. Definition 5.1) in place of $\Delta[\det,m]$.

By these results, NNL for any explicit variety can be brought down from EXPSPACE to quasi-P, assuming the hardness hypothesis for the permanent in geometric complexity theory. The quasi-prefix can be removed under a stronger assumption (cf. Theorem 4.5).

Theorem 1.7 is a consequence of the following stronger result. It shows that solving NNL for $\Delta[\det,m]$ in deterministic polynomial time is in fact equivalent, ignoring a quasi-prefix, to proving a weaker implication of the hardness hypothesis in Theorem 1.7.

The variety $\Delta[\det,m]$ has an e.s.o.p. iff, ignoring a quasi-prefix, there exists a family $\{f_{n}(x_{1},\ldots,x_{n})\}$ of exponential-time-computable, integral, multi-linear polynomials such that $f_{n}$ cannot be approximated infinitesimally closely by symbolic determinants over $(x_{1},\ldots,x_{n})$ of size $\leq 2^{n^{\epsilon}}$, for some constant $\epsilon>0$, as $n\rightarrow\infty$.

By exponential-time-computable, we mean that the polynomial can be computed, given an integral input, in time that is exponential in the total bit-length of the input.

Theorems 1.7, 1.8, 1.9, and their analogues for explicit varieties also hold in large enough positive characteristics (cf. Section 10.5). Furthermore, the largeness restriction on the characteristic can be removed assuming a slight extension of the hardness hypothesis; cf. Remark 1 at the end of Section 10.

These results establish an essential equivalence between the problem NNL for explicit varieties and the weaker form of the hardness hypothesis in geometric complexity theory.

7 Proof technique

We now briefly explain how the main results in this article are proved.

The formal notion of explicitness introduced in this article (Definition 5.1) lies at the heart of the proofs, along with the fundamental work in algebraic geometry and geometric invariant theory, the fundamental work in algebraic complexity theory, and the fundamental work on a derandomization problem in complexity theory, called black-box polynomial identity testing. Derandomization means converting a randomized efficient algorithm into a deterministic efficient algorithm by removing random bits. Theorems 1.4 and Theorems 1.6–1.9 are proved by derandomizing the Monte Carlo algorithm in Theorem 1.2 for the explicit varieties under consideration, unconditionally or assuming a suitable hardness hypothesis. Derandomization of this Monte Carlo algorithm for a given explicit variety amounts to bringing NNL for that variety from EXPSPACE, where it is by the general result (Theorem 5.12), to P. This EXPSPACE vs. P gap in the complexity of NNL that needs to be bridged to derandomize this Monte Carlo algorithm for a given explicit variety is the basic difference between derandomization in this article and derandomization in the earlier articles in complexity theory, wherein such a gap is absent. The use of geometric invariant theory in derandomization, as in the proofs of Theorems 1.4 and 1.6, is another basic difference. In contrast, the earlier works on derandomization in complexity theory do not use any invariant theory.

The efficient Monte Carlo algorithm for NNL for explicit varieties in Theorems 1.1 and 1.2 is based on the classical results in algebraic geometry due to Hilbert and others, and the fundamental work in Heintz and Schnorr on black-box polynomial identity testing; cf. Section 4.2.

Theorem 1.3 on explicitness of the categorical quotient associated with the ring of matrix invariants is proved in characteristic zero using the First and Second Fundamental Theorems for matrix invariants due to Procesi and Razmyslov ; cf. Section 6.

The situation in positive characteristic turns out to be much harder. The analogous First Fundamental Theorem for matrix invariants in positive characteristic in Donkin is too weak for the proof of Theorem 1.3 in positive characteristic, since the only known upper bound for the degrees of the generators in is exponential in the size $m$ of the matrices. The crux of the proof of Theorem 1.3 in positive characteristic is the geometric First Fundamental Theorem (cf. Theorem 10.2) proved in this article, which provides a set of separating matrix-invariants of polynomial degree in arbitrary characteristic. This is proved here using the criterion for stability in arbitrary characteristic due to Hilbert , Mumford et al. , and King , and the fundamental Brauer-Nesbitt theorem in modular representation theory.

The explicitness result in Theorem 1.3 lies at the heart of the proof of Theorem 1.4.

Theorem 1.3, in conjunction with Theorem 1.2 (which holds in arbitrary characteristic, cf. Section 10.5), implies that NNL for the ring of matrix invariants has a polynomial-time Monte Carlo algorithm in arbitrary characteristic.

Theorem 1.4 is proved by derandomizing this Monte Carlo algorithm, up to a quasi-prefix; cf. Sections 7 and 10.1. This is done in two steps.

The first crucial step (for the reasons that will become clear in Section 11) is to show that this Monte Carlo algorithm can be derandomized assuming the standard black-box derandomization hypothesis for symbolic determinant identity testing , which is recalled in Section 2.3 here. This is shown using the fundamental work in Hilbert and Mumford et al. ; cf. Theorem 5.13, Remark 3 thereafter, and Remark 2 in Section 10.5. This implies that NNL for the ring of matrix invariants has a deterministic polynomial-time algorithm assuming the standard black-box derandomization hypothesis for symbolic determinant identity testing.

Remark 1 (on the second step of derandomization): In the preliminary version of this article, only this conditional result was proved in characteristic zero. Subsequently it was pointed out by Forbes and Shpilka that the step in the proof of this result wherein symbolic determinant identity testing enters can be modified, as explained in Section 7.5 here, so as to use instead the polynomial identity testing for read-once oblivious algebraic branching programs (cf. Section 2.1). A quasi-polynomial-time deterministic black-box algorithm for this problem was already known from their earlier work . Thus this instance of NNL can be solved deterministically in quasi-polynomial time in characteristic zero using the existing techniques. This is contrary to what was suggested in the preliminary version of this article, because of the relationship of this problem with the wild (“impossible”) problem of classifying matrix tuples (though this instance of NNL itself is not wild).

This proof of Theorem 1.4 in characteristic zero can be extended to any characteristic $p\not\in[2,{\lfloor m/2\rfloor}]$, using the refined form of the Geometric First Fundamental Theorem for matrix invariants (cf. Theorem 10.2) proved in this article, in place of the First Fundamental Theorem for matrix invariants due to Procesi and Razmyslov ; cf. Section 10.1.

Theorem 1.5 on explicitness of the categorical quotient associated with the general ring of invariants of $SL_{m}$, for constant $m$, is proved using the fundamental works in geometric invariant theory due to Hilbert , Mumford et al. , and Derksen and Kemper , in conjunction with standard monomial theory , and the fundamental works in algebraic complexity theory due to Strassen , Valiant , Malod and Portier , and others; cf. Section 8.

The explicitness result in Theorem 1.5 lies at the heart of the proof of Theorem 1.6.

Theorem 1.5, in conjunction with Theorem 1.2, implies that NNL for the general ring of invariants of $SL_{m}$, for constant $m$, has a polynomial-time Monte Carlo algorithm in characteristic zero.

Theorem 1.6 is proved by derandomizing this Monte Carlo algorithm, up to a quasi-prefix; cf. Section 9. This is again done in two steps.

The first crucial step is, again, to show that this Monte Carlo algorithm can be derandomized assuming the standard black-box derandomization hypothesis for symbolic determinant identity testing. This can be done (just as in the case of Theorem 1.4) using the work of Hilbert and Mumford et al. ; cf. Theorem 5.13 and Remark 3 thereafter. This implies that NNL for the general ring of invariants of $SL_{m}$, for constant $m$, has a deterministic polynomial-time algorithm in characteristic zero, assuming the standard black-box derandomization hypothesis (cf. Section 2.3) for symbolic determinant identity testing.

Using a refined form (Theorem 8.5) of Theorem 1.5 in the first step, it follows that NNL for the general ring of invariants of $SL_{m}$, for constant $m$, has a deterministic polynomial-time algorithm assuming a weaker black-box derandomization hypothesis for diagonal depth three circuits .

This hypothesis was already known to hold, up to a quasi-prefix, from the earlier work of Shpilka and Volkovich , and Agrawal, Saha, and Saxena . Thus it follows that NNL for $V/G$ as in Theorem 1.6 can be solved in quasi-polynomial time deterministically. This was the result that was stated in the preliminary version of this article. The stronger $O(n^{O(\log\log n)})$-time bound stated in Theorem 1.6 follows in view of the recent result in Forbes, Saptharishi, and Shpilka , which gives an $O(s^{O(\log\log s)})$-time-computable black-box derandomization of polynomial identity testing for diagonal depth three circuits of size $\leq s$.

Let us now turn to Theorem 1.9, Theorem 1.7 being its corollary.

The first step is to show that the Monte Carlo polynomial-time algorithm for NNL for $\Delta[\det,m]$ in Theorem 1.1 can be derandomized assuming a strengthened form, introduced in this article (cf. Section 2.5), of the standard black-box derandomization hypothesis for symbolic determinant identity testing; cf. Section 4.3.

By Kabanets and Impagliazzo , the standard hypothesis holds, up to a quasi-prefix, assuming a sub-exponential symbolic determinant lower bound for some family of exponential-time-computable, integral, multi-linear polynomials.

It is similarly shown in this article (cf. Theorem 2.4 and the remark thereafter) that the strengthened hypothesis holds, up to a quasi-prefix, if there exists a family $\{f_{n}(x_{1},\ldots,x_{n})\}$ of exponential-time-computable, integral, multi-linear polynomials such that $f_{n}$ cannot be approximated infinitesimally closely by symbolic determinants of size sub-exponential in $n$. This is proved using the fundamental work on black-box factorization of multivariate polynomials in Kaltofen and Trager , which lies at the heart of this proof, in conjunction with the fundamental hardness vs. randomness principle in Nisan and Wigderson , and Kabanets and Impagliazzo .

This implies the reduction from NNL to hardness stated in Theorem 1.9. The reduction in the other direction is easy (cf. Lemma 4.8 and Proposition 2.7).

Theorem 1.8 and the generalization of Theorem 1.9 for general explicit varieties (Theorem 5.14) follow by systematically extending the proofs of Theorems 1.7 and 1.9; cf. Section 5.

The proofs of these results can be extended to large enough positive characteristics using the standard techniques of algebraic geometry and algebraic complexity theory; cf. Section 10.5.

Conditional generalizations of Theorem 1.6 to explicit categorical quotients associated with representations of general reductive algebraic groups are given in Section 9.6. These can be proved by extending the proof for $SL_{m}$ using the standard techniques in geometric invariant theory and representation theory.

Organization of the paper

The rest of this paper is organized as follows.

Logical structure of the proofs: The proofs of the main results are presented in the following steps. (1) The variety under consideration is shown to be explicit. (2) An EXPSPACE-algorithm is given for constructing an h.s.o.p. for the variety. For the categorical quotient associated with the ring of matrix invariants, a more efficient EXPH-algorithm is given, assuming the Generalized Riemann Hypothesis. (3) An efficient Monte Carlo algorithm is given for constructing an s.s.o.p. for the variety. (4) This algorithm is derandomized using the strengthened or the standard form of the black-box derandomization hypothesis for an appropriate class of circuits. Which form is used depends on the closure properties of the variety. The class of circuits also depends on the variety. (5) If this class is sufficiently restricted, as happens for the categorical quotients associated with the ring of matrix invariants and the general ring of invariants of $SL_{m}$ with constant $m$, then this black-box derandomization is carried out unconditionally, up to a quasi-prefix. (6) Otherwise, it is shown that the black-box derandomization hypothesis holds assuming an appropriate hardness hypothesis.

Organization of the sections: In Section 2, we introduce the strengthened form of the standard black-box derandomization hypothesis for polynomial identity testing, and prove the essential equivalence between strengthened black-box derandomization and sub-exponential algebraic circuit size lower bounds for infinitesimally close approximation. This is a key ingredient in the proofs of Theorems 1.7, 1.8, and 1.9. In Section 3, we recall Noether’s Normalization Lemma, and show that the problem of constructing an h.s.o.p. for a general variety, specified in the standard fashion by its defining equations, belongs to PH, assuming the Generalized Riemann Hypothesis. In Section 4, we study the basic prototype $\Delta[\det,m]$ of an explicit variety, and prove Theorems 1.1, 1.7, and 1.9. In Section 5, we formulate the general notion of an explicit variety motivated by its basic prototype $\Delta[\det,m]$, define the problem NNL for explicit varieties, and prove Theorems 1.2, 1.8, and the generalization of Theorem 1.9 for explicit varieties. In Section 6, we prove Theorem 1.3 in characteristic zero. Theorem 1.4 in characteristic zero is proved in Section 7. In Section 8, we prove Theorem 1.5. Theorem 1.6 is proved in Section 9. Theorems 1.3 and 1.4 in arbitrary characteristic, their generalizations to quivers, and extensions of Theorems 1.7, 1.8, and 1.9 to large enough positive characteristics are proved in Section 10. It is also explained in Section 10 how Theorems 1.1 and 1.2 can be extended to arbitrary characteristics. Furthermore, implications of the results in this article to explicit parametrization of closed orbits and explicit parametrization of semi-simple representations of finitely generated algebras are also given in Section 10. Finally, in Section 11, we discuss the difficulties that need to be overcome to improve the current best bound for NNL for $\Delta[\det,m]$ in Theorem 4.10.

Black-box polynomial identity testing

In this section, we introduce the strengthened black-box derandomization hypothesis for polynomial identity testing (cf. Section 2.5), and prove the essential equivalence between strengthened black-box derandomization and sub-exponential lower bounds for infinitesimally close approximation (cf. Theorem 2.4 and Proposition 2.7). This is a key ingredient in the proofs of Theorems 1.7, 1.8, and 1.9.

We begin by recalling the circuit classes for which we need these hypotheses.

We say that the circuit $C=C(x_{1},\ldots,x_{n})$ over the variables $x_{1},\ldots,x_{n}$ has low or small degree if the degree of the polynomial computed by it is $O(s^{a})$, for some fixed constant $a>0$, where $s$ is the size of $C$.

By a weakly skew circuit, we mean a circuit whose each node $v$ labelled with $*$ has at least one child $u$ such that the sub-circuit rooted at $u$ is connected to the rest of the circuit by just the edge $(u,v)$.

By a symbolic determinant over $x_{1},\ldots,x_{n}$ of size $m$, we mean the determinant of a symbolic $m\times m$ matrix, whose each entry is a linear combination (possibly non-homogeneous) over $K$ of of $x_{1},\ldots,x_{n}$. Weakly skew circuits are polynomially equivalent to symbolic determinants.

Weakly skew circuits are also polynomially equivalent to algebraic branching programs . In this article we will only use a special class of such programs called read-once oblivious algebraic branching programs . Such a program can be specified, for some $n,l$, and $d$, by a tuple $(M_{1},M_{2},\ldots,M_{l})$ of $n\times n$ matrices such that every entry of $M_{i}$, $1\leq i\leq l$, is a uni-variate polynomial of degree $\leq d$ over $K$ in the distinct variable $z_{i}$ associated with $M_{i}$. The uni-variate polynomials are specified by giving all their coefficients. The size of this program is $O(n^{2}ld)$. The polynomial computed by this program is defined to be ${\mbox{trace}}(\prod_{i}M_{i})$. Clearly, this polynomial can also be computed by a weakly skew circuit of ${\mbox{poly}}(n,l,d)$ size. Hence, such programs can be viewed as restricted classes of weakly skew circuits, or equivalently, symbolic determinants.

A diagonal depth three circuit $C$ over the variables $x_{1},\ldots,x_{n}$ is a circuit that computes a sum $\sum_{i=1}^{k}f_{i}^{e_{i}}$ of powers of linear functions, where each $f_{i}$ is a possibly non-homogeneous linear function of $x_{i}$’s with coefficients in $K$. Here $k$ is called the top fan-in of the circuit, and $e=\max\{e_{i}\}$ its degree. The size of this circuit is $O(nek)$.

By a circuit with oracle gates for a function $f(y_{1},\ldots,y_{r})$, we mean a circuit in which some gates are labelled with $f$. These gates have in-degree $r$. The computation of $f$ at any such gate is assigned unit cost.

2 Polynomial identity testing

Next, we recall the standard black-box derandomization hypothesis for polynomial identity testing over the algebraically closed base field $K$.

The polynomial identity testing problem over $K$ is the problem of deciding if a given circuit $C(x)$, $x=(x_{1},\ldots,x_{r})$, over $K$ computes an identically zero polynomial. By the polynomial identity testing problem for small degree circuits, or the low-degree polynomial identity testing problem, we mean the polynomial identity testing problem wherein the degree of the polynomial computed by $C(x)$ is assumed to be $O(s^{a})$, for some constant $a>0$, where $s$ is the size of $C(x)$.

There is a simple randomized polynomial-time algorithm for deciding if a given circuit with rational constants computes an identically zero polynomial: just substitute large enough random integer values for the variables, and test if the circuit evaluates to zero.

The white-box derandomization problem for polynomial identity testing is to find a deterministic polynomial time algorithm for deciding if a given circuit with rational constants computes an identically zero polynomial.

The standard black-box derandomization hypotheses for the restricted circuit classes in Section 2.1 are defined similarly.

3 Symbolic determinant identity testing

We now describe such a hypothesis for symbolic determinants (cf. Section 2.1) in more detail, since it plays a crucial role in this paper.

4 Black-box polynomial identity testing vs. hardness

The following result is a variant of Theorem 7.7 in . This is why polynomial identity testing is expected to have efficient black-box derandomization.

(cf. Theorem 7.7 in ) Suppose there exists a family $\{f_{m}(x_{1},\ldots,x_{m})\}$ of exponential-time-computable, multi-linear, integral polynomials such that $f_{m}$ cannot be evaluated by a circuit over $K$ of $O(2^{m^{a}})$ size, for some constant $a>0$, as $m\rightarrow\infty$. Then polynomial identity testing for small degree circuits over $K$ of size $\leq s$ has $O(2^{{\mbox{polylog}}(s)})$-time-computable black-box derandomization.

Here by an exponential-time-computable, integral polynomial $f_{m}(x_{1},\ldots,x_{m})$, we mean a polynomial such that, given an integral input $a=(a_{1},\ldots,a_{m})$, $f_{m}(a)$ can be computed in time that is exponential in the total bit-length of $a$. Since $f_{m}$ here is multi-linear, this is equivalent to saying that the coefficient vector of $f_{m}$ can be computed in time exponential in $m$.

The proof of Theorem 2.1 is similar to that of Theorem 7.7 in (which works in the black-box model). Since we are going to prove its stronger form (Theorem 2.4) later, we only point out here how to take care of the main difference between the setting in and the one here. The difference is that in the size of the circuit is defined to be the total number of edges in it plus the total bit-length of the constants, whereas here the size means the total number of edges. A key ingredient in the proof in is an efficient algorithm in for factoring multivariate polynomials (cf. Lemma 7.6. in ). In its place we use instead the following result in that does not depend on the bit-lengths of the constants in the circuit.

(cf. Corollary 6.2. in , Theorem 1 in , and Theorem 2.21 in Bürgisser )

Suppose $\{g_{n}(x_{1},\ldots,x_{n})\}$ is a $p$-computable family of polynomials over $K$. This means $g_{n}$ is a polynomial of ${\mbox{poly}}(n)$ degree that can be computed by a nonuniform circuit over $K$ of ${\mbox{poly}}(n)$ size. Then each factor of $g_{n}$ in $K[x_{1},\ldots,x_{n}]$ can also be computed by a nonuniform circuit over $K$ of ${\mbox{poly}}(n)$ size.

More generally, given any families $\{g_{n}(x_{1},\ldots,x_{n})\}$, $\{f_{n}(x_{1},\ldots,x_{n})\}$ of polynomials over $K$, with $f_{n}$ dividing $g_{n}$, there exists for every $n$ a nonuniform circuit over $K$ of ${\mbox{poly}}(n,\deg(g_{n}))$ size, with oracle gates for $g_{n}$, that computes $f_{n}$.

A simpler proof of the first statement in Theorem 2.2 can be found in Section 2.3 in Bürgisser (cf. Theorem 2.21 therein). Bürgisser also proves a stronger statement in (cf. Theorem 1.3 therein) concerning complexity of infinitesimally close approximation. For the converse of Theorem 2.1, see .

5 The strengthened black-box derandomization hypothesis

Next, we formulate the strengthened black-box derandomization hypothesis for polynomial identity testing.

Let $x=(x_{1},\ldots,x_{r})$ be a tuple of $r$ variables. The strengthened black-box derandomization problem for small degree circuits is to construct in ${\mbox{poly}}(s)$ time a hitting set against all nonzero polynomials $f(x)\in K[x]$ of degree $\leq d=O(s^{a})$, $a>0$ a constant, that can be approximated infinitesimally closely by circuits over $K$ and $x$ of size $\leq s$, given $r,s$, and $d$ in unary.

The following result implies that such a hitting set exists. For any positive integer $u$, let $[u]:=\{1,\ldots,u\}$.

(cf. Theorem 4.4 in and its proof) A randomly chosen subset $B\subseteq[u]^{r}$, $u=2s(d+1)^{2}$, of size $q=6(s+1+r)^{2}$ is with a high probability a hitting set against all non-zero polynomials that can be approximated infinitesimally closely by circuits over $K$ and $r$ variables of size $\leq s$ and degree $\leq d$. Specifically, at least $(1-u^{-q/6})$-th fraction of the sequences $(b_{1},\ldots,b_{q})$, $b_{i}\in[u]^{r}$, are hitting.

The strengthened black-box-derandomization hypothesis for polynomial identity testing for small degree circuits is that there exists a ${\mbox{poly}}(s)$-time-computable hitting set $S_{r,s}$. We call such a hitting set explicit. More generally, if a hitting set is computable in $O(T(s))$ time, we say that the polynomial identity testing for small degree circuits of size $\leq s$ has $O(T(s))$-time-computable strengthened black-box derandomization. The strengthened black-box derandomization hypothesis for general polynomial identity testing without any degree restrictions is defined similarly.

The similar strengthened black-box derandomization hypothesis for symbolic determinant identity testing is that, given $n$ and $m$, one can construct in ${\mbox{poly}}(n,m)$ time a hitting set against all nonzero homogeneous polynomials $h(x_{1},\ldots,x_{n})$’s over $K$ of degree $m$ that can be approximated infinitesimally closely by symbolic determinants (cf. Section 2.3) of size $m$ over $x_{1},\ldots,x_{n}$.

The strengthened black-box derandomization hypothesis is counter-intuitive unlike the standard hypothesis in Section 2.2. Conjecturally (cf. Section 11), there exist integral polynomials of small degree that can be approximated infinitesimally closely by small circuits over $K$ but cannot be computed exactly by such circuits. Hence, a priori, there is no reason why there should exist easy-to-compute hitting sets against such hard-to-compute polynomials.

6 Equivalence between strengthened black-box derandomization and lower bounds for infinitesimally close approximation

The following strengthening of Theorem 2.1 says that one can still compute efficiently in quasi-polynomial time a hitting set against such polynomials, assuming a sub-exponential lower bound for infinitesimally close approximation for a family $\{p_{m}\}$ of exponential-time-computable, multi-linear, integral polynomials. A good candidate for $p_{m}$ is the permanent. It cannot be approximated infinitesimally closely by small algebraic circuits as per the hardness hypothesis of geometric complexity theory. The result below is the main reason why the strengthened black-box derandomization hypothesis is expected to hold.

Suppose there exists a family $\{p_{m}(x_{1},\ldots,x_{m})\}$ of exponential-time-computable, multi-linear, integral polynomials such that $p_{m}$ cannot be approximated infinitesimally closely by circuits over $K$ of $O(2^{m^{\epsilon}})$ size, for some constant $\epsilon>0$, as $m\rightarrow\infty$. Then polynomial identity testing for small degree circuits over $K$ with size $\leq s$ and $n\leq s$ variables has $O(2^{{\mbox{polylog}}(s)})$-time-computable strengthened black-box derandomization.

This result also holds if we use symbolic determinants instead of circuits in the lower bound hypothesis; cf. the proof of Theorem 4.6.

Proof: We extend the proof of Theorem 7.7 in Kabanets and Impagliazzo using Theorem 2.2, which lies at the heart of this proof.

We want to construct in quasi-${\mbox{poly}}(s)$ time a hitting set for strengthened black-box derandomization of polynomial identity testing for small degree circuits with size $\leq s$ and $n\leq s$ variables.

Let $m=(\log s)^{e}$, for a large enough constant $e$ to be fixed later. Construct an $NW$-design for this $n$ (the number of variables) with this choice of $m$. By the NW-design, we mean a family of sets $R_{1},\ldots,R_{n}\subseteq[l]$, $l\leq m^{2}=(\log s)^{2e}$, each of cardinality $m$, such that $|R_{i}\cap R_{j}|\leq\log n$, for all $i\not=j$. By (cf. Lemma 2.23 in ), such a set system can be constructed in ${\mbox{poly}}(n,2^{l})=O(2^{{\mbox{polylog}}(s)})$ time.

This set system and the given hard multi-linear polynomial $p(x_{1},\ldots,x_{m})$ together yield an arithmetic NW-generator $NW^{p}$. By this we mean the function

where $x|_{R}$ denotes the tuple of the elements in $x$ indexed by $R$.

The set $H=\{NW^{p}(a)\ |\ a\in[D]^{l}\}$, $D=dm+1$, is a hitting set against every nonzero polynomial $f(y)$, $y=(y_{1},\ldots,y_{n})$, of degree $\leq d=O(s^{t})$, $t>0$ a constant, that can be approximated infinitesimally closely by circuits over $K$ and $y=(y_{1},\ldots,y_{n})$ of size $\leq s$ (assuming that the constant $e$ above is chosen to be large enough).