Uniform Bounds on Product Sylvester-Gallai Configurations

The Polynomial Identity Testing (PIT) problem is the task of determining whether a given algebraic circuit computes the zero polynomial. While there are simple and efficient randomized algorithms for the PIT problem, developing an efficient deterministic solution remains a significant open problem in theoretical computer science. The PIT problem is closely tied to fundamental topics such as lower bounds for algebraic circuits [28, 2, 30] and derandomizing key problems in mathematics and computer science [3, 19, 33, 36, 26, 18]. For a deeper exploration of PIT and its applications, see [43, 48, 44].

The recent works [1, 25, 50] have shown that the PIT problem for general circuits can be reduced to solving it for low-depth circuits, such as unrestricted depth-3 or homogeneous depth-4 circuits, which has made these circuit classes a focus of recent study. Notably, progress has been made towards deterministic, polynomial-time PIT for depth-3 circuits of constant top fanin via the connection between this problem and linear Sylvester-Gallai configurations arising from depth-3 identities [14, 32, 45].

Let us now explain how Sylvester-Gallai configurations arise in the context of depth-3 and depth-4 PIT. Let $𝐱:=(x_1,\mathrm{\dots },x_N)$ be a tuple of $N$ variables and $S:=ℂ\left[𝐱\right]$ be the polynomial ring in $N$ variables. Suppose we are given a depth three circuit with top fan-in three (denoted ${\mathrm{\Sigma }}^3\mathrm{\Pi }\mathrm{\Sigma }$) that computes a polynomial $P$. Such a polynomial has the form

where ${\mathrm{\ell }}_i,g_j,h_k$ are linear forms. When $P\equiv 0$, that is, when we have an identity, and moreover this representation of the identity is “efficient,”¹¹1The formal definition of efficient is simple and minimal, as defined in [32]. we may wonder whether the linear forms in the identity must be “low dimensional” (i.e., all such linear forms must “depend on few variables”). To capture the dimensionality of the circuit given by Equation 1, [14] defined the rank of the circuit as being the linear span of the forms that appear in the circuit. In case of Equation 1, we have that the rank is $dim{\text{span}}_{ℂ}{\{{\mathrm{\ell }}_i,g_j,h_k\}}_{i,j,k\in [m]}$.

Consider a linear form ${\mathrm{\ell }}_i$ from the first gate and a second linear form $g_j$ from the second gate. Since $P\equiv 0$, we have that for any $𝐚\in {ℂ}^N$ such that ${\mathrm{\ell }}_i(𝐚)=g_j(𝐚)=0$, it must be the case that $\prod h_k(𝐚)=0$. In other words, we have that $V({\mathrm{\ell }}_i,g_j)\subset V\left(\prod h_k\right)={\bigcup }_{k}V\left(h_k\right)$. Since the algebraic set $V({\mathrm{\ell }}_i,g_j)$ is irreducible, we must have $V({\mathrm{\ell }}_i,g_j)\subset V\left(h_a\right)$ for some $a\in [m]$. Note that this last condition (combined with the symmetry among the gates) is exactly the local constraint arising from the dual formulation of Sylvester’s problem. In [14], the authors asked whether sets ${\left\{{\mathrm{\ell }}_i\right\}}_{i\in [m]},{\left\{g_j\right\}}_{j\in [m]},{\left\{h_k\right\}}_{k\in [m]}$ arising from Equation 1 which satisfy the above conditions must be low-dimensional – more precisely, whether $dim{\text{span}}_{ℂ}{\{{\mathrm{\ell }}_i,g_j,h_k\}}_{i,j,k}=O(1)$.

As it turns out, the Sylvester-Gallai like condition in the previous paragraph can be seen as a set-version of Sylvester’s problem, which was studied by [15]. This work showed that such configurations must have constant rank. Thus, we deduce that ${\text{span}}_{ℂ}\{{\mathrm{\ell }}_i,g_j,h_k\}=O(1)$. This shows that any ${\mathrm{\Sigma }}^3\mathrm{\Pi }\mathrm{\Sigma }$ identity essentially depends on constantly many variables. Combined with the results of [31], this gives a black box deterministic PIT algorithm for such circuits. While significantly extra complexity and subtleties arise when one works with ${\mathrm{\Sigma }}^k\mathrm{\Pi }\mathrm{\Sigma }$ circuits for $k>3$, the linear forms in “efficient” identities arising from such circuits satisfy enough local relationships to deduce that they have low rank. This approach was carried out by [32, 45], who generalized the above approach and showed an intrinsic and elegant connection between ${\mathrm{\Sigma }}^k\mathrm{\Pi }\mathrm{\Sigma }$ identities and Sylvester-Gallai configurations (see [45, Theorem 1.4]). As a result of this connection, Sylvester-Gallai theorems imply deterministic, polynomial-time PIT algorithms for ${\mathrm{\Sigma }}^k\mathrm{\Pi }\mathrm{\Sigma }$ circuits, when $k=O(1)$.

