$(nd\log|\mathbb{F}|)^{O(1)}$ time. ∎

##  6 Proof of Proposition 2

In this section we present our proof of Proposition 2. The proof is
immediately implied by Lemma 6.1 which is itself proved using Lemma 6.2.
Recall definition of set of ordinary lines(Definition 2.8).

######  Lemma 6.1.

Let $\mathcal{S}\subset\mathbb{F}^{n}$ be a proper set (Definition 2.7) and
$\mathcal{T}\subset\mathbb{F}^{n}$ be any linearly independent set of size
$\log|\mathcal{S}|+2$. Then, the following holds.

$sp(\mathcal{S})\subseteq\sum\limits_{t\in\mathcal{T}}\sum\limits_{W\in\mathcal{O}(t,\mathcal{S})}W$

##### Proof of Proposition 2 using Lemma 6.1:

By simply taking dimension of both sides in the containment, applying union
bound on the right hand side and assuming $t\in\mathcal{T}$ maximizes
$dim(\sum_{W\in\mathcal{O}(t,\mathcal{S})}W))$, we get

$dim(\sum_{W\in\mathcal{O}(t,\mathcal{S})}W)\geq\frac{dim(sp(\mathcal{S}))}{\log|\mathcal{S}|+2}.$

which proves Proposition 2. So we are left with proving Lemma 6.1.

##### Proof of Lemma 6.1

Let $V$ be the vector space
$\sum_{t\in\mathcal{T}}\sum_{W\in\mathcal{O}(t,\mathcal{S})}W$. We define set
$\mathcal{S}^{\prime}=\mathcal{S}\setminus V$. $\mathcal{S}^{\prime}$ is a
proper set. We will show that $\mathcal{S}^{\prime}=\phi\Rightarrow
sp(\mathcal{S})\subset V$. If not, we show that there cannot be any ordinary
line from $\mathcal{T}$ into $\mathcal{S}^{\prime}$. Suppose there is some
such line $sp\\{t,s\\}$ where $t\in\mathcal{T}$ and $s\in\mathcal{S}^{\prime}$
are not scalar multiples. Since it is an ordinary line into
$\mathcal{S}^{\prime}$, we get that
$sp\\{s,t\\}\cap\mathcal{S}^{\prime}\subset sp\\{s\\}\cup sp\\{t\\}$. Then one
of the following mutually exclusive statements will obviously be true.

  1. 1.

$sp\\{s,t\\}\cap V\subset sp\\{s\\}\cup sp\\{t\\}$

  2. 2.

$sp\\{s,t\\}\cap V\not\subset sp\\{s\\}\cup sp\\{t\\}$

In the first case, since $\mathcal{S}=\mathcal{S}^{\prime}\cup(\mathcal{S}\cap
V)\Rightarrow sp\\{s,t\\}\cap\mathcal{S}\subset sp\\{s\\}\cup sp\\{t\\}$.
Therefore it is an ordinary line into $\mathcal{S}$. But all such lines are
subsets of $V\Rightarrow s\in V$ which is a contradiction since
$s\in\mathcal{S}^{\prime}$ which is disjoint from $V$. In the second case,
there is some $v\in sp\\{s,t\\}\cap V$ such that $v\notin sp\\{s\\}\cup
sp\\{t\\}$. Therefore $t,s,v$ are linearly dependent but $t,s$ and $s,v$ are
not $\Rightarrow$ $s\in sp\\{t,v\\}$. Both $t,v$ are in $V$ by construction
and thus $s\in V$ which is again a contradiction since
$s\in\mathcal{S}^{\prime}$ which is disjoint from $V$. Therefore if
$\mathcal{S}^{\prime}$ is non-empty, there are no ordinary lines from
$\mathcal{T}$ into $\mathcal{S}$. Now we use Lemma 6.2 and complete the proof.
We will prove Lemma 6.2 after the current proof.

######  Lemma 6.2.

Let $\mathcal{S}(\neq\phi)\subset\mathbb{F}^{n}$ be a proper set and
$\mathcal{T}\subset\mathbb{F}^{n}$ be linearly independent such that for every
$t\in\mathcal{T}$, there is no ordinary line (Definition 2.8) from $t$ into
$\mathcal{S}$. Then $|\mathcal{T}|\leq\log|\mathcal{S}|+1$.

Using Lemma 6.2 with $\mathcal{S}^{\prime}$ and $\mathcal{T}$, we get that
$\log|\mathcal{S}|+2=|\mathcal{T}|\leq\log|\mathcal{S}^{\prime}|+1$ which is a
contradiction since $\mathcal{S}^{\prime}\subset\mathcal{S}$. Therefore, the
only conclusion left is $\mathcal{S}^{\prime}=\phi$, which completes the proof
of our lemma as explained earlier.

##### Proof of Lemma 6.2:

Let $|\mathcal{T}|=d$ and $|\mathcal{S}|=m$. We present a counting argument by
building a one-to-one function mapping subsets of $[d-1]$ into $\mathcal{S}$.
Such a function implies that $m\geq 2^{d-1}$ and we’ll be done. The following
describes this one-to-one function. Fix an element $s\in\mathcal{S}$ and let
$\mathcal{T}=\\{t_{1},\ldots,t_{d}\\}$. Without loss of generality we may
assume that $s,t_{1},\ldots,t_{d-1}$ are linearly independent.

######  Claim 6.1.

For any subset $\mathcal{P}\subset[d-1]$, there exists
$s_{\mathcal{P}}\in\mathcal{S}$ in the interior262626“interior” means that
when $s_{\mathcal{P}}$ is written as a linear combination of
$\\{\\{t_{i}:i\in\mathcal{P}\\}\cup\\{s\\}\\}$, all coefficients are non-zero
of $sp\\{\\{t_{i}:i\in\mathcal{P}\\}\cup\\{s\\}\\}$.

###### Proof.

