# Relative rank and regularization

Amichai Lampert and Tamar Ziegler

###### Abstract.

We introduce a new notion of rank - relative rank associated to a filtered
collection of polynomials. When the filtration consists of one set the notion
coincides with the Schmidt rank (also called strength). We also introduce the
notion of relative bias. We prove a relation between these two notions over
finite fields. This allows us to perform a regularization procedure in a
number of steps that is polynomial in the initial number of polynomials. As an
application we prove that any collection of homogeneous polynomials
$\mathcal{P}=(P_{i})_{i=1}^{c}$ of degrees $\leq d$ in a polynomial ring over
an algebraically closed field of characteristic $>d$ is contained in an ideal
$\mathcal{I}(\mathcal{Q})$, generated by a collection $\mathcal{Q}$ of
homogeneous polynomials of degrees $\leq d$ which form a regular sequence, and
$\mathcal{Q}$ is of size $\leq Ac^{A}$, where $A=A(d)$ is independent of the
number of variables.

The authors are supported by ERC grant ErgComNum 682150, and ISF grant
2112/20.

##  1\. introduction

In [23] Schmidt introduced a notion of complexity, the Schmidt rank (also
called the $h$-invariant)111This notion of complexity was reintroduced later
in the work of Ananyan and Hochster [2] in their proof of Stillman’s
conjecture where it is called strength. for a collection of polynomials
$\mathcal{P}=(P_{i})_{i=1}^{c}$, and used it to obtain conditions on for the
existence of integer solutions for a system of equations
$\\{P_{i}(x)=0\\}_{i=1}^{c}$ defined over the rational numbers. The most
natural polynomials on which to define this quantity are homogeneous ones. If
$P$ is a polynomial of degree $d$ we denote by $\tilde{P}$ the degree $d$
homogeneous component of $P.$

######  Definition 1.1 (Schmidt Rank).

The Schimdt rank of a homogeneous polynomial
$P\in\mathbb{F}[x_{1},\ldots,x_{n}]$ is the minimal length of a presentation
$P=\sum_{i=1}^{r}Q_{i}R_{i},$ where for all $i\in[r],\ Q_{i},R_{i}$ are
homogeneous polynomials of degree $<\deg(P),$ and is denoted by $rk(P).$ For a
general polynomial $P$ we set $rk(P)=rk(\tilde{P}).$ The rank of a collection
of homogeneous polynomials $\mathcal{P}=(P_{i})_{i=1}^{c}$ is

$rk(\mathcal{P})=\min\\{rk(a_{1}P_{1}+\ldots+a_{c}P_{c}):\ 0\neq
a\in\mathbb{F}^{c}\\}.$

If $\mathcal{P}$ is a general collection of polynomials we set
$rk(\mathcal{P})=rk(\tilde{\mathcal{P}}),$ where
$\tilde{\mathcal{P}}=(\tilde{P}_{i})_{i=1}^{c}.$

Now assume $\mathbb{F}=\mathbb{F}_{q}$ is a finite field and fix a non-trivial
character $\chi:\mathbb{F}\to{\mathbb{C}}.$ We define the bias of a polynomial
as follows.

######  Definition 1.2.

For a function $P:\mathbb{F}^{n}\to\mathbb{F}$ we define

$bias(P)=\left|{\mathbb{E}}_{x\in\mathbb{F}^{n}}\chi(P(x))\right|,$

where ${\mathbb{E}}_{x\in E}:=\frac{1}{|E|}\sum_{x\in E}$ for a finite set
$E,$ with the convention ${\mathbb{E}}_{x\in\emptyset}=0.$ This quantity may
of course depend on $\chi,$ but we omit it from the notation.222For
multilinear polynomials $bias(P)$ does not depend on the character $\chi$; in
this case $-\log_{q}(bias(P))$ was introduced in [11] as the analytic rank of
$P$.

The relation between bias and rank can already be traced to the work of
Schmidt; indeed, in his paper [23] Schmidt showed that over the complex field
the Schmidt rank of a polynomial is proportional to the codimension of the
singular locus of the associated variety and used this for estimating related
exponential sums.

In [10] Green and Tao observed that one can make the relation independent of
the number of variables: 333They use a slightly weaker definition of rank, but
the results in their paper imply the theorem as stated.

######  Theorem 1.3 (Bias implies low rank).

Let $\mathbb{F}=\mathbb{F}_{q}$ be a finite field, let $0\leq
d<char(\mathbb{F})$, and let $s>0$. There exists a constant
$C=C(\mathbb{F},s,d)$ such that the following holds: For any $n$,
$P\in\mathbb{F}[x_{1},\ldots,x_{n}]$ of degree $\leq d$ with $bias(P)\geq
q^{-s}$, we have $rk(P)\leq C$.

This result was subsequently extended to include the case $d\geq
char(\mathbb{F})$ by Kauffman and Lovett in [13]. Bhowmick and Lovett [3]
showed that the bound can be made independent of the field $\mathbb{F}$ in the
sense that we can take $C=C(s,d).$ Returning to the case $d<char(\mathbb{F})$,
effective bounds for $C$ were given by Milicevic [21] who proved

$C=A(d)(1+s)^{B(d)}.$

Independently, Janzer [12] proved a similar, slightly weaker result with
$s\log q$ instead of $s$.

######  Conjecture 1.4.

For all finite fields $\mathbb{F}$ with $char(\mathbb{F})>d$ we have
$C(\mathbb{F},s,d)=A(d)(1+s)$.

Conjecture 1.4 was recently proved in the case $d=3$ in [1], [5]
independently.

A key feature of high rank collections of polynomials, that can be easily
derived from Theorem 1.3, is that all fibers of the map
$\mathcal{P}:\mathbb{\mathbb{F}}^{n}\to\mathbb{\mathbb{F}}^{c}$ are
essentially of the same size.

######  Theorem 1.5 (Size of fibers).

Let $d>0$. Let $\mathbb{F}=\mathbb{F}_{q}$ be a finite field of characteristic
$>d$. There exists $A=A(d)$ such that the following holds: For any $n$, any
collection of polynomials $\mathcal{P}=(P_{i})_{i=1}^{c}$ in
$\mathbb{F}[x_{1},\ldots,x_{n}]$ of degrees $\leq d$ and rank $>Ac^{A}$, any
$a,b\in\mathbb{F}^{c}$ we have
$||\mathcal{P}^{-1}(a)|/|\mathcal{P}^{-1}(b)|-1|<q^{-1}$.

Using model theoretic techniques one can translate the data in Theorem 1.5 to
an estimate of the dimension of the fibers of the map
$\mathcal{P}:\mathbb{\mathbb{A}}^{n}\to\mathbb{A}^{c}$ for any algebraically
closed field of characteristic zero or $>\max\deg P_{i}$, see e.g. [16, 15].

In many proofs using the notion of Schmidt rank, a key procedure is
regularization (e.g. [23], [3], [6]): given a collection of polynomials, one
applies procedure replacing the original collection of polynomials
$\mathcal{P}$ with a new collection $\mathcal{Q}$ that is of high Schmidt rank
compared to its size, (so Theorem 1.5 holds) and such that the ideal generated
by $\mathcal{P}$ is contained in the ideal generated by $\mathcal{Q}$. The
drawback in this regularization procedures is that the size of $\mathcal{Q}$
is far worse than even tower exponential in the size of $\mathcal{P}$ (the
bound that can be derived from Schmidts argument was worked out by Wooley in
[25]).

We introduce a new notion of rank relative rank, associated with a filtered
collection of polynomials, both in the algebraic and analytic contexts. We
replace the ambient space $\mathbb{F}^{n}$ by certain affine varieties and we
replace Schmidt rank by an appropriate relative rank. The definition of
relative rank is somewhat technical; we defer it to the next section
(Definition 2.1). We remark that the new notion of relative rank coincided
with the Schmidt rank and the analytic rank when the filtration consists of
one set, but is different otherwise.

Our main result (Theorem 2.2), described in detail in the next section, is a
relation between relative rank and relative bias, similar to the relation
described above between rank and bias. The key advantage in our new notion of
rank, is that while it retains many of the properties of the ranks described
above, for example Theorem 1.5 remains valid, the regularization procedure
with respect to this notion is polynomial in the size of the original
collection. As such we are able to give good quantitative bounds on a variety
of problems in which a regularization procedure is used. We provide an example
of an algebraic application in Theorem 2.6.

In the interest of exposition, we will start by presenting a special case of
our main result. This special case is actually the result we initially set out
to prove. First we give our definitions of relative rank and relative bias.

######  Definition 1.6 (Relative rank).

The relative rank of a homogeneous polynomial $P$ on a collection of
homogeneous polynomials $\mathcal{Q}=(Q_{1},\ldots,Q_{m})$ is

$rk_{\mathcal{Q}}(P):=\min\\{rk(P+\sum_{i=1}^{m}R_{i}Q_{i}):\deg(R_{i})+\deg(Q_{i})\leq\deg(P)\
\forall i\in[m]\\}.$

Note that whenever $\deg(Q_{i})>\deg(P)$ this implies $R_{i}=0.$ For general
polynomials, with $\tilde{P},\tilde{\mathcal{Q}}$ the corresponding
homogeneous polynomial and collection, set
$rk_{\mathcal{Q}}(P):=rk_{\tilde{\mathcal{Q}}}(\tilde{P}).$

######  Definition 1.7 (Relative bias).

The relative bias of a function $P:\mathbb{F}^{n}\to\mathbb{F}$ on a subset
$X\subset\mathbb{F}^{n}$ is

$bias_{X}(P)=\left|{\mathbb{E}}_{x\in X}\chi(P(x))\right|.$

For a collection $\mathcal{Q}=(Q_{i})_{i\in[m]}$ of polynomials in
$\mathbb{F}[x_{1},\ldots,x_{n}]$, denote the zero locus by

$Z(\mathcal{Q})=\left\\{x\in\mathbb{F}^{n}:Q_{i}(x)=0\ \forall
i\in[m]\right\\}.$

A special case of our main result is then:

######  Theorem 1.8.

Let $\mathbb{F}$ be a finite field and $0\leq d<char(\mathbb{F}).$ There exist
constants $A(d),B(d)$ such that if $\mathcal{Q}=(Q_{i})_{i=1}^{m}$ is a
collection of polynomials with degrees $\leq d$ with
$rk(\mathcal{Q})>A(m+s)^{B}$ and $P$ is a polynomial of degree $\leq d$ with
$bias_{Z(\mathcal{Q})}(P)\geq q^{-s}$ then we have

$rk_{\mathcal{Q}}(P)\leq A(1+s)^{B}.$

We briefly pause here and compare this to the result of Milicevic (and
Janzer). For $\mathcal{Q}=\emptyset$ this gives a new proof of their result.
Moreover, when $m\leq s$ or when $\mathcal{Q}$ is composed of polynomials of
degree $\geq\deg(P)$ the above theorem in fact follows from their result. But
it is new in the case that $\mathcal{Q}$ is composed of $\gg s$ polynomials of
lower degree than $P.$

_Acknowledgements._ The first author would like to thank the second author for
introducing him to this question and its various applications. He would also
like to thank his wife Noa for her constant support and encouragement.

##  2\. Main theorem

We now give our definitions in full and state our main theorem.

######  Definition 2.1.

  1. (1)

The relative rank of a collection of homogeneous polynomials
$\mathcal{P}=(P_{i})_{i\in[m]}$ on another collection of polynomials
$\mathcal{Q}$ is

$rk_{\mathcal{Q}}(\mathcal{P})=\min\left\\{rk_{\mathcal{Q}}\left(a\cdot\mathcal{P}\right):\
0\neq a\in\mathbb{F}^{m}\right\\}.$

If $\mathcal{P}$ is a general collection of polynomials with corresponding
homogeneous collection $\tilde{\mathcal{P}},$ then
$rk_{\mathcal{Q}}(\mathcal{P})=rk_{\mathcal{Q}}(\tilde{\mathcal{P}}).$

  2. (2)

A tower

$\mathcal{Q}=(Q_{i})_{i\in[h]}$

of height $h$ is composed of $h$ collections of polynomials
$\mathcal{Q}_{i}=(Q_{i,j})_{j\in[m_{i}]}$ which we call layers such that the
polynomials in each layer all have the same degree $d_{i}.$ The degree of the
tower is $\max\left(d_{1},\ldots,d_{h}\right)$ The dimension of the tower is
$m_{1}+\ldots+m_{h}.$ We denote the truncated tower
$\mathcal{Q}_{<i}=(\mathcal{Q}_{j})_{j\in[i-1]}.$

  3. (3)

The tower $\mathcal{Q}$ is $(A,B,s)$-regular if for every $i\in[h]$ we have

$rk_{\mathcal{Q}_{<i}}(\mathcal{Q}_{i})>A(m_{i}+m_{i+1}+\ldots+m_{h}+s)^{B}.$

The main theorem we prove is the following:

######  Theorem 2.2 (Relative bias implies relative low rank).

There exist constants $A(d,H),B(d,H)$ such that if $\mathcal{Q}$ is an
$(A,B,s)$-regular tower of degree $\leq d<char(\mathbb{F})$ and height $\leq
H,$ and $P$ is a polynomial of degree $\leq d$ with

$bias_{Z(\mathcal{Q})}(P)\geq q^{-s}.$

then

$rk_{\mathcal{Q}}(P)\leq A(1+s)^{B}.$

Theorem 2.2 implies that relatively regular collections of polynomials enjoy
similar equidistribution properties to those of high rank collections of
polynomials. In fact, all the results in [15, 16, 17], [3] which were proved
for collections of polynomials of high rank, are also valid for relatively
regular collections of polynomials. Some examples of results which transfer
seamlessly to the relatively regular setting are given in the Appendix.

For a collection of polynomials $\mathcal{Q},$ we write $I(\mathcal{Q})$ for
the ideal they generate. In many applications of the notion of rank (e.g [23],
[6]) one is given a collection of polynomials, to which one applies a
regularization process, replacing the original collection $\mathcal{Q}$ with a
new regular collection $\mathcal{Q}^{\prime}$, such that any
$\mathcal{Q}\subset I(\mathcal{Q}^{\prime}).$ The issue is that the
regularization process is very costly (see [25]). One of the advantages of
relative rank is that it allows a very efficient process of regularization.

######  Theorem 2.3 (Polynomial regularity).

Let $A,B,d$ be given. There exist constants $C(A,B,d),D(A,B,d)$ such that if
$\mathcal{Q}$ is a collection of $m$ polynomials of degree $\leq d$, then
there exists a polynomial tower $\mathcal{Q}^{\prime}$ of dimension $\leq
C(m+s)^{D}$ of degree $\leq d$ and height $\leq d$ such that
$\mathcal{Q}^{\prime}$ is $(A,B,s)$ regular, and $\mathcal{Q}\subset
I(\mathcal{Q}^{\prime}).$

######  Definition 2.4.

A collection of polynomials
$\mathcal{Q}=(Q_{i})_{i=1}^{m}\subset\mathbb{F}[x_{1},\ldots,x_{n}]$ is
$s$-uniform if

$\left|\frac{|Z(\mathcal{Q})|}{q^{n-m}}-1\right|\leq q^{-s}.$

As a corollary of Theorem 2.2 we obtain:

######  Lemma 2.5 (Regular varieties are of the expected size).

There exist constants $A(d,H),B(d,H)$ such that any $(A,B,s)$-regular
polynomial tower $\mathcal{Q}$ of degree $\leq d<char(\mathbb{F})$ and height
$\leq H$ is $s$-uniform.

In particular we obtain the following algebraic consequence:

######  Theorem 2.6.

Let $d>0$. Let $\mathbb{F}$ be an algebraically closed field of characteristic
zero or $>d$. Let $\mathcal{P}$ be a collection of $c$ polynomials of degree
$\leq d$. There exists $A=A(d)$ and a collection $\mathcal{Q}$ of dimension
$\leq Ac^{A}$ of polynomials of degree $\leq d$ such that $\mathcal{Q}$ is a
regular sequence, and $P_{i}\in\mathcal{I}(\mathcal{Q})$.

We prove Theorem 2.6 in the Appendix; it follows from Theorem 2.3 and an
adaptation of the results in [15] to the context of relative rank.

We also obtain a robust Nullstellensatz result for regular collections.

######  Theorem 2.7 (Robust Nullstellensatz for regular collections).

