Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing

Introduction

Many results in mathematics are non-constructive, in the sense that they establish that certain mathematical objects exist, but do not give an efficient or explicit construction of such objects, and often further work is needed to find constructive arguments. Motivated by the recent results of Mulmuley [Mul12a] (henceforth “Mulmuley”, but theorem and page numbering will refer to the full version [Mul12b]), this paper studies constructive versions of the Noether Normalization Lemma from commutative algebra. The lemma, as used in this paper, can be viewed as taking a commutative ring $R$, and finding a smaller subring $S\subseteq R$ such that $S$ captures many of the interesting properties of $R$ (see Section 1.2 for a formal discussion). Like many arguments in commutative algebra, the usual proof of this lemma does not focus on the computational considerations of how to find (a concise representation of) the desired subring $S$. However, the area of computational commutative algebra (eg, [DK02, CLO07]) offers methods showing how many classic results can be made constructive, and in certain cases, the algorithms are even efficient.

While constructive methods for Noether Normalization are known using Gröbner bases (cf. [CLO07]), the Gröbner basis algorithms are not efficient in the worst-case (as show by Mayr and Meyer [MM82]), and are not known to be more efficient for the problems we consider. Diverging from the Gröbner basis idea, Mulmuley recently observed that a constructive version of Noether Normalization is really a problem in derandomization. That is, given the ring $R$, if we take a sufficiently large set of “random” elements from $R$, then these elements will generate the desired subring $S$ of $R$. Indeed, the usual proof of Noether Normalization makes this precise, with the appropriate algebraic meaning of “random”. This view suggests that random sampling from $R$ is sufficient to construct $S$, and this sampling will be efficient if $R$ itself is explicitly given. While this process uses lots of randomness, the results of the derandomization literature in theoretical computer science (eg, [IW97, IKW02, KI04]) give strong conjectural evidence that randomness in efficient algorithms is not necessary. Applied to the problems here, there is thus strong conjectural evidence that the generators for the subring $S$ can be constructed efficiently, implying that the Noether Normalization Lemma can be made constructive.

Motivated by this connection, Mulmuley explored what are the minimal derandomization conjectures necessary to imply an explicit form of Noether Normalization. The existing conjectures come in two flavors. Most derandomization hypotheses concern boolean computation, and as such are not well-suited for algebraic problems (for example, a single real number can encode infinitely many bits), but Mulmuley does give some connections in this regime. Other derandomization hypotheses directly concern algebraic computation, and using them Mulmuley gives an explicit Noether Normalization Lemma, for some explicit rings of particular interest. In particular, Mulmuley proves that it would suffice to derandomize the polynomial identity testing (PIT) problem in certain models, in order to obtain a derandomization of the Noether Normalization Lemma. Mulmuley actually views this connection as an evidence that derandomizing PIT for these models is a difficult computational task (Mulmuley, p. 3) and calls this the GCT chasm. Although Mulmuley conjectures that it could be crossed he strongly argues that this cannot be achieved with current techniques (Mulmuley, p. 3):

On the negative side, the results in this article say that black-box derandomization of PIT in characteristic zero would necessarily require proving, either directly or by implication, results in algebraic geometry that seem impossible to prove on the basis of the current knowledge.

In this work, we obtain a derandomization of Noether’s Normalization Lemma for the problems discussed in Mulmuley’s Theorems 1.1 and 1.2, using existing techniques. These results alone have been suggested by Mulmuley (in public presentation) to contain the “impossible” problems mentioned above. This suggests that problems cannot be assumed to be difficult just because they originated in algebraic-geometric setting, and that one has to consider the finer structure of the problem.

In addition, just as Mulmuley’s techniques extend to Noether Normalization of arbitrary quivers (Mulmuley’s Theorem 4.1), our results also extend to this case, but we omit the straightforward details. However, we do not give any results for Noether Normalization of general explicit varieties as discussed in Mulmuley’s Theorem 1.5, and indeed that seems difficult given that Mulmuley’s Theorem 1.6 gives an equivalence between general PIT and Noether Normalization for a certain explicit variety.The main reason we could obtain our results is that for the variety we consider, there are explicitly known generators for the ring of invariants (as given in Theorem 1.3), and these generators are computationally very simple. For general explicit varieties, obtaining such explicit generators is an open problem, and even if found, the generators would not likely be as computational simple as the generators of Theorem 1.3. We refer the reader to Mulmuley’s Section 10 where these issues are discussed further.

We start by briefly describing the PIT problem. For more details, see the survey by Shpilka and Yehudayoff [SY10].

2 Noether Normalization for the Invariants of Simultaneous Conjugation

Mulmuley showed that when $R$ is a particular ring, then the problem of finding the subring $S$ given by Noether Normalization can be reduced to the black-box PIT problem, so that explicit hitting sets (of small size) would imply a constructive version of Noether Normalization for this ring. The ring considered here and in Mulmuley’s Theorems 1.1 and 1.2 is the ring of invariants of matrices, under the action of simultaneous conjugation.

The above result is explicit in two senses. The first sense is that all involved field constants can be efficiently constructed. The second is that for any $f\in\mathcal{T}$ and $\vec{A}$, $f(\vec{A})$ can be computed quickly. In particular, any $f\in\mathcal{T}$ can be computed by a $\poly(n,r)$-sized algebraic circuit, as matrix multiplication and trace can be computed efficiently by circuits. We encapsulate these notions in the following definition.

