A Polynomial Degree Bound on Equations for Non-rigid Matrices and Small Linear Circuits

Let $V\subseteq\mathbb{F}^{n}$ be a (not necessarily irreducible) affine variety and let $\mathbf{I}(V)$ denote its ideal.¹¹1For completeness, we provide the formal (standard) definitions for these notions in Section 1.4.. A non-zero polynomial $P\in\mathbf{I}(V)$ is called an equation for $V$. An equation for $V$ may serve as a “proof” that a point $\mathbf{x}\in\mathbb{F}^{n}$ is not in $V$, by showing that $P(\mathbf{x})\neq 0$.

A fundamental observation of the Geometric Complexity Theory program is that many important circuit lower bounds problems in algebraic complexity theory fit naturally into the setting of showing that a point $\mathbf{x}$ lies outside a variety $V$ [MS01, BIL⁺19]. In this formulation, one considers $V$ to be the closure of a class of polynomials of low complexity, and $\mathbf{x}$ is the coefficient vector of the candidate hard polynomial.

Let $\Delta(V):=\min_{0\neq P\in\mathbf{I}(V)}\{\deg(P)\}$. The quantity $\Delta(V)$ can be thought of as a measure of complexity for the geometry of the variety $V$. The quantity $\Delta(V)$ is a very coarse complexity measure. A recent line of work regarding algebraic natural proofs [FSV18, GKSS17] suggests to study the arithmetic circuit complexity of equations for varieties $V$ that correspond to polynomials with small circuit complexity. Having $\Delta(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.

A matrix $M$ is $(r,s)$-rigid if $M$ cannot be written as a sum $R+S$ where $\mathsf{rank}(R)\leq r$ and $S$ contains at most $s$ non-zero entries. Valiant [Val77] proved that if $A$ is $(\varepsilon n,n^{1+\delta})$-rigid for some constants $\varepsilon,\delta>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,(n-r)^{2})$-rigid for any target rank $r$.