We prove by induction on $|\mathcal{P}|$. For $|\mathcal{P}|=0$, define
$s_{\mathcal{P}}=s$ and we are done. Let’s assume the claim is true for
$|\mathcal{P}|=k-1$. We prove it for $|\mathcal{P}|=k$. Consider any element
$p\in\mathcal{P}$ and let $\mathcal{R}=\mathcal{P}\setminus\\{p\\}$. By
induction, we know there exists $s_{\mathcal{R}}$ in the interior of
$sp\\{\\{t_{i}:i\in\mathcal{R}\\}\cup\\{s\\}\\}$. Since there is no ordinary
line from any $t\in\mathcal{T}$ into $\mathcal{S}$, the line
$sp\\{t_{p},s_{\mathcal{R}}\\}$ contains $s_{\mathcal{P}}\in\mathcal{S}$ such
that $s_{\mathcal{P}}\notin sp\\{t_{p}\\}\cup
sp\\{s_{\mathcal{R}}\\}\Rightarrow s_{\mathcal{P}}=\alpha t_{p}+\beta
s_{\mathcal{R}}$ with $\alpha,\beta\in\mathbb{F}$ being non-zero scalars
$\Rightarrow s_{\mathcal{P}}$ is in the interior of
$sp\\{\\{t_{i}:i\in\mathcal{P}\\}\cup\\{s\\}\\}$ and the proof is complete. ∎

We can see that the function mapping $\mathcal{P}\subset[d-1]$ to
$s_{\mathcal{P}}\in\mathcal{S}$, is one-to-one since for sets
$\mathcal{P,Q}\subset[d-1]$, which differ at some $j\in[d-1]$, exactly one of
$s_{\mathcal{P}},s_{\mathcal{Q}}$ has a non-zero coefficient of $t_{j}$,
implying they are different. This completes the proof.

##  7 Acknowledgements

We would like to thank Vineet Nair for helping with organization and
presentation of the paper. He also provided multiple insights about the
content which led to better presentation. We would also like to thank Neeraj
Kayal and Chandan Saha for helpful comments on an early presentation of this
work. Neeraj Kayal introduced the author to black-box reconstruction problems
for depth three circuits. The simple idea behind proof of Lemma 6.2, presented
in this paper was shared with the author by Neeraj Kayal during a discussion.
We would also like to thank Anuja Sharan for proofreading and helping in
preparation of this paper.

## References

  * [AH19] Eric Allender and Shuichi Hirahara.  New insights on the (non-)hardness of circuit minimization and related problems.  ACM Trans. Comput. Theory, 11(4), September 2019.
  * [Ang88] Dana Angluin.  Queries and concept learning.  Mach. Learn., 2(4):319–342, April 1988.
  * [BDWY11] Boaz Barak, Zeev Dvir, Avi Wigderson, and Amir Yehudayoff.  Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes.  In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC ’11, page 519–528, New York, NY, USA, 2011. Association for Computing Machinery.
  * [BSV21] Vishwas Bhargava, Shubhangi Saraf, and Ilya Volkovich.  Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits.  CoRR, abs/2105.01751, 2021.
  * [Car06] Enrico Carlini.  Reducing the number of variables of a polynomial.  In Mohamed Elkadi, Bernard Mourrain, and Ragni Piene, editors, Algebraic Geometry and Geometric Modeling, pages 237–247, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
  * [DS05] Zeev Dvir and Amir Shpilka.  Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits.  In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’05, page 592–601, New York, NY, USA, 2005. Association for Computing Machinery.
  * [Dvi12] Zeev Dvir.  Incidence theorems and their applications.  Foundations and Trends® in Theoretical Computer Science, 6(4):257–393, 2012.
  * [GKL04] Shuhong Gao, Erich Kaltofen, and Alan G.B. Lauder.  Deterministic distinct-degree factorization of polynomials over finite fields.  Journal of Symbolic Computation, 38(6):1461–1470, 2004.
  * [GKL12] Ankit Gupta, Neeraj Kayal, and Satyanarayana V. Lokam.  Reconstruction of depth-4 multilinear circuits with top fan-in 2.  In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 625–642, 2012.
  * [GKS20] Ankit Garg, Neeraj Kayal, and Chandan Saha.  Learning sums of powers of low-degree polynomials in the non-degenerate case.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 889–899, 2020.
  * [GM84] Shafi Goldwasser and Silvio Micali.  Probabilistic encryption.  Journal of Computer and System Sciences, 28(2):270–299, 1984.
  * [Ier89] Douglas John Ierardi.  The Complexity of Quantifier Elimination in the Theory of an Algebraically Closed Field.  PhD thesis, Cornell University, USA, 1989.  AAI9001370.
  * [IMGZ95] M. M. Kapranov I. M. Gelfand and A. Zelevinsky.  Discriminants, resultants and multidimensional determinants.  The Mathematical Gazette, 79(485):439–440, 1995.
  * [Kal91] Erich Kaltofen.  Effective noether irreducibility forms and applications.  In Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing, STOC ’91, pages 54–63, New York, NY, USA, 1991. ACM.
  * [Kay06] Neeraj Kayal.  Derandomizing some algebraic and number-theoretic algorithms, January 2006\.
  * [Kay11] Neeraj Kayal.  Efficient algorithms for some special cases of the polynomial equivalence problem.  In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’11, page 1409–1421, USA, 2011. Society for Industrial and Applied Mathematics.
  * [KC00] Valentine Kabanets and Jin-Yi Cai.  Circuit minimization problem.  In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC ’00, page 73–79, New York, NY, USA, 2000. Association for Computing Machinery.
  * [KS01] Adam R. Klivans and Daniel Spielman.  Randomness efficient identity testing of multivariate polynomials.  In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, STOC ’01, page 216–223, New York, NY, USA, 2001. Association for Computing Machinery.
  * [KS03] Adam R. Klivans and Amir Shpilka.  Learning arithmetic circuits via partial derivatives.  In Bernhard Schölkopf and Manfred K. Warmuth, editors, Learning Theory and Kernel Machines, pages 463–476, Berlin, Heidelberg, 2003\. Springer Berlin Heidelberg.
  * [KS09] Zohar S. Karnin and Amir Shpilka.  Reconstruction of generalized depth-3 arithmetic circuits with bounded top fan-in.  In Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, CCC ’09, pages 274–285, Washington, DC, USA, 2009\. IEEE Computer Society.
  * [KS18] Neeraj Kayal and Chandan Saha.  Reconstruction of non-degenerate homogeneous depth three circuits.  In STOC, 2018.
  * [KSS14] S. Kopparty, S. Saraf, and A. Shpilka.  Equivalence of polynomial identity testing and deterministic multivariate polynomial factorization.  In Computational Complexity (CCC), 2014 IEEE 29th Conference on, pages 169–180, June 2014.
  * [KT90] Erich Kaltofen and Barry M. Trager.  Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators.  J. Symb. Comput., 9:301–320, 1990.
  * [Laz01] Daniel Lazard.  Solving systems of algebraic equations.  SIGSAM Bull., 35(3):11–37, September 2001.
  * [LLL82] Arjen Lenstra, H. Lenstra, and Lovász László.  Factoring polynomials with rational coefficients.  Mathematische Annalen, 261, 12 1982.
  * [MP13] Gary L. Mullen and Daniel Panario.  Handbook of Finite Fields.  Chapman & Hall/CRC, 1st edition, 2013.
  * [Rab05] Michael O. Rabin.  How to exchange secrets with oblivious transfer, 2005.  Harvard University Technical Report 81<EMAIL_ADDRESS>12955 received 21 Jun 2005.
  * [Sax09] Nitin Saxena.  Progress on polynomial identity testing.  Bulletin of the EATCS, 99:49–79, 2009.
  * [Sch80] J. T. Schwartz.  Fast probabilistic algorithms for verification of polynomial identities.  J. ACM, 27(4):701–717, October 1980.
  * [Sho91] Victor Shoup.  A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic.  In Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, ISSAC ’91, page 14–21, New York, NY, USA, 1991. Association for Computing Machinery.
  * [Shp07] Amir Shpilka.  Interpolation of depth-3 arithmetic circuits with two multiplication gates.  SIAM J. Comput., 38:2130–2161, 2007.
  * [Sin16a] Gaurav Sinha.  Blackbox Reconstruction of Depth Three Circuits with Top Fan-In Two.  PhD thesis, California Institute of Technology, Pasadena, CA, USA, 2016\.
  * [Sin16b] Gaurav Sinha.  Reconstruction of real depth-3 circuits with top fan-in 2.  In Proceedings of the 31st Conference on Computational Complexity, CCC ’16, pages 31:1–31:53, Germany, 2016. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [SS11] Nitin Saxena and C. Seshadhri.  Blackbox identity testing for bounded top fanin depth-3 circuits: The field doesn’t matter.  In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC ’11, pages 431–440, New York, NY, USA, 2011. ACM.
  * [SS13] Nitin Saxena and C. Seshadhri.  From sylvester-gallai configurations to rank bounds: Improved blackbox identity test for depth-3 circuits.  J. ACM, 60(5), October 2013.
  * [SW99] Amir Shpilka and Avi Wigderson.  Depth-3 arithmetic circuits over fields of characteristic zero.  Computational Complexity, 10:1–27, 1999.
  * [SY10] 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.
  * [Vol16] Ilya Volkovich.  A guide to learning arithmetic circuits.  In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 1540–1561, Columbia University, New York, New York, USA, 23–26 Jun 2016. PMLR.
  * [vzGG13] Joachim von zur Gathen and Jürgen Gerhard.  Modern Computer Algebra.  Cambridge University Press, 3 edition, 2013.
  * [Wig06] Avi Wigderson.  P, np and mathematics - a computational complexity perspective.  Proceedings oh the International Congress of Mathematicians, Vol. 1, 2006-01-01, ISBN 978-3-03719-022-7, pags. 665-712, 1, 01 2006.
  * [Zip79] Richard Zippel.  Probabilistic algorithms for sparse polynomials.  In Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, EUROSAM ’79, page 216–226, Berlin, Heidelberg, 1979\. Springer-Verlag.