In particular, the above definition implies that the resulting circuits $C$ have size at most $t(n)$. The class of circuits $\mathcal{C}$ can be the class of all algebraic circuits, or some restricted notion, such as algebraic branching programs, which are defined later in this paper. Thus, in the language of the above definition, the set of generators $\mathcal{T}$ has $\poly(n,r)$-explicit algebraic circuits.

However, the above result is unsatisfactory in that the set of generators $\mathcal{T}$ has size $\exp(\poly(n,r))$, which is unwieldy from a computational perspective. One could hope to find a smaller set of generators, but the lower bound in the above theorem seems a barrier in that direction. The number of generators is relevant here, as we will consider three computational problems where these generators are useful, but because of their number the resulting algorithms will be exponential-time, where one could hope for something faster. To define these problems, we first give the following standard definition from commutative algebra.

Let $R$ be a commutative ring, and $S$ a subring. Then $R$ is integral over $S$ if every element in $R$ satisfies some monic polynomial with coefficients in $S$.

As before, we will ask whether we can find an explicit construction.

Mulmuley observed that by the dictionary of geometric invariant theory [MFK94], $\vec{A}$ and $\vec{B}$ have a non-empty intersection of their orbit closures iff they are not distinguishable by any set of separating invariants. Thus, any explicit set $\mathcal{T}^{\prime}$ of separating invariants, would answer this question, as one could test if $f$ agrees on $\vec{A}$ and $\vec{B}$ (as $f$ is easy to compute, as it has a small circuit), for all $f\in T^{\prime}$. Thus, as before, 1.9 can be solved positively by a positive answer to 1.8.

The main results of this paper provide positive answers to Questions 1.6, 1.8 and 1.9.

3 Mulmuley’s results

Having introduced the above questions, we now summarize Mulmuley’s results that show that these questions can be solved positively if one assumes that there exist explicit hitting sets for a certain subclass of algebraic circuits, which we now define. We note that Mulmuley defines this model using linear, and not affine functions. However, we define the model using affine functions as this allows the model to compute any polynomial (and not just homogeneous polynomials), potentially with large size. However, this is without loss of generality, as derandomizing PIT is equally hard in the linear and the affine case, via standard homogenization techniques, see 4.1.

As matrix multiplication and trace both have small algebraic circuits, it follows that traces of matrix powers have small circuits. Further, as a restricted class of algebraic circuits, we can seek to deterministically solve the PIT problem for them, and the hypothesis that this is possible is potentially weaker than the corresponding hypothesis for general algebraic circuits. However, this hypothesis, in its black-box form, is strong enough for Mulmuley to derive implications for the above questions.

Assuming various plausible conjectures and using the requisite results in derandomization literature, Mulmuley showed that small explicit hitting sets exist, removing the need to outright conjecture the existence of such hitting sets. This thus established the conjectural existence of small explicit sets of separating invariants by the above theorem. We list one such conditional result here, noting that all such conditional results Mulmuley derived gave sets of separating invariants of quasi-polynomial size, or worse.

While the above result is conditional, unconditional results can also be derived, if randomness is allowed. That is, by exploiting the connection between separating invariants and closed orbit intersections mentioned above, and using that PIT can be solved using randomness, Mulmuley obtains the following randomized algorithm.

Using the just mentioned conjectures, Mulmuley can also partially derandomize the above algorithm, but not to within polynomial time.

4 Our Results

We study further the connection raised by Mulmuley regarding the construction of separating invariants and the black-box PIT problem. In particular, we more carefully study the classes of algebraic circuits arising in the reduction from Noether Normalization to PIT. Two models are particularly important, and we define them now.

A algebraic branching program with unrestricted weights of depth $d$ and width $\leq w$, on the variables $x_{1},\ldots,x_{n}$, is a directed acyclic graph such that

The vertices are partitioned in $d+1$ layers $V_{0},\ldots,V_{d}$, so that $V_{0}=\{s\}$ ($s$ is the source node), and $V_{d}=\{t\}$ ($t$ is the sink node). Further, each edge goes from $V_{i-1}$ to $V_{i}$ for some $0<i\leq d$.

Each $s$-$t$ path is said to compute the polynomial which is the product of the labels of its edges, and the algebraic branching program itself computes the sum over all $s$-$t$ paths of such polynomials.

In an algebraic branching program (ABP), for each edge $e$ the weight $f_{e}(\vec{x})$ is an affine function. The size is $nwd$.

In the definition of ROABPs we will exclusively focus on individual degree, and thus will use the term “degree” (in Section 6 we will use the more usual total degree, for a different class of circuits). The ROABP model is called oblivious because the variable order $x_{1}<\cdots<x_{d}$ is fixed. The model is called read-once because the variables are only accessed on one layer in the graph.

The ABP model is a standard algebraic model that is at least as powerful as algebraic formulas, as shown by Valiant [Val79], and can be simulated by algebraic circuits. As shown by Berkowitz [Ber84], the determinant can be computed by a small ABP over any field. See Shpilka and Yehuydayoff [SY10] for more on this model.

The ROABP model arose in prior work of the authors ([FS12]) as a natural model of algebraic computation capturing several other existing models. This model can also be seen as an algebraic analogue of the boolean model of computation known as the read-once oblivious branching program model, which is a non-uniform analogue of the complexity class $\RL$. See Forbes and Shpilka [FS12] for more of a discussion on the motivation of this class.

