Partial Derivative Complexity of a Product of Linearly Independent Quadratics

Shalmon, Nir; Shpilka, Amir

doi:10.4230/LIPIcs.ICALP.2026.152

Partial Derivative Complexity of a Product of Linearly Independent Quadratics

Nir Shalmon

Blavatnik School of Computer Science and AI, Tel Aviv University, Israel Amir Shpilka

Blavatnik School of Computer Science and AI, Tel Aviv University, Israel

Abstract

The partial derivative method is a central tool in algebraic complexity, underlying lower bounds for multilinear formulas, bounded depth circuits, and algebraic branching programs. A key feature of this measure is its subadditivity and submultiplicativity, which are usually used to upper bound the measure. However, proving lower bounds requires bounding the measure of explicit polynomials from below, and in some cases, a sharp estimate is required. For example, a frequently used fact is that the dimension of the space spanned by order $k$ partial derivatives of a product of $n$ linearly independent linear functions is $\binom{n}{k}$ .

Beyond the linear case, however, not much is known about the behavior of the (general) partial derivative measure under multiplication. In particular, it has been conjectured that for algebraically independent polynomials $g_{1},\dots,g_{r}\in{\mathbb{C}}[{{\mathbf{x}}}]$ , the partial derivative complexity of the product $\prod_{i=1}^{r}{g_{i}({{\mathbf{x}}})}$ grows exponentially with $r$ (see [5, Question 42]), but prior to this work such bounds were only known when the $g_{i}$ ’s are linear polynomials, or satisfy additional restrictions.

In this paper, we show a lower bound of $\exp(\Omega(r^{1/6}))$ for the measure of a product of $r$ linearly independent quadratic polynomials. This is the first result to show such a lower bound on the partial derivative measure of a product of nonlinear polynomials, without any further restrictions. Interestingly, we only assume linear independence, which is weaker than algebraic independence. Our proof relies on algebraic-geometric and combinatorial techniques, combining the Jacobian approach of [5] together with the theory of wide algebras introduced in [2, 25, 12]. To our knowledge, this is the first use of wide-algebra techniques for proving lower bounds on partial derivative complexity, and one of the first applications of these techniques outside the context of Sylvester–Gallai type problems.

Keywords and phrases:

algebraic complexity theory, partial derivatives, arithmetic circuits, quadratic polynomials

Category:

Track A: Algorithms, Complexity and Games

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Algebraic complexity theory

Funding:

This research was funded by the European Union (ERC, EACTP, 101142020). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.

DOI:

10.4230/LIPIcs.ICALP.2026.152

Event:

53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The partial derivative measure, introduced in [24], after being implicitly used in [23], is one of the most successful lower bound methods in algebraic complexity theory. Given a polynomial $f(x_{1},\dots,x_{n})$ and an integer $k\geq 0$ , let $\partial^{k}(f)$ denote the set of all order- $k$ partial derivatives of $f$ . The order- $k$ partial derivative measure of $f$ is

\mu_{k}(f)=\dim\bigl(\operatorname{span}{(\partial^{k}(f))}\bigr)\ .

This measure, and variants of it such as the rank of the partial derivative matrix with respect to a partition of variables [23], shifted partial derivatives [16], and projected shifted partial derivatives [17, 21], have been instrumental in proving lower bounds on algebraic circuit size. Most notably, they were used to prove lower bounds on multilinear formula size [29], on the size of depth- $4$ homogeneous circuits for polynomials in $\mathrm{VP}$ [14, 10, 19] and in the recent lower bound for bounded depth algebraic circuits computing the iterated matrix multiplication polynomial [22]. The method has also found applications for designing deterministic algorithms for the polynomial identity testing (PIT) problem [30, 9, 20, 8], and for reconstruction of algebraic circuits [3, 18]. See also the monograph [6] for more applications of the partial derivative measure.

Despite its extensive use, one basic aspect is still not well understood:

Question 1.

How does the partial derivative measure behave under multiplication?

If we consider a product of variables (or linearly independent linear functions) then it is easy to see that $\mu_{k}(x_{1}\cdot\ldots\cdot x_{n})=\binom{n}{k}$ . This is because each distinct multilinear partial derivative results in a distinct monomial, so they are linearly independent. This result can be generalized to any polynomial of the form $\prod_{i=1}^{n}x_{i}\cdot g(x_{1},\ldots,x_{n})$ , see Theorem 8.

A natural question is whether $\mu_{k}$ grows exponentially for products of linearly, or algebraically, independent polynomials of higher degrees. This was asked in the Master thesis of Bincovich [4]. A special case of this problem was studied in [5, Section 4.4] where the following conjecture was raised.

Conjecture 2 ([5, Conjecture 47]).

For all constants $\alpha_{1},\alpha_{2},\ldots,\alpha_{r}\in\mathbb{C}$ and linearly independent homogeneous linear forms $\ell_{1},\ell_{2},\ldots,\ell_{r}$ , the following holds: if $q_{1},q_{2},\ldots,q_{r}$ are polynomials whose minimum-degree nonzero monomial has degree at least $2$ , then the partial derivative complexity of the polynomial

\prod_{i=1}^{r}(\alpha_{i}+\ell_{i}+q_{i})

is at least $2^{r}$ .

Question 1 and Conjecture 2 are manifestations of a broader and poorly understood phenomenon in algebraic complexity theory: the behavior of complexity measures under multiplication. While many measures admit clean subadditivity properties under addition, their behavior under products, although submultiplicative, is often subtle and unpredictable. As a result, structural understanding of individual polynomials often fails to extend to their products.

Perhaps surprisingly, even for basic measures such as sparsity (number of monomials of a polynomial), our understanding remains incomplete. For instance, it is not known how much the number of monomials of a polynomial can decrease when the polynomial is squared; despite decades of work, there remains an exponential gap between the best known lower and upper bounds on the sparsity of powers of polynomials [1, 32]. Likewise, we do not have meaningful lower bounds on the partial derivative measure of the square of a multivariate polynomial in terms of the measure of the polynomial itself.

This difficulty already arises when one attempts to go beyond the linear setting. For example, Bincovich showed that a sparse polynomial cannot have too many linearly independent linear factors [4]. He further observed that extending such arguments to higher-degree factors appears to require lower bounds on the partial-derivative measure of products of linearly independent nonlinear polynomials.

Despite the importance and the many applications of the partial derivative measure, a nontrivial answer to Question 1 and Conjecture 2 is known only in a very special case. Concretely, Chaugule et al. [5] proved that if the $r$ polynomials are algebraically independent, and their variety of common zeros contains a nonsingular point (“Property S” in [5]), then the partial derivative measure of their product is indeed at least $2^{r}$ . In summary, outside the linear case and the Property S setting, no superpolynomial lower bound on the partial derivative measure of products of nonlinear polynomials was previously known.

1.1 Main Result and Technical Contributions

Our main result shows that linear independence alone implies superpolynomial growth of the order- $k$ partial derivative measure for products of quadratic polynomials.

Let ${\mathbb{K}}$ be an algebraically closed field of characteristic $0$ . Denote ${{\mathbf{x}}}=(x_{1},\ldots,x_{n})$ .

Theorem 3 (Main theorem).

Let $q_{1},\dots,q_{r}\in{\mathbb{K}}[{{\mathbf{x}}}]$ be linearly independent homogeneous quadratic polynomials, and let $h\in{\mathbb{K}}[{{\mathbf{x}}}]$ be any nonzero polynomial. Then for every $0\leq k\leq\left\lfloor r^{1/6}/3\right\rfloor$ ,

\mu_{k}\!\left(h\cdot\prod_{i=1}^{r}q_{i}\right)\ \geq\ \binom{\left\lfloor r^% {1/6}/3\right\rfloor}{k}.

In particular, taking $k=\left\lfloor r^{1/6}/6\right\rfloor$ yields $\mu_{k}\!\left(h\cdot\prod_{i=1}^{r}q_{i}\right)\geq\exp(\Omega(r^{1/6}))$ .

An important ingredient of our proof is the following structural theorem, which is interesting on its own and may have further applications.

Theorem 4 (Structure theorem).

Let $q_{1},\dots,q_{r}\in{\mathbb{K}}[{{\mathbf{x}}}]$ be homogeneous quadratics, and $h\in{\mathbb{K}}[{{\mathbf{x}}}]$ be nonzero. Assume that for some $0\leq k\leq r$ and some $t\in{\mathbb{N}}$ ,

\mu_{k}\left({h\cdot\prod_{i=1}^{r}{q_{i}}}\right)<\binom{t}{k}\ .

Then there is a graded vector space $V=V_{1}+V_{2}\subset{\mathbb{K}}[{{\mathbf{x}}}]$ with dimension sequence $(18t^{3},2t)$ such that $q_{1},\dots,q_{r}$ are all contained in the algebra ${\mathbb{K}}[V]$ , where $V_{1}$ consists of linear forms and $V_{2}$ of quadratic forms.

In other words, if $\mu_{k}\!\left(h\cdot\prod_{i}^{r}q_{i}\right)$ is small for some $k\leq r$ , then all quadratics $q_{i}$ must live inside a small graded algebra generated by few linear forms and few quadratic polynomials. Theorem 3 follows immediately from Theorem 4 by a dimension-counting argument.

1.2 High-level proof ideas

We explain the ideas behind the proof of Theorem 4. To provide intuition for our proof, we start with an informal proof of a toy example.

Low variable support example

Assume each of $\{q_{i}\}_{i=1}^{r}\subseteq{\mathbb{K}}[{{\mathbf{x}}}]$ depends on at most $s$ variables, and that for some $0\leq k\leq r$ ,

\mu_{k}\left(\prod_{i=1}^{r}{q_{i}}\right)<\binom{t}{k}\ .

Pick a maximal subsequence $q_{i_{1}},\dots,q_{i_{m}}$ such that the quadratics $\{q_{i_{j}}\}_{j=1}^{m}$ depend on disjoint sets of variables. Then, every monomial in $\prod_{j=1}^{m}{q_{i_{j}}}$ depends on at least $m$ distinct variables. The following folklore result implies that $\mu_{k}\left(\prod_{j=1}^{m}{q_{i_{j}}}\right)\geq\binom{m}{k}$ , so $m<t$ .

Observation 5.

If each monomial in $f\in{\mathbb{K}}[{{\mathbf{x}}}]$ contains at least $m$ variables then $\mu_{k}(f)\geq\binom{m}{k}$ for every $k$ .

Thus, if $m$ is large then we have already obtained a lower bound on the partial derivative measure of the product. So assume that $m$ is not too large. We next show a method for reducing the number of variables appearing in each quadratic from $s$ to $s-1$ .

The idea is that since the sequence $q_{i_{1}},\dots,q_{i_{m}}$ was maximal, every other quadratic shares a variable with some polynomial in it. Thus, to reduce the support of the remaining quadratics, we apply a general projection to the variables appearing in the $q_{i_{j}}$ ’s, sending them to random multiples of a fresh variable $z$ . Note that we applied the projection to at most $s m$ variables.

By the reasoning above, each quadratic in $\{q_{i}\}_{i=1}^{r}$ now depends on at most $s-1$ variables in $\{x_{1},\dots,x_{n}\}$ (and on $z$ ). Since this is a projection, it is not hard to prove that it can only reduce $\mu_{k}$ . We can therefore repeat this process again, projecting the variables of $\leq m$ other quadratics such that each resulting quadratic depends on at most $s-2$ ${{\mathbf{x}}}$ -variables. After at most $s$ iterations of this, all quadratics contain no variable in $\{x_{1},\dots,x_{n}\}$ . We conclude that $\prod_{i=1}^{r}{q_{i}}$ only ever depended on $\leq s^{2}m$ variables. Therefore, after renaming variables

\{q_{i}\}_{i=1}^{r}\subseteq\operatorname{span}(\{x_{i}x_{j}\mid 1\leq i,j\leq s% ^{2}m\})

and we conclude that

\dim(\operatorname{span}(\{q_{i}\}_{i=1}^{r}))\leq s^{4}m^{2}\ .

In particular, if $r>s^{4}m^{2}$ , this contradicts the linear independence of $q_{1},\ldots,q_{r}$ .

We next explain how to generalize this toy example to the general case.

Generalizing to arbitrary quadratics

To generalize the idea above, we use the technique of wide vector spaces and strong algebras developed in [2] to prove Stillman’s conjecture, and later adapted and extended in [25, 12, 26] to prove rank upper bounds for Sylvester–Gallai type configurations resulting from higher degree polynomials, and to obtain new polynomial identity testing (PIT) algorithms [13].

To explain the idea we first recall the Jacobian approach of [5]. The main observation is that if $\text{\boldmath$\mathbf{\gamma}$}\in{\mathbb{K}}^{n}$ is a nonsingular common zero of $q_{1},\ldots,q_{r}$ then the linear parts of the polynomials $q_{i}({{\mathbf{x}}}+\text{\boldmath$\mathbf{\gamma}$})$ are linearly independent linear forms. By considering the homogeneous term of minimal degree in the product $\prod_{i=1}^{r}q_{i}$ , it is not hard to see that $\mu_{k}\!\left(\prod_{i=1}^{r}q_{i}\right)\geq\binom{r}{k}$ .¹¹1We refer to this as the Jacobian approach, since the point $\mathbf{\gamma}$ is a common zero of the $q_{i}$ ’s at which the Jacobian has full rank.

