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

$$\begin{align*}rk_{{\mathcal Q}_{<i}}({\mathcal Q}_i)>A'(s+H+m_i+2)^{B'}. \end{align*}$$

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

$$\begin{align*}bias_{Z({\mathcal Q}_{<i})} (a\cdot {\mathcal Q}_i) < q^{-(s+H+m_i+1)}. \end{align*}$$

Fourier analysis yields

$$\begin{align*}q^{m_i}\frac{|Z({\mathcal Q}_{\le 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, \end{align*}$$

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

$$\begin{align*}\frac{|Z({\mathcal Q})|}{|V^{[k]}|} = \prod_{i\in[H+1]}\frac{|Z({\mathcal Q}_{\le i})|}{|Z({\mathcal Q}_{<i})|} = \prod_{i\in[H+1]} (1+e_i) q^{-m_i} = (1+e)q^{-m}, \end{align*}$$

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

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

We are interested in the regularity of ${\mathcal Q}(y),$ which is, by definition, the regularity of its associated multilinear 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 multilinear 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}'$ have the same associated multilinear variety (and hence the same regularity),

2. 2. $Z({\mathcal Q}')_I = Z({\mathcal Q})_I$ , and

3. 3. for any $y\in Z({\mathcal Q})_I,$ the multilinear tower associated with ${\mathcal Q}(y)$ is ${\mathcal Q}'(y).$

So after replacing ${\mathcal Q}$ with ${\mathcal Q}'$ , we can assume without loss of generality that ${\mathcal Q}(y)$ is a multilinear tower for any $y\in Z({\mathcal Q}_I).$ Write $X=Z({\mathcal Q})$ for short. Let $ A',B' $ be the constants of Lemma 3.3 at height $H.$ We deal separately with two cases.

The first case (and the easier one) is when $I_{H+1}\subset I.$ In this case, for any $y\in (X_I)_{<H+1}$ , we have ${\mathcal Q}(y) = {\mathcal Q}_{<H+1}(y).$ For $A = 2^{B'}A'$ , $B=B',$ we get that ${\mathcal Q}_{<H+1}$ is $(A',B',s+m_{H+1}+1)$ -regular. Then by the inductive hypothesis, we have that for $q^{-(s+m_{H+1}+1)}$ a.e. $y\in (X_I)_{<H+1}$ , the tower ${\mathcal Q}(y)={\mathcal Q}_{<H+1}(y)$ is $(C,D,s)$ -regular. By Lemma 3.2, we know that if $A,B$ are sufficiently large, then $\frac {|(X_I)_{<H+1}|}{|X_I|} \le q^{m_{H+1}+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+1} \not \subset I.$ In this case, we have $X_I = (X_I)_{<H+1}.$ If $A,B$ are sufficiently large, then ${\mathcal Q}$ is $(A',B',100C(m_{H+1}+s)^D)$ -regular. Let

$$\begin{align*}s' = 100C(m_{H+1}+s)^D\ , \ \varepsilon = q^{-s'}. \end{align*}$$

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

$$\begin{align*}rk_{{\mathcal Q}_{<H+1}(y)} \left( {\mathcal Q}_{H+1}(y) \right)>C(m_{H+1}+s)^D. \end{align*}$$

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

$$\begin{align*}Re \left[ {\mathbb E}_{x\in X_{<H+1}} \chi(a\cdot {\mathcal Q}_{H+1}(x)) \right] \le \varepsilon. \end{align*}$$

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

$$\begin{align*}\left| {\mathbb E}_{z\in X_{<H+1}(y)}\chi(Q(y,z)) \right| \le Re \left[ {\mathbb E}_{z\in X_{<H+1}(y)}\chi(Q(y,z)) \right] + \varepsilon. \end{align*}$$

Therefore,

$$\begin{align*}{\mathbb E}_{y\in X_I} |{\mathbb E}_{z\in X_{<H+1}(y)}\chi(Q(y,z))| < 4\varepsilon. \end{align*}$$

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

$$\begin{align*}|{\mathbb E}_{z\in X_{<H+1}(y)}\chi(Q(y,z))| < 2\sqrt{\varepsilon}. \end{align*}$$

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

$$\begin{align*}q^{-r(y)} < 4\sqrt{\varepsilon} < q^{-C(m_{H+1}+s)^D}, \end{align*}$$

which implies $r_a(y)>C(m_{H+1}+s)^D.$ Running over all $0\neq a\in {\mathbb {F}}^{m_{H+1}},$ we get that for $3\sqrt {\varepsilon }q^{m_{H+1}}\le q^{-(s+1)}$ -a.e. $y\in X_I$ , we have $ r(y)> C(m_{H+1}+s)^D$ , where $ r(y) = \max _{0\neq a\in {\mathbb {F}}^{m_{H+1}}} r_a(y). $ This completes the proof.

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

By the triangle inequality,

$$\begin{align*}\left| {\mathbb E}_{x\in X}g(x) - {\mathbb E}_{y\in X _I}{\mathbb E}_{z\in X(y)}g(y,z) \right| \le {\mathbb E}_{y\in X _I} \left| \frac{|X _I|\cdot |X(y)|}{|X|} - 1 \right|. \end{align*}$$

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) \ge 0$ for all $y\in X _I, $

2. 2. $ {\mathbb E}_{y\in X _I} f(y) = 1 $ , and

3. 3. by Lemmas 3.3(d,H+1,l+1) and 3.2(d,H+1,l+1), 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 \le \rho \le 1 $ ). Then

(3.1) $$ \begin{align} {\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|. \end{align} $$

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

$$\begin{align*}(1-\rho) {\mathbb E}_{y\in E^c} |f(y)-1| \le \varepsilon + (1-\rho) {\mathbb E}_{y\in E^c} f(y). \end{align*}$$

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

$$\begin{align*}{\mathbb E}_{y\in X _I} |f(y)-1| \le 4\varepsilon \le q^{-s}.\\[-42pt] \end{align*}$$

Proof of Lemma 3.5 rank-bias(d,H+1,l+1).

Let $X = Z({\mathcal Q}). $ First we apply Lemma 3.4(d,H+1,l+1) to get

1. 1. $Re[{\mathbb E}_{x\in X} \chi (P(x))] \ge Re[{\mathbb E}_{x\in X_I} \chi (P(x))]-q^{-2s} $ and

2. 2. $|Im[{\mathbb E}_{x\in X} \chi (P(x))]| \le |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

$$\begin{align*}|Im[{\mathbb E}_{x\in X} \chi(P(x))]| \le {\mathbb E}_{y\in X_1}|Im[{\mathbb E}_{z\in X(y)} \chi(P(y,z))]|+q^{-10s}. \end{align*}$$

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

$$\begin{align*}{\mathbb E}_{y\in X_1}|Im[{\mathbb E}_{z\in X(y)} \chi(P(y,z))]| \le q^{-5s}, \end{align*}$$

as desired.

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

$$\begin{align*}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}), \end{align*}$$

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,