Note that a polynomial computed by an ROABP of size $s$ can be computed by an ABP of size $\poly(s)$. The converse is not true, as Nisan [Nis91] gave exponential lower bounds for the size of non-commutative ABPs computing the determinant, and non-commutative ABPs encompass ROABPs, while as mentioned above Berkowitz [Ber84] showed the determinant can be computed by small ABPs. Thus the ROABP model is strictly weaker in computational power than the ABP model.

While there are no efficient (white-box or black-box) PIT algorithms for ABPs, we established in prior work ([FS12]) a quasi-polynomial sized hitting set for ROABPs. This hitting set will be at the heart of our main result.

Our contributions are split into four sections.

We study the model of algebraic computation, traces of matrix powers, shown by Mulmuley to have implications for derandomizing Noether Normalization. In particular, as this model is a restricted class of algebraic circuits, we can ask: how restricted is it? If this model was particularly simple, it would suggest that derandomizing PIT for this class would be a viable approach to derandomizing Noether Normalization. In contrast, if this model of computation is sufficiently general, then given the difficulty of derandomizing PIT for such general models, using Mulmuley’s reduction to unconditionally derandomize Noether Normalization could be a formidable challenge. In this work, we show it is the latter case, proving the following theorem.

The computational models of algebraic branching programs and traces of matrix powers are equivalent, up to polynomial blow up in size.

Derandomizing Noether Normalization via an improved reduction to PIT:

This section contains the main results of our paper. Given the above result, and the lack of progress on derandomizing PIT in such general models such as ABPs, it might seem that derandomizing Noether Normalization for simultaneous conjugation is challenging. However, we show this is not true, by showing that derandomization of black-box PIT for ROABPs suffices for derandomizing Noether Normalization for simultaneous conjugation. By then invoking our prior work on hitting sets for ROABPs cited as Theorem 1.12, we establish the following theorems, giving quasi-affirmative answers to Questions 1.6, 1.8 and 1.9. Furthermore, our results are proved unconditionally and are at least as strong as the conditional results Mulmuley obtains by assuming strong conjectures such as the Generalized Riemann Hypothesis or strong lower bound results.

Specifically, we prove the following theorem which gives an explicit set of separating invariants (see 1.8).

As a consequence of Theorem 1.13 and the discussion in Subsection 1.2 we obtain the following corollary that gives a positive answer to 1.6. In particular, it provides a derandomization of Noether Normalization Lemma for the ring of invariants of simultaneous conjugation.

For deciding intersection of orbit closures, 1.9, the natural extension of Theorem 1.13, as argued in Subsection 1.2, would yield a quasi-polynomial-time algorithm for deciding orbit closure intersection. However, by replacing the black-box PIT results for ROABPs of Forbes and Shpilka [FS12] by the white-box PIT results by Raz and Shpilka [RS05] (as as well as follow-up work by Arvind, Joglekar and Srinivasan [AJS09]), we can obtain the following better algorithm for deciding orbit closure intersection, proving a strong positive answer to 1.9.

As mentioned above, Mulmuley also gets results for Noether Normalization of arbitrary quivers (Mulmuley’s Theorem 4.1) in a generalization of the results on simultaneous conjugation. The main difference is a generalization of the list of generators given in Theorem 1.3 to arbitrary quivers, as given by Le Bruyn and Procesi [LBP90]. Our improved reduction to PIT, involving ROABPs instead of ABPS, also generalizes to this case, so analogous results to the above three theorems are readily attained. However, to avoid discussing the definition of quivers, we do not list the details here.

PIT for Depth-3 Diagonal Circuits:

Here, we give a simpler proof that the depth-3 diagonal circuit model has a quasipolynomial size hitting set. This is done using the techniques of [SV09], and have some similarities with the work of Agrawal, Saha and Saxena [ASS12]. In particular, we show the entire space of derivatives is small, for depth-3 model (but not the depth-4 model). We then show that this implies such polynomials must contain a monomial of logarithmic support, which can be found via brute-force in quasipolynomial time. Unlike the work of Agrawal, Saha and Saxena [ASS12], no shifts are required for this small monomial to exist. Thus, we get the following theorem.

Deciding (non-closed) orbit membership via PIT:

Several interesting cases of this problem were solved: Chistov, Ivanyos and Karpinski [CIK97] gave a deterministic polynomial time algorithm over finite fields and over algebraic number fields; Sergeichuk [Ser00] gaveIn his paper Sergeichuk gives credit for the algorithm to Belitskiĭ [Bel83]. a deterministic algorithm over any field, that runs in polynomial time when supplied with an oracle for finding roots of polynomials.This is not how the result is stated in [Ser00], but this is what one needs to make the algorithm efficient. In fact, to make the algorithm of Sergeichuk run in polynomial space one needs to make another assumption that would allow writing down the eigenvalues of all matrices involved in polynomial space. For example, one such assumption would be that they all belong to the some polynomial degree extension field (Grochow [Gro13]). Chistov-Ivanyos-Karpinski also mentioned that a randomized polynomial-time algorithm for the problem follows from the work of Schwartz and Zippel [Sch80, Zip79]. In conversations with Yekhanin [Yek12], we also discovered this randomized algorithm, showing that this problem is reducible to PIT for ABPs. Because of its close relation to the rest of this work, we include for completeness the proof of the following theorem.

5 Notation

6 Organization