We combine the Jacobian idea with the wide-algebra machinery in the following way. We first try to choose a small subset $\{q_{i_{j}}\}_{j=1}^{m}\subseteq\{q_{i}\}_{i=1}^{r}$ , and call its span the core space. The point is to choose it so that this space is sufficiently strong, namely, that no nonzero linear combination of the quadratics in it has low rank. By [2], this implies that the chosen quadratics form a regular sequence and generate a radical ideal. Intuitively, one should think about these quadratics as being completely unrelated, or as playing the role of disjoint variables. In particular, if such a core is large enough, the Jacobian criterion applies and yields a large partial derivative measure.

As before, we may therefore assume that no such core can be too large. The wide-algebra machinery developed in [25, 12, 26] then implies that every other quadratic is “close”, in a precise sense, to the span of the chosen ones. More formally, for every $1\leq i\leq r$ , there exists a small number of linear forms $\ell_{1},\dots,\ell_{u}\in{\mathbb{K}}[{{\mathbf{x}}}]_{1}$ such that $q_{i}\in{\mathbb{K}}[q_{i_{1}},\dots,q_{i_{m}},\ell_{1},\dots,\ell_{u}]$ . Consequently, after a linear change of variables, each $q_{i}$ depends on only a bounded number of new linear directions modulo the core space.

The notion of integral sequences allows us to reason about quadratics that are still “independent” modulo the core space, much as in the toy example we reasoned about quadratics supported on disjoint sets of variables. If we could find a long integral sequence outside the core, then the same commutative-algebra argument as above would again imply a large lower bound on $\mu_{k}$ . Hence, under our assumption on $\mu_{k}$ , every maximal integral sequence must be short.

We now imitate the toy argument. Starting from the current strong quadratic space, we choose a maximal integral sequence and project the linear directions associated with it. The difficulty is that such a projection may destroy the strongness of the current space: morally, it may push some of the core quadratics closer to one another. To repair this, we apply a strengthening step, which replaces the projected space by a new strong one while paying only a controlled number of linear forms. In this way, each round makes the remaining quadratics closer to the current strong space. Formally, one can attach to each quadratic a certain quotient space of linear directions, and the dimension of this space decreases in every round. This gives a progress measure, so the process must terminate after boundedly many steps.

Intuitively, this process mimics the low-support case in the sense that at every step we project a number of linear forms depending on $m$ , making each polynomial outside the core closer to the core. This process must terminate after a number of steps that depends on $m$ , thus proving again, that the total dimension is not too large. This yields a lower bound on $m$ , contradicting our assumption that the core cannot be large.

Strengthening was introduced in [2] and later refined in [26]. General projections were introduced in [34, 28, 27] and later extended in [25, 26, 13].

1.3 Related work

Our proof uses tools that were originally developed for rather different problems. The starting point is the work of Ananyan and Hochster [2] on Stillman’s conjecture. One of the central ideas there is that if a family of bounded-degree forms is not sufficiently strong, then it lies in a subalgebra generated by fewer forms together with boundedly many forms of lower degree. In degree $2$ , the same framework also implies that sufficiently strong quadratic spaces give regular sequences and radical ideals. In the present paper, this philosophy appears both in the construction of the initial strong quadratic space and in the strengthening step, where we restore strongness after a projection.

The subsequent works [25, 12, 26] adapted these ideas to higher-degree Sylvester–Gallai type configurations. There the goal is typically to prove an upper bound on the rank of a family of forms satisfying many algebraic incidences. The common strategy is to build a small core space, measure the remaining forms relative to that core via relative Lin-spaces, choose maximal integral sequences to capture directions that are independent modulo the core, and then apply general projections to eliminate those directions while preserving the relevant algebraic structure. After such a projection, strengthening is used to replace the projected core by a new strong/wide one so that the process can continue. Our proof uses essentially this same projection-strengthening mechanism, but the contradiction comes from lower bounds on $\mu_{k}$ rather than from Sylvester–Gallai incidences.

The same toolbox was also used recently in polynomial identity testing, where it yields structural decompositions that can be exploited algorithmically [13]. In contrast, we use only the structural statements. What is new here is the way these tools are combined with the Jacobian criterion of Chaugule et al. [5]: the Jacobian criterion turns a sufficiently large strong quadratic space into a lower bound on the partial derivative measure, while the wide-algebra machinery shows that if such a space cannot be grown too much, then all the quadratics must lie in a small graded algebra.

2 Preliminaries

We denote $[n]:=\{1,\ldots,n\}$ . We use ${{\mathbf{x}}}$ to denote the $n$ -tuple of variables ${{\mathbf{x}}}=(x_{1},\ldots,x_{n})$ . Throughout the paper, ${\mathbb{K}}$ is an algebraically closed field of characteristic $0$ . We denote by ${\mathbb{K}}[{{\mathbf{x}}}]_{d}$ the linear space of homogeneous polynomials of degree $d$ . For a ring $R$ and a set $A\subset R$ we denote by $(A)$ the ideal generated by $A$ .

We next give some basic tools that we will need for our proof and the required algebraic definitions.

2.1 The Partial Derivative Measure

Definition 6.

Let $f\in{\mathbb{K}}[{{\mathbf{x}}}]$ be a polynomial and let $k\geq 0$ be an integer. Denote by $\partial^{k}(f)$ the set of all order- $k$ partial derivatives of $f$ , i.e.,

\partial^{k}(f)=\left\{\frac{\partial^{k}f}{\partial x_{j_{1}}\cdots\partial x% _{j_{k}}}\;\middle|\;j_{1},\ldots,j_{k}\in[n]\right\}.

We define

\mu_{k}(f):=\dim\operatorname{span}\bigl(\partial^{k}(f)\bigr).

This measure has been studied and used extensively in algebraic complexity, see for example [35, 6, 31] and references therein. The next lemma states two basic facts about this measure.

Lemma 7.

Let $f,g\in{\mathbb{K}}[{{\mathbf{x}}}]$ be polynomials and $A\in\mathrm{GL}_{n}({\mathbb{K}})$ . Let $k\geq 0$ . The following hold:

1.

(Subadditivity) $\mu_{k}(f+g)\leq\mu_{k}(f)+\mu_{k}(g)$
2.

(Change of variables) $\mu_{k}(f\circ A)=\mu_{k}(f)$

Theorem 8.

Let $\ell_{1},\dots,\ell_{r}\in{\mathbb{K}}[{{\mathbf{x}}}]_{1}$ be linear homogeneous polynomials that are linearly independent over ${\mathbb{K}}$ , and let $h\in{\mathbb{K}}[{{\mathbf{x}}}]$ be nonzero. Then for every $0\leq k\leq r$ ,

\mu_{k}\!\left(h\cdot\prod_{i=1}^{r}\ell_{i}\right)\;\geq\;\binom{r}{k}.

For a proof see e.g., [11, Theorem 1].

The main goal of this paper is to extend Theorem 8 to the case of quadratic polynomials (recall Theorem 3).

2.2 The Jacobian criterion of [5]

An important ingredient of our proof is the following Jacobian criterion based on [5]. The following lemma slightly generalizes [5, Theorem 43] by taking $h$ to be an arbitrary nonzero polynomial. The proof is nearly identical. Recall the definition of the Jacobian matrix of a set of polynomials.

Definition 9.

Let $f_{1},\dots,f_{r}\in{\mathbb{K}}[{{\mathbf{x}}}]$ . The Jacobian matrix of $f_{1},\ldots,f_{r}$ is an $r\times n$ matrix, denoted ${\mathcal{J}}(f_{1},\ldots,f_{r})$ , such that ${\mathcal{J}}(f_{1},\ldots,f_{r})_{i,j}=\frac{\partial f_{i}}{\partial x_{j}}$ .

Lemma 10 (Jacobian criterion for $\mu_{k}$ ).

Let $f_{1},\dots,f_{r},h\in{\mathbb{K}}[{{\mathbf{x}}}]$ all nonzero. Suppose there exists $\text{\boldmath$\mathbf{\gamma}$}=(\gamma_{1},\dots,\gamma_{n})\in{\mathbb{K}}% ^{n}$ such that

f_{i}(\text{\boldmath$\mathbf{\gamma}$})=0\ \ \text{for all }i\in[r],\qquad% \text{and}\qquad\operatorname{rank}\bigl(\operatorname{\mathcal{J}}(f_{1},% \dots,f_{r})(\text{\boldmath$\mathbf{\gamma}$})\bigr)=r.

Then for every $0\leq k\leq r$ ,

\mu_{k}\!\left(h\cdot\prod_{i=1}^{r}f_{i}\right)\ \geq\ \binom{r}{k}.

Proof.

By the shift invariance of the partial derivative measure [5, Lemma 46], we can shift the polynomials by $\mathbf{\gamma}$ without changing the measure:

\mu_{k}\!\left(h({{\mathbf{x}}})\cdot\prod_{i=1}^{r}f_{i}({{\mathbf{x}}})% \right)=\mu_{k}\!\left(h({{\mathbf{x}}}+\text{\boldmath$\mathbf{\gamma}$})% \cdot\prod_{i=1}^{r}f_{i}({{\mathbf{x}}}+\text{\boldmath$\mathbf{\gamma}$})% \right).

Since $f_{i}(\text{\boldmath$\mathbf{\gamma}$})=0$ , the constant term of each $f_{i}({{\mathbf{x}}}+\text{\boldmath$\mathbf{\gamma}$})$ vanishes. Its Taylor expansion begins with the homogeneous linear part:

\ell_{i}({{\mathbf{x}}}):=\sum_{j=1}^{n}x_{j}\cdot\frac{\partial f_{i}}{% \partial x_{j}}(\text{\boldmath$\mathbf{\gamma}$})\ ,

followed by terms of degree $2$ or higher (see e.g., [5, Corollary 14]).

The coefficient vectors of $\ell_{1},\dots,\ell_{r}$ are exactly the rows of $\operatorname{\mathcal{J}}(f_{1},\dots,f_{r})(\text{\boldmath$\mathbf{\gamma}$})$ . The assumption that $\operatorname{rank}\bigl(\operatorname{\mathcal{J}}(f_{1},\dots,f_{r})(\text{% \boldmath$\mathbf{\gamma}$})\bigr)=r$ therefore implies that the linear forms $\ell_{1},\dots,\ell_{r}$ are linearly independent.

Let $H_{t}({{\mathbf{x}}})$ be the lowest-degree nonzero homogeneous component of $h({{\mathbf{x}}}+\text{\boldmath$\mathbf{\gamma}$})$ . The lowest-degree nonzero homogeneous component of the entire shifted product $h({{\mathbf{x}}}+\text{\boldmath$\mathbf{\gamma}$})\cdot\prod_{i=1}^{r}f_{i}({% {\mathbf{x}}}+\text{\boldmath$\mathbf{\gamma}$})$ is simply the product of the lowest-degree components of its factors $H_{t}({{\mathbf{x}}})\cdot\prod_{i=1}^{r}\ell_{i}({{\mathbf{x}}})$ . Taking the lowest-degree homogeneous component can only decrease or maintain the partial derivative measure. We therefore conclude:

\mu_{k}\!\left(h\cdot\prod_{i=1}^{r}f_{i}\right)\geq\mu_{k}\left({H_{t}({{% \mathbf{x}}})\cdot\prod_{i=1}^{r}\ell_{i}({{\mathbf{x}}})}\right)\geq\binom{r}% {k}\ ,

where the final inequality follows from Theorem 8. $\hfill\blacktriangleleft$

2.3 Regular Sequences and Lower Bounds

In this subsection, we introduce some notions from commutative algebra. We first recall some basic definitions (see, e.g.,[7]).

The Krull dimension of a commutative ring $R$ , denoted $\dim R$ , is the supremum of the integers $n$ for which there exists a chain of prime ideals $\mathfrak{p}_{0}\subsetneq\mathfrak{p}_{1}\subsetneq\cdots\subsetneq\mathfrak{% p}_{n}$ in $R$ . For an ideal $I\triangleleft R$ , define $\dim(I):=\dim(R/I)$ . We denote by $\operatorname{Spec}(R)$ the set of prime ideals of $R$ . For a prime ideal $\mathfrak{p}\in\operatorname{Spec}(R)$ , the height of $\mathfrak{p}$ , denoted $\operatorname{ht}(\mathfrak{p})$ , is the supremum of the integers $n$ for which there exists a chain of prime ideals $\mathfrak{p}_{0}\subsetneq\mathfrak{p}_{1}\subsetneq\cdots\subsetneq\mathfrak{% p}_{n}=\mathfrak{p}$ in $R$ . The codimension (or height) of an ideal $I\triangleleft R$ , denoted $\operatorname{codim}(I)$ , is $\operatorname{codim}(I):=\inf\{\operatorname{ht}(\mathfrak{p})\mid\mathfrak{p}% \in\operatorname{Spec}(R),\ I\subseteq\mathfrak{p}\}$ .