$$ \begin{align*} &Re[{\mathbb E}_{x\in X} \chi(P(x))] \ge {\mathbb E}_{y\in X_1}Re[{\mathbb E}_{z\in X(y)} \chi(P(y,z))]-q^{-10s} \\ &\qquad = \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}. \end{align*} $$

Note that:

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

2. 2. $|W|/|X_1| \ge q^{-m}$ , and

3. 3. for $q^{-10s}$ -a.e. $y\in X_1$ , the multilinear tower ${\mathcal Q}(y)$ is $(A',B',10s)$ -regular.

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

$$\begin{align*}\frac{|W|}{|X_1|}{\mathbb E}_{y\in W}Re[{\mathbb E}_{z\in X(y)} \chi(P(y,z))] \ge q^{-r}-q^{-5s}, \end{align*}$$

and the second summand by

$$\begin{align*}(1-\frac{|W|}{|X_1|}){\mathbb E}_{y\in X_1\setminus W}Re[{\mathbb E}_{z\in X(y)} \chi(P(y,z))] \ge -q^{-5s}.\\[-42pt] \end{align*}$$

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 multiaffine map of degree $ \le d+1, $ with $ bias_{Z({\mathcal Q})} (P) \ge 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

$$\begin{align*}| {\mathbb E}_{x\in X_I} \chi(P(x)) | \ge q^{-2s}, \end{align*}$$

that is, we can assume without loss of generality that $ I=[k]. $ If $ {\mathcal Q} $ is of degree $ \le 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

(4.1) $$ \begin{align} |{\mathbb E}_{x\in X} \chi(P(x))| \le \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)) |. \end{align} $$

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} \le 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 subadditivity of relative partition rank, for any $ b\neq a \in {\mathbb {F}}^{m_t}$ , we must have