In Section 2 we give the necessary background on ROABPs. We prove our main results about explicit Noether Normalization in Section 3.

The rest of our results appear in the following order. We give the equivalence between the trace of matrix power and ABP models of computation in Section 4. We give the hitting set for depth-3 diagonal circuits in Section 6, using Hasse derivatives as defined in Section 5. In Appendix A we give the reduction from the orbit membership problem to PIT.

Properties of Algebraic Branching Programs

We first derive some simple properties of ABPs, as well as ROABPs, that show their tight connection with matrix products, and traces of matrix products. We begin with the following connection between an ABP with unrestricted weights, and the product of its adjacency matrices. As the lemma is proved in generality, it will apply to ABPs and ROABPs, and we will use it for both.

Further, for an ABP, the matrix $M_{i}$ has entries which are affine forms, and for an ROABP, the matrix $M_{i}$ has entries which are univariate polynomials in $x_{i}$ of degree $<r$.

Expanding the matrix multiplication completely, one sees that it is a sum of the product of the labels of the $s$-$t$ paths such that the $i$-th edge goes from $V_{i-1}$ to $V_{i}$. By the layered structure of the ABP, this is all such paths, so this sum computes $f(\vec{x})$. ∎

The above lemma shows that one can easily convert an ABP or ROABP into a matrix product, where the entries of matrices obey the same restrictions as the weights in the ABP or ROABP. The above lemma gives matrices with varying sizes, and it will be more convenient to have square matrices, which can be done by padding, as shown in the next lemma.

that is, $\prod_{i\in[d]}M_{i}(\vec{x})$ contains a single non-zero entry located at $(0,0)$, which contains the polynomial $f(\vec{x})$. Conversely, any such polynomial $f$ such that

can be computed by a depth $d$, width $w$, ABP with unrestricted weights.

Further, for the specific cases of ABPs and ROABPs, the entries in the $M_{i}$ are restricted: for ABPs the matrix $M_{i}$ has entries which are affine forms, and for an ROABP the matrix $M_{i}$ has entries which are univariate polynomials in $x_{i}$ of degree $<r$.

where we use block-matrix notation. By the properties of block-matrix multiplication, it follows that

as desired. One can observe that the use of 2.1 implies that the $M_{i}$ have the desired restrictions on their entries.

matrices$\implies$ ABP: For $1<i<d$ define $M^{\prime}_{i}:=M_{i}$. Define $M^{\prime}_{1}$ to be the -th row of $M_{1}$, and define $M^{\prime}_{d}$ to be the -th column of $M_{d}$. Then it follows that

and that the $M^{\prime}_{i}$ have at most $w$ rows and columns. Using the $M^{\prime}_{i}$ as the adjacency matrices in an ABP with unrestricted weights, it follows by 2.1 that $f$ is computed by a depth $d$, width $w$ ABP with unrestricted weights. Further, the use of this lemma shows the entry restrictions for ABPs and ROABPs are respected, to the result holds for these models as well. ∎

We next observe that small-size ABPs and ROABPs are respectively closed under addition and multiplication.

$f+f^{\prime}$: Consider the ABPs with unrestricted weights for $f$ and $f^{\prime}$. As they have the same depth, we can align their $d+1$ layers. Consider them together as a new ABP, by merging the two source nodes, and merging the two sink nodes. This is an ABP and has the desired depth, width and degree. Note that it computes $f+f^{\prime}$, as any source-sink path must either go entirely through the ABP for $f$, or entirely though the ABP for $f^{\prime}$, i.e. there are no cross-terms. Thus, the sum over all paths can be decomposed into the paths for $f$ and the paths for $f^{\prime}$, showing that the computation is $f+f^{\prime}$ as desired.

Note that in the ABP case, all edge weights are still affine functions, and in the ROABP case, the edge weights are still univariate polynomials of degree $<r$ for the relevant variables, as we aligned the layers between $f$ and $f^{\prime}$.

$f-f^{\prime}$: This follows by showing that if $f^{\prime}$ is computable by an ABP with unrestricted weights then so is $-f^{\prime}$, all within the same bounds. To see this, observe that by flipping the sign of all edges from $V_{0}$ to $V_{1}$ in the computation for $f^{\prime}$, each source-sink path in the computation for $f^{\prime}$ will have its sign flipped, and thus the entire sum will be negated, computing $-f^{\prime}$ as desired.

Note that the allowed edge weights for ABPs and ROABPs are closed under linear combinations, so the above computation of $-f$ is also valid in these models. ∎

Reducing Noether Normalization to Read-once Oblivious Algebraic Branching Programs

We now prove the main theorems, showing how to construct small sets of explicit separating invariants. We first do this for an arbitrary hitting set, then plug in the hitting set given in our previous work as stated in Theorem 1.12.

$f\in\mathcal{T}_{\mathcal{H}}$ are homogeneous: This is clear by construction.

As done in Mulmuley’s Theorem 3.6, we can conclude that the ring of invariants is integral over the subring generated by the separating invariants. This uses the following theorem of Derksen and Kemper [DK02] (using the ideas of geometric invariant theory [MFK94]), which we only state in our specific case, but does hold more generally.

Combining Theorem 3.8 and Theorem 3.9 yields the following corollary.

Continuing with the dictionary of geometric invariant theory [MFK94], we can obtain the following deterministic black-box algorithm for testing of two orbit closures intersect.