There exist constants $A(d,H),B(d,H),s(d)$ such that if
$\mathcal{Q}=(Q_{i,j})_{i\in[h],j\in[m_{i}]}$ is an $(A,B,s)$-regular
polynomial tower of deg $\leq d<char(\mathbb{F})$ and height $\leq H,$ and $P$
is a polynomial of degree $\leq d$ which vanishes $q^{-s}$-a.e. on
$Z(\mathcal{Q}),$ then there exist polynomials $R_{i,j}$ satisfying
$\deg(R_{i,j})+\deg(Q_{i,j})\leq\deg(P)$ and

$P=\sum_{i,j}R_{i,j}Q_{i,j}.$

In order to prove Theorem 2.2, as in [21, 12], we first reduce it to an
analogous statement for multilinear maps. However, the reduction of Theorem
2.2 to its multi-linear version is not so straightforward in our case. This
will be done by induction on the degree $d$ and will require some intermediate
results that appear during the proof of the theorem in the multi-linear case.
Therefore, we postpone it to Section 9. We now turn to the multi-linear case.

###  2.1. Multi-linear definitions and main theorem

Let $V_{1},\ldots,V_{k}$ be finite-dimensional vector spaces over the finite
field $\mathbb{F}.$ For $I\subset[k],$ we denote $V^{I}=\prod_{i\in I}V_{i}.$
For $x\in V^{[k]},$ we denote by $x_{I}$ the projection of $x$ to $V^{I}.$

In order to prove our main theorem for multi-linear functions, we will need to
work with a slightly larger class of functions which we call full multi-affine
maps. Recall that a multi-affine map $P:V^{I}\to\mathbb{F}$ has a unique
presentation $P(x_{I})=\sum_{J\subset I}P_{J}(x_{J})$ where
$P_{J}:V^{J}\to\mathbb{F}$ is multi-linear for all $J\subset I.$ By abuse of
notation, we will also denote by $P$ the function $V^{[k]}\to\mathbb{F}$ given
by $x\mapsto P(x_{I}).$

######  Definition 2.8.

$P$ is called full if $P_{I}\neq 0.$ We denote by $\tilde{P}=P_{I}$ the multi-
linear part of $P.$

In [22] a notion of rank for multi-linear functions is defined, called
partition rank.

######  Definition 2.9.

Let $P:V^{I}\to\mathbb{F}$ be a multi-linear function. The partition rank of
$P$ is the minimal length of a presentation
$P(x)=\sum_{i=1}^{r}Q_{i}(x_{I_{i}})R_{i}(x_{I\setminus I_{i}}),$ where
$\emptyset\neq I_{i}\subsetneq I$ and $Q_{i}:V^{I_{i}}\to\mathbb{F},\
R_{i}:V^{I\setminus I_{i}}\to\mathbb{F}$ are multi-linear for all $i\in[r].$
We write $r=prk(P).$ We extend this definition to full multi-affine maps via
$prk(Q)=prk(\tilde{Q}).$

The bias of $P$ on $V^{[k]}$ is defined as before, but it has some interesting
properties when $P:V^{I}\to\mathbb{F}$ is multi-linear. Writing
$P(x)=A(x_{I\setminus\\{i_{0}\\}})\cdot x_{i_{0}}$ where
$A:V^{I\setminus\\{i_{0}\\}}\to V_{i_{0}}$ is multi-linear for some
$i_{0}\in[k],$ Fourier analysis yields

$bias(P)=|{\mathbb{E}}_{x\in V^{[k]}}\chi(P(x))|=\mathbb{P}_{x\in
V^{I\setminus\\{i_{0}\\}}}\left(A(x)=0\right),$

where $\mathbb{P}_{x\in E}(T):=\frac{|T|}{|E|}$ for a subset $T\subset E.$ In
particular, the character sum above is always positive and doesn’t depend on
our choice of character $\chi.$ It’s not too difficult to show that multi-
linear maps with low partition rank exhibit significant bias, see [14, 19].

######  Claim 2.10 (Low partition rank implies bias).

If $P:V^{I}\to\mathbb{F}$ is multi-linear with $prk(P)=r$ then

${\mathbb{E}}_{x\in V^{[k]}}\chi(P(x))\geq q^{-r}.$

In [21] the following (much more difficult) inequality was proved in the other
direction:

######  Theorem 2.11 (Bias implies low partition rank).

Let $\mathbb{F}$ be a finite field and $0\leq d<char(\mathbb{F}).$ Suppose
$P:V^{I}\to\mathbb{F}$ is multi-linear with $|I|\leq d$ and $bias(P)\geq
q^{-s}.$ Then

$prk(P)\leq A(1+s)^{B},$

where $A=A(d),B=B(d)$ are constants.

This result immediately extends to full multi-affine maps because a short
calculation in [26] (which we will follow in lemma 4.2) shows that

$bias(P)\leq bias(\tilde{P}),$

and by definition they have the same partition rank. We now make the
corresponding relative definitions for full multi-affine maps.

######  Definition 2.12.

  1. (1)

Let $\mathcal{Q}=(Q_{i}:V^{I_{i}}\to\mathbb{F})_{i\in[m]}$ and
$P:V^{I}\to\mathbb{F}$ be multi-linear maps. The partition rank of $P$
relative to $\mathcal{Q}$ is

$prk_{\mathcal{Q}}(P)=\min\left\\{prk\left(P-\sum_{i\in[m],I_{i}\subset
I}Q_{i}(x_{I_{i}})R_{i}(x_{I\setminus I_{i}})\right):\ R_{i}\ \text{are multi-
linear}\right\\}.$

If $P,\mathcal{Q}$ are full multi-affine, we define
$prk_{\mathcal{Q}}(P)=prk_{\tilde{\mathcal{Q}}}(\tilde{P}).$

  2. (2)

The partition rank of a collection of multi-linear maps
$\mathcal{P}=(P_{i}:V^{I}\to\mathbb{F})_{i\in[c]}$ relative to $\mathcal{Q}$
is

$prk_{\mathcal{Q}}(\mathcal{P})=\min\left\\{prk_{\mathcal{Q}}\left(a\cdot\mathcal{P}\right):\
0\neq\textbf{a}\in\mathbb{F}^{c}\right\\}.$

If $\mathcal{P},\mathcal{Q}$ are full multi-affine with all maps in
$\mathcal{P}$ defined on a fixed index set $I,$ set
$prk_{\mathcal{Q}}(\mathcal{P})=prk_{\tilde{\mathcal{Q}}}(\tilde{\mathcal{P}}).$

  3. (3)

A tower

$\mathcal{Q}=(\mathcal{Q}_{i})_{i\in[h]}$

is composed of $h$ collections of full multi-affine functions
$\mathcal{Q}_{i}=(Q_{i,j}:V^{I_{i}}\to\mathbb{F})_{j\in[m_{i}]},$ which we
call layers. We say the tower is multi-linear if all the functions in it are
multi-linear. The degree of the tower is $\max_{i}|I_{i}|,$ and the height of
the tower is $h.$ The dimension of the tower is $m=m_{1}+\ldots+m_{h}.$ For
$i\in[h],$ we denote the truncated tower by
$\mathcal{Q}_{<i}=(\mathcal{Q}_{j})_{j\in[i-1]}.$

  4. (4)

Let $A,B,s>0.$ We say that $\mathcal{Q}$ is $(A,B,s)$-regular if for each
$i\in[h]$ we have

$prk_{\mathcal{Q}_{<i}}(\mathcal{Q}_{i})>A\left(m_{i}+m_{i+1}+\ldots+m_{h}+s\right)^{B}.$

Our main theorem for full multi-affine maps is

######  Theorem 2.13 (Relative bias implies low relative rank (d,H)).

There exist constants $A(d,H),B(d,H)$ such that if $P:V^{I}\to\mathbb{F}$ is a
full multi-affine map with $|I|\leq d$, $\mathcal{Q}$ is a tower on $V^{[k]}$
of degree $\leq d$ and height $\leq H$ such that:

  1. (1)

$bias_{Z(\mathcal{Q})}(P)\geq q^{-s}.$

  2. (2)

$\mathcal{Q}$ is $(A,B,s)$-regular.

then $rk_{\mathcal{Q}}(P)\leq A(1+s)^{B}.$

We will also prove a relative version of Claim 2.10.

######  Claim 2.14 (Low relative rank implies relative bias).

There exist constants $A(d,H),B(d,H)$ such that if $\mathcal{Q}$ is an
$(A,B,s)$-regular multi-linear tower on $V^{[k]}$ of degree $\leq d$ and
height $\leq H$ and $P:V^{I}\to\mathbb{F}$ with $|I|\leq d$ is multi-linear
with $rk_{\mathcal{Q}}(P)\leq r,$ then

  1. (1)

$Re[{\mathbb{E}}_{x\in Z(\mathcal{Q})}\chi(P(x))]\geq q^{-r}-q^{-s}.$

  2. (2)

$|Im[{\mathbb{E}}_{x\in Z(\mathcal{Q})}\chi(P(x))]|\leq q^{-s}.$

Let us now give a high-level sketch of the proof of theorem 2.13. This will
proceed by induction on $d,$ where the base case $d=1$ follows from basic
Fourier analysis. Assuming the theorem holds at degree $d,$ we present some
useful consequences in section 3 and make some reductions in section 4. After
these reductions, the task at hand is to prove the theorem for multi-linear
$P:V^{[d+1]}\to\mathbb{F}$ and a multi-linear tower $\mathcal{Q}$ on
$V^{[d+1]}$ of degree $\leq d.$ In section 5, we show that there are many
”derived” towers $\mathcal{Q}_{t}$ and multi-linear functions
$\phi_{t}:V^{[d]}\to\mathbb{F}^{100s}$ such that $P$ vanishes $q^{-s}$-a.e. on
the variety $Z(\mathcal{Q}_{t})\cap\\{\phi_{t}(x_{[d]})=0\\}.$ This is similar
in spirit to previous work on this subject, but the derived towers appearing
here present a new challenge. In section 6 we pause to describe the relative
regularization process which is the multi-linear analogue of theorem 2.3. In
section 7, the regularization process is applied to the collections
$\mathcal{Q}_{t},\phi_{t}$ to obtain regular varieties on which $P$ vanishes
$q^{-s}$-a.e. In that section we also show that this means that $P$ vanishes
identically on them, similarly to proposition 5.1 in [10]. A key novel step in
our proof consists in then showing that these varieties can be ”summed” to
obtain a single tower $\mathcal{R}$ of dimension $\leq A(1+s)^{B}$ such that
$P\restriction_{Z(\mathcal{Q}\cup\mathcal{R})}\equiv 0$ and
$\mathcal{Q}\cup\mathcal{R}$ is regular. In section 8, we prove a
nullstellensatz which allows us to conclude that
$rk_{\mathcal{Q}\cup\mathcal{R}}(P)=0,$ so
$rk_{\mathcal{Q}}(P)\leq\dim(\mathcal{R})\leq A(1+s)^{B},$ which completes the
inductive step.

##  3\. Some equidistribution lemmas

As mentioned before, the proof of Theorem 2.13 will proceed by induction on
$d$ and the base case $d=1$ follows from Fourier analysis. For the purposes of
the inductive argument it will be useful to formulate a version of Theorem
2.13 with an auxiliary parameter, which we now do.

######  Theorem 3.1 (Relative bias implies low relative rank (d,H,l)).

There exist constants $A(d,H,l),B(d,H,l)$ such that if $P:V^{I}\to\mathbb{F}$
is a full multi-affine map with $|I|\leq d$, $\mathcal{Q}$ is a tower on
$V^{[k]}$ of degree $\leq d$ height $\leq H$ such that:

  1. (1)

$bias_{Z(\mathcal{Q})}(P)\geq q^{-s}.$

  2. (2)

$\mathcal{Q}$ is $(A,B,s)$-regular.

  3. (3)

$\mathcal{Q}_{\leq H-l}$ is of degree $<d.$

then $rk_{\mathcal{Q}}(P)\leq A(1+s)^{B}.$

Theorem 2.13 corresponds of course to the case $l=H.$ We call $\mathcal{Q}$ as
above a tower of type (d,H,l) for short. In this section we assume Theorem
3.1(d,H,l) holds and explore some of its useful consequences. We warm up with
the following simple but important result.

######  Lemma 3.2 (Regular varieties are of the expected size (d,H+1,l+1)).

There exist constants $A(d,H,l),B(d,H,l)$ such that for any $s>0$ and for any
$(A,B,s)$-regular tower $\mathcal{Q}$ on $V^{[k]}$ of type (d,H+1,l+1) and
dimension $m,$ we have

$\left|q^{m}\frac{|Z(\mathcal{Q})|}{|V^{[k]}|}-1\right|\leq q^{-s}.$

###### Proof.

Let $A^{\prime},B^{\prime}$ be the constants from Theorem 3.1(d,H,l). If $A,B$
are sufficiently large depending on $A^{\prime},B^{\prime}$ then $\mathcal{Q}$
is $(A^{\prime},B^{\prime},s+H+2)$ regular. So for any $i\in[H+1]$ the tower
$\mathcal{Q}_{<i}$ is $(A^{\prime},B^{\prime},s+H+m_{i})$-regular of type
(d,H,l) and

$rk_{\mathcal{Q}_{<i}}(\mathcal{Q}_{i})>A^{\prime}(s+H+m_{i}+2)^{B^{\prime}}.$

By Theorem 3.1 it follows that for any $0\neq a\in\mathbb{F}^{m_{i}}$ we have

$bias_{Z(\mathcal{Q}_{<i})}(a\cdot\mathcal{Q}_{i})<q^{-(s+H+m_{i}+1)}.$

Fourier analysis yields

$q^{m_{i}}\frac{|Z(\mathcal{Q}_{\leq
i})|}{|Z(\mathcal{Q}_{<i})|}=\sum_{a\in\mathbb{F}^{m_{i}}}{\mathbb{E}}_{x\in
Z(\mathcal{Q}_{<i})}\chi(a\cdot\mathcal{Q}_{i}(x))=1+e_{i},$

where $|e_{i}|\leq q^{-(s+H+1)}.$ Then we multiply to get

$\frac{|Z(\mathcal{Q})|}{|V^{[k]}|}=\prod_{i\in[H+1]}\frac{|Z(\mathcal{Q}_{\leq
i})|}{|Z(\mathcal{Q}_{<i})|}=\prod_{i\in[H+1]}(1+e_{i})q^{-m_{i}}=(1+e)q^{-m},$

where $|e|\leq q^{-s}.$ ∎

We now introduce some notation. For a tower $\mathcal{Q}$ on $V^{[k]}$ and a
subset $I\subset[k],$ we write
$\mathcal{Q}_{I}=(\mathcal{Q}_{i})_{i\in[h],I_{i}\subset I}$ for the
restriction to a tower on $V^{I}.$ Similarly, we define
$Z(\mathcal{Q})_{I}=Z(\mathcal{Q}_{I})\subset V^{I}.$ For $y\in V^{I}$ and a
full multi-affine function $Q:V^{J}\to\mathbb{F},$ the full multi-affine
function $Q(y):V^{J\setminus I}\to\mathbb{F}$ is defined by
$Q(y)(z)=Q(y_{I\cap J},z).$ set
$\mathcal{Q}(y)=(\mathcal{Q}_{i}(y))_{i\in[h]}$ for the tower induced on
$V^{[k]\setminus I},$ where $\mathcal{Q}_{i}(y)=(Q_{i,j}(y):V^{I_{i}\setminus
I}\to\mathbb{F})_{j\in[m_{i}]}.$ For the zero locus we write
$Z(\mathcal{Q})(y)=Z(\mathcal{Q}(y)).$

We now state several interrelated lemmas.

######  Lemma 3.3 (Derivatives(d,H+1,l+1)).

For any $C,D$ there exist constants $A(C,D,d,H,l),$ $B(C,D,d,H,l)$ such that
if $\mathcal{Q}$ is an $(A,B,s)$-regular tower on $V^{[k]}$ of type
(d,H+1,l+1) and $I\subset[k],$ then for $q^{-s}$-a.e. $y\in
Z(\mathcal{Q})_{I}$ the tower $\mathcal{Q}(y)$ on $V^{[k]\setminus I}$ is
$(C,D,s)$-regular.

######  Lemma 3.4 (Fubini(d,H+1,l+1)).