We define the affine variety of zeros of an ideal $I\triangleleft{\mathbb{K}}[{{\mathbf{x}}}]$ by $Z(I)=\{\text{\boldmath$\mathbf{\gamma}$}\in{\mathbb{K}}^{n}\mid\forall f\in I,% \;f(\text{\boldmath$\mathbf{\gamma}$})=0\}$ . We define $\dim(Z(I)):=\dim(I)$ . It follows that $\operatorname{codim}(I)=\operatorname{codim}(Z(I))$ .

Definition 11 (Nonsingular (smooth) point).

Let $I=(f_{1},\dots,f_{t})\subseteq{\mathbb{K}}[{{\mathbf{x}}}]$ be a radical ideal and $X=Z(I)$ the corresponding affine variety. We say that $\text{\boldmath$\mathbf{\gamma}$}\in{\mathbb{K}}^{n}$ is a nonsingular point if

\operatorname{rank}_{\mathbb{K}}(\operatorname{\mathcal{J}}(f_{1},\dots,f_{t})% (\text{\boldmath$\mathbf{\gamma}$}))=\operatorname{codim}(X).

Otherwise $\mathbf{\gamma}$ is a singular point.

Theorem 12 (Nonsingular locus is dense open [15, Theorem 5.3]).

If $X$ is an affine variety over ${\mathbb{K}}$ , then the set of singular points is a proper Zariski-closed subset of $X$ . Equivalently, the set of non-singular points is a nonempty Zariski-open subset.

Definition 13 (Nonzerodivisor).

Let $R$ be a commutative ring. An element $a\in R$ is a nonzerodivisor if $ab=0$ implies $b=0$ for all $b\in R$ .

We next define the notion of a regular sequence that will play an important role in our proofs. In the next definition the reader is encouraged to think of $R={\mathbb{K}}[{{\mathbf{x}}}]$ .

Definition 14 (Regular sequence).

Let $R$ be a commutative ring and let $f_{1},\dots,f_{r}\in R$ . We say that $f_{1},\dots,f_{r}$ is a regular sequence if $f_{1}$ is a nonzerodivisor in $R$ , and for each $i\geq 2$ the image of $f_{i}$ in $R/(f_{1},\dots,f_{i-1})$ is a nonzerodivisor.

Definition 15 (Depth of an ideal).

Let $R$ be a commutative Noetherian ring. For a proper ideal $I\subseteq R$ , define $0pt(I)$ to be the length of any maximal regular sequence contained in $I$ .

We note that $0pt(I)$ is well defined as all maximal regular sequences in a proper ideal have the same length [7, Corollary 17.8].

Definition 16 (Cohen–Macaulay ring).

A commutative ring $R$ such that $0pt(M)=\operatorname{codim}(M)$ for every maximal ideal $M\triangleleft R$ is called a Cohen–Macaulay ring.

Theorem 17.

[7, Theorem 18.7, Proposition 18.9] ${\mathbb{K}}[{{\mathbf{x}}}]$ is a Cohen–Macaulay ring. In particular, for every proper ideal $I\subseteq{\mathbb{K}}[{{\mathbf{x}}}]$ , $0pt(I)=\operatorname{codim}(I)$ .

Corollary 18 (Radical regular sequence gives $\mu_{k}$ lower bounds).

Let $f_{1},\dots,f_{r}\in{\mathbb{K}}[{{\mathbf{x}}}]$ be polynomials that form a regular sequence, and assume the ideal $I=(f_{1},\dots,f_{r})$ is radical. Then for every $0\leq k\leq r$ and every nonzero $h\in{\mathbb{K}}[{{\mathbf{x}}}]$ ,

\mu_{k}\!\left(h\cdot\prod_{i=1}^{r}f_{i}\right)\ \geq\ \binom{r}{k}.

Proof.

Let $X=Z(I)\subseteq{\mathbb{K}}^{n}$ . Since $f_{1},\dots,f_{r}$ is a regular sequence that generates $I$ , it is a maximal regular sequence. By Definition 15 $0pt(I)=r$ and from Theorem 17 we conclude that $\operatorname{codim}(I)=\operatorname{codim}(X)=r$ .

Since $I$ is radical, we can apply Theorem 12, therefore the nonsingular locus $X_{\mathrm{ns}}$ of $X$ is a nonempty Zariski-open subset of $X$ . Choose any nonsingular point $\text{\boldmath$\mathbf{\gamma}$}\in X_{\mathrm{ns}}$ , we have $\dim_{\mathbb{K}}(\operatorname{\mathcal{J}}(f_{1},\dots,f_{t})(\text{% \boldmath$\mathbf{\gamma}$}))=\operatorname{codim}(X)=r$ . Now apply Lemma 10 to $f_{1},\dots,f_{r}$ and the given nonzero $h$ at the point $\mathbf{\gamma}$ . It yields, for every $0\leq k\leq r$ ,

\mu_{k}\!\left(h\cdot\prod_{i=1}^{r}f_{i}\right)\ \geq\ \binom{r}{k},

as required. $\hfill\blacktriangleleft$

2.4 Wide Spaces

We recall some useful definitions and theorems from [28, 12].

Definition 19 (Rank and $\operatorname{Lin}(\cdot)$ for quadratics).

A quadratic form is an element $Q\in{\mathbb{K}}[{{\mathbf{x}}}]_{2}$ .

1.

The rank of a quadratic form $Q$ , denoted $\operatorname{rank}(Q)$ , is the smallest $s\in\mathbb{N}$ such that

$Q=\sum_{i=1}^{s}a_{i}b_{i}\qquad\text{for some }a_{i},b_{i}\in{\mathbb{K}}[{{% \mathbf{x}}}]_{1}.$

Such a decomposition is called a minimal representation of $Q$ .
2.

Let $Q\in{\mathbb{K}}[{{\mathbf{x}}}]_{2}$ have a minimal representation $Q=\sum_{i=1}^{s}a_{i}b_{i}$ . We define

$\operatorname{Lin}(Q)\ :=\ \operatorname{span}_{{\mathbb{K}}}\{a_{1},\dots,a_{% s},b_{1},\dots,b_{s}\}\ \subseteq\ {\mathbb{K}}[{{\mathbf{x}}}]_{1}.$

This space is well defined regardless of the minimal representation chosen. We shall refer to it as the Lin space of $Q$ .

Lemma 20 ([28, Fact 2.15]).

Let $Q=\sum_{i=1}^{m}a_{2i-1}\,a_{2i}$ be a homogeneous quadratic polynomial. Then $\operatorname{Lin}(Q)\subseteq\operatorname{span}\{a_{1},\ldots,a_{2m}\}$ .

Definition 21 (Wide spaces, closeness, relative linear spaces, and integral sequences).

Let $V=V_{1}+V_{2}$ be a graded vector space with $V_{i}\subseteq{\mathbb{K}}[{{\mathbf{x}}}]_{i}$ .

1.

We say that $V$ is $r$ -strong if for every nonzero $Q\in V_{2}$ we have

$\operatorname{rank}(Q)\geq r.$
2.

We say that $V$ is $r$ -wide if for every nonzero $Q\in V_{2}$ we have

$\operatorname{rank}(Q)\geq\dim(V)+r.$

In this case we also say that ${\mathbb{K}}[V]$ is an $r$ -wide algebra.
3.

A quadratic form $P\in{\mathbb{K}}[{{\mathbf{x}}}]_{2}$ is $s$ -close to $V$ if there exists $Q\in{\mathbb{K}}[V]$ such that $\operatorname{rank}(P-Q)\leq s$ . If $P$ is not $r$ -close to $V$ for any $r\leq s$ , we say that $P$ is $s$ -far from $V$ . For a linear form $\ell\in{\mathbb{K}}[{{\mathbf{x}}}]_{1}$ , $\ell$ is $1$ -close to $V$ if $\ell\notin V_{1}$ .
4.

Fix integers $r, B$ with $r>2B+1$ . When $V$ is $r$ -wide and $P$ is $s$ -close to $V$ for some $s<r/2$ , we define the relative space of linear forms $\mathbb{L}_{V}(P)\subseteq{\mathbb{K}}[{{\mathbf{x}}}]$ in the following way

$\mathbb{L}_{V}(P)\ :=\ \begin{cases}\operatorname{span}(P)+V_{1}&\text{if }P% \in{\mathbb{K}}[{{\mathbf{x}}}]_{1}\\[2.0pt] \operatorname{Lin}(P-Q)+V_{1}&\text{if }P\in{\mathbb{K}}[{{\mathbf{x}}}]_{2}% \text{ and }s\leq B\\[2.0pt] \operatorname{span}(P)&\text{otherwise}\end{cases}\ ,$

where $Q\in{\mathbb{K}}[V]$ satisfies $\operatorname{rank}(P-Q)=s$ (this is well-defined when $s\leq B$ , by [12, Proposition 54]). We also define the quotient space

$\overline{\mathbb{L}}_{V}(P)\ :=\ \begin{cases}\mathbb{L}_{V}(P)/V_{1}&\text{% if }s\leq B\\ 0&\text{otherwise}\end{cases}\ .$

We refer to it as the relative Lin of $P$ with respect to $V$ .
5.

(Integral sequences.) Let $t,B\in\mathbb{N}$ and assume $r>4tB+1$ . Let $V=V_{1}+V_{2}$ be $r$ -wide, and let $F_{1},\dots,F_{t}$ be forms that are $B$ -close to $V$ . Set $U_{0}:=V$ and for $i\geq 1$ define

$U_{i}\ :=\mathbb{L}_{U_{i-1}}(F_{i})\ +\ V_{2}.$

We say that $(F_{1},\dots,F_{t})$ is an integral sequence with respect to $V$ , if for every $i\in[t]$ :

$\dim\overline{\mathbb{L}}_{V}(F_{i})\ =\ \dim\overline{\mathbb{L}}_{U_{i-1}}(F% _{i})\qquad\text{and}\qquad F_{i}\notin(V),$

where $(V)$ denotes the ideal of ${\mathbb{K}}[{{\mathbf{x}}}]$ generated by $V$ .

The following theorem of [2] connects the notion of strength to earlier definitions.

Theorem 22 ([2, Theorem 4.14]).

If $q_{1},\dots,q_{r}\in{\mathbb{K}}[{{\mathbf{x}}}]$ are linearly independent homogeneous quadratics that span an $(r-1)$ -strong space then they form a regular sequence. Moreover, the ideal they generate, $I=(q_{1},\ldots,q_{r})$ , is radical.

Corollary 23.

If $q_{1},\dots,q_{r}\in{\mathbb{K}}[{{\mathbf{x}}}]$ are linearly independent homogeneous quadratics that span an $(r-1)$ -strong space, and $h\in{\mathbb{K}}[{{\mathbf{x}}}]$ is nonzero, then $\mu_{k}(h\cdot\prod_{i=1}^{r}{q_{i}})\geq\binom{r}{k}$ .

Proof.

This follows immediately by combining Theorem 22 with Corollary 18. $\hfill\blacktriangleleft$

The following two lemmas together with Corollary 18 show the utility of integral sequences in bounding $\mu_{k}$ :

Lemma 24 ([12, Lemma 63]).

Suppose $V$ is an $r$ -wide vector space and $F_{1},\dots,F_{t}$ is an integral sequence with respect to $V$ , where all forms are irreducible. Suppose $F_{0}\in{\mathbb{K}}[V]\setminus\{0\}$ . Then $F_{0},F_{1},\dots,F_{t}$ is a regular sequence in ${\mathbb{K}}[{{\mathbf{x}}}]$ . Moreover, it holds that $F_{1},\dots,F_{t}$ is also a regular sequence in ${\mathbb{K}}[{{\mathbf{x}}}]$ .

$\blacktriangleright$ Remark 25.

The “moreover” part of Lemma 24 is not explicitly stated in [12, Lemma 63] but it follows easily from the lemma combined with [12, Corollary 62]. In general it is not always true that if $f_{1},\ldots,f_{t}$ is a regular sequence then so is $f_{2},\ldots,f_{t}$ .

Lemma 26 ([12, Lemma 64]).

Suppose $V$ is an $r$ -wide vector space and $F_{1},\dots,F_{t}$ is an integral sequence with respect to $V$ , where all forms are irreducible. Then $(F_{1},\dots,F_{t})$ is radical, and for any minimal prime $(F_{1},\dots,F_{t})\subseteq\mathfrak{p}$ we have $\mathfrak{p}\cap{\mathbb{K}}[V]=(0)$ .

3 General Projections

3.1 Definition and Basic Properties

We now recall the definition and properties of projection maps from [34, 28, 12].

Definition 27 (Projection map).

