# Robust Sylvester-Gallai type theorem for quadratic polynomials

Shir Peleg  The Blavatnik School of Computer Science, Tel Aviv University, Tel
Aviv, Israel. Emails<EMAIL_ADDRESS><EMAIL_ADDRESS>The
research leading to these results has received funding from the Israel Science
Foundation (grant number 514/20) and from the Len Blavatnik and the Blavatnik
Family foundation.  Amir Shpilka11footnotemark: 1

###### Abstract

In this work we extend the robust version of the Sylvester-Gallai theorem,
obtained by Barak, Dvir, Wigderson and Yehudayoff, and by Dvir, Saraf and
Wigderson, to the case of quadratic polynomials. Specifically, we prove that
if ${\mathcal{Q}}\subset\mathbb{C}[x_{1}.\ldots,x_{n}]$ is a finite set,
$|{\mathcal{Q}}|=m$, of irreducible quadratic polynomials that satisfy the
following condition:

  * •

There is $\delta>0$ such that for every $Q\in{\mathcal{Q}}$ there are at least
$\delta m$ polynomials $P\in{\mathcal{Q}}$ such that whenever $Q$ and $P$
vanish then so does a third polynomial in ${\mathcal{Q}}\setminus\\{Q,P\\}$,

then $\dim(\operatorname{span}\\{{{\mathcal{Q}}}\\})=\poly(1/\delta)$.

The work of Barak et al. and Dvir et al. studied the case of linear
polynomials and proved an upper bound of $O(1/\delta)$ on the dimension (in
the first work an upper bound of $O(1/\delta^{2})$ was given, which was
improved to $O(1/\delta)$ in the second work).

###### Contents

  1. 1 Introduction
    1. 1.1 Proof idea
    2. 1.2 Discussion
  2. 2 Preliminaries
    1. 2.1 Notation and basic facts
    2. 2.2 Rank of quadratic polynomials
    3. 2.3 Projection mapping
  3. 3 Robust-SG theorems in $\mathbb{C}^{n}$
  4. 4 Strengthening Case (iii) of Theorem 1.13
  5. 5 Robust Sylvester-Gallai theorem for quadratic polynomials.
    1. 5.1 Poof of Claim 5.6
    2. 5.2 Proof of Claim 5.7
    3. 5.3 Proof of Claim 5.8
  6. A Appendix

##  1 Introduction

In this paper we prove a robust version of a result of [42]: Let
${\mathcal{T}}\subset\mathbb{C}[x_{1},\ldots,x_{n}]$ be a finite set of
polynomials. We say that
$Q_{1}({{\mathbf{x}}}),Q_{2}({{\mathbf{x}}})\in{\mathcal{Q}}$ satisfy the
_Polynomial Sylvester-Gallai condition_ (PSG-condition for short) if there is
a third polynomial $Q_{3}({{\mathbf{x}}})\in{\mathcal{Q}}$ such that
$Q_{3}({{\mathbf{x}}})$ vanishes whenever $Q_{1}({{\mathbf{x}}})$ and
$Q_{2}({{\mathbf{x}}})$ vanish. We prove that if
${\mathcal{T}}\subset\mathbb{C}[x_{1},\ldots,x_{n}]$ is a finite set
containing only irreducible quadratic polynomials, such that for every
$Q\in{\mathcal{T}}$ a $\delta$ fraction of the polynomials in ${\mathcal{T}}$
satisfy the PSG-condition with $Q$, then
$\dim\left(\operatorname{span}\\{{{\mathcal{T}}}\\}\right)=\poly(1/\delta)$.

The motivation for proving this result, besides its own appeal, is two fold: a
similar theorem played an important role in the polynomial identity testing
(PIT for short) problem for small depth algebraic circuits, one of the
fundamental open problems in theoretical computer science, see [37]; and it is
also related to a long line of work extending and generalizing the original
Sylvester-Gallai theorem [33, 20] such as the results in [7, 35, 10, 3]. In
particular, our result builds and generalizes a result of [4, 12], that can be
viewed as proving an analogous claim for the case of degree-$1$ polynomials.
Such results are useful in discrete geometry [4, 12], in the study of locally
correctable codes, for reconstruction of certain depth-$3$ circuits [41, 29,
43] and more. See the survey of Dvir on incidence geometry for some
applications of Sylvester-Gallai type theorems [14].

We next give background on the Sylvester-Gallai theorem, and some of its
variants, and then discuss the connection to the polynomial identity testing
problem.

#### Sylvester-Gallai type theorems:

The Sylvester-Gallai theorem (SG-theorem) asserts that given a set
$S=\left\\{{{\mathbf{v}}}_{1},\ldots,{{\mathbf{v}}}_{m}\right\\}\subset\mathbb{R}^{n}$
such that $S$ is not contained in a line, there must be a line that contains
exactly two points from $S$. It was first conjectured by Sylvester in 1893
[48] and then proved, independently, by Melchior in 1941 [33] and Gallai [20]
in 1943 (in an answer to the same question posed by Erdös, who was unaware of
Melchior’s result [15]). There are many extensions and generalizations of the
theorem. We shall state a few that are related to this work. It is also
helpful to think of the contra-positive statement. We say that a set of points
is a Sylvester-Gallai configuration (SG-configuration for short) if every line
that intersects the set at two points, must contain at least three points from
the set. Thus, an SG-configuration in $\mathbb{R}^{n}$ must be colinear.

In [40] Serre, aware that the original formulation of the theorem is not true
over $\mathbb{C}$ asked “Is there a nonplanar version of the Sylvester-Gallai
configuration over the field of complex numbers?” Kelly proved that the answer
is no, i.e. that every finite set of points in $\mathbb{C}^{n}$ satisfying the
SG-condition is planar [27]. Edelstein and Kelly proved a colorful variant of
the problem: if three finite sets of points in $\mathbb{R}^{n}$ satisfy that
every line passing through points from two different sets also contains a
point from the third set, then, the points belong to a three-dimensional
affine space. This result can be extended to any constant number of sets. Many
more extensions and generalizations of the SG-theorem are known, e.g. [25,
10]. The survey by Borwein and Moser [5] is a good resource on the SG-Theorem
and some of the different variants that have been studied in the past.

More recently, Barak et al. [4] and Dvir, Saraf and Wigderson [12], motivated
by questions on locally decodable codes and construction of rigid matrices,
proved a _robust_ (or fractional) version of the SG-theorem:

######  Definition 1.1 ($\delta$-SG configuration).

We say that a set of points $v_{1},\ldots,v_{m}\in\mathbb{C}^{n}$ is a
$\delta$-SG configuration if for every $i\in[m]$ there exists at least
$\delta(m-1)$ values of $j\in[m]$ such that the line through $v_{i},v_{j}$
contains a third point in the set.

######  Theorem 1.2 (Theorem 1.9 of [12]).

Let $V=\\{v_{1},\ldots,v_{m}\\}\subset\mathbb{C}^{n}$ be a $\delta$-SG
configuration. Then
$\dim(\operatorname{span}\\{{v_{1},\ldots,v_{m}}\\})\leq\frac{12}{\delta}+1$.

#### Algebraic generalizations of Sylvester-Gallai type theorems:

Although the Sylvester-Gallai theorem and Theorem 1.2 are formulated in the
setting of discrete geometry, there is a very natural algebraic formulation:
If a finite set of pairwise linearly independent vectors,
${\mathcal{S}}\subset\mathbb{C}^{n}$, has the property that every two vectors
span a third vector in the set, then the dimension of ${\mathcal{S}}$ is at
most $3$. The proof is immediate from Kelly’s theorem: pick a subspace $H$ of
codimension $1$, which is in general position with respect to the vectors in
${\mathcal{S}}$. The intersection points
$p_{i}=H\cap\operatorname{span}\\{{s_{i}}\\}$, for $s_{i}\in{\mathcal{S}}$,
satisfy the SG-condition over $\mathbb{C}$. Therefore, $\dim(S)\leq 3$. An
equivalent formulation, in the case of linear functions, is the following: If
a finite set of pairwise linearly independent linear forms,
${\mathcal{L}}\subset\mathbb{C}[{x}_{1},\ldots,{x}_{n}]$, has the property
that for every two forms $\ell_{i},\ell_{j}\in{\mathcal{L}}$ there is a third
$\ell_{k}\in{\mathcal{L}}$, such that $\ell_{k}=0$ whenever
$\ell_{i}=\ell_{j}=0$, then the linear dimension of ${\mathcal{L}}$ is at most
$3$. To see the equivalence note that it must be the case that
$\ell_{k}\in\operatorname{span}\\{{\ell_{i},\ell_{j}}\\}$ and thus the
coefficient vectors of the forms in the set satisfy the condition for the
(vector version of the) SG-theorem, and the bound on the dimension follows.
Observe that the last example shows that in the case of linear functions the
PSG-condition and the SG-condition are equivalent. The last formulation can
now be generalized to higher degree polynomials. In particular, the following
conjecture was raised by Gupta [24].

######  Definition 1.3 (PSG-configuration).

Let ${\mathcal{T}}\subset\mathbb{C}[x_{1},\ldots,x_{n}]$ be a set of
polynomials. We say that $Q_{1},Q_{2}\in{\mathcal{T}}$ satisfy the _Polynomial
Sylvester-Gallai condition_ (PSG-condition for short) if there is a third
polynomial $Q_{3}({{\mathbf{x}}})\in{\mathcal{T}}$ such that $Q_{3}$ vanishes
whenever $Q_{1}$ and $Q_{2}$ vanish.

We say that a set ${\mathcal{T}}$ is a PSG-configuration if every two
polynomials $Q_{1},Q_{2}\in{\mathcal{T}}$ satisfy the PSG-condition.

######  Problem 1.4 (Conjecture 2 of [24]).

There is a function $\lambda:\mathbb{N}\to\mathbb{N}$ such that for any finite
set ${\mathcal{T}}\subset\mathbb{C}[{x}_{1},\ldots,{x}_{n}]$ of pairwise
linearly independent and irreducible polynomials, of degree at most $r$, that
satisfy the PSG-condition, it holds that the _algebraic rank_ of
${\mathcal{T}}$ is at most $\lambda(r)$.

This problem was answered affirmatively, with a stronger conclusion, in the
case of quadratic polynomials ($r=2$) in [42].

######  Theorem 1.5 (Theorem 1.7 of [42]).

There is a constant $\lambda$ such that the following holds for every
$n\in\mathbb{N}$. Let ${\mathcal{T}}\subset\mathbb{C}[{x}_{1},\ldots,{x}_{n}]$
consist of homogeneous quadratic polynomials, such that each
$Q\in{\mathcal{T}}$ is either irreducible or a square of a linear function. If
${\mathcal{T}}$ satisfies the PSG-condition then
$\dim\left(\operatorname{span}\\{{{\mathcal{T}}}\\}\right)\leq\lambda$.

Motivated by applications for the polynomial identity testing problem, Gupta
[24] and Beecken, Mittmann and Saxena [6] also raised the following colorful
variant, which generalizes the Edelstein-Kelly theorem.

######  Conjecture 1.6 (Conjecture 30 of [24]).

There is a function $\lambda:\mathbb{N}\to\mathbb{N}$ such that the following
holds for every $r,n\in\mathbb{N}$. Let $R,B,G$ be finite disjoint sets of
pairwise linearly independent, irreducible, homogeneous polynomials in
$\mathbb{C}[x_{1},\ldots,x_{n}]$ of degree $\leq r$ such that for every pair
$Q_{1},Q_{2}$ from distinct sets there is a $Q_{3}$ in the remaining set so
that whenever $Q_{1}$ and $Q_{2}$ vanish then also $Q_{3}$ vanishes. Then the
algebraic rank of $(R\cup B\cup G)$ is at most $\lambda(r)$.

This problem was also answered affirmatively, with the same stronger
conclusion, in [42], for the case of quadratic polynomials.

######  Theorem 1.7 (Theorem 1.8 of [42]).

There is a constant $\lambda$ such that the following holds for every
$n\in\mathbb{N}$. Let ${\mathcal{T}}_{1},{\mathcal{T}}_{2}$ and
${\mathcal{T}}_{3}$ be finite sets of homogeneous quadratic polynomials over
$\mathbb{C}$ satisfying the following properties:

  * •

Each $Q\in\cup_{i}{\mathcal{T}}_{i}$ is either irreducible or a square of a
linear function.

  * •

No two polynomials are multiples of each other (i.e., every pair is linearly
independent).

  * •

For every two polynomials $Q_{1}$ and $Q_{2}$ from distinct sets there is a
polynomial $Q_{3}$ in the third set so that whenever $Q_{1}$ and $Q_{2}$
vanish then also $Q_{3}$ vanishes.

Then $\dim\left(\operatorname{span}\\{{\cup_{i}{\mathcal{T}}_{i}}\\}\right)$
has dimension $O(1)$.

#### PIT and Sylvester-Gallai type theorems:

The PIT problem asks to give a deterministic algorithm that given an
arithmetic circuit as input determines whether it computes the identically
zero polynomial. The circuit can be given either via a description of its
graph of computation (white-box model) or via oracle access to the polynomial
that it computes (black-box model). This is a fundamental problem in
theoretical computer science that has received a lot of attention from
researchers in the last two decades. Besides of being a natural and elegant
question, the PIT problem is important due its connections to lower bounds for
arithmetic circuits (hardness-randomness tradeoffs) [26, 1, 28, 13, 8]; its
relation to other derandomization problems such as finding perfect matching
deterministically, in parallel, [16, 46], derandomizing factoring algorithms
[32], derandomization questions in geometric complexity theory [34, 18]; its
role in algebraic natural proofs [19, 22]. In particular, PIT appears to be
the most general algebraic derandomization problem. For more on the PIT
problem see [47, 38, 39, 17]. For a survey of algebraic hardness-randomness
tradeoffs see [31].

A beautiful line of work has shown that deterministic algorithms for the PIT
problem for homogeneous depth-$4$ circuits or for depth-$3$ circuits would
lead to deterministic algorithms for general circuits [2, 21]. This makes
small depth circuits extremely interesting for the PIT problem. This is also
the setting where Sylvester-Gallai type theorems play an important role. The
relation between (colored-versions of the) SG-theorem and deterministic PIT
algorithms for depth-$3$ circuits was observed in [11]. The work of [30, 45]
used this relation to obtain polynomial- and quasi-polynomial-time PIT
algorithms for depth-$3$ circuits, depending on the characteristic. Currently,
the best algorithm for PIT of depth-$3$ circuits was obtained through a
different yet highly related approach in [44]. As the SG-theorem played such
an important role in derandomizing PIT for depth-$3$ circuits, it was asked
whether a similar approach could work for depth-$4$ circuits. This motivated
[6, 24] to raise Problem 1.4 and Conjecture 1.6. In [37] we gave a positive
answer to Conjecture 1.6 for the case of degree-$2$ polynomials ($r=2$).
Interestingly, Theorem 1.2 played a crucial role in the proof, as well as in
the proofs of [42, 36]. Studying the proofs of [42, 36, 37] leads to the
conclusion that in order to solve Problem 1.4 and Conjecture 1.6 for degrees
larger than $2$, we must first obtain a result analogous to Theorem 1.2.

#### Our results:

In this work we are able to prove an analog of Theorem 1.2 for quadratic
polynomials. We hope that this result will lead to an extension of the works
[42, 36, 37] to higher degree polynomials.

######  Definition 1.8 ($\delta$-PSG-configuration).

Let ${\mathcal{Q}}\subset\mathbb{C}[x_{1},\ldots,x_{n}]$ be a set of
polynomials. We say that a finite set of polynomials ${\mathcal{Q}}$ is a
$\delta$-PSG configuration if for every $Q\in{\mathcal{Q}}$ there are at least
$\delta\cdot|{\mathcal{Q}}|$ polynomials $P\in{\mathcal{Q}}$ such that $Q$ and
$P$ satisfy the PSG condition.

######  Theorem 1.9.

Let ${\mathcal{Q}}\subset\mathbb{C}[x_{1},\ldots,x_{n}]$ a finite set of
irreducible quadratic polynomials. If ${\mathcal{Q}}$ is a $\delta$-PSG
configuration then
$\dim(\operatorname{span}\\{{{\mathcal{Q}}}\\})=O(1/\delta^{16})$.

######  Remark 1.10.

The same conclusion holds even if we allow irreducible polynomials of degree
at most $2$ (i.e. if we allow linear functions). The proof is similar in
nature, with more case analysis, and so we decided to omit it.

Note that this is robust version of Theorem 1.5 in the same sense that Theorem
1.2 is a robust version of the SG-theorem.

######  Remark 1.11.

While the result in Theorem 1.2 tight (up to the constant in the big Oh), we
do not believe that the result of Theorem 1.9 is tight. In particular, we
believe that the upper bound should be $O(1/\delta)$.

######  Remark 1.12.

After this work was completed, we learned from Garg, Oliviera and Sengupta
that they have independently obtained the same result and are in the process
of writing it [23]. Both proofs heavily rely on case analysis and are similar
in nature with small technical differences. The main difference between the
proofs is that we relied on Theorem 1.10 of [42] (see Theorem 1.13) while they
proved a generalization of that theorem.

###  1.1 Proof idea

To explain the proof we will use some notation that we define in Section 2.1.
For example, $\left\langle{\cdot}\right\rangle$ denotes an ideal,
$\sqrt{\left\langle{\cdot}\right\rangle}$ denotes the radical of the ideal,
and $\mathbb{C}[V]_{2}$ denotes the space of all quadratic polynomials defined
only using the linear forms in $V$.

At the heart of all previous work lies an algebraic theorem, classifying the
cases in which a quadratic polynomial vanishes when two other quadratics
vanish (actually, for [36, 37] a more general result was needed - a
characterization of the different cases in which a product of quadratic
polynomials vanishes whenever two other quadratics vanish).

######  Theorem 1.13 (Theorem 1.10 of [42]).

Let $A,B$ and $C$ be $n$-variate, homogeneous, quadratic polynomials, over
$\mathbb{C}$, such that whenever $A$ and $B$ vanish then so does $C$. Then,
one of the following cases must hold:

  1. (i)

$C$ is in the linear span of $A$ and $B$.

  2. (ii)

There exists a non trivial linear combination of the form $\alpha A+\beta
B=\ell^{2}$ for some linear form $\ell$.

  3. (iii)

There exist two linear forms $\ell_{1}$ and $\ell_{2}$ such that when setting
$\ell_{1}=\ell_{2}=0$ we get that $A$ and $B$ (and consequently $C$) vanish.

The high level idea in the proof of Theorem 1.5 (which was generalized in [36,
37]), includes two steps; The first step constructs a linear space of linear
forms $V$, and a subset ${\mathcal{J}}\subset Q$, both of constant dimension
such that a vast majority of the polynomials in ${\mathcal{Q}}$ are in
$\operatorname{span}\\{{{\mathcal{J}},{\mathcal{Q}}\cap\left\langle{V}\right\rangle}\\}$.111
[42] had different notations, and $|{\mathcal{J}}|=1$. Implementing this idea
requires a lot of case analysis, according to Theorem 1.13. In the second step
the dimension of ${\mathcal{Q}}\cap\left\langle{V}\right\rangle$ is upper
bounded.

The idea outlined above heavily relies on the fact that when $\delta=1$, the
set ${\mathcal{Q}}\cap\left\langle{V}\right\rangle$ is a PSG-configuration in
itself. Indeed, let
$Q_{1},Q_{2}\in{\mathcal{Q}}\cap\left\langle{V}\right\rangle$. When $\delta=1$
it follows that there is $Q_{3}\in{\mathcal{Q}}$ such that
$Q_{3}\in\sqrt{\left\langle{Q_{1},Q_{2}}\right\rangle}\subseteq\left\langle{V}\right\rangle$.
In order to bound the dimension of
${\mathcal{Q}}\cap\left\langle{V}\right\rangle$, [42] "projected" $V$ to a one
dimensional space $\operatorname{span}\\{{z}\\}$ (where $z$ is a new
variable). Every polynomial
$Q_{i}\in{\mathcal{Q}}\cap\left\langle{V}\right\rangle$ is mapped to a
polynomial of the form $z\cdot\ell_{i}$, for some linear form $\ell_{i}$.
Then, it is proved that the $\ell_{i}$’s form an SG-condition.222The reader
should take note that this is a very high-level simplification of one part in
the proof. For more details see the ”easy-case” in [36, 37].