##  Appendix A Proof of Claims 4.1, 4.2 and 4.3

###  A.1 Proofs of Claims 4.1 and 4.2

In these claims we are given that $T_{i}=\alpha y_{1}^{t}$ for some
$i\in[2],\alpha\in\mathbb{F}$ and linear form $y_{1}$.

  1. 1.

To see the proof of Claim 4.1, consider any linear factor $\ell$ of
$T_{1}+T_{2}$. $\ell\nmid T_{1},T_{2}$ since $gcd(T_{1},T_{2})=1$. Let $\Phi$
be an isomorphism mapping $\ell\mapsto x_{1}$. Setting $x_{1}=0$, we get that
${\Phi(T_{1})}_{|_{x_{1}=0}}=-{\Phi(T_{2})}_{|_{x_{1}=0}}\neq 0$. Both sides
are non-zero products of linear forms in $\mathbb{F}[x_{2},\ldots,x_{n}]$.
Therefore, by unique factorization we can match factors (upto scalar
multiplication). This implies that $dim(\\{\text{linear form }\ell:\ell\mid
T_{1}\\})$ and $dim(\\{\text{linear form }\ell:\ell\mid T_{2}\\})$ cannot
differ from each other by more than $1$. But since
$rank(f)=\Omega(\log^{3}d)$, this cannot happen since one of the $T_{i}$’s
spans a one dimensional space. Therefore $T_{1}+T_{2}$ has no linear factors
and we are done.

  2. 2.

To see proof of Claim 4.2, without loss of generality assume $y_{1}\mid
T_{1}$. Define isomorphism $\Phi$ mapping $y_{1}\mapsto x_{1}$. Using Claim
4.1 we know that

$0\neq{\Phi(T_{2})}_{|_{x_{1}=0}}=(\Phi(T_{1})+\Phi(T_{2}))_{|_{x_{1}=0}}=\Phi(NonLin(f))_{|_{x_{1}=0}}$

So first condition of Definition 2.12 is satisfied. As argued in Claim 4.1,
$rank(f)\geq\Omega(\log^{3}d)\Rightarrow$ linear forms dividing $T_{2}$, span
a $\Omega(\log^{3}d)$ dimensional space. Since ${\Phi(T_{2})}_{|_{x_{1}=0}}$
is non-zero, it’s factors also span $\Omega(\log^{3}d)$ dimensional space and
so there exist two linearly independent factors $y_{2},y_{3}$ of $T_{2}$ such
that $NonLin(f)$ vanishes on both $\mathbb{V}(y_{1},y_{2})$ and
$\mathbb{V}(y_{1},y_{3})$. This implies that second condition of Definition
2.12 is also satisfied. Therefore, some scalar multiple of
$y_{1}\in\mathcal{L}(NonLin(f))$.

###  A.2 Proof of Claim 4.3

Recall definition of sets,

$\mathcal{L}_{good}=\\{\ell\in\mathcal{L}(NonLin(f)):\ell\mid T_{1}\times
T_{2}\\},\hskip
20.00003pt\mathcal{L}_{bad}=\mathcal{L}(NonLin(f))\setminus\mathcal{L}_{good},$
$\mathcal{L}_{others}=\\{\ell\mid T_{1}\times
T_{2}:sp(\ell)\cap\mathcal{L}(NonLin(f))=\phi\\}\hskip
10.00002pt\text{and}\hskip 10.00002pt\mathcal{L}_{factors}=\\{\ell:\ell\mid
T_{1}+T_{2}\\}$