Let $W\subseteq{\mathbb{K}}[{{\mathbf{x}}}]_{1}$ be a subspace of linear forms of dimension $t$ and let $\{y_{1},\dots,y_{t}\}$ be a basis of $W$ . Let $y_{1},\dots,y_{n}$ be a basis of ${\mathbb{K}}[{{\mathbf{x}}}]_{1}$ that extends the basis of $W$ . Let $z$ be a formal variable not in $\{x_{1},\dots,x_{n}\}$ . For $\text{\boldmath$\mathbf{\alpha}$}=(\alpha_{1},\dots,\alpha_{t})\in{\mathbb{K}}% ^{t}$ we define the projection map²²2The quotient space is isomorphic to a polynomial ring. The choice of basis affects the resulting isomorphism; however, for our purposes, the specific choice of isomorphic polynomial ring is immaterial.

\varphi_{(W,\text{\boldmath$\mathbf{\alpha}$})}:{\mathbb{K}}[{{\mathbf{x}}}]% \rightarrow{\mathbb{K}}[\mathbf{y}]\rightarrow{\mathbb{K}}[\mathbf{y},z]% \rightarrow{\mathbb{K}}[\mathbf{y},z]/(W)\simeq{\mathbb{K}}[y_{t+1},\ldots,y_{% n},z]

where ${\mathbb{K}}[{{\mathbf{x}}}]\rightarrow{\mathbb{K}}[\mathbf{y}]$ is a simple change of basis, ${\mathbb{K}}[\mathbf{y}]\rightarrow{\mathbb{K}}[\mathbf{y},z]$ is defined by

y_{i}\mapsto\begin{cases}\alpha_{i}z&\text{if }1\leq i\leq t\\[6.0pt] y_{i}&\text{otherwise}\end{cases}\ .

and ${\mathbb{K}}[\mathbf{y},z]\rightarrow{\mathbb{K}}[\mathbf{y},z]/(W)$ is the canonical projection into the quotient ring.

$\blacktriangleright$ Remark 28.

With the notation of Definition 27, the image of the map ${\mathbb{K}}[\mathbf{y}]\rightarrow{\mathbb{K}}[\mathbf{y},z]$ already lies in the subring ${\mathbb{K}}[y_{t+1},\dots,y_{n},z]$ , since the variables $y_{1},\dots,y_{t}$ are sent to scalar multiples of $z$ . Thus the final quotient by $(W)=(y_{1},\dots,y_{t})$ does not change the image; it merely removes the unused variables $y_{1},\dots,y_{t}$ from the ambient ring and allows us to view the target as the polynomial ring ${\mathbb{K}}[y_{t+1},\dots,y_{n},z]$ . Equivalently, one may view $\varphi_{(W,\text{\boldmath$\mathbf{\alpha}$})}$ as the map induced by the quotient

{\mathbb{K}}[y_{1},\dots,y_{n},z]\big/\bigl(y_{1}-\alpha_{1}z,\dots,y_{t}-% \alpha_{t}z\bigr),

but we prefer the formulation in Definition 27 because later arguments treat the target as an explicit polynomial ring with distinguished variable $z$ .

We next define the notion of a general projection. Intuitively, it means that $\mathbf{\alpha}$ is generic with respect to a finite set of polynomials.

Definition 29 (General projection).

Let $W\subseteq{\mathbb{K}}[{{\mathbf{x}}}]_{1}$ be a linear space. We say that a property ${\mathcal{P}}$ holds for a general projection $\varphi_{(W,\text{\boldmath$\mathbf{\alpha}$})}$ , if there exists a non-empty open subset (with respect to the Zariski topology) $U\subseteq{\mathbb{K}}^{t}$ such that ${\mathcal{P}}$ holds for all $\varphi_{(W,\text{\boldmath$\mathbf{\alpha}$})}$ with $\text{\boldmath$\mathbf{\alpha}$}\in U$ . Equivalently, there is a closed set $C$ such that the property holds for all $\varphi_{(W,\text{\boldmath$\mathbf{\alpha}$})}$ such that $\alpha\not\in C$ .

In the definition, $U\subseteq{\mathbb{K}}^{t}$ is open with respect to the Zariski topology, hence it is the complement of the zero set of finitely many polynomial functions on ${\mathbb{K}}^{t}$ . The definition of a general projection allows us to say that we can choose the projection according to an element $\mathbf{\alpha}$ that avoids any finite set of polynomial constraints.

$\blacktriangleright$ Remark 30.

For any projection $\varphi_{(W,\text{\boldmath$\mathbf{\alpha}$})}$ and any vector space $V\subseteq{\mathbb{K}}[{{\mathbf{x}}}]$ , $\varphi_{(W,\text{\boldmath$\mathbf{\alpha}$})}(V)$ is a vector space. Moreover, applying $\varphi$ does not change the degree of any monomial (that remains nonzero), and in particular maps homogeneous polynomials of degree $d$ to homogeneous polynomials of degree $d$ , or to $0$ .

As shown in previous work, general projections preserve several important properties of polynomials.

Proposition 31 ([25, Proposition 2.6]).

Let $F\in{\mathbb{K}}[{{\mathbf{x}}}]$ be a polynomial and let $W\subseteq{\mathbb{K}}[{{\mathbf{x}}}]_{1}$ be a vector space of linear forms of dimension $t$ . Let $\text{\boldmath$\mathbf{\alpha}$}\in{\mathbb{K}}^{t}$ .

1.

If $F\notin{\mathbb{K}}[W]$ , then $\varphi_{(W,\text{\boldmath$\mathbf{\alpha}$})}(F)\notin{\mathbb{K}}[z]$ for a general projection $\varphi_{(W,\text{\boldmath$\mathbf{\alpha}$})}:{\mathbb{K}}[{{\mathbf{x}}}]% \to{\mathbb{K}}[y_{t+1},\dots,y_{n},z]$ .
2.

If $F\neq 0$ , then $\varphi_{(W,\text{\boldmath$\mathbf{\alpha}$})}(F)\neq 0$ for a general projection.
3.

Suppose $F$ is a form which does not have any multiple factors and $F\in(W)$ . If $\varphi_{(W,\text{\boldmath$\mathbf{\alpha}$})}(F)=z^{k}G$ where $G\notin(z)$ , then $G$ does not have any multiple factors.

The following lemma is a special case of [13, Proposition 5.12]. We defer its proof as well as the proof of the other claims in this section to the full version [33].

Lemma 32 (General projections are composable).

Let $W\subseteq{\mathbb{K}}[{{\mathbf{x}}}]_{1}$ and $\text{\boldmath$\mathbf{\alpha}$}\in{\mathbb{K}}^{\dim(W)}$ . Then, for every $W^{\prime}\subseteq{\mathbb{K}}_{1}[y_{\dim(W)+1},\dots,y_{n},z]$ such that $z\in W^{\prime}$ , there exists a vector space $W^{\prime\prime}\subseteq{\mathbb{K}}[{{\mathbf{x}}}]_{1}$ with $\dim(W^{\prime\prime})=\dim(W)+\dim(W^{\prime})-1$ such that for any $\text{\boldmath$\mathbf{\alpha}$}^{\prime}\in{\mathbb{K}}^{\dim(W^{\prime})}$ , there is $\text{\boldmath$\mathbf{\alpha}$}^{\prime\prime}\in{\mathbb{K}}^{\dim(W^{% \prime\prime})}$ for which $\varphi_{(W^{\prime},\text{\boldmath$\mathbf{\alpha}$}^{\prime})}\circ\varphi_% {(W,\text{\boldmath$\mathbf{\alpha}$})}=\varphi_{(W^{\prime\prime},\text{% \boldmath$\mathbf{\alpha}$}^{\prime\prime})}$ . Moreover, a property that holds for a general $\text{\boldmath$\mathbf{\alpha}$},\text{\boldmath$\mathbf{\alpha}$}^{\prime}$ holds for a general $\text{\boldmath$\mathbf{\alpha}$}^{\prime\prime}$ .

Lemma 33 (Pullback of a graded algebra under a general projection).

Let $W\subseteq{\mathbb{K}}[{{\mathbf{x}}}]_{1}\subset{\mathbb{K}}[{{\mathbf{x}}},z% ]_{1}$ be a linear space of dimension $t\geq 1$ , with basis $\left\{{y_{1},\ldots,y_{t}}\right\}$ . Let $V^{\prime}_{1}\subseteq{\mathbb{K}}[{{\mathbf{x}}},z]_{1}$ be a linear space such that $z\in V^{\prime}_{1}$ and such that $V^{\prime}_{1}\cap W=\{0\}$ . Denote $\dim V^{\prime}_{1}=s+1$ , and let $y_{t+1},\ldots,y_{t+s}$ be a basis for $V^{\prime}_{1}\cap{\mathbb{K}}[{{\mathbf{x}}}]$ . Let $\left\{{y_{1},\ldots,y_{n}}\right\}$ be a basis of ${\mathbb{K}}[{{\mathbf{x}}}]$ and $V^{\prime}_{2}\subseteq{\mathbb{K}}_{2}[y_{t+1},\dots,y_{n},z]$ be a linear space of quadratics. Then there exist linear spaces $V_{1}\subseteq{\mathbb{K}}[{{\mathbf{x}}}]_{1}$ and $V_{2}\subseteq{\mathbb{K}}[{{\mathbf{x}}}]_{2}$ satisfying:

1.

$\dim(V_{1})\leq\dim(W)+\dim(V^{\prime}_{1})+\dim(V^{\prime}_{2})-1$
2.

$\dim(V_{2})\leq 2\dim(V^{\prime}_{2})$ .
3.

For every quadratic $q\in{\mathbb{K}}[{{\mathbf{x}}}]_{2}$ , if for a general projection $\varphi_{(W,\text{\boldmath$\mathbf{\alpha}$})}(q)\in{\mathbb{K}}[V^{\prime}_{% 1}+V^{\prime}_{2}]$ , then $q\in{\mathbb{K}}[V_{1}+V_{2}]$ .

Corollary 34.

Fix a vector space $W\!\subseteq\!{\mathbb{K}}[{{\mathbf{x}}}]_{1}$ . We have $\dim(\operatorname{Lin}(\varphi_{(W,\text{\boldmath$\mathbf{\alpha}$})}(q)))\!% \geq\!\dim(\operatorname{Lin}(q))-\dim(W)$ for a general projection.

3.2 Rank and Distance Under General Projections

We continue with a few lemmas that show how the notions of rank and distance of quadratics behave under general projections. We omit the proofs in this version and the interested reader can find them in [33].

Lemma 35 (Projections do not increase distances).

Let $V_{1}\subseteq{\mathbb{K}}_{1}[x_{1},\dots,x_{n}],V_{2}\subseteq{\mathbb{K}}_{% 2}[x_{1},\dots,x_{n}]$ be vector spaces, and let $P\in{\mathbb{K}}_{2}[x_{1},\dots,x_{n}]$ be $B$ -close to $V$ . For any vector space $W\subseteq{\mathbb{K}}_{1}[x_{1},\dots,x_{n}]$ and $\text{\boldmath$\mathbf{\alpha}$}\in{\mathbb{K}}^{\dim(W)}$ , $\varphi_{(W,\text{\boldmath$\mathbf{\alpha}$})}(P)$ is $B$ -close to $\varphi_{(W,\text{\boldmath$\mathbf{\alpha}$})}(V)$ .

Lemma 36.

Let $V\subseteq V_{1}+V_{2}$ be a graded vector space that is $2B+1$ -wide, and let $P\in{\mathbb{K}}[{{\mathbf{x}}}]_{2}$ be $B$ -close to $V$ . Let $W\subseteq{\mathbb{K}}[{{\mathbf{x}}}]_{1}$ . Assume $\overline{\mathbb{L}}_{V}(P)\cap((W+V_{1})/V_{1})\neq\{0\}$ . Let $V^{\prime}=V^{\prime}_{1}+V^{\prime}_{2}$ be any graded vector space in $\text{Im}(\varphi_{(W,\text{\boldmath$\mathbf{\alpha}$})})={\mathbb{K}}[y_{% \dim(W)+1},\dots,y_{n},z]$ that is $2B+1$ -wide, such that $z\in V^{\prime}_{1}$ , and for a general projection mapping it holds that ${\mathbb{K}}[\varphi_{(W,\text{\boldmath$\mathbf{\alpha}$})}(V)]\subseteq{% \mathbb{K}}[V^{\prime}]$ . Then $\dim{\bigl(\overline{\mathbb{L}}_{V^{\prime}}(\varphi_{(W,\text{\boldmath$% \mathbf{\alpha}$})}(P))\bigr)}<\dim{\bigl(\overline{\mathbb{L}}_{V}(P)\bigr)}$ .

Lemma 37 (Dimension of partials does not increase under projections).

Let $W\subseteq{\mathbb{K}}[{{\mathbf{x}}}]_{1}$ be a subspace of linear forms. Let $\text{\boldmath$\mathbf{\alpha}$}=(\alpha_{1},\ldots,\alpha_{t})\in{\mathbb{K}% }^{t}$ . Then for every $f\in{\mathbb{K}}[{{\mathbf{x}}}]$ and $k\geq 0$ ,

\mu_{k}\bigl(\varphi_{(W,\text{\boldmath$\mathbf{\alpha}$})}(f)\bigr)\ \leq\ % \mu_{k}(f).