Thus, the above results, Theorem 3.8, 3.10, and 3.11 give positive results to Questions 1.8, 1.6, and 1.9 respectively, assuming small explicit hitting sets for ROABPs. Plugging in the hitting sets results of Forbes and Shpilka [FS12] as cited in Theorem 1.12, we obtain Theorem 1.13 and 1.14.

However, using the hitting set of Theorem 1.12 does not allow us to deduce the efficient algorithm for orbit closure intersection claimed in Theorem 1.15 as the hitting set is too large. To get that result, we observe that deciding the orbit closure intersection problem does not require black-box PIT, and that white-box PIT suffices. Thus, invoking the white-box results of Raz and Shpilka [RS05], and the follow-up work by Arvind, Joglekar and Srinivasan [AJS09], we can get the desired result.

We comment briefly on space-bounded boolean computation, and its relation with this work. As noted in Forbes and Shpilka [FS12], the ROABP model is a natural algebraic analogue of space-bounded boolean computation and the hitting sets given by Forbes and Shpilka [FS12] can be seen as an algebraic analogue of the boolean pseudorandom generator (PRG) given by Nisan [Nis92]. First, we note that by this analogy, and the fact that subsequent work by Nisan [Nis94] showed that the PRG of Nisan [Nis92] can be made polynomial-time with additional space, one expects that the quasi-polynomial-time blackbox identity test (or hitting set) of Forbes and Shpilka [FS12] can be made into a parallel polynomial-time whitebox identity test for ROABPs, which would bring the proof of Theorem 1.15 more in line with the other parts of this paper. However, the $\NC^{3}$ version of the Raz-Shpilka [RS05] algorithm is simpler than any modification of the Forbes-Shpilka [FS12] result, we do not pursue the details here.

By this connection, it follows that one can convert the white-box PIT problem for ROABPs into a derandomization question in small-space computation (once the bit-lengths of the numbers involved are bounded). Thus, one could avoid the algorithms of Raz-Shpilka [RS05] and Arvind, Joglekar and Srinivasan [AJS09], and simply use the algorithm of Nisan [Nis94]. However, this is less clean, and furthermore this booleanization cannot give similar results to Theorem 3.8, since one cannot a priori bound the bit-length of the matrices $\vec{A}$ and $\vec{B}$.

We note here that the above result for testing intersection of orbit closures is stated in the unit-cost arithmetic model for simplicity. At its core, the result uses linear algebra, which can be done efficiently even when the bit-lengths of the numbers are considered. Thus, it seems likely the above algorithm is also efficient with respect to bit-lengths, but we do not pursue the details here.

Equivalence of Trace of Matrix Powers, Determinants and ABPs

In this section we study the class of polynomials computed by small traces of matrix powers, to gain insight into the strength of the derandomization hypotheses that Mumuley requires for his implications regarding Noether Normalization. In particular, we show that a polynomial can be computed as a small trace of matrix power iff it can be computed by a small ABP, as defined in 1.11.

We first show that from the perspective of the hardness of derandomizing PIT, a trace of matrix power can be either defined using linear or affine forms, so that we are not losing generality in our equivalence results below, when using the affine definition. Specifically, we want to relate the complexity of PIT for $\operatorname{trace}(A(\vec{x})^{d})$, for an affine matrix $A(\vec{x})=A_{0}+\sum_{i=1}^{n}A_{i}x_{i}$, to the complexity of PIT of $\operatorname{trace}(A^{\prime}(\vec{x},z)^{d})$, where $A^{\prime}$ is the homogenized version $A^{\prime}(\vec{x},z):=A_{0}z+\sum_{i=1}^{n}A_{i}x_{i}$. Clearly, one can reduce the homogenized linear case back to the affine case, by taking $z=1$, in both the black-box and white-box PIT model. We now consider reducing the affine case to the linear case. Note that this is trivial in the white-box model of PIT, as given the trace of matrix power $\operatorname{trace}(A(\vec{x})^{d})$ we can easily construct the trace of matrix power $\operatorname{trace}(A^{\prime}(\vec{x},z)^{d})$ by replacing constants by the appropriate multiple of $z$. The next lemma shows that these two traces are also polynomially equivalent in the black-box model.

Let $A(x_{1},\ldots,x_{n})=A_{0}+\sum_{i=1}^{n}A_{i}x_{i}$ be matrix of affine forms. Define its homogenization $A^{\prime}(\vec{x},z)=A_{0}z+\sum_{i=1}^{n}A_{i}x_{i}$. Then for any $\vec{\alpha}$ and $\beta$, $\operatorname{trace}(A^{\prime}(\vec{\alpha},\beta)^{d})$ can be computed using $\poly(d)$ queries to $\operatorname{trace}(A(\vec{x})^{d})$.

$\beta\neq 0$: Observe that by homogeneity and linearity of the trace, we have that $\operatorname{trace}(A^{\prime}(\vec{\alpha},\beta)^{d})=\beta^{d}\operatorname{trace}(A(\vec{\alpha}/\beta)^{d})$, where $\vec{\alpha}/\beta$ is the resulting of dividing $\vec{\alpha}$ by $\beta$ coordinate-wise. Thus, only 1 query is needed in this case.