For all sets, we keep linear forms upto scalar multiplication and therefore
treat them as proper sets (Definition 2.7). Below we prove all parts of Claim
4.3.

  1. 1.

$dim(sp(\mathcal{L}_{factors}))\leq\log d+2$: By definition
$\mathcal{L}_{factors}$ is the set of all factors of $T_{1}+T_{2}$. Consider
any linearly independent subset $\mathcal{Z}\subset\mathcal{L}_{factors}$ and
let $\ell\in\mathcal{Z}$. Define isomorphism $\Phi$ mapping $\ell\mapsto
x_{1}$. Setting $x_{1}=0$ in $\Phi(T_{1})+\Phi(T_{2})$ gives
${\Phi(T_{1})}_{|_{x_{1}=0}}=-{\Phi(T_{2})}_{|_{x_{1}=0}}\neq 0$. By unique
factorization in ring $\mathbb{F}[x_{2},\ldots,x_{n}]$, for every linear form
$\ell_{1}\mid T_{1}$ there exists $\ell_{2}\mid T_{2}$ such that $\ell_{2}\in
sp\\{\ell,\ell_{1}\\}$. Since $\ell_{2}\notin sp\\{\ell\\}\cup
sp\\{\ell_{1}\\}$, this means that $sp\\{\ell,\ell_{1}\\}$ is not an ordinary
line from $\ell$ into the proper set $\mathcal{L}$ containing linear factors
of $T_{1},T_{2}$. This set has size $\leq 2d$. Since $\ell$ was arbitrary in
$\mathcal{Z}$, there are no ordinary lines from $\mathcal{Z}$ into
$\mathcal{L}$. So using Lemma 6.2 we get that
$|\mathcal{Z}|\leq\log|\mathcal{L}|+1=\log d+2$, completing the proof.

  2. 2.

$dim(sp(\mathcal{L}_{good}))\geq rank(f)-2$ and $\mathcal{L}_{others}\leq 2$:
Define $V_{i}=\\{\text{linear form }\ell:\ell\mid T_{i}\\}$. We break the
proof into two cases. Note that linear forms dividing $T_{1},T_{2}$ satisfy
first condition of Definition 2.12. So whenever we are trying to show that
they belong to $\mathcal{L}(NonLin(f))$, we only prove that they satisfy
second condition of Definition 2.12.

    1. (a)

First we discuss the case $dim(V_{i})\geq\log d+5$ for all $i\in[2]$. Let $H$
be such that $T_{1}+T_{2}=H\times NonLin(f)$. Let $\ell_{1}\mid T_{1}$ and
$\Phi$ be isomorphism mapping $\ell_{1}\mapsto x_{1}$, then, we see that
${\Phi(T_{2})}_{|_{x_{1}=0}}=\Phi(H)_{|_{x_{1}=0}}\times\Phi(NonLin(f))_{|_{x_{1}=0}}\neq
0$. Dimension of span of linear factors of ${\Phi(T_{2})}_{|_{x_{1}=0}}$ is at
least $\log d+4$ by assumption in this case. By previous part,
$dim(sp(\mathcal{L}_{factors}))\leq\log
d+2\Rightarrow\Phi(NonLin(f))_{|_{x_{1}=0}}$ has two independent linear
factors. Using these we can satisfy second condition of Definition 2.12 for
$\ell_{1}\Rightarrow$ some scalar multiple of
$\ell_{1}\in\mathcal{L}(NonLin(f))$. The same argument can be repeated for a
linear factor $\ell_{2}\mid T_{2}$. Thus all linear factors of $T_{1}\times
T_{2}$ are in $\mathcal{L}(NonLin(f))$ (upto scalar multiplication)
$\Rightarrow$ $dim(\mathcal{L}_{good})=rank(f)$. This also implies that
$dim(\mathcal{L}_{others})=0$.

    2. (b)

In the case when $dim(V_{i})\leq\log d+4$ for some $i\in[2]$, we know that
$dim(V_{3-i})=\Omega(\log^{3}d)$ and therefore by an argument similar to the
one given in proof of Claim 4.1, $NonLin(f)=T_{1}+T_{2}$. Consider any basis
$\\{\ell_{1},\ldots,\ell_{r}\\}$ of $V_{1}+V_{2}$. If $dim(V_{i})\geq 3$ for
all $i\in[2]$, then using a similar argument as before, we can show that all
$\ell_{i}$ satisfy second condition in Definition 2.12 $\Rightarrow
dim(\mathcal{L}_{good})=rank(f)\Rightarrow dim(\mathcal{L}_{others})=0$. In
case for some $i\in[2]$, $dim(V_{i})=2$ (recall we have assumed
$dim(V_{i})\geq 2$ in the statement of Claim 4.3), then all linear forms
dividing $T_{3-i}$ are not contained in $V_{i}$ and hence satisfy second
condition of Definition 2.12. Thus $dim(\mathcal{L}_{good})\geq rank(f)-2$ and
$dim(\mathcal{L}_{others})\leq 2$.

  3. 3.

$dim(sp(\mathcal{L}_{bad}))\leq\log d+2$: Assume
$dim(\mathcal{L}_{bad})\geq\log d+3$. Consider the proper set $\mathcal{L}$
containing all linear factors of $T_{1},T_{2}\Rightarrow|\mathcal{L}|\leq
2d\Rightarrow|\mathcal{L}_{bad}|\geq\log|\mathcal{L}|+2$. Let
$\mathcal{T}\subset\mathcal{L}_{bad}$ be a linearly independent set of size
$\log|\mathcal{L}|+2$. Then by Proposition 1, there exists $t\in\mathcal{T}$
such that ordinary lines from $t$ into $\mathcal{L}$ span a space of dimension
$\geq\frac{dim(sp(\mathcal{L}))}{\log|\mathcal{L}|+2}\geq\frac{rank(f)}{\log
d+3}=\Omega(\log^{2}d)$. Since $t\in\mathcal{L}_{bad}$, restricting
$T_{1}+T_{2}$ to $\mathbb{V}(t)$ (see Definition 2.11) gives some non-zero
product of linear factors, say $H$. Let $\Phi$ be an isomorphism mapping
$t\mapsto x_{1}$. Then,

${\Phi(T_{1})}_{|_{x_{1}=0}}+{\Phi(T_{2})}{|_{x_{1}=0}}-H=0$