There exist constants $A(d,H,l),B(d,H,l)$ such that if $\mathcal{Q}$ is an
$(A,B,s)$-regular tower on $V^{[k]}$ of type (d,H+1,l+1), $I\subset[k],$ and
$g:V^{[k]}\to{\mathbb{C}}$ satisfies $|g(x)|\leq 1$ for all $x\in V^{[k]}$,
then

$\left|{\mathbb{E}}_{x\in Z(\mathcal{Q})}g(x)-{\mathbb{E}}_{y\in
Z(\mathcal{Q})_{I}}{\mathbb{E}}_{z\in Z(\mathcal{Q})(y)}g(y,z)\right|\leq
q^{-s}.$

######  Lemma 3.5 (Rank-bias(d,H+1,l+1)).

There exist constants $A(d,H,l),B(d,H,l)$ such that if $\mathcal{Q}$ is an
$(A,B,s)$-regular multi-linear tower on $V^{[k]}$ of type (d,H+1,l+1) and
$P:V^{I}\to\mathbb{F}$ is a multi-linear map with $|I|\leq d+1$ then

  1. (1)

$|Im[{\mathbb{E}}_{x\in Z(\mathcal{Q})}\chi(P(x))]|\leq q^{-s}.$

  2. (2)

If $rk_{\mathcal{Q}}(P)=r,$ then

$Re[{\mathbb{E}}_{x\in Z(\mathcal{Q})}\chi(P(x))]\geq q^{-r}-q^{-s}.$

The above lemmas will be proved together by induction on the height $h$ of the
tower $\mathcal{Q}.$ The implications are as follows

$\text{Rank-bias(h-1) + Fubini(h-1)}\implies\text{Derivatives(h)}$
$\text{Derivatives(h)}\implies\text{Fubini(h)}$ $\text{Derivatives(h) +
Fubini(h)}\implies\text{Rank-bias(h)}$

In the base case $h=0,$ Lemmas 3.3 and 3.4 are trivial and Lemma 3.5 is proved
in [14, 19].

###### Proof of Lemma 3.3 (derivatives(h)).

We are interested in the regularity of $\mathcal{Q}(y),$ which is by
definition the regularity of its associated multi-linear tower. Which
multilinear maps appear? For $Q_{i,j}\in\mathcal{Q}_{i},$ write
$Q_{i,j}=\sum_{J\subset I_{i}}Q_{i,j}^{J}$ as a sum of multi-linear maps
$Q_{i,j}^{J}:V^{J}\to\mathbb{F},$ and set
$Q^{\prime}_{i,j}=\sum_{I_{i}\setminus I\subset J\subset I_{i}}Q_{i,j}^{J},$
$\mathcal{Q}^{\prime}_{i}=\\{Q^{\prime}_{i,j}\\}_{j\in m_{i}}.$ Note that the
following properties hold:

  1. (1)

$\mathcal{Q},\mathcal{Q}^{\prime}$ have the same associated multi-linear
variety (and hence the same regularity).

  2. (2)

$Z(\mathcal{Q}^{\prime})_{I}=Z(\mathcal{Q})_{I}$

  3. (3)

For any $y\in Z(\mathcal{Q})_{I},$ the multi-linear tower associated with
$\mathcal{Q}(y)$ is $\mathcal{Q}^{\prime}(y).$

So after replacing $\mathcal{Q}$ with $\mathcal{Q}^{\prime}$, we can assume
without loss of generality that $\mathcal{Q}(y)$ is a multi-linear tower for
any $y\in Z(\mathcal{Q}_{I}).$ Write $X=Z(\mathcal{Q})$ for short. Let
$A^{\prime},B^{\prime}$ be the constants of Lemma 3.3 at height $h-1.$ We deal
separately with two cases.

The first case (and the easier one) is when $I_{h}\subset I.$ In this case for
any $y\in(X_{I})_{<h}$ we have $\mathcal{Q}(y)=\mathcal{Q}_{<h}(y).$ For
$A=2^{B^{\prime}}A^{\prime},$ $B=B^{\prime},$ we get that $\mathcal{Q}_{<h}$
is $(A^{\prime},B^{\prime},s+m_{h}+1)$-regular. Then by the inductive
hypothesis we have that for $q^{-(s+m_{h}+1)}$ a.e. $y\in(X_{I})_{<h}$ the
tower $\mathcal{Q}(y)=\mathcal{Q}_{<h}(y)$ is $(C,D,s)$-regular. By Lemma 3.2
we know that if $A,B$ are sufficiently large then
$\frac{|(X_{I})_{<h}|}{|X_{I}|}\leq q^{m_{h}+1}.$ Therefore $\mathcal{Q}(y)$
is regular for $q^{-s}$-a.e. $y\in X_{I},$ as desired.

The second case is when $I_{h}\not\subset I.$ In this case we have
$X_{I}=(X_{I})_{<h}.$ If $A,B$ are sufficiently large then $\mathcal{Q}$ is
$(A^{\prime},B^{\prime},100C(m_{h}+s)^{D})$-regular. Let

$s^{\prime}=100C(m_{h}+s)^{D}\ ,\ \varepsilon=q^{-s^{\prime}}.$

For the rest of this proof, we will assume wherever needed that
$A,B,A^{\prime},B^{\prime},C,D$ are sufficiently large with respect to
$d,h,l.$ By the inductive hpothesis we have that for $\varepsilon$-a.e. $y\in
X_{I}$ the tower $\mathcal{Q}_{<h}(y)$ is $(C,D,s^{\prime})$-regular. By a
union bound, it’s enough to show that for $q^{-(s+1)}$-a.e. $y\in X_{I}$ we
have

$rk_{\mathcal{Q}_{<h}(y)}\left(\mathcal{Q}_{h}(y)\right)>C(m_{h}+s)^{D}.$

Fix $0\neq a\in\mathbb{F}^{m_{h}}.$ Applying Theorem 3.1, we have

$Re\left[{\mathbb{E}}_{x\in
X_{<h}}\chi(a\cdot\mathcal{Q}_{h}(x))\right]\leq\varepsilon.$

Lemma 3.4 at height $h-1$ yields ${\mathbb{E}}_{y\in
X_{I}}Re\left[{\mathbb{E}}_{z\in X_{<h}(y)}\chi(Q(y,z))\right]\leq
2\varepsilon.$ For $\varepsilon$-a.e. $y\in X_{I}$ we can apply Lemma 3.5 at
height $h-1$ to get

$\left|{\mathbb{E}}_{z\in X_{<h}(y)}\chi(Q(y,z))\right|\leq
Re\left[{\mathbb{E}}_{z\in X_{<h}(y)}\chi(Q(y,z))\right]+\varepsilon.$

Therefore,

${\mathbb{E}}_{y\in X_{I}}|{\mathbb{E}}_{z\in
X_{<h}(y)}\chi(Q(y,z))|<4\varepsilon.$

By Markov’s inequality, this means that for $2\sqrt{\varepsilon}$-a.e. $y\in
X_{I},$ we have

$|{\mathbb{E}}_{z\in X_{<h}(y)}\chi(Q(y,z))|<2\sqrt{\varepsilon}.$

Then for $3\sqrt{\varepsilon}$-a.e. $y\in X_{I}$ both the above inequality
holds and the tower $\mathcal{Q}^{<h}(y)$ is $(C,D,s^{\prime})$-regular. Let
$r_{a}(y)=rk_{\mathcal{Q}^{<h}(y)}(a\cdot\mathcal{Q}_{h}(y)).$ Applying Lemma
3.5 at height $h-1$ we find that for these $y$ we have

$q^{-r(y)}<4\sqrt{\varepsilon}<q^{-C(m_{h}+s)^{D}},$

which implies $r_{a}(y)>C(m_{h}+s)^{D}.$ Running over all $0\neq
a\in\mathbb{F}^{m_{h}},$ we get that for $3\sqrt{\varepsilon}q^{m_{h}}\leq
q^{-(s+1)}$-a.e. $y\in X_{I}$ we have $r(y)>C(m_{h}+s)^{D}$ where
$r(y)=\max_{0\neq a\in\mathbb{F}^{m_{h}}}r_{a}(y).$ This completes the proof.
∎

###### Proof of Lemma 3.4 fubini(h).

By the triangle inequality,

$\left|{\mathbb{E}}_{x\in X}g(x)-{\mathbb{E}}_{y\in X_{I}}{\mathbb{E}}_{z\in
X(y)}g(y,z)\right|\leq{\mathbb{E}}_{y\in
X_{I}}\left|\frac{|X_{I}|\cdot|X(y)|}{|X|}-1\right|.$

Denoting $f(y)=\frac{|X_{I}|\cdot|X(y)|}{|X|},\ \varepsilon=q^{-(s+2)},$ and
assuming $A,B$ are sufficiently large, we note the following:

  1. (1)

$f(y)\geq 0$ for all $y\in X_{I}.$

  2. (2)

${\mathbb{E}}_{y\in X_{I}}f(y)=1.$

  3. (3)

By Lemmas 3.3 and 3.2 applied at height $h$, for $\varepsilon$-a.e. $y\in
X_{I},$ we have $1-\varepsilon<f(y)<1+\varepsilon.$

Let $E\subset X_{I}$ be the set of $y$ for which this last inequality holds,
and let $\rho=\frac{|E|}{|X_{I}|}$ (so $1-\varepsilon\leq\rho\leq 1$). Then

(1) ${\mathbb{E}}_{y\in X_{I}}|f(y)-1|=\rho\cdot{\mathbb{E}}_{y\in
E}|f(y)-1|+(1-\rho){\mathbb{E}}_{y\in E^{c}}|f(y)-1|.$

The first term is $\leq\varepsilon$ by the definition of $E.$ For the second
term we have

$(1-\rho){\mathbb{E}}_{y\in
E^{c}}|f(y)-1|\leq\varepsilon+(1-\rho){\mathbb{E}}_{y\in E^{c}}f(y).$

By the three properties listed above, we get that $(1-\rho){\mathbb{E}}_{y\in
E^{c}}f(y)\leq 2\varepsilon.$ Plugging this into inequality 1 yields

${\mathbb{E}}_{y\in X_{I}}|f(y)-1|\leq 4\varepsilon\leq q^{-s}.$

∎

###### Proof of Lemma 3.5 rank-bias(h).

Let $X=Z(\mathcal{Q}).$ First we apply Lemma 3.4 to get

  1. (1)

$Re[{\mathbb{E}}_{x\in X}\chi(P(x))]\geq Re[{\mathbb{E}}_{x\in
X_{I}}\chi(P(x))]-q^{-2s}.$

  2. (2)

$|Im[{\mathbb{E}}_{x\in X}\chi(P(x))]|\leq|Im[{\mathbb{E}}_{x\in
X_{I}}\chi(P(x))]|+q^{-2s}.$

so we can assume without loss of generality that $I=[k].$ We will prove the
lemma by induction on $|I|.$ For $|I|=1$ the lemma follows from basic Fourier
analysis. For the general case, we start by showing the second inequality
holds. Apply Lemma 3.4 again to get

$|Im[{\mathbb{E}}_{x\in X}\chi(P(x))]|\leq{\mathbb{E}}_{y\in
X_{1}}|Im[{\mathbb{E}}_{z\in X(y)}\chi(P(y,z))]|+q^{-10s}.$

Let $A^{\prime},B^{\prime}$ be the constants for Lemma 3.5 on an index set of
size $|I|-1.$ By Lemma 3.3, if $A,B$ are sufficiently large then for
$q^{-10s}$-a.e. $y\in X_{1}$ the multi-linear tower $\mathcal{Q}(y)$ is
$(A^{\prime},B^{\prime},10s)$-regular. The induction hypothesis implies that

${\mathbb{E}}_{y\in X_{1}}|Im[{\mathbb{E}}_{z\in X(y)}\chi(P(y,z))]|\leq
q^{-5s},$

as desired.

Now for the first inequality, suppose modulo the maps in $\mathcal{Q}$ we have
the low partition rank presentation

$P(x_{[k]})=\sum_{i=1}^{m}l_{i}(x_{1})g_{i}(x_{[2,k]})+\sum_{j=m+1}^{r}q_{i}(x_{I_{j}})r_{i}(x_{[k]\setminus
I_{j}}),$

where $I_{j}\neq\\{1\\},[2,k].$ Let $W=\\{y\in X_{1}:l_{i}(y)=0\ \forall
i\in[m]\\}.$ By Lemma 3.4,

$Re[{\mathbb{E}}_{x\in X}\chi(P(x))]\geq{\mathbb{E}}_{y\in
X_{1}}Re[{\mathbb{E}}_{z\in X(y)}\chi(P(y,z))]-q^{-10s}\\\
=\frac{|W|}{|X_{1}|}{\mathbb{E}}_{y\in W}Re[{\mathbb{E}}_{z\in
X(y)}\chi(P(y,z))]+(1-\frac{|W|}{|X_{1}|}){\mathbb{E}}_{y\in X_{1}\setminus
W}Re[{\mathbb{E}}_{z\in X(y)}\chi(P(y,z))]-q^{-10s}.$

Note that

  1. (1)

For any $y\in W$ the rank of $P(y,\cdot)$ on $X(y)$ is $\leq r-m.$

  2. (2)

$|W|/|X_{1}|\geq q^{-m}$

  3. (3)

For $q^{-10s}$-a.e. $y\in X_{1}$ the multi-linear tower $\mathcal{Q}(y)$ is
$(A^{\prime},B^{\prime},10s)$-regular.

By these properties and the induction hypothesis for $P(y,\cdot)$ on $X(y)$ we
can lower bound the first summand by

$\frac{|W|}{|X_{1}|}{\mathbb{E}}_{y\in W}Re[{\mathbb{E}}_{z\in
X(y)}\chi(P(y,z))]\geq q^{-r}-q^{-5s},$

and the second summand by

$(1-\frac{|W|}{|X_{1}|}){\mathbb{E}}_{y\in X_{1}\setminus
W}Re[{\mathbb{E}}_{z\in X(y)}\chi(P(y,z))]\geq-q^{-5s}.$

∎

##  4\. Some reductions

In this section we reduce the proof of Theorem 2.13 for degree $d+1$ to the
$l=0$ case of Theorem 3.1.

######  Lemma 4.1.

Suppose Theorem 3.1(d+1,H,l) holds for $l=0$ and all $H$. Then it holds for
all $l,H.$

###### Proof.

By induction on $l.$ Suppose the theorem holds for (d+1,H,l). Let
$\mathcal{Q}$ be an $(A,B,s)$-regular tower on $V^{[k]}$ of type (d+1,H,l+1)
and $P:V^{I}\to\mathbb{F}$ a full multi-affine map of degree $\leq d+1,$ with
$bias_{Z(\mathcal{Q})}(P)\geq q^{-s}.$ Again, we denote $X=Z(\mathcal{Q})$ for
short. We saw in the last section that Theorem 3.1(d+1,H,l) implies Lemma 3.4
for (d+1,H+1,l+1), so

$|{\mathbb{E}}_{x\in X_{I}}\chi(P(x))|\geq q^{-2s},$

i.e. we can assume without loss of generality that $I=[k].$ If $\mathcal{Q}$
is of degree $\leq d$ then we are done. Suppose not, then $k=d+1$ and there is
some layer $t\in[H]$ with $\mathcal{Q}_{t}$ of degree $d+1$. Let
$\mathcal{Q}_{\neq t}=(\mathcal{Q}_{i})_{i\in[H]\setminus\\{t\\}}$ and
$X_{\neq t}=Z(\mathcal{Q}_{\neq t}).$ By Fourier analysis, we have

(2) $|{\mathbb{E}}_{x\in X}\chi(P(x))|\leq\frac{|X_{\neq
t}|}{|X|}q^{-m_{t}}\sum_{a\in\mathbb{F}^{m_{t}}}|{\mathbb{E}}_{x\in X_{\neq
t}}\chi(P(x)+a\cdot\mathcal{Q}_{t}(x))|.$

By Lemma 3.2(d+1,H,l+1) (which follows from Theorem 3.1(d+1,H,l)),
$\frac{|X_{\neq t}|}{|X|}q^{-m_{t}}\leq q.$ As for the second term, choose
$b\in\mathbb{F}^{m_{t}}$ such that $prk_{\mathcal{Q}_{\neq
t}}(P(x)+b\cdot\mathcal{Q}_{t}(x))$ is minimal. By sub-additivity of relative
partition rank, for any
$b\neq a\in\mathbb{F}^{m_{t}}$ we must have