$$\begin{align*}prk_{{\mathcal Q}_{\neq t}} ( P(x)+a\cdot {\mathcal Q}_t(x) ) \ge \frac{A}{2}(m_t+s)^B. \end{align*}$$

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}, $

$$\begin{align*}| {\mathbb E}_{x\in X_{\neq t}}\chi(P(x)+a\cdot {\mathcal Q}_t(x)) | \le q^{-m_t-4s}. \end{align*}$$

Plugging these estimates into inequality (4.1) yields

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

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

$$\begin{align*}prk_{\mathcal Q} (P(x)) \le prk_{{\mathcal Q}_{\neq t}} ( P(x)+b\cdot {\mathcal Q}_t(x) ) \le A(1+s)^B.\\[-37pt] \end{align*}$$

Proof. By applying Lemma 3.4, we get

$$\begin{align*}|{\mathbb E}_{x\in X} \chi(P(x))| \le |{\mathbb E}_{x\in X_I} \chi(P(x))| + q^{-2s}, \end{align*}$$

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 multiaffine maps. Again, using Lemma 3.4 twice, we have

$$ \begin{align*} |{\mathbb E}_{x\in X} \chi(P(x))| &\le |{\mathbb E}_{x\in X_{I\setminus\{i\}}} \chi(b(x)) {\mathbb E}_{y\in X(x)} \chi(A(x)\cdot y)| + q^{-10ks} \\ &\qquad\qquad\quad\le {\mathbb E}_{x\in X_{I\setminus\{i\}}} |{\mathbb E}_{y\in X(x)} \chi(A(x)\cdot y)| + q^{-10ks} \\ &\qquad\qquad\quad={\mathbb E}_{x\in X_{I\setminus\{i\}}} {\mathbb E}_{y\in \widetilde{X(x)}} \chi(A(x)\cdot y) + q^{-10ks} \\ &\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\le |{\mathbb E}_{x\in X'} \chi(A(x_{[k]\setminus\{i\}})\cdot x_i)|+ q^{-5ks}, \end{align*} $$

where $X'$ 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 multiaffine 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

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

where the second inequality follows from Lemma 3.5.

Proof. We may assume without loss of generality that $ {\mathcal Q} $ is multilinear. Because there are $ l_1\ldots l_k $ times as many maps, it is enough to show that the relative ranks are unchanged. Suppose we have a linear combination with

$$\begin{align*}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). \end{align*}$$

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

$$\begin{align*}rk_{{\mathcal Q}_{<i}} ( a_{\textbf{j}}\cdot {\mathcal Q}_i ) < rk_{{\mathcal Q}_{<i}} ({\mathcal Q}_i), \end{align*}$$

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

Proof. Choosing a nondegenerate bilinear form on $V^{d+1},$ we can write $P(x) = A(x_{[d]})\cdot x_{d+1},$ where $A:V^{[d]}\to V^{d+1}$ is multilinear. Apply Lemma 3.4 to get

(5.1) $$ \begin{align} q^{-2s} \le {\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], \end{align} $$

where $v\perp w$ means $v\cdot w =0.$ 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

$$\begin{align*}\phi_t(x_{[d]}) = (A(x_{[d]})\cdot t_1,\ldots, A(x_{[d]})\cdot t_l). \end{align*}$$

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

$$\begin{align*}\mathbb P_{t\in X(x_{[d]})^l} (\phi_t(x) = 0) = q^{-l}. \end{align*}$$

Therefore,

$$\begin{align*}{\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} \le q^{-l}. \end{align*}$$

If $ A,B $ are sufficiently large, then by Claim 5.1 and Lemma 3.4, we have

$$\begin{align*}{\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} \le q^{-l}+q^{-100s} \le q^{-50s}. \end{align*}$$

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

(5.2) $$ \begin{align} {\mathbb E}_{x\in X_t} 1_{A(x_{[d]})\not\perp X(x_{[d]})} 1_{\phi_t(x) = 0} \le q^{-25s}. \end{align} $$

Also, by Lemma 3.4 together with inequality (5.1)

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

Markov’s inequality gives us

$$\begin{align*}\mathbb P_{t\in X_{d+1}^l} \left[ {\mathbb E}_{x\in X_t} 1_{A(x_{[d]}) \perp X(x_{[d]})} \ge q^{-5s}\right] \ge q^{-5s}. \end{align*}$$

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