Let $\mathbb{F}$ be an algebraically closed field. Let $A_{r,s}\subseteq\mathbb{F}^{n\times n}$ denote the set of matrices which are not $(r,s)$-rigid. Let $V_{r,s}=\overline{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 [KLPS14]. Among other results, they prove that for every $s<(n-r)^{2}$, $\Delta(V_{r,s})\leq n^{4n^{2}}$. A slightly improved (but still exponential) upper bound was obtained by Gesmundo, Hauenstein, Ikenmeyer and Landsberg [GHIL16], who also conjectured that for some $\varepsilon,\delta>0$, $\Delta(V_{\varepsilon n,n^{1+\delta}})$ grows like a polynomial function in $n$. The following theorem which we prove in this note confirms this conjecture.

In fact, the conjecture of [GHIL16] was slightly weaker: they conjectured that $\Delta(U)$ is polynomial in $n$ for every irreducible component $U$ of $V_{\varepsilon n,n^{1+\delta}}$. As shown by [KLPS14], the irreducible components are in one-to-one correspondence with subsets of $[n]\times[n]$ of size $n^{1+\delta}$ corresponding to possible supports of the sparse matrix $S$.

As we observe in 2.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 which 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 [KLPS14, GHIL16].

The original motivation for defining rigidity was in the context of proving lower bounds for algebraic circuits [Val77]. If $A\in\mathbb{F}^{n\times n}$ is an $(\varepsilon n,n^{1+\delta})$-rigid matrix, for any $\varepsilon,\delta>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},\ldots,X_{n}$ and $n$ output nodes. Each edge is labeled by a scalar $\alpha\in\mathbb{F}$. Each node computes a linear function in $X_{1},\ldots,X_{n}$ defined inductively. An internal node $u$ with children, $v_{1},\ldots,v_{k}$, connected to it by edges labeled $\alpha_{1},\ldots,\alpha_{k}$, computes the linear function $\sum_{i}\alpha_{i}\ell_{v_{i}}$, where $\ell_{v_{i}}$ is the linear function computed by $v_{i}$, $1\leq i\leq 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 in order to prove a polynomial upper bound on an equation for a variety containing all matrices $A\in\mathbb{F}^{n\times 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.

Our proofs are based on a dimension counting arguments, and are therefore 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 paper. Here “explicit” means a polynomial which has arithmetic circuits of size $\poly(n)$.²²2Although one may consider other, informal notions of explicitness which could nevertheless be helpful. The question of whether such equations exists has a win-win flavor: if they do, this can aid in explicit constructions of rigid matrices, and on the other hand, if all equations are hard, we have identified a family of polynomials which 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.

Let $\mathsf{PIT}$ denote the set of strings which describe arithmetic circuits (say, over $\mathbb{C}$) which compute the zero polynomial. It is well known that $\mathsf{PIT}\in\coRP$. Kabanets and Impagliazzo [KI04] proved that certain circuit lower bounds follow from the assumption that $\mathsf{PIT}\in\P$. As a corollary to Theorem 1.2, we are able to prove theorem of a similar kind.

A constant free arithmetic circuit is an arithmetic circuit which is only allowed to use the constants $\{0,\pm 1\}$.

A different way to interpret 1.3 is as saying that at least one of the following three lower bound results hold: either $\mathsf{PIT}\not\in\P$, or (at least) one of the two circuit lower bounds stated in the corollary. We emphasize that the result holds under any (even so-called white box) derandomization of $\mathsf{PIT}$.

Our statement is similar to, but incomparable with the result of Kabanets and Impagliazzo [KI04] who proved that if $\mathsf{PIT}\in\P$ then either the permanent does not have polynomial size constant free arithmetic circuits, or $\NEXP\not\subseteq\P/\poly$.

Since $(\varepsilon n,\varepsilon n^{2})$-rigid matrices have linear circuit of size $3\varepsilon n^{2}$, the last item of 1.3 in particular implies a conditional construction of $(\Omega(n),\Omega(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 [AC19, BHPT20]. However, the rigidity parameters in these papers are not enough to imply circuit lower bounds (furthermore, even optimal rigidity parameters are not enough to imply $\Omega(n^{2})$ lower bounds for general linear circuits).

Since it is widely believed that $\mathsf{PIT}\in\P$, the answer to which of the last two items of 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 [MS10]), it is tempting to also believe that the equations should not be easily computable, as they provide “proof” for rigidity which 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.

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 $\mathbb{F}$ be an algebraically closed field. A set $V\subseteq\mathbb{F}^{n}$ is called an affine variety if there exist polynomials $f_{1},\ldots,f_{t}\in\mathbb{F}[x_{1},\ldots,x_{n}]$ such that $V=\{\mathbf{x}:f_{1}(\mathbf{x})=f_{2}(\mathbf{x})=\cdots=f_{t}(\mathbf{x})=0\}$. For convenience, in this paper we often refer to affine varieties simply as varieties.

For each variety $V$ there is a corresponding ideal $\mathbf{I}(V)\subseteq\mathbb{F}[x_{1},\ldots,x_{n}]$ which is defined as

Conversely, for an ideal $I\subseteq\mathbb{F}[x_{1},\ldots,x_{n}]$ we may define the variety

Given a set $A\subseteq\mathbb{F}^{n}$ we may similarly define the ideal $\mathbf{I}(A)$. The (Zariski) closure of a set $A$, denoted $\overline{A}$, is the set $\mathbf{V}(\mathbf{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 which contains $A$. By construction, $\overline{A}$ is a variety, and a polynomial which vanishes everywhere on $A$ is also vanishes on $\overline{A}$.

Over $\mathbb{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 paper (which correspond to sets of “low complexity” objects, e.g., non-rigid matrices or matrices which 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 [BI17]).

A variety $V$ is called irreducible if it cannot be written as a union $V=V_{1}\cup V_{2}$ of varieties $V_{1},V_{2}$ that are properly contained in $V$. Every variety can be uniquely written as a union $V=V_{1}\cup V_{2}\cup\cdots\cup V_{m}$ of irreducible varieties. The varieties $V_{1},\ldots,V_{m}$ are then called the irreducible components of $V$.

We now define a map $U(\mathbf{x},\mathbf{y})$ which is “universal” for size $s$ linear circuits, i.e., it contains in its image all $n\times n$ matrices $A$ whose corresponding linear transformation can be computed by a linear circuit of size at most $s$.

Let $s\geq n$. We first define a universal graph $G$ for size $s$. $G$ has a set $V_{0}$ of $n$ input nodes labeled $X_{1},\ldots 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},\ldots,V_{s}$, each contains $s$ vertices.

Each vertex $v\in V_{i}$, for $0\leq i\leq s+1$, has as its children all vertices $u\in V_{j}$ for all $0\leq 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^{\prime}\leq s^{4}$ be the number of edges in $V$ and let $e_{i}$ denote the $i$-th edge, $1\leq i\leq s^{\prime}$. The edge $e_{i}$ is labeled by the $i$-th coordinate of the map $\mathrm{SV}_{s^{\prime},s}(\mathbf{x},\mathbf{y})$ given in 2.1.

Thus, the graph $G$ with this labeling computes a linear transformation (over the field $\mathbb{F}(\mathbf{x},\mathbf{y})$) in the variables $X_{1},\ldots,X_{n}$. More explicitly, the $(i,j)$-th entry of the matrix $U(\mathbf{x},\mathbf{y})$ representing this linear transformation is given by the sum, over all paths from $X_{i}$ to the $j$-th output node, of the product of the edge labels on that path. This entry is a polynomial in $\mathbf{x},\mathbf{y}$, so that we can think of $U$ as a polynomial map from $\mathbb{F}^{2s}$ to $\mathbb{F}^{n^{2}}$.

Analogous to the proof of Theorem 1.1, we now observe via a dimension counting argument that the image of the polynomial map $U(\mathbf{x},\mathbf{y})$ has a equation of degree at most $n^{3}$. This would complete the proof of Theorem 1.2.