$prk_{\mathcal{Q}_{\neq
t}}(P(x)+a\cdot\mathcal{Q}_{t}(x))\geq\frac{A}{2}(m_{t}+s)^{B}.$

By Theorem 3.1(d+1,H,l) (assuming $A,B$ are sufficiently large) this means
that for any $b\neq a\in\mathbb{F}^{m_{t}},$

$|{\mathbb{E}}_{x\in X_{\neq t}}\chi(P(x)+a\cdot\mathcal{Q}_{t}(x))|\leq
q^{-m_{t}-4s}.$

Plugging these estimates into inequality 2 yields

$q^{-2s-1}\leq|{\mathbb{E}}_{x\in X_{\neq
t}}\chi(P(x)+b\cdot\mathcal{Q}_{t}(x))|.$

Now apply Theorem 3.1(d+1,h,l) to conclude that

$prk_{\mathcal{Q}}(P(x))\leq prk_{\mathcal{Q}_{\neq
t}}(P(x)+b\cdot\mathcal{Q}_{t}(x))\leq A(1+s)^{B}.$

∎

Therefore all we have to do is prove Theorem 3.1(d+1,H,0) in order to deduce
Theorem 2.13 at degree $d+1.$ The following lemma allows us to reduce further
to the case that $P,\mathcal{Q}$ are multi-linear and defined on the same
index set. From now on we assume Theorem 2.13(d,H) holds for all $H,$ and work
towards proving Theorem 3.1(d+1,H,0) for all $H.$ We may safely forget about
the auxillary parameter $l$ of Theorem 3.1, it has served its purpose. The
following lemma allows us to reduce further to the case where $P,\mathcal{Q}$
are multi-linear and are defined on the same index set.

######  Lemma 4.2.

There exist $A(d,h),B(d,h)$ such that if $\mathcal{Q}$ is an $(A,B,s)$-regular
tower of degree $\leq d$ and height $\leq h$ on $V^{[k]}$ and
$P:V^{I}\to\mathbb{F}$ is a full multi-affine map of degree $|I|\leq d+1$ then

$|{\mathbb{E}}_{x\in X}\chi(P(x))|\leq
Re[{\mathbb{E}}_{x\in\tilde{X}_{I}}\chi(\tilde{P}(x))]+q^{-s},$

where $X=Z(\mathcal{Q})$ and $\tilde{P},\tilde{X}$ are the corresponding
multi-linear map and variety.

###### Proof.

By applying Lemma 3.4, we get

$|{\mathbb{E}}_{x\in X}\chi(P(x))|\leq|{\mathbb{E}}_{x\in
X_{I}}\chi(P(x))|+q^{-2s},$

so we can assume without loss of generality that $I=[k].$ Now choose some
$i\in[k]$ and write $P(x)=A(x_{[k]\setminus\\{i\\}})\cdot
x_{i}+b(x_{I\setminus\\{i\\}}),$ where $A,b$ are multi-affine maps. Again
using Lemma 3.4 twice, we have

$|{\mathbb{E}}_{x\in X}\chi(P(x))|\leq|{\mathbb{E}}_{x\in
X_{I\setminus\\{i\\}}}\chi(b(x)){\mathbb{E}}_{y\in X(x)}\chi(A(x)\cdot
y)|+q^{-10ks}\\\ \leq{\mathbb{E}}_{x\in
X_{I\setminus\\{i\\}}}|{\mathbb{E}}_{y\in X(x)}\chi(A(x)\cdot y)|+q^{-10ks}\\\
={\mathbb{E}}_{x\in
X_{I\setminus\\{i\\}}}{\mathbb{E}}_{y\in\widetilde{X(x)}}\chi(A(x)\cdot
y)+q^{-10ks}\\\ \leq|{\mathbb{E}}_{x\in
X^{\prime}}\chi(A(x_{[k]\setminus\\{i\\}})\cdot x_{i})|+q^{-5ks},$

where $X^{\prime}$ is the variety associated with $X$ which is linear in the
$i$-th coordinate and $A(x_{[k]\setminus\\{i\\}})\cdot x_{i}$ is the multi-
affine map associated with $P$ which is linear in the $i$-th coordinate.
Iterating this inequality over and over for all the other coordinates, we end
up with

$|{\mathbb{E}}_{x\in
X}\chi(P(x))|\leq|{\mathbb{E}}_{x\in\tilde{X}}\chi(\tilde{P}(x))|+(k+1)q^{-5ks}\leq
Re[{\mathbb{E}}_{x\in\tilde{X}}\chi(\tilde{f}(x))]+q^{-s},$

where the second inequality follows from lemma 3.5. ∎

##  5\. Many low rank approximations

In the previous section we showed that in order to prove Theorem 2.13 for
degree $d+1,$ the only new case we have to deal with is when
$P:V^{[d+1]}\to\mathbb{F}$ is multi-linear and $\mathcal{Q}$ is a multi-linear
tower on $V^{[d+1]}$ of degree $\leq d.$ In this section we will prove the
existence of an abundance of relative low rank approximations, and in the next
sections we will ”glue” them together to get a genuine relative low rank
presentation. We start with a useful algebraic claim which we will need here
and in later sections.

######  Claim 5.1.

Let $\mathcal{Q}$ be a tower on $V^{[k]}$ and $\textbf{l}\in\mathbb{N}^{k}$ a
vector. Define $\mathcal{Q}^{\otimes\textbf{l}}$ to be the tower on
$(V_{1})^{l_{1}}\times\ldots\times(V_{k})^{l_{k}}$ obtained by multiplying the
first coordinate $l_{1}$ times, the second $l_{2}$ times and so on - i.e. a
tower of the same height as $\mathcal{Q}$ with

$\left(\mathcal{Q}^{\otimes\textbf{l}}\right)_{i}=\bigcup_{\textbf{j}\in\prod_{t\in
I_{i}}[l_{t}]}\mathcal{Q}_{i}((x_{t,j_{t}})_{t\in I_{i}}).$

Define $\mathcal{Q}^{\times\textbf{l}}$ to be the tower composed of the same
equations, but on $V^{[kl_{1}\ldots l_{k}]},$ so it has $l_{1}\ldots l_{k}$ as
many layers as $\mathcal{Q}$ (We order the layers corresponding to
$\mathcal{Q}_{i}$ arbitrarily within themselves, but keep the order
otherwise). Then if $\mathcal{Q}$ is $(A(l_{1}\ldots l_{k})^{B},B,s)$-regular
then both $\mathcal{Q}^{\otimes\textbf{l}}$ and
$\mathcal{Q}^{\times\textbf{l}}$ are $(A,B,s)$-regular.

###### Proof.

We may assume without loss of generality that $\mathcal{Q}$ is multi-linear.
Because there are $l_{1}\ldots l_{k}$ times as many maps, it’s enough to show
that the relative ranks are unchanged. Suppose we have a linear combination
with

$rk_{\mathcal{Q}^{\otimes\textbf{l}}_{<i}}\left(\sum_{\textbf{j}\in\prod_{t\in
I_{i}}[l_{t}]}a_{\textbf{j}}\cdot\mathcal{Q}_{i}((x_{t,j_{t}})_{t\in
I_{i}})\right)<rk_{\mathcal{Q}_{<i}}(\mathcal{Q}_{i}).$

For any $\textbf{j}\in\prod_{t\in I_{i}}[l_{t}],$ plugging in
$x_{\alpha,\beta}=0$ for all $\beta\neq j_{\alpha},$ we get

$rk_{\mathcal{Q}_{<i}}(a_{\textbf{j}}\cdot\mathcal{Q}_{i})<rk_{\mathcal{Q}_{<i}}(\mathcal{Q}_{i}),$

which implies that $a_{\textbf{j}}=0.$ The proof for
$\mathcal{Q}^{\times\textbf{l}}$ is identical. ∎

Now we are ready to prove that we can find an abundance of low rank
approximations of $P$ on $Z(\mathcal{Q}).$ The following is inspired by lemma
12 in [21].

######  Proposition 5.2 (Low rank approximations).

There exist constants $A(d,H),B(d,H)$ such that the following holds: If
$\mathcal{Q}$ is an $(A,B,s)$-regular multi-linear tower on $V^{[d+1]}$ of
degree $\leq d$ and height $\leq H,$ $X=Z(\mathcal{Q}),$ and
$P:V^{[d+1]}\to\mathbb{F}$ is a multi-linear map satisfying $bias_{X}(P)\geq
q^{-s},$ then there exists a set $E\subset(X_{d+1})^{100s}$ of density $\geq
q^{-10s}$ such that for all $t\in E$ there’s a multi-linear function
$\phi_{t}:V^{[d]}\to\mathbb{F}^{100s}$ with

$\mathbb{P}_{x\in X_{t}\cap\\{\phi_{t}(x_{[d]})=0\\}}(P(x)=0)\geq 1-q^{-s},$

where $X_{t}=\\{x\in X:x_{[d]}\in\bigcap_{i=1}^{100s}X(t_{i})\\}.$

###### Proof.

Write $P(x)=A(x_{[d]})\cdot x_{d+1}.$ Apply lemma 3.4 to get that

(3) $q^{-2s}\leq{\mathbb{E}}_{x_{[d]}\in X_{[d]}}{\mathbb{E}}_{x_{d+1}\in
X(x)}A(x_{[d]})\cdot x_{d+1}=\mathbb{P}_{x_{[d]}\in
X_{[d]}}\left[A(x_{[d]})\perp X(x_{[d]})\right].$

Now, fix $x_{[d]}\in X_{[d]}.$ To test for the event above, choose
$t\in(X(x_{[d]}))^{l}$ at random where $l=100s$ and define

$\phi_{t}(x_{[d]})=(A(x_{[d]})\cdot t_{1},\ldots,A(x_{[d]})\cdot t_{l}).$

If $A(x_{[d]})\perp X(x_{[d]}),$ then $\phi_{t}(x)=0$ for any
$t\in(X(x_{[d]}))^{l}$ and if $A(x_{[d]})\not\perp X(x_{[d]})$ then

$\mathbb{P}_{t\in X(x_{[d]})^{l}}(\phi_{t}(x)=0)=q^{-l}.$

Therefore,

${\mathbb{E}}_{x_{[d]}\in X_{[d]}}1_{A(x_{[d]})\not\perp
X(x_{[d]})}{\mathbb{E}}_{t\in(X(x_{[d]}))^{l}}1_{\phi_{t}(x)=0}\leq q^{-l}.$

If $A,B$ are sufficiently large, then by claim 5.1 and lemma 3.4 we have

${\mathbb{E}}_{t\in(X_{d+1})^{l}}{\mathbb{E}}_{x\in
X_{t}}1_{A(x_{[d]})\not\perp X(x_{[d]})}1_{\phi_{t}(x)=0}\leq
q^{-l}+q^{-100s}\leq q^{-50s}.$

By Markov’s inequality, for $q^{-25s}$-a.e. $t\in X_{d+1}^{l},$ we have

(4) ${\mathbb{E}}_{x\in X_{t}}1_{A(x_{[d]})\not\perp
X(x_{[d]})}1_{\phi_{t}(x)=0}\leq q^{-25s}.$

Also, by Lemma 3.4 together with inequality 3

${\mathbb{E}}_{t\in X_{d+1}^{l}}{\mathbb{E}}_{x\in X_{t}}1_{A(x_{[d]})\perp
X(x_{[d]})}\geq q^{-3s}.$

Markov’s inequality gives us

$\mathbb{P}_{t\in X_{d+1}^{l}}\left[{\mathbb{E}}_{x\in
X_{t}}1_{A(x_{[d]})\perp X(x_{[d]})}\geq q^{-5s}\right]\geq q^{-5s}.$

So for a collection of $t\in X_{d+1}^{l}$ of density $\geq q^{-10s}$ we have
both

${\mathbb{E}}_{x\in X_{t}}1_{A(x_{[d]})\perp X(x_{[d]})}\geq q^{-5s}$

and inequality 4. For these $t,$ we have

$\mathbb{P}_{x\in
X_{t}\cap\\{\phi_{t}(x_{[d]})=0\\}}(P(x)=0)\geq\mathbb{P}_{x\in
X_{t}}(A(x_{[d]})\perp X(x_{[d]})|\phi_{t}(x)=0)\\\ =\frac{\mathbb{P}_{x\in
X_{t}}(A(x_{[d]})\perp X(x_{[d]}))}{\mathbb{P}_{x\in X_{t}}(A(x_{[d]})\perp
X(x_{[d]}))+\mathbb{P}_{x\in X_{t}}(A(x_{[d]})\not\perp
X(x_{[d]}),\phi_{t}(x)=0)}\\\ \geq\frac{q^{-5s}}{q^{-5s}+\mathbb{P}_{x\in
X_{t}}(A(x_{[d]})\not\perp
X(x_{[d]}),\phi_{t}(x)=0)}\geq\frac{q^{-5s}}{q^{-5s}+q^{-25s}}\geq 1-q^{-s}.$

∎

##  6\. Regularization

In order to improve our approximation from the last section to a genuine low
rank representation, we will have to take the $100s$ maps
$\phi_{t}:V^{[d]}\to\mathbb{F}^{100s}$ and replace them by a tower which is
relatively regular together with the maps of $X_{t}.$ In this section we
describe an efficient algorithm for doing this. The following notion will come
in handy:

######  Definition 6.1.

Let
$\mathcal{R}=(\mathcal{R}_{i})_{i\in[h]},\mathcal{Q}=(\mathcal{Q}_{j})_{j\in[h]}$
be towers on $V^{[k]}$ and $m_{i}=|\mathcal{R}_{i}|.$ We say that
$\mathcal{R}$ is $(A,B,s)$-regular relative to $\mathcal{Q}$ if for all
$i\in[h]$ we have

$rk_{\mathcal{Q}\cup\mathcal{R}_{<i}}(\mathcal{R}_{i})>A(m_{i}+m_{i+1}+\ldots+m_{h}+s)^{B}.$

Note that if $\mathcal{Q},\mathcal{R}$ are two towers such that $\mathcal{R}$
is $(A,B,s)$-regular relative to $\mathcal{Q}$ and $\mathcal{Q}$ is
$(A,B,s+m)$-regular ($m$ is the dimension of $\mathcal{R}$), then
$\mathcal{Q}\cup\mathcal{R}$ is $(A,B,s)$-regular with the layers ordered by
having $\mathcal{Q}$ on the bottom and $\mathcal{R}$ on top.

######  Claim 6.2 (Regular decomposition).

For any $A,B$ there exist constants $C(A,B,d,k),D(A,B,d,k)$ such that the
following holds: If $\mathcal{Q}$ is a tower on $V^{[k]}$ and $\mathcal{R}$ is
a collection of full multi-affine maps of degree $\leq d$ then there exist
towers $\mathcal{S}_{1},\ldots,\mathcal{S}_{l}$ such that:

  1. (1)

$\mathcal{S}_{i}$ is $(A,B,s)$-regular relative to $\mathcal{Q}$.

  2. (2)

$\mathcal{S}_{i}$ is of degree $\leq d$ and height $\leq 2^{k}.$

  3. (3)

$\dim(\mathcal{S}_{i})\leq C(s+\dim(\mathcal{R}))^{D}.$

  4. (4)

We have a decomposition
$Z(\mathcal{Q}\cup\mathcal{R})=\bigsqcup_{i=1}^{l}Z(\mathcal{Q}\cup\mathcal{S}_{i})$

In addition, if $\mathcal{Q},\mathcal{R}$ are multi-linear then we can take
$\mathcal{S}_{1}$ to be multi-linear.

###### Proof.

First, arrange $\mathcal{R}$ in a tower
$\mathcal{R}=(\mathcal{R}_{i}:V^{I_{i}}\to\mathbb{F})_{i\in[2^{k}]}$, with the
higher degree maps above the lower degree ones. As usual, denote
$m_{i}=|\mathcal{R}_{i}|.$ To the $i$-th layer we assign a number $n_{i},$
according to a formula we will give later. We describe an algorithm for
producing $\mathcal{S}_{i}$ and then show that it has the desired properties.
If for every $i$

$rk_{\mathcal{Q}\cup\mathcal{R}_{<i}}(\mathcal{R}_{i})>A(n_{i}+s)^{B},$

then we stop. Otherwise, there’s some $0\neq a\in\mathbb{F}^{m_{i}}$ such that