4 Main Proof

In this section we prove Theorem 3 and Theorem 4. As explained in Section 1.2, Theorem 3 is an easy consequence of Theorem 4.

We first give a high level view of the proof.

4.1 Roadmap of the proof

We prove Theorem 4 by contradiction. Assume that

\mu_{k}\!\left(h\cdot\prod_{i=1}^{r}q_{i}\right)<\binom{t}{k}.

The first step is to construct a small $t$ -strong quadratic space $V_{2}$ such that every $q_{i}$ is $t$ -close to $V_{2}$ ; otherwise Corollary 23 would already imply the desired lower bound on $\mu_{k}$ .

The second step is to repair the fact that projections may decrease the rank of quadratics in $V_{2}^{(j)}$ : we apply the strengthening lemma (Lemma 39), which replaces the current quadratic space by a projected one that is again strong while projecting only a controlled number of linear forms. The third step is to choose a maximal integral sequence among the irreducible projected quadratics. Such a sequence cannot have length $t$ , by Lemma 40 together with Lemma 37. We then project the sum of the corresponding relative Lin-spaces. Maximality implies that every remaining irreducible quadratic has nontrivial intersection with that projected space modulo the current ambient linear space, and therefore its quotient relative Lin-space drops by at least one; this is the content of Lemma 36. Since this quotient dimension starts at most $2t$ , after at most $2t$ rounds every irreducible quadratic lies in a small algebra. Finally, the remaining projected quadratics are reducible, so their linear factors span only a small linear space by Theorem 8. A pullback argument (Lemma 33) then yields the desired small graded algebra in the original ring.

4.2 Key Lemmas

We first start with a simple lemma bounding the dimension of the degree $2$ homogeneous part of ${\mathbb{K}}[V_{1}+V_{2}]$ . The proof can be found in the full version [33].

Lemma 38.

Let $V_{1}\subseteq{\mathbb{K}}[{{\mathbf{x}}}]_{1}$ and $V_{2}\subseteq{\mathbb{K}}[{{\mathbf{x}}}]_{2}$ be ${\mathbb{K}}$ -vector spaces, and let $Q$ be a set of quadratic forms such that $Q\subseteq{\mathbb{K}}[V_{1}+V_{2}]\cap{\mathbb{K}}[{{\mathbf{x}}}]_{2}$ . Then

\dim\operatorname{span}(Q)\ \leq\ \dim(V_{1})^{2}+\dim(V_{2}).

We next define the strengthening operation. Closely related operations appeared in the aforementioned previous works.

The motivation for this definition is the following. A projection can decrease the rank of quadratics in the current strong quadratic space, and hence destroy the strongness assumptions needed later to define and control relative linear spaces. The purpose of the strengthening step is to repair this loss. Starting from a quadratic space $V_{2}$ , it projects away a controlled number of linear forms so as to produce a new quadratic space $V_{2}^{\prime}$ that is again strong. The key point is that the number of linear forms spent in this repair is proportional to the loss in quadratic dimension. Properties 1–4 below are exactly the formal outputs of this procedure that will be needed in the main iteration.

Lemma 39 (Strengthening).

Let $V_{2}\subseteq{\mathbb{K}}[\mathbf{x},z]$ be a vector space. Let $B\in{\mathbb{N}}$ . Let $z^{\prime}$ be a new formal variable. There exists vector spaces $V_{1}\subseteq{\mathbb{K}}[{{\mathbf{x}}},z]_{1}$ , and $V^{\prime}_{2}\in{\mathbb{K}}_{2}[y_{\dim(V_{1})+1},\dots,y_{n},z^{\prime}]$ such that the following properties hold:

1.

$z\in V_{1}$
2.

${\mathbb{K}}[\varphi_{(V_{1},\text{\boldmath$\mathbf{\alpha}$}_{1})}(V_{2})]% \subseteq{\mathbb{K}}[\operatorname{span}(z^{\prime})+V^{\prime}_{2}]$ for a general projection, where $z^{\prime}$ is the variable we project to.
3.

$V^{\prime}_{2}$ is $B$ -strong.
4.

$\dim(V_{1})\leq\max(2B\cdot(\dim(V_{2})-\dim(V^{\prime}_{2})),1)$ .

Proof.

The idea of the proof is to perform the following process. As long as there exists a form $q\in V_{2}$ of rank $<B$ , we apply a general projection with respect to $\operatorname{Lin}(q)$ , sending it to random multiples of $z^{\prime}$ . This, in particular, sends $q$ to an element of $\operatorname{span}(z^{\prime 2})$ . The subspace $\operatorname{Lin}(q)$ has dimension at most $2B-2$ , and each such projection reduces $\dim(V_{2})$ by one. The process terminates when we arrive at a strong space, and the resulting composed projection has the required properties. We now proceed with the formal proof.

The proof of the claim is by induction on $\dim(V_{2})$ . The base case $\dim(V_{2})=0$ is trivial, with $V_{1}=\operatorname{span}(z)$ .

Assume $d=\dim(V_{2})>0$ , and that we proved the lemma for dimensions up to $d-1$ . If $V_{2}$ is already $B$ -strong, then let $V_{1}=\operatorname{span}(z)$ , and $V^{\prime}_{2}=\varphi_{(V_{1},\text{\boldmath$\mathbf{\alpha}$})}(V_{2})$ (this is just replacing $z$ with a multiple of $z^{\prime}$ ). It is clear that the desired properties hold. Otherwise, $V_{2}$ is not $B$ -strong. Assume $0\neq f\in V_{2}$ has rank smaller than $B$ , so in particular $\dim{\bigl(\operatorname{Lin}(f)\bigr)}\leq 2B-2$ . Complete $f$ to a basis of $V_{2}$ , $\left\{{b_{1},\dots,b_{d-1},f}\right\}$ .

Denote $t\mathrel{\mathop{:}}=\dim(\operatorname{Lin}(f)+\operatorname{span}(z))$ . Consider a general projection

\varphi_{(\operatorname{Lin}(f)+\operatorname{span}(z)),\text{\boldmath$% \mathbf{\alpha}$}}:{\mathbb{K}}[{{\mathbf{x}}},z]\rightarrow{\mathbb{K}}[\hat{% y}_{t+1},\dots,\hat{y}_{n},\hat{z}]

introducing a new variable $\hat{z}$ . Clearly, $\varphi_{(\operatorname{Lin}(f)+\operatorname{span}(z)),\text{\boldmath$% \mathbf{\alpha}$}}(f)\in\operatorname{span}(\hat{z}^{2})$ . By linearity,

\varphi_{({\operatorname{Lin}(f)+\operatorname{span}(z)},\text{\boldmath$% \mathbf{\alpha}$})}(V_{2})=\operatorname{span}\left({\varphi_{({\operatorname{% Lin}(f)+\operatorname{span}(z)}),\text{\boldmath$\mathbf{\alpha}$}}(b_{1}),% \dots,\varphi_{({\operatorname{Lin}(f)+\operatorname{span}(z)}),\text{% \boldmath$\mathbf{\alpha}$}}(b_{d-1}),\hat{z}^{2}}\right)\ .

Assume without loss of generality that

\varphi_{({\operatorname{Lin}(f)+\operatorname{span}(z)}),\text{\boldmath$% \mathbf{\alpha}$}}(V_{2})=\operatorname{span}\left({\varphi_{({\operatorname{% Lin}(f)+\operatorname{span}(z)}),\text{\boldmath$\mathbf{\alpha}$}}(b_{1}),% \dots,\varphi_{({\operatorname{Lin}(f)+\operatorname{span}(z)}),\text{% \boldmath$\mathbf{\alpha}$}}(b_{s}),\hat{z}^{2}}\right)

and that $\left\{{\varphi_{({\operatorname{Lin}(f)+\operatorname{span}(z)}),\text{% \boldmath$\mathbf{\alpha}$}}(b_{1}),\dots,\varphi_{({\operatorname{Lin}(f)+% \operatorname{span}(z)}),\text{\boldmath$\mathbf{\alpha}$}}(b_{s}),\hat{z}^{2}% }\right\}$ are linearly independent. Denote

\hat{V}_{2}=\operatorname{span}\left({\varphi_{(\operatorname{Lin}(f)+% \operatorname{span}(z)),\text{\boldmath$\mathbf{\alpha}$}}(b_{1}),\dots,% \varphi_{(\operatorname{Lin}(f)+\operatorname{span}(z)),\text{\boldmath$% \mathbf{\alpha}$}}(b_{s})}\right)\subsetneq\varphi_{(\operatorname{Lin}(f)+% \operatorname{span}(z)),\text{\boldmath$\mathbf{\alpha}$}}(V_{2})\ .

Clearly,

\dim(\hat{V}_{2})=s=\dim(\varphi_{(\operatorname{Lin}(f)+\operatorname{span}(z% )),\text{\boldmath$\mathbf{\alpha}$}}(V_{2}))-1\leq\dim(V_{2})-1\ ,

(1)

and

\hat{V}_{2}+\operatorname{span}(\hat{z}^{2})=\varphi_{(\operatorname{Lin}(f)+% \operatorname{span}(z)),\text{\boldmath$\mathbf{\alpha}$}}(V_{2})\ .

(2)

Apply the lemma inductively for $\hat{V}_{2}$ and $\hat{z}$ to get the vector spaces $\hat{V}_{1},\hat{V}^{\prime}_{2}$ that satisfy the desired properties. Since $\hat{V}_{2}\subseteq{\mathbb{K}}[\hat{y}_{t+1},\dots,\hat{y}_{n},\hat{z}]$ we make a change of basis to $\left\{{\mathbf{y^{\prime}},\hat{z}}\right\}$ so that the first basis elements span $\hat{V}_{1}$ . Let $\varphi_{\hat{V}_{1},\hat{\text{\boldmath$\mathbf{\alpha}$}}}:{\mathbb{K}}[% \hat{y}_{t+1},\dots,\hat{y}_{n},\hat{z}]\rightarrow{\mathbb{K}}[\mathbf{y^{% \prime}},z^{\prime}]$ be a general projection that sends $\hat{V}_{1}$ to $\operatorname{span}(z^{\prime})$ . Denote $\hat{R}={\mathbb{K}}[\hat{y}_{t+1},\dots,\hat{y}_{n},\hat{z}]$ , and $R^{\prime}={\mathbb{K}}[\mathbf{y^{\prime}},z^{\prime}]$ . Observe that $\hat{V}_{1},\hat{V}_{2}\subseteq\hat{R}$ and $\hat{V}^{\prime}_{2}\subseteq R^{\prime}$ . By the induction hypothesis (Property 1) we have $\hat{z}\in\hat{V}_{1}$ . From Lemma 32,

\varphi_{\hat{V}_{1},\hat{\text{\boldmath$\mathbf{\alpha}$}}}\circ\varphi_{(% \operatorname{Lin}(f)+\operatorname{span}(z)),\text{\boldmath$\mathbf{\alpha}$% }}=\varphi_{(V_{1},\text{\boldmath$\mathbf{\alpha}$}_{1})}

for some $V_{1}\subseteq{\mathbb{K}}[{{\mathbf{x}}},z]_{1}$ and $\text{\boldmath$\mathbf{\alpha}$}_{1}\in{\mathbb{K}}^{\dim(V_{1})}$ . By Lemma 32 we see that $\varphi_{(V_{1},\text{\boldmath$\mathbf{\alpha}$}_{1})}$ is a general projection. We next show that $V_{1}$ and $V^{\prime}_{2}:=\hat{V}^{\prime}_{2}$ satisfy the requirement of the lemma, for $V_{2}$ .

Property 1

By following the composition, one can witness that it sends $z$ to a multiple of $z^{\prime}$ . Therefore, $z\in V_{1}$ .

Property 2

From the definition of the composition, (2), and the fact that the composed general projection sends $z$ to a multiple of $z^{\prime}$ we obtain

	$\displaystyle{\mathbb{K}}[\varphi_{{V}_{1},\text{\boldmath$\mathbf{\alpha}$}_{% 1}}(V_{2})]$	$\displaystyle={\mathbb{K}}[\varphi_{\hat{V}_{1},\hat{\text{\boldmath$\mathbf{% \alpha}$}}}\bigl(\varphi_{(\operatorname{Lin}(f)+\operatorname{span}(z)),\text% {\boldmath$\mathbf{\alpha}$}}(V_{2})\bigr)]$
		$\displaystyle={\mathbb{K}}[\varphi_{\hat{V}_{1},\hat{\text{\boldmath$\mathbf{% \alpha}$}}}\left({\hat{V}_{2}+\operatorname{span}(\hat{z}^{2})}\right)]% \subseteq{\mathbb{K}}[\operatorname{span}(z^{\prime})+\varphi_{\hat{V}_{1},% \hat{\text{\boldmath$\mathbf{\alpha}$}}}(\hat{V}_{2})]\ .$

By the induction hypothesis, Property 2 holds and therefore