This technique fails when $\delta\in(0,1)$. First, we cannot expect to prove
that ${\mathcal{Q}}\cap\left\langle{V}\right\rangle$ is a
$\delta^{\prime}$-PSG configuration by itself (even when we allow smaller, yet
fixed, $\delta^{\prime}\leq\delta$). For example, since $\delta<1$, it may be
the case that (many polynomials)
$Q\in{\mathcal{Q}}\cap\left\langle{V}\right\rangle$ have _all_ of their
neighbors outside ${\mathcal{Q}}\cap\left\langle{V}\right\rangle$.
Furthermore, even if we knew that
${\mathcal{Q}}\cap\left\langle{V}\right\rangle$ is a $\delta^{\prime}$-PSG
configuration, then it is not clear that by following the lines of [42] and
mapping $\left\langle{V}\right\rangle$ to $\operatorname{span}\\{{z}\\}$, the
resulting $\ell_{i}$s, form a $\delta^{\prime}$-PSG configurations. The reason
for that is a bit subtle: note that it may be the case that many polynomials
$Q\in{\mathcal{Q}}\cap\left\langle{V}\right\rangle$ were mapped to
$\operatorname{span}\\{{z^{2}}\\}$. Thus, it may be the case that all the
neighbors of some $z\cdot\ell$ are in $\operatorname{span}\\{{z^{2}}\\}$,
which gives us no information at all about $\ell$. In contrast, in [42], since
$\delta=1$, we could get information about $\ell$ by its interaction with
polynomials not in $\operatorname{span}\\{{z^{2}}\\}$.

In order to overcome these issues, we needed to develop new techniques, and
improve the characterization given in Theorem 1.13(iii) (see 4.10). Next, we
present the outline of the proof in more details.

We start with the same line of constructing a linear space of linear forms
$V$, and a subset ${\mathcal{J}}\subset Q$, both of dimension
$O(\mathsf{poly}(\frac{1}{\delta}))$ such that
${\mathcal{Q}}\subseteq\operatorname{span}\\{{{\mathcal{J}},\left\langle{V}\right\rangle}\\}$.
We partition ${\mathcal{Q}}$ to four sets:
${\mathcal{C}}_{[V]}={\mathcal{Q}}\cap\mathbb{C}[V]_{2}$;
${\mathcal{C}}_{\left\langle{V}\right\rangle}=({\mathcal{Q}}\cap\left\langle{V}\right\rangle)\setminus{\mathcal{C}}_{[V]}$;
${\mathcal{J}}_{[V]}={\mathcal{Q}}\cap\operatorname{span}\\{{{\mathcal{J}}\cup
C[V]_{2}}\\}$; and the remaining set
${\mathcal{J}}_{\left\langle{V}\right\rangle}={\mathcal{Q}}\cap\operatorname{span}\\{{{\mathcal{J}}\cup\left\langle{V}\right\rangle}\\}\setminus{\mathcal{J}}_{[V]}$.
We already know that $\dim({\mathcal{C}}_{[V]}\cup{\mathcal{J}}_{[V]})$ is
small, so we only have to bound the dimension of
${\mathcal{C}}_{\left\langle{V}\right\rangle}\cup{\mathcal{J}}_{\left\langle{V}\right\rangle}$.

Let us focus on ${\mathcal{C}}_{\left\langle{V}\right\rangle}$. We would like
to prove that we can add a few linear functions to $V$ to get a subspace $U$
such that
${\mathcal{C}}_{\left\langle{V}\right\rangle}\subset\mathbb{C}[U]_{2}$. Let
$P\in{\mathcal{C}}_{\left\langle{V}\right\rangle}$. First we consider the case
that many of $P$’s neighbors (i.e. those polynomials with which $P$ satisfies
the PSG-condition) are in
${\mathcal{C}}_{[V]}\cup{\mathcal{C}}_{\left\langle{V}\right\rangle}$. To
handle this case we strengthen Theorem 1.13(iii) and use it to show that if
$Q\in{\mathcal{C}}_{[V]}$ is a neighbor of $P$ then the polynomial
$Q^{\prime}\in\sqrt{\left\langle{P,Q}\right\rangle}$ is unique (see 4.4). This
means that by moving the linear functions on which $P$ depends to $U$, we move
many polynomials from ${\mathcal{C}}_{\left\langle{V}\right\rangle}$ to
$\mathbb{C}[V+U]_{2}$.

Next we consider the case where $P$ has “many” neighbors in
${\mathcal{J}}_{[V]}\cup{\mathcal{J}}_{\left\langle{V}\right\rangle}$. To
handle this case we first prove that $P$ can only satisfy theorem 1.13(i) with
polynomials in
${\mathcal{J}}_{[V]}\cup{\mathcal{J}}_{\left\langle{V}\right\rangle}$. We
prove that under this condition, there is a “large” subset of
${\mathcal{C}}_{\left\langle{V}\right\rangle}$ that is of constant dimension.
Thus, by adding a few linear functions to $U$, we move many polynomials from
${\mathcal{C}}_{\left\langle{V}\right\rangle}$ to $\mathbb{C}[V+U]_{2}$ (see
5.17). We can continue this process as long as
${\mathcal{C}}_{\left\langle{V}\right\rangle}$ is large enough, as the amount
of polynomials that we move at any step depends on
$|{\mathcal{C}}_{\left\langle{V}\right\rangle}|$. Therefore, when this process
terminates we still have to deal with a set
${\mathcal{C}}_{\left\langle{V}\right\rangle}$ that is not large but not too
small either (it is of size $\Omega(\delta m)$). Now, we turn our attention to
${{\mathcal{J}}_{\left\langle{V}\right\rangle}}$. Using similar arguments, and
relying on the fact that
$\left|{{\mathcal{C}}_{\left\langle{V}\right\rangle}}\right|$ is small, we
prove that we can add a few linear functions to $U$ and make
$\left|{{\mathcal{J}}_{\left\langle{V+U}\right\rangle}}\right|$ small. Having
achieved that, we prove that if both
$\left|{{\mathcal{C}}_{\left\langle{V+U}\right\rangle}}\right|$ and
$\left|{{\mathcal{J}}_{\left\langle{V+U}\right\rangle}}\right|$ are small then
they are in fact, empty (see 5.16).

###  1.2 Discussion

There are two distinct goals to the line of work [42, 36, 37], including this
paper. The first is obtaining higher degree geometric extensions of the
Sylvester-Gallai and Edelstein-Kelley theorems.

From the complexity theoretic point of view, the goal is to eventually obtain
PIT algorithms for $\Sigma^{[k]}\Pi^{[d]}\Sigma\Pi^{[r]}$ circuits, for any
$k,r=O(1)$. Currently we have a polynomial time PIT algorithm only for the
case $k=3$ and $r=2$ [37]. To understand such a difficult question one has to
start somewhere, and the case $k=3$ and $r=2$ was a natural starting point for
the investigation (especially as no subexponential time PIT algorithm, even
for $\Sigma^{[3]}\Pi^{[d]}\Sigma\Pi^{[2]}$ circuits, was known prior to [37]).
Since so little is known, we believe that a natural approach for advancing is
to first extend the results of [37] to higher degrees (i.e. higher values of
$r$), and then for a higher top fan-in (i.e. higher values of $k$). Before we
explain the difficulties in going to higher degrees we recall that [37] needed
the following strengthening of Theorem 1.7 for their PIT algorithm.

######  Theorem 1.14 (Theorem 1.6 in [37]).

There exists a universal constant $\lambda$ such that the following holds. Let
${\mathcal{T}}_{1},{\mathcal{T}}_{2},{\mathcal{T}}_{3}\subset\mathbb{C}[x_{1},\ldots,x_{n}]$
be finite sets of pairwise linearly independent homogeneous polynomials
satisfying the following properties:

  * •

Each $Q\in\cup_{j\in[3]}{\mathcal{T}}_{j}$ is either irreducible quadratic or
a square of a linear function.

  * •

Every two polynomials $Q_{1}$ and $Q_{2}$ from distinct sets satisfy that
whenever they vanish then the product of all the polynomials in the third set
vanishes as well.

Then,
$\dim(\operatorname{span}\\{{\cup_{j\in[3]}{\mathcal{T}}_{j}}\\})\leq\lambda$.

There are several difficult hurdles in going from $r=2$ to general $r$, or
even to $r=3$, if we wish to continue working in the framework of [42, 36, 37]
(and this paper). The first is understanding what is the correct
generalization of Theorem 1.13 to higher degrees, as this theorem lies at the
heart of all these papers. A second hurdle is obtaining a robust version of
Theorem 1.14. First for $r=2$ and then for higher degrees.

For extending Theorem 1.13 to higher degrees it seems natural to find an
extension to $r=3$. While it seems that such an approach could last forever
and lead nowhere (as we will then have to prove a result for $r=4$ etc.), we
believe that understanding the case $r=3$ can shed more light on the general
case, as sometimes going from degree $2$ to $3$ is as difficult as the general
case.

Once we prove such a structural theorem, we will need to extend Theorem 1.14
to higher values of $r$. An important tool in the proof of Theorem 1.14 was a
robust version of the EK-theorem.

######  Definition 1.15 ($\delta$-EK configuration).

We say that the sets
${\mathcal{T}}_{1},{\mathcal{T}}_{2},{\mathcal{T}}_{3}\subset\mathbb{C}^{n}$
form a $\delta$-EK configuration if for every $i\in[3]$ and
$p\in{\mathcal{T}}_{i}$ a $\delta$ fraction of the vectors $q$ in the union of
the two other sets satisfy that $p$ and $q$ span some vector in the third set
(the one not containing $p$ and $q$). We refer to a $1$-EK configuration as
simply an EK-configuration.

######  Theorem 1.16 (Theorem 3.9 of [37]).

Let $0<\delta\leq 1$ be any constant. Let
${\mathcal{T}}_{1},{\mathcal{T}}_{2},{\mathcal{T}}_{3}\subset\mathbb{C}^{n}$
be disjoint finite sets that form a $\delta$-EK configuration. Then,
$\dim(\operatorname{span}\\{{\cup_{i}{\mathcal{T}}_{i}}\\})=O(1/\delta^{3})$.

Thus, a natural continuation would be to prove a robust version of Theorem
1.16 for quadratic polynomials (i.e. a robust version of Theorem 1.7) and then
to extend it to a robust version of Theorem 1.14 and to higher degrees. While
in this paper we only prove a robust version of Theorem 1.5, we believe that
with some more technical work this can be extended to a robust version of
Theorem 1.7 as well. Hence, the next immediate challenge would be to obtain a
robust version of Theorem 1.14 (or even of the main result of [36]). If we
obtain such an extension and, in addition extend Theorem 1.13 to higher values
of $r$, then we expect that a PIT algorithm for the case $k=3$ and $r=3$ would
follow. More importantly, we believe that this will let us gain important
understanding on how to generalize the results for arbitrary values of $r$.

##  2 Preliminaries

In this section we explain our notation and present some basic algebraic
preliminaries.

###  2.1 Notation and basic facts

Greek letters $\alpha,\beta,\ldots$ denote scalars from $\mathbb{C}$. Non-
capitalized letters $a,b,c,\ldots$ denote linear forms and $x,y,z$ denote
variables (which are also linear forms). Bold faced letters denote vectors,
e.g. ${{\mathbf{x}}}=(x_{1},\ldots,x_{n})$ denotes a vector of variables,
${\boldsymbol{\alpha}}=(\alpha_{1},\ldots,\alpha_{n})$ is a vector of scalars,
and ${\mathbf{0}}=(0,\ldots,0)$ is the zero vector. We sometimes do not use a
boldface notation for a point in a vector space if we do not use its structure
as a vector. Capital letters such as $A,P,Q$ denote quadratic polynomials
whereas $V,U,W$ denote linear spaces, and $I,J$ denote ideals. Calligraphic
letters $\cal I,J,F,Q,T$ denote sets. For a positive integer $n$ we denote
$[n]=\\{1,2,\ldots,n\\}$.

We denote with $\mathbb{C}[{x}_{1},\ldots,{x}_{n}]$ the ring of $n$-variate
polynomials over $\mathbb{C}$. We shall denote with
$\mathbb{C}[{x}_{1},\ldots,{x}_{n}]_{d}$ the linear space of homogeneous
polynomials of degree $d$. In particular,
$\mathbb{C}[{x}_{1},\ldots,{x}_{n}]_{1}$ is the linear space of all linear
forms. An _Ideal_ $I\subseteq\mathbb{C}[{x}_{1},\ldots,{x}_{n}]$ is an abelian
subgroup that is closed under multiplication by ring elements. For
${\mathcal{S}}\subset\mathbb{C}[{x}_{1},\ldots,{x}_{n}]$, we denote with
$\left\langle{{\mathcal{S}}}\right\rangle$, the ideal generated by
${\mathcal{S}}$, that is, the smallest ideal that contains ${\mathcal{S}}$.
For example, for two polynomials $Q_{1}$ and $Q_{2}$, the ideal
$\left\langle{Q_{1},Q_{2}}\right\rangle$ is the set
$\mathbb{C}[{x}_{1},\ldots,{x}_{n}]Q_{1}+\mathbb{C}[{x}_{1},\ldots,{x}_{n}]Q_{2}$.
For a linear subspace $V\subseteq\mathbb{C}[{x}_{1},\ldots,{x}_{n}]$, we have
that $\left\langle{V}\right\rangle$ is the ideal generated by any basis of
$V$. The _radical_ of an ideal $I$, denoted $\sqrt{I}$, is the set of all ring
elements, $r$, satisfying that for some natural number $m$ (that may depend on
$r$), $r^{m}\in I$. Hilbert’s Nullstellensatz implies that, in
$\mathbb{C}[x_{1},\ldots,x_{n}]$, if a polynomial $Q$ vanishes whenever
$Q_{1}$ and $Q_{2}$ vanish, then
$Q\in\sqrt{\left\langle{Q_{1},Q_{2}}\right\rangle}$ (see e.g. [9]). We shall
often use the notation $Q\in\sqrt{\left\langle{Q_{1},Q_{2}}\right\rangle}$ to
denote this vanishing condition. For an ideal
$I\subseteq\mathbb{C}[{x}_{1},\ldots,{x}_{n}]$ we denote by
$\mathbb{C}[{x}_{1},\ldots,{x}_{n}]/I$ the _quotient ring_ , that is, the ring
whose elements are the cosets of $I$ in $\mathbb{C}[{x}_{1},\ldots,{x}_{n}]$
with the proper multiplication and addition operations. For an ideal
$I\subseteq\mathbb{C}[{x}_{1},\ldots,{x}_{n}]$ we denote the set of all common
zeros of elements of $I$ by ${\mathcal{Z}}(I)$. An ideal $I$ is called _prime_
if for every $f$ and $g$ such that $fg\in I$ it holds that either $f\in I$ or
$g\in I$. We next present basic facts about prime ideals that are used
throughout the proof.

######  Fact 2.1.

  1. 1.

If $F$ is an irreducible polynomial then $\left\langle{F}\right\rangle$ is a
prime ideal.

  2. 2.

For linear forms ${a}_{1},\ldots,{a}_{k}$ the ideal
$\left\langle{{a}_{1},\ldots,{a}_{k}}\right\rangle=\left\langle{\operatorname{span}\\{{{a}_{1},\ldots,{a}_{k}}\\}}\right\rangle$
is prime.

  3. 3.

If $I$ is a prime ideal then $\sqrt{I}=I$.

For $V_{1},\ldots,V_{k}$ linear spaces, we use $\sum_{i=1}^{k}V_{i}$ to denote
the linear space $V_{1}+\ldots+V_{k}$. For two nonzero polynomials $A$ and $B$
we denote $A\sim B$ if there is a nonzero $\alpha\in\mathbb{C}$ such that
$B=\alpha\cdot A$. For a space of linear forms
$V=\operatorname{span}\\{{{v}_{1},\ldots,{v}_{\Delta}}\\}\subseteq\mathbb{C}[{x}_{1},\ldots,{x}_{n}]$,
we say that a polynomial $P\in\mathbb{C}[{x}_{1},\ldots,{x}_{n}]$ depends only
on $V$ if the value of $P$ is determined by the values of the linear forms
$v_{1},\ldots,v_{\Delta}$. More formally, we say that $P$ depends only on $V$
if there is a $\Delta$-variate polynomial $\tilde{P}$ such that
$P\equiv\tilde{P}(v_{1},\ldots,v_{\Delta})$. We denote by
$\mathbb{C}[V]\subseteq\mathbb{C}[{x}_{1},\ldots,{x}_{n}]$ the subring of
polynomials that depend only on $V$. Similarly we denote by
$\mathbb{C}[V]_{2}\subseteq\mathbb{C}[{x}_{1},\ldots,{x}_{n}]$, the linear
subspace of all homogeneous quadratic polynomials that depend only on $V$.

Another notation that we will use throughout the proof is congruence modulo
linear forms.

######  Definition 2.2.

Let $V\subset\mathbb{C}[{x}_{1},\ldots,{x}_{n}]_{1}$ be a linear space333I.e.,
$V$ is a linear space of linear forms. and
$P,Q\in\mathbb{C}[{x}_{1},\ldots,{x}_{n}]$. We say that $P\equiv_{V}Q$ if
$P-Q\in\left\langle{V}\right\rangle$.

We end with a simple observation that follows immediately from the fact that
the quotient ring $\mathbb{C}[{x}_{1},\ldots,{x}_{n}]/{\langle V\rangle}$is a
unique factorization domain.

######  Observation 2.3.

Let $V\subset\mathbb{C}[{x}_{1},\ldots,{x}_{n}]_{1}$ be a linear space and
$P=\prod_{k=1}^{t}P_{k}$,
$Q=\prod_{k=1}^{t}Q_{k}\in\mathbb{C}[{x}_{1},\ldots,{x}_{n}]$. If for every
$k$, $P_{k}$ and $Q_{k}$ are irreducible in
$\mathbb{C}[{x}_{1},\ldots,{x}_{n}]/{\langle V\rangle}$, and
$P\equiv_{V}Q\not\equiv_{V}0$ then, up to a permutation of the indices,
$P_{k}\equiv_{V}Q_{k}$ for all $k\in[t]$.

We shall use this observation implicitly when factoring polynomials modulo
linear spaces of linear forms.

###  2.2 Rank of quadratic polynomials

We next give some facts regarding quadratic polynomials. Many of these facts
already appeared in [36].

######  Definition 2.4.

For a homogeneous quadratic polynomial $Q$ we denote with
$\operatorname{rank}_{s}(Q)$444In some recent works this was defined as
$\text{algebraic-rank}(Q)$ or $\text{tensor-rank}(Q)$, but as these notions
have different meanings we decided to continue with the notation of [36]. the
minimal $r$ such that there are $2r$ linear forms $\\{a_{k}\\}_{k=1}^{2r}$
satisfying $Q=\sum_{k=1}^{r}a_{2k}\cdot a_{2k-1}$. We call such representation
a _minimal representation_ of $Q$.

This is a slightly different notion than the usual one for the rank of a
quadratic form,555The usual definition says that $\operatorname{rank}(Q)$ is
the minimal $t$ such that there are $t$ linear forms $\\{a_{k}\\}_{k=1}^{t}$,
satisfying $Q=\sum_{k=1}^{t}a_{k}^{2}$. but it is more suitable for our needs.
We note that a quadratic $Q$ is irreducible if and only if
$\operatorname{rank}_{s}(Q)>1$. The next claim shows that a minimal
representation is unique in the sense that the space spanned by the linear
forms in it is unique.

######  Claim 2.5 (Claim 2.13 in [36]).

Let $Q$ be a homogeneous quadratic polynomial, and let
$Q=\sum_{i=1}^{r}a_{2i-1}\cdot a_{2i}$ and $Q=\sum_{i=1}^{r}b_{2i-1}\cdot
b_{2i}$ be two different minimal representations of $Q$. Then,
$\operatorname{span}\\{{{a}_{1},\ldots,{a}_{2r}}\\}=\operatorname{span}\\{{{b}_{1},\ldots,{b}_{2r}}\\}$.

2.5 shows that the minimal space is well defined, which allows us to define
the notion of a minimal space of a quadratic polynomial $Q$.

######  Definition 2.6.

Let Q be a quadratic polynomial. Assume that $\operatorname{rank}_{s}(Q)=r$,
and let $Q=\sum\limits_{i=1}^{r}a_{2i-1}a_{2i}$ be some minimal representation
of $Q$. We denote
$\text{Lin}(Q)\vcentcolon=\operatorname{span}\\{{{a}_{1},\ldots,{a}_{2r}}\\}$.
For a set $\\{Q_{i}\\}_{i=1}^{k}$ of quadratic polynomials we denote
$\text{Lin}({Q}_{1},\ldots,{Q}_{k})=\sum\limits_{i=1}^{k}\text{Lin}(Q_{i})$.

The following fact is easy to verify.

######  Fact 2.7.

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

######  Claim 2.8 (Claim 2.16 in [36]).

Let $Q$ be a homogeneous quadratic polynomial with
$\operatorname{rank}_{s}(Q)=r$, and let
$V\subset\mathbb{C}[{x}_{1},\ldots,{x}_{n}]$ be a linear space of linear forms
such that $\dim(V)=\Delta$. Then, $\operatorname{rank}_{s}(Q|_{V=0})\geq
r-\Delta$.

######  Claim 2.9 (Claim 2.17 in [36]).

Let $P_{1}\in\mathbb{C}[{x}_{1},\ldots,{x}_{k}]_{2}$, and
$P_{2}=y_{1}y_{2}\in\mathbb{C}[{y}_{1},\ldots,{y}_{2}]$. Then
$\operatorname{rank}_{s}(P_{1}+P_{2})=\operatorname{rank}_{s}(P_{1})+1$.
Moreover, $y_{1},y_{2}\in\text{Lin}(P_{1}+P_{2}).$