$a\cdot\mathcal{R}_{i}=\sum_{j=1}^{t}q_{j}(x_{I_{j}})r_{j}(x_{I_{i}\setminus
I_{j}})+\sum_{J\subsetneq
I_{i}}u_{J}(x_{J})+\sum_{f\in\mathcal{Q}\cup\mathcal{R}_{<i},\ I_{f}\subset
I_{i}}f(x_{I_{f}})h_{f}(x_{I_{i}\setminus I_{f}}),$

where $t\leq A(n_{i}+s)^{B}.$ Assume without loss of generality that
$a_{m_{i}}\neq 0.$ Let $\mathcal{R}^{\prime}$ be the tower obtained from
$\mathcal{R}$ by deleting $R_{i,m_{i}}.$ In
$Z(\mathcal{Q}\cup\mathcal{R}^{\prime}),$ the value of $R_{i,m_{i}}$ is
determined by the $q_{j},r_{j},u_{J}.$ We add these maps to the lower layers
of $\mathcal{R}^{\prime}$ and call the new tower $\mathcal{R}^{\prime\prime}.$
We can then split

$Z(\mathcal{Q}\cup\mathcal{R})=\bigsqcup_{i=1}^{c}\left(Z(\mathcal{Q})\cap\\{\mathcal{R}^{\prime\prime}=b_{i}\\}\right),$

where $b_{1},\ldots,b_{c}\in\mathbb{F}^{\mathcal{R}^{\prime\prime}}$ are the
values causing the maps in $\mathcal{R}$ to vanish on
$Z(\mathcal{Q})\cap\\{\mathcal{R}^{\prime\prime}=b_{i}\\}.$ Now we do the same
thing for each of the towers $\mathcal{R}^{\prime\prime}-b_{i}$ (with the same
$n_{i}$ we chose at the start) and so on. Because at each stage we replace a
map by maps of lower degree (and when handling a linear map we just delete
it), this algorithm eventually terminates. We now give the definition of
$n_{i}$ and check that the $\mathcal{S}_{i}$ we end up with satisfy
requirements 1-4. Set

$n_{2^{k}}=m_{2^{k}},\
n_{i}=m_{i}+n_{i+1}\left[2A(s+n_{i+1})^{B}+2^{d}\right].$

We prove inductively that the total number of polynomials passing through
layer $i$ and above during this process is $\leq n_{i}.$ For $i=2^{k}$ this is
clear since during regularization we only add polynomials to lower layers. Now
suppose this bound holds for $i.$ Any polynomials added to layer $i-1$ come
from regularizing the higher layers. Each polynomial upstairs can contribute
at most $2A(s+n_{i})^{B}+2^{d}$ when regularizing, so the bound at layer $i-1$
is proved, assuming the bound at layer $i.$ Therefore, conditions 1 and 3 are
satisfied. Conditions 2 and 4 clearly hold. If $\mathcal{Q},\mathcal{R}$ are
multi-linear then we can take $b_{1}=0$ at every stage, leaving us with
$\mathcal{S}_{1}$ multi-linear. ∎

##  7\. Fixing the approximation

In this section, we will take the many approximations that we get from
proposition 5.2 and ”glue” them together to get a single tower $\mathcal{R}$
such that $P$ vanishes identically on $Z(\mathcal{Q}\cup\mathcal{R}).$ A
central tool will be the following proposition (cf. proposition 5.1 in [10]):

######  Proposition 7.1 (Almost surely vanishing implies vanishing).

There exist constants $A(d,H),B(d,H),s(d)$ such that if $\mathcal{Q}$ is an
$(A,B,s)$-regular tower on $V^{[d+1]}$ of degree $\leq d$ and height $\leq H$
and $f:V^{[d+1]}\to\mathbb{F}$ is a polynomial map (not even necessarily
multi-affine) of degree $\leq d+1$ satisfying

$\mathbb{P}_{x\in Z(\mathcal{Q})}\left(f(x)=0\right)\geq 1-q^{-s},$

then $f(x)=0$ for all $x\in Z(\mathcal{Q}).$

Let $\mathcal{Q}=(\mathcal{Q}_{i})_{i\in[h]}$ where
$\deg(\mathcal{Q}_{i})=d_{i}$ and write $X=Z(\mathcal{Q})$ for short. In order
to prove this lemma we will need to count parallelepipeds based at any point
$x\in X.$ Given $x\in X$ and an integer $l,$ for each layer $i\in[h]$ we
define a layer $(\mathcal{Q}_{x,l})_{i}$ of maps
$(V_{1})^{l}\times\ldots\times(V_{d+1})^{l}\to\mathbb{F}$ by

$(\mathcal{Q}_{x,l})_{i}:=\\{\mathcal{Q}_{i}(x+\omega\cdot
t):\omega\in\\{0,1\\}^{l},0<|\omega|\leq d_{i}\\},$

and $\mathcal{Q}_{x,l}$ is the resulting tower. Writing
$X_{x,l}=Z(\mathcal{Q}_{x,l}),$ note that

$X_{x,l}:=\\{t_{1},\ldots,t_{l}\in V^{[d+1]}:x+\omega\cdot t\in X\
\forall\omega\in\\{0,1\\}^{l}\\}.$

We will also need to count parallelepipeds containing an additional point of
the form $x+t_{1}.$ Given $t_{1}\in X-x$ and $c\in[l],$ set

$X_{x,l,c}(t_{1})=\\{t_{2},\ldots,t_{l}\in V^{[d+1]}:(t_{1}-\ldots-
t_{c},t_{2},\ldots,t_{l})\in X_{x,l}\\}.$

######  Lemma 7.2.

If $\mathcal{Q}$ is $(Cl^{(d+1)D},D,s)$-regular then $\mathcal{Q}_{x,l}$ is an
$(C,D,s)$-regular tower of the same degree and height. Also, if $C,D$ are
sufficiently large depending on $A,B,d,H,l$ then for $q^{-s}$ a.e. $t_{1}\in
X-x$ we have $X_{x,l,c}(t_{1})=Z(\mathcal{R})$ where $\mathcal{R}$ is an
$(A,B,s)$-regular tower of the same degree as $\mathcal{Q}$, height $\leq
Hl^{d+1}$ and

$\dim(\mathcal{R})=\dim(\mathcal{Q}_{x,l})-\dim(\mathcal{Q}).$

###### Proof.

As usual, let $\tilde{\mathcal{Q}}$ denote the multi-linear tower
corresponding to $\mathcal{Q}.$ The multi-linear tower corresponding to
$\mathcal{Q}_{x,l}$ is then $\tilde{\mathcal{Q}}_{0,l},$ so we can assume
without loss of generality that $\mathcal{Q}$ is multi-linear and $x=0.$ By
claim 5.1, the tower $\mathcal{Q}^{\otimes(l,\ldots,l)}$ is $(A,B,s)$-regular.
The maps in $\mathcal{Q}_{x,l}$ are linear combinations of the maps in
$\mathcal{Q}^{\otimes(l,\ldots,l)},$ so we just need to verify that they are
linearly independent. Let $Q\in\mathcal{Q}$ be a map of degree $e$, assume
w.l.o.g. that $Q:V^{[e]}\to\mathbb{F},$ and suppose (to get a contradiction)
that we have a non-trivial linear combination

(5) $\sum_{\omega\in\\{0,1\\}^{l},0<|\omega|\leq e}a_{\omega}Q(\omega\cdot
t)=0.$

Let $\omega_{0}$ be the largest element with respect to the lexicographic
ordering on $\\{0,1\\}^{l}$ such that $a_{\omega_{0}}\neq 0$ and choose
$i_{1},\ldots,i_{e}\in\omega_{0}$ such that for every other $\omega$ with
$a_{\omega}\neq 0$ we have $\\{i_{1},\ldots,i_{e}\\}\not\subset\omega.$ Then
the coefficient of $Q(t_{i_{1}}(1),\ldots,t_{i_{e}}(e))$ in the left hand side
of equation 5 is $a_{\omega_{0}}\neq 0,$ contradiction. Now we turn to the
second part of the lemma. Since invertible affine transformations don’t affect
regularity, the variety

$\\{(t_{1},\ldots,t_{l}):(t_{1}-\ldots-t_{c},t_{2},\ldots,t_{l})\in
X_{x,l}\\}$

is the zero locus of a $(C,D,s)$-regular tower on
$(V_{1})^{l}\times\ldots\times(V_{d+1})^{l}.$ This tower remains regular if we
split up the layers into at most $l^{d+1}$ layers so that it’s a tower on

$V_{1}\times\ldots\times V_{1}\times\ldots\times V_{d+1}\times\ldots\times
V_{d+1}.$

Then by lemma 3.3 we get that for $q^{-s}$-a.e. $t_{1}\in X-x$ the variety

$\\{(t_{2},\ldots,t_{l}):(t_{1}-\ldots-t_{c},t_{2},\ldots,t_{l})\in
X_{x,l}\\}$

is the zero locus of a tower $\mathcal{R}$ which has the required properties.
∎

We now use this to prove the proposition from the start of this section.

###### Proof of proposition 7.1.

Let $G=\\{x\in X:f(x)=0\\},$ and $B=X\setminus G$ be the good and bad points
of $X,$ respectively. Fix $x\in X.$ Since $f$ is a polynomial of degree $\leq
d+1,$ for any $t_{1},\ldots,t_{d+2}\in V^{[d+1]}$ we have

$\sum_{\omega\in\\{0,1\\}^{d+2}}(-1)^{|\omega|}f(x+\omega\cdot t)=0.$

This means that if we can find $t\in X_{x,d+2}$ with $x+\omega\cdot t\in G$
for all $0\neq\omega\in\\{0,1\\}^{d+2}$ then $x\in G$ as well. Since the
previous claim (together with lemma 3.2) implies in particular that
$X_{x,d+2}\neq\emptyset,$ it’s enough to show the following bound for any
fixed $0\neq\omega\in\\{0,1\\}^{d+2}$

${\mathbb{E}}_{t\in X_{x,d+2}}1_{B}(x+\omega\cdot t)\leq 2^{-(d+2)}.$

By reordering the $t_{j}$, assume without loss of generality that
$\omega=(1^{c},0^{d+2-c}).$ By replacing $t_{1}$ with $t_{1}-t_{2}-\ldots-
t_{c},$ the left hand side becomes

${\mathbb{E}}_{t,(t_{1}-t_{2}-\ldots-t_{c},t_{2},\ldots,t_{d+2})\in
X_{x,d+2}}1_{B}(x+t_{1}).$

By lemma 7.2, the conclusion of lemma 3.4 holds (the proof is the same),
meaning

${\mathbb{E}}_{t,(t_{1}-t_{2}-\ldots-t_{c},t_{2},\ldots,t_{d+2})\in
X_{x,d+2}}1_{B}(x+t_{1})\leq{\mathbb{E}}_{t_{1}\in
X-x}1_{B}(x+t_{1})+q^{-s}\leq q^{1-s}.$

This proves the proposition for $s\geq 3+d.$ ∎

We now prove a claim which will allow us to glue the various approximations we
get in lemma 5.2 together.

######  Claim 7.3.

There exist $A(d,H),B(d,H),s(d)$ such that if $f:V^{[d+1]}\to\mathbb{F}$ is
multi-linear, $\mathcal{Q},\mathcal{G}_{1},\mathcal{G}_{2}$ are multi-linear
towers on $V^{[k]}$ satisfying
$f\restriction_{Z(\mathcal{Q}\cup\mathcal{G}_{j})}=0$ and
$\mathcal{Q}\cup\mathcal{G}_{1}\cup\mathcal{G}_{2}$ is $(A,B,s)$-regular of
degree $\leq d$ and height $\leq H,$ then for any $i\in[d+1]$ we have

$f\restriction_{\\{x\in Z(\mathcal{Q})\ :\ x_{[d+1]\setminus\\{i\\}}\in
Z(\mathcal{G}_{1}\cup\mathcal{G}_{2})_{[d+1]\setminus\\{i\\}}\\}}\equiv 0.$

###### Proof.

Denote $Z=Z(\mathcal{Q})\ ,\ Z_{j}=Z(\mathcal{G}_{j}).$ For any $x\in(Z\cap
Z_{1}\cap Z_{2})_{[d+1]\setminus\\{i\\}}$ we have
$f(x,\cdot)\restriction_{(Z\cap Z_{j})(x)}=0$ for $j=1,2$ so by multi-
linearity,

$f(x,\cdot)\restriction_{(Z\cap Z_{1})(x)+(Z\cap Z_{2})(x)}=0.$

By Lemma 3.3, for $q^{-2s}$-a.e. such $x,$ the linear equations appearing in
$\mathcal{Q}(x)\cup\mathcal{G}_{1}(x)\cup\mathcal{G}_{2}(x)$ are linearly
independent, in which case

$(Z\cap Z_{1})(x)+(Z\cap Z_{2})(x)=Z(x).$

By Lemma 3.4,

$\mathbb{P}_{\\{x\in Z\ :\ x_{[d+1]\setminus\\{i\\}}\in(Z_{1}\cap
Z_{2})_{[d+1]\setminus\\{i\\}}\\}}(f(x)=0)\geq 1-q^{-s}.$

Applying proposition 7.1, we get that this holds for any $x$ in the above
variety. ∎

######  Corollary 7.4.

There exist $A(d,H),B(d,H),s(d)$ such that when $f:V^{[d+1]}\to\mathbb{F}$ is
multi-linear, $\mathcal{Q},\mathcal{G}_{1},\ldots,\mathcal{G}_{2^{l}}$ are
multi-linear towers on $V^{[d+1]}$ such that the $\mathcal{G}_{j}$ only depend
on the first $l$ coordinates,
$\mathcal{Q}\cup\mathcal{G}_{1}\cup\ldots\cup\mathcal{G}_{2^{l}}$ is
$(A,B,s)$-regular of degree $\leq d$ and height $\leq H$, and

$f\restriction_{Z(\mathcal{Q})\cap Z(\mathcal{G}_{j})}\equiv 0\ \forall
j\in[2^{l}]$

then $f\restriction_{Z(\mathcal{Q})}\equiv 0.$

###### Proof.

By induction on $l.$ For $l=0$ this is clear. Suppose it holds up to some $l$
and we are given $\mathcal{G}_{1},\ldots,\mathcal{G}_{2^{l+1}}$ depending on
the first $l+1$ coordinates. Applying Claim 7.3 to each pair
$\mathcal{G}_{i},\mathcal{G}_{i+1}$ we get that

$f\restriction_{\\{x\in Z(\mathcal{Q})\ :\ x_{[d+1]\setminus\\{l\\}}\in
Z(\mathcal{G}_{i}\cup\mathcal{G}_{i+1})_{[d+1]\setminus\\{l\\}}\\}}\equiv 0.$

Then apply the inductive hypothesis to

$\mathcal{Q},(\mathcal{G}_{1}\cup\mathcal{G}_{2})_{[l]},\ldots,(\mathcal{G}_{2^{l+1}-1}\cup\mathcal{G}_{2^{l+1}})_{[l]}.$

∎

We summarize our results thus far with the following proposition, which brings
us very close to proving Theorem 2.13.

######  Proposition 7.5.

There exist constants $C(A,B,d,H),D(A,B,d,H)$ such that the following holds:
If $P:V^{[d+1]}\to\mathbb{F}$ is multi-linear, $\mathcal{Q}$ is a multi-linear
tower of degree $\leq d$ and height $\leq H$ such that:

  1. (1)

$bias_{Z(\mathcal{Q})}(P)\geq q^{-s}.$

  2. (2)

$\mathcal{Q}$ is $(C,D,s)$-regular.

then there exists a multi-linear tower $\mathcal{R}$ of degree $\leq d$ and
height $\leq 2^{d+1}$ satisfying

  1. (1)

$\dim(\mathcal{R})\leq C(1+s)^{D}.$

  2. (2)

$\mathcal{R}\cup\mathcal{Q}$ is $(A,B,s)$-regular.

  3. (3)

$P\restriction_{Z(\mathcal{R}\cup\mathcal{Q})}\equiv 0.$

###### Proof.