$$\begin{align*}{\mathbb E}_{x\in X_t} 1_{A(x_{[d]}) \perp X(x_{[d]})} \ge q^{-5s} \end{align*}$$

and inequality (5.2). For these t, we have

$$ \begin{align*} &{\mathbb P}_{x\in X_t\cap \{\phi_t(x_{[d]})=0\}} (P(x) = 0) \ge \mathbb P_{x\in X_t} (A(x_{[d]}) \perp X(x_{[d]}) | \phi_t(x)=0) \\ &\qquad\qquad\quad= \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)} \\ &\qquad\qquad\qquad\qquad \ \ge \frac{q^{-5s}}{q^{-5s}+\mathbb P_{x\in X_t} (A(x_{[d]})\not \perp X(x_{[d]}) ,\phi_t(x)=0)} \ge \frac{q^{-5s}}{q^{-5s}+q^{-25s}} \ge 1-q^{-s}. \end{align*} $$

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 $

$$\begin{align*}rk_{{\mathcal Q}\cup\mathcal R_{<i}} (\mathcal R_i)>A(n_i+s)^B, \end{align*}$$

then we stop. Otherwise, there is some $0\neq a\in {\mathbb {F}}^{m_i} $ , such that

$$\begin{align*}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}), \end{align*}$$

where $t \le A(n_i+s)^B.$ Assume without loss of generality that $ a_{m_i} \neq 0. $ Let $ \mathcal R' $ be the tower obtained from $ \mathcal R $ by deleting $ R_{i,m_i}. $ In $Z({\mathcal Q}\cup \mathcal R'),$ 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'$ and call the new tower $\mathcal R".$ We can then split

$$\begin{align*}Z({\mathcal Q}\cup\mathcal R) = \bigsqcup_{i=1}^c \left( Z({\mathcal Q}) \cap \{\mathcal R"=b_i\} \right) , \end{align*}$$

where $ b_1,\ldots ,b_c \in {\mathbb {F}}^{\mathcal R"}$ are the values causing the maps in $ \mathcal R $ to vanish on $ Z({\mathcal Q}) \cap \{\mathcal R"=b_i\}. $ Now we do the same thing for each of the towers $ \mathcal R"-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

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

We prove inductively that the total number of polynomials passing through layer i and above during this process is $\le 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 multilinear, then we can take $ b_1 = 0 $ at every stage, leaving us with $ \mathcal S_1 $ multilinear.

Proof. As usual, let $ \tilde {{\mathcal Q}} $ denote the multilinear tower corresponding to $ {\mathcal Q}. $ The multilinear 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 multilinear 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 without loss of generality that $ Q:V^{[e]}\to {\mathbb {F}}, $ and suppose (to get a contradiction) that we have a nontrivial linear combination

(7.1) $$ \begin{align} \sum_{\omega\in\{0,1\}^l,0<|\omega|\le e} a_\omega Q(\omega\cdot t) = 0. \end{align} $$

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 (7.1) is $ a_{\omega _0} \neq 0, $ contradiction. Now we turn to the second part of the lemma. Since invertible affine transformations do not affect regularity, the variety

$$\begin{align*}\{(t_1,\ldots,t_l): (t_1-\ldots-t_c,t_2,\ldots,t_l)\in X_{x,l}\} \end{align*}$$

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 is a tower on

$$\begin{align*}V_1\times\ldots\times V_1\times\ldots\times V_{d+1}\times\ldots\times V_{d+1}. \end{align*}$$

Then, by Lemma 3.3, we get that for $ q^{-s} $ -a.e. $ t_1\in X-x $ the variety

$$\begin{align*}\{(t_2,\ldots,t_l): (t_1-\ldots-t_c,t_2,\ldots,t_l)\in X_{x,l}\} \end{align*}$$

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

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 $ \le d+1, $ for any $ t_1,\ldots ,t_{d+2}\in V^{[d+1]} $ , we have

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

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 is enough to show the following bound for any fixed $0\neq \omega \in \{0,1\}^{d+2}$

$$\begin{align*}{\mathbb E}_{t\in X_{x,d+2} } 1_B (x+\omega\cdot t) \le 2^{-(d+2)}. \end{align*}$$

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

$$\begin{align*}{\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). \end{align*}$$

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

$$\begin{align*}{\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) \le {\mathbb E}_{t_1\in X-x}1_B (x+t_1)+q^{-s} \le q^{1-s}. \end{align*}$$

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

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 multilinearity,

$$\begin{align*}f(x,\cdot) \restriction _{(Z\cap Z_1)(x)+(Z\cap Z_2)(x)} = 0. \end{align*}$$

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

$$\begin{align*}(Z\cap Z_1)(x)+(Z\cap Z_2)(x) = Z(x). \end{align*}$$

By Lemma 3.4,

$$\begin{align*}\mathbb P_{ \{x\in Z\ :\ x_{[d+1] \setminus \{i\}} \in (Z_1\cap Z_2)_{[d+1] \setminus \{i\}} \} } (f(x) = 0) \ge 1-q^{-s}. \end{align*}$$

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

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

$$\begin{align*}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. \end{align*}$$

Then apply the inductive hypothesis to

$$\begin{align*}{\mathcal Q}, (\mathcal G_1\cup \mathcal G_2) _ {[l]},\ldots, (\mathcal G_{2^{l+1}-1}\cup \mathcal G_{2^{l+1}}) _ {[l]}.\\[-37pt] \end{align*}$$

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}) \le F(1+s)^G $ for some constants $F(A,B,d),G(A,B,d)$ , and such that