Motivated by these results, Gupta [24] studied depth four circuits with constant top and bottom fan-ins. This circuit family is denoted ${\mathrm{\Sigma }}^k\mathrm{\Pi }\mathrm{\Sigma }{\mathrm{\Pi }}^d$, and it computes polynomials which can be written as a sum of $k$ products of polynomials of degree at most $d$.

Consider a polynomial $Q$ computed by a ${\mathrm{\Sigma }}^3\mathrm{\Pi }\mathrm{\Sigma }{\mathrm{\Pi }}^d$ circuit. It has the form

where $A_i,B_j,C_k$ are polynomials of degree at most $d$. If $Q\equiv 0$ and the representation is efficient, as in the previous case, we have $V(A_i,B_j)\subseteq V\left(\prod C_k\right)$.²²2By symmetry among the gates, we also have $V(A_i,C_k)\subseteq V\left(\prod B_j\right)$ and $V(B_j,C_k)\subseteq V\left(\prod A_i\right)$. However, as the forms are not necessarily linear, we have that $V(A_i,B_j)$ is not necessarily irreducible, and thus we no longer have the same Sylvester-Gallai type configuration, as we cannot guarantee the existence of $k\in [m]$ such that $V(A_i,B_j)\subset V\left(C_k\right)$. Nevertheless, as there are many constraints of the form $V(A_i,B_j)\subseteq V\left(\prod C_k\right)$, [24] asked whether such Sylvester-Gallai type conditions would be enough to prove that $dim{\text{span}}_{ℂ}{\{A_i,B_j,C_k\}}_{i,j,k}$ is small enough.

Given any “efficient” ${\mathrm{\Sigma }}^3\mathrm{\Pi }\mathrm{\Sigma }{\mathrm{\Pi }}^d$ circuit (not necessarily computing the zero polynomial), [24] called it a Sylvester-Gallai circuit if the above constraints on the zerosets (i.e. $V(A_i,B_j)\subseteq V\left(\prod C_k\right)$) hold. The above discussion shows that all such circuits that compute $0$ are Sylvester-Gallai circuits, but the converse is not true: for instance, multiplying a single form by a constant can change whether or not the circuit computes $0$ without changing the above condition.

Non Sylvester-Gallai circuits are relatively simple compared to Sylvester-Gallai circuits. Non Sylvester-Gallai circuits do not have too many cancellations (the above discussion shows that they can never compute $0$), and the circuit structure can be preserved by certain linear variable reduction maps, which is the main tool used in the works [24, 23] to handle these circuits. This allows these works to certify the non-zeroness of non-Sylvester-Gallai circuits.

The cancellations in Sylvester-Gallai circuits on the other hand are a lot more subtle, and it is not clear if they are preserved by the linear maps of [24, 23]. Similar to how linear Sylvester-Gallai configurations have constant rank, Gupta conjectured that sets of higher degree forms satisfying the local condition $V(A_i,B_j)\subset V\left({\prod }_k{C}_k\right)$ must “depend on constantly many variables.” If this is true, then we can efficiently test if Sylvester-Gallai circuits are nonzero using the methods of [8]. A simpler form of Gupta’s main conjecture is the following generalization of the configurations studied in [15]:

A first step towards establishing the above conjecture is to establish the Sylvester-Gallai version of the above conjecture. This motivates us to consider the Sylvester-Gallai configurations we study in this article, which we now define. By way of the algebraic-geometric dictionary, we will henceforth replace the geometric condition $V(A,B)\subset V\left(C\right)$ by the equivalent algebraic condition $\mathrm{rad}\left(C\right)\subset \mathrm{rad}(A,B)$.