Denote $X=Z(\mathcal{Q})$ and let $E$ be the set from proposition 5.2. Given
$t\in E^{2^{d+1}},$ let $Y_{i}=\\{x\in V^{[d+1]}:\phi_{t_{i}}(x_{[d]})=0\\}$
\- so $P$ vanishes $q^{-s}$-a.e. on $X_{t_{i}}\cap Y_{i}.$ Applying lemma 6.2,
there are towers $\mathcal{R}_{i,1},\ldots,\mathcal{R}_{i,l}$ which are
$(A,B,s)$-regular relative to the tower defining $X_{t_{i}},$ satisfy
$\dim(\mathcal{R}_{i,j})\leq F(1+s)^{G}$ for some constants
$F(A,B,d),G(A,B,d)$ and such that

$X_{t_{i}}\cap Y_{i}=\bigsqcup_{j=1}^{l}(X_{t_{i}}\cap Y_{i,j}),$

where $Y_{i,j}=Z(\mathcal{R}_{i,j}).$ By averaging, there is some $j\in[l]$
such that $P$ vanishes $q^{-s}$-a.e. on $X_{t_{i}}\cap Y_{i,j}$ \- replace
$Y_{i}$ by this $Y_{i,j}.$ Now suppose that $X_{t_{i}}$ is
$(A,B,s+F(1+s)^{G})$-regular (we will soon explain why we can choose $t$ such
that this happens) and note that $X_{t_{i}}\cap Y_{i}$ is $(A,B,s)$-regular.
Applying lemma 4.2, we can replace $Y_{i}$ by $\tilde{Y_{i}}$ and still have
$\mathbb{P}_{x\in X_{t_{i}}\cap Y_{i}}\geq 1-q^{1-s}.$ By lemma 7.1,
$P\restriction_{X_{t_{i}}\cap Y_{i}}\equiv 0.$ Setting $Y=Y_{1}\cap\ldots\cap
Y_{2^{d+1}}$ we have $P\restriction_{X_{t_{i}}\cap Y}\equiv 0$ for all
$i\in[2^{d+1}].$ After applying Lemma 6.2 to $Y$ relative to
$X_{t}:=X_{t_{1}}\cap\ldots\cap X_{t_{2^{d+1}}}$ and assuming $X_{t}$ is
$(A,B,s+F(2^{d+1}F(1+s)^{G})^{G})$-regular we get that $X_{t}\cap Y$ is
$(A,B,s)$-regular. By corollary 7.4, we conclude that $P\restriction_{X\cap
Y}\equiv 0$ as desired.

Now we need to justify our assumptions on the regularity of $X_{t}.$ Writing
$n=100s,$ claims 3.3 and 5.1 imply that if $\mathcal{Q}$ is $(C,D,s)$-regular
for sufficiently large $C(A,B,d,H),D(A,B,d,H),$ then for $q^{-2^{d+2}n}$-a.e.
$t\in\left(X_{d+1}^{n}\right)^{2^{d+1}}$ the variety $X_{t}$ is
$(A,B,s+F(2^{d+1}F(1+s)^{G})^{G})$-regular as desired (in which case
$X_{t_{i}},$ which is only defined by some of the equations, also must have
the regularity we wanted). By Lemma 5.2, $E$ has density at least $q^{-n}$ in
$X_{d+1}^{n},$ so $E^{2^{d+1}}$ has density at least $q^{-2^{d+1}n}$ in
$\left(X_{d+1}^{n}\right)^{2^{d+1}}$ which means that there must be some $t\in
E^{2^{d+1}}$ for which $X_{t}$ has the desired regularity. ∎

##  8\. Nullstellensatz

In this section we finish the proof of Theorem 2.13, by proving a
nullstellensatz for regular towers. This is similar to section 3 of [21], but
by restricting our attention to regular towers we can prove a stronger result
for them. We start with the following definition.

######  Definition 8.1.

We give $V^{[k]}$ a graph structure where two points $x,y\in V^{[k]}$ are
connected by an edge if there exists some $i\in[k]$ such that
$x_{[k]\setminus\\{i\\}}=y_{[k]\setminus\\{i\\}},$ i.e. they differ in at most
one coordinate.

We will need the following technical lemma.

######  Lemma 8.2.

There exist constants $A(d,H),B(d,H)$ such that if $\mathcal{Q}$ is an
$(A,B,s)$-regular tower on $V^{[d+1]}$ of degree $\leq d$ and height $\leq H,$
$X=Z(\mathcal{Q})$ and $I\subset[d+1]$ then for $q^{-s}$-a.e. $x\in X,$ for
a.e. $y\in X\cap X(x_{\geq I})$ (with $X(x_{\geq I}):=\cap_{I\subset
J}\left(X(x_{J})\times V^{J}\right)),$ the points $x_{I},y_{I}$ are connected
by a path in $X(y_{[d+1]\setminus I}).$

###### Proof.

A sufficient condition for there to be a path in $X(y_{[d+1]\setminus I})$
between $x_{I},y_{I}$ is that there exists $z$ such that for all $K\subset I$
we have

$(x_{K},z_{I\setminus K}),(y_{K},z_{I\setminus K})\in X(y_{[d+1]\setminus
I}).$

Take the following variety

$Y=\left\\{(x_{K},z_{I\setminus K},y_{[d+1]\setminus I}),(y_{K},z_{I\setminus
K},y_{[d+1]\setminus I}),(x_{J},y_{[d+1]\setminus J})\in X:\ K\subset I\subset
J\right\\}.$

The equations defining it are partial to those of $\mathcal{Q}^{\times 3},$ so
by claim 5.1 we have $Y=Z(\mathcal{G})$ fo a $(C,D,s)$-regular tower of degree
$\leq d$ and height $\leq 3^{d+1}H$ as long as $\mathcal{Q}$ is
$(C(3^{d+1})^{D},D,s)$-regular. By lemmas 3.3 and 3.4, for $q^{-s}$-a.e. $x\in
X,$ for $q^{-s}$-a.e. $y\in X\cap X(x_{\geq I}),$ the variety $Y(x,y)$ (which
is composed of the $z^{\prime}$s we want) is
$(C^{\prime},D^{\prime},s)$-regular. In particular, by lemma 3.2 it is non-
empty. ∎

Now we are ready to prove:

######  Theorem 8.3 (Nullstellensatz).

There exist constants $A(d,H),B(d,H),s(d)$ such that if $\mathcal{Q}$ is an
$(A,B,s)$-regular multi-linear tower on $V^{[d+1]}$ of deg $\leq d$ and height
$\leq H$ and $P:V^{[d+1]}\to\mathbb{F}$ is a multi-linear map which vanishes
$q^{-s}$-a.e. on $Z(\mathcal{Q}),$ then $rk_{\mathcal{Q}}(P)=0.$

The proof of this theorem (like everything else in this paper) will be by
induction. For the inductive step we will use the following simple corollary
many times.

######  Corollary 8.4.

If $R_{1},R_{2}:V^{I}\to\mathbb{F}$ are multilinear maps,
$\mathcal{Q}_{1}\cup\mathcal{Q}_{2}$ is a multi-linear tower on $V^{[d+1]}$
for which the conclusion of theorem 8.3 holds, and

$\mathbb{P}_{x\in
Z(\mathcal{Q}_{1}\cup\mathcal{Q}_{2})}[R_{1}(x)=R_{2}(x)]\geq 1-q^{-s}$

then there exists a multi-linear map $R:V^{I}\to\mathbb{F}$ with
$R\restriction_{Z(\mathcal{Q}_{1})}\equiv
R_{1}\restriction_{Z(\mathcal{Q}_{1})}$ and
$R\restriction_{Z(\mathcal{Q}_{2})}\equiv
R_{2}\restriction_{Z(\mathcal{Q}_{2})}.$

###### Proof of corollary.

By theorem 8.3, $rk_{\mathcal{Q}_{1}\cup\mathcal{Q}_{2}}(R_{1}-R_{2})=0.$
Therefore there exist multi-linear maps $f,g:V^{I}\to\mathbb{F}$ with
$rk_{\mathcal{Q}_{1}}(f)=rk_{\mathcal{Q}_{2}}(g)=0$ and $R_{1}-R_{2}=f+g.$
Setting $R=R_{1}-f=R_{2}+g$ does the job. ∎

###### Proof of theorem 8.3.

By lemma 7.1, we have that $P\restriction_{Z(\mathcal{Q})}=0.$ The proof will
proceed by induction on $\mathcal{Q}.$ For the base case
$\mathcal{Q}=\emptyset$ this is trivial. For the inductive step, choose some
$Q_{0}\in\mathcal{Q}$ with a maximal size index set $I,$ and write
$\mathcal{Q}^{\prime}=\mathcal{Q}\setminus\\{Q_{0}\\}.$ Apply lemma 8.2 to the
variety $X=Z(\mathcal{Q}^{\prime})\cap\\{Q_{0}=1\\}.$ Choose
$x^{1},\ldots,x^{2^{d+1}}\in X$ such that for each $j,$ $x^{j}$ satisfies the
conclusion of lemma 8.2 with $q^{-s}$-a.e. $y\in X\cap X(x^{j}_{\geq I})$ and
such that $\mathcal{Q}\cup\mathcal{Q}(\textbf{x}_{\geq I})$ is
$(C,D,s)$-regular, where $\mathcal{Q}(\textbf{x}_{\geq
I}):=\bigcup_{j=1}^{2^{d+1}}\mathcal{Q}(x^{j}_{\geq I}).$ The reason we can
choose such $x^{j}$’s is that the first condition holds $2^{d+1}q^{-s}$-a.s.
by a union bound and the second one holds (as long as $A,B$ are sufficiently
large) $q^{-s}$-a.s. by claim 5.1 and lemma 3.3. Let
$\mathcal{Q}^{j}=\mathcal{Q}^{\prime}\cup\mathcal{Q}(x^{j}_{\geq I})$ and
define $R^{j}(y_{[d+1]\setminus I})=P(x^{j}_{I},y_{[d+1]\setminus I}).$ We
claim that

$\mathbb{P}_{y\in Z(\mathcal{Q}^{j})}[P(y)=R^{j}(y_{[d+1]\setminus
I})Q_{0}(y_{I})]\geq 1-q^{-s}.$

Note that

$Z(\mathcal{Q}^{j})=\bigsqcup_{a\in\mathbb{F}}Z(\mathcal{Q}^{j})\cap\\{Q_{0}=a\\},$

and both sides vanish on $Z(\mathcal{Q})$ by assumption, so by scaling one of
the coordinates it’s enough to prove that

$\mathbb{P}_{y\in
Z(\mathcal{Q}^{j})\cap\\{Q_{0}=1\\}}[P(y)=R^{j}(y_{[d+1]\setminus
I})Q(y_{I})]\geq 1-q^{-s}.$

Recall that by our definitions, $Z(\mathcal{Q}^{j})\cap\\{Q_{0}=1\\}=X\cap
X(x^{j}_{\geq I}).$ Now, for any $y\in X\cap X(x^{j}_{\geq I})$ we have
equality at the point $(x^{j}_{I},y_{[d+1]\setminus I})\in
Z(\mathcal{Q}^{j}).$ Also, for $q^{-s}$-a.e. such $y,$ the points
$x^{j}_{I},y_{I}$ are connected in $X(y_{[d+1]\setminus I}).$ Each time two
points in $X$ differ by a single coordinate in $I,$ the values of both sides
don’t change, because the difference of the two points is in $Z(\mathcal{Q}).$
This means that

$\mathbb{P}_{y\in X\cap X(x^{j}_{\geq I})}[P(y)=R^{j}(y_{[d+1]\setminus
I})Q_{0}(y_{I})]\geq 1-q^{-s}$

as desired, implying the same for $Z(\mathcal{Q}^{j}).$

By lemma 7.1, we get that $P(y)=R^{j}(y_{[d+1]\setminus I})Q(y_{I})$ for all
$y\in Z(\mathcal{Q}^{j}).$ The following claim will complete the inductive
step.

######  Claim 8.5.

There exist constants $C(d,H),D(d,H)$ such that if
$\mathcal{F},\mathcal{G}^{j}$ for $j\in[2^{k}]$ are towers on $V^{[d+1]},$ of
degree $\leq d$ and height $\leq H,$ such that the $\mathcal{G}^{j}$ depend
only on the first $k$ coordinates, and
$Q:V^{I}\to\mathbb{F},R^{j}:V^{[d+1]\setminus I}\to\mathbb{F}$ are multi-
linear maps, where

  1. (1)

$P(y)=R^{j}(y_{[d+1]\setminus I})Q(y_{I})\ \forall y\in
Z(\mathcal{F}\cup\mathcal{G}^{j}).$

  2. (2)

$\mathcal{F}\cup\\{Q\\}\cup\bigcup_{j\in[2^{k}]}\mathcal{G}^{j}$ is
$(C,D,s)$-regular.

  3. (3)

The nullstellensatz holds for
$\mathcal{F}\cup\bigcup_{j\in[2^{k}]}\mathcal{G}^{j}$ and towers contained in
it.

Then there exists a multi-linear $R:V^{[d+1]\setminus I}\to\mathbb{F}$ such
that $P(y)=R(y_{[d+1]\setminus I})Q(y_{I})$ for all $y\in Z(\mathcal{F}).$

###### Proof of claim.

We prove this by induction on $k.$ For $k=0$ there’s nothing to prove. Now
suppose we’ve proved it up to $k$ and $\mathcal{G}^{j}$ are all defined on the
first $k+1$ coordinates. By looking at
$Z(\mathcal{F}\cup\mathcal{G}^{i}\cup\mathcal{G}^{i+1})$, we get
$R^{i}(y_{[d+1]\setminus I})Q(y_{I})=R^{i+1}(y_{[d+1]\setminus I})Q(y_{I})$ on
$Z(\mathcal{F}\cup\mathcal{G}^{i}\cup\mathcal{G}^{i+1}).$ By lemma 3.3
(together with lemma 3.2), for $q^{-s}$-a.e. $y_{[d+1]\setminus I}\in
Z(\mathcal{F}\cup\mathcal{G}^{i}\cup\mathcal{G}^{i+1})_{[d+1]\setminus I},$
there exists $y_{I}$ such that $y\in
Z(\mathcal{F}\cup\mathcal{G}^{i}\cup\mathcal{G}^{i+1})\cap\\{Q(y_{I})=1\\},$
in which case $R^{i}(y_{[d+1]\setminus I})=R^{i+1}(y_{[d+1]\setminus I}).$ By
corollary 8.4, there exists $S^{i}$ such that
$P\restriction_{Z(\mathcal{F}\cup\mathcal{G}^{j})}=S^{i}(x_{[d+1]\setminus
I})Q(x_{I}).$ for $j=i,i+1.$ Applying Lemma 7.3, we get that
$P\restriction_{Z(\mathcal{F}\cup(\mathcal{G}^{i}\cup\mathcal{G}^{i+1})_{[k]})}=S^{i}(x_{[d+1]\setminus
I})Q(x_{I}).$ Now apply the induction hypothesis to the collection
$(\mathcal{G}^{i}\cup\mathcal{G}^{i+1})_{[k]}$ and we’re done. ∎

Applying the above claim with $\mathcal{F}=\mathcal{Q}^{\prime}$ and
$\mathcal{G}^{j}=\mathcal{Q}(x^{j}_{\geq I})$ (Note that the equations coming
from $x^{j}_{\geq I}$ are of deg $<|I|,$ so the induction hypothesis applies
to $\mathcal{Q}^{\prime}\cup\bigcup_{j\in[2^{d+1}]}Q^{j}$ and towers partial
to it) we get that $P(y)=R(y_{[d+1]\setminus I})Q(y_{I})$ on
$Z(\mathcal{Q}^{\prime}).$ By the inductive hypothesis,
$rk_{\mathcal{Q}^{\prime}}\left(P(y)-R(y_{[d+1]\setminus I})Q(y_{I})\right)=0$
and this completes the inductive step. ∎

##  9\. Reduction to the multi-linear case

In this section, we show that Theorem 2.2 and 2.7 follow from their multi-
linear analogues - Theorem 2.13 and Theorem 8.3. In order to do this, we will
show that both relative bias and relative rank behave well when passing from
polynomials to corresponding multi-linear maps. We start by recalling the
polarization identity which associates a multi-linear map to a polynomial. The
following is well known.

######  Claim 9.1.

Given a polynomial $P$ on $V$ of degree $d<char(\mathbb{F}),$ the map
$\bar{P}:V^{d}\to\mathbb{F}$ defined by
$\bar{P}(x_{1},\ldots,x_{d})=\frac{1}{d!}\triangle_{x_{1}}\ldots\triangle_{x_{d}}P$
is multilinear and satisfies $\bar{P}(x,\ldots,x)=\tilde{P}(x)$ (the
homogeneous part of $P$ of highest degree).