{\mathbb{K}}[\varphi_{\hat{V}_{1},\hat{\text{\boldmath$\mathbf{\alpha}$}}}(% \hat{V}_{2})]\subseteq{\mathbb{K}}[\operatorname{span}(z^{\prime})+\hat{V}^{% \prime}_{2}]\ .

Combining these equations we get

{\mathbb{K}}[\varphi_{(V_{1},\text{\boldmath$\mathbf{\alpha}$}_{1})}(V_{2})]% \subseteq{\mathbb{K}}[\operatorname{span}(z^{\prime})+\varphi_{\hat{V}_{1},% \hat{\text{\boldmath$\mathbf{\alpha}$}}}(\hat{V}^{\prime}_{2})]={\mathbb{K}}[% \operatorname{span}(z^{\prime})+{V}^{\prime}_{2}]\ ,

so Property 2 holds.

Property 3

This follows immediately as $V^{\prime}_{2}=\hat{V}^{\prime}_{2}$ , and $\hat{V}^{\prime}_{2}$ is $B$ -strong by the induction hypothesis.

Property 4

From Lemma 32, the induction hypothesis and (1) we conclude that

	$\displaystyle\dim(V_{1})$	$\displaystyle=\dim{\bigl(\operatorname{Lin}(f)+\operatorname{span}(z)\bigr)}+% \dim{(\hat{V}_{1})}-1$
		$\displaystyle\leq 2B-1+\max\bigl(2B\cdot(\dim(\hat{V}_{2})-\dim(\hat{V}^{% \prime}_{2})),1\bigr)-1$
		$\displaystyle\leq 2B-1+2B\cdot(\dim(\hat{V}_{2})-\dim(\hat{V}^{\prime}_{2}))$
		$\displaystyle\leq 2B\cdot\bigl(\dim(V_{2})-\dim(\hat{V}^{\prime}_{2})\bigr)$
		$\displaystyle=2B\cdot\bigl(\dim(V_{2})-\dim(V^{\prime}_{2})\bigr)\ ,$

as required. $\hfill\blacktriangleleft$

Lemma 40 (Integral Sequence Bound).

Let $V_{2}$ be a vector space in ${\mathbb{K}}[{{\mathbf{x}}},z]_{2}$ which is $(4t^{2}+\dim(V_{2})+3)$ -strong. If $q_{1},\dots,q_{t}$ is an integral sequence with respect to $V+\operatorname{span}(z)$ , of irreducible quadratics which are $t$ -close to $V+\operatorname{span}(z)$ , then for any nonzero polynomial $h\in{\mathbb{K}}[{{\mathbf{x}}}]$ :

\mu_{k}\left(h\cdot\prod_{i=1}^{t}q_{i}\right)\geq\binom{t}{k}.

Proof.

The choice of parameters satisfies the conditions of Lemma 24, from which (together with Remark 25) it follows that $q_{1},\dots,q_{t}$ is a regular sequence. By Lemma 26, this sequence generates a radical ideal. Corollary 18 gives the bound on the partial derivative measure. $\hfill\blacktriangleleft$

4.3 Proof of Theorem 4

The proof proceeds in four steps. We first construct the initial strong quadratic space $V_{2}$ . Next, we describe one round of the iteration: first strengthen the current strong quadratic space, then choose a maximal integral sequence, and finally project the sum of its relative linear spaces. Following that we show that each round decreases the dimension of the quotient relative linear space of every remaining irreducible quadratic by at least $1$ , and hence the process terminates after at most $2t$ rounds. Finally, we handle the remaining reducible quadratics and then pull the resulting small algebra back to the original ring.

Proof of Theorem 4.

We begin by constructing a strong space. Think of the $q_{i}$ as polynomials in ${\mathbb{K}}[{{\mathbf{x}}},z]$ , for the purpose of applying the iterative process described below. Also, assume $t\geq 2$ as otherwise the theorem is trivial. Start by collecting forms $q_{i}$ , one by one, into a vector space $V_{2}$ , as long as the resulting space remains $t$ -strong. Observe that by the assumption on $\mu_{k}$ and Corollary 23, this process must terminate after we collected at most $t$ forms. Let $V_{2}$ be maximal with respect to this property. Then $\dim(V_{2})\leq t$ , and maximality implies that every remaining quadratic $q_{i}$ is $t$ -close to $V_{2}$ , as otherwise adjoining $q_{i}$ would still preserve $t$ -strongness. Thus, we may assume that there is a $t$ -strong vector space $V_{2}\subseteq{\mathbb{K}}[{{\mathbf{x}}},z]_{2}$ with $\dim(V_{2})\leq t$ such that all $q_{1},\dots,q_{r}$ are $t$ -close to it. We note that it may be the case that $V_{2}=\{0\}$ .

During the iteration we will maintain quadratic spaces $V_{2}^{(j)}$ and distinguished variables $z^{(j)}$ such that after round $j$ , every irreducible projected quadratic $P$ satisfies

P\text{ is $t$-close to }\operatorname{span}(z^{(j)})+V_{2}^{(j)},\qquad\dim% \bigl(\overline{\mathbb{L}}_{\operatorname{span}(z^{(j)})+V_{2}^{(j)}}(P)\bigr% )\leq 2t-j.

(3)

The role of each round is to preserve the first condition while decreasing the right-hand side of the second by $1$ .

Given our $t$ -strong vector space $V_{2}$ , we now apply an iterative process: Set $B=4t^{2}+3t+3$ . Apply the strengthening lemma (Lemma 39) to $V_{2}$ . Let $V_{1}$ and $V^{\prime}_{2}$ be the subspaces guaranteed by the lemma. Call the new variable introduced by the strengthening lemma $z^{\prime}$ . Lemma 35 implies that for a general projection $\varphi_{(V_{1},\text{\boldmath$\mathbf{\alpha}$}_{1})}$ and for all $i$ , $\varphi_{(V_{1},\text{\boldmath$\mathbf{\alpha}$}_{1})}(q_{i})$ is $t$ -close to $\varphi_{(V_{1},\text{\boldmath$\mathbf{\alpha}$}_{1})}(V_{2})$ . By Property 2 of Lemma 39, $\varphi_{(V_{1},\text{\boldmath$\mathbf{\alpha}$}_{1})}(V_{2})\subseteq{% \mathbb{K}}[\operatorname{span}(z^{\prime})+V^{\prime}_{2}]_{2}$ . Hence, $\varphi_{(V_{1},\text{\boldmath$\mathbf{\alpha}$}_{1})}(q_{i})$ is $t$ -close to ${\mathbb{K}}[\operatorname{span}(z^{\prime})+V^{\prime}_{2}]_{2}$ . Consequently,

\dim{\bigl(\overline{\mathbb{L}}_{\operatorname{span}(z^{\prime})+V^{\prime}_{% 2}}(\varphi_{(V_{1},\text{\boldmath$\mathbf{\alpha}$}_{1})}(q_{i}))\bigr)}\leq 2% t\ .

(4)

Denote $R_{1}={\mathbb{K}}[y_{\dim(V_{1})+1},\dots,y_{n},z^{\prime}]$ , so that $\varphi_{(V_{1},\text{\boldmath$\mathbf{\alpha}$}_{1})}:{\mathbb{K}}[{{\mathbf% {x}}},z]\rightarrow R_{1}$ .

By Property 3 of Lemma 39, $V^{\prime}_{2}$ is $B$ -strong. Hence, from Lemma 40 and our assumption on $\mu_{k}$ we obtain that the irreducible polynomials among $\left\{{\varphi_{(V_{1},\text{\boldmath$\mathbf{\alpha}$}_{1})}(q_{i})}\right\}$ do not contain an integral sequence of length $t$ with respect to $\operatorname{span}(z^{\prime})+V^{\prime}_{2}$ . Indeed, any such sequence would again result in a contradiction to the assumption on $\mu_{k}$ (by Lemma 37, projection cannot increase $\mu_{k}$ ).

If there are no irreducible quadratics in $\left\{{\varphi_{(V_{1},\text{\boldmath$\mathbf{\alpha}$}_{1})}(q_{i})}\right\}$ then we stop the process. Otherwise, pick a maximal integral sequence with respect to $\operatorname{span}(z^{\prime})+V^{\prime}_{2}$ , among the irreducible $\left\{{\varphi_{(V_{1},\text{\boldmath$\mathbf{\alpha}$}_{1})}(q_{i})}\right\}$ . Denote this sequence by $\varphi_{(V_{1},\text{\boldmath$\mathbf{\alpha}$}_{1})}(q_{i_{j}})$ , for $1\leq j\leq m<t$ .

Denote

W\mathrel{\mathop{:}}=\sum_{j=1}^{m}\mathbb{L}_{\operatorname{span}(z^{\prime}% )+V^{\prime}_{2}}\!\left(\varphi_{(V_{1},\text{\boldmath$\mathbf{\alpha}$}_{1}% )}(q_{i_{j}})\right).

Thus $W$ is the space spanned by the relative Lin-spaces of the forms in the chosen integral sequence. By definition of $\mathbb{L}_{\operatorname{span}(z^{\prime})+V^{\prime}_{2}}(\varphi_{(V_{1},% \text{\boldmath$\mathbf{\alpha}$}_{1})}(q_{i_{j}}))$ it holds that $z^{\prime}\in W$ .

We now use the maximality of the integral sequence. Every irreducible quadratic outside the sequence must have nontrivial interaction with the directions already captured by the sequence. Concretely, if $\varphi_{(V_{1},\text{\boldmath$\mathbf{\alpha}$}_{1})}(q_{i})$ is irreducible and not in the sequence, then

\operatorname{span}(z^{\prime})\subsetneq\mathbb{L}_{\operatorname{span}(z^{% \prime})+V^{\prime}_{2}}\!\left(\varphi_{(V_{1},\text{\boldmath$\mathbf{\alpha% }$}_{1})}(q_{i})\right)\cap W.

Otherwise, $\varphi_{(V_{1},\text{\boldmath$\mathbf{\alpha}$}_{1})}(q_{i})$ could be appended to the integral sequence, contradicting maximality. Passing to the quotient by $\operatorname{span}(z^{\prime})$ , we obtain
$\{0\}\neq\left({\mathbb{L}_{\operatorname{span}(z^{\prime})+V^{\prime}_{2}}(% \varphi_{(V_{1},\text{\boldmath$\mathbf{\alpha}$}_{1})}(q_{i}))\cap W}\right)/% (\operatorname{span}(z^{\prime}))=\overline{\mathbb{L}}_{\operatorname{span}(z% ^{\prime})+V^{\prime}_{2}}(\varphi_{(V_{1},\text{\boldmath$\mathbf{\alpha}$}_{% 1})}(q_{i}))\cap\bigl((W)/\operatorname{span}(z^{\prime})\bigr)\ .$ (5)

Consider a general projection of $W$ , and let $R_{2}=R_{1}[\mathbf{y^{\prime}},z^{\prime\prime}]$ so that $\varphi_{(W,\text{\boldmath$\mathbf{\alpha}$})}:R_{1}\rightarrow R_{2}$ .

From Corollary 34 and since $V^{\prime}_{2}$ is $B$ -strong it follows that $\varphi_{(W,\text{\boldmath$\mathbf{\alpha}$})}(V^{\prime}_{2})$ is $(B-\dim(W))\geq(3t+3)$ -strong. Assume $\varphi_{(V_{1},\text{\boldmath$\mathbf{\alpha}$}_{1})}(q_{i})$ is irreducible and not in our integral sequence. Lemma 36 (applied to $P=\varphi_{(V_{1},\text{\boldmath$\mathbf{\alpha}$}_{1})}(q_{i})$ , $V=\operatorname{span}(z^{\prime})+V^{\prime}_{2}$ and $V^{\prime}=\operatorname{span}(z^{\prime\prime})+\varphi_{(W,\text{\boldmath$% \mathbf{\alpha}$})}(V^{\prime}_{2})$ , with (5) showing the nonzeroness of the intersection) implies that
$\dim{\bigl(\overline{\mathbb{L}}_{\operatorname{span}(z^{\prime\prime})+% \varphi_{(W,\text{\boldmath$\mathbf{\alpha}$})}(V^{\prime}_{2})}(\varphi_{(W,% \text{\boldmath$\mathbf{\alpha}$})}(\varphi_{(V_{1},\text{\boldmath$\mathbf{% \alpha}$}_{1})}(q_{i})))\bigr)}\leq\dim{\bigl(\overline{\mathbb{L}}_{% \operatorname{span}(z^{\prime})+V^{\prime}_{2}}(\varphi_{(V_{1},\text{% \boldmath$\mathbf{\alpha}$}_{1})}(q_{i}))\bigr)}-1\leq 2t-1\ .$ (6)