$$\begin{align*}X_{t_i}\cap Y_i = \bigsqcup_{j=1}^l (X_{t_i}\cap Y_{i,j}), \end{align*}$$

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} \ge 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.

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

$$\begin{align*}(x_K , z_{I\setminus K}) , (y_K , z_{I\setminus K}) \in X(y_{[d+1] \setminus I }). \end{align*}$$

Take the following variety

$$\begin{align*}Y = \left\lbrace (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\rbrace. \end{align*}$$

The equations defining it are partial to those of $ {\mathcal Q}^{\times 3}, $ so by Claim 5.1, we have $ Y=Z(\mathcal G) $ for a $ (C,D,s) $ -regular tower of degree $ \le d $ and height $ \le 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_{\ge I}), $ the variety $ Y(x,y) $ (which is composed of the $ z'$ s we want) is $ (C',D',s) $ -regular. In particular, by Lemma 3.2, it is nonempty.

Proof of corollary.

By Theorem 8.3, $ rk_{{\mathcal Q}_1\cup {\mathcal Q}_2} (R_1-R_2) = 0. $ Therefore, there exist multilinear 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 the degree of $ {\mathcal Q}, $ and then on the number of layers of maximal degree. 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}' = {\mathcal Q}\setminus \{Q_0\}. $ Apply Lemma 8.2 to the variety $X = Z({\mathcal Q}')\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_{\ge I}) $ and such that $ {\mathcal Q} \cup {\mathcal Q}(\textbf {x}_{\ge I})$ is $ (C,D,s) $ -regular, where $ {\mathcal Q}(\textbf {x}_{\ge I}) := \bigcup _{j=1}^{2^{d+1}} {\mathcal Q}(x^j_{\ge 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}'\cup {\mathcal Q}(x^j_{\ge I}) $ , and define $ R^j(y_{[d+1]\setminus I}) = P(x^j_I,y_{[d+1]\setminus I}). $ We claim that

$$\begin{align*}\mathbb P_{y\in Z({\mathcal Q}^j)} [P(y) = R^j(y_{[d+1]\setminus I})Q_0(y_I)] \ge 1-q^{-s}. \end{align*}$$

Note that

$$\begin{align*}Z({\mathcal Q}^j) = \bigsqcup_{a\in{\mathbb{F}}} Z({\mathcal Q}^j)\cap \{Q_0 = a\}, \end{align*}$$

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

$$\begin{align*}\mathbb P_{y\in Z({\mathcal Q}^j) \cap \{Q_0 = 1\}} [P(y) = R^j(y_{[d+1]\setminus I})Q(y_I)] \ge 1-q^{-s}. \end{align*}$$

Recall that by our definitions, $ Z({\mathcal Q}^j) \cap \{Q_0 = 1\} = X\cap X(x^j_{\ge I}). $ Now, for any $ y\in X\cap X(x^j_{\ge 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 do not change, because the difference of the two points is in $Z({\mathcal Q}). $ This means that

$$\begin{align*}\mathbb P_{y\in X\cap X(x^j_{\ge I})} [P(y) = R^j(y_{[d+1]\setminus I})Q_0(y_I)] \ge 1-q^{-s} \end{align*}$$

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.

Applying the above claim with $ \mathcal F = {\mathcal Q}' $ and $ \mathcal G^j = {\mathcal Q}(x^j_{\ge I}) $ (note that the equations coming from $ x^j_{\ge I} $ are of deg $ < |I|, $ so the induction hypothesis applies to $ {\mathcal Q}'\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}'). $ By the inductive hypothesis, $ rk_{{\mathcal Q}'} \left ( P(y) - R(y_{[d+1]\setminus I})Q(y_I) \right ) = 0 $ , and this completes the inductive step.

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} \le 2^k $ polynomials in $ {\mathcal Q}(k), $ so we just need to check that