######  Definition 9.2.

Given a polynomial tower $\mathcal{Q}$ on $V,$ of degree $\leq
d<char(\mathbb{F})$ and height $\leq H,$ there exists a symmetric multi-linear
tower $\mathcal{Q}(k)$ of degree $\leq d$ and height $\leq 2^{k}H$ on $V^{k}$
corresponding to it. For a layer $\mathcal{Q}_{i}$ of degree $e$ and a subset
$E\subset[k]$ of size $e,$ we get $\mathcal{Q}(k)_{i,E}:V^{E}\to\mathbb{F}$
given by $\bar{\mathcal{Q}_{i}}.$ Conversely, given a multi-linear tower
$\mathcal{Q}$ on $V^{k}$ it induces a polynomial tower $\mathcal{Q}\circ D$ on
$V$ by pre-composition with the diagonal map $\mathcal{Q}\circ
D=\mathcal{Q}(x,\ldots,x).$

######  Claim 9.3.

If $\mathcal{Q}$ is an $(A2^{kB},B,s)$-regular polynomial tower, then
$\mathcal{Q}(k)$ is $(A,B,s)$-regular. Conversely if $\mathcal{Q}(k)$ is
$(A2^{kB},B,s)$-regular and $k\geq\deg(\mathcal{Q})$, then $\mathcal{Q}$ is
$(A,B,s)$-regular.

###### Proof.

Assume without loss of generality that $\mathcal{Q}$ is homogeneous. The
polynomials of degree $d_{i}$ in $\mathcal{Q}$ give $\binom{k}{d_{i}}\leq
2^{k}$ polynomials in $\mathcal{Q}(k),$ so we just need to check that

$prk_{\bar{\mathcal{Q}}_{<i}}(\bar{\mathcal{Q}}_{i})\geq
rk_{\mathcal{Q}_{<i}}(\mathcal{Q}_{i}).$

This follows by plugging in the diagonal for any relative low partition rank
combination. For the converse, we need to check that

$prk_{\bar{\mathcal{Q}}_{<i}}(\bar{\mathcal{Q}}_{i})\leq
2^{k}rk_{\mathcal{Q}_{<i}}(\mathcal{Q}_{i}).$

This follows from the polarization identity for any low relative polynomial
rank combination. ∎

We recall theorem 2.2:

######  Theorem 9.4 (Relative bias implies relative low rank).

There exist constants $A(d,H),B(d,H)$ such that if $\mathcal{Q}$ is an
$(A,B,s)$-regular tower of degree $\leq d<char(\mathbb{F})$ and height $\leq
H$ and $P$ is a polynomial of degree $\leq d$ with

$bias_{Z(\mathcal{Q})}(P)\geq q^{-s}.$

then

$rk_{\mathcal{Q}}(P)\leq A(1+s)^{B}.$

We call $\mathcal{Q}$ as above a tower of type $(d,H)$ for short. The proof
will be by induction on the degree $d.$ For $d=1$ it follows from classical
Fourier analysis. Now we assume the theorem holds for degree $d$ and explore
some consequences.

######  Lemma 9.5 (Regular varieties are of the expected size (d,H)).

There exist constants $A(d,H),B(d,H)$ such that for any $s>0$ and for any
$(A,B,s)$-regular polynomial tower $\mathcal{Q}$ of type $(d,H)$ defined on
$V$ of degree $\leq d,$ height $\leq H$ and dimension $m,$ we have

$\left|q^{m}\frac{|Z(\mathcal{Q})|}{|V|}-1\right|\leq q^{-s}.$

###### Proof.

Identical to that of Lemma 3.2. ∎

Now we will prove a lemma analogous to Lemma 3.3. For a polynomial tower
$\mathcal{Q}$ and $t\in V$ we denote

$\triangle_{t}\mathcal{Q}=\\{\triangle_{t}Q:Q\in\mathcal{Q}\\}\ ,\
\mathcal{Q}_{t}=\mathcal{Q}\cup\triangle_{t}\mathcal{Q}.$

######  Lemma 9.6 (Derivatives).

For any $C,D$ there exist constants $A(C,D,d,H),$ $B(C,D,d,H)$ such that if
$\mathcal{Q}$ is an $(Ak^{B},B,s)$-regular polynomial tower of type $(d,H)$
then for $q^{-s}$-a.e. $t_{1},\ldots,t_{k}\in Z(\mathcal{Q}(1))$ the tower
$\mathcal{Q}_{t_{1}}\cup\ldots\cup\mathcal{Q}_{t_{k}}$ is $(C,D,s)$-regular.

###### Proof.

By Claim 9.3, it’s enough that
$(\mathcal{Q}_{t_{1}}\cup\ldots\cup\mathcal{Q}_{t_{k}})(d)$ is
$(C2^{dD},D,s)$-regular. By the same claim, $\mathcal{Q}(d+1)$ is
$(Ek^{F},F,s)$-regular as long as $A,B$ are large. By Claim 5.1 applied with
multiplicity vector $l=(1,\ldots,1,k),$ the tower
$\mathcal{Q}^{\prime}=(\mathcal{Q}(d+1))^{\otimes l}$ is $(E,F,s)$-regular.
Then by lemma 3.3 for $E,F$ sufficiently large, it follows that for
$q^{-s}$-a.e. $t_{1},\ldots,t_{k}\in Z(\mathcal{Q}(1)),$ the tower
$\mathcal{Q}^{\prime}(t_{1},\ldots,t_{k})$ is $(C,D,s)$-regular.
$\mathcal{Q}^{\prime}(t_{1},\ldots,t_{k})=(\mathcal{Q}_{t_{1}}\cup\ldots\cup\mathcal{Q}_{t_{k}})(d),$
so we are done. ∎

######  Corollary 9.7 (Fubini).

There are constants $A(d,H),B(d,H)$ such that if $\mathcal{Q}$ is an
$(A,B,s)$-regular polynomial tower of type $(d,H)$ and $f$ is a one-bounded
function, then we have

$\left|{\mathbb{E}}_{x,y\in Z(\mathcal{Q})}f(x,y)-{\mathbb{E}}_{t\in
Z(\mathcal{Q}(1))}{\mathbb{E}}_{x\in Z(\mathcal{Q}_{t})}f(x,x+t)\right|\leq
q^{-s}.$

###### Proof.

Identical to the proof of lemma 3.4. ∎

For a function $f:V\to{\mathbb{C}},$ and $t\in V,$ denote the (multiplicative)
derivative by $\triangle_{t}f(x)=f(x+t)\bar{f}(x).$ For $t=(t_{1}\ldots
t_{k})\in V^{k},$ write
$\mathcal{Q}_{t}=(\ldots(\mathcal{Q}_{t_{1}})_{t_{2}})\ldots)_{t_{k}}.$

######  Lemma 9.8 (Cauchy-Shcwarz).

There exist $A(d,H,k),B(d,H,k)$ such that if $\mathcal{Q}$ is an
$(A,B,s)$-regular polynomial tower of degree $\leq d$ and height $\leq H,$ and
$f:V\to{\mathbb{C}}$ is a one-bounded function, then

$|{\mathbb{E}}_{x\in Z(\mathcal{Q})}f(x)|^{2^{k}}\leq
Re\left({\mathbb{E}}_{t\in Z(\mathcal{Q}(k))}{\mathbb{E}}_{x\in
Z(\mathcal{Q}_{t})}\triangle_{t_{1}}\ldots\triangle_{t_{k}}f(x)\right)+q^{-s}.$

###### Proof.

By induction on $k.$ For $k=1$ this follows from corollary 9.7. Suppose it
holds up to $k-1.$ Then if $A,B$ are sufficiently large we can apply corollary
9.7 to get

$|{\mathbb{E}}_{x\in Z(\mathcal{Q})}f(x)|^{2^{k}}=|{\mathbb{E}}_{x,y\in
Z(\mathcal{Q})}f(x)\bar{f}(y)|^{2^{k-1}}\leq|{\mathbb{E}}_{t\in
Z(\mathcal{Q}(1))}{\mathbb{E}}_{x\in
Z(\mathcal{Q}_{t})}\triangle_{t}f(x)|^{2^{k-1}}+q^{-4s}\\\
\leq{\mathbb{E}}_{t\in Z(\mathcal{Q}(1))}|{\mathbb{E}}_{x\in
Z(\mathcal{Q}_{t})}\triangle_{t}f(x)|^{2^{k-1}}+q^{-4s}.$

If $A,B$ are sufficiently large, then by Lemma 9.6 the inductive hypothesis
applies to $q^{-4s}$-a.e. $\mathcal{Q}_{t}.$ Therefore,

${\mathbb{E}}_{t\in Z(\mathcal{Q}(1))}|{\mathbb{E}}_{x\in
Z(\mathcal{Q}_{t})}\triangle_{t}f(x)|^{2^{k-1}}\\\ \leq
Re\left({\mathbb{E}}_{t\in Z(\mathcal{Q}(1))}{\mathbb{E}}_{s\in
Z(\mathcal{Q}_{t}(k-1))}{\mathbb{E}}_{x\in
Z((\mathcal{Q}_{t})_{s})}\triangle_{s}\triangle_{t}f(x)\right)+q^{-2s}.$

Finally, using the fact that $\mathcal{Q}_{t}(k-1)=(\mathcal{Q}(k))(t)$ and
applying Lemma 3.4 for $\mathcal{Q}(k),$ we get that

$Re\left({\mathbb{E}}_{t\in Z(\mathcal{Q}(1))}{\mathbb{E}}_{s\in
Z(\mathcal{Q}_{t}(k-1))}{\mathbb{E}}_{x\in
Z(\mathcal{Q}_{(t,s)})}\triangle_{s}\triangle_{t}f(x)\right)\\\ \leq
Re\left({\mathbb{E}}_{t\in Z(\mathcal{Q}(k))}{\mathbb{E}}_{x\in
Z(\mathcal{Q}_{t})}\triangle_{t_{1}}\ldots\triangle_{t_{k}}f(x)\right)+q^{-2s},$

which completes the inductive step. ∎

######  Corollary 9.9.

Theorem 2.2 holds for polynomials of degree $\leq d+1$ on towers of degree
$\leq d.$

###### Proof.

When $\deg(P)\leq d$ we are already assuming this holds, so we deal with the
case $\deg(P)=d+1.$ If $bias_{Z(\mathcal{Q})}(P)\geq q^{-s}$ then by Lemma 9.8
we get that $bias_{Z(\mathcal{Q}(d+1))}(\bar{P})\geq q^{-2s}.$ By Claim 9.3,
the tower $\mathcal{Q}(d+1)$ is regular, so we can apply Theorem 2.13 to
deduce that $prk_{\mathcal{Q}(d+1)}(\bar{P})\leq A(1+s)^{B}.$ Plugging in the
diagonal, we get that $rk_{\mathcal{Q}}(P)\leq A(1+s)^{B}.$ ∎

To deal with towers of degree $d+1,$ we introduce an auxiliary parameter like
we did in the proof of theorem 2.13:

######  Theorem 9.10 (Relative bias implies relative low rank).

There exist constants $A(d,H,l),B(d,H,l)$ such that if $\mathcal{Q}$ is an
$(A,B,s)$-regular tower of degree $\leq d+1<char(\mathbb{F})$ and height $\leq
H$ such that $\mathcal{Q}_{\leq H-l}$ is of degree $\leq d,$ and $P$ is a
polynomial of degree $\leq d+1$ with

$bias_{Z(\mathcal{Q})}(P)\geq q^{-s}.$

then

$rk_{\mathcal{Q}}(P)\leq A(1+s)^{B}.$

A tower $\mathcal{Q}$ as above is called a tower of type $(d+1,H,l)$ for
short. We have just seen this theorem holds for towers of type $(d+1,H,0).$
Theorem 2.2 is for towers of type $(d+1,H,H).$

###### Proof of theorem 9.10.

By induction on $l.$ We have just seen the base case $l=0.$ Suppose the
theorem holds for towers of type $(d+1,H,l)$ and $\mathcal{Q}$ is now of type
$(d+1,H,l+1).$ The inductive assumption implies lemma 9.5 for $\mathcal{Q}$
and $\mathcal{Q}_{<H}$ (as in the proof of lemma 3.2), so we get

$\sum_{a\in\mathbb{F}^{m_{H}}}bias_{Z(\mathcal{Q}_{<H})}(P+a\cdot\mathcal{Q}_{H})\geq
q^{-2s}.$

By sub-additivity of relative rank, there is at most a single
$a_{0}\in\mathbb{F}^{m_{H}}$ with
$rk_{\mathcal{Q}_{<H}}(P+a\cdot\mathcal{Q}_{H})\leq A/2(m_{H}+s)^{B},$ and if
$\deg(P)<\deg(\mathcal{Q}_{H})$ then $a_{0}=0.$ By the theorem applied to
$\mathcal{Q}_{<H}$ we get that for all $a\neq a_{0},$

$bias_{Z(\mathcal{Q}_{<H})}(P+a\cdot\mathcal{Q}_{H})\leq q^{-4s-m_{H}},$

so $bias_{Z(\mathcal{Q}_{<H})}(P+a_{0}\cdot\mathcal{Q}_{H})\geq q^{-4s}.$ This
gives

$rk_{\mathcal{Q}}(P)\leq
rk_{Z(\mathcal{Q}_{<H})}(P+a_{0}\cdot\mathcal{Q}_{H})\leq A(1+s)^{B}.$

∎

We are also ready to prove Theorem 2.7:

######  Theorem 9.11 (Robust Nullstellensatz for regular collections).

There exist constants $A(d,H),B(d,H),s(d)$ such that if
$\mathcal{Q}=(Q_{i,j})_{i\in[h],j\in[m_{i}]}$ is an $(A,B,s)$-regular
polynomial tower of deg $\leq d<char(\mathbb{F})$ and height $\leq H,$ and $P$
is a polynomial of degree $\leq d$ which vanishes $q^{-s}$-a.e. on
$Z(\mathcal{Q}),$ then there exist polynomials $R_{i,j}$ satisfying
$\deg(R_{i,j})+\deg(Q_{i,j})\leq\deg(P)$ and

$P=\sum_{i,j}R_{i,j}Q_{i,j}.$

###### Proof.

By induction on $\deg(P).$ For constant $P$ there is nothing to prove, since
we know by Lemma 9.5 that $Z(\mathcal{Q})\neq\emptyset.$ Suppose the theorem
holds up to degree $k-1$ and $\deg(P)=k.$ Suppose $P$ vanishes $q^{-s}$-a.e.
on $Z(\mathcal{Q}).$ By lemmas 9.8 and 3.4, $\bar{P}$ vanishes $q^{-s}$-a.e.
on $Z(\mathcal{Q}(k)).$ By Theorem 8.3, $rk_{\mathcal{Q}(k)}(\bar{P})=0.$
Plugging in the diagonal, this implies that
$rk_{\tilde{\mathcal{Q}}}(\tilde{P})=0$ so there exist $R_{i,j}$ with
$\tilde{P}=\sum R_{i,j}\tilde{Q}_{i,j}.$ The polynomial $P^{\prime}=P-\sum
R_{i,j}Q_{i,j}$ has $\deg(P^{\prime})\leq k-1$ and also vanishes $q^{-s}$-a.e.
on $Z(\mathcal{Q}).$ Applying the inductive hypothesis finishes the proof. ∎

##  Appendix A Adaptations of results involving rank to relative rank

We formulate and prove the relevant parts of the Theorems in [15, 17],
replacing rank with relative rank. Let $\mathbb{F}$ be a field. For an
algebraic $\mathbb{F}$-variety $\mathbb{X}$ we write
$X(\mathbb{F}):=\mathbb{X}(\mathbb{F})$. To simplify notations we often write
$X$ instead of $X(\mathbb{F})$. In particular we write
$V:=\mathbb{V}(\mathbb{F})$ when $\mathbb{V}$ is a vector space and write
$\mathbb{F}^{N}$ for $\mathbb{A}^{N}(\mathbb{F})$.