Write $V^{(0)}_{2}:=V_{2}$ , $V_{2}^{(1)}:=\varphi_{(W,\text{\boldmath$\mathbf{\alpha}$})}(V^{\prime}_{2})$ , $z^{(0)}=z$ and $z^{(1)}=z^{\prime\prime}$ . Further denote $\varphi^{(0)}=\varphi_{(W,\text{\boldmath$\mathbf{\alpha}$})}\circ\varphi_{(V_% {1},\text{\boldmath$\mathbf{\alpha}$}_{1})}$ , which is a general projection (recall Lemma 32). In the case where all $\varphi_{(V_{1},\text{\boldmath$\mathbf{\alpha}$}_{1})}(q_{i})$ are reducible, so we did not define $W$ , we write $\varphi^{(0)}=\varphi_{(V_{1},\text{\boldmath$\mathbf{\alpha}$}_{1})}$ . Rewrite (6) with the new notation: For each irreducible $\varphi_{(V_{1},\text{\boldmath$\mathbf{\alpha}$}_{1})}(q_{i})$ , $\varphi^{(0)}(q_{i})$ is irreducible and

\dim{\bigl(\overline{\mathbb{L}}_{\operatorname{span}(z^{\prime\prime})+V^{(1)% }_{2}}\bigl(\varphi^{(0)}(q_{i})\bigr)\bigr)}\leq 2t-1\ .

(7)

Repeat this process iteratively on $V_{2}^{(1)}$ and $\left\{{\varphi^{(0)}(q_{i})}\right\}$ by alternating between strengthening the space and projecting the relative Lins of a maximal integral sequence. For each iteration $j$ , we maintain that every irreducible $\varphi^{(j-1)}\circ\dots\circ\varphi^{(0)}(q_{i})$ has

\dim{\bigl(\overline{\mathbb{L}}_{\operatorname{span}(z^{(j)})+V^{(j)}_{2}}% \bigl(\varphi^{(j-1)}\circ\dots\circ\varphi^{(0)}(q_{i})\bigr)\bigr)}\leq 2t-j\ .

After some number $s\leq 2t$ of iterations, we will get to $V_{2}^{(s)}$ , such that all irreducible projections $\varphi^{(s-1)}\circ\dots\circ\varphi^{(0)}(q_{i})$ will be $0$ -close to $V_{2}^{(s)}+\operatorname{span}(z^{(s)})$ . That is,

\varphi^{(s-1)}\circ\dots\circ\varphi^{(0)}(q_{i})\in{\mathbb{K}}[% \operatorname{span}(z^{(s)})+V_{2}^{(s)}]\ ,

for all $i$ .

Once the iterative process terminates after $s\leq 2t$ steps, we must bound the total dimension projected in the final composed projection. In each iteration, we composed two projections (or one if there is no $W^{(j)}$ ): $\varphi_{(W^{(j)},\text{\boldmath$\mathbf{\alpha}$}^{(j)})}$ and $\varphi_{(V^{(j)}_{1},\text{\boldmath$\mathbf{\alpha}$}_{1}^{(j)})}$ . Recall that one stopping condition was that at the final iteration all quadratics became reducible after applying $\varphi_{(V^{(s-1)}_{1},\text{\boldmath$\mathbf{\alpha}$}_{1}^{(s-1)})}$ . In that case we did not define $W^{(s-1)}$ , so we write $W^{(s-1)}=\{\mathbf{0}\}$ and $\varphi_{W^{(j)}}=\text{id}$ . Note that by (4), for every $j$

\dim{\bigl(W^{(j)}\bigr)}\leq 2t^{2}+1\ .

Indeed, $W^{(j)}$ contains at most $2t$ linear forms from each quadratic in the integral sequence (recall that the length of the sequence is at most $t$ ), as well as $z^{\prime(j)}$ . Property 4 of Lemma 39 gives

\dim{\bigl(V^{(j)}_{1}\bigr)}\leq 2B\cdot\left({\dim(V^{(j)}_{2})-\dim(V^{% \prime(j)}_{2})}\right)\ .

Note that $\dim\left({V^{\prime(j)}_{2}}\right)\geq\dim\left({\varphi_{(W,\text{\boldmath% $\mathbf{\alpha}$})}(V^{\prime(j)}_{2})}\right)=\dim\left({V_{2}^{(j+1)}}\right)$ , which is the starting point of the next iteration. Summing over all iterations:

	$\displaystyle\sum_{j=0}^{s-1}{\dim\bigl(V_{1}^{(j)}\bigr)}$	$\displaystyle\leq 2B\cdot\sum_{j=0}^{s-1}\left({\dim(V^{(j)}_{2})-\dim(V^{% \prime(j)}_{2})}\right)$
		$\displaystyle\leq 2B\cdot\sum_{j=0}^{s-1}\left({\dim(V^{(j)}_{2})-\dim(V^{(j+1% )}_{2})}\right)$
		$\displaystyle\leq 2B\cdot\dim(V^{(0)}_{2})$
		$\displaystyle\leq 2Bt\ .$

Therefore the total dimension projected in the final composed projection is at most

\sum_{j=0}^{s-1}\dim{\bigl(W^{(j)}\bigr)}+\sum_{j=0}^{s-1}{\dim\bigl(V_{1}^{(j% )}\bigr)}\leq s(2t^{2}+1)+2Bt\leq 2t(2t^{2}+1)+2t(4t^{2}+3t+3)\leq 17t^{3}\ ,

where the last inequality follows since we assumed $t\geq 2$ . By Lemma 32, we can write the composed projection as

\varphi_{U}=\varphi^{(s-1)}\circ\dots\circ\varphi^{(0)}

for some $U\subset{\mathbb{K}}_{1}[\mathbf{x},z]$ of dimension $\dim(U)\leq 17t^{3}$ .

It remains to handle the reducible forms. After applying the final composed projection, all remaining quadratics $\varphi_{U}(q_{i})$ , which are not in ${\mathbb{K}}[\operatorname{span}(z^{(s)})+V^{(s)}_{2}]$ , are reducible. Namely each is a product of two linear forms. Recall the rank bound for a product of linear forms Theorem 8. Due to our assumption on having small $\mu_{k}$ and Lemma 37 the span of all of these linear factors, denoted $V_{\text{fac}}$ , must satisfy $\dim{\bigl(V_{\text{fac}}\bigr)}\leq t$ .

In conclusion, for all $i$ , $\varphi_{U}(q_{i})\in{\mathbb{K}}[\operatorname{span}(z^{(s)})+V_{\text{fac}}+% V_{2}^{(s)}]$ . From Lemma 33, we have that all $q_{i}$ are contained in a graded algebra with dimension sequence at most $(18t^{3},2t)$ , proving the theorem. $\hfill\blacktriangleleft$

Using this structure lemma, the proof of Theorem 3 becomes simple.

Proof of Theorem 3.

We can assume $r\geq 2$ as otherwise $\left\lfloor r^{1/6}/3\right\rfloor=0$ and the theorem is trivial. Suppose for a contradiction that for some $0\leq k\leq r^{1/6}/3$ it holds that

\mu_{k}(h\cdot\prod_{i=1}^{r}q_{i})<\binom{\left\lfloor r^{1/6}/3\right\rfloor% }{k}\ .

From our structure theorem, Theorem 4, applied for $t=\left\lfloor r^{1/6}/3\right\rfloor$ , we conclude that all the $q_{i}$ ’s are contained in an algebra with a dimension sequence of at most $\left({\frac{18}{3^{3}}r^{1/2},\frac{2}{3}r^{1/6}}\right)$ . Lemma 38 implies that they are contained in a vector space of dimension at most $\frac{324}{729}r+\frac{2}{3}r^{1/6}<r$ . This contradicts the linear independence of the $r$ quadratics $q_{i}$ . Therefore, for all $0\leq k\leq r^{1/6}/3$ :

\mu_{k}(h\cdot\prod_{i=1}^{r}q_{i})\geq\binom{\left\lfloor r^{1/6}/3\right% \rfloor}{k}\ ,

as claimed. $\hfill\blacktriangleleft$

5 Open Problems

While the bound of $\displaystyle\binom{\left\lfloor r^{1/6}/3\right\rfloor}{k}$ in Theorem 3 is the first nontrivial rank bound for a product of linearly independent quadratics that we are aware of, it is still below the conjectured $\binom{r}{k}$ . It would be interesting to improve that bound, or show a stronger upper bound. It is possible that assuming algebraic independence of the quadratics could help.

Another interesting open problem is generalizing the bound to polynomials of larger (even unbounded) degree.

References

[1] John Abbott. Sparse Squares of Polynomials. Mathematics of Computation, 71(237):407–413, 2002. doi:10.1090/S0025-5718-00-01294-1.
[2] Tigran Ananyan and Melvin Hochster. Strength conditions, small subalgebras, and Stillman bounds in degree $\leq 4$ . Transactions of the American Mathematical Society, 373(7):4757–4806, 2020.
[3] Amos Beimel, Francesco Bergadano, Nader H Bshouty, Eyal Kushilevitz, and Stefano Varricchio. Learning functions represented as multiplicity automata. Journal of the ACM (JACM), 47(3):506–530, 2000. doi:10.1145/337244.337257.
[4] Tomer Bincovich. The Rank of Linear Factors of Sparse Polynomials. Master’s thesis, Tel Aviv University, Tel Aviv, Israel, 2017.
[5] Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, and Srikanth Srinivasan. Schur polynomials do not have small formulas if the determinant does not. Computational Complexity, 32(1):3, 2023. doi:10.1007/S00037-023-00236-X.
[6] Xi Chen, Neeraj Kayal, and Avi Wigderson. Partial Derivatives in Arithmetic Complexity and Beyond. Foundations and Trends in Theoretical Computer Science, 6(1-2):1–138, September 2011. doi:10.1561/0400000043.
[7] David Eisenbud. Commutative Algebra with a View Toward Algebraic Geometry, volume 150 of Graduate Texts in Mathematics. Springer, 1995.
[8] Michael A. Forbes. Deterministic divisibility testing via shifted partial derivatives. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science—FOCS 2015, pages 451–465. IEEE Computer Soc., Los Alamitos, CA, 2015. doi:10.1109/FOCS.2015.35.
[9] Michael A Forbes and Amir Shpilka. Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 243–252. IEEE, 2013. doi:10.1109/FOCS.2013.34.
[10] Hervé Fournier, Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan. Lower Bounds for Depth- $4$ Formulas Computing Iterated Matrix Multiplication. SIAM J. Comput., 44(5):1173–1201, 2015. doi:10.1137/140990280.
[11] Ignacio Garcia-Marco, Pascal Koiran, Timothée Pecatte, and Stéphan Thomassé. On the Complexity of Partial Derivatives. In Heribert Vollmer and Brigitte Vallée, editors, 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, Hannover, Germany, March 8-11, 2017, volume 66 of LIPIcs, pages 37:1–37:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPIcs.STACS.2017.37.
[12] Abhibhav Garg, Rafael Oliveira, Shir Peleg, and Akash Kumar Sengupta. Radical Sylvester-Gallai Theorem for Tuples of Quadratics. In 38th Computational Complexity Conference (CCC 2023), volume 264 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1–20:30. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.CCC.2023.20.
[13] Abhibhav Garg, Rafael Oliveira, and Akash Kumar Sengupta. Rank Bounds and PIT for $\Sigma^{3}\Pi\Sigma\Pi^{d}$ Circuits via a Non-linear Edelstein–Kelly Theorem. In Proceedings of the 66th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2025), 2025. FOCS 2025. doi:10.48550/arXiv.2504.14729.
[14] Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Approaching the chasm at depth four. Journal of the ACM (JACM), 61(6):1–16, 2014. doi:10.1145/2629541.
[15] Robin Hartshorne. Algebraic Geometry, volume 52 of Graduate Texts in Mathematics. Springer, 1977. doi:10.1007/978-1-4757-3849-0.
[16] Neeraj Kayal. An exponential lower bound for the sum of powers of bounded degree polynomials. Electron. Colloquium Comput. Complex., TR12-081, 2012. URL: https://eccc.weizmann.ac.il/report/2012/081.
[17] Neeraj Kayal, Nutan Limaye, Chandan Saha, and Srikanth Srinivasan. An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas. SIAM J. Comput., 46(1):307–335, 2017. doi:10.1137/151002423.
[18] Adam Klivans and Amir Shpilka. Learning restricted models of arithmetic circuits. Theory of computing, 2(1):185–206, 2006. doi:10.4086/TOC.2006.V002A010.
[19] Mrinal Kumar and Shubhangi Saraf. The Limits of Depth Reduction for Arithmetic Formulas: It’s All About the Top Fan-In. SIAM J. Comput., 44(6):1601–1625, 2015. doi:10.1137/140999220.
[20] Mrinal Kumar and Shubhangi Saraf. Arithmetic Circuits with Locally Low Algebraic Rank. Theory Comput., 13(1):1–33, 2017. doi:10.4086/TOC.2017.V013A006.
[21] Mrinal Kumar and Shubhangi Saraf. On the power of homogeneous depth 4 arithmetic circuits. SIAM Journal on Computing, 46(1):336–387, 2017. doi:10.1137/140999335.
[22] Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. Superpolynomial lower bounds against low-depth algebraic circuits. Journal of the ACM, 72(4):1–35, 2025. doi:10.1145/3734215.
[23] Noam Nisan. Lower bounds for non-commutative computation. In Proceedings of the twenty-third annual ACM symposium on Theory of computing, pages 410–418, 1991.
[24] Noam Nisan and Avi Wigderson. Lower bounds on arithmetic circuits via partial derivatives. Computational Complexity, 6(3):217–234, 1996. doi:10.1007/BF01294256.
[25] Rafael Oliveira and Akash Kumar Sengupta. Radical Sylvester-Gallai Theorem for Cubics. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 212–220, 2022. doi:10.1109/FOCS54457.2022.00027.
[26] Rafael Oliveira and Akash Kumar Sengupta. Strong Algebras and Radical Sylvester-Gallai Configurations. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 95–105. ACM, 2024. doi:10.1145/3618260.3649617.
[27] Shir Peleg and Amir Shpilka. Polynomial time deterministic identity testing algorithm for $\Sigma^{[3]}\Pi\Sigma\Pi^{[2]}$ circuits via Edelstein–Kelly type theorem for quadratic polynomials. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 259–271, 2021. doi:10.1145/3406325.3451013.
[28] Shir Peleg and Amir Shpilka. A generalized Sylvester–Gallai-type theorem for quadratic polynomials. In Forum of Mathematics, Sigma, volume 10, page e112. Cambridge University Press, 2022.
[29] Ran Raz. Separation of multilinear circuit and formula size. Theory of Computing, 2(1):121–135, 2006. doi:10.4086/TOC.2006.V002A006.
[30] Ran Raz and Amir Shpilka. Deterministic polynomial identity testing in non-commutative models. Computational Complexity, 14(1):1–19, 2005. doi:10.1007/S00037-005-0188-8.
[31] Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity. GitHub repository, 2021. URL: https://github.com/dasarpmar/lowerbounds-survey.
[32] Andrzej Schinzel and Umberto Zannier. On the number of terms of a power of a polynomial. Rendiconti Lincei, 20(1):95–98, 2009.
[33] Nir Shalmon and Amir Shpilka. Partial Derivative Complexity of a Product of Linearly Independent Quadratics. Electron. Colloquium Comput. Complex., TR26-065, 2026. URL: https://eccc.weizmann.ac.il/report/2026/065.
[34] Amir Shpilka. Sylvester-Gallai type theorems for quadratic polynomials. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 1203–1214, 2019. doi:10.1145/3313276.3316341.
[35] Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends® in Theoretical Computer Science, 5(3–4):207–388, 2010. doi:10.1561/0400000039.