######  Corollary 2.10 (Corollary 2.18 in [36]).

Let $a$ and $b$ be linearly independent linear forms. If $c,d,e$ and $f$ are
linear forms such that $ab+cd=ef$ then it must hold that
$\dim(\operatorname{span}\\{{a,b}\\}\cap\operatorname{span}\\{{c,d}\\})\geq
1$.

######  Claim 2.11 (Claim 2.19 in [36]).

Let $a,b,c$ and $d$ be linear forms, and $V$ be a linear space of linear
forms. Assume $\\{{\mathbf{0}}\\}\neq\text{Lin}(ab-cd)\subseteq V$. Then,
$\operatorname{span}\\{{a,b}\\}\cap V\neq\\{{\mathbf{0}}\\}$.

######  Definition 2.12.

Let $a$ be a linear form and
$V\subseteq\mathbb{C}[{x}_{1},\ldots,{x}_{n}]_{1}$ a linear space. We denote
by ${V^{\perp}}(a)$ the projection of $a$ to $V^{\perp}$ (e.g., by identifying
each linear form with its vector of coefficients and taking the usual
projection). We also extend this definition to linear spaces:
$V^{\perp}(\operatorname{span}\\{{{a}_{1},\ldots,{a}_{k}}\\})=\operatorname{span}\\{{{V^{\perp}}(a_{1}),\ldots,{V^{\perp}}(a_{k})}\\}$.

######  Claim 2.13.

Let $Q,Q^{\prime}$ be quadratic polynomials, and $U$ a linear space of linear
forms. Let $r\in\mathbb{N}$ be a constant. Then, there exists a linear space
of linear forms, $V$, of dimension at most $8r$, with the following property:
For every $P\in\mathbb{C}[U]_{2}$ and every linear combination $\alpha Q+\beta
Q^{\prime}+P$ that satisfy $\operatorname{rank}_{s}(\alpha Q+\beta
Q^{\prime}+P)\leq r$, it holds that $\text{Lin}(\alpha Q+\beta
Q^{\prime}+P)\subseteq V+U$.

###### Proof.

If there are $T,T^{\prime}\in\mathbb{C}[U]_{2}$ such that
$\operatorname{rank}_{s}(Q-T),\operatorname{rank}_{s}(Q^{\prime}-T^{\prime})\leq
2r$ then let $V=\text{Lin}(Q-T)+\text{Lin}(Q^{\prime}-T^{\prime})$ and the
statement clearly holds. Thus, assume without loss of generality that for
every $T\in\mathbb{C}[U]_{2}$, $\operatorname{rank}_{s}(Q-T)>2r$. Let
$A_{1}=\alpha_{1}Q+\beta_{1}Q^{\prime}+P_{1}$ satisfy
$\operatorname{rank}_{s}(A_{1})\leq r$, for some $P_{1}\in\mathbb{C}[U]_{2}$.
Set $V=\text{Lin}(A_{1})$. If $V$ does not satisfy the statement then let
$P_{2}\in\mathbb{C}[U]_{2}$ and $A_{2}=\alpha_{2}Q+\beta_{2}Q^{\prime}+P_{2}$
be such that $\operatorname{rank}_{s}(A_{2})\leq r$ and
$\text{Lin}(A_{2})\not\subseteq V+U$. In particular, the vectors
$(\alpha_{1},\beta_{1})$ and $(\alpha_{2},\beta_{2})$ are linearly
independent. Hence, $Q\in\operatorname{span}\\{{A_{1},A_{2},P_{1},P_{2}}\\}$.
Consequently, there is
$T\in\operatorname{span}\\{{P_{1},P_{2}}\\}\subseteq\mathbb{C}[U]_{2}$ such
that $\operatorname{rank}_{s}(Q-T)\leq 2r$, in contradiction. ∎

######  Claim 2.14.

Let $Q,Q^{\prime}$ be quadratic polynomials and let $r\in\mathbb{N}$ be a
constant. Then, there exists a linear space of linear forms, $V$, of dimension
at most $8r$, such that for every linear combination satisfying
$\operatorname{rank}_{s}(\alpha Q+\beta Q^{\prime})\leq r$ it holds that
$\text{Lin}(\alpha Q+\beta Q^{\prime})\subseteq V$

###### Proof.

This claim follows immediately from 2.13 with $U=\\{{\mathbf{0}}\\}.$ ∎

######  Claim 2.15.

Let $P$ be a homogeneous irreducible quadratic polynomial and let $a$ and $b$
be linear forms. Assume that
$\prod_{i\in{\mathcal{I}}}T_{i}\in\sqrt{\left\langle{P,ab}\right\rangle}$, for
some set ${\mathcal{I}}$. Then, either $\operatorname{rank}_{s}(P)=2$ and
$a\in\text{Lin}(P)$ or there is $i\in{\mathcal{I}}$ such that $T_{i}=\alpha
P+ac$ for some linear form $c$ and $\alpha\in\mathbb{C}$.

###### Proof.

Since $P$ is irreducible we have that $\operatorname{rank}_{s}(P)\geq 2$. We
consider two cases concerning $P|_{a=0}$. If $P$ becomes reducible when
setting $a=0$ then $\operatorname{rank}_{s}(P|_{a=0})=1$. Therefore it must
hold that $\operatorname{rank}_{s}(P)=2$ and $a\in\text{Lin}(P)$. If $P$
remains irreducible after setting $a=0$ then
$\left\langle{P|_{a=0}}\right\rangle$ is a prime ideal. Hence,
$\sqrt{\left\langle{P|_{a=0}}\right\rangle}=\left\langle{P|_{a=0}}\right\rangle$
and thus there is $i\in{\mathcal{I}}$ with
$T_{i}|_{a=0}\in\left\langle{P|_{a=0}}\right\rangle$. In particular,
$T_{i}=\alpha P+ac$ for some linear form $c$. ∎

In [36] the following claim was proved.

######  Claim 2.16 (Claim 2.20 in [36]).

Let $V=\sum_{i=1}^{m}V_{i}$ where $V_{i}$ are linear subspaces, and for every
$i$, $\dim(V_{i})=2$. If for every $i\neq j\in[m]$, $\dim(V_{i}\cap V_{j})=1$,
then either $\dim(\bigcap_{i=1}^{m}V_{i})=1$ or $\dim(V)=3$.

###  2.3 Projection mapping

This section collects some facts from [36] concerning projections of linear
spaces and the effect on relevant quadratic polynomials.

######  Definition 2.17 (Definition 2.21 of [36]).

Let
$V=\operatorname{span}\\{{{v}_{1},\ldots,{v}_{\Delta}}\\}\subseteq\operatorname{span}\\{{x_{1},\ldots,x_{n}}\\}$
be a $\Delta$-dimensional linear space of linear forms, and let
$\\{{u}_{1},\ldots,{u}_{{n-\Delta}}\\}$ be a basis for $V^{\perp}$. For
${\boldsymbol{\alpha}}=({\alpha}_{1},\ldots,{\alpha}_{\Delta})\in\mathbb{C}^{\Delta}$
we define
$T_{{\boldsymbol{\alpha}},V}:\mathbb{C}[{x}_{1},\ldots,{x}_{n}]\mapsto\mathbb{C}[{x}_{1},\ldots,{x}_{n},z]$,
where $z$ is a new variable, to be the linear map given by the following
action on the basis vectors: $T_{{\boldsymbol{\alpha}},V}(v_{i})=\alpha_{i}z$
and $T_{{\boldsymbol{\alpha}},V}(u_{i})=u_{i}$.

Thus, if we pick ${\boldsymbol{\alpha}}$ at random, then
$T_{{\boldsymbol{\alpha}},V}$ projects $V$ to $\operatorname{span}\\{{z}\\}$
in a random way while keeping the perpendicular space intact. Clearly
$T_{{\boldsymbol{\alpha}},V}$ is a linear transformation, and it defines a
ring homomorphism from $\mathbb{C}[{x}_{1},\ldots,{x}_{n}]$ to
$\mathbb{C}[{x}_{1},\ldots,{x}_{n},z]$ in the natural way.

######  Claim 2.18 (Claim 2.23 of [36]).

Let $V\subseteq\operatorname{span}\\{{x_{1},\ldots,x_{n}}\\}$ be a
$\Delta$-dimensional linear space of linear forms. Let $F$ and $G$ be two
polynomials that share no common irreducible factor. Then, with probability
$1$ over the choice of ${\boldsymbol{\alpha}}\in[0,1]^{\Delta}$ (say according
to the uniform distribution), every common factor of
$T_{{\boldsymbol{\alpha}},V}(F)$ and $T_{{\boldsymbol{\alpha}},V}(G)$ (if
there is such) must be in $\mathbb{C}[z]$.

######  Claim 2.19 (Corollary 2.24 of [36]).

Let $V$ be a $\Delta$-dimensional linear space of linear forms. Let $F$ and
$G$ be two linearly independent, irreducible quadratics, such that
$\text{Lin}(F),\text{Lin}(G)\not\subseteq V$. Then, with probability $1$ over
the choice of ${\boldsymbol{\alpha}}\in[0,1]^{\Delta}$ (say according to the
uniform distribution), $T_{{\boldsymbol{\alpha}},V}(F)$ and
$T_{{\boldsymbol{\alpha}},V}(G)$ are linearly independent.

######  Claim 2.20 (Claim 2.25 of [36]).

Let $Q$ be an irreducible quadratic polynomial, and $V$ a $\Delta$-dimensional
linear space. Then for every ${\boldsymbol{\alpha}}\in\mathbb{C}^{\Delta}$,
$\operatorname{rank}_{s}(T_{{\boldsymbol{\alpha}},V}(Q))\geq\operatorname{rank}_{s}(Q)-\Delta$.

######  Claim 2.21 (Claim 2.26 of [36]).

Let ${\mathcal{Q}}$ be a set of quadratics, and $V$ be a $\Delta$-dimensional
linear space. Then, if there are linearly independent vectors,
$\\{{\boldsymbol{\alpha}}^{1},\dots,{\boldsymbol{\alpha}}^{\Delta}\\}\subset\mathbb{C}^{\Delta}$
such that for every $i$,666Recall that
$\text{Lin}(T_{{\boldsymbol{\alpha}}^{i},V}({\mathcal{Q}}))$ is the space
spanned by
$\cup_{Q\in{\mathcal{Q}}}\text{Lin}(T_{{\boldsymbol{\alpha}}^{i},V}({\mathcal{Q}}))$.
$\dim(\text{Lin}(T_{{\boldsymbol{\alpha}}^{i},V}({\mathcal{Q}})))\leq\sigma$
then $\dim(\text{Lin}({\mathcal{Q}}))\leq(\sigma+1)\Delta$.

##  3 Robust-SG theorems in $\mathbb{C}^{n}$

We shall need the following generalizations of Theorem 1.2. We postpone the
proofs to Appendix A.

######  Theorem 3.1.

Let $0<\delta\leq 1$ be any constant. Let $W\subset\mathbb{C}^{n}$ be an
$r$-dimensional space. Let $\mathcal{W}\subset W$ and
${\mathcal{K}}\subset\mathbb{C}^{n}\setminus W$ be finite subsets such that no
two vectors in ${\mathcal{T}}={\mathcal{K}}\cup{\mathcal{W}}$ are linearly
dependent. Assume further that all the elements in ${\mathcal{K}}$ satisfy the
following relaxed EK-property: For every $p\in{\mathcal{K}}$, for at least
$\delta$ fraction of the points $q\in{\mathcal{T}}$ the span of $p$ and $q$
contains a point in ${\mathcal{T}}\setminus\\{p,q\\}$. Then,
$\dim(\operatorname{span}\\{{{\mathcal{T}}}\\})\leq O(r+\frac{1}{\delta})$.

We also use the following bi-partitive version of [12, Corollary 1.11] this is
a slight variation of the formulation presented in their paper.

######  Claim 3.2.

Let $V={v}_{1},\ldots,{v}_{n}\subset\mathbb{C}^{d}$ be a set of $n$ distinct
points. Suppose that there is ${\mathcal{B}}\subseteq V$ such that there are
at least $\delta n^{2}$ pairs in
${\mathcal{B}}\times(V\setminus{\mathcal{B}})$ that lie on a special line.
Then there exists a subset ${\mathcal{B}}^{\prime}\subseteq{\mathcal{B}}$ such
that $\left|{{\mathcal{B}}^{\prime}}\right|\geq(\delta/6)n$ and $\text{affine-
dim}({\mathcal{B}}^{\prime})\leq O(1/\delta)$.

The important difference between 3.2 and [12, Corollary 1.11] is that 3.2
guarantees the existence of a low-dimensional subspace that contains a
constant fraction of the points in ${\mathcal{B}}$, whereas from [12,
Corollary 1.11] we do not get any guarantee about the fraction of points from
${\mathcal{B}}$ in the low-dimensional space.

##  4 Strengthening Case (iii) of Theorem 1.13

The following claim strengthens Theorem 1.13(iii) by providing more
information on the polynomial in the radical.

######  Claim 4.1.

Let $P,Q$ and $T$ be irreducible homogeneous quadratic polynomials, such that
$T\in\sqrt{\left\langle{P,Q}\right\rangle}$. Furthermore, assume that they
satisfy Theorem 1.13(iii) and not any other case, that is, there are linear
forms $v_{1},v_{2}$ such that
$T,P,Q\in\left\langle{v_{1},v_{2}}\right\rangle$. Finally, assume
$\text{Lin}(P)\not\subseteq\text{Lin}(Q)$. Then there are linear forms
$v^{\prime}_{1},v^{\prime}_{2}\in\operatorname{span}\\{{v_{1},v_{2}}\\}$ such
that the following holds:

  * •

$P=v^{\prime}_{1}\ell+{v^{\prime}}_{2}^{2}$ for some linear form $\ell$.

  * •

$Q=v^{\prime}_{1}u-{v^{\prime}}_{2}^{2}$ for some linear form $u$.

  * •

$T={v^{\prime}}_{2}(\ell+u)+\alpha P+\beta Q$ for some constants
$\alpha,\beta\in\mathbb{C}$,

where the qualities holds up to a constant non zero factor.

###### Proof.

Denote $P=v_{1}\ell_{1}+v_{2}\ell_{2}$, $Q=v_{1}u_{1}+v_{2}u_{2}$ and
$V=\operatorname{span}\\{{v_{1},v_{2},u_{1},u_{2}}\\}=\text{Lin}(Q)$. From the
fact that $Q$ is irreducible it follows, without loss of generality, that
$u_{1}\notin\operatorname{span}\\{{v_{1},v_{2}}\\}$.

#### Case 1: $\operatorname{span}\\{{\ell_{1},\ell_{2}}\\}\cap
V=\\{{\mathbf{0}}\\}$:

First we note that since $P$ is irreducible we must have that $\ell_{1}$ and
$\ell_{2}$ are linearly independent and therefore,
$\text{Lin}(P)=\operatorname{span}\\{{v_{1},v_{2},\ell_{1},\ell_{2}}\\}$ and
$\dim(\text{Lin}(P))=4$. Observe further that $Q|_{\ell_{1}=\ell_{2}=0}$ is
irreducible (as $\operatorname{span}\\{{\ell_{1},\ell_{2}}\\}\cap
V=\\{{\mathbf{0}}\\}$).

######  Claim 4.2.

There exist $\alpha\in\mathbb{C}$ and linear forms
$v^{\prime},v^{\prime\prime}\in\operatorname{span}\\{{v_{1},v_{2}}\\}$ such
that $T=\alpha Q+v^{\prime}\ell_{1}+v^{\prime\prime}\ell_{2}$.

###### Proof.

Since $P\equiv_{\ell_{1},\ell_{2}}0$ we get that
$T|_{\ell_{1}=\ell_{2}=0}\in\left\langle{Q|_{\ell_{1}=\ell_{2}=0}}\right\rangle$.
Irreducibility of $Q|_{\ell_{1}=\ell_{2}=0}$ implies that for some
$\alpha\in\mathbb{C}$ and linear forms $w^{\prime}$ and $w^{\prime\prime}$, we
have that $T=\alpha Q+w^{\prime}\ell_{1}+w^{\prime\prime}\ell_{2}$. Denote
$T^{\prime}=w^{\prime}\ell_{1}+w^{\prime\prime}\ell_{2}\in\left\langle{\ell_{1},\ell_{2}}\right\rangle$.
As $T^{\prime}=T-\alpha Q\in\left\langle{v_{1},v_{2}}\right\rangle$ it follows
that $w^{\prime}\ell_{1}\equiv_{v_{1},v_{2}}-w^{\prime\prime}\ell_{2}$. The
assumption $\operatorname{span}\\{{\ell_{1},\ell_{2}}\\}\cap
V=\\{{\mathbf{0}}\\}$ implies that
$w^{\prime}\in\operatorname{span}\\{{\ell_{2},v_{1},v_{2}}\\}$ and
$w^{\prime\prime}\in\operatorname{span}\\{{\ell_{1},v_{1},v_{2}}\\}$. Denote
$w^{\prime}=\beta^{\prime}\ell_{2}+v^{\prime}$ and
$w^{\prime\prime}=\beta^{\prime\prime}\ell_{1}+v^{\prime\prime}$ for
$v^{\prime},v^{\prime\prime}\in\operatorname{span}\\{{v_{1},v_{2}}\\}$. Thus,
$T^{\prime}=(\beta^{\prime}+\beta^{\prime\prime})\ell_{1}\ell_{2}+\ell_{1}\cdot
v^{\prime}+\ell_{2}\cdot v^{\prime\prime}$. Since
$T^{\prime}\in\left\langle{v_{1},v_{2}}\right\rangle$ it follows that
$\beta^{\prime}+\beta^{\prime\prime}=0$. Hence, $T^{\prime}=\ell_{1}\cdot
v^{\prime}+\ell_{2}\cdot v^{\prime\prime}$ as claimed. ∎

Since
$T^{\prime}\in\sqrt{\left\langle{P,Q}\right\rangle}\subseteq\left\langle{v_{2},u_{1},\ell_{1}}\right\rangle$
it follows that $\ell_{2}\cdot
v^{\prime\prime}\in\left\langle{v_{2},u_{1},\ell_{1}}\right\rangle$. Note that
since
$\operatorname{span}\\{{\ell_{1},\ell_{2}}\\}\cap\text{Lin}(Q)=\\{{\mathbf{0}}\\}$
it must be the case that
$v^{\prime\prime}\in\operatorname{span}\\{{v_{2},u_{1},\ell_{1}}\\}$. The same
argument shows that
$v^{\prime\prime}\in\operatorname{span}\\{{v_{2},u_{1}}\\}$ and since
$u_{1}\notin\operatorname{span}\\{{v_{1},v_{2}}\\}$ we get that
$v^{\prime\prime}\in\operatorname{span}\\{{v_{2}}\\}$. Denote
$v^{\prime\prime}=\beta^{\prime\prime}v_{2}$. We have that
$T^{\prime}-\beta^{\prime\prime}P=\ell_{1}\cdot(v^{\prime}-\beta^{\prime\prime}v_{1})=\ell_{1}\cdot(\gamma
v_{1}+\delta v_{2})$, for some $\gamma,\delta\in\mathbb{C}$. From the
assumption that $T\not\in\operatorname{span}\\{{P,Q}\\}$ we see that at least
one among $\gamma,\delta$ is not zero.

Let $\lambda$ be such that both $\lambda\cdot\gamma+\delta\neq 0$ and $\lambda
u_{1}+u_{2}\not\in\operatorname{span}\\{{v_{1},v_{2}}\\}$ hold. As
$u_{1},v_{1},v_{2},\ell_{1},\ell_{2}$ are linearly independent it follows that
there is an assignment ${\boldsymbol{\alpha}}$ such that
$v_{2}({\boldsymbol{\alpha}})=\ell_{1}({\boldsymbol{\alpha}})=1$, and
$v_{1}({\boldsymbol{\alpha}})=-\ell_{2}({\boldsymbol{\alpha}})=\lambda$.
Observe that $P({\boldsymbol{\alpha}})=0$ and
$T^{\prime}({\boldsymbol{\alpha}})=(\gamma\lambda+\delta)\neq 0$. Also note
that our choice of $\lambda$ implies that we can choose
${\boldsymbol{\alpha}}$ so that we also have $Q({\boldsymbol{\alpha}})=0$.
Consequently, $P({\boldsymbol{\alpha}})=Q({\boldsymbol{\alpha}})=0$ and
$T({\boldsymbol{\alpha}})=T^{\prime}({\boldsymbol{\alpha}})\neq 0$, in
contradiction to the fact that $T\in\sqrt{\left\langle{Q,P}\right\rangle}$.

#### Case 2: $\operatorname{span}\\{{\ell_{1},\ell_{2}}\\}\cap
V\neq\\{{\mathbf{0}}\\}$:

From the requirement $\text{Lin}(P)\not\subseteq\text{Lin}(Q)$ we can assume,
without loss of generality, that $\ell_{1}\notin\text{Lin}(Q)$. It follows
that $v_{1}\notin\operatorname{span}\\{{\ell_{1},u_{1},v_{2}}\\}$. As
$\operatorname{span}\\{{\ell_{1},\ell_{2}}\\}\cap V\neq\\{{\mathbf{0}}\\}$ we
have that for some $\alpha^{\prime}\in\mathbb{C}$ and $v\in V$,
$\ell_{2}=\alpha^{\prime}\ell_{1}+v$. By applying a change of basis to
$\operatorname{span}\\{{v_{1},v_{2}}\\}$ (if necessary), we can assume,
without loss of generality, that $\alpha=0$. Concluding, we have that
$P=v_{1}\ell_{1}+v_{2}v$ and $Q=v_{1}u_{1}+v_{2}u_{2}$, where $v\in V$. Note
that $v\not\in\operatorname{span}\\{{v_{1}}\\}$ as otherwise $P$ would be
reducible. Observe further that
$\operatorname{span}\\{{\ell_{1},u_{1}}\\}\cap\operatorname{span}\\{{v_{1},v_{2}}\\}=\\{0\\}$.

Denote $T=v_{1}t_{1}+v_{2}t_{2}$. As
$T\in\sqrt{\left\langle{Q,P}\right\rangle}\subseteq\left\langle{v_{2},\ell_{1},u_{1}}\right\rangle$,
it follows that $t_{1}\in\operatorname{span}\\{{v_{2},\ell_{1},u_{1}}\\}$.
Denote $t_{1}=\alpha\ell_{1}+\beta u_{1}+\gamma v_{2}$. Let
$T^{\prime}=T-\alpha P-\beta Q=v_{2}(\gamma v_{1}+t_{2}-\alpha v-\beta
u_{2})$. Let $t=\gamma v_{1}+t_{2}-\alpha v-\beta u_{2}$. As
$T\not\in\operatorname{span}\\{{P,Q}\\}$, we have that $t\neq 0$. The
following claim implies that $t\notin V$.

######  Claim 4.3.

Let $A\in\sqrt{\left\langle{P,Q}\right\rangle}$ be a polynomial. If
$A\in\mathbb{C}[V]$ then $A\in\left\langle{Q}\right\rangle$.

###### Proof.

Observe that if for every
${\boldsymbol{\alpha}}\in{\mathcal{Z}}(Q)\setminus{\mathcal{Z}}(v_{1})$ it
holds that ${\boldsymbol{\alpha}}\in{\mathcal{Z}}(A)$ then
${\mathcal{Z}}(Q)=\overline{{\mathcal{Z}}(Q)\setminus{\mathcal{Z}}(v_{1})}\subseteq{\mathcal{Z}}(A)$777We
take closure with respect to Zariski topology., and thus by Hilbert’s
Nullstellensatz it follows that
$A\in\sqrt{\left\langle{Q}\right\rangle}=\left\langle{Q}\right\rangle$ as
claimed.

So let
${\boldsymbol{\alpha}}\in({\mathcal{Z}}(Q)\setminus{\mathcal{Z}}(v_{1}))\setminus{\mathcal{Z}}(A)$.
As $\ell_{1}\not\in V$ and $v_{1}({\boldsymbol{\alpha}})\neq 0$, we can choose
${\boldsymbol{\alpha}}$ that in addition satisfies
$P({\boldsymbol{\alpha}})=0$. Thus, we have that
$P({\boldsymbol{\alpha}})=Q({\boldsymbol{\alpha}})=0$ but
$A({\boldsymbol{\alpha}})\neq 0$, contradicting the assumption
$A\in\sqrt{\left\langle{P,Q}\right\rangle}$. ∎

Observe that if $t\in V$ then $T^{\prime}=v_{2}\cdot
t\in\sqrt{\left\langle{P,Q}\right\rangle}$ and
$\text{Lin}(T^{\prime})\subseteq V$. The claim implies that
$T^{\prime}\in\left\langle{Q}\right\rangle$ in contradiction (as $Q$ is
irreducible and $T^{\prime}\neq 0$).

We now note that $\ell_{1}\in\operatorname{span}\\{{V,t}\\}$. Indeed, if this
is not the case then whenever $v_{1}\neq 0$ we can make sure that $P$ vanishes
(by substituting $\ell_{1}=-v_{2}\cdot v/v_{1}$) without affecting the values
of $Q$ and $T$. A similar argument as in the proof of the claim implies that
in this case too we have $T\in\left\langle{Q}\right\rangle$ in contradiction.
We can therefore assume that $t=\ell_{1}+w$ for some $w\in V$ (this is
possible as we can rescale $v_{2}$ if needed). Summarizing, we have that:

$\displaystyle P$ $\displaystyle=v_{1}\ell_{1}+v_{2}v$ $\displaystyle Q$
$\displaystyle=v_{1}u_{1}+v_{2}u_{2}$ $\displaystyle T^{\prime}$
$\displaystyle=v_{2}(\ell_{1}+w)=v_{2}\ell_{1}+v_{2}w$

Let $A=v_{2}\cdot P-v_{1}\cdot T^{\prime}=v_{2}(v_{1}\cdot w-v\cdot v_{2})$.
Since $P$ is irreducible we have that $A\neq 0$. As $A$ depends only on the
linear functions in $V$, and clearly
$A\in\sqrt{\left\langle{P,Q}\right\rangle}$, 4.3 implies
$A\in\left\langle{Q}\right\rangle$. Therefore, $v_{2}(v_{1}\cdot w-v\cdot
v_{2})=A=aQ$ for some non zero linear form $a$. Rescaling if necessary,
irreducibility of $Q$ implies that $v_{2}=a$ and $(v_{1}\cdot w-v\cdot
v_{2})=Q$. Consequently, $v_{1}(w-u_{1})=v_{2}(u_{2}+v)$, which in turns
implies that there is a non-zero $\varepsilon\in\mathbb{C}$ such that
$\varepsilon v_{1}=(u_{2}+v)$ and $\varepsilon v_{2}=(w-u_{1})$. Hence,
$u_{1}=w-\varepsilon v_{2}$ and $u_{2}=\varepsilon v_{1}-v$. Therefore,
$Q=v_{1}(w-\varepsilon v_{2})+v_{2}(\varepsilon v_{1}-v)=v_{1}w-v_{2}v$. As
$P,Q\in\left\langle{v,v_{1}}\right\rangle$ we deduce that
$T^{\prime}=v_{2}(\ell_{1}+w)\in\left\langle{v,v_{1}}\right\rangle$. Hence,
$v_{2}\in\operatorname{span}\\{{v_{1},v}\\}$. As $v,v_{2}\not\sim v_{1}$ it
follows that we can write $v=\delta v_{2}+\gamma v_{1}$ and up to a proper
rescaling $v=v_{2}+\gamma v_{1}$. We conclude that

$\displaystyle P$ $\displaystyle=v_{1}\ell_{1}+v_{2}(v_{2}+\gamma
v_{1})=v_{1}(\ell_{1}+\gamma v_{2})+v_{2}^{2}$ $\displaystyle Q$
$\displaystyle=v_{1}w-v_{2}(v_{2}+\gamma v_{1})=v_{1}(w-\gamma
v_{2})-v_{2}^{2}$ $\displaystyle T^{\prime}$
$\displaystyle=v_{2}(\ell_{1}+w)=v_{2}(\ell_{1}+\gamma v_{2}+w-\gamma v_{2}),$

as claimed. ∎

As a consequence of the claim we can deduce the following uniqueness property.

######  Corollary 4.4.

Let $P,Q,Q^{\prime},T$ be pairwise linearly independent irreducible quadratics
such that $T\in\sqrt{\left\langle{P,Q}\right\rangle}$. Let $T^{\prime}$ be
such that $T^{\prime}\not\sim P,Q,Q^{\prime}$ and such that
$T^{\prime}\in\sqrt{\left\langle{P,Q^{\prime}}\right\rangle}$. Assume further
that $P\in\left\langle{\text{Lin}(Q)+\text{Lin}(Q^{\prime})}\right\rangle$ but
$\text{Lin}(P)\not\subseteq\text{Lin}(Q)+\text{Lin}(Q^{\prime})$. Then $T\neq
T^{\prime}$. In addition,
$\text{Lin}(T),\text{Lin}(T^{\prime})\not\subseteq{\text{Lin}(Q)+\text{Lin}(Q^{\prime})}$.

###### Proof.

Set $V={\text{Lin}(Q)+\text{Lin}(Q^{\prime})}$. If $P,Q$ satisfy Theorem
1.13(ii) then there is a linear form $\ell$ such that $\ell^{2}=\alpha P+\beta
Q\in\left\langle{V}\right\rangle$. This implies $\ell\in V$ and therefore
$\text{Lin}(P)\subseteq\text{Lin}(Q)+\operatorname{span}\\{{\ell}\\}\subseteq
V$, in contradiction. Similarly $P,Q^{\prime}$ do not satisfy Theorem
1.13(ii).

Assume towards a contradiction that $T=T^{\prime}$.

From pairwise independence, if
$T\in\operatorname{span}\\{{P,Q^{\prime}}\\}\cap\operatorname{span}\\{{P,Q}\\}$
then $P\in\operatorname{span}\\{{Q,Q^{\prime}}\\}$, and again we get
$\text{Lin}(P)\subseteq V$, in contradiction. Thus, without loss of
generality, $P$ and $Q$ satisfy Theorem 1.13(iii) and not any other case of
Theorem 1.13. 4.1 implies (up to rescaling of $P,Q$ and $T$) that for some
$v_{1},v_{2},u\in V$ and $\alpha,\beta\in\mathbb{C}$:

$\displaystyle P$ $\displaystyle=v_{1}\ell+v_{2}^{2}$ $\displaystyle Q$
$\displaystyle=v_{1}u-v_{2}^{2}$ (4.5) $\displaystyle T$
$\displaystyle=v_{2}(\ell+u)+\alpha P+\beta Q\;,$

where $\ell\not\in V$. If $T\in\operatorname{span}\\{{P,Q^{\prime}}\\}$ we
deduce that $v_{2}(\ell+u)+\alpha P+\beta Q=T=\gamma P+\delta Q^{\prime}$.
Rearranging we obtain that
$\ell(v_{2}+(\alpha-\gamma)v_{1})\in\mathbb{C}[V]_{2}$ which implies that
either $v_{1}\sim v_{2}$, in contradiction to the assumption that the
polynomials are irreducible, or, that $\ell\in V$, in contradiction to the
assumption that $\text{Lin}(P)\not\subseteq V$. Thus, it follows that $P$ and
$Q^{\prime}$ satisfy Theorem 1.13(iii) and not any other case of Theorem 1.13.
Applying 4.1 again we get that for some $u_{1},u_{2},u^{\prime}\in V$ and
$\nu,\alpha^{\prime},\beta^{\prime}\in\mathbb{C}$:

$\displaystyle P$ $\displaystyle=u_{1}\ell^{\prime}+u_{2}^{2}$ $\displaystyle
Q^{\prime}$ $\displaystyle=u_{1}u^{\prime}-u_{2}^{2}$ (4.6) $\displaystyle T$
$\displaystyle=\nu(u_{2}(\ell^{\prime}+u^{\prime}))+\alpha^{\prime}P+\beta^{\prime}Q^{\prime}.$

Considering both representations of $P$ we deduce that
$v_{1}\ell+v_{2}^{2}\in\left\langle{u_{1},u_{2}}\right\rangle$. As
$\ell\notin\operatorname{span}\\{{u_{1},u_{2},v_{1},v_{2}}\\}\subseteq V$ it
follows that
$\operatorname{span}\\{{v_{1},v_{2}}\\}=\operatorname{span}\\{{u_{1},u_{2}}\\}$.
Thus for some $\delta,\delta^{\prime},\gamma,\gamma^{\prime}\in\mathbb{C}$ we
have $v_{1}=\delta^{\prime}u_{1}+\gamma^{\prime}u_{2}$ and $v_{2}=\delta
u_{1}+\gamma u_{2}$. Substituting we obtain
$u_{1}\ell^{\prime}+u_{2}^{2}=P=v_{1}\ell+v_{2}^{2}=(\delta^{\prime}u_{1}+\gamma^{\prime}u_{2})\ell+(\delta
u_{1}+\gamma u_{2})^{2}$. Thus,

$u_{1}\ell^{\prime}+u_{2}^{2}=u_{1}(\delta^{\prime}\ell+\delta^{2}u_{1}+2\delta\gamma
u_{2})+u_{2}(\gamma^{\prime}\ell+\gamma^{2}u_{2})$

and therefore

$u_{1}(\ell^{\prime}-(\delta^{\prime}\ell+\delta^{2}u_{1}+2\delta\gamma
u_{2}))=u_{2}(\gamma^{\prime}\ell+(\gamma^{2}-1)u_{2})\;.$ (4.7)

Since $u_{1}\not\sim u_{2}$, it follows that
$\gamma^{\prime}\ell+(\gamma^{2}-1)u_{2}\sim u_{1}$, which implies
$\gamma^{\prime}=0$ (as otherwise we will have $\ell\in V$) and $\gamma=\pm
1$. Rescaling $u_{2}$ and both $u_{1}$ and $u$ if needed, we can assume
without loss of generality that $\gamma=1$ and $\delta^{\prime}=1$.
Concluding, we have that

$v_{1}=u_{1}\quad\text{ and }\quad v_{2}=\delta u_{1}+u_{2}\;.$

Equation (4.7) now gives $u_{1}(\ell^{\prime}-(\ell+\delta^{2}u_{1}+2\delta
u_{2}))=0$ which implies

$\ell^{\prime}=\ell+\delta^{2}u_{1}+2\delta u_{2}=\ell+\delta(v_{2}+u_{2})\;.$
(4.8)

Similarly, considering both representations of $T$ we get

$\nu(u_{2}(\ell^{\prime}+u^{\prime}))+\alpha^{\prime}P+\beta^{\prime}Q^{\prime}=T=(\delta
u_{1}+u_{2})(\ell+u)+\alpha P+\beta Q\;.$ (4.9)

Rearranging and using Equation (4.8) gives

$\ell\cdot\left((\nu-1)u_{2}+(\alpha^{\prime}-\delta-\alpha)u_{1}\right)\in\mathbb{C}[V]_{2}\;.$

As $\ell\not\in V$ and $u_{1}\not\sim u_{2}$, it must hold that

$\nu=1\quad\text{ and }\quad\alpha^{\prime}=\delta+\alpha\;.$

Substituting in Equation (4.9) we get

$u_{2}(\delta(v_{2}+u_{2})+u^{\prime})+\delta
v_{2}^{2}+\beta^{\prime}(u_{1}u^{\prime}-u_{2}^{2})=uv_{2}+\beta(u_{1}u-v_{2}^{2})\;.$

Rearranging,

$\displaystyle u^{\prime}(u_{2}+\beta^{\prime}u_{1})-u(v_{2}+\beta
u_{1})=-(\beta+\delta)v_{2}^{2}-u_{2}(\delta(v_{2}+u_{2})-\beta^{\prime}u_{2})$

and as the second term is a homogeneous quadratic in two linear forms it
follows that it is of the form $ww^{\prime}$ for
$w,w^{\prime}\in\mathbb{C}[\operatorname{span}\\{{v_{2},u_{2}}\\}]_{2}$.
Therefore, there is a non trivial linear combination $u^{\prime}=\varepsilon
u+u_{3}$ for $u_{3}\in\operatorname{span}\\{{v_{2},u_{2}}\\}$. Substituting we
get that

$u(\varepsilon
u_{2}+\varepsilon\beta^{\prime}u_{1}-(\delta+\beta)u_{1}-u_{2})\in\operatorname{span}\\{{u_{1},u_{2}}\\}\;.$

If $u\in\operatorname{span}\\{{u_{1},u_{2}}\\}$ then $Q$ is reducible in
contradiction. Therefore, as $u_{1}\not\sim u_{2}$, it must hold that

$\varepsilon=1\;(\text{hence }u^{\prime}=u+u_{3}),\quad\text{ and
}\quad\beta^{\prime}=\beta+\delta\;.$

Looking again at Equation (4.9) we obtain

$\displaystyle u_{2}(\ell^{\prime}+u^{\prime})+\delta(P+Q^{\prime})$
$\displaystyle=v_{2}(\ell+u)+\beta(Q-Q^{\prime})$ $\displaystyle(u_{2}+\delta
u_{1})(\ell^{\prime}+u^{\prime})$
$\displaystyle=v_{2}(\ell+u)+\beta(Q-Q^{\prime})$ $\displaystyle
v_{2}(\ell^{\prime}+u^{\prime}-\ell-u)$
$\displaystyle=\beta(u_{1}(u-u^{\prime})+u_{2}^{2}-v_{2}^{2})$ $\displaystyle
v_{2}(\delta(v_{2}+u_{2})+u_{3})$ $\displaystyle=-\beta
u_{1}(u_{3}+\delta(v_{2}+u_{2}))\;.$

Setting $u_{1}=0$ we conclude that for some $\mu$, $u_{3}+2\delta u_{2}=\mu
u_{1}$. Therefore,

$\displaystyle v_{2}(\delta(v_{2}+u_{2})+u_{3})$ $\displaystyle=-\beta
u_{1}(u_{3}+\delta(v_{2}+u_{2}))$ $\displaystyle u_{3}(v_{2}+\beta u_{1})$
$\displaystyle=-\delta(v_{2}+u_{2})(v_{2}+\beta u_{1})\;.$

As $v_{2}\not\sim u_{1}$ it follows that

$\displaystyle\mu u_{1}-2\delta u_{2}$
$\displaystyle=u_{3}=-\delta(v_{2}+u_{2})$ $\displaystyle\mu u_{1}$
$\displaystyle=\delta(u_{2}-v_{2})=-\delta^{2}u_{1}$

Hence, $\delta^{2}+\mu=0$. Therefore,

$\displaystyle u_{1}u^{\prime}$ $\displaystyle=u_{1}u+u_{1}u_{3}$
$\displaystyle=u_{1}u-\delta^{2}u_{1}^{2}-2\delta u_{1}u_{2}$
$\displaystyle=u_{1}u-v_{2}^{2}+u_{2}^{2}\;.$

Rearranging we get $Q^{\prime}=u_{1}u^{\prime}-u_{2}^{2}=u_{1}u-v_{2}^{2}=Q$,
in contradiction. ∎

We finish this section by formulating the improvement for Theorem 1.13 which
follows immediately from 4.1

######  Corollary 4.10 (Improvement of Theorem 1.10 of [42]).

Let $A,B$ and $C$ be $n$-variate, homogeneous, quadratic polynomials, over
$\mathbb{C}$, such that $C\in\sqrt{\left\langle{A,B}\right\rangle}$. Then, one
of the following cases must hold:

  1. (i)

$C$ is in the linear span of $A$ and $B$.

  2. (ii)

There exists a non trivial linear combination of the form $\alpha A+\beta
B=\ell^{2}$ for some linear form $\ell$.

  3. (iii)

If none of the above hold, then there exist two linear forms $\ell_{1}$ and
$\ell_{2}$ such that $A,B,C\in\left\langle{\ell_{1},\ell_{2}}\right\rangle$.
Furthermore, we have that either $\text{Lin}(P)\subseteq\text{Lin}(Q)$ or

     * •

$A=\ell_{1}a+\ell_{2}^{2}$ for some linear form $a$.

     * •

$B=\ell_{1}b-\ell_{2}^{2}$ for some linear form $b$.

     * •

$C={\ell}_{2}(a+b)+\alpha A+\beta B$ for some constants
$\alpha,\beta\in\mathbb{C}$.

##  5 Robust Sylvester-Gallai theorem for quadratic polynomials.

We divide
${\mathcal{Q}}={\mathcal{Q}}_{1}\cup{\mathcal{Q}}_{2}\cup{\mathcal{Q}}_{3}$ as
following:

${\mathcal{Q}}_{1}=\left\\{Q\in{\mathcal{Q}}\;\middle|\;\begin{tabular}[]{@{}l@{}}Q
satisfies \autoref{thm:structure}\ref{case:span} with at least\\\ $\delta/100$
fraction of the polynomials in ${\mathcal{Q}}$\end{tabular}\right\\},$ (5.1)
${\mathcal{Q}}_{2}=\left\\{Q\in{\mathcal{Q}}\;\middle|\;\begin{tabular}[]{@{}l@{}}Q
satisfies \autoref{thm:structure}\ref{case:rk1} with at least\\\ $\delta/100$
fraction of the polynomials in ${\mathcal{Q}}$\end{tabular}\right\\},$ (5.2)
${\mathcal{Q}}_{3}=\left\\{Q\in{\mathcal{Q}}\;\middle|\;\begin{tabular}[]{@{}l@{}}Q
satisfies \autoref{thm:structure}\ref{case:2} with at least\\\ $\delta/100$
fraction of the polynomials in ${\mathcal{Q}}$\end{tabular}\right\\}.$ (5.3)