This gives an identically zero $\Sigma\Pi\Sigma(3,n,d,\mathbb{F})$ circuit.
Since $t\in\mathcal{L}_{bad}$, it does not divide $T_{1},T_{2}\Rightarrow$ the
above circuit is minimal (Definition 2.4). After cancelling common linear
forms from the three gates
${\Phi(T_{1})}_{|_{x_{1}=0}},{\Phi(T_{2})}_{|_{x_{2}=0}},H$, we have a simple
(Definition 2.3) and minimal, identically zero
$\Sigma\Pi\Sigma(3,n,d,\mathbb{F})$ circuit. The $\Omega(\log^{2}d)$ ordinary
lines from $t$ into $\mathcal{L}$ imply that after cancelling the common
linear forms, the simple minimal circuit has rank $\Omega(\log^{2}d)$ which is
a contradiction to Lemma 2.6. Thus we conclude that
$dim(sp(\mathcal{L}_{bad}))\leq\log d+2$.

##  Appendix B Proof of Lemma 5.2

Let $T_{i}=\prod\limits_{j=1}^{m}\ell_{i,j}$ where $\ell_{i,j}$ are linear
forms. We know that,

$\prod\limits_{j=1}^{m}{\Phi(\ell_{1,j})}_{|_{x_{1}=0,x_{2}=0}}=-\prod\limits_{j=1}^{m}{\Phi(\ell_{2,j})}_{|_{x_{1}=0,x_{2}=0}}\neq
0.$

Note that ${\Phi(\ell_{i,j})}_{|_{x_{1}=0,x_{2}=0}}$ can be thought of as
linear forms over $\mathbb{F}$ in $n-2$ variables, and by using unique
factorization of polynomials over $\mathbb{F}$, without loss of generality we
can assume
${\Phi(\ell_{1,j})}_{|_{x_{1}=0,x_{2}=0}}=\beta_{j}{\Phi(\ell_{2,j})}_{|_{x_{1}=0,x_{2}=0}}$
for some $0\neq\beta_{j}\in\mathbb{F}$. This implies272727since $\Phi$ is an
isomorphism.
$U_{j}=sp\\{\ell_{1,j},\ell_{2,j}\\}$282828$\ell_{1,j},\ell_{2,j}$ are
linearly independent since $gcd(T_{1},T_{2})=1$ intersects
$U=sp\\{\ell_{1},\ell_{2}\\}$ non-trivially. Since
${\Phi(\ell_{i,j})}_{|_{x_{1}=0,x_{2}=0}}\neq 0$, we know that $U\neq
U_{j}\Rightarrow U\cap U_{j}$ is $1$ dimensional292929since both $U,U_{j}$ are
$2$ dimensional. We split the proof into two cases:

  * •

There exist two distinct spaces, say $U_{i},U_{j}$ such that $U\cap
U_{i}=U\cap U_{j}$ : This implies $U\cap U_{i}\subset U_{i}\cap U_{j}$. The
space $U_{i}\cap U_{j}$ is $1$ dimensional since $U_{i},U_{j}$ are distinct,
say $U_{i}\cap U_{j}=sp\\{\ell\\}$. Both sides of the containment $U\cap
U_{i}\subset U_{i}\cap U_{j}$ are $1$ dimensional implying $U_{i}\cap
U_{j}=U\cap U_{i}\subset U=sp\\{\ell_{1},\ell_{2}\\}$. This further implies
that $\ell\in U\Rightarrow W\subset\mathbb{V}(\ell)=V$. There are $\leq d^{4}$
choices for such $U_{i},U_{j}$ and therefore $d^{4}$ possibilities for such
$V$.

  * •

For all distinct $U_{i},U_{j}$, $U\cap U_{i}\neq U\cap U_{j}$ : Vector space
$U\cap U_{i}+U\cap U_{j}$ is $2$ dimensional, since it is a sum of disjoint
$1$ dimensional spaces. $U$ is also $2$ dimensional $\Rightarrow U=U\cap
U_{i}+U\cap U_{j}\subset U_{i}+U_{j}$. Using statement of Proposition 1, we
know that

$5\leq
rank(f)=dim(sp\\{\ell_{i,j}\\})=dim(\sum\limits_{j=1}^{m}U_{j})\leq\sum\limits_{j=1}^{m}dim(U_{j}).$

$dim(U_{i}+U_{j})\leq 4$, thus there exists $U_{k}$ such that
$U_{k}\not\subset U_{i}+U_{j}$. Note that this would imply that
$U_{k}\cap(U_{i}+U_{j})$ has dimension $\leq 1$. Since $U\subset U_{i}+U_{j}$,
we get that $U_{k}\cap U\subset U_{k}\cap(U_{i}+U_{j})$. Both sides are $1$
dimensional. Writing $U_{k}\cap(U_{i}+U_{j})=sp\\{\ell\\}\Rightarrow\ell\in
U\Rightarrow W\subset\mathbb{V}(\ell)=V$. There are $\leq d^{6}$ choices for
$U_{i},U_{j},U_{k}$ and so $\leq d^{6}$ possibilities for such $V$.

$\mathcal{A}$ is collection of all $V$’s obtained above. $|\mathcal{A}|\leq
d^{4}+d^{6}$ and $\mathcal{A}$ satisfies the required conditions.

##  Appendix C Proofs of Lemmas in Algorithm 7

In this appendix, we provide proofs to lemmas that were stated and used in
Algorithm 7 but proofs were not provided.

###  C.1 Proof of Lemma 5.3

We prove each part one by one below. Let
$\hat{\ell}_{i}=\sum\limits_{j=1}^{n}\alpha_{i,j}x_{j},i\in[n]$ be the $n$
linear forms that were constructed using the uniformly randomly independently
samples $\alpha_{i,j},i\in[n],j\in[n]$. Recall that $\Phi$ maps
$x_{i}\mapsto\hat{\ell}_{i}$. Let $\Gamma$ be a homomorphism from
$\mathbb{F}[x_{1},\ldots,x_{n}]\rightarrow\mathbb{F}[x_{1},x_{2},x_{3},x_{4},x_{i}]$
that sets $x_{5}=0,\ldots,x_{i-1}=0,x_{i+1}=0,\ldots,x_{n}=0$.

  1. 1.

Showing that these linear forms are independent is equivalent to showing that
with probability $1-o(1)$, the matrix $(\alpha_{i,j})_{(i,j)\in[n]\times[n]}$
is invertible. This is equivalent to saying that the determinant polynomial of
this matrix is non-zero. Applying Lemma 2.3 on the determinant polynomial, we
get this result.

  2. 2.