[bib.bib1] [1] John Abbott. Sparse Squares of Polynomials. Mathematics of Computation, 71(237):407–413, 2002. doi:10.1090/S0025-5718-00-01294-1.

[bib.bib2] [2] Tigran Ananyan and Melvin Hochster. Strength conditions, small subalgebras, and Stillman bounds in degree $\leq 4$ . Transactions of the American Mathematical Society, 373(7):4757–4806, 2020.

[bib.bib3] [3] Amos Beimel, Francesco Bergadano, Nader H Bshouty, Eyal Kushilevitz, and Stefano Varricchio. Learning functions represented as multiplicity automata. Journal of the ACM (JACM), 47(3):506–530, 2000. doi:10.1145/337244.337257.

[bib.bib4] [4] Tomer Bincovich. The Rank of Linear Factors of Sparse Polynomials. Master’s thesis, Tel Aviv University, Tel Aviv, Israel, 2017.

[bib.bib5] [5] Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, and Srikanth Srinivasan. Schur polynomials do not have small formulas if the determinant does not. Computational Complexity, 32(1):3, 2023. doi:10.1007/S00037-023-00236-X.

[bib.bib6] [6] Xi Chen, Neeraj Kayal, and Avi Wigderson. Partial Derivatives in Arithmetic Complexity and Beyond. Foundations and Trends in Theoretical Computer Science, 6(1-2):1–138, September 2011. doi:10.1561/0400000043.

[bib.bib7] [7] David Eisenbud. Commutative Algebra with a View Toward Algebraic Geometry, volume 150 of Graduate Texts in Mathematics. Springer, 1995.

[bib.bib8] [8] Michael A. Forbes. Deterministic divisibility testing via shifted partial derivatives. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science—FOCS 2015, pages 451–465. IEEE Computer Soc., Los Alamitos, CA, 2015. doi:10.1109/FOCS.2015.35.

[bib.bib9] [9] Michael A Forbes and Amir Shpilka. Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 243–252. IEEE, 2013. doi:10.1109/FOCS.2013.34.

[bib.bib10] [10] Hervé Fournier, Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan. Lower Bounds for Depth- $4$ Formulas Computing Iterated Matrix Multiplication. SIAM J. Comput., 44(5):1173–1201, 2015. doi:10.1137/140990280.

[bib.bib11] [11] Ignacio Garcia-Marco, Pascal Koiran, Timothée Pecatte, and Stéphan Thomassé. On the Complexity of Partial Derivatives. In Heribert Vollmer and Brigitte Vallée, editors, 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, Hannover, Germany, March 8-11, 2017, volume 66 of LIPIcs, pages 37:1–37:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPIcs.STACS.2017.37.

[bib.bib12] [12] Abhibhav Garg, Rafael Oliveira, Shir Peleg, and Akash Kumar Sengupta. Radical Sylvester-Gallai Theorem for Tuples of Quadratics. In 38th Computational Complexity Conference (CCC 2023), volume 264 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1–20:30. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.CCC.2023.20.

[bib.bib13] [13] Abhibhav Garg, Rafael Oliveira, and Akash Kumar Sengupta. Rank Bounds and PIT for $\Sigma^{3}\Pi\Sigma\Pi^{d}$ Circuits via a Non-linear Edelstein–Kelly Theorem. In Proceedings of the 66th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2025), 2025. FOCS 2025. doi:10.48550/arXiv.2504.14729.

[bib.bib14] [14] Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Approaching the chasm at depth four. Journal of the ACM (JACM), 61(6):1–16, 2014. doi:10.1145/2629541.

[bib.bib15] [15] Robin Hartshorne. Algebraic Geometry, volume 52 of Graduate Texts in Mathematics. Springer, 1977. doi:10.1007/978-1-4757-3849-0.

[bib.bib16] [16] Neeraj Kayal. An exponential lower bound for the sum of powers of bounded degree polynomials. Electron. Colloquium Comput. Complex., TR12-081, 2012. URL: https://eccc.weizmann.ac.il/report/2012/081.

[bib.bib17] [17] Neeraj Kayal, Nutan Limaye, Chandan Saha, and Srikanth Srinivasan. An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas. SIAM J. Comput., 46(1):307–335, 2017. doi:10.1137/151002423.

[bib.bib18] [18] Adam Klivans and Amir Shpilka. Learning restricted models of arithmetic circuits. Theory of computing, 2(1):185–206, 2006. doi:10.4086/TOC.2006.V002A010.

[bib.bib19] [19] Mrinal Kumar and Shubhangi Saraf. The Limits of Depth Reduction for Arithmetic Formulas: It’s All About the Top Fan-In. SIAM J. Comput., 44(6):1601–1625, 2015. doi:10.1137/140999220.

[bib.bib20] [20] Mrinal Kumar and Shubhangi Saraf. Arithmetic Circuits with Locally Low Algebraic Rank. Theory Comput., 13(1):1–33, 2017. doi:10.4086/TOC.2017.V013A006.

[bib.bib21] [21] Mrinal Kumar and Shubhangi Saraf. On the power of homogeneous depth 4 arithmetic circuits. SIAM Journal on Computing, 46(1):336–387, 2017. doi:10.1137/140999335.

[bib.bib22] [22] Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. Superpolynomial lower bounds against low-depth algebraic circuits. Journal of the ACM, 72(4):1–35, 2025. doi:10.1145/3734215.

[bib.bib23] [23] Noam Nisan. Lower bounds for non-commutative computation. In Proceedings of the twenty-third annual ACM symposium on Theory of computing, pages 410–418, 1991.

[bib.bib24] [24] Noam Nisan and Avi Wigderson. Lower bounds on arithmetic circuits via partial derivatives. Computational Complexity, 6(3):217–234, 1996. doi:10.1007/BF01294256.

[bib.bib25] [25] Rafael Oliveira and Akash Kumar Sengupta. Radical Sylvester-Gallai Theorem for Cubics. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 212–220, 2022. doi:10.1109/FOCS54457.2022.00027.

[bib.bib26] [26] Rafael Oliveira and Akash Kumar Sengupta. Strong Algebras and Radical Sylvester-Gallai Configurations. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 95–105. ACM, 2024. doi:10.1145/3618260.3649617.

[bib.bib27] [27] Shir Peleg and Amir Shpilka. Polynomial time deterministic identity testing algorithm for $\Sigma^{[3]}\Pi\Sigma\Pi^{[2]}$ circuits via Edelstein–Kelly type theorem for quadratic polynomials. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 259–271, 2021. doi:10.1145/3406325.3451013.

[bib.bib28] [28] Shir Peleg and Amir Shpilka. A generalized Sylvester–Gallai-type theorem for quadratic polynomials. In Forum of Mathematics, Sigma, volume 10, page e112. Cambridge University Press, 2022.

[bib.bib29] [29] Ran Raz. Separation of multilinear circuit and formula size. Theory of Computing, 2(1):121–135, 2006. doi:10.4086/TOC.2006.V002A006.

[bib.bib30] [30] Ran Raz and Amir Shpilka. Deterministic polynomial identity testing in non-commutative models. Computational Complexity, 14(1):1–19, 2005. doi:10.1007/S00037-005-0188-8.

[bib.bib31] [31] Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity. GitHub repository, 2021. URL: https://github.com/dasarpmar/lowerbounds-survey.

[bib.bib32] [32] Andrzej Schinzel and Umberto Zannier. On the number of terms of a power of a polynomial. Rendiconti Lincei, 20(1):95–98, 2009.

[bib.bib33] [33] Nir Shalmon and Amir Shpilka. Partial Derivative Complexity of a Product of Linearly Independent Quadratics. Electron. Colloquium Comput. Complex., TR26-065, 2026. URL: https://eccc.weizmann.ac.il/report/2026/065.

[bib.bib34] [34] Amir Shpilka. Sylvester-Gallai type theorems for quadratic polynomials. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 1203–1214, 2019. doi:10.1145/3313276.3316341.

[bib.bib35] [35] Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends® in Theoretical Computer Science, 5(3–4):207–388, 2010. doi:10.1561/0400000039.

Partial Derivative Complexity of a Product of Linearly Independent Quadratics

Abstract

Keywords and phrases:

Category:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Question 1.

Conjecture 2 ([5, Conjecture 47]).

1.1 Main Result and Technical Contributions

Theorem 3 (Main theorem).

Theorem 4 (Structure theorem).

1.2 High-level proof ideas

Low variable support example

Observation 5.

Generalizing to arbitrary quadratics

1.3 Related work

2 Preliminaries

2.1 The Partial Derivative Measure

Definition 6.

Lemma 7.

Theorem 8.

2.2 The Jacobian criterion of [5]

Definition 9.

Lemma 10 (Jacobian criterion for μk).

Proof.

2.3 Regular Sequences and Lower Bounds

Definition 11 (Nonsingular (smooth) point).

Theorem 12 (Nonsingular locus is dense open [15, Theorem 5.3]).

Definition 13 (Nonzerodivisor).

Definition 14 (Regular sequence).

Definition 15 (Depth of an ideal).

Definition 16 (Cohen–Macaulay ring).

Theorem 17.

Corollary 18 (Radical regular sequence gives μk lower bounds).

Proof.

2.4 Wide Spaces

Definition 19 (Rank and Lin⁡(⋅) for quadratics).

Lemma 20 ([28, Fact 2.15]).

Definition 21 (Wide spaces, closeness, relative linear spaces, and integral sequences).

Theorem 22 ([2, Theorem 4.14]).

Corollary 23.

Proof.

Lemma 24 ([12, Lemma 63]).

▶ Remark 25.

Lemma 26 ([12, Lemma 64]).

3 General Projections

3.1 Definition and Basic Properties

Definition 27 (Projection map).

▶ Remark 28.

Definition 29 (General projection).

▶ Remark 30.

Proposition 31 ([25, Proposition 2.6]).

Lemma 32 (General projections are composable).

Lemma 33 (Pullback of a graded algebra under a general projection).

Corollary 34.

3.2 Rank and Distance Under General Projections

Lemma 35 (Projections do not increase distances).

Lemma 36.

Lemma 37 (Dimension of partials does not increase under projections).

4 Main Proof

4.1 Roadmap of the proof

4.2 Key Lemmas

Lemma 38.

Lemma 39 (Strengthening).

Proof.

Property 1

Property 2

Property 3

Property 4

Lemma 40 (Integral Sequence Bound).

Proof.

4.3 Proof of Theorem 4

Proof of Theorem 4.

Lemma 10 (Jacobian criterion for $\mu_{k}$ ).

Corollary 18 (Radical regular sequence gives $\mu_{k}$ lower bounds).

Definition 19 (Rank and $\operatorname{Lin}(\cdot)$ for quadratics).

$\blacktriangleright$ Remark 25.

$\blacktriangleright$ Remark 28.

$\blacktriangleright$ Remark 30.