As stated above, the reader may find it strange that the product constraint no longer seems local, since the condition for each $F_i,F_j$ involves every other form in the configuration. However, by a standard Bézout type argument it follows that the condition ${\prod }_{F\in ℱ\setminus \{F_i,F_j\}}F\in \mathrm{rad}(F_i,F_j)$ is equivalent to the (local) condition that there are indices $k_1,\mathrm{\dots },k_{d^2}$ different from $i,j$ such that

Since $d$ is a constant, each (local) condition now only depends on constantly many forms in the configuration as expected. As this equivalent condition is more cumbersome to state, we prefer to work with the above definition.

In a similar fashion to [24], we can also conjecture that such “product” configurations are “low dimensional.” This is the content of the following conjecture:

The above conjecture was first considered by [39], where the authors proved Conjecture 4 for $d=2$. Our main theorem, which we now state, generalizes their main result to forms of every degree, thus fully settling Conjecture 4.

Our proof techniques build upon the techniques introduced in [47, 38] to study radical Sylvester-Gallai configurations, which we define in Section 1.3. In Section 1.3 we also discuss related and previous works on non-linear Sylvester-Gallai configurations and the PIT problem for depth-4 circuits. In Section 1.4, we give a high level outline of our proof, highlighting the technical difficulties that need to be overcome, as well as the new conceptual contributions of this work. We will now discuss the main contributions of this work, where we state our main technical result, which is of independent interest. Formal statements and proofs of all claims can be found in the full version of this paper.

This paper has two main contributions. The first is the proof of Theorem 5, which states that product Sylvester-Gallai configurations of degree bounded by $d$ have dimension uniformly upper bounded by a function which depends only on $d$. This result simultaneously generalizes [47, 39, 38], putting us one step closer towards a proof of Conjecture 2, and also to the main conjecture of Gupta [24]. To achieve this, we adapt the inductive approach from [38] to work with product configurations. This adaptation, as we discuss in Section 1.4, requires us to deal with several subtleties, one of them being to establish a useful property of the general quotients of [47, 38]: we prove that such general quotients behave well with respect to (a generalized notion of) absolute irreducibility. More precisely, we prove that that these quotients send absolutely reducible forms to reducible elements, and that forms which are absolutely irreducible over the vector space being quotiented out will remain absolutely irreducible after a general quotient.

The second contribution is our main technical result which relates absolute irreducibility of a polynomial $P$ with an effective and uniform bound on the non-primality of certain ideals containing $P$. In a simplified form, it can be stated as:

We believe that the above theorem, and its more general version (which can be found in the full version), together with its proof, are of independent interest. We now briefly discuss the ingredients needed in the proof of the above theorem. If one only combines results from Gröbner basis theory and elimination theory with techniques from algebraic geometry, one can obtain an effective bound for the above theorem which depends on $N,n$ and $d$. Since the goal of a Sylvester-Gallai theorem is to obtain bounds independent of the number of variables, such a bound will not be good enough for our purposes. By combining the Stillman’s uniformity bounds of [5] with results from elimination theory and algebraic geometry, we are able to obtain an effective bound (depending only on $n,d$) on the number of non-associate irreducible forms $Q$ such that $(P,Q)$ is not prime.

Once the dependence on $N$ has been removed and a finite bound on the number of (non-associate) bad forms $Q$ has been established, we can then use Bertini’s theorem and the Ananyan-Hochster principle to further drop the dependency on $n$, finally obtaining a bound which simply depends on the degree $d$. To achieve this, we give very effective bounds on the degrees of generators of Gröbner bases for ideals generated by a small number of variables of low degree, and also for certain elimination ideals of such ideals. These bounds could be of independent interest.

An important point to note is that [38] builds on the Ananyan-Hochster principle to show their transfer theorems, which we also use. However, to prove the above theorem, we also need to apply the Ananyan-Hochster principle in a different manner: combined with results from Gröbner basis theory, we use it to find low degree polynomials in elimination ideals of ideals generated by a small number of low degree forms.

In this subsection we provide an overview of the proof of our main result, Theorem 5. We begin by outlining the high-level approach used in previous works to bound the dimension of the span of radical Sylvester-Gallai configurations and discuss the challenges of applying this method in our context. Next, we describe the tools that we employ to address these challenges. Finally, we provide a concise summary of how these components are combined to establish our main theorem.

To illustrate the ideas in this overview, we use a special case of product Sylvester-Gallai configurations with a simplifying assumption as an example. In the final part of this subsection, we explain how this assumption can be eliminated to extend the argument to the general case.