$\beta=0$: Writing $y\vec{x}$ for the coordinate-wise multiplication of $y$ on $\vec{x}$, we can expand the trace of matrix power in the variable $y$, so that $\operatorname{trace}(A(y\vec{x})^{d})=\sum_{j}\operatorname{\mathfrak{C}}_{y^{j}}(\operatorname{trace}(A(y\vec{x})^{d}))$, where $\operatorname{\mathfrak{C}}_{y^{j}}$ extracts the relevant coefficient in $y$, resulting in a polynomial in $\vec{x}$. It follows from polynomial interpolation that in $d+1$ queries to $\operatorname{trace}(A(y\vec{x})^{d})$ we can compute $\operatorname{\mathfrak{C}}_{y^{j}}(\operatorname{trace}(A(y\vec{x})^{d}))$ for any $j$. Observing that $\operatorname{trace}(A^{\prime}(\vec{\alpha},0)^{d})=\operatorname{\mathfrak{C}}_{y^{d}}(\operatorname{trace}(A(y\vec{x})^{d}))$ yields the result. ∎

Thus as $\operatorname{trace}(A^{\prime}(\vec{x},z)^{d})=0$ iff $\operatorname{trace}(A(\vec{x})^{d})=0$, solving black-box PIT for $\operatorname{trace}(A^{\prime}(\vec{x},z)^{d})$ solves it for $\operatorname{trace}(A(\vec{x})^{d})$, and the above lemma gives the needed query-access reduction. Thus, as the linear and affine models are equivalent with respect to PIT, we now only discuss traces of matrix powers in the affine case, and seek to show this model is computationally equivalent (not just with respect to PIT) to the ABP model. We first establish that traces of matrix powers can efficiently simulate ABPs. To do this, we first study matrix powers and how they interact with traces.

Let $x_{0},\ldots,x_{d-1}$ be formally non-commuting variables, and let $R$ be any commutative ring. Define $A(\vec{x})\in R[x_{0},\ldots,x_{d-1}]^{{\llbracket{d}\rrbracket}\times{\llbracket{d}\rrbracket}}$ by

Then $\operatorname{trace}(A(\vec{x})^{d})=\sum_{i\in{\llbracket{d}\rrbracket}}x_{i}x_{i+1}\cdots x_{(i-1\bmod{d})}$.

The matrix $A$ defines an adjacency matrix on a $d$-vertex graph, which is the directed cycle with weights $x_{0},x_{1},\ldots,x_{d-1}$ ordered cyclically. Raising $A$ to the $d$-power corresponds to the adjacency matrix for the length-$d$ walks on the length-$d$ cycle. The only such walks are single traversals of the cycle, starting and ending at some vertex $i$, and these walks have weight $x_{i}x_{i+1}\cdots x_{(i-1\bmod{d})}$. Taking the trace of $A^{d}$ corresponds to summing the weights of these walks, giving the desired formula. ∎

It follows that the only nonzero contribution is when $i_{j}=i_{j-1}+1$ for all $j$, when defining $i_{0}=i_{d}=i$ and working modulo $d$, and that this yields $x_{i}x_{i+1}\cdots x_{(i-1\bmod{d})}$. The claim follows by summing over $i$. ∎

As this result holds even when the variables $x_{i}$ are non-commuting, we can use this lemma over the ring of matrices and thus embed matrix multiplication (over varying matrices) to matrix powering (of a single matrix).

Let $R$ be a commutative ring, and let $M_{1},\ldots,M_{d}\in R^{{\llbracket{n}\rrbracket}\times{\llbracket{n}\rrbracket}}$ be matrices. Define the larger matrix $A\in R^{{\llbracket{nd}\rrbracket}\times{\llbracket{nd}\rrbracket}}$ by treating $A$ as a block matrix in $(R^{{\llbracket{n}\rrbracket}\times{\llbracket{n}\rrbracket}})^{{\llbracket{d}\rrbracket}\times{\llbracket{d}\rrbracket}}$, so that

Then $\operatorname{trace}(A^{d})=d\operatorname{trace}(M_{1}\cdots M_{d})$.

The properties of block-matrix multiplication imply that we can treat the $M_{i}$ as lying in the non-commutative ring of matrices, and thus we apply 4.2 to the trace of $A^{d}$ to see that

where the second equality uses that trace is cyclic. ∎

This lemma shows that the trace of a matrix power can embed the trace of a matrix product (up to the factor $d$), and 2.2 shows that traces of matrix products capture ABPs. This leads to the equivalence of traces of matrix powers and ABPs.

Conversely, if a polynomial $f$ is computable by a width $w$, depth $d$ trace of matrix power, then $f$ can also be computed by a width $w^{2}$, depth $d$ ABP.

trace of matrix power $\implies$ ABP: Suppose $f(\vec{x})=\operatorname{trace}(A(\vec{x})^{d})$, where $A(\vec{x})$ is a ${\llbracket{w}\rrbracket}\times{\llbracket{w}\rrbracket}$ matrix of affine forms. Note then that for each $i$, the $(i,i)$-th entry of $A(\vec{x})^{d}$ is computable by a width $w$, depth $d$ ABP, as established by 2.2, after applying the suitable permutation of indices. As the trace is the summation over $i$ of these functions, we can apply 2.3 to get the result. ∎

Thus the above shows that, up to polynomial factors in size, ABPs and traces of matrix powers compute the same polynomials. We note that there is also an equivalent computational model, defined by the determinant, which we mention for completeness.

Valiant [Val79] (see also [MP08]) showed any small ABP can be simulated by a small projection of a determinant. Conversely, phrased in the language of this paper, Berkowitz [Ber84] gave a small ABP for computing a small projection of a determinant. Thus, the projection of determinant model is also equivalent to the ABP model. We summarize these results in the following theorem.