We will also use the following notation: Let $Q\in{\mathcal{Q}}$, and
$t\in\\{(i),(ii),(iii)\\}$ we denote

$\Gamma_{t}(Q)=\\{P\in{\mathcal{Q}}\mid Q,P\text{ satisfiy case t of
\autoref{thm:structure}}\\}\,.$

Finally we set
${\mathcal{Q}}_{1}={\mathcal{Q}}_{1}\setminus({\mathcal{Q}}_{2}\cup{\mathcal{Q}}_{3})$.
This implies that if $P\in{\mathcal{Q}}_{1}$ then at least a $\delta/100$
fraction of the polynomials in ${\mathcal{Q}}$ satisfy Theorem 1.13(i) with
$P$ and no other case.

######  Observation 5.4.

The definition of $\Gamma_{t}$ naturally defines an undirected graph with an
edge between $P$ and $Q$ if for some $t$, $Q\in\Gamma_{t}(P)$ (which is
equivalent to saying $P\in\Gamma_{t}(Q)$). Thus, when we speak of “edges” and
“neighbors” this graph is the one that we refer to.

Throughout the proof, we will use the following simple claim.

######  Claim 5.5.

Let $P,T\in{\mathcal{Q}}$. Removing $T$ from ${\mathcal{Q}}$, causes the
removal of at most two polynomials from $\Gamma_{(i)}(P)$, and this happens
only in the case that $P\in\Gamma_{(i)}(T)$ and
$|{\mathcal{Q}}\cap\operatorname{span}\\{{P,T}\\}|=3$.

###### Proof.

First, note that for $Q_{1},Q_{2},Q_{3}\in{\mathcal{Q}}$ if
$Q_{3}\in\operatorname{span}\\{{Q_{1},Q_{2}}\\}$, then for every $k\neq
j\in[3]$, $Q_{k}\in\Gamma_{(i)}(Q_{j})$. In particular, if
$P\not\in\Gamma_{(i)}(T)$, then removing $T$ from ${\mathcal{Q}}$ does not
affect $\Gamma_{(i)}(P)$.

Let $P\in\Gamma_{(i)}(T)$. By the argument above, if
$|{\mathcal{Q}}\cap\operatorname{span}\\{{P,T}\\}|>3$ then removing $T$ does
not affect $\Gamma_{(i)}(P)$. Thus, the only case the $\Gamma_{(i)}(P)$. is
affected is when $|{\mathcal{Q}}\cap\operatorname{span}\\{{P,T}\\}|=3$ and in
this case the third polynomial in the span is removed from $\Gamma_{(i)}(P)$.
∎

The proof of Theorem 1.9 is organized as follows. In Section 5.1 we bound the
dimension of ${\mathcal{Q}}_{2}$. Specifically, we prove the following claim.

######  Claim 5.6.

There exist a subset ${\mathcal{I}}\subseteq{\mathcal{Q}}_{2}$ of size
$|{\mathcal{I}}|=O({1}/{\delta})$, and a linear space of linear forms
$V^{\prime}$ such that $\dim(V^{\prime})=O({1}/{\delta^{2}})$ such that
${\mathcal{Q}}_{2}\subset\operatorname{span}\\{{{\mathcal{I}},\mathbb{C}[V^{\prime}]_{2}}\\}$.

In Section 5.2 We prove that for some small dimensional space
$V^{\prime\prime}$, it holds that
${\mathcal{Q}}_{3}\subset\left\langle{V^{\prime\prime}}\right\rangle$.

######  Claim 5.7.

There exists a linear space of linear forms, $V^{\prime\prime}$, such that
$\dim(V^{\prime\prime})=O({1}/{\delta})$ and
${\mathcal{Q}}_{3}\subset\left\langle{V^{\prime\prime}}\right\rangle$.

Set $V=V^{\prime}+V^{\prime\prime}$. So far it holds that
${\mathcal{Q}}_{2}\in\operatorname{span}\\{{{\mathcal{I}},\mathbb{C}[V]_{2}}\\}$
and ${\mathcal{Q}}_{3}\subset\left\langle{V}\right\rangle$. Next, we find a
small set of polynomials ${\mathcal{J}}$ such that
${\mathcal{Q}}\subset\left\langle{V}\right\rangle+\operatorname{span}\\{{{\mathcal{J}}}\\}$.
We prove this claim in Section 5.3.

######  Claim 5.8.

There exists a set ${\mathcal{J}}\subseteq{\mathcal{Q}}$, of size
$|{\mathcal{J}}|=O(1/\delta)$, such that
${\mathcal{Q}}\subset\operatorname{span}\\{{({\mathcal{Q}}\cap\left\langle{V}\right\rangle),{\mathcal{J}},\mathbb{C}[V]_{2}}\\}$.
Furthermore, if $P\in{\mathcal{Q}}\setminus\left\langle{V}\right\rangle$ then
there is no quadratic $L$ such that $P+L\in\left\langle{V}\right\rangle$ and
$\operatorname{rank}_{s}(L)\leq 2$.

Given the claims above we have that
${\mathcal{Q}}\subset\operatorname{span}\\{{({\mathcal{Q}}\cap\left\langle{V}\right\rangle),{\mathcal{J}},\mathbb{C}[V]_{2}}\\}$,
where $|{\mathcal{J}}|=O({1}/{\delta})$ and $\dim(V)=O({1}/{\delta^{2}})$. We
are not done yet as the dimension of $\left\langle{V}\right\rangle$, as a
vector space, is not a constant. To bound this dimension we partition
${\mathcal{Q}}$ to four sets and study the subgraphs induces by any two of the
sets.

$\displaystyle{\mathcal{C}}_{[V]}$
$\displaystyle=\left\\{Q\in{\mathcal{Q}}\;\middle|\;Q\in\mathbb{C}[V]_{2}\right\\}$
(5.9) $\displaystyle{\mathcal{C}}_{\left\langle{V}\right\rangle}$
$\displaystyle=\left\\{Q\in{\mathcal{Q}}\;\middle|\;Q\in\left\langle{V}\right\rangle\right\\}\setminus{\mathcal{C}}_{[V]}$
(5.10) $\displaystyle{\mathcal{J}}_{[V]}$
$\displaystyle=\left\\{Q\in{\mathcal{Q}}\;\middle|\;Q\in\operatorname{span}\\{{{\mathcal{J}},\mathbb{C}[V]_{2}}\\}\setminus\mathbb{C}[V]_{2}\right\\}$
(5.11) $\displaystyle{\mathcal{J}}_{\left\langle{V}\right\rangle}$
$\displaystyle=\left\\{Q\in{\mathcal{Q}}\;\middle|\;Q\in\operatorname{span}\\{{{\mathcal{J}},\left\langle{V}\right\rangle}\\}\setminus\left\langle{V}\right\rangle\right\\}\setminus{\mathcal{J}}_{[V]}\;.$
(5.12)

In words, ${\mathcal{C}}_{[V]}$ is the set of all quadratics in
${\mathcal{Q}}$ that only depend on linear functions in $V$.
${\mathcal{C}}_{\left\langle{V}\right\rangle}$ is the set of polynomials that
are in $\left\langle{V}\right\rangle$ but not in ${\mathcal{C}}_{[V]}$, etc.

Our goal is to bound the dimension of each of these sets. In fact, we already
know that $\dim({\mathcal{C}}_{[V]}),\dim({\mathcal{J}}_{[V]})\leq
O(1/\delta^{4})$ so we only need to bound
$\dim({\mathcal{C}}_{\left\langle{V}\right\rangle})$ and
$\dim({\mathcal{J}}_{\left\langle{V}\right\rangle})$. For that we will analyze
the edges between the different sets.

We first note that the “furthermore” part of 5.8, stating that the “rank-
distance” between nonzero polynomials in
$\operatorname{span}\\{{{\mathcal{J}}}\\}$ and quadratics in
$\left\langle{V}\right\rangle$ is larger than $2$, implies the following:

######  Observation 5.13.

  1. 1.

If $P\in{\mathcal{C}}_{\left\langle{V}\right\rangle}\cup{\mathcal{C}}_{[V]}$
and $Q\in{\mathcal{J}}_{\left\langle{V}\right\rangle}\cup{\mathcal{J}}_{[V]}$
satisfy that $P\in\Gamma(Q)$ then $P$ and $Q$ satisfy Theorem 1.13(i).

  2. 2.

If $P\in{\mathcal{J}}_{\left\langle{V}\right\rangle}$ and
$Q\in{\mathcal{C}}_{\left\langle{V}\right\rangle}\cup{\mathcal{C}}_{[V]}\cup{\mathcal{J}}_{[V]}$
satisfy that $P\in\Gamma(Q)$ then $P$ and $Q$ satisfy Theorem 1.13(i).

###### Proof.

We only prove the first case as the proof of the second case is similar. As
$Q\in{\mathcal{J}}_{\left\langle{V}\right\rangle}\cup{\mathcal{J}}_{[V]}$, we
have that $\operatorname{rank}_{s}(Q_{1})>2$. In particular, $P$ and $Q$ do
not satisfy Theorem 1.13(iii). If $P$ and $Q$ satisfy Theorem 1.13(ii) then
$Q=\alpha P+\ell^{2}$ for some linear form $\ell$, which contradicts the
structure of ${\mathcal{J}}$ guaranteed in 5.8. ∎

To bound the dimension of ${\mathcal{C}}_{\left\langle{V}\right\rangle}$ we
note that any edge going from
$P\in{\mathcal{C}}_{\left\langle{V}\right\rangle}\cup{\mathcal{J}}_{\left\langle{V}\right\rangle}$
to ${\mathcal{C}}_{[V]}\cup{\mathcal{J}}_{[V]}$ defines uniquely a third
polynomial in
${\mathcal{C}}_{\left\langle{V}\right\rangle}\cup{\mathcal{J}}_{\left\langle{V}\right\rangle}$.
This uniqueness property guarantees that if we add $\text{Lin}(P)$ to $V$,
then many polynomials move from
${\mathcal{C}}_{\left\langle{V}\right\rangle}\cup{\mathcal{J}}_{\left\langle{V}\right\rangle}$
to ${\mathcal{C}}_{[V]}\cup{\mathcal{J}}_{[V]}$.

######  Claim 5.14.

Let $P\in{\mathcal{C}}_{\left\langle{V}\right\rangle}$ then,

  1. 1.

for every polynomial $Q_{1}\in\Gamma(P)\cap{\mathcal{J}}_{[V]}$ there is a
unique polynomial
$Q^{\prime}_{1}\in{\mathcal{J}}_{\left\langle{V}\right\rangle}$ such that
$Q^{\prime}_{1}\in\operatorname{span}\\{{P,Q_{1}}\\}$. I.e., there is no other
$Q_{2}\in{\mathcal{J}}_{[V]}$ such that
$Q^{\prime}_{1}\in\operatorname{span}\\{{P,Q_{2}}\\}$.

  2. 2.

for every polynomial $Q_{1}\in\Gamma(P)\cap{\mathcal{C}}_{[V]}$ there is a
unique polynomial
$Q^{\prime}_{1}\in{\mathcal{C}}_{\left\langle{V}\right\rangle}$ such that
$Q^{\prime}_{1}\in\sqrt{\left\langle{P,Q_{1}}\right\rangle}$. I.e., there is
no other $Q_{2}\in{\mathcal{C}}_{[V]}$ such that
$Q^{\prime}_{1}\in\sqrt{\left\langle{P,Q_{2}}\right\rangle}$.

###### Proof.

  1. 1.

Let $Q_{1}\in\Gamma(P)\cap{\mathcal{J}}_{[V]}$. By Observation 5.13, $P$ and
$Q_{1}$ satisfy Theorem 1.13(i). We first prove that they span a polynomial in
${\mathcal{J}}_{\left\langle{V}\right\rangle}$ and then prove its uniqueness.
Any polynomial in
$T\in\operatorname{span}\\{{P,Q_{1}}\\}\setminus(\operatorname{span}\\{{P}\\})$
has $\operatorname{rank}_{s}(T)>2$, even when setting the linear forms in $V$
to $0$. Hence, $P$ and $Q_{1}$ span a polynomial
$Q^{\prime}_{1}\in{\mathcal{J}}_{[V]}\cup{\mathcal{J}}_{\left\langle{V}\right\rangle}$.
As $P\not\in\mathbb{C}[V]_{2}$ we can conclude that
$Q^{\prime}_{1}\in{\mathcal{J}}_{\left\langle{V}\right\rangle}$. To prove that
$Q^{\prime}_{1}$ is unique assume that
$Q^{\prime}_{1}\in\operatorname{span}\\{{P,Q_{2}}\\}$ for some
$Q_{2}\in{\mathcal{J}}_{[V]}$. Pairwise linear independence implies that
$P\in\operatorname{span}\\{{Q_{1},Q_{2}}\\}$ which implies that
$P\in{\mathcal{C}}_{[V]}$, in contradiction.

  2. 2.

Follows from 4.4.

∎

######  Claim 5.15.

Let $P\in{\mathcal{J}}_{\left\langle{V}\right\rangle}$. Then for every
polynomial $Q_{1}\in\Gamma(P)\cap({\mathcal{J}}_{[V]}\cup{\mathcal{C}}_{[V]})$
there is a unique polynomial
$Q^{\prime}_{1}\in{\mathcal{J}}_{\left\langle{V}\right\rangle}\cup{\mathcal{C}}_{\left\langle{V}\right\rangle}$
such that $Q^{\prime}_{1}\in\operatorname{span}\\{{P,Q_{1}}\\}$. By “unique”
we mean that there is no other $Q_{2}\in{\mathcal{J}}_{[V]}$ such that
$Q^{\prime}_{1}\in\operatorname{span}\\{{P,Q_{2}}\\}$.

###### Proof.

We first consider the case $Q_{1}\in\Gamma(P)\cap{\mathcal{C}}_{[V]}$.
Observation 5.13 implies that $P$ and $Q_{1}$ satisfy Theorem 1.13(i). By
construction of ${\mathcal{J}}$, any polynomial in
$T\in\operatorname{span}\\{{P,Q_{1}}\\}\setminus(\operatorname{span}\\{{Q_{1}}\\})$
has $\operatorname{rank}_{s}(T)>2$, even when setting the linear forms in $V$
to $0$. Hence, $P$ and $Q_{1}$ span a polynomial
$Q^{\prime}_{1}\in{\mathcal{J}}_{[V]}\cup{\mathcal{J}}_{\left\langle{V}\right\rangle}$.
As $P\not\in{\mathcal{J}}_{[V]}$ we conclude that
$Q^{\prime}_{1}\in{\mathcal{J}}_{\left\langle{V}\right\rangle}$. To prove that
$Q^{\prime}_{1}$ is unique assume that
$Q^{\prime}_{1}\in\operatorname{span}\\{{P,Q_{2}}\\}$ for some
$Q_{2}\in{\mathcal{J}}_{[V]}\cup{\mathcal{C}}_{[V]}$. As before, pairwise
linear independence shows that $P\in\operatorname{span}\\{{Q_{1},Q_{2}}\\}$,
which implies that $P\in{\mathcal{J}}_{[V]}$, in contradiction.

Consider the case $Q_{1}\in\Gamma(P)\cap{\mathcal{J}}_{[V]}$. As before, $P$
and $Q_{1}$ must satisfy Theorem 1.13(i). Any polynomial in
$T\in\operatorname{span}\\{{P,Q_{1}}\\}\setminus(\operatorname{span}\\{{Q_{1}}\\})$
is not in ${\mathcal{J}}_{[V]}\cup{\mathcal{C}}_{[V]}$. Hence, $P$ and $Q_{1}$
span a polynomial
$Q^{\prime}_{1}\in{\mathcal{C}}_{\left\langle{V}\right\rangle}\cup{\mathcal{J}}_{\left\langle{V}\right\rangle}$.
Uniqueness follows exactly as in the first case. ∎

We next show that the uniqueness property proved in Claims 5.14 and 5.15 imply
that ${\mathcal{J}}_{\left\langle{V}\right\rangle}$ and
${\mathcal{C}}_{\left\langle{V}\right\rangle}$ cannot be “too small,” unless
they are empty.

######  Claim 5.16.

If
$|{\mathcal{J}}_{\left\langle{V}\right\rangle}|,|{\mathcal{C}}_{\left\langle{V}\right\rangle}|\leq(\delta/10)\cdot
m$, then
${\mathcal{J}}_{\left\langle{V}\right\rangle}={\mathcal{C}}_{\left\langle{V}\right\rangle}=\emptyset$.

###### Proof.

Assume towards a contradiction that there is
$P\in{\mathcal{C}}_{\left\langle{V}\right\rangle}\cup{\mathcal{J}}_{\left\langle{V}\right\rangle}$.
As $|\Gamma(P)|\geq\delta m$ it follows that
$|\Gamma(P)\cap({\mathcal{C}}_{[V]}\cup{\mathcal{J}}_{[V]})|\geq(8\delta/10)\cdot
m$. Claims 5.14 and 5.15 imply that there are at least
$|\Gamma(P)\cap({\mathcal{C}}_{[V]}\cup{\mathcal{J}}_{[V]})|\geq 8\delta/10$
polynomials in
${\mathcal{J}}_{\left\langle{V}\right\rangle}\cup{\mathcal{C}}_{\left\langle{V}\right\rangle}$
in contradiction to the assumption that there are at most $(2\delta/10)\cdot
m$ polynomials in
${\mathcal{J}}_{\left\langle{V}\right\rangle}\cup{\mathcal{C}}_{\left\langle{V}\right\rangle}$.
∎

Thus, if we can
make$|{\mathcal{J}}_{\left\langle{V}\right\rangle}|,|{\mathcal{C}}_{\left\langle{V}\right\rangle}|\leq(\delta/10)\cdot
m$ without increasing $\dim(V)$ and $|{\mathcal{J}}|$ too much then 5.16 would
imply that
${\mathcal{Q}}\in\operatorname{span}\\{{{\mathcal{J}},\mathbb{C}[V]_{2}}\\}$,
from which the theorem would follow. We first show how to reduce
$|{\mathcal{C}}_{\left\langle{V}\right\rangle}|$ and then we reduce
$|{\mathcal{J}}_{\left\langle{V}\right\rangle}|$. We will need the following
easy observation.

######  Claim 5.17.

There is a linear subspace $V\subseteq V^{\prime}$, of dimension
$\dim(V^{\prime})\leq 1/\delta^{4}\cdot\dim(V)\leq 1/\delta^{6}$, such that
$|{\mathcal{C}}_{\left\langle{V^{\prime}}\right\rangle}|\leq\delta/10\cdot m$.

###### Proof.

Denote
${\mathcal{B}}_{1}=\\{Q\in{\mathcal{C}}_{\left\langle{V}\right\rangle}\mid|\Gamma(Q)\cap({\mathcal{J}}_{\left\langle{V}\right\rangle}\cup{\mathcal{J}}_{[V]})|\geq
0.1\delta m\\}$ and
${\mathcal{B}}_{2}={\mathcal{C}}_{\left\langle{V}\right\rangle}\setminus{\mathcal{B}}_{1}$.
We first bound the dimension of ${\mathcal{B}}_{2}$.

######  Claim 5.18.

$\dim(\text{Lin}({\mathcal{B}}_{2}))=O(1/\delta\cdot\dim(V))$.

###### Proof.

For each $Q\in{\mathcal{B}}_{2}$ we remove from $\Gamma(Q)$ all the
polynomials from
${\mathcal{J}}_{\left\langle{V}\right\rangle}\cup{\mathcal{J}}_{[V]}$. This
removes at most $0.1\delta m$ polynomials from $\Gamma(Q)$. From 5.14 we know
that $Q$ satisfies Theorem 1.13(i) with each of them, and the resulting
polynomial must have high-rank and thus it is not in
${\mathcal{C}}_{\left\langle{V}\right\rangle}\cup{\mathcal{C}}_{\left\langle{V}\right\rangle}$.
It follows that each $Q\in{\mathcal{B}}_{2}$ has at least $0.9\delta m$
neighbors $Q^{\prime}$ such that the third polynomial (the one in
$\sqrt{\left\langle{Q,Q^{\prime}}\right\rangle}$) belongs to
${\mathcal{C}}_{[V]}\cup{\mathcal{C}}_{\left\langle{V}\right\rangle}$.

Let $Q_{i}\in{\mathcal{B}}_{2}$. Observe that a polynomial from
${\mathcal{B}}_{2}$ and a polynomial from ${\mathcal{B}}_{1}$ can only satisfy
Theorem 1.13(i) or Theorem 1.13(iii). Indeed, if they satisfy Theorem 1.13(ii)
then the spanned $\ell^{2}$ must belong to $V$ and we get that
$Q_{i}\in{\mathcal{C}}_{[V]}$, in contradiction.