$$\begin{align*}prk_{ \bar{{\mathcal Q}}_{<i} } (\bar{{\mathcal Q}}_i) \ge rk_{{\mathcal Q}_{<i}} ({\mathcal Q}_i). \end{align*}$$

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

$$\begin{align*}prk_{ \bar{{\mathcal Q}}_{<i} } (\bar{{\mathcal Q}}_i) \le 2^k rk_{{\mathcal Q}_{<i}} ({\mathcal Q}_i). \end{align*}$$

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

Proof. Identical to that of Lemma 3.2.

Proof. By Claim 9.3, it is 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}' = ({\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}'(t_1,\ldots ,t_k) $ is $ (C,D,s) $ -regular. $ {\mathcal Q}'(t_1,\ldots ,t_k) = ({\mathcal Q}_{t_1}\cup \ldots \cup {\mathcal Q}_{t_k} )(d), $ so we are done.

Proof. Identical to the proof of Lemma 3.4.

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

$$ \begin{align*} | {\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}} &\le | {\mathbb E}_{t\in Z({\mathcal Q}(1))} {\mathbb E}_{x\in Z({\mathcal Q}_t)} D_t f(x) |^{2^{k-1}} + q^{-4s} \\ &\qquad\quad \ \le {\mathbb E}_{t\in Z({\mathcal Q}(1))} |{\mathbb E}_{x\in Z({\mathcal Q}_t)} D_t f(x)|^{2^{k-1}} + q^{-4s}. \end{align*} $$

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

$$ \begin{align*} {\mathbb E}_{t\in Z({\mathcal Q}(1))} |{\mathbb E}_{x\in Z({\mathcal Q}_t)} D_t f(x)|^{2^{k-1}} &\\ &\le 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)} D_sD_t f(x) \right) +q^{-2s}. \end{align*} $$

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

$$ \begin{align*} &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)})} D_sD_t f(x) \right) \\ &\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\le Re \left( {\mathbb E}_{t\in Z({\mathcal Q}(k))}{\mathbb E}_{x\in Z({\mathcal Q}_t)} D_{t_1}\ldots D_{t_k} f(x) \right) + q^{-2s}, \end{align*} $$

which completes the inductive step.

Proof. When $ \deg (P) \le d $ , we are already assuming this holds, so we deal with the case $ \deg (P) =d+1. $ If $ bias_{Z({\mathcal Q})} (P) \ge q^{-s} $ , then by Lemma 9.8, we get that $ bias_{Z({\mathcal Q}(d+1))} (\bar P) \ge 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) \le A(1+s)^B. $ Plugging in the diagonal, we get that $ rk_{\mathcal Q} (P) \le A(1+s)^B. $

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

$$\begin{align*}\sum_{a\in{\mathbb{F}}^{m_H}} bias_{Z({\mathcal Q}_{<H})} (P+a\cdot {\mathcal Q}_H) \ge q^{-2s}. \end{align*}$$

By subadditivity 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) \le 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, $

$$\begin{align*}bias_{Z({\mathcal Q}_{<H})} (P+a\cdot {\mathcal Q}_H) \le q^{-4s-m_H}, \end{align*}$$

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

$$\begin{align*}rk_{\mathcal Q} (P) \le rk_{Z({\mathcal Q}_{<H})}(P+a_0\cdot {\mathcal Q}_H) \le A(1+s)^B.\\[-38pt] \end{align*}$$

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 3.4 and 9.8, $ \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' = P-\sum R_{i,j} Q_{i,j} $ has $ \deg (P') \le k-1 $ and also vanishes $ q^{-s} $ -a.e. on $ Z({\mathcal Q}). $ Applying the inductive hypothesis finishes the proof.