Consider any isomorphism $\Psi$ mapping $\ell_{1}\mapsto x_{1},\ell_{2}\mapsto
x_{2}$, then $\Psi\circ\Phi^{-1}$ is an isomorphism mapping
$\Phi(\ell_{1})\mapsto x_{1},\Phi(\ell_{2})\mapsto x_{2}$. Further,
$\Psi(NonLin(f))=\Psi\circ\Phi^{-1}(\Phi(NonLin(f)))$. Restricting both sides
to $x_{1}=0,x_{2}=0$ gives,

$\Psi(NonLin(f))_{|_{x_{1}=0,x_{2}=0}}=\Psi\circ\Phi^{-1}(\Phi(NonLin(f)))_{|_{x_{1}=0,x_{2}=0}},$

implying that $NonLin(f)$ vanishes on $\mathbb{V}(\ell_{1},\ell_{2})$ if an
only if $\Phi(NonLin(f))$ vanishes on subspace
$\mathbb{V}(\Phi(\ell_{1}),\Phi(\ell_{2}))$. Since $\Phi$ is an isomorphism,
irreducible factors of $f$ remain irreducible on applying $\Phi$, thereby
implying that $\Phi(NonLin(f))=NonLin(\Phi(f))=NonLin(g)$. Hence claim is
proved.

  3. 3.

Recall $f=G\times(T_{1}+T_{2})$, with $G,T_{1},T_{2}$ being product of linear
forms and $gcd(T_{1},T_{2})=1$. Since $\Phi$ is an isomorphism, we get that
$g=\Phi(G)\times(\Phi(T_{1})+\Phi(T_{2}))$. Since $\Phi$ is an isomorphism,
$gcd(\Phi(T_{1}),\Phi(T_{2}))=1$. Therefore we get,

$g_{i}=\Gamma(g)=\Gamma(\Phi(G))(\Gamma(\Phi(T_{1}))+\Gamma(\Phi(T_{2}))).$

Next, consider linear forms $\ell=\sum\limits_{j=1}^{n}a_{j}x_{j}$ and
$\ell^{\prime}=\sum\limits_{j=1}^{n}a_{j}^{\prime}x_{j}$ such that $\ell\mid
T_{1}$ and $\ell^{\prime}\mid T_{2}$. Applying $\Phi$ to these linear forms we
get,
$\Phi(\ell)=\sum\limits_{k=1}^{n}\sum\limits_{j=1}^{n}a_{j}\alpha_{j,k}x_{k}$.
Therefore coefficients of $x_{1},x_{2}$ in $\Gamma(\Phi(\ell))$ are
$\sum\limits_{j=1}^{n}a_{j}\alpha_{j,1},\sum\limits_{j=1}^{n}a_{j}\alpha_{j,2}$
respectively and those in $\Gamma(\Phi(\ell^{\prime}))$ are
$\sum\limits_{j=1}^{n}a_{j}^{\prime}\alpha_{j,1},\sum\limits_{j=1}^{n}a_{j}^{\prime}\alpha_{j,2}$.
We argue that vectors
$(\sum\limits_{j=1}^{n}a_{j}\alpha_{j,1},\sum\limits_{j=1}^{n}a_{j}\alpha_{j,2})$
and
$(\sum\limits_{j=1}^{n}a_{j}^{\prime}\alpha_{j,1},\sum\limits_{j=1}^{n}a_{j}^{\prime}\alpha_{j,2})$
are not scalar multiples with probability $1-o(1)$. This is equivalent to
showing that the following determinant is non-zero.

$\begin{vmatrix}\sum\limits_{j=1}^{n}a_{j}\alpha_{j,1}&\sum\limits_{j=1}^{n}a_{j}\alpha_{j,2}\\\
\sum\limits_{j=1}^{n}a_{j}^{\prime}\alpha_{j,1}&\sum\limits_{j=1}^{n}a_{j}^{\prime}\alpha_{j,2}\end{vmatrix}$

If $\ell,\ell^{\prime}$ are not scalar multiples, this determinant is not an
identically zero polynomial in the $\alpha_{j,k},j\in[n],k\in[2]$ and
therefore probability (over the random choices of $\alpha_{j,k}$) that the
determinant is non-zero $=1-o(1)$. Therefore with probability $1-o(1)$,
$\Gamma(\Phi(\ell))$ and $\Gamma(\Phi(\ell^{\prime}))$ are not scalar
multiples. Since $\ell,\ell^{\prime}$ are arbitrary linear factors of
$T_{1},T_{2}$ respectively, by union bound with probability $1-o(1)$,
$gcd(\Gamma(\Phi(T_{1})),\Gamma(\Phi(T_{2})))=1$ implying that all $g_{i}$
exhibit $\Sigma\Pi\Sigma(2,5,d,\mathbb{F})$ circuit. Since
$rank(f)=\Omega(\log^{2}d)$, we know that $dim(sp\\{\text{linear form
}\ell:\ell\mid T_{1}\times T_{2}\\})\geq 5$, therefore, a similar argument
(again using Lemma 2.3), can be used to say that
$\\{\Gamma(\Phi(\ell)):\text{linear form }\ell\mid T_{1}\times T_{2}\\}$ spans
a $5$ dimensional space. This set is the same as $\\{\text{linear form
}\ell:\ell\mid\Gamma(\Phi(T_{1}))\times\Gamma(\Phi(T_{2}))\\})\\}$, proving
that $rank(g_{i})=5$ for all $i\in[5,n]$.

  4. 4.

By effective Hilbert’s irreducibility theorem (Lemma 2.8), we know that with
probability $1-o(1)$ over the $\alpha_{i,j},i\in[n],j\in[n]$, the irreudicible
factors of $\Phi(f)(x_{1},\ldots,x_{n})=f(\Phi(x_{1}),\ldots,\Phi(x_{n}))$
remain irreducible on setting
$x_{5}=0,\ldots,x_{i-1}=0,x_{i+1}=0,\ldots,x_{n}=0$ i.e. on applying $\Gamma$.
Example if $h$ is an irreducible factor of $f$, then $\Gamma(\Phi(h))$ is an
irreducible factor of $\Gamma(\Phi(f))$. The same will apply to product (with
multiplicity) of all non-linear irreducible factors implying that,

$NonLin(\Gamma(\Phi(f)))=\Gamma(NonLin(\Phi(f))).$

The left hand side is same as polynomial $NonLin(g_{i})$ and right hand side
is same as polynomial
$NonLin(g)_{|_{x_{5}=0,\ldots,x_{i-1}=0,x_{i+1}=0,\ldots,x_{n}=0}}$. Hence
Proved.

  5. 5.