Consider now the map $T_{V,{\boldsymbol{\alpha}}}$, for a random
${\boldsymbol{\alpha}}$, as in 2.12. It maps all polynomials
$Q_{i}\in{\mathcal{C}}_{\left\langle{V}\right\rangle}\cup{\mathcal{C}}_{[V]}$
to polynomials of the form $T(Q_{i})=z\ell_{i}$ for some linear form
$\ell_{i}$. Pairwise independence and 2.19 guaranty that if $Q_{i}\neq
Q_{j}\in{\mathcal{C}}_{\left\langle{V}\right\rangle}$ then
$\ell_{i}\not\sim\ell_{j}$. Denote
$T_{V,{\boldsymbol{\alpha}}}({\mathcal{B}}_{2})=\\{\ell_{i}\mid\exists
Q_{i}\in{\mathcal{B}}_{2},T_{V,{\boldsymbol{\alpha}}}(Q_{i})=z\ell_{i}\\}$. To
prove the claim we show that $T_{V,{\boldsymbol{\alpha}}}({\mathcal{B}}_{2})$
satisfies the conditions of Theorem 3.1. This implies that
$\dim(T_{V,{\boldsymbol{\alpha}}}({\mathcal{B}}_{2}))\leq O(1/\delta)$. The
claim then follows from 2.21.

If $|\Gamma_{\ref{case:span}}(Q_{i})\cap{\mathcal{C}}_{[V]}|>\delta m/20$ then
5.14 implies that there are more than $\delta m/20$ polynomials in
${\mathcal{C}}_{\left\langle{V}\right\rangle}\cap\operatorname{span}\\{{Q_{i},\mathbb{C}[V]_{2}}\\}$.
Similarly, if $|\Gamma_{\ref{case:2}}(Q_{i})\cap{\mathcal{C}}_{[V]}|>\delta
m/20$ then 4.1 implies that there are at least $\delta m/20$ unique
polynomials in ${\mathcal{C}}_{\left\langle{V}\right\rangle}$ that are in
$\mathbb{C}[V+\text{Lin}(Q_{i})]_{2}$. In either cases, there are at least
$\delta m/20$ different polynomials in
${\mathcal{C}}_{\left\langle{V}\right\rangle}\cap\mathbb{C}[V+\text{Lin}(Q_{i})]_{2}$.

The previous argument implies that for $Q_{i}\in{\mathcal{B}}_{2}$, if
$|\Gamma(Q_{i})\cap{\mathcal{C}}_{[V]}|>\delta m/10$ then there are at least
$\delta m/20$ different polynomials in
${\mathcal{C}}_{\left\langle{V}\right\rangle}\cap\mathbb{C}[V+\text{Lin}(Q_{i})]_{2}$.
It follows that $\operatorname{span}\\{{\ell_{i},z}\\}$ contains at least
$\delta m/20$ of the other $\ell_{j}$, each of them is no a multiple of $z$
(as they come from polynomials in
${\mathcal{C}}_{\left\langle{V}\right\rangle}$). Thus, there are at most
$20/\delta$ such $\ell_{i}$s that are linearly independent modulo $z$ (i,e,
that their projections on $\operatorname{span}\\{{z}\\}^{\perp}$ are linearly
independent). Denote their span by $W$ (thus $\dim(W)\leq 20/\delta$) and
update
$T_{V,{\boldsymbol{\alpha}}}({\mathcal{B}}_{2})=T_{V,{\boldsymbol{\alpha}}}({\mathcal{B}}_{2})\setminus
W$. Next, remove all edges between polynomials in
$T_{V,{\boldsymbol{\alpha}}}({\mathcal{B}}_{2})$ and
$T_{V,{\boldsymbol{\alpha}}}({\mathcal{B}}_{1})$. This removes at most
$2\delta m/10$ neighbors for each $Q_{i}\in{\mathcal{B}}_{2}$ (uniqueness
implies that each $Q\in{\mathcal{C}}_{[V]}$ can affect the removal of at most
two edges as in 5.5).

At this point we clearly have that for every $Q_{i}\in{\mathcal{B}}_{2}$,
$|\Gamma(T_{V,{\boldsymbol{\alpha}}}(Q_{i}))\cap
T_{V,{\boldsymbol{\alpha}}}({\mathcal{B}}_{2})|>\delta m/2$. Therefore, the
set $\\{z,T_{V,{\boldsymbol{\alpha}}}({\mathcal{B}}_{2})\\}$ satisfies the
condition of Theorem 3.1 with $W=\operatorname{span}\\{{W,z}\\}$ and
${\mathcal{W}}=W\cap T_{V,{\boldsymbol{\alpha}}}({\mathcal{B}}_{2})$. It
follows that $\dim(T_{V,{\boldsymbol{\alpha}}}({\mathcal{B}}_{2}))\leq
O(\dim(W)+1/\delta)=O(1/\delta)$. 2.21 implies that
$\dim(\text{Lin}({\mathcal{B}}_{2}))=O(1/\delta\cdot\dim(V))$. ∎

We next bound $|{\mathcal{B}}_{1}|$. Assume that
$|{\mathcal{B}}_{1}|\geq\delta/10\cdot m$. It follows that at least
$\frac{\delta^{2}}{100}m^{2}$ edges have one side in ${\mathcal{B}}_{1}$ and
the other in
${\mathcal{J}}_{\left\langle{V}\right\rangle}\cup{\mathcal{J}}_{[V]}$. Set
${\mathcal{B}}^{\prime}_{1}=\emptyset$. The combination of 5.13 and 3.2 with
${\mathcal{B}}={\mathcal{B}}_{1}$ (and $\varepsilon=\delta^{2}/100$) imply
that there is a subset ${\mathcal{B}}^{\prime}\subseteq{\mathcal{B}}_{1}$ of
size $O(m/\delta^{2})$ and dimension $O({1}/{\delta^{2}})$. Set
${\mathcal{B}}^{\prime}_{1}={\mathcal{B}}^{\prime}_{1}\cup{\mathcal{B}}^{\prime}$,
${\mathcal{B}}_{1}={\mathcal{B}}_{1}\setminus{\mathcal{B}}^{\prime}_{1}$ and
repeat this again (i.e. move a set of size $O(m/\delta^{2})$ and dimension
$O({1}/{\delta^{2}})$ from ${\mathcal{B}}_{1}$ to
${\mathcal{B}}^{\prime}_{1}$). As in each step we remove at least
$\Omega({\delta^{2}}m)$ polynomials from ${\mathcal{B}}_{1}$, this process
must terminate after $O({1}/{\delta^{2}})$ many iterations. Thus, when the
process terminates, $|{\mathcal{B}}_{1}|\leq\delta/10\cdot m$ and
$\dim({\mathcal{B}}^{\prime}_{1})\leq O(1/\delta^{2}\cdot
1/\delta^{2})=O(1/\delta^{4})$. Hence,
$\dim(\text{Lin}({\mathcal{B}}^{\prime}_{1}))\leq
O(1/\delta^{4}\cdot\dim(V))$.

We are now ready to define $V^{\prime}$. Let
$V^{\prime}=\text{Lin}({\mathcal{B}}_{2})+\text{Lin}({\mathcal{B}}^{\prime}_{1})+V$.
By 5.18 $\dim(\text{Lin}({\mathcal{B}}_{2}))=O(1/\delta\cdot\dim(V))$, and as
we just proved, $\dim(\text{Lin}({\mathcal{B}}^{\prime}_{1}))\leq
O(1/\delta^{4}\cdot\dim(V))$. Thus, $\dim(V^{\prime})\leq
O(1/\delta^{4}\cdot\dim(V))$. It is also clear that now
${\mathcal{B}}_{2}\in\mathbb{C}[V]_{2}$ and that
$|{\mathcal{B}}_{1}|\leq\delta m/10$, as claimed. ∎

Note that it may now be the case that some linear combination of polynomials
in ${\mathcal{J}}$ is now “close” to $V^{\prime}$. We therefore perform the
following simple process (as in the proof of the “furthermore” part in Section
5.3): if $Q\in\operatorname{span}\\{{{\mathcal{J}}}\\}$ is such that for some
quadratic $L$ of $\operatorname{rank}(L)=2$ we have that
$P+L\in\left\langle{V^{\prime}}\right\rangle$ then we can add $\text{Lin}(L)$
to $V^{\prime}$ and remove one polynomial from ${\mathcal{J}}$ while still
maintaining that
${\mathcal{Q}}\subset\operatorname{span}\\{{({\mathcal{Q}}\cap\left\langle{V^{\prime}}\right\rangle),{\mathcal{J}},\mathbb{C}[V^{\prime}]_{2}}\\}$.
As $|{\mathcal{J}}|=O(1/\delta)$, this does not have much affect on the
dimension of $V^{\prime}$, which is still $O(1/\delta^{4}\cdot\dim(V))$.

To simplify notation, we denote with $V$ the linear space guaranteed by 5.17.
As $V$ may have changed, we update the sets ${\mathcal{C}}_{[V]}$,
${\mathcal{C}}_{\left\langle{V}\right\rangle}$, ${\mathcal{J}}_{[V]}$ and
${\mathcal{J}}_{\left\langle{V}\right\rangle}$ accordingly. By construction of
$V=V^{\prime}$, we now have that
$|{\mathcal{C}}_{\left\langle{V}\right\rangle}|\leq\delta/100m$.

We now complete the proof of Theorem 1.9 by bounding the dimension of
${\mathcal{J}}_{\left\langle{V}\right\rangle}$.

######  Claim 5.19.

There is a set
${\mathcal{J}}\subseteq{\mathcal{J}}^{\prime}\subset{\mathcal{Q}}$ such that
$|{\mathcal{J}}^{\prime}|\leq|{\mathcal{J}}|+O(1/\delta)$ and
$\dim({\mathcal{J}}^{\prime}_{\left\langle{V}\right\rangle})\leq
O({1}/{\delta}+\dim(V)^{2})$.

###### Proof.

Denote ${\mathcal{T}}_{1}=\\{Q\in{\mathcal{J}}\mid|\Gamma_{(ii)}(Q)|\geq
0.1\delta m\\}$ and
${\mathcal{T}}_{2}={\mathcal{J}}_{\left\langle{V}\right\rangle}\setminus{\mathcal{T}}_{1}$.
For every polynomial in $Q\in{\mathcal{J}}_{\left\langle{V}\right\rangle}$,
denote $Q=Q_{{\mathcal{J}}}+Q_{\left\langle{V}\right\rangle}$ where
$Q_{{\mathcal{J}}}\in\operatorname{span}\\{{{\mathcal{J}}}\\}$ and
$Q_{\left\langle{V}\right\rangle}\in\left\langle{V}\right\rangle$. Note that
neither $Q_{{\mathcal{J}}}$ nor $Q_{\left\langle{V}\right\rangle}$ can be zero
as this would imply
$Q\in{\mathcal{J}}_{[V]}\cup{\mathcal{C}}_{\left\langle{V}\right\rangle}$.

######  Claim 5.20.

There is a subset ${\mathcal{T}}^{\prime}_{1}\subseteq{\mathcal{T}}_{1}$ of
size at most $10/\delta$ such that
${\mathcal{T}}_{1}\subset\operatorname{span}\\{{{\mathcal{T}}^{\prime}_{1},{\mathcal{J}},\mathbb{C}[V]_{2}}\\}$.

###### Proof.

Let $Q_{1}\neq Q_{2}\in{\mathcal{T}}_{1}$. If
$P\in\Gamma_{\ref{case:rk1}}(Q_{1})\cap\Gamma_{\ref{case:rk1}}(Q_{2})$ then
$P=Q_{1}+\ell_{1}^{2}=\alpha_{2}Q_{2}+\ell_{2}^{2}$, for some
$0\neq\alpha_{2}\in\mathbb{C}$ and linear functions $\ell_{i}$. As no
polynomial in $\operatorname{span}\\{{{\mathcal{J}}}\\}$ is at “rank-distance”
two from $\left\langle{V}\right\rangle$, it follows that
$P\in\left({\mathcal{Q}}\cap\left(\operatorname{span}\\{{{\mathcal{J}},\left\langle{V}\right\rangle}\\}\setminus{\left\langle{V}\right\rangle}\right)\right)$.
Denote $P=P_{{\mathcal{J}}}+P_{\left\langle{V}\right\rangle}$ where $0\neq
P_{{\mathcal{J}}}\in\operatorname{span}\\{{{\mathcal{J}}}\\}$ and
$P_{\left\langle{V}\right\rangle}\in\left\langle{V}\right\rangle$. Thus
$P_{{\mathcal{J}}}-{Q_{1}}_{{\mathcal{J}}}={Q_{1}}_{\left\langle{V}\right\rangle}-P_{\left\langle{V}\right\rangle}+\ell_{1}^{2}$.
As there is no linear combination of polynomials in ${\mathcal{J}}$ that has
$\operatorname{rank}_{s}\leq 2$ when setting $V=0$, we conclude that
$P_{{\mathcal{J}}}-{Q_{1}}_{{\mathcal{J}}}=0$ and thus $\ell_{1}\in V$.
Similarly, can show that $\ell_{2}\in V$. Thus,
$Q_{2}\in\operatorname{span}\\{{Q_{1},\mathbb{C}[V]_{2}}\\}$.

Let ${\mathcal{T}}^{\prime}_{1}\subseteq{\mathcal{T}}_{1}$ be a maximal subset
(with respect to inclusion) that has the property that for every pair of
polynomials $Q_{1},Q_{2}\in{\mathcal{T}}^{\prime}_{!}$ it holds that
$\Gamma_{{\ref{case:rk1}}}(Q_{1})\cap\Gamma_{\ref{case:rk1}}(Q_{2})=\emptyset$.
By the argument above,
${\mathcal{T}}_{1}\subset\operatorname{span}\\{{{\mathcal{T}}^{\prime}_{1},\mathbb{C}[V]_{2}}\\}$.
The assumption that every $Q_{i}\in{\mathcal{T}}_{1}$ satisfies
$|\Gamma_{\ref{case:rk1}}(Q)|\geq\delta/10m$ implies that
$|{\mathcal{T}}^{\prime}_{1}|\leq 10/\delta$, as claimed. ∎

Set
${\mathcal{T}}_{2}={\mathcal{T}}_{2}\setminus\operatorname{span}\\{{{\mathcal{T}}_{1},{\mathcal{J}},\mathbb{C}[V]_{2}}\\}$.
Every $Q\in{\mathcal{T}}_{2}$ must now satisfy that
$|\Gamma_{\ref{case:span}}(Q)|\geq 0.9\delta m$. Indeed, this follows from the
fact that $Q\not\in{\mathcal{T}}_{1}$ and that it cannot satisfy Theorem
1.13(iii) with any polynomial. Remove from $\Gamma_{\ref{case:span}}(Q)$ all
the polynomials in ${\mathcal{B}}_{1}$, this removes at most
$2|{\mathcal{B}}_{1}|\leq 2/10\delta m$ polynomials from
$\Gamma_{\ref{case:span}}(Q)$ (using an argument similar to 5.5), leaving
$|\Gamma_{(i)}(Q)|\geq 0.7\delta m$. This implies that
${\mathcal{K}}={\mathcal{T}}_{2}$,
$W=\operatorname{span}\\{{{\mathcal{T}}_{1},{\mathcal{J}},\mathbb{C}[V]_{2}}\\}$
and
${\mathcal{W}}={\mathcal{Q}}\cap\operatorname{span}\\{{{\mathcal{T}}_{1},{\mathcal{J}},\mathbb{C}[V]_{2}}\\}$
satisfy the conditions of Theorem 3.1. As $\dim(W)\leq O(\dim(V)^{2})$ it
follows that $\dim({\mathcal{J}}_{\left\langle{V}\right\rangle})\leq
O({1}/{\delta}+\dim(V)^{2})$.

Setting ${\mathcal{J}}^{\prime}={\mathcal{T}}^{\prime}_{1}\cup{\mathcal{J}}$
completes the proof. ∎

We now put everything together and prove Theorem 1.9.

###### Proof of Theorem 1.9.

Claims 5.6, 5.7 and 5.8 imply that there exists a set
${\mathcal{J}}\subseteq{\mathcal{Q}}$, of size $|{\mathcal{J}}|=O(1/\delta)$,
and a subspace of linear functions $V$ of dimension $\dim(V)=O(1/\delta^{2})$
such that
${\mathcal{Q}}\subset\operatorname{span}\\{{({\mathcal{Q}}\cap\left\langle{V}\right\rangle),{\mathcal{J}},\mathbb{C}[V]_{2}}\\}$.

By Claims 5.17 and 5.19 there are
${\mathcal{J}}\subseteq{\mathcal{J}}^{\prime}$ and $V\subseteq V^{\prime}$
such that $\dim(V^{\prime})\leq 1/\delta^{4}\cdot\dim(V)\leq 1/\delta^{6}$ and
$|{\mathcal{J}}^{\prime}|=O(1/\delta)$, for which it holds that
$|{\mathcal{C}}_{\left\langle{V^{\prime}}\right\rangle}|\leq\delta/10\cdot m$
and $\dim({\mathcal{J}}^{\prime}_{\left\langle{V}\right\rangle})\leq
O({1}/{\delta}+\dim(V)^{2})=O(1/\delta^{8})$. We now set
${\mathcal{J}}={\mathcal{J}}^{\prime}$, $V=V^{\prime}$ and, if needed, we add
$O(|{\mathcal{J}}|)$ linear functions to $V$ to make sure that no non-trivial
linear combination of polynomials in ${\mathcal{J}}$ is of the form $L+F(V)$
where $\operatorname{rank}_{s}(L)\leq 2$ and $F\in\mathbb{C}[V]_{2}$, we
obtain that ${\mathcal{J}}_{\left\langle{V}\right\rangle}=\emptyset$ and
$|{\mathcal{C}}_{\left\langle{V}\right\rangle}|\leq\delta m/10$. Claim 5.16
now guarantees that we also have that
${\mathcal{C}}_{\left\langle{V}\right\rangle}=\emptyset$. Hence,
${\mathcal{Q}}={\mathcal{C}}_{[V]}\cup{\mathcal{J}}_{[V]}$ and it follows that
$\dim(\operatorname{span}\\{{{\mathcal{Q}}}\\})\leq|{\mathcal{J}}|+\dim(V)^{2}=O(1/\delta^{16})$.
∎

###  5.1 Poof of Claim 5.6

Here we study a special case in which the set of polynomials is the union of
two sets such that each polynomial from the first set satisfies Theorem
1.13(ii) with $\delta$ fraction of the polynomials in the second set. The
Claim below clearly implies 5.6.

######  Claim 5.21.

Let $\delta\in(0,1]$. Let ${\mathcal{A}}$ and ${\mathcal{B}}$ be two sets of
irreducible quadratic polynomials such that the polynomials in
${\mathcal{A}}\cup{\mathcal{B}}$ are pairwise linearly independent. Assume
further that for every $Q\in{\mathcal{A}}$ the set
$\Gamma(Q)=\\{P\in{\mathcal{B}}\mid P\text{ and }Q\text{ satisfy
}\autoref{thm:structure}\ref{case:rk1}\\}$ has size
$|\Gamma(Q)|\geq\delta\cdot|{\mathcal{B}}|$. Then, there is a subset
${\mathcal{I}}\subseteq{\mathcal{A}}$ of size
$|{\mathcal{I}}|=O(\frac{1}{\delta})$, and a linear space of linear forms $V$
with $\dim(V)=O\left({1}/{\delta^{2}}\right)$, such that
${\mathcal{A}}\subset\operatorname{span}\\{{{\mathcal{I}},\mathbb{C}[V]_{2}}\\}$.

###### Proof.

Let ${\mathcal{I}}\subseteq{\mathcal{A}}$ be defined as a maximal set of
polynomials in ${\mathcal{A}}$ that satisfy the following condition: For every
$Q\in{\mathcal{I}}$ there is at most one polynomial $P\in\Gamma(Q)$ such that
$P\in\Gamma(Q^{\prime})\cap\Gamma(Q^{\prime\prime})$ for two other polynomials
$Q^{\prime},Q^{\prime\prime}\in{\mathcal{I}}\setminus\\{Q\\}$. In other words,
for every polynomial $Q$ in ${\mathcal{I}}$ there is at most one polynomial
$P\in\Gamma(Q)$ that satisfies Theorem 1.13(ii) with (at least) two other
polynomials in ${\mathcal{I}}$.

######  Claim 5.22.

For every such ${\mathcal{I}}$ it holds that
$|{\mathcal{I}}|<\frac{6}{\delta}$.

###### Proof.

We start with four buckets of polynomials ${\mathcal{B}}_{0}={\mathcal{B}}$
and ${\mathcal{B}}_{1}={\mathcal{B}}_{2}={\mathcal{B}}_{3}=\emptyset$. Let us
add the polynomials to ${\mathcal{I}}$ one by one. When adding $Q$ to
${\mathcal{I}}$, we move the polynomials in $\Gamma(Q)$ from
${\mathcal{B}}_{i}$ to ${\mathcal{B}}_{i+1}$ (unless they are already in
${\mathcal{B}}_{3}$, in which case we leave them there). By definition of
${\mathcal{I}}$, we know that in each step there is at most one polynomial
$P\in\Gamma(Q)\cap{\mathcal{B}}_{3}$. I.e. at most one polynomial in
$\Gamma(Q)$ is not being moved. As at each step $Q$ moves at least
$\delta|{\mathcal{B}}|-1>\delta/2|{\mathcal{B}}|$ polynomials and every
polynomial can be moved at most three times, we conclude that the number of
steps, which is $|{\mathcal{I}}|$ satisfies
$|{\mathcal{I}}|<\frac{6}{\delta}$. ∎