The computational models of algebraic branching programs, traces of matrix powers, and projections of determinants are equivalent, up to polynomial blow up in size.

In particular, this implies that derandomizing black-box PIT is equally hard for all three of these computational models.

Hasse Derivatives

In this section we define Hasse derivatives, which are a variant of (formal) partial derivatives but work better over finite fields. For completeness, we will derive various properties of Hasse derivatives. We start with the definition.

Let $R$ be a commutative ring, and $R[\vec{x}]$ be the ring of $n$-variate polynomials. For a vector $\vec{u}\in R^{n}$ and $k\geq 0$, define $\partial_{\vec{u}^{k}}(f):R[\vec{x}]\to R[\vec{x}]$, the $k$-th Hasse derivative of $f$ in direction $\vec{u}$, by $\partial_{\vec{u}^{k}}(f)=\operatorname{\mathfrak{C}}_{y^{k}}(f(\vec{x}+\vec{u}y))\in R[\vec{x}]$, where $\vec{x}+\vec{u}y$ is defined as the vector whose $i$-th coordinate in $x_{i}+u_{i}y$.

Note that for $k=1$, this is usual (formal) partial derivative. We now use this definition to establish some basic properties of the Hasse derivative. In particular, the below commutativity property shows that the definition of $\partial_{\vec{x}^{\vec{i}}}$ is not dependent on the order of the variables. Note that while Hasse derivatives are linear operators on $R[\vec{x}]$, they are not linear in the direction $\vec{u}$ of the derivative, and so several of these properties will be stated for more than two terms.

$\partial_{\vec{u}^{k}}(\alpha f+\beta g)=\alpha\partial_{\vec{u}^{k}}(f)+\beta\partial_{\vec{u}^{k}}(g)$

$f(\vec{x}+\vec{u}_{1}y_{1}+\cdots+\vec{u}_{m}y_{m})=\sum_{k_{1},\ldots,k_{m}\geq 0}\partial_{\vec{u}_{m}^{k_{1}}}\cdots\partial_{\vec{u}_{m}^{k_{m}}}(f)y_{1}^{k_{1}}\cdots y_{m}^{k_{m}}$

$\partial_{\vec{u}_{1}^{k_{1}}}\cdots\partial_{\vec{u}_{m}^{k_{m}}}(f)=\operatorname{\mathfrak{C}}_{y_{1}^{k_{1}}\cdots y_{m}^{k_{m}}}(f(\vec{x}+\vec{u}_{1}y_{1}+\cdots+\vec{u}_{m}y_{m}))$

$\partial_{\left(\sum_{j=1}^{m}\alpha_{j}\vec{u}_{j}\right)^{k}}(f)=\sum_{k_{1}+\cdots+k_{m}=k}\left(\prod_{j}\alpha_{j}^{k_{j}}\right)\partial_{\vec{u}_{1}^{k_{1}}}\cdots\partial_{\vec{u}_{m}^{k_{m}}}(f)$

$\partial_{\vec{u}^{k_{1}}}\cdots\partial_{\vec{u}^{k_{m}}}(f)=\binom{k_{1}+\cdots+k_{m}}{k_{1},\ldots,k_{m}}\partial_{\vec{u}^{k_{1}+\cdots+k_{m}}}$

(2): This follows from the linearity of $\operatorname{\mathfrak{C}}_{y^{k}}(\cdot)$, and so

(3): This will be proven by induction on $m$.

$m=1$: This is the definition of the Hasse derivative.

Making the substitution $\vec{x}\leftarrow\vec{x}+\vec{u}_{1}y_{1}$ we obtain

and so by expanding $\partial_{\vec{u}_{2}^{k_{2}}}\cdots\partial_{\vec{u}_{m}^{k_{m}}}(f)$ into its Hasse derivatives, we obtain

and applying the substitution $y_{j}\leftarrow\alpha_{j}y$ we obtain

and thus taking the coefficient of $y^{k}$ yields the result.

We now recover the action of a partial derivative on a monomial.

We can now use the above properties to establish the product rule for Hasse derivatives.

For $f,g\in R[\vec{x}]$, $\vec{u}\in R^{n}$ and $k\geq 0$,

and result follows by taking the coefficient of $y^{k}$. ∎

We now will establish the chain rule for Hasse derivatives. As Hasse derivatives necessarily take multiple derivatives all at once, the chain rule we derive will be more complicated than the usual chain rule for (formal) partial derivatives, which was only for a single partial derivative. This formula, and its variants, are sometimes called Faà di Bruno’s formula. The below formula is written with vector exponents, as explained in Subsection 1.5, and the $\partial$ operators applied to vectors of polynomials are defined coordinate-wise.

For $f\in R[\vec{x}]$ and $g_{1},\ldots,g_{n}\in R[\vec{y}]$,

We now seek to take derivatives “in the direction of $\partial_{\vec{u}^{j}}(\vec{g})(\vec{y})$” from the point $\vec{x}:=\vec{g}(\vec{y})$, treating each $j$ as a different direction and each $z^{j}$ as a different variable. However, this is a subtle operation, as up until now we have taken the directions of our derivatives as independent of the point of derivation. To make this subtlety clear, we now study the above equation, by “undoing” the substitutions $\vec{x}\leftarrow\vec{g}(\vec{y})$, and $z_{j}\leftarrow z^{j}$, and working with derivatives in the ring $R[\vec{y}][\vec{x}]$. We will then later “redo” these substitutions. A simpler form of this logic was used to establish 5.2.6. We start about by applying 5.2.3 to expand out $f$ in the directions $\partial_{\vec{u}^{j}}(\vec{g})(\vec{y})$.

