A set V ⊆ F n is called an affine variety if it is the common zero set of a set of polynomials in F[x 1 , . . . , x n ]. Let V ⊆ F n be an affine variety and let I(V ) denote its ideal, i.e., the set of polynomials vanishing on V . 1 A non-zero polynomial P ∈ I(V ) is called an equation for V . An equation for V may serve as a "proof" that a point x ∈ F n is not in V , by showing that P (x) 0.
A fundamental idea that dates back to Strassen [23] is that many important circuit lower bounds problems in algebraic complexity theory fit naturally into the setting of showing that a point x lies outside a variety V . It was vastly extended in the Geometric Complexity Theory program [17], and was recently central to the algebraic natural proofs paradigm [5,7,8,10]. In this formulation, one considers V to be the closure of a class of polynomials of low complexity, and x is the coefficient vector of the candidate hard polynomial.
Let Δ(V ) := min 0 P ∈I(V ) {deg(P )}. The quantity Δ(V ) can be thought of as a measure of complexity for the geometry of the variety V . The quantity Δ(V ) is a very coarse complexity measure. The recent line of work regarding algebraic natural proofs [8,10] suggests to study the arithmetic circuit complexity of equations for varieties V that correspond to polynomials with small circuit complexity. Having Δ(V ) growing like a polynomial in n is a necessary (but not a sufficient) condition for a variety V to have an algebraic natural proof for non-containment if one insists that the "proof" (that is, the equation P) belongs to the class VP.
The usefulness of equations was also noticed by Raz [18] in his elusive functions approach for proving circuit lower bounds. Briefly, one component of Raz's method is the observation that it is possible to consider not only a single point x describing the coefficient vector of a single polynomial, but also a larger set of polynomials that is the image of an explicit polynomial map f (y) in a small number of variables. The image of f is thought of as a family of polynomials indexed by the variables y, or as a polynomial in the original set of variables and additional auxiliary variables y (but, since their number is so small, this has little effect on the total circuit complexity). If V is a variety and P is an equation for P, then if P ( f (y)) is a non-zero polynomial in y, the map f is called "elusive" and its image contains a point that is not in V , which implies a circuit lower bound for the explicit polynomial (in the original set of variables and additional auxiliary variables y) described by f .
A matrix M is (r , s)-rigid if M cannot be written as a sum R +S where rank(R) ≤ r and S contains at most s non-zero entries. Valiant [24] proved that if A is (εn, n 1+δ )-rigid for some constants ε, δ > 0, then A cannot be computed by arithmetic circuits of size O (n) and depth O (log n), and posed the problem of explicitly constructing rigid matrices with these parameters, which is still open. It is easy to prove that most matrices have much stronger rigidity parameters: Over algebraically closed fields a generic matrix is (r , (nr ) 2 )-rigid for any target rank r .
Let F be an algebraically closed field. Let A r,s ⊆ F n×n denote the set of matrices that are not (r , s)-rigid. Let V r,s = A r,s denote the Zariski closure of A r,s . A geometric study of V r,s was initiated by Kumar, Lokam, Patankar, and Sarma [12]. Among other results, they prove that for every s < (nr ) 2 , Δ(V r,s ) ≤ n 4n 2 . A slightly improved (but still exponential) upper bound was obtained by Gesmundo, Hauenstein, Ikenmeyer, and Landsberg [9], who also conjectured that for some ε, δ > 0, Δ(V εn,n 1+δ ) grows like a polynomial function in n. The following theorem, which we prove in this article, confirms this conjecture:
A Polynomial Degree Bound on Equations 6:3 Theorem 1.1. Let ε < 1/25, and let F be a field of size at least n 2 . For every large enough n, there exists a non-zero polynomial Q ∈ F[x 1,1 , . . . , x n,n ], of degree at most n 3 , which is a non-trivial equation for matrices that are not (εn, εn 2 )-rigid. That is, for every such matrix M, Q (M ) = 0.
In fact, the conjecture of Reference [9] was slightly weaker: They conjectured that Δ(U ) is polynomial in n for every irreducible component U of V εn,n 1+δ . As shown by Reference [12], the irreducible components are in one-to-one correspondence with subsets of [n] × [n] of size n 1+δ corresponding to possible supports of the sparse matrix S.
As we observe in Remark 3.3, it is somewhat simpler to show that each of these irreducible components has an equation with a polynomial degree bound. However, since the number of such irreducible components is exponentially large, it is not clear if there is a single equation for the whole variety that is of polynomially bounded degree. We do manage to reverse the order of quantifiers and prove such an upper bound in Theorem 1.1. This suggests that the set of non-rigid matrices is much less complex than what one may suspect given the results of References [9,12].
The original motivation for defining rigidity was in the context of proving lower bounds for algebraic circuits [24]. If A ∈ F n×n is an (εn, n 1+δ )-rigid matrix, for any ε, δ > 0, then the linear transformation represented by A cannot be computed by an algebraic circuit of depth O (log n) and size O (n).
Every algebraic circuit computing a linear transformation is without loss of generality a linear circuit. A linear circuit is a directed acyclic graph that has n inputs labeled X 1 , . . . , X n and n output nodes. Each edge is labeled by a scalar α ∈ F. Each node computes a linear function in X 1 , . . . , X n defined inductively. An internal node u with children, v 1 , . . . ,v k , connected to it by edges labeled α 1 , . . . , α k , computes the linear function v = i α i v i , where v i is the linear function computed by v i , 1 ≤ i ≤ k. The size of the circuit is the number of edges in the circuit.
It is possible to use similar techniques to those used in the proof of Theorem 1.1 to prove a polynomial upper bound on an equation for a variety containing all matrices A ∈ F n×n whose corresponding linear transformation can be computed by an algebraic circuit of size at most n 2 /200 (even without restriction on the depth). Note that this is nearly optimal as any such linear transformation can be computed by a circuit of size n 2 . More formally, we show the following: Theorem 1.2. Let F be a field of size at least n 2 . For every large enough n, there exists a non-zero polynomial Q ∈ F[x 1,1 , . . . , x n,n ], of degree at most n 3 , which is a non-trivial equation for matrices that are computed by algebraic circuit of size at most n 2 /200.
Let PIT denote the set of strings that describe arithmetic circuits (say, over C) that compute the zero polynomial. It is well known that PIT ∈ coRP. Kabanets and Impagliazzo [11] proved that certain circuit lower bounds follow from the assumption that PIT ∈ P. As a corollary to Theorem 1.2, we are able to prove theorem of a similar kind. Corollary 1.3. Suppose PIT ∈ P. Then at least one of the following is true:
(1) There exists a family of n-variate polynomials of degree poly(n) over C, which can be computed (as its list of coefficients, given the input 1 n ) in PSPACE, which does not have polynomial size constant free arithmetic circuits. (2) there exists a family of matrices, constructible in polynomial time with an NP oracle (given the input 1 n ), which requires linear circuits of size Ω(n 2 ).
A constant free arithmetic circuit is an arithmetic circuit that is only allowed to use the constants {0, ±1}.
A different way to interpret Corollary 1.3 is by saying that at least one of the following three lower bound results hold: Either PIT P, or (at least) one of the two circuit lower bounds stated in the corollary. We emphasize that the result holds under any derandomization of PIT, that is, even under white box derandomization of PIT, which is a weaker assumption then black-box derandomization of PIT.
Our statement is similar to, but incomparable with the result of Kabanets and Impagliazzo [11], who proved that if PIT ∈ P, then either the permanent does not have polynomial size constant free arithmetic circuits, or NEXP P/poly.
Since (εn, εn 2 )-rigid matrices have linear circuit of size 3εn 2 , the last item of Corollary 1.3 in particular implies a conditional construction of (Ω(n), Ω(n 2 ))-rigid matrices (it is also possible to directly use Theorem 1.1 instead of Theorem 1.2 to deduce this result). Unconditional constructions of rigid matrices in polynomial time with an NP oracle were recently given in References [2,3]. However, the rigidity parameters in these papers are not strong enough to imply circuit lower bounds (furthermore, even optimal rigidity parameters do not imply Ω(n 2 ) lower bounds for general linear circuits).
Since it is widely believed that PIT ∈ P, the answer to which of the last two items of Corollary 1.3 holds boils down to the question of whether there exists an equation for non-rigid matrices of degree poly(n) and circuit size poly(n). If determining if a matrix is rigid is coNP-hard (as is known for some restricted ranges of parameters [15]), then it is tempting to also believe that the equations should not be easily computable, as they provide "proof" for rigidity that can be verified in randomized polynomial time. However, it could still be the case that those equations that have polynomial size circuits only prove the rigidity of "easy" instances; and it could also be the case that the number of equations defining the set of non-rigid matrices is very large, so even if each one of them was easily computable, one still would not get an efficient algorithm for deciding rigidity.
As another application of our our techniques used in the proofs of Theorems 1.1 and 1.2, we can also prove the following upper bound on the degree of equations for low rank tensors: Theorem 1.4. For every field F and for all n, d ∈ N, there exists a non-zero polynomial Q on n d variables and degree at most n 2d , which is a non-trivial equation for d-dimensional tensors τ :
Raz [19] proved that when d is a super-constant but slowly growing function of n (e.g., d = O (log n/ log log n)), strong enough lower bounds for tensor rank would imply super-polynomial lower bounds for general arithmetic formulas. While Theorem 1.4 holds for such super-constant values of d (and a rank lower bound of n d -1 /100d would suffice for Raz's approach), the equations we get for such values of d are of slightly super-polynomial degree.
Our proof of Theorems 1.1 and 1.2 are short, elementary, and based on a two-step argument.
In the first step, we show that there is a polynomial map of low degree and on a small number of variables such that any non-rigid matrix (respectively, a matrix with a small algebraic circuit) lies in its image. The parameters of the polynomial map, e.g., its degree and arity depend on the upper bound on the rigidity of the matrices we are working with (and the size of the algebraic circuit for Theorem 1.2). Once we have such a map, an immediate observation is that any non-trivial annihilating polynomial of this polynomial map gives us an equation satisfied by everything in the image of the maps. To complete our proof, we use the bounds on the degree and arity of these maps to show that they do indeed have low-degree annihilating polynomials. This second step is a very simple linear algebraic argument based on dimension counting. For our construction of the polynomial map, we rely on an application of a polynomial map due to Shpilka and Volkovich [21]. Shpilka and Volkovich constructed this map in the context of designing deterministic algorithms for polynomial identity testing for various subclasses of algebraic circuits.
This technique shares some similarities with Raz's elusive function approach for circuit lower bounds [18]. In both cases, the main underlying observation is that the set of low complexity objects is contained in an image of a low-degree polynomial map in a small number of variables.
One downside of the fact that our proofs are based on dimension counting arguments is that they are non-constructive and do not give explicit equations for the relevant varieties. It thus remains a very interesting open problem to provide explicit low-degree equations for any of the varieties considered in this article. Here, "explicit" means a polynomial that has arithmetic circuits of size poly(n), although one can be even more permissive and ask for polynomials in the class VNP.
The question of whether such equations exists has a win-win flavor: If they do, then this can aid in explicit constructions of rigid matrices; if, however, all equations are hard, then we have identified a family of polynomials that requires super-polynomial arithmetic circuits. Assuming the existence of a polynomial time algorithm for polynomial identity testing, we are able to make this connection formal to prove Corollary 1.3.
For completeness, in this section, we define some basic notions in algebraic geometry. A reader who is familiar with this topic may skip to the next section.
Let F be an algebraically closed field. A set V ⊆ F n is called an affine variety if there exist polynomials f 1 , . . . ,
For convenience, in this article, we often refer to affine varieties simply as varieties.
For each variety V there is a corresponding ideal I(V ) ⊆ F[x 1 , . . . , x n ] that is defined as
Conversely, for an ideal I ⊆ F[x 1 , . . . , x n ], we may define the variety
Given a set A ⊆ F n , we may similarly define the ideal I(A). The (Zariski) closure of a set A, denoted A, is the set V(I(A)). In words, the closure of A is the set of common zeros of all the polynomials that vanish on A. It is also the smallest variety with respect to inclusion that contains A. By construction, A is a variety, and a polynomial that vanishes everywhere on A is also vanishes on A.
Over C, it is instructive to think of the Zariski closure of A as the usual Euclidean closure. In fact, for the various sets A we consider in this article (which correspond to sets of "low complexity" objects, e.g., non-rigid matrices or matrices that can be computed with a small circuit), it can be shown that these two notions of closure coincide (see, e.g., Section 4.2 of Reference [4]).
A variety V is called irreducible if it cannot be written as a union V = V 1 ∪V 2 of varieties V 1 , V 2 that are properly contained in V . Every variety can be uniquely written as a union
A key ingredient in our proofs is the following elementary lemma, which shows that images of low-degree polynomial maps in a small number of variables have a low-degree annihilator: Lemma 2.1. Let F be a field and let P :
Then there's a non-zero polynomial Q ∈ F[y 1 , . . . ,y N ] of degree at most Δ such that for any α in the image of P, Q (α ) = 0.
Proof. Let V 1 denote the subspace of polynomials over F in N variables of degree at most Δ. Let V 2 denote the subspace of polynomials over F in K variables of degree at most DΔ. Consider the linear transformation T : V 1 → V 2 given by Q → Q •P, where Q •P denotes the composition of the polynomial Q with the map P, i.e., (Q
We have that dim
by assumption. This implies that T has a non-trivial kernel, that is, there exists 0
Suppose α is in the image of P. That this, there exists β ∈ F K such that P (β ) = α. Then
In this section, we prove Theorem 1.1. A key component of the proof is the use of the following construction, due to Shpilka and Volkovich, which provides an explicit low-degree polynomial map on a small number of variables, which contains all sparse matrices in its image. For completeness, we provide the construction and prove its basic property.
). Let F be a field such that |F| > n. Then for all k ∈ N, there exists an explicit polynomial map SV n,k (x, y) : F 2k → F n of degree at most n such that for any subsetT = {i 1 , . . . , i k } ⊆ [n] of size k, there exists a setting y = α such that SV(x, α ) is identically zero on every coordinate j T , and equals x j in coordinate i j for all j ∈ [k].
Proof. Arbitrarily pick distinct α 1 , . . . α n ∈ F, and let u 1 , . . . ,u n be their corresponding Lagrange's interpolation polynomials, i.e., polynomials of degree at most n -1 such that u i (α j ) = 1 if j = i and 0 otherwise (more explicitly, u i (z) = j i (z-α j ) j i (α i -α j ) ). Let P i (x 1 , . . . , x k , y 1 , . . . ,y k ) = k j=1 u i (y j ) • x j , and finally let SV n,k (x, y) = (P 1 (x, y), . . . , P n (x, y)).
It readily follows that givenT = {i 1 , . . . , i k } as in the statement of the lemma, we can set y j = α i j for j ∈ [k] to derive the desired conclusion. The upper bound on the degree follows by inspection.
As a step toward the proof of Theorem 1.1, we show there is a polynomial map on much fewer than n 2 variables with degree polynomially bounded in n such that its image contains every nonrigid matrix. In the next step, we show that the image of every such polynomial map has an equation of degree poly(n). Lemma 3.2. For every r ≤ n and s ≤ n 2 , there exists an explicit polynomial map P : F 2r n+2s → F n×n , of degree at most n 2 , such that every matrix M that is not (r , s) rigid lies in its image.
Proof. Let u, v be disjoint sets of rn variables each, and x, y be disjoint sets of s variables each. Let U be a symbolic n × r matrix whose entries are labeled by the variables u, and similarly let V be a symbolic r × n matrix labeled by v. Let UV(u, v) : F 2r n → F n×n be the degree 2 polynomial map defined by the matrix multiplication UV .
A Polynomial Degree Bound on Equations 6:7
Finally, let P : F 2r n+2s → F n×n be defined as
where SV n 2 ,s is as defined in Lemma 3.1.
Suppose now M is a not an (r , s) rigid matrix, i.e., M = R + S for R of rank at most r and S that is s-sparse. Decompose R = U 0 V 0 for n × r matrix U 0 and r × n matrix V 0 . Let T denote the support of S. For convenience, we may assume |T | = s (otherwise, pad with zeros arbitrarily). Let α ∈ F s denote the setting for y in SV n 2 ,s that maps x 1 , . . . , x s to T , and let β = (β 1 , . . . , β s ) denote the non-zero entries of S. Then
To complete the proof of Theorem 1.1, we need to show that for the relevant range of parameters it is possible to combine Lemma 3.2 with Lemma 2.1.
Proof of Theorem 1.1. We apply Lemma 2.1 with the map P from Lemma 3.2 for r = εn and s = εn 2 so 2rn + 2s = 4εn 2 .
It remains to be shown that the assumption of Lemma 2.1 indeed holds if we pick Δ = n 3 . Indeed, note that N = n 2 , D = n 2 and K = 4εn 2 , so n 2 +n 3 n 2 ≥ n n 2 whereas 4εn 2 +n 5 4εn 2 ≤ (2n 5 ) 4εn 2 , and thus by the choice of ε, this is smaller than n n 2 for every large enough n.
As the map P from Lemma 3.2 contains in its image all matrices that are not (εn, εn 2 )-rigid, the statement follows: Remark 3.3. If the support of the sparse matrix is fixed a priori to some set S ⊆ [n] × [n] of cardinality at most ϵn 2 , then it is easier to come up with a universal map P : F 3ϵn 2 → F n×n such that every matrix M whose rank can be reduced to at most ϵn by changing entries in the set S is contained in the image of P. Just consider P (w, x, y) = UV(u, v) +W , whereW is a matrix such that for all (i, j) ∈ [n] × [n], if (i, j) ∈ S, thenW (i, j) = w i, j and W (i, j) is zero otherwise. Here, each w i, j is a distinct formal variable. Combined with the dimension comparison argument of Lemma 2.1, it can be seen that there is a non-zero low-degree polynomial Q such that Q • P ≡ 0. This argument provides a (different) equation of polynomial degree for each irreducible component of the variety of non-rigid matrices. Note that the degree of P is 2 (rather than n 2 as in the construction of P in Lemma 3.2) but other methods are currently unable to leverage that to obtain a meaningful improvement in the parameters. Remark 3.4. It is possible to use the equation given in Theorem 1.1, and using the methods of Reference [12], to construct "semi-explicit" (εn, εn 2 )-rigid matrices. These are matrices whose entries are algebraic numbers (over Q) with short description, which are non-explicit from the computational complexity point of view. However, such constructions are also known using different methods (see Section 2.4 of Reference [14]).
In this section, we prove Theorem 1.2. Our strategy, as before, is to observe that all matrices with a small circuit lie in the image of a polynomial map P on a small number of variables and small degree. Circuits of size s can have many different topologies and thus, we first construct a "universal" linear circuit, of size s ≤ s 4 , that contains as subcircuits all linear circuits of size s. Importantly, s will affect the degree of P but not its number of variables. We note that constructions of such universal maps whose image contain all polynomials with small circuits have appeared before in the literature. In the context of circuits computing univariate polynomials, similar maps were constructed by Strassen [23] and Lipton [13], who used those maps to prove the existence of certain such polynomials that are hard to compute. Our approach is much more reminiscent of that of Raz [18], who constructed universal maps for circuits computing multivariate polynomials. Raz's approach first constructs a universal circuit graph, which is a graph of size poly(s) that contains a subgraph every circuit of size s. The universal circuit graph is then used to construct the universal map by associating a variable with every edge of the universal graph. This poly(s) size blow up, which translates to a polynomial map with poly(s) variables, is fine when one considers multivariate polynomials of large degree and wishes to find polynomials with exponential circuit complexity. In our context, however, this increase in the number of variables is unacceptable, since every n × n matrix defines a linear transformation that can be computed by circuits of size at most O (n 2 ), and we wish to separate between those who can be computed by linear size circuits and those who require super-linear size. Thus, a naive use of ideas in Reference [18] is insufficient, and we compose the universal circuit construction with the Shpilka-Volkovich map to get around this difficulty.
We now define a map U (x, y) that is "universal" for size s linear circuits, i.e., it contains in its image all n ×n matrices A whose corresponding linear transformation can be computed by a linear circuit of size at most s.
Let s ≥ n. We first define a universal graph G for size s. G has a set V 0 of n input nodes labeled X 1 , . . . X n and a set V s+1 of n designated output nodes. In addition, G is composed of s disjoint sets of vertices V 1 , . . . ,V s , each contains s vertices.
Each vertex v ∈ V i , for 0 ≤ i ≤ s + 1, has as its children all vertices u ∈ V j for all 0 ≤ j < i. It is clear than every directed acyclic graph with s edges (and hence at most s vertices, and depth at most s) can be (perhaps non-uniquely) embedded in G as a subgraph.
We now describe the edge labeling. Let s ≤ s 4 be the number of edges in G and let e i denote the ith edge, 1 ≤ i ≤ s . The edge e i is labeled by the ith coordinate of the map SV s ,s (x, y) given in Lemma 3.1.
Thus, the graph G with this labeling computes a linear transformation (over the field F(x, y)) in the variables X 1 , . . . , X n . More explicitly, the (i, j)th entry of the matrix U (x, y) representing this linear transformation is given by the sum, over all paths from X i to the jth output node, of the product of the edge labels on that path. This entry is a polynomial in x, y, so we can think of U as a polynomial map from F 2s to F n 2 . Lemma 4.1. The map U (x, y) : F 2s → F n 2 defined above contains in its image all n × n matrices A whose corresponding linear transformation can be computed by a linear circuit of size at most s. The degree of U is at most s • (s + 1).
Proof. Let A be a matrix whose linear transformation is computed by a size s circuit C. The graph of C can be embedded as a subgraph in the graph G constructed above (if the embedding is not unique, pick one arbitrarily). Let e i 1 , . . . , e i s be the edges of this subgraph, and let β = (β 1 , . . . , β s ) be their corresponding labels in C. By the properties of the map SV s ,s (x, y) given in Lemma 3.1, it is possible to set the tuple of variables y to field elements α 1 , . . . , α s such that the jth coordinate of SV(β, α ) equals β i if j = i k for some 1 ≤ k ≤ s the 0 otherwise. Observe that under this labeling of the edges, the circuit G computes the same transformation as the circuit C. Hence, U (β, α ) = A.
To upper bound the degree of U , note that each edge label in G is a polynomial of degree s , and each path is of length at most s + 1.
A Polynomial Degree Bound on Equations 6:9
In a similar manner to the proof of Theorem 1.1, we now combine Lemma 2.1 with the map U (x, y) to show that its image has a equation of degree at most n 3 . This would complete the proof of Theorem 1.2.
Proof of Theorem 1.2. Let U : F 2s → F n 2 be the map given by Lemma 4.1 for s = n 2 /200 so s ≤ n 8 , and the degree of U is at most s (s + 1) ≤ n 10 .
We apply Lemma 2.1 with the map U (x, y) so now N = n 2 , D ≤ n 10 and K = 2s. Setting Δ = n 3 , we once again get that n 3 +n 2 n 2 ≥ n n 2 , whereas n 2 /100+n 13 n 2 /100 ≤ (2n 13 ) n 2 /100 < n n 2 for every large enough n, so we can get a non-zero polynomial Q of degree at most n 3 such that Q (A) = 0 for every matrix in the image of U . By Lemma 4.1, if A has a circuit of size n 2 /200, then it is in the image of U .
In this section, we prove Theorem 1.4. We start by quickly recalling the definitions of a tensors and that of tensor rank.
For tensors considered in this article, n 1 , . . . , n d are all equal and denoted by the parameter n. Thus, such tensors simply functions from [n] d to F. Tensors are alternatively defined in terms of multilinear maps and in algebraic complexity, often as set-multilinear polynomials. For the discussion in this article, we work with Definition 5.1 and refer to the survey by Saptharishi [20] for further discussions on these alternative definitions and their equivalence. We now define the notion of a rank one tensor and use it to define tensor rank, which is the main property of interest in this section. Definition 5.2. Let d, n ∈ N, F be a field and τ : [n] d → F be a tensor. Then, τ is said to be of rank one if there exist vectors u 1 , u 2 , . . . , u d ∈ F n such that for every (i
where, (u j ) i j denotes the i j th coordinate of u i ∈ F n .
In other words, τ is a rank one tensor if there exist vectors u 1 , u 2 , . . . , u d ∈ F n such that τ is an outer product of u 1 , u 2 , . . . , u d , i.e.,
We are now ready to define the rank of a tensor. Definition 5.3. Let d, n ∈ N, F be a field and τ : [n] d → F be a tensor. Then, the rank of τ is the smallest r ∈ N such that τ can be written as a sum of r rank one tensors.
A fairly standard dimension-based argument shows for all n, d ∈ N and every field F, there exist tensors τ : [n] d → F of rank at least n d -1 /d. However, constructing an explicit family of tensors of such high rank (or in fact even rank n d (1/2+ϵ ) for any ϵ > 0) continues to be a challenging open problem. In addition to being a clean and natural question on its own, one of the reasons of interest in this question of tensor rank lower bounds is its connection to arithmetic circuit lower bounds. For instance, it is known that a three-dimensional tensor of rank at least r implies a lower bound of Ω(r ) on an arithmetic circuit computing the bi-linear function associated with the tensor. As mentioned earlier, Raz [19] proved that strong enough lower bounds for d-dimensional tensors (for deterministically a matrix on which the equation evaluates to non-zero, which implies the matrix requires large linear circuits.
There are some technical difficulties involved with this plan that we now describe. The first problem is that even arithmetic circuits of small size can have large description as bit strings, due to the field constants appearing in the circuits. To prevent this issue, we only consider constant free arithmetic circuits, which are only allowed inputs labeled by {0, ±1} (but can still compute other constants in the circuit using arithmetic operations).
The second problem is that, to be able to find a non-zero of the equation in the last step of the algorithm (using the mere assumption that PIT ∈ P), we need not only the size of the circuit but also its degree to be bounded by poly(n). Of course, by Theorem 1.2, there exists such a circuit, but we need to be able to prevent a malicious prover from providing us with a poly(n) size circuit of exponential degree, and it is not known how to compute the degree of a circuit in deterministic polynomial time, even assuming PIT ∈ P. To solve this issue, we use an idea of Malod and Portier ([16], Theorem 1), who showed that any polynomial with circuit of size poly(n) and degree d also has a multiplicatively disjoint (MD) circuit of size poly(n, d ). An MD circuit is a circuit in which every multiplication gate multiplies two disjoint subcircuits. This is a syntactic notion that is easy to verify efficiently and deterministically, and an MD circuit of size s is guaranteed to compute a polynomial of degree at most s.
A final technical issue is that the notion of MD circuits does not fit perfectly within the framework of constant free circuits. Therefore, we use the notion of "almost MD" circuits, where the inputs to a multiplication gates are not disjoint, but at least one of these inputs is the root of a subcircuit in which only constants appear. Definition 6.1. We say a gate v in a circuit is constant producing (CP) if in the subcircuit rooted at v, all input nodes are field constants.
An almost-MD circuit is a circuit where every multiplication gate either multiplies two disjoint subcircuits, or at least one of its children is constant producing. Lemma 6.2. Suppose f is an n-variate polynomial of degree poly(n) that has a constant free arithmetic circuit of degree poly(n). Then f has a constant free almost-MD circuit of size poly(n).
Proof. Let C 0 be a constant free arithmetic circuit for f . We first homogenize the circuit C 0 to obtain a circuit C 1 (a homogeneous circuit is a circuit in which every gate computes a homogeneous polynomial; see, e.g., Reference [22]). Since C 1 is homogeneous, all the gates that compute non-zero field constants are CP gates. We then eliminate all gates that compute constants by allowing the edges entering sum gates to be labeled by field scalars and interpreting a sum gate as computing a linear combination whose coefficients are given by the edge labels. We call this circuit C 2 . Note that we are now in a more general model in which the edges of the circuit are allowed to be labeled by field constants, and this step does not maintain constant-freeness. However, the new circuit still computes the same polynomial, and every label appearing on the edges of C 2 was computed in C 1 , so it can be computed by a constant-free arithmetic circuit of polynomial size.
We now do the transformation detailed in Lemma 2 of Reference [16] to C 2 to obtain an MD circuit C 3 , which has labels on the edges (we emphasize that Lemma 2 of Reference [16] indeed applies for this more general model of circuits with labels on the edges). This step does not produce new constants. Finally, we convert C 3 to an almost-MD constant free circuit C 4 by re-computing every label appearing on the edge using a fresh subcircuit for each label and rewiring the circuit. accordingly (this step will convert the circuit from an MD circuit to an almost MD circuit). These subcircuits are guaranteed to have polynomial size constant free circuits, since these constant were all computed in C 0 , which keeps the total size poly(n).
(2) There is an efficient construction with an NP oracle of a three-dimensional tensor of rank Ω(n 2 ).
We remark that for tensors of large rank there are no analogs of References [2,3], i.e., there do not exist even constructions with an NP oracle of tensors with slightly super-linear rank.
For completeness, we provide the formal (standard) definitions for these notions in Section
2.1.
ACM Transactions on Computation Theory, Vol. 14, No. 2, Article 6. Publication date: September 2022.