Let ${\mathcal{I}}\subseteq{\mathcal{A}}$ be such maximal set (with respect to
inclusion). We partition ${\mathcal{B}}$ as in the proof of 5.22:
$P\in{\mathcal{B}}_{t}$ if $P\in\Gamma(Q_{i})$ for $t$ different polynomials
$Q_{i}\in{\mathcal{A}}$, and, abusing notation, we set
${\mathcal{B}}_{3}=\cup_{t\geq 3}{\mathcal{B}}_{t}$.

######  Claim 5.23.

There is a linear space of linear forms, $V$, such that
$\dim(V)=O({1}/{\delta^{2}})$ and every polynomial in
$P\in{\mathcal{B}}_{2}\cup{\mathcal{B}}_{3}$ is of the form
$P=P^{\prime}+\ell^{2}$ for some $\ell\in V$ and
$P^{\prime}\in\operatorname{span}\\{{{\mathcal{I}}}\\}$.

In particular the claim implies that
${\mathcal{B}}_{2}\cup{\mathcal{B}}_{3}\subset\operatorname{span}\\{{{\mathcal{I}}}\\}+\mathbb{C}[V]_{2}$.

###### Proof.

Note that ${\mathcal{B}}_{2}\cup{\mathcal{B}}_{3}=\cup_{Q_{i}\neq
Q_{j}\in{\mathcal{I}}}(\Gamma(Q_{i})\cap\Gamma_{(}Q_{j}))$. As
$|{\mathcal{I}}|<{6}/{\delta}$, there are $<{18}/{\delta^{2}}$ pairs
$Q_{i}\neq Q_{j}\in{\mathcal{I}}$. We next prove that for every such
$Q_{i}\neq Q_{j}\in{\mathcal{I}}$ there is a subspace $V_{i,j}$ such that
$\dim(V_{i,j})\leq 4$ and every $P\in\Gamma(Q_{i})\cap\Gamma(Q_{j})$ is of the
form $Q_{i}+\ell^{2}$ for some $\ell\in V_{i,j}$. This clearly implies the
claim by setting $V=\cup_{i,j}V_{i,j}$.

To ease notations we show the existence of $V_{1,2}$. We shall use the
following definition of $\beta_{i}$, $\ell_{i}$ and $\ell^{\prime}_{i}$:
(possibly after rescaling) express each
$P_{i}\in\Gamma(Q_{1})\cap\Gamma(Q_{2})$ as
$P_{i}=Q_{1}+{\ell_{i}}^{2}=\beta_{i}Q_{2}+{\ell^{\prime}_{i}}^{2}$, where
$\ell_{i}$ and $\ell^{\prime}_{i}$ are linear forms and
$\beta_{i}\in\mathbb{C}$. We consider two cases:

  1. 1.

There is a single $\beta$ such that for every
$P_{i}\in\Gamma(Q_{1})\cap\Gamma(Q_{2})$, $\beta_{i}=\beta$: Set
$V_{1,2}=\operatorname{span}\\{{\ell_{1},\ell_{1}^{\prime}}\\}$. From the two
representations of $P_{1}$ we get that

$Q_{1}-\beta
Q_{2}=\ell_{1}^{{}^{\prime}2}-\ell^{2}_{1}=(\ell_{1}^{\prime}-\ell_{1})\cdot(\ell_{1}^{\prime}+\ell_{1})\neq
0,$

where the expression above is nonzero as $Q_{1}$ and $Q_{2}$ are linearly
independent. Consider a different $P_{j}$. Considering the two representations
of $P_{j}$ we get that

$Q_{1}-\beta
Q_{2}=\ell_{j}^{{}^{\prime}2}-\ell^{2}_{j}=(\ell_{j}^{\prime}-\ell_{j})\cdot(\ell_{j}^{\prime}+\ell_{j})\neq
0\;.$

Thus,
$(\ell_{j}^{\prime}-\ell_{j})\cdot(\ell_{j}^{\prime}+\ell_{j})=(\ell_{1}^{\prime}-\ell_{1})\cdot(\ell_{1}^{\prime}+\ell_{1})$
. Unique factorization implies that $\ell_{j}^{\prime},\ell_{j}\in V_{1,2}$,
which is what we wanted to prove.

  2. 2.

There is $j$ such that $\beta_{j}\neq\beta_{1}$: In this case we have that

$\displaystyle P_{1}=Q_{1}+\ell_{1}$
$\displaystyle=\beta_{1}Q_{2}+\ell^{\prime}_{1}$ $\displaystyle
P_{j}=Q_{1}+\ell_{j}$ $\displaystyle=\beta_{j}Q_{2}+\ell^{\prime}_{j}\;,$

and the matrix $\begin{bmatrix}1&-\beta_{1}\\\ 1&-\beta_{j}\end{bmatrix}$ has
full rank. It follows that

$Q_{1},Q_{2}\in\operatorname{span}\\{{(\ell_{j}^{\prime}-\ell_{j})\cdot(\ell_{j}^{\prime}+\ell_{j}),(\ell_{1}^{\prime}-\ell_{1})\cdot(\ell_{1}^{\prime}+\ell_{1})}\\}\;.$

Set
$V_{1,2}=\operatorname{span}\\{{\ell_{j}^{\prime},\ell_{j},\ell_{1}^{\prime},\ell_{1}}\\}$.
Consider any other $P_{k}\in\Gamma(Q_{1})\cap\Gamma(Q_{2})$ and, without loss
of generality, assume $\beta_{k}\neq\beta_{1}$. As before,

$Q_{1},Q_{2}\in\operatorname{span}\\{{(\ell_{j}^{\prime}-\ell_{j})\cdot(\ell_{j}^{\prime}+\ell_{j}),(\ell_{k}^{\prime}-\ell_{k})\cdot(\ell_{k}^{\prime}+\ell_{k})}\\}\;.$

Hence, either for some $\alpha\in\mathbb{C}$,
$Q_{1}=\alpha(\ell_{j}^{\prime}-\ell_{j})\cdot(\ell_{j}^{\prime}+\ell_{j})$ or
there exist $\gamma\in\mathbb{C}$ and a nonzero $\delta\in\mathbb{C}$ such
that
$Q_{1}=\gamma(\ell_{j}^{\prime}-\ell_{j})\cdot(\ell_{j}^{\prime}+\ell_{j})+\delta(\ell_{k}^{\prime}-\ell_{k})\cdot(\ell_{k}^{\prime}+\ell_{k})$.
In the first case we get that both $Q_{1}$ and $Q_{1}-\beta_{j}Q_{2}$ are in
$\operatorname{span}\\{{(\ell_{j}^{\prime}-\ell_{j})\cdot(\ell_{j}^{\prime}+\ell_{j})}\\}$
which implies that $Q_{1},Q_{2}$ are linearly dependent, in contradiction to
our assumption. In the second case we have that for some $\mu,\eta$:

$\gamma(\ell_{j}^{\prime}-\ell_{j})\cdot(\ell_{j}^{\prime}+\ell_{j})+\delta(\ell_{k}^{\prime}-\ell_{k})\cdot(\ell_{k}^{\prime}+\ell_{k})=Q_{1}=\mu(\ell_{j}^{\prime}-\ell_{j})\cdot(\ell_{j}^{\prime}+\ell_{j})+\eta(\ell_{1}^{\prime}-\ell_{1})\cdot(\ell_{1}^{\prime}+\ell_{1}).$

It follows that both $\ell_{k}^{\prime}-\ell_{k}$ and
$\ell_{k}^{\prime}+\ell_{k}$ are spanned by the functions in $V_{1,2}$.

Thus, in wither cases $V_{1,2}$ has the required property. ∎

######  Claim 5.24.

There is a linear space of linear forms $V^{\prime}$, such that
$\dim(V)=O({1}/{\delta^{2}})$ such that
${\mathcal{A}}\subset\operatorname{span}\\{{{\mathcal{I}},\mathbb{C}[V^{\prime}]_{2}}\\}$
and hence $\dim({\mathcal{A}})=O({1}/{\delta^{4}})$.

###### Proof.

We construct $V^{\prime}$ from $V$ and ${\mathcal{I}}$ in the following way:
We start by setting $V^{\prime}=V$. Now, as long as there is a linear
combination of polynomials in ${\mathcal{I}}$ that gives a polynomial of the
form $F(V^{\prime})+\ell_{1}\cdot\ell_{2}$, for
$F\in\mathbb{C}[V^{\prime}]_{2}$, we remove one of the polynomials in the
linear combination from $I$ and add $\ell_{1}$ and $\ell_{2}$ to $V^{\prime}$.
That is, if

$\sum_{Q_{i}\in{\mathcal{I}}}\alpha_{i}Q_{i}=F({{\mathbf{x}}})+\ell_{1}\cdot\ell_{2}\;,$

where $F\in\mathbb{C}[V^{\prime}]_{2}$ then we remove the first polynomial
with a nonzero coefficient from ${\mathcal{I}}$ and define (abusing notation)
$V^{\prime}=V^{\prime}+\operatorname{span}\\{{\ell_{1},\ell_{2}}\\}$. Note
that by doing so,
$\operatorname{span}\\{{{\mathcal{I}}}\\}+\mathbb{C}[V^{\prime}]_{2}$ can only
increase. As this process can take at most $|{\mathcal{I}}|<6/\delta$ steps
and at each step we added at most two linear functions to $V^{\prime}$ we have
that $\dim(V^{\prime})\leq\dim(V)+12/\delta=O(1/\delta^{2})$.

Now, let $Q\in{\mathcal{A}}\setminus{\mathcal{I}}$. As
$Q\not\in{\mathcal{I}}$, by definition of ${\mathcal{I}}$, there must be at
least two polynomials
$P_{1},P_{2}\in\Gamma(Q)\cap({\mathcal{B}}_{2}\cup{\mathcal{B}}_{3})$. As
$P_{1},P_{2}\in\Gamma(Q)$, for $i\in[2]$, there is a linear function
$\ell^{\prime}_{i}$ such that $P_{i}=Q+\ell^{{}^{\prime}2}_{i}$. Note that
$\ell^{\prime}_{1}\neq\ell^{\prime}_{2}$ as $P_{1}\neq P_{2}$. Furthermore,
5.23 implies that, for $i\in[2]$, there are $\alpha_{i}\in\mathbb{C}$,
$Q_{i}\in{\mathcal{I}}$ and linear form $\ell_{i}\in V^{\prime}$, such that
$P_{i}=\alpha_{i}Q_{i}+\ell^{2}_{i}$. Thus,

$0\neq
P_{1}-P_{2}=\ell^{{}^{\prime}2}_{1}-\ell^{{}^{\prime}2}_{2}=\alpha_{1}Q_{1}+\ell^{2}_{1}-\alpha_{2}Q_{2}-\ell^{2}_{2}\in\operatorname{span}\\{{{\mathcal{I}},\mathbb{C}[V^{\prime}]_{2}}\\}\;.$

It follows that there is a linear combination of polynomials in
${\mathcal{I}}$ that equals a polynomial of the form
$F(V^{\prime})+(\ell^{\prime}_{1}-\ell^{\prime}_{2})(\ell^{\prime}_{1}+\ell^{\prime}_{2})$.
Thus, by construction of $V^{\prime}$ it must be the case that the linear
combination is trivial. In particular,
$F(V^{\prime})+(\ell^{\prime}_{1}-\ell^{\prime}_{2})(\ell^{\prime}_{1}+\ell^{\prime}_{2})=0$,
which implies that $\ell^{\prime}_{1}\pm\ell^{\prime}_{2}\in V^{\prime}$.
Therefore,
$Q=\alpha_{1}Q_{1}+\ell^{2}_{1}-\ell^{{}^{\prime}2}_{1}\in\operatorname{span}\\{{{\mathcal{I}},\mathbb{C}[V^{\prime}]_{2}}\\}$
as claimed. ∎

This concludes the proof of 5.21. ∎

###### Proof of Claim 5.6.

The claim follows from 5.21 for ${\mathcal{A}}={\mathcal{Q}}_{2}$,
${\mathcal{B}}={\mathcal{T}}$ and $\delta=\delta/100$. ∎

###  5.2 Proof of Claim 5.7

Here we consider the situation where the set of polynomials is the union of
two sets such that each polynomial in the first set satisfies Theorem
1.13(iii) with $\delta$ fraction of the polynomials in the second set. The
proof of 5.7 is an immediate corollary of the next claim.

######  Claim 5.25.

Let $\delta\in(0,1]$. Let ${\mathcal{A}}$ and ${\mathcal{C}}$ be two sets of
irreducible quadratic polynomials such that the polynomials in
${\mathcal{A}}\cup{\mathcal{C}}$ are pairwise linearly independent.
Furthermore, assume that for every $Q\in{\mathcal{A}}$ there is a subset
$\Gamma(Q)\subseteq{\mathcal{C}}$ such that
$|\Gamma(Q)|\geq\delta|{\mathcal{C}}|$ and for every $P\in\Gamma(Q)$, $Q$ and
$P$ satisfy Theorem 1.13(iii). Then, there is a linear space of linear forms
$V$ such that $\dim(V)=O({1}/{\delta})$ and
${\mathcal{A}}\subset\left\langle{V}\right\rangle$.

###### Proof.

The intuition behind the claim is based on the following observation.

######  Observation 5.26.

If $Q\in{\mathcal{A}}$ and $P\in{\mathcal{C}}$ satisfy Theorem 1.13(iii) then
$\dim(\text{Lin}(Q)),\dim(\text{Lin}(P))\leq 4$ and
$\dim(\text{Lin}(Q)\cap\text{Lin}(P))\geq 2$.

Thus, we have many small dimensional spaces that have large pairwise
intersections and we can therefore expect that such a $V$ may exist.

We prove the existence of $V$ by explicitly constructing it. Consider the
following process: start by setting $V^{\prime}=\\{{\mathbf{0}}\\}$, and
${\mathcal{A}}^{\prime}=\emptyset$. As long as there is $Q\in{\mathcal{A}}$,
such that $Q\notin\left\langle{V^{\prime}}\right\rangle$, we set
$V^{\prime}=\text{Lin}(Q)+V^{\prime}$, and
${\mathcal{A}}^{\prime}={\mathcal{A}}^{\prime}\cup\\{Q\\}$. We show next that
this process must end after at most $\frac{3}{\delta}$ steps. In particular,
at termination, $|{\mathcal{A}}^{\prime}|\leq\frac{3}{\delta}$,
$\dim(V^{\prime})\leq 12/\delta$ and
${\mathcal{A}}\subset\left\langle{V^{\prime}}\right\rangle$.

######  Claim 5.27.

Let $P\in{\mathcal{C}}$. Let ${\mathcal{B}}\subseteq{\mathcal{A}}^{\prime}$ be
the subset of all polynomials in ${\mathcal{A}}^{\prime}$ that satisfy Theorem
1.13(iii) with $P$. Then, $|{\mathcal{B}}|\leq 3$.

###### Proof.

Assume towards a contradiction that $|{\mathcal{B}}|\geq 4$, and that
$Q_{1},Q_{2},Q_{3}$ and $Q_{4}$ are the first four elements of ${\mathcal{B}}$
that where added to ${\mathcal{A}}^{\prime}$, in this order. Denote
$U=\text{Lin}(P)$, and $U_{i}=U\cap\text{Lin}(Q_{i})$, for $1\leq i\leq 4$.

As $P$ and $Q_{1}$ satisfy Theorem 1.13(iii), we have that $\dim(U)\leq 4$.
Furthermore, for every $i$, $\dim(U_{i})\geq 2$ (by 5.26). As the $Q_{i}$s
were picked by the iterative process, we have that $U_{2}\not\subseteq U_{1}$.
Indeed, since $Q_{2}\in\left\langle{U_{2}}\right\rangle$, if we had
$U_{2}\subseteq U_{1}\subseteq\text{Lin}(Q_{1})\subseteq V^{\prime}$, then
this would imply that $Q_{2}\in\left\langle{V^{\prime}}\right\rangle$, in
contradiction to the fact that $Q_{2}$ was added to ${\mathcal{A}}^{\prime}$
after $Q_{1}$. Similarly we get that $U_{3}\not\subseteq U_{1}+U_{2}$ and
$U_{4}\not\subseteq U_{1}+U_{3}+U_{3}$. However, as the next simple lemma
shows, this is not possible.

######  Lemma 5.28.

Let $V$ be a linear space of dimension $\leq 4$, and let
$V_{1},V_{2},V_{3}\subset V^{\prime}$ each of dimension $\geq 2$, such that
$V_{1}\not\subseteq V_{2}$ and $V_{3}\not\subseteq V_{2}+V_{1}$. Then,
$V=V_{1}+V_{2}+V_{3}$.

###### Proof.

As $V_{1}\not\subseteq V_{2}$ we have that $\dim(V_{1}+V_{2})\geq 3$.
Similarly we get $4\leq\dim(V_{1}+V_{2}+V_{3})\leq\dim(V)=4$. ∎

5.28 implies that $V^{\prime}=U_{1}+U_{2}+U_{3}$ and in particular,
$U_{4}\subseteq U_{1}+U_{2}+U_{3}$ in contradiction. This completes the proof
of 5.27. ∎

On the one hand we have that for every $Q\in{\mathcal{A}}^{\prime}$, it holds
that $|\Gamma{(Q)}|\geq\delta|{\mathcal{C}}|$. On the other hand, 5.27 implies
that each $P\in{\mathcal{C}}$ satisfies Theorem 1.13(iii) with at most three
different polynomials in ${\mathcal{A}}^{\prime}$. It follows that
$|{\mathcal{A}}^{\prime}|\cdot\delta|{\mathcal{C}}|\leq 3\cdot|{\mathcal{C}}|$
and therefore, $|{\mathcal{A}}^{\prime}|\leq 3/\delta$. As in each step we add
at most four linearly independent linear forms to $V^{\prime}$, we obtain
$\dim(V^{\prime})\leq\frac{12}{\delta}$. ∎

###### Proof of Claim 5.7.

The claim follows from 5.25 for ${\mathcal{A}}={\mathcal{Q}}_{3}$,
${\mathcal{C}}={\mathcal{T}}$ and $\delta=\delta/100$. ∎

###  5.3 Proof of Claim 5.8

###### Proof.

As in the proof of 5.21, we construct ${\mathcal{J}}$ iteratively as follows.
We start by setting ${\mathcal{J}}={\mathcal{I}}$ and
${\mathcal{B}}={\mathcal{Q}}_{2}\cup{\mathcal{Q}}_{3}$. We first add to
${\mathcal{B}}$ any polynomial from ${\mathcal{Q}}_{1}$ that is in
$\operatorname{span}\\{{({\mathcal{Q}}\cap\left\langle{V}\right\rangle),{\mathcal{J}},\mathbb{C}[V]_{2}}\\}$.
Observe that at this point we have that
${\mathcal{B}}\subset\operatorname{span}\\{{({\mathcal{Q}}\cap\left\langle{V}\right\rangle),\mathbb{C}[V]_{2},{\mathcal{J}}}\\}$.
Next, consider the following iterative process for the polynomials in
${\mathcal{Q}}_{1}$: In each step pick any
$P\in{\mathcal{Q}}_{1}\setminus{\mathcal{B}}$ that satisfies Theorem 1.13(i)
with at least $\frac{\delta}{300}m$ polynomials in ${\mathcal{B}}$, and add it
to both ${\mathcal{J}}$ and to ${\mathcal{B}}$. Then, add to ${\mathcal{B}}$
all the polynomials $P^{\prime}\in{\mathcal{Q}}_{1}$ that satisfy
$P^{\prime}\in\operatorname{span}\\{{({\mathcal{Q}}\cap\left\langle{V}\right\rangle),{\mathcal{J}},\mathbb{C}[V]_{2}}\\}$.
Note, that we always maintain that
${\mathcal{B}}\subset\operatorname{span}\\{{({\mathcal{Q}}\cap\left\langle{V}\right\rangle),\mathbb{C}[V]_{2},{\mathcal{J}}}\\}$.
We continue this process as long as possible. The next claim shows that when
the process terminates we have that $|{\mathcal{J}}|\leq O(1/\delta)$.

######  Claim 5.29.

In each step we added to ${\mathcal{B}}$ at least $\frac{\delta}{300}m$ new
polynomials from ${\mathcal{Q}}_{1}$. In particular, $|{\mathcal{J}}|\leq
300/\delta$.

###### Proof.