Hitting Sets for Depth-3 Diagonal Circuits

A polynomial $f(x_{1},\ldots,x_{n})$ is computable by a depth-3 diagonal circuit if

The hitting sets will actually be for any polynomial whose space of partial derivatives is low-dimensional. We now define this, using the notion of Hasse derivatives from Section 5 so the results apply over any characteristic.

As Hasse derivatives are linear (5.2) it follows that

and thus taking dimensions finishes the claim. ∎

We now work to proving that depth-3 diagonal circuits have low-dimensional spaces of partial derivatives. We first study the partial derivatives of a single monomial.

Note that this upper bound is an equality over characteristic zero, but not over finite characteristic, as seen by $x^{p}$ in characteristic $p$, where $|\partial(x^{p})|=2$ but $|p|_{\times}=p+1$. However, this slack does not qualitatively affect the results. We now extend this dimension bound by using the chain rule.

By sub-additivity of dimension of Hasse derivatives (6.3) it suffices to prove the claim for $s=1$. Thus consider some $f(\vec{x})=\vec{L}(\vec{x})^{\vec{e}}$. Note that $f(\vec{x})=g(\vec{L}(\vec{x}))$, where $g(\vec{y})=\vec{y}^{\vec{e}}$. The claim then follows from 6.5 and 6.4. ∎

We now seek to show that any polynomial with low-dimensional derivatives must have a small-support monomial. To do so, we introduce the notion of a monomial ordering (see [CLO07] for more on monomial orderings) and establish facts about its interactions with derivatives.

For concreteness, one can consider the lexicographic ordering on monomials, which is easily seen to be a monomial ordering. We now observe that derivatives are monotonic with respect to monomial orderings, except when the characteristic prevents it. That is, over characteristic $p$ we have $x^{p-1}\prec x^{p}$ (in any ordering), but $\partial_{x}(x^{p})=0$, which is not included in the ordering.

By 5.3, the assumptions of $\partial_{\vec{x}^{\vec{k}}}(\vec{x}^{\vec{i}}),\partial_{\vec{x}^{\vec{k}}}(\vec{x}^{\vec{j}})\neq 0$ imply that $\vec{k}\leq\vec{i},\vec{j}$, and that

where $a,b\neq 0$ are constants. As the monomial ordering is total, and is monotonic over multiplication, it follows $\vec{x}^{\vec{i}-\vec{k}}\prec\vec{x}^{\vec{j}-\vec{k}}$, as desired. ∎

Monotonicity then implies that the largest monomial of a polynomial $f$ will continue to be largest when taking derivatives, as long as it is not annihilated. Treating polynomial as vectors, this then gives us a diagonal system of vectors, from which we can deduce the following rank bound.

so that all vectors in $A$ have support contained in $\operatorname{Supp}(\vec{i})$. For a fixed $\vec{j}\in A$, linearity and 5.3 imply that

Just as in 6.4, the characteristic of the underlying field affects the tightness of this result. In particular, in characteristic zero, one can improve this result to $|\vec{i}|_{\times}\leq\log|\partial(f)|$.

The above lemma shows that any $f$ with a small-dimensional space of derivatives must have a small-support monomial. We now give a construction aimed at hitting any polynomial with such small-support monomials. Note that this will beat the union bound, in the sense that a union-bound argument for creating hitting sets against polynomials with small-support monomials will not yield small hitting sets as there are too many such polynomials. However, there is still a small hitting set, as we now construct.

We now establish the desired properties of this construction.

$\mathcal{H}^{\prime}$ is explicit: This is clear from construction.

$|\mathcal{H}^{\prime}|\leq(nd)^{m}$: This is clear from construction.

$f=0\implies f|_{\mathcal{H}^{\prime}}\equiv 0$: This is clear.

By combining Theorem 6.11 with 6.6 we obtain the following hitting set for diagonal circuits.

Acknowledgments

The first author would like to thank Peter Bürgisser for explaining the work of Mulmuley, and the Complexity Theory week at Mathematisches Forschungsinstitut Oberwolfach for facilitating that conversation. He would also like to thank Sergey Yekhanin for the conversation that led to Theorem A.1, and Scott Aaronson for some helpful comments.

The authors are grateful to Josh Grochow [Gro13] for bringing the works of Chistov-Ivanyos-Karpinski [CIK97], Sergeichuk [Ser00] and Belitskiĭ [Bel83] to their attention, and for explaining these works to them.

References

Appendix A Orbit Intersection Reduces to PIT

In this section, we study the (non-closed) orbit intersection problem, as compared with the orbit closure intersection problem studied in Section 3. Unlike with orbit closures, the orbits with non-empty intersections must be equal, because the group action is invertible. Thus, the orbit intersection problem is equivalent to the orbit membership problem. As mentioned before, Chistov, Ivanyos, and Karpinski [CIK97] observed a randomized algorithm for the orbit membership problem, based on the Schwartz-Zippel lemma [Sch80, Zip79]. In conversations with Yekhanin [Yek12], we also discovered this result, which we include for completeness, given its closeness to the other questions studied in this work.