Let $\mathbb{V}(\hat{\ell}_{1},\hat{\ell_{2}})$ belong to
$\mathcal{S}(NonLin(f))$. Assume
$\hat{\ell}_{1}=\sum\limits_{j=1}^{n}a_{j}x_{j}$ and
$\hat{\ell}_{2}=\sum\limits_{j=1}^{n}b_{j}x_{j}$, Then we get that
$\Phi(\hat{\ell}_{1})=\sum\limits_{k=1}^{n}(\sum\limits_{j=1}^{n}a_{j}\alpha_{j,k})x_{k}$
and
$\Phi(\hat{\ell}_{2})=\sum\limits_{k=1}^{n}(\sum\limits_{j=1}^{n}b_{j}\alpha_{j,k})x_{k}$.
We define $c_{k}=\sum\limits_{j=1}^{n}a_{j}\alpha_{j,k}$ an
$d_{k}=\sum\limits_{j=1}^{n}b_{j}\alpha_{j,k}$ for $k\in[n]$. Therefore
$\Phi(\hat{\ell}_{1})=\sum\limits_{k=1}^{n}c_{k}x_{k}$ and
$\Phi(\hat{\ell}_{2})=\sum\limits_{k=1}^{n}d_{k}x_{k}$. Now we define new
linear forms as follows:

$\displaystyle\begin{bmatrix}\ell_{3}\\\
\ell_{4}\end{bmatrix}=\begin{bmatrix}d_{2}&-c_{2}\\\
-d1&c_{1}\end{bmatrix}\begin{bmatrix}\Phi(\hat{\ell}_{1})\\\
\Phi(\hat{\ell}_{2})\end{bmatrix}$ (1)

Determinant of the matrix is $d_{2}c_{1}-c_{2}d_{1}$. This defines a
polynomial in the $\alpha_{j,k},j\in[n],k\in[2]$. Like in the previous part,
unless $\hat{\ell}_{1},\hat{\ell}_{2}$ are linearly dependent this polynomial
is not identically $0$. Therefore with probability $1-o(1)$ over the uniformly
randomly chosen linear forms in Step $1$, the determinant is non-zero implying
that $d_{2}c_{1}-c_{2}d_{1}\neq 0$. This also means that $\ell_{3},\ell_{4}$
are linearly independent and
$\mathbb{V}(\ell_{3},\ell_{4})=\mathbb{V}(\Phi(\hat{\ell}_{1}),\Phi(\hat{\ell}_{2}))$.
Analyzing $\ell_{3},\ell_{4}$ we see that,

$\ell_{3}=(d_{2}c_{1}-c_{2}d_{1})x_{1}+\sum\limits_{k=3}^{n}(d_{2}c_{k}-c_{2}d_{k})x_{k},and$
$\ell_{4}=(d_{2}c_{1}-c_{2}d_{1})x_{2}+\sum\limits_{k=3}^{n}(d_{k}c_{1}-c_{k}d_{1})x_{k}.$

Define
$\ell_{1}^{\prime}=-\sum\limits_{k=3}^{n}\frac{d_{2}c_{k}-c_{2}d_{k}}{d_{2}c_{1}-c_{2}d_{1}}x_{k}$,
and
$\ell_{2}^{\prime}=-\sum\limits_{k=3}^{n}\frac{d_{k}c_{1}-c_{k}d_{1}}{d_{2}c_{1}-c_{2}d_{1}}x_{k}$,
further implying that
$\mathbb{V}(\ell_{1},\ell_{2})=\mathbb{V}(x_{1}-\ell_{1}^{\prime},x_{2}-\ell_{2}^{\prime})$
with $\ell_{1}^{\prime},\ell_{2}^{\prime}\in\mathbb{F}[x_{3},\ldots,x_{n}]$.
Now since $\mathcal{S}(NonLin(f))$ has size $d^{O(1)}$, by union bound, with
probability $1-o(1)$, we can prove all of this for every
$\mathbb{V}(\hat{\ell}_{1},\hat{\ell_{2}})\in\mathcal{S}(NonLin(f))$.

Now, given any $\mathbb{V}(\ell_{1},\ell_{2})\in\mathcal{S}(NonLin(g))$, by
Part $2$ of this Lemma, we know that
$\mathbb{V}(\ell_{1},\ell_{2})\in\mathcal{S}(NonLin(g))$ if and only if
$\mathbb{V}(\Phi^{-1}(\ell_{1}),\Phi^{-1}(\ell_{2}))\in\mathcal{S}(NonLin(g))$.
So we can use our argument for $\hat{\ell}_{1}=\Phi^{-1}(\ell_{1})$, and
$\hat{\ell}_{2}=\Phi^{-1}(\ell_{2})$, thereby completing the proof.

  6. 6.

Let $\mathbb{V}(\ell_{1},\ell_{2})\in\mathcal{S}(NonLin(g))$ and
$\ell_{j}^{i}={\ell_{j}}_{|_{x_{5}=0,\ldots,x_{i-1}=0,x_{i+1}=0,\ldots,x_{n}=0}}$.
By previous part we know that there exists
$\ell_{1}^{\prime},\ell_{2}^{\prime}\in\mathbb{F}[x_{3},\ldots,x_{n}]$ such
that
$\mathbb{V}(\ell_{1},\ell_{2})=\mathbb{V}(x_{1}-\ell_{1}^{\prime},x_{2}-\ell_{2}^{\prime})$.
Let $\Theta$ be an isomorphism mapping $x_{1}-\ell_{1}^{\prime}\mapsto
x_{1},x_{2}-\ell_{2}^{\prime}\mapsto x_{2}$ and for $j\in[3,n]$, $x_{j}\mapsto
x_{j}$. Similarly let $\Theta^{\prime}$ be isomorphism on
$\mathbb{F}[x_{1},x_{2},x_{3},x_{4},x_{i}]$ mapping
$x_{1}-\ell_{1}^{\prime\prime}\mapsto
x_{1},x_{2}-\ell_{2}^{\prime\prime}\mapsto x_{2}$ and for $j\in\\{3,4,i\\}$,
$x_{j}\mapsto x_{j}$. Finally let $\Gamma$ be the homomorphism from
$\mathbb{F}[x_{1},\ldots,x_{n}]$ to
$\mathbb{F}[x_{1},x_{2},x_{3},x_{4},x_{i}]$ mapping $x_{j}\mapsto 0$ for all
$j\in[5,i-1]\cup[i+1,n]$. The following diagram commutes.