For a $\mathbb{F}$-vector space $\mathbb{V}$ we denote by
$\mathcal{P}_{\bar{d}}(\mathbb{V})$ the algebraic variety of tuples
polynomials $\bar{P}=(P_{1},\ldots,P_{c})$ on $\mathbb{V}$ of degrees
$\leq\bar{d}$ and by $\mathcal{P}_{\bar{d}}(V)$ the set of tuples of
polynomials functions $\bar{P}:V\to\mathbb{F}^{c}$ of degree $\leq\bar{d}$. We
always assume that $d<char(\mathbb{F})$, so the restriction map
$\mathcal{P}_{\bar{d}}(\mathbb{V})(\mathbb{F})\to\mathcal{P}_{\bar{d}}(V)$ is
a bijection.

We recall some of the definitions in [15].

######  Definition A.1.

  1. (1)

For $m\geq 1$ and a $\mathbb{F}$-vector space $V$, we denote by
$\text{Aff}_{m}(\mathbb{V})$ the algebraic variety of affine maps
$\phi:\mathbb{A}^{m}\to\mathbb{V}$ and write
$\text{Aff}_{m}(V):=\text{Aff}_{m}(\mathbb{V})(\mathbb{F})$.

  2. (2)

We define an algebraic morphism
$\tilde{\kappa}_{\bar{P}}:\text{Aff}_{m}(\mathbb{V})\to\mathcal{P}_{\bar{d}}(\mathbb{A}^{m})$
by $\tilde{\kappa}_{\bar{P}}(\phi):=\bar{P}\circ\phi$, and denote by
$\kappa_{\bar{P}}$ the corresponding map
$\text{Aff}_{m}(V)\to\mathcal{P}_{\bar{d}}(\mathbb{F}^{m})$.

######  Definition A.2.

A map $\kappa:M\to N$ between finite sets is $\varepsilon$-uniform, where
$\varepsilon>0$, if for all $n\in N$ we have

$\left||N||\kappa^{-1}(n)|-|M|\right|\leq\varepsilon|M|.$

######  Theorem A.3.

There exist constants $A(d,h),B(d,h)$ such that for any $m,s\geq 1,$ any
finite field $\mathbb{F}=\mathbb{F}_{q},$ and any $(Am^{B},B,s)$-regular tower
$\bar{P}$ of degree $\leq d<char(\mathbb{F})$ and height $\leq h,$ the map
$\kappa_{\bar{P}}:\text{Aff}_{m}(\mathbb{V})\to\mathcal{P}_{\bar{d}}(\mathbb{A}^{m})$
is $q^{-s}$ uniform.

As a corollary we obtain (as in [15])

######  Theorem A.4.

For any $m\geq 1$, any algebraically closed field $\mathbb{F}$ of
characteristic zero or $>d$, any $\mathbb{F}$-vector space $V$ and any
$(Am^{B},B,2)$-regular tower $\bar{P}$ of degree $\leq d$ and height $\leq h,$
where $A,B$ are the constants of Theorem A.3, we have

  1. (1)

The map $\kappa_{\bar{P}}$ is surjective.

  2. (2)

All fibers of the morphism $\tilde{\kappa}_{\bar{P}}$ are of the same
dimension.

  3. (3)

The morphism $\tilde{\kappa}_{\bar{P}}$ is flat.

  4. (4)

$\bar{P}\subset\mathbb{F}[V^{\vee}]$ is a regular sequence.

Let $\epsilon>0$ we say that a property holds for $\epsilon$-a.e. $s\in S$ if
it holds for all but $(1-\epsilon)|S|$ of the elements in $S$.

As in [15], Theorem A.3 follows from the following result:

######  Theorem A.5.

Let $d\geq 0$. There exist $A(d,h),B(d,h)$ such that for any $s,m>0$ the
following holds: Let $\mathbb{F}=\mathbb{F}_{q}$ be a finite field of
characterisitc $>d$, let $\bar{P}$ be an $(Am^{B},B,s)$-regular tower of
degree $\leq d$ and height $\leq h$ composed of polynomials
$(P_{1},\ldots,P_{c})$ of degrees $(d_{1},\ldots,d_{c})$ on
$V=\mathbb{F}^{n}.$ Then:

  1. (1)

For any collection of polynomials $\bar{R}=(R_{i})_{1\leq i\leq c}$, with
$R_{i}:\mathbb{F}^{m}\to\mathbb{F}$ of degree $d_{i}$, there exist an affine
map $w:\mathbb{F}^{m}\to\mathbb{F}^{n}$ such that $\bar{P}(w(x))=\bar{R}(x)$.
Furthermore, if we denote by $n_{\bar{R}}$ the number of such affine maps,
then for any $\bar{R}_{1},\bar{R}_{2}$ as above
$|1-n_{\bar{R}_{1}}/n_{\bar{R}_{2}}|<q^{-s}$.

  2. (2)

If $\bar{P}$ is homogeneous, then for any homogeneous collection
$\bar{R}=(R_{i})_{1\leq i\leq c}$, $R_{i}:\mathbb{F}^{m}\to\mathbb{F}$ of
degree $d_{i}$, there exist a linear map $w:\mathbb{F}^{m}\to\mathbb{F}^{n}$
such that $\bar{P}(w(x))=\bar{R}(x)$. Furthermore, if we denote by
$n_{\bar{R}}$ the number of such linear maps, then for any
$\bar{R}_{1},\bar{R}_{2}$ as above
$|1-n_{\bar{R}_{1}}/n_{\bar{R}_{2}}|<q^{-s}$.

###### Proof.

We prove by induction on $d$. For $d=1$ the statement is clear. Assume $d>1$
We are given a filtered collection of polynomials
$\mathcal{P}=\\{P^{e,f}\\}_{1\leq e\leq h,0\leq f\leq J_{e}}$. We first make
the following observation. Let $P$ be of degree $d$ .
$P(t)=\sum_{I\in\mathcal{I}_{k}}a_{I}t_{I}$ where $\mathcal{I}_{d}(n)$ is the
set of ordered tuples $I=(i_{1},\ldots,i_{d})$ with $1\leq i_{1}\leq\ldots\leq
i_{d}\leq n$, and $t_{I}=t_{i_{1}}\ldots t_{i_{d}}$. Note that for any
polynomials $l(t)$ of degrees $<d$ we have that $P(t)+l(t)$ is of the same
rank as $P$. We can write

$P(w(x))=\sum_{I\in\mathcal{I}_{d}(n)}a_{I}w^{I}(x)=\sum_{I\in\mathcal{I}_{d}(n)}a_{I}\sum_{l_{1},\ldots,l_{d}=1}^{m}w^{i_{1}}_{l_{1}}\ldots
w^{i_{d}}_{l_{d}}x_{l_{1}}\ldots x_{l_{d}},$

where $w^{I}=\prod_{i\in I}w^{i}$. For
$(l_{1},\ldots,l_{d})\in\mathcal{I}_{d}(m)$ the term $x_{l_{1}}\ldots
x_{l_{d}}$ has as coefficient

$Q_{(l_{1},\ldots,l_{d})}(w)=\sum_{\sigma\in
S_{d}}\sum_{I\in\mathcal{I}(n)}a_{I}w^{i_{1}}_{l_{\sigma(1)}}\ldots
w^{i_{d}}_{l_{\sigma(d)}}.$

Observe that restricted to the subspace $w_{l_{1}}=\ldots=w_{l_{d}}$ we can
write the above as

$Q_{(l_{1},\ldots,l_{d})}(w)=d!P(w_{l_{1}})+R(w)$

where $w_{j}=(w_{j}^{1},\ldots,w_{j}^{n})$, and $R(w)$ is of lower degree in
$w_{l_{1}}$.

Now consider the filtered system $\mathcal{P}$. It gives rise to a filtered
system

$\\{Q^{e,f}_{(l_{1},\ldots,l_{e})}(w)\\}_{1\leq e\leq h,0\leq f\leq
J_{e},(l_{1},\ldots,l_{d_{e}})\in\mathcal{I}_{d_{e}}(m)}$

Given an element $Q^{e,f}_{(l_{1},\ldots,l_{d})}$ at level $e$ of degree $d$,
we restrict to a subspace as above and get
$Q^{e,f}(w)=d!P(w_{l_{1}})+R^{e,f}(w)$ and $R(w)$ is of lower degree in
$w_{l_{1}}$. But the same holds for all lower degree polynomials as well -
restricted to this subspace they are of the form
$j!P^{e,f}(w_{l_{1}})+R^{e,f}(w)$ where $R^{e,f}$ of lower degree in
$w_{l_{1}}$. Similarly this hold for a linear combination of elements at lever
$h$. This is sufficient since relative rank can only decrease when restricting
to a subspace. So we just need to make sure that the original relative rank
beats the new number of polynomials at each level which is $\leq m^{O(d)}$.

∎

We formulate a number of additional results, that were proved in the context
of high rank collections of polynomials, and whose proofs can be easily
adapted to the new notion of relative rank.

We recall the definition of weakly polynomial function from [15]

######  Definition A.6.

  1. (1)

Let $V$ be a $\mathbb{F}$-vector space and $X\subset V$. We say that a
function $f:X\to\mathbb{F}$ is weakly polynomial of degree $\leq a$ if the
restriction $f_{|L}$ to any affine subspace $L\subset X$ is a polynomial of
degree $\leq a$.

  2. (2)

$X$ satisfies $\star^{a}$ if any weakly polynomial function of degree $\leq a$
on $X$ is a restriction of a polynomial function of degree $\leq a$ on $V$.

######  Theorem A.7.

For any $d,a\geq 1$ there exist constants $A(d,h,a),B(d,h,a)$ such that the
following holds: For any field $\mathbb{F}$ which is either finite with
$|\mathbb{F}|>ad$ or algebraically closed of characteristic zero or $>d$, a
$\mathbb{F}$-vector space $V$, an $(A,B,2)$-regular tower $\mathcal{P}$ of
degree $\leq d$ and height $\leq h,$ the subset $Z(\mathcal{P})\subset V$ has
the property $\star_{a}$.

Combined with the polynomial cost regularization of theorem 2.3 we obtain:

######  Theorem A.8.

For any $d,a\geq 1$ there exists $A=A(d,a)$ such the following holds: for any
field $\mathbb{F}$ which is either finite with $|\mathbb{F}|>ad$ or
algebraically closed of characteristic zero or $>d$, a $\mathbb{F}$-vector
space $V$, a collection of polynomials $\bar{P}=(P_{i})_{1\leq i\leq c}$ with
$\deg P_{i}\leq d$, there exists a collection of polynomials $\mathcal{Q}$
such that $\bar{P}\subset\mathcal{I}(\mathcal{Q})$ such that
$Z(\mathcal{Q})\subset V$ has the property $\star_{a}$, and $|\mathcal{Q}|\leq
Ac^{A}$.

Finally we can also adapt the results from [17] to the setting of relative
rank: Let $V$ be a vector space over a field $\mathbb{F}$. An $m$-cube in a
vector space $V$ is a collection $(u|\bar{v}),u\in V,\bar{v}\in V^{m}$ of
$2^{m}$ points $\\{u+\sum_{i=1}^{m}\omega_{i}v_{i}\\}$,
$\omega_{i}\in\\{0,1\\}$.

For any map $f:V\to H$ where $H$ is an abelian group we denote by $f_{m}$ the
map from the set $C_{m}(V)$ of $m$-cubes to $H$ given by

$f_{m}(u|\bar{v})=\sum_{\bar{\omega}\in\\{0,1\\}^{m}}(-1)^{|w|}f(u+\sum_{i=1}^{m}\omega_{i}v_{i})$

where $|\omega|=\sum_{i=1}^{m}\omega_{i}$. For a subset $X\subset V$ we denote
$C_{m}(X)$ the set of $m$-cubes in $V$ with all vertices in $X$. Note that in
the case that $H=\mathbb{F}$, where $\mathbb{F}$ a prime field, functions
$f:V\to\mathbb{F}$ such that $f_{m}$ vanishes on $C_{m}(V)$ are precisely
polynomials of degree $<m$.

######  Theorem A.9.

Let $m,d>0$. There exists $C=C(d,m,h)$ such that the following holds: For any
$0<\epsilon$, a finite field $\mathbb{F}$ and an $\mathbb{F}$-vector space
$V$, a $(C,C,2)$-regular tower $\mathcal{P}$ of degree $\leq d$ and height
$\leq h$ and any $f:X=Z(\mathcal{P})\to H$ with $f_{m}(c)=0$ for
$\epsilon$-a.e. $c\in C_{m}(X)$, there exists a function $h:X\to H$ such that
$h_{m}\equiv 0$, and $h(x)=f(x)$ on $C\epsilon$-a.e. $x\in X$.

## References

  * [1] Adiprasito, K. , Kazhdan, D., Ziegler, T On the Schmidt and analytic ranks for trilinear forms. arXiv:2102.03659 (2021).
  * [2] Ananyan, T., Hochster, M. Small subalgebras of polynomial rings and Stillman’s Conjecture. J. Amer. Math. Soc. 33 (2020), 291-309.
  * [3] Bhowmick A., Lovett S. Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory. ArXiv:1506.02047.
  * [4] Croot, E., Lev, V.P., Pach, P. Progression-free sets in ${\mathbb{Z}}_{4}^{n}$ are exponentially small. Ann. of Math., vol. 185, 331-337, (2017).
  * [5] Cohen, A., Moshkovitz, G. Structure vs. randomness for bilinear maps, to appear in the 53rd ACM Symposium on Theory of Computing (STOC 2021).
  * [6] Cook, B., Magyar, A. Diophantine equations in the primes. Inventiones mathematicae, 198 (3) 701-737, 2014.
  * [7] Dersken. H. The $G$-stable rank for tensors arxiv.org/abs/2002.08435.
  * [8] Hrushovski, E. The Elementary Theory of the Frobenius Automorphisms arXiv: 0406514.
  * [9] Ellenberg, J, Gijswijt, D. On large subsets of $\mathbb{F}_{q}^{n}$ with no three-term arithmetic progression. Ann. of Math., vol. 185, 339-343, (2017).
  * [10] Green, B., Tao, T. The distribution of polynomials over finite fields, with applications to the Gowers norms. Contrib. Discrete Math, 4(2):1-36, 2009.
  * [11] Gowers, T, Wolf, J. Linear Forms and Higher-Degree Uniformity for Functions On $\mathbb{F}_{p}^{n}$. Geom. Funct. Anal. 21, 36-69 (2011).
  * [12] Janzer, O. Polynomial bound for the partition rank vs the analytic rank of tensors Discrete Analysis 2020:7.
  * [13] Kaufman, T., Lovett, S.Worst case to average case reductions for polynomials. Proc. 49th Annual IEEE Symposium on Foundations of Computer Science (2008),166-175.
  * [14] Kazhdan, D., Ziegler, T. Approximate cohomology. Selecta Math. (N.S.) 24 (2018), no. 1, 499 - 509.
  * [15] Kazhdan, D.,Ziegler, T. Properties of high rank subvarieties of affine spaces, Geom. Funct. Anal. 30 (2020), 1063-1096.
  * [16] Kazhdan, D., Ziegler, T. Applications of algebraic combinatorics to algebraic geometry, arXiv:2005.12542 (2020).
  * [17] Kazhdan, D., Ziegler, T. Polynomials as splines Sel. Math. New Ser. (2019) 25: 31.
  * [18] Kronecker, L. Algebraische Reduction der Scharen bilinearer Formen, Sitzungsber. Akad. Berlin, Jbuch. 22 (169) (1890) 1225-1237.
  * [19] Lovett, S. The Analytic rank of tensors and its applications. Discrete Analysis 2019:7
  * [20] F. S. Macaulay, _The algebraic theory of modular systems_ , Cambridge University, 1916.
  * [21] Milićević, L. Polynomial bound for partition rank in terms of analytic rank Geom. Funct. Anal. 29 (2019), no. 5, 1503-1530.
  * [22] Naslund, E. The partition rank of a tensor andk-right corners in $\mathbb{F}^{n}_{q}$. arXiv:1701.04475. (2017)
  * [23] Schmidt, W. M. The density of integer points on homogeneous varieties. Acta Math. 154 (1985), no. 3-4, 243-296.
  * [24] Tao, T. A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound. terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev-pach-ellenberg-gijswijt-capset-bound/
  * [25] Wooley, T. An explicit version of Birch’s Theorem. Acta Arithmetica, 85(1), (1998) 79-96.
  * [26] Lovett, S. The analytic rank of tensors and its applications. Discrete Analysis 2019:7, 10 pp.