Consider what happens when we add some polynomial $P$ to ${\mathcal{J}}$. By
the description of our process, $P$ satisfies Theorem 1.13(i) with at least
$\frac{\delta}{300}m$ polynomials in ${\mathcal{B}}$. Any $Q\in{\mathcal{B}}$,
that satisfies Theorem 1.13(i) with $P$, must span with $P$ a polynomial
$P^{\prime}\in{{\mathcal{Q}}_{1}}$. To see that
$P^{\prime}\in{\mathcal{Q}}_{1}$ observe that otherwise we would have that
$P\in\operatorname{span}\\{{{\mathcal{B}}}\\}\subset\operatorname{span}\\{{({\mathcal{Q}}\cap\left\langle{V}\right\rangle),\mathbb{C}[V]_{2},{\mathcal{J}}}\\}$,
which implies $P\in{\mathcal{B}}$, in contradiction to the definition of the
process. Furthermore, for each such $Q\in{\mathcal{B}}$ the polynomial
$P^{\prime}$ is unique. Indeed, if there was a $P\neq
P^{\prime}\in{\mathcal{Q}}_{1}$ and $Q_{1},Q_{2}\in{\mathcal{B}}$ such that
$P^{\prime}\in\operatorname{span}\\{{Q_{1},P}\\}\cap\operatorname{span}\\{{Q_{2},P}\\}$
then pairwise independence implies that
$P\in\operatorname{span}\\{{Q_{1},Q_{2}}\\}\subset\operatorname{span}\\{{{\mathcal{B}}}\\}$,
from which we infer that $P\in{\mathcal{B}}$, in contradiction. Thus, when we
add $P$ to ${\mathcal{J}}$, at least $\frac{\delta}{3}m$ polynomials are added
to ${\mathcal{B}}$. In particular, the process must terminates after at most
$300/\delta$ steps. Consequently, $|{\mathcal{J}}|\leq 300/\delta$ as claimed.
∎

Consider the polynomials left in ${\mathcal{Q}}_{1}\setminus{\mathcal{B}}$
when the process terminated. As they ”survived” the process, each of them
satisfies Theorem 1.13(i) with less than $\frac{\delta}{300}m$ polynomials in
${\mathcal{B}}$. From the fact that
${\mathcal{Q}}_{3}\cup{\mathcal{Q}}_{2}\subseteq{\mathcal{B}}$ and the
uniqueness property that was observed in the proof of 5.29, we get that the
set ${\mathcal{Q}}_{1}\setminus{\mathcal{B}}$ satisfies the conditions of 1.1
with parameter $\delta^{\prime}=(\delta/100-\delta/300)$. Theorem 1.2 implies
that $\dim({\mathcal{Q}}_{1}\setminus{\mathcal{B}})\leq O(1/\delta)$. Adding a
basis of ${\mathcal{Q}}_{1}\setminus{\mathcal{B}}$ to ${\mathcal{J}}$ we get
that $|{\mathcal{J}}|=O(1/\delta)$ and every polynomial in ${\mathcal{Q}}$ is
in
$\operatorname{span}\\{{({\mathcal{Q}}\cap\left\langle{V}\right\rangle),\mathbb{C}[V]_{2},{\mathcal{J}}}\\}$.

To prove the furthermore part we note that if $Q\in{\mathcal{Q}}$ is such that
for some quadratic $L$ of $\operatorname{rank}(L)=2$ we have that
$P+L\in\left\langle{V}\right\rangle$ then we can add $\text{Lin}(L)$ to $V$
and remove one polynomial from ${\mathcal{J}}$ while still maintaining that
${\mathcal{Q}}\subset\operatorname{span}\\{{({\mathcal{Q}}\cap\left\langle{V}\right\rangle),{\mathcal{J}},\mathbb{C}[V]_{2}}\\}$,
in a similar way to the process described at 5.24.

∎

## References

  * Agr [05] Manindra Agrawal.  Proving Lower Bounds Via Pseudo-random Generators.  In Ramaswamy Ramanujam and Sandeep Sen, editors, FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, 25th International Conference, Hyderabad, India, December 15-18, 2005, Proceedings, volume 3821 of Lecture Notes in Computer Science, pages 92–105. Springer, 2005.
  * AV [08] Manindra Agrawal and V. Vinay.  Arithmetic Circuits: A Chasm at Depth Four.  In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 67–75. IEEE Computer Society, 2008.
  * BDSW [19] Abdul Basit, Zeev Dvir, Shubhangi Saraf, and Charles Wolf.  On the Number of Ordinary Lines Determined by Sets in Complex Space.  Discret. Comput. Geom., 61(4):778–808, 2019.
  * BDWY [13] Boaz Barak, Zeev Dvir, Avi Wigderson, and Amir Yehudayoff.  Fractional Sylvester–Gallai theorems.  Proceedings of the National Academy of Sciences, 110(48):19213–19219, 2013.
  * BM [90] Peter Borwein and William O. J. Moser.  A survey of Sylvester’s problem and its generalizations.  Aequationes Mathematicae, 40:111–135, 1990.
  * BMS [13] Malte Beecken, Johannes Mittmann, and Nitin Saxena.  Algebraic independence and blackbox identity testing.  Inf. Comput., 222:2–19, 2013.
  * Chv [04] Vasek Chvátal.  Sylvester-Gallai Theorem and Metric Betweenness.  Discret. Comput. Geom., 31(2):175–195, 2004.
  * CKS [18] Chi-Ning Chou, Mrinal Kumar, and Noam Solomon.  Hardness vs Randomness for Bounded Depth Arithmetic Circuits.  In Rocco A. Servedio, editor, 33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA, volume 102 of LIPIcs, pages 13:1–13:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * CLO [07] David A. Cox, John Little, and Donal O’Shea.  Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra.  Springer, 3rd edition, 2007.
  * DH [16] Zeev Dvir and Guangda Hu.  Sylvester-Gallai for Arrangements of Subspaces.  Discrete & Computational Geometry, 56(4):940–965, 2016.
  * DS [07] Zeev Dvir and Amir Shpilka.  Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits.  SIAM J. Comput., 36(5):1404–1434, 2007.
  * DSW [14] Zeev Dvir, Shubhangi Saraf, and Avi Wigderson.  Improved rank bounds for design matrices and a new proof of Kelly’s theorem.  Forum of Mathematics, Sigma, 2, 2014.  Pre-print available at arXiv:1211.0330.
  * DSY [09] Zeev Dvir, Amir Shpilka, and Amir Yehudayoff.  Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits.  SIAM J. Comput., 39(4):1279–1293, 2009.
  * Dvi [12] Zeev Dvir.  Incidence Theorems and Their Applications.  Found. Trends Theor. Comput. Sci., 6(4):257–393, 2012.
  * Erd [43] Paul Erdös.  Problems for Solution: 4065.  The American Mathematical Monthly, 50(1):65, 1943.
  * FGT [19] Stephen A. Fenner, Rohit Gurjar, and Thomas Thierauf.  A deterministic parallel algorithm for bipartite perfect matching.  Commun. ACM, 62(3):109–115, 2019.
  * For [14] Michael A. Forbes.  Polynomial identity testing of read-once oblivious algebraic branching programs.  PhD thesis, Massachusetts Institute of Technology, 2014.
  * FS [13] Michael A. Forbes and Amir Shpilka.  Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing.  In Prasad Raghavendra, Sofya Raskhodnikova, Klaus Jansen, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings, volume 8096 of Lecture Notes in Computer Science, pages 527–542. Springer, 2013.
  * FSV [18] Michael A. Forbes, Amir Shpilka, and Ben Lee Volk.  Succinct Hitting Sets and Barriers to Proving Lower Bounds for Algebraic Circuits.  Theory of Computing, 14(1):1–45, 2018.
  * Gal [44] Tibor Gallai.  Solution to Problem 4065.  The American Mathematical Monthly, 51:169–171, 1944.
  * GKKS [16] Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi.  Arithmetic Circuits: A Chasm at Depth 3.  SIAM J. Comput., 45(3):1064–1079, 2016.
  * GKSS [17] Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, and Shubhangi Saraf.  Towards an algebraic natural proofs barrier via polynomial identity testing.  CoRR, abs/1701.01717, 2017.  Pre-print available at arXiv:1701.01717.
  * GOS [21] Abhibhav Garg, Rafael Oliviera, and Akash Kumar Sengupta.  Robust Radical Sylvester-Gallai Theorem for Quadratics.  Personal communication, 2021.
  * Gup [14] Ankit Gupta.  Algebraic Geometric Techniques for Depth-4 PIT & Sylvester-Gallai Conjectures for Varieties.  Electronic Colloquium on Computational Complexity (ECCC), 21:130, 2014.
  * Han [65] Sten Hansen.  A generalization of a theorem of Sylvester on the lines determined by a finite point set.  Mathematica Scandinavica, 16:175–180, 1965.
  * HS [80] Joos Heintz and Claus-Peter Schnorr.  Testing Polynomials which Are Easy to Compute (Extended Abstract).  In Raymond E. Miller, Seymour Ginsburg, Walter A. Burkhard, and Richard J. Lipton, editors, Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28-30, 1980, Los Angeles, California, USA, pages 262–272. ACM, 1980.
  * Kel [86] Leroy Milton Kelly.  A resolution of the Sylvester-Gallai problem of J.-P. Serre.  Discrete & Computational Geometry, 1(2):101–104, 1986.
  * KI [04] Valentine Kabanets and Russell Impagliazzo.  Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds.  Computational Complexity, 13(1-2):1–46, 2004.
  * [29] Zohar S. Karnin and Amir Shpilka.  Reconstruction of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-in.  In Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pages 274–285. IEEE Computer Society, 2009.
  * [30] Neeraj Kayal and Shubhangi Saraf.  Blackbox Polynomial Identity Testing for Depth 3 Circuits.  In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 198–207. IEEE Computer Society, 2009.
  * KS [19] Mrinal Kumar and Ramprasad Saptharishi.  Hardness-Randomness Tradeoffs for Algebraic Computation.  Bull. EATCS, 129, 2019.
  * KSS [15] Swastik Kopparty, Shubhangi Saraf, and Amir Shpilka.  Equivalence of Polynomial Identity Testing and Polynomial Factorization.  Computational Complexity, 24(2):295–331, 2015.
  * Mel [41] Eberhard Melchior.  Über Vielseite der Projektive Ebene.  Deutsche Mathematik, 5:461–475, 1941.
  * Mul [17] Ketan D. Mulmuley.  Geometric complexity theory V: Efficient algorithms for Noether normalization.  J. Amer. Math. Soc., 30(1):225–309, 2017.
  * PS [09] Lourens M. Pretorius and Konrad J. Swanepoel.  The Sylvester-Gallai theorem, colourings and algebra.  Discret. Math., 309(2):385–399, 2009.
  * [36] Shir Peleg and Amir Shpilka.  A Generalized Sylvester-Gallai Type Theorem for Quadratic Polynomials.  In Shubhangi Saraf, editor, 35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbrücken, Germany (Virtual Conference), volume 169 of LIPIcs, pages 8:1–8:33. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [37] Shir Peleg and Amir Shpilka.  Polynomial time deterministic identity testing algorithm for $\Sigma$${}^{\mbox{[3]}}$$\Pi$$\Sigma$$\Pi$${}^{\mbox{[2]}}$ circuits via Edelstein-Kelly type theorem for quadratic polynomials.  CoRR, abs/2006.08263, 2020.  Pre-print available at arXiv:2006.08263.
  * Sax [09] Nitin Saxena.  Progress on polynomial identity testing.  Bulletin of EATCS, 99:49–79, 2009.
  * Sax [14] Nitin Saxena.  Progress on Polynomial Identity Testing-II.  In M. Agrawal and V. Arvind, editors, Perspectives in Computational Complexity: The Somenath Biswas Anniversary Volume, Progress in Computer Science and Applied Logic, pages 131–146. Springer International Publishing, 2014.
  * Ser [66] Jean-Pierre Serre.  Advanced Problems: 5359.  The American Mathematical Monthly, 73(1):89, 1966.
  * Shp [09] Amir Shpilka.  Interpolation of Depth-3 Arithmetic Circuits with Two Multiplication Gates.  SIAM J. Comput., 38(6):2130–2161, 2009.
  * Shp [20] Amir Shpilka.  Sylvester-Gallai type theorems for quadratic polynomials.  Discrete Analysis, 13, 2020.
  * Sin [16] Gaurav Sinha.  Reconstruction of Real Depth-3 Circuits with Top Fan-In 2.  In Ran Raz, editor, 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, volume 50 of LIPIcs, pages 31:1–31:53. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016.
  * SS [12] Nitin Saxena and Comandur Seshadhri.  Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn’t Matter.  SIAM J. Comput., 41(5):1285–1298, 2012.
  * SS [13] Nitin Saxena and Comandur Seshadhri.  From Sylvester-Gallai configurations to rank bounds: Improved blackbox identity test for depth-3 circuits.  J. ACM, 60(5):33, 2013.
  * ST [17] Ola Svensson and Jakub Tarnawski.  The Matching Problem in General Graphs Is in Quasi-NC.  In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 696–707. IEEE Computer Society, 2017.
  * SY [10] 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.
  * Syl [93] James Joseph Sylvester.  Mathematical question 11851.  Educational Times, pages 59–98, 1893.

##  Appendix A Appendix

###### Proof of Theorem 3.1.

We say that $q\in{\mathcal{T}}$ is a neighbor of $p\in{\mathcal{K}}$, if the
span of $p$ and $q$ contains a third point in ${\mathcal{T}}$. We denote with
$\Gamma(p)$ the set of all neighbors of $p$.

We perform the following process: While there is $p\in{\mathcal{K}}$ such that
$|\Gamma(p)\cap W|\geq 0.1\cdot\delta|{\mathcal{T}}|$ we set, abusing
notation, $W=\operatorname{span}\\{{W,p}\\}$, ${\mathcal{W}}={\mathcal{T}}\cap
W$ and ${\mathcal{K}}={\mathcal{T}}\setminus{\mathcal{W}}$. We first wish to
prove that this process must terminate after $O(1/\delta)$ many iterations.
For that we will show that at every step of the process, at least
$0.1\cdot\delta|{\mathcal{K}}|$ points from ${\mathcal{K}}$ are moved to
${\mathcal{W}}$.

So consider a step of the process, and let $p\in{\mathcal{K}}$ be the relevant
polynomial. Observe that for any $w\in\Gamma(p)\cap W$, the space spanned by
$p$ and $w$ must contain a point in ${\mathcal{K}}$, as at every step of the
process we maintain that ${\mathcal{K}}\cap W=\emptyset$. Furthermore, all the
points in ${\mathcal{K}}$ that are obtained in this manner (i.e. that are in
the span of $p$ and some $w\in{\mathcal{W}}$) must be distinct. Indeed, if $p$
spans $q\in{\mathcal{K}}$ with two different $w_{1},w_{2}\in{\mathcal{W}}$
then, as $w_{1}$ and $w_{2}$ are linearly independent, and so are $p$ and $q$,
we get that
$\operatorname{span}\\{{p,q}\\}=\operatorname{span}\\{{w_{1},w_{2}}\\}$ which
implies that $p\in W$, in contradiction. From this and the assumption that
$|\Gamma(p)\cap W|\geq 0.1\cdot\delta|{\mathcal{T}}|\geq
0.1\cdot\delta|{\mathcal{K}}|$, it follows that at least
$0.1\cdot\delta|{\mathcal{K}}|$ points from ${\mathcal{K}}$ are moved to
${\mathcal{W}}$ at this step of our process. Hence, the process must terminate
after at most $10/\delta$ steps. Note that when the process terminates,
$\dim(W)\leq r+\frac{10}{\delta}$.

After the termination of the process, it holds that for every
$p\in{\mathcal{K}}$ ,$|\Gamma(p)\cap W|<0.1\cdot\delta|{\mathcal{T}}|$. We now
wish to prove that ${\mathcal{K}}$ satisfies the conditions of Theorem 1.2
(the usual robust-SG theorem ) with parameter $\delta^{\prime}=0.8\delta$. For
this we have to prove that for every $p\in{\mathcal{K}}$ there are at least
$0.8\cdot\delta|{\mathcal{K}}|$ points in ${\mathcal{K}}$ that each spans with
$p$ a third point in ${\mathcal{K}}$. To show this we prove that the number of
points $q\in\Gamma(p)$ that do not span with $p$ a point in ${\mathcal{K}}$,
is at most $0.1\cdot\delta|{\mathcal{K}}|$.

Indeed, if $q\in\Gamma(p)\cap{\mathcal{K}}$ does not span with $p$ a point in
${\mathcal{K}}$ then it must span some $w\in{\mathcal{W}}$. Furthermore,
$w\in\Gamma(p)$. The crucial observation is that there cannot be any other
point $q\neq q^{\prime}\in{\mathcal{K}}\cap\Gamma(p)$ such that
$w\in\operatorname{span}\\{{p,q}\\}\cap\operatorname{span}\\{{p,q^{\prime}}\\}$,
as in this case, by our assumption on pairwise independence, we would have
that $q^{\prime}\in\operatorname{span}\\{{p,q}\\}$, in contradiction to the
assumption that $q$ does not span with $p$ a point in ${\mathcal{K}}$.
Therefore, when restricting ourselves to ${\mathcal{K}}$, we have that $p$ has
at least $\delta|{\mathcal{T}}|-2|\Gamma(p)\cap W|\geq
0.8\cdot\delta|{\mathcal{T}}|\geq 0.8\cdot\delta|{\mathcal{K}}|$ neighbors in
${\mathcal{K}}$ that span together with $p$ a third point in ${\mathcal{K}}$,
as we wanted to prove.

As we just proved that ${\mathcal{K}}$ satisfies Theorem 1.2 with parameter
$\delta^{\prime}=0.8\delta$, it follows that
$\dim({\mathcal{K}})\leq\frac{15}{\delta}+1$. In conclusion we get that
$\dim({\mathcal{T}})\leq\dim(W)+\dim({\mathcal{K}})\leq\left(r+\frac{10}{\delta}\right)+\left(\frac{15}{\delta}+1\right)=O(r+\frac{1}{\delta})$,
as claimed. ∎

###### Proof of 3.2.

For a point $v\in{\mathcal{B}}$ denote by $\Gamma(v)=\\{u\in
V\setminus{\mathcal{B}}\mid u,v\text{ lie on a special line}\\}$, similarly
for a point $u\in V\setminus{\mathcal{B}}$ denote by
$\Gamma(u)=\\{v\in{\mathcal{B}}\mid v,u\text{ lie on a special line}\\}$. Note
that for $v\in{\mathcal{B}}$, $u\in\Gamma(v)$ if the special line between $v$
and $u$ contains $w\in V\setminus{\mathcal{B}}$, then $w\in\Gamma(V)$. Denote

$\overline{\gamma}(V)=\frac{\sum_{v\in
V}\left|{\Gamma(v)}\right|}{\left|{V}\right|}.$

From the assumption that there are $\delta m^{2}$ pairs of points
$v\in{\mathcal{B}}$, $u\in V\setminus{\mathcal{B}}$ that lie on a special line
it follows that $\overline{\gamma}(V)\geq 2\delta\cdot m$. If for every $v\in
V$ it holds that $|\Gamma(v)|\geq(\delta/2)\cdot m$ then $V$ is a
$\delta/2$-SG configuration and thus $\dim(V)=O(1/\delta)$ and in particular
${\mathcal{B}}^{\prime}={\mathcal{B}}$ satisfies the claim.

While there is $v\in V$ with $\left|{\Gamma(v)}\right|<(\delta/2)\cdot m$,
remove $v$ from $V$. We want to bound the number of lines that became ordinary
after removing $v$. Assume without loss of generality, that
$v\in{\mathcal{B}}$.

First, we remove one neighbor for every point in $\Gamma(v)\subset
V\setminus{\mathcal{B}}$. The other case to consider is two neighbors
$v^{\prime}\in{\mathcal{B}},u\in V\setminus{\mathcal{B}}$ that lie on a
special line containing $v$, and thus, it might be that after removing $v$
they do not lie on a special line anymore. In this case we should remove $u$
from $\Gamma(v^{\prime})$ and vice versa. Note that in this case we have
$u\in\Gamma(v)$. If there is another $v^{\prime\prime}\in{\mathcal{B}}$ such
that $v$ lie on the line between $u$ and $v^{\prime\prime}$, then the line
between $u$ and $v$ contains both $v^{\prime}$ and $v^{\prime\prime}$. in
particular, removing $v$ still keeps the line special as it intersect the set
with at least three points $u,v^{\prime},v^{\prime\prime}$. Therefore, we do
not need to remove any neighbors of $u$. To conclude, we removed at most two
lines for every point in $\Gamma(v)$. As each line that became ordinary
affects the neighborhoods of the (only) two points that are on it. Thus, we
conclude that,

$\overline{\gamma}_{new}(V)=\frac{\sum_{u\in
V}|\Gamma(u)|-4|\Gamma(v)|}{n-1}>\overline{\gamma}(V).$

as $4|\Gamma(v)|<2\delta\cdot m.$ Thus we can continue this process until all
the points satisfy $|\Gamma(v)|\geq(\delta/2)\cdot m$, as the average degree
increases in every step, the process must terminates and leave
$|{\mathcal{B}}|>(\delta/2)\cdot m$, and thus
${\mathcal{B}}^{\prime}={\mathcal{B}}$ satisfies the claim.

∎