${\mathbb{F}[x_{1},\ldots,x_{n}]}$${\mathbb{F}[x_{1},\ldots,x_{n}]}$${\mathbb{F}[x_{1},x_{2},x_{3},x_{4},x_{i}]}$${\mathbb{F}[x_{1},x_{2},x_{3},x_{4},x_{i}]}$$\scriptstyle{\Theta}$$\scriptstyle{\Gamma}$$\scriptstyle{\Gamma}$$\scriptstyle{\Theta^{\prime}}$

We know that $NonLin(g)$ vanishes on
$\mathbb{V}(x_{1}-\ell_{1}^{\prime},x_{2}-\ell_{2}^{\prime})$, therefore
$\Theta(NonLin(g))_{|_{x_{1}=0,x_{2}=0}}=0$, implying that
$\Gamma(\Theta(NonLin(g))_{|_{x_{1}=0,x_{2}=0}})=0$. We know that $\Gamma$
fixes $x_{1},x_{2}$ therefore we can set $x_{1}=0,x_{2}=0$ after applying
$\Gamma$, thereby giving $\Gamma(\Theta(NonLin(g)))_{|_{x_{1}=0,x_{2}=0}}=0$.
Using the above commutative diagram we get,
$\Theta^{\prime}(\Gamma(NonLin(g)))_{|_{x_{1}=0,x_{2}=0}}=0$. Now, Part $4$ of
this lemma gives $NonLin(g_{i})=\Gamma(NonLin(g))$. Using this we get,
$\Theta^{\prime}(NonLin(g_{i}))_{|_{x_{1}=0,x_{2}=0}}=0$. Therefore
$NonLin(g_{i})$ vanishes on the co-dimension $2$ subspace
$\mathbb{V}(x_{1}-{\ell_{1}}^{\prime\prime},x_{2}-{\ell_{2}}^{\prime\prime})$
of $\mathbb{F}^{5}$, thereby completing the proof.

###  C.2 Proof of Lemma 5.4

Fix $i\in[6,n]$. Consider a pair of distinct tuples
$(x_{1}-\ell_{1},x_{2}-\ell_{2})$,
$(x_{1}-\ell_{1}^{\prime},x_{2}-\ell_{2}^{\prime})$ in $\mathcal{S}_{i}$. By
construction,
$\ell_{1},\ell_{2},\ell_{1}^{\prime},\ell_{2}^{\prime}\in\mathbb{F}[x_{3},x_{4},x_{i}]$.
So we assume that, $\ell_{1}=a_{3}x_{3}+a_{4}x_{4}+a_{i}x_{i}$,
$\ell_{2}=b_{3}x_{3}+b_{4}x_{4}+b_{i}x_{i}$,
$\ell_{1}^{\prime}=a_{3}^{\prime}x_{3}+a_{4}^{\prime}x_{4}+a_{i}^{\prime}x_{i}$
and
$\ell_{2}^{\prime}=b_{3}^{\prime}x_{3}+b_{4}^{\prime}x_{4}+b_{i}^{\prime}x_{i}$.
Therefore,

$\begin{split}&\Delta(\ell_{1})=(a_{3}+\alpha_{i,3}a_{i})x_{3}+(a_{4}+\alpha_{i,4}a_{i})x_{4}+a_{i}x_{i},\\\
&\Delta(\ell_{2})=(b_{3}+\alpha_{i,3}b_{i})x_{3}+(b_{4}+\alpha_{i,4}b_{i})x_{i}+b_{i}x_{i},\\\
&\Delta(\ell_{1}^{\prime})=(a_{3}^{\prime}+\alpha_{i,3}a_{i}^{\prime})x_{3}+(a_{4}^{\prime}+\alpha_{i,4}a_{i}^{\prime})x_{4}+a_{i}^{\prime}x_{i},\\\
&\Delta(\ell_{2}^{\prime})=(b_{3}^{\prime}+\alpha_{i,3}b_{i}^{\prime})x_{3}+(b_{4}^{\prime}+\alpha_{i,4}b_{i}^{\prime})x_{4}+b_{i}^{\prime}x_{i}\end{split}$

If
$(\Delta(\ell_{1})_{|_{x_{i}=0}},\Delta(\ell_{2})_{|_{x_{i}=0}})=(\Delta(\ell_{1}^{\prime})_{|_{x_{i}=0}},\Delta(\ell_{2}^{\prime})_{|_{x_{i}=0}})$,
then we get a system of linear equations in $\alpha_{i,3},\alpha_{i,4}$ which
can be simplified to get

$\begin{bmatrix}\alpha_{i,3}(a_{i}-a_{i}^{\prime})\\\
\alpha_{i,4}(a_{i}-a_{i}^{\prime})\\\ \alpha_{i,3}(b_{i}-b_{i}^{\prime})\\\
\alpha_{i,4}(b_{i}-b_{i}^{\prime})\end{bmatrix}=\begin{bmatrix}a_{3}^{\prime}-a_{3}\\\
a_{4}^{\prime}-a_{4}\\\ b_{3}^{\prime}-b_{3}\\\
b_{4}^{\prime}-b_{4}\end{bmatrix}$

Since tuples $(\ell_{1},\ell_{2})$ and $(\ell_{1}^{\prime},\ell_{2}^{\prime})$
are distinct, at least one of
$(a_{3}^{\prime}-a_{3}),(a_{i}-a_{i}^{\prime}),(a_{4}^{\prime}-a_{4}),(b_{i}-b_{i}^{\prime}),(b_{3}^{\prime}-b_{3}),(b_{4}^{\prime}-b_{4})$
is non-zero implying that at least one linear equation is not identically
zero. By Lemma 2.3, we then know that with probability $1-o(1)$ over the
uniformly random choices of $\alpha_{i,3},\alpha_{i,4}$ the equation cannot be
zero. Therefore with probability $1-o(1)$,
$(\Delta(\ell_{1})_{|_{x_{i}=0}},\Delta(\ell_{2})_{|_{x_{i}=0}})\neq(\Delta(\ell_{1}^{\prime})_{|_{x_{i}=0}},\Delta(\ell_{2}^{\prime})_{|_{x_{i}=0}})$.
Using Part $3$ of Lemma 5.3, we know that $rank(NonLin(g_{i}))=5$ implying
that $|\mathcal{S}_{i}|=d^{O(1)}$. So we can take a union bound over all pairs
of tuples in $\mathcal{S}_{i}$. Finally, we take a union bound over all $i$
and guarantee that with probability $1-o(1)$, the statement in this lemma
holds.