$\tilde{\gamma}_{0}\in\text{poly}(V_{p}(\tilde{M})\to(G_{2})_{\mathbb{N}}|(\Gamma\cap
G_{2}))$. Writing $\tilde{h}(n):=\tilde{g}(n)\tilde{\gamma}_{0}(n)^{-1}$, we
have that
$\tilde{h}\in\text{poly}_{p}(V_{p}(\tilde{M})\to(G_{2})_{\mathbb{N}}|(\Gamma\cap
G_{2}))$. Note that for all $n,h_{1},h_{2}\in\mathbb{Z}^{d}$,

(8.39)
$\begin{split}&\quad\Delta_{h_{2}}\Delta_{h_{1}}(\eta_{2}\circ\tilde{g}(n))=\eta_{2}\circ(\Delta_{h_{2}}\Delta_{h_{1}}\tilde{g})(n)=\eta_{2}\circ(\Delta_{h_{2}}\Delta_{h_{1}}\tilde{g}_{\text{nlin}})(n)\\\
&=\Delta_{h_{2}}\Delta_{h_{1}}(\eta_{2}\circ\tilde{g}_{\text{nlin}})(n)=\Delta_{h_{2}}\Delta_{h_{1}}(\frac{1}{q}Q_{2}(n)+T(n))=\Delta_{h_{2}}\Delta_{h_{1}}(\frac{1}{q}Q_{2}(n)).\end{split}$

By Lemma 8.2, we have that $p^{\lfloor s/2\rfloor}\eta_{2}\circ\tilde{g}$ and
thus $p^{\lfloor
s/2\rfloor}\Delta_{h_{2}}\Delta_{h_{1}}(\frac{1}{q}Q_{2}(\cdot))$ takes values
in $\mathbb{Z}$. By (8.39), we have that

(8.40)
$\begin{split}&\quad\Delta_{h_{2}}\Delta_{h_{1}}(\eta_{2}\circ\tilde{h}(n))=\Delta_{h_{2}}\Delta_{h_{1}}(\eta_{2}\circ\tilde{g}(n))-\Delta_{h_{2}}\Delta_{h_{1}}(\eta_{2}\circ\tilde{\gamma}_{0}(n))=(1-q^{\ast}qq^{\prime})\Delta_{h_{2}}\Delta_{h_{1}}(\frac{1}{q}Q_{2}(n)).\end{split}$

So $\Delta_{h_{2}}\Delta_{h_{1}}(\eta_{2}\circ\tilde{h}(\cdot))$ is integer
valued. By Proposition 3.25, there exists
$\tilde{\gamma}^{\prime}\in\text{poly}(\mathbb{Z}^{d}\to
G_{\mathbb{N}}|\Gamma)$ such that

(8.41)
$\begin{split}\Delta_{h_{2}}\Delta_{h_{1}}(\eta_{2}\circ\tilde{h}(n))=\Delta_{h_{2}}\Delta_{h_{1}}(\eta_{2}\circ\tilde{\gamma}^{\prime}(n))\end{split}$

for all $n,h_{1},h_{2}\in\mathbb{Z}^{d}$.

Set $\tilde{\gamma}:=\tilde{\gamma}_{0}\tilde{\gamma}^{\prime}$ and
$\tilde{g}^{\prime}:=\tilde{g}\tilde{\gamma}^{-1}=\tilde{g}_{\text{nlin}}\tilde{g}_{\text{lin}}\tilde{\gamma}^{-1}$.
Since
$\tilde{\gamma}_{0}\in\text{poly}(V_{p}(\tilde{M})\to(G_{2})_{\mathbb{N}}|(\Gamma\cap
G_{2}))$ and $\tilde{\gamma}^{\prime}$ takes values in $\Gamma$, we have that
$\tilde{\gamma}\in\text{poly}(V_{p}(\tilde{M})\to G_{\mathbb{N}}|\Gamma).$ It
is clear that $\tilde{g}^{\prime}\in\text{poly}(\mathbb{Z}^{d}\to
G_{\mathbb{N}})$. Moreover, by (8.40) and (8.41),

$\Delta_{h_{2}}\Delta_{h_{1}}(\eta_{2}\circ\tilde{g}^{\prime})(n)=\eta_{2}(\Delta_{h_{2}}\Delta_{h_{1}}\tilde{g}^{\prime}(n))=0$

for all $n,h_{1},h_{2}\in\mathbb{Z}^{d}$. So it is not hard to see that
$\tilde{g}^{\prime}$ belongs to $\text{poly}(\mathbb{Z}^{d}\to
G^{\prime}_{\mathbb{N}})$. Finally, for all for all
$n,n^{\prime}\in\mathbb{Z}^{d}$ with $\tilde{M}(n)\in\mathbb{Z}$, we have that

$\tilde{g}^{\prime}(n+pn^{\prime})^{-1}\tilde{g}^{\prime}(n)=\tilde{\gamma}(n+pn^{\prime})\tilde{g}(n+pn^{\prime})^{-1}\tilde{g}(n)\tilde{\gamma}(n)^{-1}.$

Since all of $\tilde{\gamma}(n+pn^{\prime})$,
$\tilde{g}(n+pn^{\prime})^{-1}\tilde{g}(n)$ and $\tilde{\gamma}(n)^{-1}$
belong to $\Gamma$, we have that
$\tilde{g}^{\prime}(n+pn^{\prime})^{-1}\tilde{g}^{\prime}(n)\in\Gamma$.
Therefore, we have that
$\tilde{g}^{\prime}\in\text{poly}_{p}(V_{p}(\tilde{M})\to
G^{\prime}_{\mathbb{N}}|\Gamma)$. ∎

##  9\. Sets and equations generated by quadratic forms

###  9.1. $M$-sets

Our next goal is to extend Theorem 5.1 from $V(M)$ to the intersection of the
zeros of many quadratic polynomials. When working with a subset of
$(\mathbb{F}_{p}^{d})^{k}$ or $(\mathbb{Z}^{d})^{k}$, it is convenient to
group the variables $(n_{1},\dots,n_{dk})$ into $k$ groups

$(n_{1},\dots,n_{d}),(n_{d+1},\dots,n_{2d}),\dots,(n_{d(k-1)+1},\dots,n_{k})$

and treat each tuple $(n_{d(j-1)+1},\dots,n_{j})$ as a single multi-
dimensional variable. To this end, we introduce some definitions reflecting
such a point of view.

We say that a linear transformation
$L\colon(\mathbb{F}_{p}^{d})^{k}\to(\mathbb{F}_{p}^{d})^{k^{\prime}}$ is _$d$
-integral_ if there exist $a_{i,j}\in\mathbb{F}_{p}$ for $1\leq i\leq k$ and
$1\leq j\leq k^{\prime}$ such that

$L(n_{1},\dots,n_{k})=\Bigl{(}\sum_{i=1}^{k}a_{i,1}n_{i},\dots,\sum_{i=1}^{k}a_{i,k^{\prime}}n_{i}\Bigr{)}$

for all $n_{1},\dots,n_{k}\in\mathbb{F}_{p}^{d}$. Let
$L\colon(\mathbb{F}_{p}^{d})^{k}\to\mathbb{F}_{p}^{d}$ be a $d$-integral
linear transformation given by $L(n_{1},\dots,n_{k})=\sum_{i=1}^{k}a_{i}n_{i}$
for some $a_{i}\in\mathbb{F}_{p},1\leq i\leq k$. We say that $L$ is the
$d$-integral linear transformation _induced_ by
$(a_{1},\dots,a_{k})\in\mathbb{F}_{p}^{k}$.

Similarly, we say that a linear transformation
$L\colon(\mathbb{Z}^{d})^{k}\to(\frac{1}{p}\mathbb{Z}^{d})^{k^{\prime}}$ is
_$d$ -integral_ if there exist $a_{i,j}\in\mathbb{Z}/p$ for $1\leq i\leq k$
and $1\leq j\leq k^{\prime}$ such that

$L(n_{1},\dots,n_{k})=\Bigl{(}\sum_{i=1}^{k}a_{i,1}n_{i},\dots,\sum_{i=1}^{k}a_{i,k^{\prime}}n_{i}\Bigr{)}$

for all $n_{1},\dots,n_{k}\in\mathbb{Z}^{d}$.

There is a natural correspondence between $d$-integral linear transformations
in $\mathbb{Z}/p$ and those in $\mathbb{F}_{p}$. The proof of the following
lemma is similar to the proof of Lemma A.1 and we omit the details:

######  Lemma 9.1.

Every $d$-integral linear transformation
$\tilde{L}\colon(\mathbb{Z}^{d})^{k}\to(\frac{1}{p}\mathbb{Z}^{d})^{k^{\prime}}$
induces a $d$-integral linear transformation
$L\colon(\mathbb{F}_{p}^{d})^{k}\to(\mathbb{F}_{p}^{d})^{k^{\prime}}$.
Conversely, every $d$-integral linear transformation
$L\colon(\mathbb{F}_{p}^{d})^{k}\to(\mathbb{F}_{p}^{d})^{k^{\prime}}$ admits a
regular lifting
$\tilde{L}\colon(\mathbb{Z}^{d})^{k}\to(\frac{1}{p}\mathbb{Z}^{d})^{k^{\prime}}$
which is a $d$-integral linear transformation.

Moreover, we have that $p\tilde{L}\circ\tau\equiv\tau\circ L\mod
p(\mathbb{Z}^{d})^{k^{\prime}}$.

Let $d\in\mathbb{N}_{+}$, $p$ be a prime,
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a quadratic form with $A$
being the associated matrix. We need to work with a large family of sets
generated by $M$. We say that a function
$F\colon(\mathbb{F}_{p}^{d})^{k}\to\mathbb{F}_{p}$ is an _$(M,k)$ -integral
quadratic function_ if

(9.1) $F(n_{1},\dots,n_{k})=\sum_{1\leq i\leq j\leq k}b_{i,j}(n_{i}A)\cdot
n_{j}+\sum_{1\leq i\leq k}v_{i}\cdot n_{i}+u$

for some $b_{i,j},u\in\mathbb{F}_{p}$ and $v_{i}\in\mathbb{F}_{p}^{d}$. We say
that an $(M,k)$-integral quadratic function $F$ is _pure_ if $F$ can be
written in the form of (9.1) with $v_{1}=\dots=v_{k}=\mathbb{0}$. We say that
an $(M,k)$-integral quadratic function
$F\colon(\mathbb{F}_{p}^{d})^{k}\to\mathbb{F}_{p}$ is _nice_ if

$F(n_{1},\dots,n_{k})=\sum_{1\leq i\leq k^{\prime}}b_{i}(n_{k^{\prime}}A)\cdot
n_{i}+u$

for some $0\leq k^{\prime}\leq k$, $b_{i},u\in\mathbb{F}_{p}$.

For $F$ given in (9.1), denote

$v_{M}(F):=(b_{k,k},b_{k,k-1},\dots,b_{k,1},v_{k},b_{k-1,k-1},\dots,b_{k-1,1},v_{k-1},\dots,b_{1,1},v_{1},u)\in\mathbb{F}_{p}^{\binom{k+1}{2}+kd+1},$

and

$v^{\prime}_{M}(F):=(b_{k,k},b_{k,k-1},\dots,b_{k,1},v_{k},b_{k-1,k-1},\dots,b_{k-1,1},v_{k-1},\dots,b_{1,1},v_{1})\in\mathbb{F}_{p}^{\binom{k+1}{2}+kd}.$

Informally, we say that $b_{i,j}$ is the $n_{i}n_{j}$-coefficient, $v_{i}$ is
the $n_{i}$-coefficient, and $u$ is the constant term coefficient for these
vectors.

######  Definition 9.2 (Different types of $(M,k)$-families).

An _$(M,k)$ -family_ is a collections of $(M,k)$-integral quadratic functions.
Let $\mathcal{J}=\\{F_{1},\dots,F_{r}\\}$ be an $(M,k)$-family.

  * •

We say that $\mathcal{J}$ is _pure_ if all of $F_{1},\dots,F_{r}$ are pure.

  * •

We say that $\mathcal{J}$ is _consistent_ if $(0,\dots,0,1)$ does not belong
to the span of $v_{M}(F_{1}),$ $\dots,$ $v_{M}(F_{r})$, or equivalently, there
is no linear combination of $F_{1},\dots,F_{r}$ which is a constant nonzero
function, or equivalently, for all $c_{1},\dots,c_{r}\in\mathbb{F}_{p}$, we
have

$c_{1}v^{\prime}_{M}(F_{1})+\dots+c_{r}v^{\prime}_{M}(F_{r})=\mathbb{0}\Rightarrow
c_{1}v_{M}(F_{1})+\dots+c_{r}v_{M}(F_{r})=\mathbb{0}.$

  * •

We say that $\mathcal{J}$ is _independent_ if
$v^{\prime}_{M}(F_{1}),\dots,v^{\prime}_{M}(F_{r})$ are linearly independent,
or equivalently, there is no nontrivial linear combination of
$F_{1},\dots,F_{r}$ which is a constant function, or equivalently, for all
$c_{1},\dots,c_{r}\in\mathbb{F}_{p}$, we have

$c_{1}v^{\prime}_{M}(F_{1})+\dots+c_{r}v^{\prime}_{M}(F_{r})=\mathbb{0}\Rightarrow
c_{1}=\dots=c_{r}=0.$

  * •

We say that $\mathcal{J}$ is _nice_ if there exist some bijective $d$-integral
linear transformation
$L\colon(\mathbb{F}_{p}^{d})^{k}\to(\mathbb{F}_{p}^{d})^{k}$ and some
$v\in(\mathbb{F}_{p}^{d})^{k}$ such that $F_{i}(L(\cdot)+v)$ is nice for all
$1\leq i\leq r$.

The dimension of the span of
$v^{\prime}_{M}(F_{1}),\dots,v^{\prime}_{M}(F_{r})$ is called the _dimension_
of an $(M,k)$-family $\\{F_{1},\dots,F_{r}\\}$.

When there is no confusion, we call an $(M,k)$-family to be an _$M$ -family_
for short.

We say that a subset $\Omega$ of $(\mathbb{F}_{p}^{d})^{k}$ is an _$M$ -set_
if there exists an $(M,k)$-family
$\\{F_{i}\colon(\mathbb{F}_{p}^{d})^{k}\to\mathbb{F}_{p}^{d}\colon 1\leq i\leq
r\\}$ such that $\Omega=\cap_{i=1}^{r}V(F_{i})$. We call either
$\\{F_{1},\dots,F_{r}\\}$ or the ordered set $(F_{1},\dots,F_{r})$ an _$M$
-representation_ of $\Omega$.

Let $\mathbb{P}\in\\{\text{pure, nice, independent, consistent}\\}$. We say
that $\Omega$ is $\mathbb{P}$ if one can choose the $M$-family
$\\{F_{1},\dots,F_{r}\\}$ to be $\mathbb{P}$. We say that the
$M$-representation $(F_{1},\dots,F_{r})$ is $\mathbb{P}$ if $\\{F_{i}\colon
1\leq i\leq r\\}$ is $\mathbb{P}$. We say that $r$ is the _dimension_ of the
$M$-representation $(F_{1},\dots,F_{r})$. The _total co-dimension_ of a
consistent $M$-set $\Omega$, denoted by $r_{M}(\Omega)$, is the minimum of the
dimension of the independent $M$-representations of $\Omega$.242424We will
show in Proposition C.8 that $r_{M}(\Omega)$ is independent of the choice of
the independent $M$-representation if $d$ and $p$ are sufficiently large.

We say that an independent $M$-representation $(F_{1},\dots,F_{r})$ of
$\Omega$ is _standard_ if the matrix $\begin{bmatrix}v_{M}(F_{1})\\\ \dots\\\
v_{M}(F_{r})\end{bmatrix}$ is in the reduced row echelon form (or
equivalently, the matrix $\begin{bmatrix}v^{\prime}_{M}(F_{1})\\\ \dots\\\
v^{\prime}_{M}(F_{r})\end{bmatrix}$ is in the reduced row echelon form). If
$(F_{1},\dots,F_{r})$ is a standard $M$-representation of $\Omega$, then we
may relabeling $(F_{1},\dots,F_{r})$ as

$(F_{k,1},\dots,F_{k,r_{k}},F_{k-1,1},\dots,F_{k-1,r_{k-1}},\dots,F_{1,1},\dots,F_{1,r_{1}})$

for some $r_{1},\dots,r_{k}\in\mathbb{N}$ such that $F_{i,j}$ is non-constant
with respect to $n_{i}$ and is independent of $n_{i+1},\dots,n_{k}$. We also
call $(F_{i,j}\colon 1\leq i\leq k,1\leq j\leq r_{i})$ a _standard
$M$-representation_ of $\Omega$. The vector $(r_{1},\dots,r_{k})$ is called
the _dimension vector_ of this representation.

######  Convention 9.3.

We allow $(M,k)$-families, $M$-representations and dimension vectors to be
empty. In particular, $(\mathbb{F}_{p}^{d})^{k}$ is considered as a nice and
consistent $M$-set with total co-dimension zero.

######  Example 9.4.

Let $d,s\in\mathbb{N}_{+}$, $p$ be a prime,
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a quadratic form associated
with the matrix $A$, and $h_{1},\dots,h_{s}\in\mathbb{F}_{p}^{d}$. Then the
set $V(M)^{h_{1},\dots,h_{s}}$ defined in Definition 4.15 is an $M$-set with a
dimension vector $(s+1)$. Moreover, it is consistent if $h_{1}A,\dots,h_{s}A$
are linearly independent. On the other hand, $V(M)^{h_{1},\dots,h_{s}}$ is not
a nice $M$-set.

######  Example 9.5.

Let $M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a quadratic form
associated with the matrix $A$ and $s\in\mathbb{N}$. It follows from Lemma
4.18 that the Gowers set $\Box_{s}(V(M))$ is a consistent $M$-set with a
dimension vector $(1,1,\dots,s)$, whose total co-dimension is $(s^{2}+s+2)/2$.
On the other hand, let $L(n,h_{1},\dots,h_{s}):=(h_{1},\dots,h_{s},n)$. Then
it follows from Lemma 4.18 that $L(\Box_{s}(V(M)))$ is a consistent $M$-set
with a dimension vector $(0,\dots,s-1,s+1)$, whose total co-dimension is also
$(s^{2}+s+2)/2$. We will show later in Example B.4 that these $M$-sets are
nice when $M$ is non-degenerate.

We refer the readers to Appendix B for some basic properties as well as more
examples of $M$-sets, and to Appendix C for the Fubini’s theorem on $M$-sets
(which will be used extensively in [18, 19]).

###  9.2. Irreducible properties for sets generated by quadratic forms

In Section 10, we will boost Theorem 5.1 to cover partially $p$-periodic
polynomials on a large class of $M$-sets. Before generalizing Theorem 5.1, we
need to address a technical issue on the irreducible property for $M$-sets: if
$P$ is a polynomial whose set of solutions has a “large” intersection with
some $M$-set $\Omega$, then does it imply that all the elements in $\Omega$
are solutions to $P$? To answer this question, we start with the following
definition:

######  Definition 9.6 ($\delta$-irreducible sets).

Let $k\in\mathbb{N}_{+},s\in\mathbb{N},\delta>0$ and $p$ be a prime. We say
that a subset $\Omega$ of $\mathbb{F}_{p}^{k}$ is _$\delta$ -irreducible up to
degree $s$_ if for all $P\in\text{poly}(\mathbb{F}_{p}^{k}\to\mathbb{F}_{p})$
of degree at most $s$, either $|V(P)\cap\Omega|\leq\delta|\Omega|$ or
$\Omega\subseteq V(P)$.

Let $\Omega$ be a subset of $\mathbb{Z}^{k}$. Let
$\Omega^{\prime}:=\tau\circ\iota(\Omega)=(\Omega+p\mathbb{Z}^{k})\cap[p]^{k}$
be the set of $n\in[p]^{k}$ such that $n+pm\in\Omega$ for some
$m\in\mathbb{Z}^{k}$. We say that $\Omega$ is _weakly $(\delta,p)$-irreducible
up to degree $s$_ if for all $P\in\text{poly}(\mathbb{Z}^{k}\to\mathbb{Z}/p)$
of degree at most $s$, either
$|V_{p}(P)\cap\Omega^{\prime}|\leq\delta|\Omega^{\prime}|$ or
$\Omega^{\prime}\subseteq V_{p}(P).$ We say that $\Omega$ is _strongly
$(\delta,p)$-irreducible up to degree $s$_ if for all
$P\in\text{poly}(\mathbb{Z}^{k}\to\mathbb{Z}/p^{s})$ of degree at most $s$,
either $|V_{p}(P)\cap\Omega^{\prime}|\leq\delta|\Omega^{\prime}|$ or
$\Omega^{\prime}\subseteq V_{p}(P).$

######  Remark 9.7.

If $\Omega\subseteq\mathbb{F}_{p}^{k}$ is a $1/2$-irreducible algebraic set,
then it is not hard to see that for any
$P,Q\in\text{poly}(\mathbb{F}_{p}^{k}\to\mathbb{F}_{p})$, if $\Omega\subseteq
V(P)\cup V(Q)$, then either $\Omega\subseteq V(P)$ or $\Omega\subseteq V(Q)$.
In the language of algebraic geometry, this means that $\Omega$ is an
_irreducible algebraic set_ (or an _algebraic variety_).

The following basic proposition explains the connections between different
notions of irreducibility.

######  Proposition 9.8 (Connections between notions of irreduciblities).

Let $k\in\mathbb{N}_{+},s\in\mathbb{N},\delta>0$ and $p$ be a prime with
$p>s$.

  1. (i)

If $\Omega\subseteq\mathbb{F}_{p}^{k}$ is $\delta$-irreducible up to degree
$s$, then $\tau(\Omega)\subseteq[p]^{k}$ is $(\delta,p)$-irreducible up to
degree $s$.

  2. (ii)

Conversely, if $\Omega\subseteq[p]^{k}$ is $(\delta,p)$-irreducible up to
degree $s$, then $\iota(\Omega)\subseteq\mathbb{F}_{p}^{k}$ is
$\delta$-irreducible up to degree $s$.

  3. (iii)

If $\Omega\subseteq[p]^{k}$ is strongly $(\delta,p)$-irreducible up to degree
$s$, then it is also weakly $(\delta,p)$-irreducible up to degree $s$.

###### Proof.

Part (i) follows from the fact that for every
$P\in\text{poly}(\mathbb{Z}^{k}\to\mathbb{Z}/p)$ of degree at most $s$, we
have $\iota\circ
pP\circ\tau\in\text{poly}(\mathbb{F}_{p}^{k}\to\mathbb{F}_{p})$ and
$V_{p}(P)\cap\tau(\Omega)=\tau(V(\iota\circ pP\circ\tau)\cap\Omega)$. Part
(ii) follows from the fact that for every
$P\in\text{poly}(\mathbb{F}_{p}^{k}\to\mathbb{F}_{p})$, there exists a regular
lifting $\tilde{P}\in\text{poly}(\mathbb{Z}^{k}\to\mathbb{Z}/p)$ of $P$ with
$\tilde{P}=\frac{1}{p}\tau(P\circ\iota)\mod\mathbb{Z}$ and
$V(P)\cap\iota(\Omega)=\iota(V_{p}(\tilde{P})\cap\Omega)$. Part (iii) follows
from the inclusion
$\text{poly}(\mathbb{Z}^{k}\to\mathbb{Z}/p)\subseteq\text{poly}(\mathbb{Z}^{k}\to\mathbb{Z}/p^{s})$.
∎

It is not hard to see that the full set $\mathbb{F}_{p}^{d}$ is
$\delta$-irreducible. To be more precise, we have

######  Proposition 9.9 ($\mathbb{F}_{p}^{d}$ is irreducible).

Let $d\in\mathbb{N}_{+},s\in\mathbb{N},\delta>0$ and $p$ be a prime. If
$p\gg_{d,s}\delta^{-O_{d,s}(1)}$, then

  1. (i)

$\mathbb{F}_{p}^{d}$ is $\delta$-irreducible up to degree $s$;

  2. (ii)

$[p]^{d}$ is weakly $(\delta,p)$-irreducible up to degree $s$;

  3. (iii)

$[p]^{d}$ is strongly $(\delta,p)$-irreducible up to degree $s$.

###### Proof.

Part (i) follows from Lemma 4.10. Part (ii) follows from Part (i) and
Proposition 9.8. We now prove Part (iii). The idea is to use Part (ii) and the
$p$-expansion trick. Let $g\in\text{poly}(\mathbb{Z}^{d}\to\mathbb{Z}/p^{s})$
be of degree at most $s$ with $|V_{p}(g)|>\delta p^{d}$. By the multivariate
polynomial interpolation, there exists $Q\in\mathbb{N},p\nmid Q$ such that
$Qg=\sum_{i=0}^{s}\frac{g_{i}}{p^{i}}$ for some integer valued polynomials
$g_{i}\colon\mathbb{Z}^{d}\to\mathbb{Z}$ of degree at most $s$. Let
$k\in\mathbb{N}$ be the smallest integer such that there exists
$Q\in\mathbb{N},p\nmid Q$ with $Qg=\sum_{i=0}^{k}\frac{g_{i}}{p^{i}}$ for some
integer valued polynomials $g_{i}\colon\mathbb{Z}^{d}\to\mathbb{Z}$ .
Obviously such $k$ exists and is at most $s$. Our goal is to show that $k=0$.

Suppose that $k>0$. For all $n\in V_{p}(g)$ and $m\in\mathbb{Z}^{d}$, by
definition $g(n+pm)\in\mathbb{Z}$. Therefore, we must have that
$g_{k}(n+pm)\in p\mathbb{Z}$. So
$|V_{p}(\frac{1}{p}g_{k})\cap[p]^{d}|\geq|V_{p}(g)\cap[p]^{d}|>\delta p^{d}$.
By Part (ii), we have that $V_{p}(\frac{1}{p}g_{k})\supseteq[p]^{d}$ and thus
$\frac{1}{p}g_{k}(n)\in\mathbb{Z}$ for all $n\in\mathbb{Z}^{d}$. Then there
exists $Q^{\prime}\in\mathbb{N},p\nmid Q^{\prime}$ such that
$\frac{Q^{\prime}}{p}g_{k}$ and thus $Q^{\prime}(g_{k-1}+\frac{1}{p}g_{k})$ is
an integer valued polynomial, a contradiction to the minimality of $k$.

We have thus proved that $k=0$ and thus $Qg$ itself is integer valued for some
$Q\in\mathbb{N},p\nmid Q$. Then for all $n\in[p]^{d}$, we have that
$g(n)\in\mathbb{Z}/Q$. Since $g$ takes values in $\mathbb{Z}/p^{s}$, we have
that $g(n)\in(\mathbb{Z}/Q)\cap(\mathbb{Z}/p^{s})=\mathbb{Z}$. So $[p]^{d}$ is
strongly $(\delta,p)$-irreducible up to degree $s$. ∎

As a consequence of Lemma 6.1, we have:

######  Proposition 9.10 ($V(M)$ is irreducible).

Let $d\in\mathbb{N}_{+},s\in\mathbb{N},\delta>0$ and $p$ be a prime. If
$p\gg_{d,s}\delta^{-O_{d,s}(1)}$, then

  1. (i)

for every quadratic form $M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ of rank
at least 3, the set $V(M)$ is $\delta$-irreducible up to degree $s$;

  2. (ii)

for every quadratic form $M\colon\mathbb{Z}^{d}\to\mathbb{Z}/p$ of $p$-rank at
least 3, the set $V_{p}(M)$ is weakly $(\delta,p)$-irreducible up to degree
$s$;

  3. (iii)

for every quadratic form $M\colon\mathbb{Z}^{d}\to\mathbb{Z}/p$ of $p$-rank at
least 3, the set $V_{p}(M)$ is strongly $(\delta,p)$-irreducible up to degree
$s$.

###### Proof.

Part (i) follows from Lemma 6.1. Part (ii) follows from Part (i) and
Proposition 9.8. We now prove Part (iii) using Part (ii) and the $p$-expansion
trick. The proof is very similar to that of Proposition 7.8. Let
$g\in\text{poly}(\mathbb{Z}^{d}\to\mathbb{Z}/p^{s})$ be of degree at most $s$
with $|V_{p}(g)\cap V_{p}(M)\cap[p]^{d}|>\delta|V_{p}(M)\cap[p]^{d}|$. By the
multivariate polynomial interpolation, there exists $Q\in\mathbb{N},p\nmid Q$
such that

$Qg=\sum_{i=0}^{s}\frac{g_{i}}{p^{i}}$

for some integer valued polynomials $g_{i}\colon\mathbb{Z}^{d}\to\mathbb{Z}$
of degree at most $s$. We say that a polynomial $f$ is _good_ if

$f=\sum_{i=0}^{\lfloor s/2\rfloor}M^{i}R_{i}$

for some integer valued polynomial $R_{i}\colon\mathbb{Z}^{d}\to\mathbb{Z}$ of
degree at most $s-2i$. Let $k\in\mathbb{N}$ be the smallest integer such that
there exists $Q\in\mathbb{N},p\nmid Q$ with

$Qg=\sum_{i=0}^{k}\frac{g_{i}}{p^{i}}$

for some good polynomials $g_{i}\colon\mathbb{Z}^{d}\to\mathbb{Z}$ . Obviously
such $k$ exists and is at most $s$. Our goal is to show that $k=0$.

Suppose that $k>0$. For all $n\in V_{p}(g)\cap V_{p}(M)$ and
$m\in\mathbb{Z}^{d}$, by definition $g(n+pm)\in\mathbb{Z}$. Therefore, we must
have that $g_{k}(n+pm)\in p\mathbb{Z}$. Suppose that

$g_{k}=\sum_{i=0}^{\lfloor s/2\rfloor}M^{i}R_{i}$

for some integer valued polynomials $R_{i}\colon\mathbb{Z}^{d}\to\mathbb{Z}$
of degree at most $s-2i$. Assume that

$M(n)=\frac{1}{p}((nA)\cdot n+u\cdot n+v)$

for some symmetric integer valued $d\times d$ matrix $A$, some
$u\in\mathbb{Z}^{d}$ and some $v\in\mathbb{Z}$. Then for all $n\in
V_{p}(g)\cap V_{p}(M)$ and $m\in\mathbb{Z}^{d}$, writing
$x:=M(n)+(2(nA)+u)\cdot m$, we have

(9.2) $\begin{split}&\quad 0\equiv g_{k}(n+pm)\equiv\sum_{i=0}^{\lfloor
s/2\rfloor}M(n+pm)^{i}R_{i}(n)\\\ &\equiv\sum_{i=0}^{\lfloor
s/2\rfloor}(M(n)+(2(nA)+u)\cdot m)^{i}R_{i}(n)=\sum_{i=0}^{\lfloor
s/2\rfloor}x^{i}R_{i}(n)\mod p\mathbb{Z}.\end{split}$

Note that if $2(nA)+u\notin p\mathbb{Z}^{d}$, then for any $x\in[p]$, there
exists $m\in\mathbb{Z}^{d}$ such that $M(n)+(2(nA)+u)\cdot m\equiv x\mod
p\mathbb{Z}$. So viewing the right hand side of (9.2) as a polynomial of $x$,
we have that $R_{i}(n)\in p\mathbb{Z}/Q^{\prime}$ for some
$Q^{\prime}\in\mathbb{N},p\nmid Q^{\prime}$ for all $0\leq i\leq\lfloor
s/2\rfloor$ and $n\in V_{p}(g)\cap V_{p}(M)$ with $2(nA)+u\notin
p\mathbb{Z}^{d}$.

Since $\text{rank}_{p}(M)\geq 3$, it is not hard to see that the number of
$n\in[p]^{d}$ with $2(nA)+u\in p\mathbb{Z}^{d}$ is at most $p^{d-3}$. So

$|V_{p}(Q^{\prime}R_{i})\cap V_{p}(M)\cap[p]^{d}|\geq|V_{p}(g)\cap
V_{p}(M)\cap[p]^{d}|-p^{d-3}>\delta|V_{p}(M)\cap[p]^{d}|/2.$

By Part (ii), we have that $V_{p}(M)\subseteq V_{p}(Q^{\prime}R_{i})$ for all
$0\leq i\leq\lfloor s/2\rfloor$. Let
$Q^{\prime\prime}\in\mathbb{N},Q^{\prime}|Q^{\prime\prime},p\nmid
Q^{\prime\prime}$ be such that $Q^{\prime\prime}R_{i}$ is an integer
coefficient polynomial for all $0\leq i\leq\lfloor s/2\rfloor$. We may invoke
Corollary 7.2 to conclude that

$\frac{Q^{\prime\prime}}{p}R_{i}=MR^{\prime}_{i}+R^{\prime\prime}_{i}$

for some integer valued polynomials $R_{i},R^{\prime\prime}_{i}$ of degrees at
most $s-2i-2$ and $s-2i$ respectively. Then $\frac{Q^{\prime\prime}}{p}g_{k}$
and thus $Q^{\prime\prime}(g_{k-1}+\frac{1}{p}g_{k})$ is good, a contradiction
to the minimality of $k$.

We have thus proved that $k=0$ and thus $Qg$ itself is good for some
$Q\in\mathbb{N},p\nmid Q$. Then for all $n\in V_{p}(M)$, we have that
$g(n)\in\mathbb{Z}/Q$. Since $g$ takes values in $\mathbb{Z}/p^{s}$, we have
that $g(n)\in(\mathbb{Z}/Q)\cap(\mathbb{Z}/p^{s})=\mathbb{Z}$ and thus
$V_{p}(M)\subseteq V_{p}(g)$. So $V_{p}(M)$ is strongly
$(\delta,p)$-irreducible up to degree $s$. ∎

We provide some basic propositions for the irreducible properties. Firstly, it
is straightforward that the irreducible properties are preserved under
translations.

######  Proposition 9.11 (Irreducible sets are translation invariant).

Let $d\in\mathbb{N}_{+},s\in\mathbb{N},\delta>0$ and $p>s$ be a prime.

  1. (i)

Let $\Omega\subseteq\mathbb{F}_{p}^{d}$ be $\delta$-irreducible up to degree
$s$ and $v\in\mathbb{F}_{p}^{d}$. Then $\Omega+v$ is also $\delta$-irreducible
up to degree $s$.

  2. (ii)

Let $\Omega\subseteq\mathbb{Z}^{d}$ be weakly $(\delta,p)$-irreducible up to
degree $s$ and $v\in\mathbb{Z}^{d}$. Then $\Omega+v$ is also weakly
$(\delta,p)$-irreducible up to degree $s$.

  3. (iii)

Let $\Omega\subseteq\mathbb{Z}^{d}$ be strongly $(\delta,p)$-irreducible up to
degree $s$ and $v\in\mathbb{Z}^{d}$. Then $\Omega+v$ is also strongly
$(\delta,p)$-irreducible up to degree $s$.

###### Proof.

Let $P\in\text{poly}(\mathbb{F}_{p}^{d}\to\mathbb{F}_{p})$ be a polynomial of
degree at most $s$ such that
$|V(P)\cap(\Omega+v)|\geq\delta|\Omega+v|=\delta|\Omega|$. Then
$|V(P(\cdot-v))\cap\Omega|\geq\delta|\Omega|$. Since $\Omega$ is
$\delta$-irreducible up to degree $s$, we have that
$V(P(\cdot-v))\subseteq\Omega$ and thus $V(P)\subseteq\Omega+v$. This proves
Part (i).

The proofs of Parts (ii) and (iii) are similar to Part (i) and we leave them
to the interested readers. ∎

Moreover, the irreducible properties are preserved under products.

######  Proposition 9.12 (Products of irreducible sets are irreducible).

Let $d_{1},d_{2}\in\mathbb{N}_{+},s\in\mathbb{N},\delta>0$ and $p>s$ be a
prime. Let $\Omega_{1}\subseteq\mathbb{F}_{p}^{d_{1}}$,
$\Omega_{2}\subseteq\mathbb{F}_{p}^{d_{2}}$ and
$\Omega=\Omega_{1}\times\Omega_{2}$.

  1. (i)

If $\Omega_{1}\subseteq\mathbb{F}_{p}^{d_{1}}$ and
$\Omega_{2}\subseteq\mathbb{F}_{p}^{d_{2}}$ are $\delta$-irreducible up to
degree $s$, then
$\Omega_{1}\times\Omega_{2}\subseteq\mathbb{F}_{p}^{d_{1}+d_{2}}$ is
$2\delta$-irreducible up to degree $s$.

  2. (ii)

If $\Omega_{1}\subseteq\mathbb{Z}^{d_{1}}$ and
$\Omega_{2}\subseteq\mathbb{Z}^{d_{2}}$ are weakly $(\delta,p)$-irreducible up
to degree $s$, then
$\Omega_{1}\times\Omega_{2}\subseteq\mathbb{Z}^{d_{1}+d_{2}}$ is weakly
$(2\delta,p)$-irreducible up to degree $s$.

  3. (iii)

If $\Omega_{1}\subseteq\mathbb{Z}^{d_{1}}$ and
$\Omega_{2}\subseteq\mathbb{Z}^{d_{2}}$ are strongly $(\delta,p)$-irreducible
up to degree $s$, then
$\Omega_{1}\times\Omega_{2}\subseteq\mathbb{Z}^{d_{1}+d_{2}}$ is strongly
$(2\delta,p)$-irreducible up to degree $s$.

###### Proof.

Let $P\in\text{poly}(\mathbb{F}_{p}^{d_{1}+d_{2}}\to\mathbb{F}_{p})$ be a
polynomial of degree at most $s$ such that
$|V(P)\cap(\Omega_{1}\times\Omega_{2})|\geq
2\delta|\Omega_{1}|\cdot|\Omega_{2}|$. By the Pigeonhole Principle, there
exists a subset $U$ of $\Omega_{2}$ with $|U|\geq\delta|\Omega_{2}|$ such that
for all $y\in U$,
$|V(P(\cdot,y))\cap\Omega_{1}|=|V(P)\cap(\Omega_{1}\times\\{y\\})|\geq\delta|\Omega_{1}|$.
Since $\Omega_{1}$ is $\delta$-irreducible up to degree $s$, we have that
$\Omega_{1}\subseteq V(P(\cdot,y))$ for all $y\in U$. In other words, for all
$x\in\Omega_{1}$,
$|V(P(x,\cdot))\cap\Omega_{2}|\geq|U|\geq\delta|\Omega_{2}|$. Since
$\Omega_{2}$ is $\delta$-irreducible up to degree $s$, we have that
$\Omega_{2}\subseteq V(P(x,\cdot))$ for all $x\in\Omega_{1}$. In other words,
$\Omega_{1}\times\Omega_{2}\subseteq V(P)$. This proves Part (i).

The proofs of Parts (ii) and (iii) are similar to Part (i) and we leave them
to the interested readers. ∎

Finally, the irreducible properties are preserved under isomorphisms.

######  Proposition 9.13 (Irreducible sets are invariant under isomorphisms).

Let $k\in\mathbb{N}_{+},s\in\mathbb{N},\delta>0$ and $p>s$ be a prime. Let
$\Omega\subseteq\mathbb{F}_{p}^{k}$ and
$L\colon\mathbb{F}_{p}^{k}\to\mathbb{F}_{p}^{k}$ be a bijective linear
transformation.

  1. (i)

If $\Omega$ is $\delta$-irreducible up to degree $s$, then so is $L(\Omega)$.

  2. (ii)

If $\tau(\Omega)$ is weakly $(\delta,p)$-irreducible up to degree $s$, then so
is $\tau(L(\Omega))$.

  3. (iii)

If $\tau(\Omega)$ is strongly $(\delta,p)$-irreducible up to degree $s$, then
so is $\tau(L(\Omega))$.

###### Proof.

We first prove Part (i). Let
$P\in\text{poly}(\mathbb{F}_{p}^{k}\to\mathbb{F}_{p})$ be a polynomial of
degree at most $s$ with

$|V(P\circ L)\cap\Omega|=|V(P)\cap
L(\Omega)|\geq\delta|L(\Omega)|=\delta|\Omega|.$

Clearly $P\circ L\colon\mathbb{F}_{p}^{k}\to\mathbb{F}_{p}$ is a polynomial of
degree at most $s$. Since $\Omega$ is $\delta$-irreducible up to degree $s$,
we have that $\Omega\subseteq V(P\circ L)$ and so $L(\Omega)\subseteq V(P)$.
So $L(\Omega)$ is $\delta$-irreducible up to degree $s$.

We now prove Part (ii). Let $P\in\text{poly}(\mathbb{Z}^{k}\to\mathbb{Z}/p)$
be a polynomial of degree at most $s$ with
$|V_{p}(P)\cap\tau(L(\Omega))|\geq\delta|\tau(L(\Omega))|=\delta|\Omega|$ (we
have $|\tau(L(\Omega))|=|\Omega|$ because the map $n\to\tau(L(n))$ is
injective). By Lemma 9.1, there exists a linear transformation
$\tilde{L}\colon\mathbb{Z}^{k}\to\mathbb{Z}^{k}$ such that
$\tilde{L}\circ\tau\equiv\tau\circ L\mod p\mathbb{Z}^{k}$. Since $L$ is
bijective, $\tilde{L}$ maps different residue classes mod $p\mathbb{Z}^{k}$ to
different residue classes mod $p\mathbb{Z}^{k}$. So

$|V_{p}(P)\cap\tau(L(\Omega))|=|V_{p}(P)\cap\tilde{L}\circ\tau(\Omega)|=|V_{p}(P\circ\tilde{L})\cap\tau(\Omega)|.$

It is clear that $P\circ\tilde{L}$ is a polynomial belonging to
$\text{poly}(\mathbb{Z}^{k}\to\mathbb{Z}/p)$ of degree at most $s$. Since
$\tau(\Omega)$ is weakly $(\delta,p)$-irreducible up to degree $s$, we have
that $\tau(\Omega)\subseteq V_{p}(P\circ\tilde{L})$ and thus
$\tau(L(\Omega))\subseteq V_{p}(P)$ since
$P\circ\tilde{L}\in\text{poly}(\mathbb{Z}^{k}\to\mathbb{Z}/p)$. So
$\tau(L(\Omega))$ is weakly $(\delta,p)$-irreducible up to degree $s$.

Note that if $P\in\text{poly}(\mathbb{Z}^{k}\to\mathbb{Z}/p^{s})$ is a
polynomial of degree at most $s$, then so is $P\circ\tilde{L}$. The rest proof
of Part (iii) is almost identical to that of Part (ii) and we omit the
details. ∎

We are now ready to state the main irreducible theorem for $M$-sets:

######  Theorem 9.14 (Nice and consistent $M$-sets are irreducible).

Let $d,K\in\mathbb{N}_{+},s\in\mathbb{N}$, $p$ be a prime, and $\delta>0$. Let
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a non-degenerate quadratic
form and $\Omega\subseteq(\mathbb{F}_{p}^{d})^{K}$ be a nice and consistent
$M$-set. If $d\geq\max\\{2r_{M}(\Omega)+1,4K-1\\}$ and
$p\gg_{d,s}\delta^{-O_{d,s}(1)}$, then

  1. (i)

$\Omega$ is $\delta$-irreducible up to degree $s$;

  2. (ii)

$\tau(\Omega)$ is weakly $(\delta,p)$-irreducible up to degree $s$;

  3. (iii)

$\tau(\Omega)$ is strongly $(\delta,p)$-irreducible up to degree $s$.

The proof of Theorem 9.14 is rather complicated. We postpone the proof of
Theorem 9.14 to Appendix D to prevent the readers from being distracted by
technical details.

######  Remark 9.15.

The method we use to prove Theorem 9.14 can be adapted to show that all
consistent $M$-sets are irreducible in all the three senses. However, we do
not need such a general result in this paper.

##  10\. Leibman dichotomy

In this section, we extend Theorem 5.1 to all nice and consistent $M$-sets.
For convenience, we introduce the following definition:

######  Definition 10.1 ($(\delta,K)$-Leibman dichotomy).

Let $d\in\mathbb{N}_{+},s\in\mathbb{N}$, $C,\delta,K>0$, $p$ be a prime, and
$\Omega$ be a non-empty subset of $\mathbb{F}_{p}^{d}$. We say that $\Omega$
admits a _$(\delta,K)$ -Leibman dichotomy up to step $s$ and complexity $C$_
if for any $\mathbb{N}$-filtered nilmanifold $G/\Gamma$ of degree at most $s$
and complexity at most $C$, and any $g(n)\in\text{poly}_{p}(\Omega\to
G_{\mathbb{N}}|\Gamma)$, either $(g(n)\Gamma)_{n\in\Omega}$ is
$\delta$-equidistributed on $G/\Gamma$, or there exists a nontrivial type-I
horizontal character $\eta$ with $0<\|\eta\|\leq K$ such that $\eta\circ
g|_{\Omega}\colon\Omega\to\mathbb{R}$ is a constant mod $\mathbb{Z}$.

We may deduce the following Leibman dichotomy from the main result of [8]:

######  Theorem 10.2 ($\mathbb{F}_{p}^{d}$ admits a Leibman dichotomy).

Let $d\in\mathbb{N}_{+},s\in\mathbb{N}$, $C>0$ and $p$ be a prime. There
exists $K=O_{C,d,s}(1)$ such that for all $0<\delta<1/2$, $\mathbb{F}_{p}^{d}$
admits a $(\delta,K\delta^{-K})$-Leibman dichotomy up to step $s$ and
complexity $C$.

###### Proof.

Let $g\in\text{poly}_{p}(\mathbb{F}_{p}^{d}\to G_{\mathbb{N}}|\Gamma)$ and
$\delta>0$. Suppose that the sequence $(g(n)\Gamma)_{n\in\mathbb{F}_{p}^{d}}$
is not $\delta$-equidistributed on $G/\Gamma$. Then
$g\circ\iota(n+pm)\Gamma=g\circ\iota(n)\Gamma$ for all $m,n\in\mathbb{Z}^{d}$.
Therefore, we have that $g\circ\iota\in\text{poly}(\mathbb{Z}^{d}\to
G_{\mathbb{N}})$ and that $(g\circ\iota(n)\Gamma)_{n\in[pN]^{d}}$ is not
$\delta$-equidistributed on $G/\Gamma$ for all $N\in\mathbb{N}_{+}$. By
Theorem 8.6 of [8], there exists a nontrivial type-I horizontal character
$\eta$ with $0<\|\eta\|\leq O_{C,d,s}(\delta^{-O_{C,d,s}(1)})$ such that
$\|\eta\circ
g\circ\iota\|_{C^{\infty}[pN]^{d}}\ll_{C,d,s}\delta^{-O_{C,d,s}(1)}$ (see
Definition 8.2 of [8] for the definition of the smoothness norm
$\|\cdot\|_{C^{\infty}[N]^{d}}$). Letting $N\to\infty$, we have that
$\|\eta\circ g\circ\iota\|_{C^{\infty}[pN]^{d}}=0$ if $N$ is sufficiently
large and thus $\eta\circ g\circ\iota\mod\mathbb{Z}$ is a constant. So
$\eta\circ g\mod\mathbb{Z}$ is a constant and we are done. ∎

We may also rephrase Theorem 5.1 using the Leibman dichotomy as below:

######  Theorem 10.3 ($V(M)$ admits a Leibman dichotomy).

Let $d\in\mathbb{N}_{+},r,s\in\mathbb{N}$, $C>0$ and $p$ be a prime. There
exists $K=O_{C,d-r}(1)$ such that for any affine subspace $V+c$ of
$\mathbb{F}_{p}^{d}$ of co-dimension $r$, any quadratic form
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ with $\text{rank}(M|_{V+c})\geq
s+13$, and any $0<\delta<1/2$, if $p\gg_{C,d-r}\delta^{-O_{C,d-r}(1)}$, then
$V(M)\cap(V+c)$ admits a $(\delta,K\delta^{-K})$-Leibman dichotomy up to step
$s$ and complexity $C$.252525It follows from Corollary 4.14 that
$V(M)\cap(V+c)$ is non-empty.

The following lemma is a straightforward consequence of the definition of the
Leibman dichotomy and Proposition 3.19. Its proof is left to the interested
readers.

######  Lemma 10.4.

Let $k\in\mathbb{N}_{+},s\in\mathbb{N}$, $\delta,K>0$, $p$ be a prime,
$\Omega\subseteq\mathbb{F}_{p}^{k}$ be non-empty, $v\in\mathbb{F}_{p}^{k}$ and
$L\colon\mathbb{F}_{p}^{k}\to\mathbb{F}_{p}^{k}$ be a bijective linear
transformation. If $\Omega$ admits a $(\delta,K)$-Leibman dichotomy up to step
$s$ and complexity $C$, then so does $L(\Omega)+v$.

We are now ready to state the generalization of Theorem 5.1 for nice and
consistent $M$-sets:

######  Theorem 10.5 (Nice and consistent $M$-sets admit Leibman dichotomies).

Let $d,k\in\mathbb{N}_{+},s,r\in\mathbb{N}$ with
$d\geq\max\\{4r+1,4k+3,2k+s+11\\}$, $C>0$ and $p$ be a prime. There exists
$K:=O_{C,d}(1)$ such that for any non-degenerate quadratic form
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$, any nice and consistent $M$-set
$\Omega\subseteq(\mathbb{F}_{p}^{d})^{k}$ of total co-dimension $r$, and any
$0<\delta<1/2$, if $p\gg_{C,d}\delta^{-O_{C,d}(1)}$, then $\Omega$ admits a
$(\delta,K\delta^{-K})$-Leibman dichotomy up to step $s$ and complexity
$C$.262626It follows from Theorem C.3 that $\Omega$ is non-empty.

The proof of Theorem 10.5 is rather complicated. We postpone the proof of
Theorem 10.5 to Appendix E to prevent the readers from being distracted by
technical details.

######  Remark 10.6.

Let $\eta$ be any nontrivial type-I horizontal character of complexity 1. By
Lemma 3.24, for any $g\in\text{poly}_{p}(\Omega\to G_{\mathbb{N}}|\Gamma)$,
$p^{s}\eta\circ g\mod\mathbb{Z}$ is a constant. So every non-empty set
$\Omega\subseteq\mathbb{F}_{p}^{d}$ admits a $(\delta,p^{s})$-Leibman
dichotomy for any $\delta$. Therefore, it is not hard to see that the
restriction that $p\gg\delta^{-O(1)}$ can be dropped in Theorems 1.1, 5.1 as
well as in all the results in Section 10.

##  11\. Factorization theorems

With all the preparations in the previous sections, we are now ready to derive
the factorization theorem for partially $p$-periodic polynomial sequences $g$
on a set $\Omega$ admitting a Leibman dichotomy. We show that $g$ can be
written as the product of a small constant term $\epsilon$, a polynomial
sequence $g^{\prime}$ which is sufficiently well equidistributed on a
subnilmanifold, and a polynomial sequence $\gamma$ taking values in $\Gamma$
on $\Omega$. To begin with, we prove a weak factorization theorem, where
$g^{\prime}$ is only required to take values on a subnilmanifold.

For a nilmanifold $G/\Gamma$ with filtration $(G_{i})_{i\in\mathbb{N}}$, the
_total dimension_ of $G/\Gamma$ is the quantity
$\sum_{i\in\mathbb{N}}\dim(G_{i})$.

######  Proposition 11.1 (Weak factorization property).

Let $d,s\in\mathbb{N}_{+}$, $C,\delta,K>0$ and $p\gg_{C,d,K,s}1$ be a prime.
Let $\Omega\subseteq\mathbb{F}_{p}^{d}$ be a non-empty set admitting a
$(\delta,K)$-Leibman dichotomy up to degree $s$ and complexity $C$. Let
$G/\Gamma$ be an $s$-step $\mathbb{N}$-filtered nilmanifold of complexity at
most $C$, equipped with a $C$-rational Mal’cev basis $\mathcal{X}$, and let
$g\in\text{poly}_{p}(\Omega\to G_{\mathbb{N}}|\Gamma)$. If
$(g(n)\Gamma)_{n\in\Omega}$ is not $\delta$-equidistributed on $G/\Gamma$,
then we may factorize $g$ as

$g(n)=\epsilon g^{\prime}(n)\gamma(n)\text{ for all }n\in\mathbb{F}_{p}^{d},$

where $\epsilon\in G$ of complexity at most 1,
$g^{\prime}\in\text{poly}_{p}(\Omega\to
G^{\prime}_{\mathbb{N}}|\Gamma^{\prime})$, $g^{\prime}(\mathbb{0})=id_{G}$ for
some sub-nilmanifold $G^{\prime}/\Gamma^{\prime}$ of $G/\Gamma$ whose Mal’cev
basis is $O_{C,d}(K)$-rational relative to $\mathcal{X}$ and whose total
dimension is smaller than that of $G/\Gamma$, and
$\gamma\in\text{poly}(\Omega\to G_{\mathbb{N}}|\Gamma)$ with
$\gamma(\mathbb{0})=id_{G}$.

###### Proof.

The proof uses ideas from Proposition 9.2 of Green and Tao’s work [8] and the
work of Candela and Sisask [1]. In our case, the constructions of the
sequences $g^{\prime}$ and $\gamma$ are more intricate, as we need them to
satisfy certain partial periodic conditions.

Throughout the proof we assume that $p\gg_{C,d,K,s}1$. Denote
$m_{i}:=\dim(G_{i})$ for $i\in\mathbb{N}$ and $m:=\dim(G)$. Let
$\mathcal{X}=\\{X_{1},\dots,X_{m}\\}$ be the Mal’cev basis of $G/\Gamma$.
Write $g:=\\{g(\mathbb{0})\\}g_{\ast}[g(\mathbb{0})]$. Then
$g_{\ast}\in\text{poly}_{p}(\Omega\to G_{\mathbb{N}}|\Gamma)$. So replacing
$g$ by $g_{\ast}$ if necessary, we may assume without loss of generality that
$g(\mathbb{0})=id_{G}$.

If $(g(n)\Gamma)_{n\in\Omega}$ is not $\delta$-equidistributed, then since
$\Omega$ admits a $(\delta,K)$-Leibman dichotomy, there exists a nontrivial
type-I horizontal character $\eta$ with $0<\|\eta\|\leq K$ such that
$\eta\circ g\mod\mathbb{Z}$ is a constant on $\Omega$. We may assume that
$g=\tilde{g}\circ\tau$, for some $\tilde{g}\in\text{poly}_{p}(\tau(\Omega)\to
G_{\mathbb{N}}|\Gamma)$. Since $g(\mathbb{0})=id_{G}$, we have that
$\tilde{g}(\mathbb{0})=id_{G}$. So we may use the type-I Taylor expansion to
write $\tilde{g}$ as

$\tilde{g}(n)=\prod_{i\in\mathbb{N}^{d},0<|i|\leq s}g_{i}^{\binom{n}{i}}\text{
for all }n\in\mathbb{Z}^{d}$

for some $g_{i}\in G_{|i|}$. Since $\eta\circ g\mod\mathbb{Z}$ is a constant
on $\Omega$, $\eta\circ\tilde{g}\mod\mathbb{Z}$ is a constant on
$\tau(\Omega)$.

Let $G^{\prime}$ be the connected component of $\ker(\eta)$. Then $G^{\prime}$
is a subgroup of $G$ which is $O_{C,d}(K)$-rational relative to $\mathcal{X}$.
Write

$\psi(\tilde{g}(n))=\sum_{i\in\mathbb{N}^{d},0<|i|\leq s}t_{i}\binom{n}{i}$

for some $t_{i}\in\\{0\\}^{m-m_{|i|}}\times\mathbb{R}^{m_{|i|}}$. The type-I
horizontal character $\eta$ is given in coordinates by

$\eta\circ\tilde{g}(n)=\sum_{i\in\mathbb{N}^{d},0<|i|\leq s}k\cdot
t_{i}\binom{n}{i}$

for some $k=(k_{1},\dots,k_{m})\in\mathbb{Z}^{m}$ of complexity at most
$O_{C,d}(K)$. Let $0\leq s^{\prime}\leq s$ be the largest integer such that at
least one of the entries $k_{m-m_{s^{\prime}}+1},\dots,k_{m-m_{s^{\prime}+1}}$
is nonzero (where we denote $m_{0}:=m$). Since $\eta$ is nontrivial, such an
$s^{\prime}$ always exists. Denote $m^{\prime}:=m-m_{s^{\prime}+1}$. Then we
may write $k=(k^{\prime},\mathbb{0})$ for some
$k^{\prime}\in\mathbb{Z}^{m^{\prime}}$. Write
$t_{i}=(t^{\prime}_{i},t^{\prime\prime}_{i})$ for some
$t^{\prime}_{i}\in\mathbb{R}^{m^{\prime}}$ and
$t^{\prime\prime}_{i}\in\mathbb{R}^{m-m^{\prime}}$. Since the first
$m-m_{|i|}$ entries of $t_{i}$ are zero, and the last $m_{s^{\prime}+1}$
entries of $k$ are zero, we have that $k\cdot t_{i}=0$ if $|i|\geq
s^{\prime}+1$. So

$\eta\circ\tilde{g}(n)=\sum_{i\in\mathbb{N}^{d},0<|i|\leq s}k^{\prime}\cdot
t^{\prime}_{i}\binom{n}{i}=\sum_{i\in\mathbb{N}^{d},0<|i|\leq
s^{\prime}}k^{\prime}\cdot t^{\prime}_{i}\binom{n}{i}.$

Since $k$ is of complexity at most $O_{C,d}(K)$, there exists
$Q\in\mathbb{N}_{+},Q\leq O_{C,\delta,d,K}(1)$ and
$u=(u_{1},\dots,u_{m})\in\mathbb{Z}^{m}$ whose only nonzero entries are
$u_{m-m_{s^{\prime}}+1},\dots,u_{m-m_{s^{\prime}+1}}$ such that $k\cdot u=Q.$
Denote

$\gamma_{0}(n):=\prod_{i=m-m_{s^{\prime}}+1}^{m-m_{s^{\prime}+1}}\exp(Q^{\ast}u_{i}\eta(\tilde{g}(n))X_{i}),$

where $Q^{\ast}$ is any integer such that $Q^{\ast}Q\equiv 1\mod
p^{s}\mathbb{Z}$. Clearly $\gamma_{0}(\mathbb{0})=id_{G}$. Since
$\tilde{g}\in\text{poly}_{p}(\tau(\Omega)\to G_{\mathbb{N}}|\Gamma)$, we have
that
$\eta\circ\tilde{g}\in\text{poly}_{p}(\tau(\Omega)\to\mathbb{R}|\mathbb{Z})$
by Lemma 3.23. This implies that $\gamma_{0}\in\text{poly}(\tau(\Omega)\to
G_{\mathbb{N}}|\Gamma)$.

Since $\Omega$ is non-empty, by Lemma 3.24, we have that
$p^{s}\eta\circ\tilde{g}(n)\in\mathbb{Z}$ for all $n\in\mathbb{Z}^{d}$. On the
other hand, writing $h(n):=\tilde{g}(n)\gamma_{0}(n)^{-1}$ we have that
$h\in\text{poly}(\mathbb{Z}^{d}\to G_{\mathbb{N}})$ by Corollary B.4 of [11]
and that

$\eta\circ h(n)=\eta\circ\tilde{g}(n)-Q^{\ast}(k\cdot
u)\eta\circ\tilde{g}(n)=(1-Q^{\ast}Q)\eta\circ\tilde{g}(n),$

which is an integer valued polynomial. Since
$\gamma_{0}\in\text{poly}(\tau(\Omega)\to G_{\mathbb{N}}|\Gamma)$ and
$\tilde{g}\in\text{poly}_{p}(\tau(\Omega)\to G_{\mathbb{N}}|\Gamma)$, it
follows from Lemma 3.17 that $h\in\text{poly}_{p}(\tau(\Omega)\to
G_{\mathbb{N}}|\Gamma)$. By Proposition 3.25, there exists
$\gamma^{\prime}\in\text{poly}(\mathbb{Z}^{d}\to G_{\mathbb{N}}|\Gamma)$ with
$\gamma^{\prime}(\mathbb{0})=id_{G}$ such that $\eta\circ
h=\eta\circ\gamma^{\prime}$.

Setting $\gamma:=\gamma_{0}\gamma^{\prime}$ and
$g^{\prime}:=\tilde{g}\gamma^{-1}$, it is not hard to see that
$\gamma\in\text{poly}(\tau(\Omega)\to G_{\mathbb{N}}|\Gamma)$ and
$g^{\prime}\in\text{poly}(\mathbb{Z}^{d}\to G_{\mathbb{N}})$. Moreover, since
$\tilde{g}(\mathbb{0})=\gamma_{0}(\mathbb{0})=\gamma^{\prime}(\mathbb{0})=id_{G}$,
we have that $g^{\prime}(\mathbb{0})=\gamma(\mathbb{0})=id_{G}$. Note that

$\eta\circ
g^{\prime}(n)=\eta\circ\tilde{g}(n)-\eta\circ\gamma_{0}(n)-\eta\circ\gamma^{\prime}(n)=\eta\circ
h(n)-\eta\circ\gamma^{\prime}(n)=0.$

So $g^{\prime}\in\text{poly}(\mathbb{Z}^{d}\to G^{\prime}_{\mathbb{N}})$.
Finally, for all $m,n\in\tau(\Omega)+p\mathbb{Z}^{d}$, we have that

$g^{\prime}(n+pm)^{-1}g^{\prime}(n)=\gamma(n+pm)\tilde{g}(n+pm)^{-1}\tilde{g}(n)\gamma(n)^{-1}.$

Since all of $\gamma(n+pm)$, $\tilde{g}(n+pm)^{-1}\tilde{g}(n)$ and
$\gamma(n)^{-1}$ belong to $\Gamma$, we have that
$g^{\prime}(n+pm)^{-1}g^{\prime}(n)\in\Gamma$. Therefore, we have that
$g^{\prime}\in\text{poly}_{p}(\tau(\Omega)\to
G^{\prime}_{\mathbb{N}}|\Gamma^{\prime})$. Since $\tilde{g}=g^{\prime}\gamma$,
we are done by composing both sides by $\tau$. ∎

By repeatedly using Proposition 11.1, we get the following strong
factorization property:

######  Theorem 11.2 (Strong factorization property for nice $M$-sets).

Let $d,k\in\mathbb{N}_{+},r,s\in\mathbb{N}$, $C>0$,
$\mathcal{F}\colon\mathbb{R}_{+}\to\mathbb{R}_{+}$ be a growth function,
$p\gg_{C,d,\mathcal{F},k,r,s}1$ be a prime,
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a quadratic form, and
$\Omega\subseteq(\mathbb{F}_{p}^{d})^{k}$ satisfying one of the following
assumptions:

  1. (i)

$r=0$ and $\Omega=(\mathbb{F}_{p}^{d})^{k}$;

  2. (ii)

$k=1,r=0$ and $\Omega=V(M)\cap(V+c)$ for some affine subspace $V+c$ of
$\mathbb{F}_{p}^{d}$ with $\text{rank}(M|_{V+c})\geq s+13$;

  3. (iii)

$M$ is non-degenerate, $d\geq\max\\{4r+1,4k+3,2k+s+11\\}$ and $\Omega$ is a
nice and consistent $M$-set of total co-dimension $r$.

Let $G/\Gamma$ be an $s$-step $\mathbb{N}$-filtered nilmanifold of complexity
at most $C$, and let $g\in\text{poly}_{p}(\Omega\to G_{\mathbb{N}}|\Gamma)$.
There exist some $C\leq C^{\prime}\leq O_{C,d,\mathcal{F},k,r,s}(1)$, a proper
subgroup $G^{\prime}$ of $G$ which is $C^{\prime}$-rational relative to
$\mathcal{X}$, and a factorization

$g(n)=\epsilon g^{\prime}(n)\gamma(n)\text{ for all }n\in\mathbb{F}_{p}^{d}$

such that $\epsilon\in G$ is of complexity $O_{C^{\prime}}(1)$,
$g^{\prime}\in\text{poly}_{p}(\Omega\to
G^{\prime}_{\mathbb{N}}|\Gamma^{\prime})$, $g^{\prime}(\mathbb{0})=id_{G}$ and
$(g^{\prime}(n)\Gamma)_{n\in\Omega}$ is
$\mathcal{F}(C^{\prime})^{-1}$-equidistributed on
$G^{\prime}/\Gamma^{\prime}$, where $\Gamma^{\prime}:=G^{\prime}\cap\Gamma$,
and that $\gamma\in\text{poly}(\Omega\to G_{\mathbb{N}}|\Gamma)$,
$\gamma(\mathbb{0})=id_{G}$.

###### Proof.

The method is similar to the proof of Theorem 1.19 of [8]. Throughout the
proof, we assume that $p\gg_{C,d,\mathcal{F},k,r,s}1$. Enlarging $C$ if
necessary, we may assume without loss of generality that $\mathcal{F}(C)>2$.
By Theorem 10.2, 10.3 or 10.5, $\Omega$ is a non-empty set which admits an
$(\mathcal{F}(C)^{-1},O_{C,d,\mathcal{F},k,r,s}(1))$-Leibman dichotomy up to
step $s$ and complexity $C$. So by Proposition 11.1, either
$(g(n)\Gamma)_{n\in\Omega}$ is $\mathcal{F}(C)^{-1}$-equidistributed, or we
may write

$g(n)=\epsilon_{1}g_{1}(n)\gamma_{1}(n)\text{ for all }n\in\mathbb{F}_{p}^{d}$

such that $\epsilon_{1}\in G$ is of complexity at most 1,
$g_{1}\in\text{poly}_{p}(\Omega\to(G_{1})_{\mathbb{N}}|\Gamma_{1})$,
$g_{1}(\mathbb{0})=id_{G}$ for some proper subgroup $G_{1}$ of $G$ which is
$O_{C,d,\mathcal{F},k,r,s}(1)$-rational relative to $\mathcal{X}$ and whose
total dimension is less than that of $G$, and that
$\gamma_{1}\in\text{poly}(\Omega\to G_{\mathbb{N}}|\Gamma)$,
$\gamma_{1}(\mathbb{0})=id_{G}$. Let $\Gamma_{1}:=G_{1}\cap\Gamma$. By Lemma
A.10 of [8], $G_{1}/(G_{1}\cap\Gamma)$ admits a $C_{1}$-rational Mal’cev basis
for some $C_{1}=O_{C,d,\mathcal{F},k,r,s}(1)$.

By Theorem 10.2, 10.3 or 10.5, $\Omega$ admits an
$(\mathcal{F}(C_{1})^{-1},O_{C,d,\mathcal{F},k,r,s}(1))$-Leibman dichotomy up
to step $s$ and complexity $C_{1}$. So by Proposition 11.1, either
$(g_{1}(n)\Gamma)_{n\in\Omega}$ is $\mathcal{F}(C_{1})^{-1}$-equidistributed
on $G_{1}/\Gamma_{1}$, or we may write

$g_{1}(n)=\epsilon_{2}g_{2}(n)\gamma_{2}(n)\text{ for all
}n\in\mathbb{F}_{p}^{d}$

such that $\epsilon_{2}\in G_{1}$ is of complexity at most 1,
$g_{2}\in\text{poly}_{p}(\Omega\to(G_{2})_{\mathbb{N}}|\Gamma_{2})$,
$g_{2}(\mathbb{0})=id_{G}$ for some proper subgroup $G_{2}$ of $G_{1}$ which
is $O_{C,d,\mathcal{F},k,r,s}(1)$-rational relative to $\mathcal{X}$ and whose
total dimension is less than that of $G_{1}$, and that
$\gamma_{2}\in\text{poly}(\Omega\to G_{\mathbb{N}}|\Gamma)$,
$\gamma_{2}(\mathbb{0})=id_{G}$. Since $\epsilon_{2}\in G_{1}$ is of
complexity at most 1, we have that $\epsilon_{2}$ is of complexity
$O_{C_{1}}(1)$ as an element of $G$. Let $\Gamma_{2}:=G_{2}\cap\Gamma$. By
Lemma A.10 of [8], $G_{2}/(G_{2}\cap\Gamma)$ admits a $C_{2}$-rational Mal’cev
basis for some $C_{2}=O_{C,d,\mathcal{F},k,r,s}(1)$. We may also require that
$C_{2}\geq C_{1}$.

We may continue this process to get a sequence $C\leq C_{1}\leq
C_{2}\leq\dots$. Since this iteration will terminate after at most $O_{C}(1)$
steps, we can find $1\leq t\leq O_{C}(1)$, some $C\leq C_{t}\leq
O_{C,d,\mathcal{F},k,r,s}(1)$, and a factorization

$g(n)=\epsilon_{1}\dots\epsilon_{t}g_{t}(n)\gamma_{1}(n)\dots\gamma_{t}(n)\text{
for all }n\in\mathbb{F}_{p}^{d}$

$\epsilon_{1},\dots,\epsilon_{t}\in G$ are of complexities at most
$O_{C_{t}}(1)$,
$g_{t}\in\text{poly}_{p}(\Omega\to(G_{t})_{\mathbb{N}}|\Gamma_{t})$,
$g_{t}(\mathbb{0})=id_{G}$ for some proper subgroup $G_{t}$ of $G$ which is
$C_{t}$-rational relative to $\mathcal{X}$ and $(g_{t}(n)\Gamma)_{n\in\Omega}$
is $\mathcal{F}(C_{t})^{-1}$-equidistributed on $G_{t}/\Gamma_{t}$ (where
$\Gamma_{t}:=G_{t}\cap\Gamma$), and that $\gamma_{i}\in\text{poly}(\Omega\to
G_{\mathbb{N}}|\Gamma)$, $\gamma_{i}(\mathbb{0})=id_{G}$ for $1\leq i\leq t$.
We are done by setting $C=C_{t}$, $\epsilon=\epsilon_{1}\dots\epsilon_{t}$,
$g^{\prime}=g_{t}$ and $\gamma=\gamma_{1}\dots\gamma_{t}$ (since it is not
hard to see from Lemma A.3 of [8] that $\epsilon$ is of complexity
$O_{t,C_{t}}(1)=O_{C_{t}}(1)$). ∎

######  Remark 11.3.

It is tempting to conjecture that in Theorems 11.2, if
$g\in\text{poly}_{p}(\mathbb{F}_{p}^{d}\to G_{\mathbb{N}}|\Gamma)$, then one
can further require $g^{\prime}\in\text{poly}_{p}(\mathbb{F}_{p}^{d}\to
G^{\prime}_{\mathbb{N}}|\Gamma^{\prime})$. However, we were unable to prove
it. The difficulty is that even if we start with some $p$-periodic $g$, the
polynomial sequence $g^{\prime}$ obtained in Proposition 11.1 is not
necessarily $p$-periodic (we can only make $g^{\prime}$ to be partially
$p$-periodic on $\Omega$). This is a major reason why we need to prove most of
the results in this paper for the partially $p$-periodic polynomials.

##  12\. Open questions

We collect some open questions in this section. Recall that we need to require
$d\geq s+13$ in Theorem 1.1. It is natural to ask:

######  Question 12.1.

What is the optimal lower bound for the dimension $d$ in Theorem 1.1?

In order to improve the lower bound of $d$ in Theorem 1.1, it is natural to
attempt to sharpen the tools we used in proving Theorem 1.1. Therefore, one
can ask:

######  Question 12.2.

What are the optimal lower bounds for the dimension $d$ in Proposition 6.8,
Theorems 9.14, 10.5, and C.3?

Let $M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a quadratic form. It is an
interesting question to ask what is the connection between $p$-periodic
polynomial sequences on $\mathbb{F}_{p}^{d}$ and partially $p$-periodic
polynomial sequences on $V(M)$. In particular, is it true that a partially
$p$-periodic polynomial sequence on $V(M)$ merely the restriction to $V(M)$ of
a $p$-periodic polynomial sequences on $\mathbb{F}_{p}^{d}$?

######  Question 12.3.

Let $d,s\in\mathbb{N}_{+}$, $p$ be a prime,
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a quadratic form of rank at
least 3, and $G_{\mathbb{N}}$ be a nilpotent group of step $s$. Let
$p\gg_{d,s}1$. For all $g\in\text{poly}_{p}(V(M)\to G_{\mathbb{N}}|\Gamma)$,
is there any $g^{\prime}\in\text{poly}_{p}(\mathbb{F}_{p}^{d}\to
G_{\mathbb{N}}|\Gamma)$ such that $g(n)\Gamma=g^{\prime}(n)\Gamma$ for all
$n\in V(M)$?

Another interesting question is to ask if there is an intrinsic definition for
partially $p$-periodic polynomials on $V(M)$. This is Conjecture 6.9 which we
restate below:

######  Question 12.4.

Let $g\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a function,
$d,s\in\mathbb{N}_{+}$ and $p\gg_{d}1$ be a prime. Let
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a quadratic form with
$\text{rank}(M)\gg_{s}1$. Are the followings equivalent?

  1. (i)

$\Delta_{h_{s}}\dots\Delta_{h_{1}}g(n)=0$ for all
$(n,h_{1},\dots,h_{s})\in\Box_{s}(V(M))$.

  2. (ii)

There exists a polynomial
$g^{\prime}\in\text{poly}(\mathbb{F}_{p}^{d}\to\mathbb{F}_{p})$ of degree at
most $s-1$ such that $g(n)=g^{\prime}(n)$ for all $n\in V(M)$.

As is mentioned in Section 6.4, we were only able to answer a special case of
this question.

Another interesting question in algebra is that whether all the nice and
consistent $M$-sets satisfy Hilbert Nullstellensatz. This is Conjecture D.9
which we restate below:

######  Question 12.5.

Let $d,k\in\mathbb{N}_{+}$, $s\in\mathbb{N}$, $p$ be a prime,
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a non-degenerate quadratic
form, and $\Omega\subseteq(\mathbb{F}_{p}^{d})^{k}$ be a consistent $M$-set
given by $\Omega=V(\mathcal{J})$ for some consistent $(M,k)$-family
$\mathcal{J}=\\{f_{1},\dots,f_{r}\\}$ for some $r\in\mathbb{N}_{+}$. If
$d\gg_{k,r,s}1$ and $p\gg_{d}1$, then for any polynomial
$P\in\text{poly}((\mathbb{F}_{p}^{d})^{k}\to\mathbb{F}_{p})$ of degree at most
$s$ with $\Omega\subseteq V(P)$, can we write

$P=\sum_{j=1}^{r}f_{j}Q_{j}$

for some polynomial $Q_{j}$ of degree $O_{k,r,s}(1)$?

In Appendix D, We prove a weaker version of Conjecture D.9 in Proposition
D.10. Also it is proved in Proposition 6.3 that Conjecture D.9 holds for
$\Omega=V(M)$. But the general case remains unanswered.

Finally, it is an important question to ask whether the factorization theorems
holds in the setting of $p$-periodic polynomial sequences.

######  Question 12.6.

In Proposition 11.1 and Theorem 11.2, if we assume in addition that $g$ is
$p$-periodic, then can we also require $g^{\prime}$ to be $p$-periodic in the
factorization of $g$?

If the answer to Question 12.6 is affirmative, then many arguments in this
paper as well as in [18, 19] can be greatly simplified by restricting
ourselves to $p$-periodic polynomial sequences.

##  Appendix A Properties for liftings of polynomials

In this appendix, we provide some basic properties for liftings of
polynomials.

######  Lemma A.1 (Basic properties for lifting).

Let $d,d^{\prime},d^{\prime\prime}\in\mathbb{N}_{+}$ and
$p>\max\\{d,d^{\prime},d^{\prime\prime}\\}$ be a prime.

  1. (i)

Every $f\in\text{poly}(\mathbb{Z}^{d}\to(\mathbb{Z}/p)^{d^{\prime}})$ of
degree less than $p$ induces $\iota\circ pf\circ\tau$, which is a polynomial
of degree at most $\deg(f)$. Moreover, if $f$ is homogeneous, then so is
$\iota\circ pf\circ\tau$;

  2. (ii)

Every $F\in\text{poly}(\mathbb{F}_{p}^{d}\to\mathbb{F}^{d^{\prime}}_{p})$ of
degree less than $p$ admits a regular lifting. Moreover, if $F$ is
homogeneous, we may further require the lifting to be homogeneous;

  3. (iii)

If $f\in\text{poly}(\mathbb{Z}^{d}\to(\mathbb{Z}/p)^{d^{\prime}})$ is a
lifting of some
$F\in\text{poly}(\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}^{d^{\prime}})$ with both
$f$ and $F$ having degrees at most $p-1$, then for any
$f^{\prime}\in\text{poly}(\mathbb{Z}^{d}\to(\mathbb{Z}/p)^{d^{\prime}})$ of
degree less than $p$, $f^{\prime}$ is a lifting of $F$ if and only if
$f-f^{\prime}$ is integer valued;

  4. (iv)

If $f,f^{\prime}\in\text{poly}(\mathbb{Z}^{d}\to(\mathbb{Z}/p)^{d^{\prime}})$
are liftings of
$F,F^{\prime}\in\text{poly}(\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}^{d^{\prime}})$
respectively with all of $f,f^{\prime},F$ and $F^{\prime}$ having degrees at
most $(p-1)/2$, then $f+f^{\prime}$ is a lifting of $F+F^{\prime}$ and
$pff^{\prime}$ is a lifting of $FF^{\prime}$;

  5. (v)

If $f\in\text{poly}(\mathbb{Z}^{d}\to(\mathbb{Z}/p)^{d^{\prime}})$ is a
lifting of some
$F\in\text{poly}(\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}^{d^{\prime}})$ with both
$f$ and $F$ having degree at most $\sqrt{p}$, and
$f\in\text{poly}(\mathbb{Z}^{d^{\prime}}\to(\mathbb{Z}/p)^{d^{\prime\prime}})$
is a lifting of some
$F\in\text{poly}(\mathbb{F}_{p}^{d^{\prime}}\to\mathbb{F}_{p}^{d^{\prime\prime}})$
with both $f$ and $F$ having degrees less than $\sqrt{p}$, then
$f^{\prime}\circ pf$ is a lifting of $F^{\prime}\circ F$;

  6. (vi)

If $f\in\text{poly}(\mathbb{Z}^{d}\to(\mathbb{Z}/p)^{d^{\prime}})$ is a
lifting of some
$F\in\text{poly}(\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}^{d^{\prime}})$ with both
$f$ and $F$ having degrees less than $p$, then $\tau\circ F\equiv
pf\circ\tau\mod\mathbb{Z}^{d^{\prime}}$.

###### Proof.

Part (i). Since $f$ takes values in $(\mathbb{Z}/p)^{d^{\prime}}$, by the
multivariate polynomial interpolation, there exists $Q\in\mathbb{N},p\nmid Q$
such that

$f(n_{1},\dots,n_{d}):=\sum_{0\leq a_{1},\dots,a_{d}\leq
p-1,a_{i}\in\mathbb{N}}\frac{C_{a_{1},\dots,a_{d}}}{Qp^{s}}n^{a_{1}}_{1}\dots
n^{a_{d-1}}_{d}$

for some $C_{a_{1},\dots,a_{d}}\in\mathbb{Z}^{d^{\prime}}$ and
$s\in\mathbb{N}$. Using the property that
$f(n+pm)-f(n)\in\mathbb{Z}^{d^{\prime}}$ for all $m,n\in\mathbb{Z}^{d}$, it is
not hard to see that we may further write $f$ as

$f(n_{1},\dots,n_{d}):=\sum_{0\leq a_{1},\dots,a_{d}\leq
p-1,a_{i}\in\mathbb{N}}\frac{C^{\prime}_{a_{1},\dots,a_{d}}}{Qp}n^{a_{1}}_{1}\dots
n^{a_{d-1}}_{d}$

for some $C^{\prime}_{a_{1},\dots,a_{d}}\in\mathbb{Z}^{d^{\prime}}$ and
$Q\in\mathbb{N},p\nmid Q$. Let
$C^{\prime\prime}_{a_{1},\dots,a_{d}}\in\\{0,\dots,p-1\\}^{d^{\prime}}$ be
such that $C^{\prime\prime}_{a_{1},\dots,a_{d}}Q\equiv
C^{\prime}_{a_{1},\dots,a_{d}}\mod p\mathbb{Z}^{d^{\prime}}$. Denote
$f^{\prime}\colon\mathbb{Z}^{d}\to(\mathbb{Z}/p)^{d^{\prime}}$,

$f^{\prime}(n_{1},\dots,n_{d}):=\sum_{0\leq a_{1},\dots,a_{d}\leq
p-1,a_{i}\in\mathbb{N}}\frac{C^{\prime\prime}_{a_{1},\dots,a_{d}}}{p}n^{a_{1}}_{1}\dots
n^{a_{d-1}}_{d}.$

and $F\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}^{d^{\prime}}$,

$F(n_{1},\dots,n_{d}):=\sum_{0\leq a_{1},\dots,a_{d}\leq
p-1,a_{i}\in\mathbb{N}}\iota(C^{\prime\prime}_{a_{1},\dots,a_{d}})n^{a_{1}}_{1}\dots
n^{a_{d-1}}_{d}.$

Since
$f(n)-f^{\prime}(n)\in(\mathbb{Z}^{d^{\prime}}/Q)\cap(\mathbb{Z}^{d^{\prime}}/p^{d^{\prime}})=\mathbb{Z}^{d^{\prime}}$
for all $n\in\mathbb{Z}^{d}$, we have that $\iota\circ pf\circ\tau=\iota\circ
pf^{\prime}\circ\tau=F$ is a well defined polynomial in
$\text{poly}(\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}^{d^{\prime}})$. It is also
clear that the degree of $F$ is at most $\deg(f)$, and that $F$ is homogeneous
if $f$ is homogeneous.

Part (ii). Assume that

$F(n_{1},\dots,n_{d})=\sum_{0\leq a_{1},\dots,a_{d}\leq
p-1,a_{i}\in\mathbb{N}}C_{a_{1},\dots,a_{d}}n^{a_{1}}_{1}\dots
n^{a_{d-1}}_{d}$

for some $C_{a_{1},\dots,a_{d}}\in\mathbb{F}_{p}^{d^{\prime}}$. Let

$f(n_{1},\dots,n_{d}):=\sum_{0\leq a_{1},\dots,a_{d}\leq
p-1,a_{i}\in\mathbb{N}}C^{\prime}_{a_{1},\dots,a_{d}}n^{a_{1}}_{1}\dots
n^{a_{d-1}}_{d},$

where $C^{\prime}_{a_{1},\dots,a_{d}}$ is any element in
$\\{0,\frac{1}{p},\dots,\frac{p-1}{p}\\}^{d^{\prime}}$ such that
$\iota(pC^{\prime}_{a_{1},\dots,a_{d}})=C_{a_{1},\dots,a_{d}}$. Then it is
easy to check that $f$ is a regular lifting of $F$. Moreover, $f$ is
homogeneous if $F$ is homogeneous.

Part (iii). Suppose first that $f^{\prime}$ is a lifting of $F$. Note that
both $f$ and $f^{\prime}$ are $p$-periodic by Lemma 2.7. Then $\iota\circ
pf\circ\tau=F=\iota\circ pf^{\prime}\circ\tau$. So
$pf(\tau(n))-pf^{\prime}(\tau(n))\in p\mathbb{Z}^{d^{\prime}}$. This implies
that $f(m)-f^{\prime}(m)\in\mathbb{Z}^{d^{\prime}}$ for all
$m\in\tau(\mathbb{F}_{p})=\\{0,\dots,p-1\\}^{d}$. Since $f-f^{\prime}$ is
$p$-periodic, we have that $f(m)-f^{\prime}(m)\in\mathbb{Z}^{d^{\prime}}$ for
all $m\in\mathbb{Z}^{d}$.

Conversely, if $f(m)-f^{\prime}(m)\in\mathbb{Z}^{d^{\prime}}$ for all
$m\in\mathbb{Z}^{d}$, then $pf(\tau(n))-pf^{\prime}(\tau(n))\in
p\mathbb{Z}^{d^{\prime}}$ and thus $\iota\circ
pf^{\prime}\circ\tau(n)=\iota\circ pf\circ\tau(n)=F(n)$.

Part (iv). It is clear that both $f+f^{\prime}$ and $pff^{\prime}$ have
degrees less than $p$. The conclusion follows from the fact that

$\iota\circ pf\circ\tau+\iota\circ pf\circ\tau=\iota\circ
p(f+f^{\prime})\circ\tau\text{ and }(\iota\circ pf\circ\tau)\cdot(\iota\circ
pf\circ\tau)=\iota\circ p^{2}ff^{\prime}\circ\tau.$

Part (v). It is clear that $f^{\prime}\circ
pf\in\text{poly}(\mathbb{Z}^{d}\to(\mathbb{Z}/p)^{d^{\prime\prime}})$ and
$F^{\prime}\circ
F\in\text{poly}(\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}^{d^{\prime\prime}})$, both
of which are of degree less than $p$. Since $\tau\circ\iota\equiv id\mod
p\mathbb{Z}$, we have that $pf^{\prime}\equiv
pf^{\prime}\circ\tau\circ\iota\mod p\mathbb{Z}^{d^{\prime}}$ and thus

$\iota\circ pf^{\prime}\circ
pf\circ\tau=\iota\circ(pf^{\prime}\circ\tau\circ\iota)\circ
pf\circ\tau=(\iota\circ pf^{\prime}\circ\tau)\circ(\iota\circ
pf\circ\tau)=F^{\prime}\circ F.$

So $f^{\prime}\circ pf$ is a lifting of $F^{\prime}\circ F$.

Part (vi). Since $\tau\circ\iota\equiv id\mod p$, we have that

$\tau\circ F=\tau\circ(\iota\circ pf\circ\tau)=(\tau\circ\iota)\circ
pf\circ\tau\equiv pf\circ\tau\mod p\mathbb{Z}^{d^{\prime}}.$

∎

##  Appendix B Properties for $M$-sets

In this appendix, we provide some elementary properties for $M$-sets. We also
present some important examples of $M$-sets which will be used in [17, 18,
19].

We start with the following lemma on the existence of $M$-representations.

######  Lemma B.1.

Let $d\in\mathbb{N}_{+},r\in\mathbb{N}$, $p$ be a prime, and
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a quadratic form. For any
consistent $(M,k)$-family $\mathcal{J}=\\{F_{1},\dots,F_{r}\\}$, the set
$\Omega:=V(\mathcal{J})$ admits a standard $M$-representation
$(F^{\prime}_{1},\dots,F^{\prime}_{r^{\prime}})$ for some
$r^{\prime}\in\mathbb{N}$.

Moreover, if $\mathcal{J}$ is independent, then we may further require
$r^{\prime}=r$; if $\mathcal{J}$ is nice/pure, then we may further require
$F^{\prime}_{1},\dots,F^{\prime}_{r^{\prime}}$ to be nice/pure.

###### Proof.

We may assume without loss of generality that
$v_{M}(F_{1}),\dots,v_{M}(F_{r^{\prime}})$ is a basis of
$\text{span}_{\mathbb{F}_{p}}\\{v_{M}(F_{1}),\dots,v_{M}(F_{r})\\}$ for some
$1\leq r^{\prime}\leq r$. Fix $r^{\prime}+1\leq i\leq r$. There exist
$t_{1},\dots,t_{r^{\prime}}\in\mathbb{F}_{p}$ such that

$\begin{split}t_{1}v_{M}(F_{1})+\dots+t_{r^{\prime}}v_{M}(F_{r^{\prime}})-v_{M}(F_{i})=\mathbb{0}.\end{split}$

Therefore,

$\begin{split}t_{1}F_{1}+\dots+t_{r^{\prime}}F_{r^{\prime}}-F_{i}\equiv
0.\end{split}$

So $V(F_{i})\subseteq\cap_{j=1}^{r^{\prime}}V(F_{j})$ and thus
$\Omega=\cap_{j=1}^{r^{\prime}}V(F_{j}).$
$\\{F_{i}\colon(\mathbb{F}_{p}^{d})^{k}\to\mathbb{F}_{p}^{d}\colon 1\leq i\leq
r\\}$ is consistent, so is
$\\{F_{i}\colon(\mathbb{F}_{p}^{d})^{k}\to\mathbb{F}_{p}^{d}\colon 1\leq i\leq
r^{\prime}\\}$. Also since $v_{M}(F_{1}),\dots,v_{M}(F_{r^{\prime}})$ are
linearly independent, the matrix $\begin{bmatrix}v_{M}(F_{1})\\\ \dots\\\
v_{M}(F_{r^{\prime}})\end{bmatrix}$ is of rank $r^{\prime}$ and does not
contain a row of the form $(0,\dots,0,a),a\in\mathbb{F}_{p}$. We remark that
one can choose $r^{\prime}=r$ if $\mathcal{J}$ is independent.

Let $X=(x_{i,j})_{1\leq i,j\leq r^{\prime}}$ be an $r^{\prime}\times
r^{\prime}$ invertible matrix and denote
$F^{\prime}_{i}:=\sum_{j=1}^{r^{\prime}}x_{i,j}F_{j}$ for $1\leq i\leq
r^{\prime}$. Then clearly
$\text{span}_{\mathbb{F}_{p}}\\{v_{M}(F^{\prime}_{i}),1\leq i\leq
r^{\prime}\\}=\text{span}_{\mathbb{F}_{p}}\\{v_{M}(F_{i}),1\leq i\leq r\\}$
and $\Omega=\cap_{j=1}^{r^{\prime}}V(F^{\prime}_{j}).$ Since the matrix
$\begin{bmatrix}v_{M}(F_{1})\\\ \dots\\\ v_{M}(F_{r^{\prime}})\end{bmatrix}$
is of rank $r^{\prime}$ and does not contain a row of the form
$(0,\dots,0,a),a\in\mathbb{F}_{p}$, we may choose $X$ in a way such that the
matrix $\begin{bmatrix}v_{M}(F^{\prime}_{1})\\\ \dots\\\
v_{M}(F^{\prime}_{r^{\prime}})\end{bmatrix}$ is in the reduced row echelon
form which does not contain a row of the form
$(0,\dots,0,a),a\in\mathbb{F}_{p}$. So
$v^{\prime}_{M}(F^{\prime}_{1}),\dots,v^{\prime}_{M}(F^{\prime}_{r^{\prime}})$
are linearly independent and thus
$(F^{\prime}_{1},\dots,F^{\prime}_{r^{\prime}})$ is a standard
$M$-representation of $\Omega$.

Moreover, if $\mathcal{J}$ is nice/pure, then all of
$F_{1},\dots,F_{r^{\prime}}$ are nice/pure. By the knowledge of linear
algebra, it is not hard to see that we may choose $X$ in a way such that
$F^{\prime}_{1},\dots,F^{\prime}_{r^{\prime}}$ are also nice/pure. This
completes the proof. ∎

We next provide some basic properties for different notions of $M$-sets.

######  Corollary B.2.

Let $d\in\mathbb{N}_{+}$, $p$ be a prime, and
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a quadratic form.

  1. (i)

Any independent $M$-family, $M$-set, or $M$-representation is also a
consistent $M$-family, $M$-set, or $M$-representation respectively.

  2. (ii)

Non-consistent $M$-sets are empty.272727Conversely, by Theorem C.3 to be
proved later in this paper, consistent $M$-sets are non-empty provided that
$d$ and $p$ are sufficiently large.

  3. (iii)

Any consistent $M$-set $\Omega$ admits a standard $M$-representation (so
consistent $M$-sets are the same as independent $M$-sets).

###### Proof.

Part (i) follows from the definitions. For Part (ii), if
$\Omega=\cap_{i=1}^{r}V(F_{i})$ for some non-consistent $(M,k)$-family
$\\{F_{1},\dots,F_{r}\\}$, then 1 is a linear combination of
$F_{1},\dots,F_{r}$. So $\Omega\subseteq V(1)=\emptyset$. Part (iii) follows
from Lemma B.1. ∎

The next proposition provides us some simple ways to construct new $M$-sets
from an existing one.

######  Proposition B.3.

Let $d,k,r\in\mathbb{N}_{+}$, $p$ be a prime,
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a quadratic form and
$\mathcal{J}=\\{F_{1},\dots,F_{r}\\},F_{i}\colon(\mathbb{F}_{p}^{d})^{k}\to\mathbb{F}_{p},1\leq
i\leq r$ be an $(M,k)$-family.

  1. (i)

For any subset $I\subseteq\\{1,\dots,r\\}$, $\\{F_{i}\colon i\in I\\}$ is an
$(M,k)$-family.

  2. (ii)

Let $I\subseteq\\{1,\dots,r\\}$ be a subset such that all of $F_{i},i\in I$
are independent of the last $d$-variables. Then writing
$G_{i}(n_{1},\dots,n_{k-1}):=F_{i}(n_{1},\dots,n_{k-1})$, we have that
$\\{G_{i}\colon i\in I\\}$ is an $(M,k-1)$-family.

  3. (iii)

For any bijective $d$-integral linear transformation
$L\colon(\mathbb{F}_{p}^{d})^{k}\to(\mathbb{F}_{p}^{d})^{k}$ and any
$v\in(\mathbb{F}_{p}^{d})^{k}$,
$\\{F_{1}(L(\cdot)+v),\dots,F_{r}(L(\cdot)+v)\\},F_{i}\colon(\mathbb{F}_{p}^{d})^{k}\to\mathbb{F}_{p},1\leq
i\leq r$ is an $(M,k)$-family.

  4. (iv)

Let $1\leq k^{\prime}\leq k$ and $1\leq r^{\prime}\leq r$ be such that
$F_{1},\dots,F_{r^{\prime}}$ are independent of
$n_{k-k^{\prime}+1},\dots,n_{r}$ and that every non-trival linear combination
of $F_{r^{\prime}+1},\dots,F_{r}$ dependents nontrivially on some of
$n_{k-k^{\prime}+1},\dots,n_{r}$. Define
$G_{i},H_{i}\colon(\mathbb{F}_{p}^{d})^{k+k^{\prime}}\to\mathbb{F}_{p},1\leq
i\leq r$ by

$\text{$G_{i}(n_{1},\dots,n_{k+k^{\prime}}):=F_{i}(n_{1},\dots,n_{k})$ and
$H_{i}(n_{1},\dots,n_{k+k^{\prime}}):=F_{i}(n_{1},\dots,n_{k-k^{\prime}},n_{k+1},\dots,n_{k+k^{\prime}})$}.$

Then
$\\{F_{1},\dots,F_{r^{\prime}},G_{r^{\prime}+1},\dots,G_{r},H_{r^{\prime}+1},\dots,H_{r}\\}$282828Here
we regard $F_{1},\dots,F_{r^{\prime}}$ as functions of
$n_{1},\dots,n_{k+k^{\prime}}$, which acutally depends only on
$n_{1},\dots,n_{k-k^{\prime}}$. is an $(M,k+k^{\prime})$-family.

Moreover, if $\mathcal{J}$ is nice, then so are the sets mentioned in Parts
(i)-(iii); if $\mathcal{J}$ is consistent/independent, then so are the sets
mentioned in Parts (i)-(iv); if $\mathcal{J}$ is pure, then so are the sets
mentioned in Parts (i), (ii), (iv), and so is the set mentioned in Part (iii)
when $v=\mathbb{0}$.

###### Proof.

We only need to show that if $\mathcal{J}$ is consistent/independent, then so
are the sets mentioned in Parts (i)-(iv), since the other parts are easy to
verify. For any $(M,k)$-integral quadratic function $G$, let
$G^{\prime\prime}$ denote the degree 2 terms of $G$, and $G^{\prime}$ denote
the degree 1 and 2 terms of $G$. Then an $(M,k)$-family
$\\{G_{1},\dots,G_{t}\\}$ is

  * •

consistent if and only if for all $c_{1},\dots,c_{t}\in\mathbb{F}_{p}$,
$c_{1}G^{\prime}_{1}+\dots+c_{t}G^{\prime}_{t}\equiv 0$ implies that
$c_{1}G_{1}+\dots+c_{t}G_{t}\equiv 0$;

  * •

independent if and only if for all $c_{1},\dots,c_{t}\in\mathbb{F}_{p}$,
$c_{1}G^{\prime}_{1}+\dots+c_{t}G^{\prime}_{t}\equiv 0$ implies that
$c_{1}=\dots=c_{t}=0$.

Parts (i) and (ii) are straightforward. We now prove Part (iii). Suppose first
that $\sum_{i=1}^{r}c_{i}(F_{i}(L(\cdot)+v))^{\prime}\equiv 0$ for some
$c_{1},\dots,c_{r}\in\mathbb{F}_{p}$. Since
$(F_{i}(L(\cdot)+v))^{\prime}-F^{\prime}_{i}(L(\cdot)+v)$ is a constant, so is
$\sum_{i=1}^{r}c_{i}F^{\prime}_{i}(L(\cdot)+v)$. Since $L$ is bijective, we
have that $\sum_{i=1}^{r}c_{i}F^{\prime}_{i}$ and thus
$\sum_{i=1}^{r}c_{i}F_{i}$ is a constant. If $\mathcal{J}$ is consistent, then
this implies that $\sum_{i=1}^{r}c_{i}F_{i}\equiv 0$ and thus
$\sum_{i=1}^{r}c_{i}(F_{i}(L(\cdot)+v))\equiv 0$. If $\mathcal{J}$ is
independent, then this implies that $c_{1}=\dots=c_{t}=0$. This proves Part
(iii).

For Part (iv), suppose first that

(B.1)
$\sum_{i=1}^{r^{\prime}}c_{i}F^{\prime}_{i}(n_{1},\dots,n_{k-k^{\prime}})+\sum_{i=r^{\prime}+1}^{r}(c^{\prime}_{i}G^{\prime}_{i}+c^{\prime\prime}_{i}H^{\prime}_{i})(n_{1},\dots,n_{k+k^{\prime}})\equiv
0$

for some $c_{i},c^{\prime}_{i},c^{\prime}_{i}\in\mathbb{F}_{p}$. Setting
$n_{k-k^{\prime}+j}=n_{k+j}$ for all $1\leq j\leq k^{\prime}$, we have that

(B.2)
$\sum_{i=1}^{r^{\prime}}c_{i}F^{\prime}_{i}(n_{1},\dots,n_{k-k^{\prime}})+\sum_{i=r^{\prime}+1}^{r}(c^{\prime}_{i}+c^{\prime\prime}_{i})F^{\prime}_{i}(n_{1},\dots,n_{k})\equiv
0.$

If $\mathcal{J}$ is consistent, then (B.2) implies that
$\sum_{i=1}^{r^{\prime}}c_{i}(F_{i}-F^{\prime}_{i})+\sum_{i=r^{\prime}+1}^{r}(c^{\prime}_{i}+c^{\prime\prime}_{i})(F_{i}-F^{\prime}_{i})\equiv
0$. Since $F_{i}-F^{\prime}_{i}=G_{i}-G^{\prime}_{i}=H_{i}-H^{\prime}_{i}$, we
have that

$\sum_{i=1}^{r^{\prime}}c_{i}(F_{i}-F^{\prime}_{i})(n_{1},\dots,n_{k-k^{\prime}})+\sum_{i=r^{\prime}+1}^{r}(c^{\prime}_{i}(G_{i}-G^{\prime}_{i})+c^{\prime\prime}_{i}(H_{i}-H^{\prime}_{i}))(n_{1},\dots,n_{k+k^{\prime}})\equiv
0.$

It then follows from (B.1) that

$\sum_{i=1}^{r^{\prime}}c_{i}F_{i}(n_{1},\dots,n_{k-k^{\prime}})+\sum_{i=r^{\prime}+1}^{r}(c^{\prime}_{i}G_{i}+c^{\prime\prime}_{i}H_{i})(n_{1},\dots,n_{k+k^{\prime}})\equiv
0.$

So
$\\{F_{1},\dots,F_{r^{\prime}},G_{r^{\prime}+1},\dots,G_{r},H_{r^{\prime}+1},\dots,H_{r}\\}$
is consistent.

If $\mathcal{J}$ is independent, then (B.2) implies that
$c_{1}=\dots=c_{r^{\prime}}=c^{\prime}_{r^{\prime}+1}+c^{\prime\prime}_{r^{\prime}+1}=\dots=c^{\prime}_{r}+c^{\prime\prime}_{r}=0$.
Substituting this back to (B.1), we have that

$\sum_{i=r^{\prime}+1}^{r}c^{\prime}_{i}F^{\prime}_{i}(n_{1},\dots,n_{k})\equiv-\sum_{i=r^{\prime}+1}^{r}c^{\prime}_{i}F^{\prime}_{i}(n_{1},\dots,n_{k-k^{\prime}},n_{k+1}\dots,n_{k+k^{\prime}}).$

This implies that
$\sum_{i=r^{\prime}+1}^{r}c^{\prime}_{i}F^{\prime}_{i}(n_{1},\dots,n_{k})$ is
independent of $n_{k-k^{\prime}+1},\dots,n_{r}$. If
$c^{\prime}_{r^{\prime}+1},\dots,c^{\prime}_{r}$ are not all zero, by
assumption, $\sum_{i=r^{\prime}+1}^{r}c^{\prime}_{i}F_{i}(n_{1},\dots,n_{k})$
and thus
$\sum_{i=r^{\prime}+1}^{r}c^{\prime}_{i}F^{\prime}_{i}(n_{1},\dots,n_{k})$
dependents nontrivially on $n_{k-k^{\prime}+1},\dots,n_{r}$, a contradiction.
So $c^{\prime}_{r^{\prime}+1}=\dots=c^{\prime}_{r}=0$ and thus
$c^{\prime\prime}_{r^{\prime}+1}=\dots=c^{\prime\prime}_{r}=0$. So
$\\{F_{1},\dots,F_{r^{\prime}},G_{r^{\prime}+1},\dots,G_{r},H_{r^{\prime}+1},\dots,H_{r}\\}$
is independent. ∎

Finally, we provide some examples of nice $M$-sets which will be used in [17,
18, 19].

######  Example B.4.

Let $d\in\mathbb{N}_{+}$, $s\in\mathbb{N}$, $p$ be a prime, and
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a non-degenerate quadratic
form associated with the matrix $A$. Clearly, we may write

(B.3) $V(M)=V(M^{\prime})+b$

for some pure non-degenerate quadratic form
$M^{\prime}\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ of the form
$M^{\prime}(n)=(nA)\cdot n+c$ for some $c\in\mathbb{F}_{p}$, for and some
$b\in\mathbb{F}_{p}^{d}$.

  * •

The set $\mathbb{F}_{p}^{d}$ is a nice and consistent $M$-set of total co-
dimension 0 by Convention 9.3.

  * •

The set $V(M)\subseteq\mathbb{F}_{p}^{d}$ is a nice and consistent $M$-set of
total co-dimension 1, since $M^{\prime}$ is pure.

  * •

The Gowers set $\Box_{s}(V(M))$ is a nice and consistent $M$-set. To see this,
note that
$\Box_{s}(V(M))=\Box_{s}(V(M^{\prime}))+(b,\mathbb{0},\dots,\mathbb{0})$. Let
$L\colon(\mathbb{F}_{p}^{d})^{s+1}\to(\mathbb{F}_{p}^{d})^{s+1}$ be the
bijective $d$-integral linear transformation given by
$L(n,h_{1},\dots,h_{s}):=(h_{1},\dots,h_{s},n)$. By Lemma 4.18,
$(h_{1},\dots,h_{s},n)\in L(\Box_{s}(V(M^{\prime})))$ if and only if
$M^{\prime}(n),M^{\prime}(n+h_{i})-M^{\prime}(n),(h_{i}A)\cdot h_{j}=0$ for
all $1\leq i,j\leq s,i\neq j$. Since all of these functions forms a nice and
independent $M$-family, we have that $L(\Box_{s}(V(M^{\prime})))$ is a nice
and consistent $M$-set of total co-dimension $(s^{2}+s+2)/2$, and thus so is
$\Box_{s}(V(M))$ by Proposition B.3 (iii).

  * •

The set

$\Omega_{1}:=\\{(x_{1},\dots,x_{5})\in(\mathbb{F}_{p}^{d})^{5}\colon
x_{1}-x_{i},x_{i}\in V(M),2\leq i\leq 5\\}$

is a nice and consistent $M$-set. To see this, note that
$\Omega_{1}=L(\Omega_{1}^{\prime})+(2b,b,b,b,b)$, where
$L\colon(\mathbb{F}_{p}^{d})^{5}\to(\mathbb{F}_{p}^{d})^{5}$ is given by
$L(x_{1},\dots,x_{5})=(x_{5},x_{1},\dots,x_{4})$ and $\Omega^{\prime}_{1}$ is
the set of $(y_{1},\dots,y_{5})\in(\mathbb{F}_{p}^{d})^{5}$ such that
$M^{\prime}(y_{i})$ and $M^{\prime}(y_{i}-y_{5})$ are zero for all $1\leq
i\leq 4$. Since all of these functions forms a nice and independent
$M$-family, we have that $\Omega^{\prime}_{1}$ is a nice and consistent
$M$-set of total co-dimension 8, and thus so is $\Omega_{1}$ by Proposition
B.3 (iii).

  * •

Let $s\geq 2$ and denote $\mathbb{w}:=(w_{1},\dots,w_{5})$,
$\mathbb{h}^{\prime}:=(h_{1},\dots,h_{s-1})$ and
$\mathbb{h}:=(h_{1},\dots,h_{s+1})$ with $h_{i},w_{i}\in\mathbb{F}_{p}^{d}$.
Let $\Omega_{2}$ be the set of
$(\mathbb{w},\mathbb{h})\in(\mathbb{F}_{p}^{d})^{s+6}$ such that
$(w_{1},\mathbb{h}),(w_{2},\mathbb{h})\in\Box_{s+1}(V(M))$,
$(w_{3},\mathbb{h}^{\prime},h_{s}),$
$(w_{4},\mathbb{h}^{\prime},h_{s+1})\in\Box_{s}(V(M))$,
$(w_{5},\mathbb{h}^{\prime})\in\Box_{s-1}(V(M))$. Then
$\Omega_{2}=\Omega^{\prime}_{2}+(b,b,b,b,b,\mathbb{0},\dots,\mathbb{0})$,
where $\Omega_{2}^{\prime}$ is the set of
$(\mathbb{w},\mathbb{h})\in(\mathbb{F}_{p}^{d})^{s+6}$ such that
$(w_{1},\mathbb{h}),(w_{2},\mathbb{h})\in\Box_{s+1}(V(M^{\prime}))$,
$(w_{3},\mathbb{h}^{\prime},h_{s}),(w_{4},\mathbb{h}^{\prime},h_{s+1})\in\Box_{s}(V(M^{\prime}))$,
$(w_{5},\mathbb{h}^{\prime})\in\Box_{s-1}(V(M^{\prime}))$. Let
$L\colon(\mathbb{F}_{p}^{d})^{s+6}\to(\mathbb{F}_{p}^{d})^{s+6}$ be the
bijective $d$-integral linear transformation given by
$L(\mathbb{w},\mathbb{h}):=(\mathbb{h},\mathbb{w})$. By Lemma 4.18,
$(\mathbb{h},\mathbb{w})\in L(\Omega_{2}^{\prime})$ if and only if
$M(w_{i}),M(w_{i}+h_{j_{i}})-M(w_{i}),(h_{j}A)\cdot h_{j^{\prime}}$ equal to
zero for all $1\leq i\leq 5$, $1\leq j,j^{\prime}\leq s+1,j\neq j^{\prime}$,
$1\leq j_{1},j_{2}\leq s+1$, $1\leq j_{3}\leq s$,
$j_{4}\in\\{1,\dots,s-1\\}\cup\\{s\\}$ and $1\leq j_{5}\leq s-1$. Since all of
these functions forms a nice and independent $M$-family, we have that
$L(\Omega^{\prime}_{2})$ is a nice and consistent $M$-set of total co-
dimension $(s^{2}+11s+12)/2$, and thus so is $\Omega_{2}$ by Proposition B.3
(iii).

  * •

Let $M$ be of the form $M(n)=(nA)\cdot n$,
$k\in\mathbb{N}_{+},v_{0},\dots,v_{k}\in\mathbb{F}_{p}^{d},r\in\mathbb{F}_{p}$
and $\Omega_{3}\subseteq(\mathbb{F}_{p}^{d})^{k+1}$ be the set of
$(x_{0},\dots,x_{k+1})\in(\mathbb{F}_{p}^{d})^{k}$ such that
$M(x_{i}-x_{j})=M(v_{i}-v_{j})$ and $M(x_{i})=r$ for all $0\leq i\leq j\leq
k,i\neq j$. Note that $(x_{0},\dots,x_{k})\in\Omega_{3}$ if and only if
$(x_{i}A)\cdot x_{i}-r$ and $(x_{i}A)\cdot x_{j}-r+\frac{1}{2}M(v_{i}-v_{j})$
are zero for all $0\leq i,j\leq k,i\neq j$. Since all of these functions forms
a nice and independent $M$-family, we have that $\Omega_{3}$ is a nice and
consistent $M$-set of total co-dimension $(k+2)(k+1)/2$.

  * •

Fix some $\Omega_{3}$ defined above. Let $\Omega_{4}$ denote the set of
$(x,\mathbb{x},\mathbb{x}^{\prime})\in(\mathbb{F}_{p}^{d})^{2k+1}$ such that
$(x,\mathbb{x}),(x,\mathbb{x}^{\prime})\in\Omega_{4}$, where
$x\in\mathbb{F}_{p}^{d}$ and
$\mathbb{x},\mathbb{x}^{\prime}\in(\mathbb{F}_{p}^{d})^{k}$. Note that
$(x_{0},x_{1},\dots,x_{k},x^{\prime}_{1},\dots,$ $x^{\prime}_{k})$ belongs to
$\Omega_{4}$ if and only if $(x_{0}A)\cdot x_{0}-r$, $(x_{i}A)\cdot x_{i}-r$,
$(x^{\prime}_{i}A)\cdot x^{\prime}_{i}-r$, $(x_{0}A)\cdot
x_{j}-r+\frac{1}{2}M(v_{0}-v_{j})$, $(x_{0}A)\cdot
x^{\prime}_{j}-r+\frac{1}{2}M(v_{0}-v_{j})$, $(x_{i}A)\cdot
x_{j}-r+\frac{1}{2}M(v_{i}-v_{j})$, $(x^{\prime}_{i}A)\cdot
x^{\prime}_{j}-r+\frac{1}{2}M(v_{i}-v_{j})$ are zero for all $1\leq i,j\leq
k,i\neq j$. Since all of these functions forms a nice and independent
$M$-family, we have that $\Omega_{4}$ is a nice and consistent $M$-set of
total co-dimension $k^{2}+3k+1$.

##  Appendix C Fubini’s Theorem for $M$-sets

In this section, we prove a Fubini-type theorem for consistent $M$-sets. To
this end, we need to define the projections of $M$-sets. We start with
defining the projections of ideals of the polynomial ring. Let
$n_{i}=(n_{i,1},\dots,n_{i,d})\in\mathbb{F}_{p}^{d}$ denote a $d$-dimensional
variable for $1\leq i\leq k$. For convenience we denote
$\mathbb{F}^{d}_{p}[n_{1},\dots,n_{k}]$ to be the polynomial ring
$\mathbb{F}_{p}[n_{1,1},\dots,n_{1,d},\dots,n_{k,1},\dots,n_{k,d}]$. Let
$J,J^{\prime},J^{\prime\prime}$ be finitely generated ideals of the polynomial
ring $\mathbb{F}^{d}_{p}[n_{1},\dots,n_{k}]$ and
$I\subseteq\\{n_{1},\dots,n_{k}\\}$. Suppose that
$J=J^{\prime}+J^{\prime\prime}$, $J^{\prime}\cap J^{\prime\prime}=\\{0\\}$,
all the polynomials in $J^{\prime}$ are independent of
$\\{n_{1},\dots,n_{k}\\}\backslash I$, and all the non-zero polynomials in
$J^{\prime\prime}$ depend nontrivially on $\\{n_{1},\dots,n_{k}\\}\backslash
I$. Then we say that $J^{\prime}$ is an _$I$ -projection_ of $J$ and that
$(J^{\prime},J^{\prime\prime})$ is an _$I$ -decomposition_ of $J$.

######  Proposition C.1.

Let $d,k\in\mathbb{N}_{+}$, $p\gg_{d,k}1$ be a prime, and
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a quadratic form. Let
$\mathcal{J}=\\{F_{i}\in\mathbb{F}^{d}_{p}[n_{1},\dots,n_{k}]\colon 1\leq
i\leq r\\}$ be a consistent $(M,k)$-family and
$I\subseteq\\{n_{1},\dots,n_{k}\\}$. Let $J$ be the ideal generated by
$\mathcal{J}$. Then the $I$-projection of $J$ exists and is unique.

###### Proof.

Note that for any $r\times r$ invertible matrix $(t_{i,j})_{1\leq i,j\leq r}$
in $\mathbb{F}_{p}$, $J$ is also the ideal generated by
$\\{F^{\prime}_{i}:=t_{i,1}F_{1}+\dots+t_{i,r}F_{r}\colon 1\leq i\leq r\\}$,
which is also a consistent $(M,k)$-family. By the knowledge of linear algebra
and the expression of $(M,k)$-quadratic functions, we may choose
$(t_{i,j})_{1\leq i,j\leq r}$ in a way such that for some $0\leq
r^{\prime}\leq r$, $F^{\prime}_{1},\dots,F^{\prime}_{r^{\prime}}$ are
independent of $\\{n_{1},\dots,n_{k}\\}\backslash I$, and
$F^{\prime}_{r^{\prime}+1},\dots,F^{\prime}_{r}$ depend nontrivially on
$\\{n_{1},\dots,n_{k}\\}\backslash I$. Since $\\{F^{\prime}_{i}\colon 1\leq
i\leq r\\}$ is consistent, setting $J^{\prime}$ to be the ideal generated by
$F^{\prime}_{1},\dots,F^{\prime}_{r^{\prime}}$ and $J^{\prime\prime}$ to be
the ideal generated by $F^{\prime}_{r^{\prime}+1},\dots,F^{\prime}_{k}$, we
have that $J^{\prime}$ is an $I$-projection of $J$. This proves the existence
of the $I$-projection (note that $J^{\prime}$ and $J^{\prime\prime}$ dose not
contain 1 since $\mathcal{J}$ is consistent).

Now suppose that $J$ has two $I$-projections $J^{\prime}$ and
$\tilde{J}^{\prime}$. Then exist some ideal $J^{\prime\prime}$ of
$\mathbb{F}_{p}[n_{1},\dots,n_{k}]$ such that $J=J^{\prime}+J^{\prime\prime}$,
$J^{\prime}\cap J^{\prime\prime}=\\{0\\}$, and all the non-zero polynomials in
$J^{\prime\prime}$ depend nontrivially on $\\{n_{1},\dots,n_{k}\\}\backslash
I$.

Pick any $f\in\tilde{J}^{\prime}$. We may write
$f=f^{\prime}+f^{\prime\prime}$ for some $f^{\prime}\in J^{\prime}$ and
$f^{\prime\prime}\in J^{\prime\prime}$. Then $f^{\prime\prime}=f-f^{\prime}$
is independent of $\\{n_{1},\dots,n_{k}\\}\backslash I$. By the construction
of $J^{\prime\prime}$, we have that $f^{\prime\prime}=0$ and thus
$f=f^{\prime}$. This means that $\tilde{J}^{\prime}\subseteq J^{\prime}$. By
symmetry $J^{\prime}\subseteq\tilde{J}^{\prime}$ and so
$\tilde{J}^{\prime}=J^{\prime}$. This proves the uniqueness of the
$I$-projection. ∎

Let $\mathcal{J}$, $\mathcal{J}^{\prime}$ and $\mathcal{J}^{\prime\prime}$ be
finite subsets of $\mathbb{F}^{d}_{p}[n_{1},\dots,n_{k}]$, and
$I\subseteq\\{n_{1},\dots,n_{k}\\}$. Let $J,J^{\prime}$, and
$J^{\prime\prime}$ be the ideals generated by $\mathcal{J}$,
$\mathcal{J}^{\prime}$ and $\mathcal{J}^{\prime\prime}$ respectively. If
$J^{\prime}$ is an $I$-projection of $J$ with $(J^{\prime},J^{\prime\prime})$
being an $I$-decomposition of $J$, then we say that $\mathcal{J}^{\prime}$ is
an _$I$ -projection_ of $\mathcal{J}$ and that
$(\mathcal{J}^{\prime},\mathcal{J}^{\prime\prime})$ is an _$I$ -decomposition_
of $\mathcal{J}$. Note that the $I$-projection $\mathcal{J}^{\prime}$ of
$\mathcal{J}$ is not unique. However, by Proposition C.1 the ideal generated
by $\mathcal{J}^{\prime}$ and the set of zeros $V(\mathcal{J}^{\prime})$ are
unique.

If $I$ is a subset of $\\{1,\dots,k\\}$, for convenience we say that
$J^{\prime}$ is an _$I$ -projection_ of $J$ if $J^{\prime}$ is an
$\\{n_{i}\colon i\in I\\}$-projection of $J$. Similarly, we say that
$(J^{\prime},J^{\prime\prime})$ is an _$I$ -decomposition_ of $J$ if
$(J^{\prime},J^{\prime\prime})$ is an $\\{n_{i}\colon i\in I\\}$-decomposition
of $J$. Here $J,J^{\prime},J^{\prime\prime}$ are either ideals or finite
subsets of the polynomial ring.

We are now ready to define the projections of $M$-sets. Let
$\mathcal{J}\subseteq\mathbb{F}_{p}[n_{1},\dots,n_{k}]$ be a consistent
$(M,k)$-family and let
$\Omega=V(\mathcal{J})\subseteq(\mathbb{F}_{p}^{d})^{k}$. Let $I\cup J$ be a
partition of $\\{1,\dots,k\\}$ (where $I$ and $J$ are non-empty), and
$(\mathcal{J}_{I},\mathcal{J}^{\prime}_{I})$ be an $I$-decomposition of
$\mathcal{J}$. Let $\Omega_{I}$ denote the set of $(n_{i})_{i\in
I}\in(\mathbb{F}_{p}^{d})^{|I|}$ such that $f(n_{1},\dots,n_{k})=0$ for all
$f\in\mathcal{J}_{I}$ and $(n_{j})_{j\in J}\in(\mathbb{F}_{p}^{d})^{|J|}$.
Note that all $f\in\mathcal{J}_{I}$ are independent of $(n_{j})_{j\in J}$, and
that $\Omega_{I}$ is independent of the choice of the $I$-decomposition. We
say that $\Omega_{I}$ is an _$I$ -projection_ of $\Omega$.

For $(n_{i})_{i\in I}\in(\mathbb{F}_{p}^{d})^{|I|}$, let
$\Omega_{I}((n_{i})_{i\in I})$ be the set of $(n_{j})_{j\in
J}\in(\mathbb{F}_{p}^{d})^{|J|}$ such that $f(n_{1},\dots,n_{k})=0$ for all
$f\in\mathcal{J}^{\prime}_{I}$. By construction, for any $(n_{i})_{i\in
I}\in\Omega_{I}$, we have that $(n_{j})_{j\in J}\in\Omega_{I}((n_{i})_{i\in
I})$ if and only if $(n_{1},\dots,n_{k})\in\Omega$. So for all $(n_{i})_{i\in
I}\in\Omega_{I}$, $\Omega_{I}((n_{i})_{i\in I})$ is independent of the choice
of the $I$-decomposition.

######  Example C.2.

Let $M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a quadratic form
associated to the matrix $A$. Consider the set $\Box_{s}(V(M))$. By Lemma
4.18, we may write
$\Box_{s}(V(M))=V(\mathcal{J})\subseteq\mathbb{F}_{p}[n,h_{1},\dots,h_{s}]$
where

$\mathcal{J}:=\\{M(n),M(n+h_{i}),(h_{i}A)\cdot h_{j}\colon 1\leq i,j\leq
s,i\neq j\\}$

is a consistent $(M,s+1)$-family of total dimension $\frac{s(s+1)}{2}+1$. Let

$\mathcal{J}^{\prime}:=\\{M(n),M(n+h_{i}),(h_{i}A)\cdot h_{j}\colon 1\leq
i,j\leq t,i\neq j\\}$

and $\mathcal{J}^{\prime\prime}:=\mathcal{J}\backslash\mathcal{J}^{\prime}$.
It is not hard to compute that
$(\mathcal{J}^{\prime},\mathcal{J}^{\prime\prime})$ is an
$\\{n,h_{1},\dots,h_{t}\\}$-decomposition of $\mathcal{J}$. So
$\Box_{t}(V(M))$ is an $\\{n,h_{1},\dots,h_{t}\\}$-projection of
$\Box_{s}(V(M))$.

We are now ready to state Fubini’s theorem for $M$-sets:

######  Theorem C.3 (Fubini’s Theorem).

Let $d,k\in\mathbb{N}_{+}$, $r_{1},\dots,r_{k}\in\mathbb{N}$ and $p$ be a
prime. Set $r:=r_{1}+\dots+r_{k}$. Let
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a quadratic form with
$\text{rank}(M)\geq 2r+1$, and $\Omega\subseteq(\mathbb{F}_{p}^{d})^{k}$ be a
consistent $M$-set admitting a standard $M$-representation of $\Omega$ with
dimension vector $(r_{1},\dots,r_{k})$.

  1. (i)

We have $|\Omega|=p^{dk-r}(1+O_{k,r}(p^{-1/2}))$;

  2. (ii)

If $I=\\{1,\dots,k^{\prime}\\}$ for some $1\leq k^{\prime}\leq k-1$, then
$\Omega_{I}$ is a consistent $M$-set admitting a standard $M$-representation
with dimension vector $(r_{1},\dots,r_{k^{\prime}})$. Moreover, for all but at
most
$(k-k^{\prime})r^{\prime}_{k^{\prime}}p^{dk^{\prime}+r^{\prime}_{k^{\prime}}-1-\text{rank}(M)}$
many $(n_{i})_{i\in I}\in(\mathbb{F}_{p}^{d})^{k^{\prime}}$, we have that
$\Omega_{I}((n_{i})_{i\in I})$ has a standard $M$-representation with
dimension vector $(r_{k^{\prime}+1},\dots,r_{k})$ and that
$|\Omega_{I}((n_{i})_{i\in
I})|=p^{d(k-k^{\prime})-(r_{k^{\prime}+1}+\dots+r_{k})}(1+O_{k,r}(p^{-1/2}))$,
where $r^{\prime}_{k^{\prime}}:=\max_{k^{\prime}+1\leq i\leq k}r_{i}$.

  3. (iii)

If $k\geq 2$, and $I\cup J$ is a partition of $\\{1,\dots,k\\}$ (where $I$ and
$J$ are non-empty), then for any function $f\colon\Omega\to\mathbb{C}$ with
norm bounded by 1, we have that

(C.1)
$\mathbb{E}_{(n_{1},\dots,n_{k})\in\Omega}f(n_{1},\dots,n_{k})=\mathbb{E}_{(n_{i})_{i\in
I}\in\Omega_{I}}\mathbb{E}_{(n_{j})_{j\in J}\in\Omega_{I}((n_{i})_{i\in
I})}f(n_{1},\dots,n_{k})+O_{k,r}(p^{-1/2}).$

The major difficulty in showing (C.1) is that the cardinality of
$\Omega_{I}((n_{i})_{i\in I})$ is dependent on the choice of $(n_{i})_{i\in
I}$. However, under a careful computation, one can show that for almost all
choices of $(n_{i})_{i\in I}$, the cardinalities of $\Omega_{I}((n_{i})_{i\in
I})$ are almost the same. Therefore, it is still possible to write the average
of $f$ as two iterated averages, at the cost of an error term
$O_{k,r}(p^{-1/2})$.

###### Proof of Theorem C.3.

We first assume that $I=\\{1,\dots,k^{\prime}\\}$ and
$J=\\{k^{\prime}+1,\dots,k\\}$ for some $1\leq k^{\prime}\leq k$. We prove
Theorem C.3 by induction with respect to $k$. We first show that Theorem C.3
holds if $k=1$. Let $(F_{1},\dots,F_{r})$ be a standard $M$-representation of
$\Omega$ (which exists by Corollary B.2 (iii)). Since $k=1$, either
$F_{1}(n)=(nA)\cdot n+v_{1}\cdot n+u_{1}$ and $F_{i}(n)=v_{i}\cdot
n+u_{i},2\leq i\leq r$ for some linearly independent $v_{2},\dots,v_{r}$, or
$F_{i}(n)=v_{i}\cdot n+u_{i},1\leq i\leq r$ for some linearly independent
$v_{1},\dots,v_{r}$. Since $\\{F_{1},\dots,F_{r}\\}$ is consistent, in the
former case $\Omega$ is the intersection of $V(F_{1})$ with an affine subspace
of $\mathbb{F}_{p}^{d}$ of co-dimension $r-1$, and in the later case $\Omega$
is an affine subspace of $\mathbb{F}_{p}^{d}$ of co-dimension $r$. Since
$\text{rank}(M)-2(r-1)\geq 3$, by Lemma 4.10 and Corollary 4.14, we have that
$|\Omega|=p^{d-r}(1+O(p^{-1/2}))$ in both cases. Since $k=1$, there is nothing
to prove in Parts (ii) and (iii).

We now assume that the conclusion holds for $k-1$ for some $k\geq 2$ and we
prove it for $k$. We may then write $\Omega=V(\mathcal{J})$ for some
$\mathcal{J}=(F_{i,j}\colon(\mathbb{F}_{p}^{d})^{k}\to\mathbb{F}_{p}\colon
1\leq i\leq k,1\leq j\leq r_{i})$, where $F_{i,j}$ depends nontrivially on
$n_{i}$ and is independent of $n_{i^{\prime}}$ for all $i^{\prime}>i$. For
convenience denote $\Omega_{k^{\prime}}:=\Omega_{\\{1,\dots,k^{\prime}\\}}$
and
$\Omega_{k^{\prime}}(n_{1},\dots,n_{k^{\prime}}):=\Omega_{\\{1,\dots,k^{\prime}\\}}(n_{1},\dots,n_{k^{\prime}})$.
By Proposition B.3 (ii), it is not hard to see that
$\Omega_{k^{\prime}}=\cap_{1\leq i\leq k^{\prime}}\cap_{1\leq j\leq
r_{i}}V(F_{i,j})$ (where $F_{i,j}$ are viewed as a polynomial in
$(n_{1},\dots,n_{k^{\prime}})$ since it is independent of
$n_{i+1},\dots,n_{k}$) and thus $\Omega_{k^{\prime}}$ is a consistent $M$-set
admitting a consistent $M$-representation with dimension vector
$(r_{1},\dots,r_{k^{\prime}})$. So by induction hypothesis,

(C.2)
$|\Omega_{k^{\prime}}|=p^{dk^{\prime}-(r_{1}+\dots+r_{k^{\prime}})}(1+O_{k,r}(p^{-1/2})).$

For convenience also denote $\mathbb{m}=(n_{1},\dots,n_{k^{\prime}})$ and
$\mathbb{n}=(n_{k^{\prime}+1},\dots,n_{k})$. Note that for all
$\mathbb{m}\in\Omega_{k^{\prime}}$, we have that
$\mathbb{n}\in\Omega_{k^{\prime}}(\mathbb{m})$ if and only if
$F_{i,j}(\mathbb{m},\mathbb{n})=0$ for all $i>k^{\prime}$ and $1\leq j\leq
r_{i}$.

For $1\leq i\leq k$, since the matrix $\begin{bmatrix}v_{M}(F_{i,1})\\\
\dots\\\ v_{M}(F_{i,r_{i}})\end{bmatrix}$ is in the reduced row echelon form
and does not contain a row of the form $(0,\dots,0,a),a\in\mathbb{F}_{p}$, we
have that

$F_{i,j}(n_{1},\dots,n_{i})=(n_{i}A)\cdot(u_{i,j,1}n_{1}+\dots+u_{i,j,i}n_{i})+v_{i,j}\cdot
n_{i}+f_{i,j}(n_{1},\dots,n_{i-1})$

for all $1\leq j\leq r_{i}$ for some
$u_{i,j}=(u_{i,j,i},\dots,u_{i,j,1})\in(\mathbb{F}_{p}^{d})^{i}$,
$v_{i,j}\in\mathbb{F}_{p}^{d}$, and some $(M,i-1)$-integral quadratic function
$f_{i,j}$ such that the $r_{i}\times(i+1)d$ matrix
$B_{i}:=\begin{bmatrix}u_{i,1},v_{i,1}\\\ \dots\\\
u_{i,r_{i}},v_{i,r_{i}}\end{bmatrix}$ is in the reduced row echelon form which
does not contain zero rows.

Denote $u^{\prime}_{i,j}:=(u_{i,j,i},\dots,u_{i,j,k^{\prime}+1})$ and
$v^{\prime}_{i,j}(n_{1},\dots,n_{k^{\prime}}):=v_{i,j}+(u_{i,j,1}n_{1}+\dots+u_{i,j,k^{\prime}}n_{k^{\prime}})A\in\mathbb{F}_{p}^{d}$
. Note that if we view $n_{1},\dots,n_{k^{\prime}}$ as constants and consider
$F_{i,j}$ as a function in the varaibles $n_{k^{\prime}+1},\dots,n_{k}$, then
for $k^{\prime}+1\leq i\leq k$ and $1\leq j\leq r_{i}$,

$F_{i,j}(n_{1},\dots,n_{i})=(n_{i}A)\cdot(u_{i,j,k^{\prime}+1}n_{k^{\prime}+1}+\dots+u_{i,j,i}n_{i})+v^{\prime}_{i,j}(n_{1},\dots,n_{k^{\prime}})\cdot
n_{i}+f_{i,j}(n_{1},\dots,n_{i-1})$

and thus

$v_{M}(F_{i,j}(\mathbb{m},\cdot))=(0,\dots,0,u^{\prime}_{i,j},v^{\prime}_{i,j}(\mathbb{m}),\dots),$

where $u^{\prime}_{i,j}$ starts from the $n_{i}^{2}$ coordinate and
$v^{\prime}_{i,j}(\mathbb{m})$ terminates right before the $n_{i-1}^{2}$
coordinate (and we do not care about the remaining coordinates).

Let $Z_{k^{\prime}}$ denote the set of
$\mathbb{m}\in(\mathbb{F}_{p}^{d})^{k^{\prime}}$ such that the
$r_{i}\times(i-k^{\prime}+1)d$ matrix
$B_{i}(\mathbb{m}):=\begin{bmatrix}u^{\prime}_{i,1},v^{\prime}_{i,1}(\mathbb{m})\\\
\dots\\\ u^{\prime}_{i,r_{i}},v^{\prime}_{i,r_{i}}(\mathbb{m})\end{bmatrix}$
is not of rank $r_{i}$ for some $k^{\prime}+1\leq i\leq k$. Note that the
matrix with

$v_{M}(F_{k,1}),\dots,v_{M}(F_{k,r_{k}}),\dots,v_{M}(F_{1,1}),\dots,v_{M}(F_{1,r_{1}})$

as row vectors is a block upper triangular matrix in the row echelon form of
the form

$\begin{bmatrix}B_{k}&\dots&\dots&\dots&\dots\\\ &B_{k-1}&\dots&\dots&\dots\\\
&&\ddots&\dots&\dots\\\ &&&B_{1}&\dots\end{bmatrix}$

which does not contain a row of the form $(0,\dots,0,a),a\in\mathbb{F}_{p}$
(note that there is only 1 column to the right of $B_{1}$, which correspondent
to the constant coefficients). For all
$\mathbb{m}\in\Omega_{k^{\prime}}\backslash Z_{k^{\prime}}$, $k^{\prime}+1\leq
i\leq k$ and $1\leq j\leq r_{i}$, the matrix with

$\begin{split}v_{M}(F_{k,1}(\mathbb{m},\cdot)),\dots,v_{M}(F_{k,r_{k}}(\mathbb{m},\cdot)),\dots,v_{M}(F_{k^{\prime}+1,1}(\mathbb{m},\cdot)),\dots,v_{M}(F_{k^{\prime}+1,r_{k^{\prime}+1}}(\mathbb{m},\cdot))\end{split}$

as row vectors is a block upper triangular matrix of the form

$\begin{bmatrix}B_{k}(\mathbb{m})&\dots&\dots&\dots&\dots\\\
&B_{k-1}(\mathbb{m})&\dots&\dots&\dots\\\ &&\ddots&\dots&\dots\\\
&&&B_{k^{\prime}+1}(\mathbb{m})&\dots\end{bmatrix},$

where there is only 1 column to the right of $B_{k^{\prime}+1}(\mathbb{m})$.
Since $B_{i}(\mathbb{m})$ is of rank $r_{i}$, this matrix does not contain a
row of the form $(0,\dots,0,a),a\in\mathbb{F}_{p}$. We may then use elementary
row operations to transform this matrix into the reduced echelon form which
can be written as

$\begin{bmatrix}B^{\prime}_{k}(\mathbb{m})&\dots&\dots&\dots&\dots\\\
&B^{\prime}_{k-1}(\mathbb{m})&\dots&\dots&\dots\\\ &&\ddots&\dots&\dots\\\
&&&B^{\prime}_{k^{\prime}+1}(\mathbb{m})&\dots\end{bmatrix}$

for some $B^{\prime}_{i}(\mathbb{m})$, which are in the reduced echelon form
and of the same size as $B_{i}(\mathbb{m})$. Again this matrix does not
contain a row of the form $(0,\dots,0,a),a\in\mathbb{F}_{p}$. This implies
that $\Omega_{k^{\prime}}(\mathbb{m})$ has a standard $M$-representation with
dimension vector $(r_{k^{\prime}+1},\dots,r_{k})$. So by induction hypothesis,

(C.3)
$|\Omega_{k^{\prime}}(\mathbb{m})|=p^{d(k-k^{\prime})-(r_{k^{\prime}+1}+\dots+r_{k})}(1+O_{k,r}(p^{-1/2}))\text{
for all }\mathbb{m}\in\Omega_{k^{\prime}}\backslash Z_{k^{\prime}}.$

We now compute the cardinality of $Z_{k^{\prime}}$. Fix $k^{\prime}+1\leq
i\leq k$. If $B_{i}(\mathbb{m})$ is not of rank $r_{i}$, then there exist
$c_{1},\dots,c_{r_{i}}$ with at least one of them equal to 1 such that
$\sum_{j=1}^{r_{i}}c_{j}u^{\prime}_{i,j}=\mathbb{0}$ and
$\sum_{j=1}^{r_{i}}c_{j}(v_{i,j}+(u_{i,j,1}n_{1}+\dots+u_{i,j,k^{\prime}}n_{k^{\prime}})A)=\mathbb{0}.$
If $\sum_{j=1}^{r_{i}}c_{j}u_{i,j,t}=0$ for all $1\leq t\leq k^{\prime}$, then
we have that $\sum_{j=1}^{r_{i}}c_{j}v_{i,j}=\mathbb{0}$ and this contradicts
to the fact that $B_{i}$ is of full rank. So at least one of
$\sum_{j=1}^{r_{i}}c_{j}u_{i,j,t},1\leq t\leq k^{\prime}$ is nonzero.
Therefore, for all $m\in\mathbb{F}_{p}^{d}$, then number of
$n_{1},\dots,n_{k^{\prime}}\in\mathbb{F}_{p}^{d}$ with
$m=\sum_{j=1}^{r_{i}}c_{j}(u_{i,j,1}n_{1}+\dots+u_{i,j,k^{\prime}}n_{k^{\prime}})$
is $p^{d(k^{\prime}-1)}$.

On the other hand, the number of $c_{j}\in\mathbb{F}_{p},1\leq j\leq r_{i}$
with at least one of them equal to 1 is at most $r_{i}p^{r_{i}-1}$; the number
of $m$ with $\sum_{j=1}^{r_{i}}c_{j}v_{i,j}+mA=\mathbb{0}$ is at most
$p^{d-\text{rank}(M)}$. So

(C.4) $|Z_{k^{\prime}}|\leq\sum_{i=k^{\prime}+1}^{k}r_{i}p^{r_{i}-1}\cdot
p^{d(k^{\prime}-1)}\cdot
p^{d-\text{rank}(M)}\leq(k-k^{\prime})r^{\prime}_{k^{\prime}}p^{dk^{\prime}+r^{\prime}_{k^{\prime}}-1-\text{rank}(M)}.$

So Part (ii) is proved by combining (C.2), (C.3) and (C.4).

Since $\text{rank}(M)\geq r_{1}+\dots+r_{k}$ by (C.2), (C.3), and (C.4), we
have

$\begin{split}&\quad\sum_{\mathbb{m}\in\Omega_{k^{\prime}}\backslash
Z_{k^{\prime}}}|\Omega_{k^{\prime}}(\mathbb{m})|\\\
&=|\Omega_{k^{\prime}}\backslash Z_{k^{\prime}}|\cdot
p^{d(k-k^{\prime})-(r_{k^{\prime}+1}+\dots+r_{k})}(1+O_{k,r}(p^{-1/2}))=p^{dk-(r_{1}+\dots+r_{k})}(1+O_{k,r}(p^{-1/2}))\end{split}$

and

(C.5) $\begin{split}\sum_{\mathbb{m}\in
Z_{k^{\prime}}}|\Omega_{k^{\prime}}(\mathbb{m})|\leq|Z_{k^{\prime}}|\cdot
p^{d(k-k^{\prime})}\leq(k-k^{\prime})r^{\prime}_{k^{\prime}}p^{dk+r^{\prime}_{k^{\prime}}-1-\text{rank}(M)}.\end{split}$

Since $\text{rank}(M)\geq 2r+1$, we have that

$|\Omega|=\sum_{\mathbb{m}\in\Omega_{k^{\prime}}}|\Omega_{k^{\prime}}(\mathbb{m})|=p^{dk-(r_{1}+\dots+r_{k})}(1+O_{k,r}(p^{-1/2})).$

This proves Part (i).

Finally, we have that

(C.6)
$\begin{split}&\quad|\mathbb{E}_{(\mathbb{m},\mathbb{n})\in\Omega}f(\mathbb{m},\mathbb{n})-\mathbb{E}_{\mathbb{n}\in\Omega_{k^{\prime}}}\mathbb{E}_{\mathbb{n}\in\Omega_{k^{\prime}}(\mathbb{m})}f(\mathbb{m},\mathbb{n})|\\\
&=\Bigl{|}\frac{1}{|\Omega_{k^{\prime}}|}\sum_{\mathbb{m}\in\Omega_{k^{\prime}}}\sum_{\mathbb{n}\in\Omega_{k^{\prime}}(\mathbb{m})}f(\mathbb{m},\mathbb{n})(\frac{|\Omega_{k^{\prime}}|}{|\Omega|}-\frac{1}{|\Omega_{k^{\prime}}(\mathbb{m})|})\Bigr{|}\\\
&\leq\frac{1}{|\Omega_{k^{\prime}}|}\sum_{\mathbb{m}\in\Omega_{k^{\prime}}}\sum_{\mathbb{n}\in\Omega_{k^{\prime}}(\mathbb{m})}\Bigl{|}\frac{|\Omega_{k^{\prime}}|}{|\Omega|}-\frac{1}{|\Omega_{k^{\prime}}(\mathbb{m})|}\Bigr{|}=\frac{1}{|\Omega_{k^{\prime}}|}\sum_{\mathbb{m}\in\Omega_{k^{\prime}}}\Bigl{|}\frac{|\Omega_{k^{\prime}}|\cdot|\Omega_{k^{\prime}}(\mathbb{m})|}{|\Omega|}-1\Bigr{|}\\\
&=\frac{1}{|\Omega_{k^{\prime}}|}\sum_{\mathbb{m}\in\Omega_{k^{\prime}}\backslash
Z_{k^{\prime}}}\Bigl{|}\frac{|\Omega_{k^{\prime}}|\cdot|\Omega_{k^{\prime}}(\mathbb{m})|}{|\Omega|}-1\Bigr{|}+\frac{1}{|\Omega_{k^{\prime}}|}\sum_{\mathbb{m}\in\Omega_{k^{\prime}}\cap
Z_{k^{\prime}}}\Bigl{|}\frac{|\Omega_{k^{\prime}}|\cdot|\Omega_{k^{\prime}}(\mathbb{m})|}{|\Omega|}-1\Bigr{|}.\end{split}$

Note that for $\mathbb{m}\in\Omega_{k^{\prime}}\backslash Z_{k^{\prime}}$,

$\begin{split}&\quad\frac{|\Omega_{k^{\prime}}|\cdot|\Omega_{k^{\prime}}(\mathbb{m})|}{|\Omega|}\\\
&=\frac{p^{dk^{\prime}-(r_{1}+\dots+r_{k^{\prime}})}(1+O_{k,r}(p^{-1/2}))\cdot
p^{d(k-k^{\prime})-(r_{k^{\prime}+1}+\dots+r_{k})}(1+O_{k,r}(p^{-1/2}))}{p^{dk-(r_{1}+\dots+r_{k})}(1+O_{k,r}(p^{-1/2}))}=1+O_{k,r}(p^{-1/2}).\end{split}$

For all $\mathbb{m}\in\Omega_{k^{\prime}}\cap Z_{k^{\prime}}$,

$\frac{|\Omega_{k^{\prime}}|\cdot|\Omega_{k^{\prime}}(\mathbb{m})|}{|\Omega|}\leq\frac{p^{d(k-k^{\prime})}|\Omega_{k^{\prime}}|}{|\Omega|}=p^{r_{k^{\prime}+1}+\dots+r_{k}}(1+O_{k,r}(p^{-1/2})).$

Moreover,

$\frac{|Z_{k^{\prime}}|}{|\Omega_{k^{\prime}}|}=O_{k,r}(p^{(r_{1}+\dots+r_{k^{\prime}}+r^{\prime}_{k^{\prime}})-\text{rank}(M)-1}),\frac{|\Omega_{k^{\prime}}\backslash
Z_{k^{\prime}}|}{|\Omega_{k^{\prime}}|}=1+O_{k,r}(p^{-1/2}).$

So the right hand side of (C.6) is at most

$O_{k,r}(p^{-1/2})(1+O_{k,r}(p^{-1/2}))+O_{k,r}(p^{(r+r^{\prime}_{k^{\prime}})-\text{rank}(M)-1})=1+O_{k,r}(p^{-1/2})$

since $\text{rank}(M)\geq 2r+1$. This proves Part (iii).

We now consider the general case. Let $\mathcal{J}=(F_{1},\dots,F_{r})$ be a
standard $M$-representation of $\Omega$ with dimension vector
$(r_{1},\dots,r_{k})$. Let $\sigma\colon\\{1,\dots,k\\}\to\\{1,\dots,k\\}$ be
a permutation with $\sigma(\\{1,\dots,k^{\prime}\\})=I$ for some $1\leq
k^{\prime}\leq k$, and let
$L(n_{1},\dots,n_{k}):=(n_{\sigma(1)},\dots,n_{\sigma(k)})$ be the
$d$-integral linear transformation which moves the variables $n_{i},i\in I$ to
the front. By Proposition B.3 (iii), $\\{F_{1}\circ L^{-1},\dots,F_{r}\circ
L^{-1}\\}$ is an independent $(M,k)$-family and
$L(\Omega)=\cap_{i=1}^{r}V(F_{1}\circ L^{-1})$. By Corollary B.2 (iii),
$L(\Omega)$ admits a standard $M$-representation with some dimension vector
$(r^{\prime}_{1},\dots,r^{\prime}_{k})$ such that
$r^{\prime}_{1}+\dots+r^{\prime}_{k}=r$. We may now apply Theorem C.3 for the
case $I=\\{1,\dots,k^{\prime}\\}$ and $J=\\{k^{\prime}+1,\dots,k\\}$ to the
set $L(\Omega)$ and complete the proof. ∎

######  Remark C.4.

It is worth noting that Proposition C.3 has many room for improvement. For
example:

  * •

the lower bound of $\text{rank}(M)$ could be made into a function of the
dimension vector $(r_{1},\dots,r_{k})$ instead of a function of $r$, which
would give us a better lower bound.

  * •

by a more careful computation, the error term $O_{k,r}(p^{-1/2})$ in (C.1) can
be improved to $O_{k}(p^{-A_{d,k,r}})$ for some $A_{d,k,r}>0$ with
$\lim_{d\to\infty}A_{d,k,r}=\infty$;

  * •

the estimate for the sum $\sum_{(n_{1},\dots,n_{k^{\prime}})\in
Z_{k^{\prime}}}|\Omega_{k^{\prime}}(n_{1},\dots,n_{k^{\prime}})|$ in (C.5) is
very coarse. In fact, for most $(n_{1},\dots,n_{k^{\prime}})\in
Z_{k^{\prime}}$, the cardinality of
$\Omega_{k^{\prime}}(n_{1},\dots,n_{k^{\prime}})$ is much smaller than
$p^{d(k-k^{\prime})}$. If we estimate this sum more carefully, it is promising
to provide a much better lower bound for $\text{rank}(M)$.

However, we will not pursue these improvements in this paper.

######  Remark C.5.

An annoying fact is that each time we apply Theorem C.3 for a set $\Omega$, we
need to first compute the $I$-projection $\Omega_{I}$, and then the set
$\Omega_{I}((n_{i})_{i\in I})$. This computation is not difficult by using the
algorithm in the proof of Proposition C.1, but is rather redundant. For
conciseness, in this paper as well as in [18, 19], we only provide essential
details on computations of the sets $\Omega_{I}$ and $\Omega_{I}((n_{i})_{i\in
I})$, instead of providing complete computations.

######  Remark C.6.

By Proposition B.3 (i), if $\Omega\subseteq(\mathbb{F}_{p}^{d})^{k}$ is a
consistent $M$-set, then for all $I\subseteq\\{1,\dots,k\\}$, $\Omega_{I}$ is
also a consistent $M$-set. So one can repeatedly use Theorem C.3 to write
$\mathbb{E}_{(n_{1},\dots,n_{k})\in\Omega}f(n_{1},\dots,n_{k})$ as a multiple
average in any way we see fit. For example, by Lemma 4.18, if $M$ is a
quadratic form associated with the matrix $A$, then we may write

$\begin{split}&\quad\mathbb{E}_{(n,h_{1},\dots,h_{4})\in\Box_{4}(V(M))}f(n,h_{1},\dots,h_{4})\\\
&=\mathbb{E}_{(h_{4},h_{2})\in(\mathbb{F}_{p}^{d})^{2}\colon(h_{2}A)\cdot
h_{4}=0}\mathbb{E}_{n\in V(M)^{h_{2},h_{4}}}\mathbb{E}_{(h_{1},h_{3})\in
W(n,h_{2},h_{4})}f(n,h_{1},\dots,h_{4})+O(p^{-1/2}),\end{split}$

where $W(n,h_{2},h_{4})$ is the set of
$(h_{1},h_{3})\in(\mathbb{F}_{p}^{d})^{2}$ such that
$M(n+\epsilon_{1}h_{1}+\dots+\epsilon_{4}h_{4})=0$ for all
$\epsilon_{1},\dots,\epsilon_{4}\in\\{0,1\\}$ with
$(\epsilon_{1},\epsilon_{3})\neq(0,0)$. It is possible to further simplify the
description of the set $W(n,h_{2},h_{4})$ and compute its the dimension
vectors. However, in many applications we do not have to specify all the sets
appearing in the averages explicitly.

As an application of Theorem C.3, we have the following estimate for the
cardinality of Gowers sets.

######  Corollary C.7 (Cardinality of Gowers sets).

Let $d\in\mathbb{N}_{+},r,s\in\mathbb{N}$ and $p$ be a prime. Let
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a quadratic form and $V+c$ be
an affine subspace of $\mathbb{F}_{p}^{d}$ of co-dimension $r$. If either
$\text{rank}(M|_{V+c})$ or $\text{rank}(M)-2r$ is at least $s^{2}+s+3$, then

$|\Box_{s}(V(M)\cap(V+c))|=p^{(s+1)(d-r)-(\frac{s(s+1)}{2}+1)}(1+O_{s}(p^{-1/2})).$

###### Proof.

By Proposition 4.8, it suffices to consider the case when
$\text{rank}(M|_{V+c})\geq s^{2}+s+3$. Let $\phi\colon\mathbb{F}_{p}^{d-r}\to
V$ be any bijective linear transformation, and let
$M^{\prime}(m):=M(\phi(m)+c)$. By Lemma 4.18,
$|\Box_{s}(V(M)\cap(V+c))|=|\Box_{s}(V(M^{\prime}))|$. By Example 9.5,
$\Box_{s}(V(M^{\prime}))$ admits a standard $M$-representation with dimension
vector $(1,1,2,\dots,s)$. We may then apply Theorem C.3 to conclude that
$|\Box_{s}(V(M^{\prime}))|=p^{(s+1)(d-r)-(\frac{s(s+1)}{2}+1)}(1+O_{s}(p^{-1/2})).$
∎

Another application of Theorem C.3 is to prove Proposition 4.19. We leave the
details to the interested readers.

We conclude this section with some properties on the dimension vectors of
$M$-sets.

######  Proposition C.8.

Let $d,k,r\in\mathbb{N}_{+}$, $p$ be a prime,
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a quadratic form and
$\Omega\subseteq(\mathbb{F}_{p}^{d})^{k}$ be a consistent $M$-set. Suppose
that $\Omega=\cap_{i=1}^{r}V(F_{i})$ for some consistent $(M,k)$-family
$\\{F_{1},\dots,F_{r}\\}$. Let $1\leq k^{\prime}\leq k$. Suppose that
$\text{rank}(M)\geq 2r+1$ and $p\gg_{k,r}1$.

  1. (i)

The dimension of all independent $M$-representations of $\Omega$ equals to
$r_{M}(\Omega)$.

  2. (ii)

We have that $r_{M}(\Omega)\leq r$, and that $r_{M}(\Omega)=r$ if the
$(M,k)$-family $\\{F_{1},\dots,F_{r}\\}$ is independent.

  3. (iii)

For all $I\subseteq\\{1,\dots,r\\}$, the set $\Omega^{\prime}:=\cap_{i\in
I}V(F_{i})$ is a consistent $M$-set such that $r_{M}(\Omega^{\prime})\leq
r_{M}(\Omega)$. Moreover, if the $(M,k)$-family $\\{F_{1},\dots,F_{r}\\}$ is
independent, then $r_{M}(\Omega^{\prime})=|I|$.

  4. (iv)

For any bijective $d$-integral linear transformation
$L\colon(\mathbb{F}_{p}^{d})^{k}\to(\mathbb{F}_{p}^{d})^{k}$ and
$v\in(\mathbb{F}_{p}^{d})^{k}$, we have that $L(\Omega)+v$ is a consistent
$M$-set and that $r_{M}(L(\Omega)+v)=r_{M}(\Omega)$.

  5. (v)

Assume that $\Omega$ admits a standard $M$-representation with dimension
vector $(r_{1},\dots,$ $r_{k})$, Then for all $1\leq k^{\prime}\leq k$, the
set

$\\{(n_{1},\dots,n_{k+k^{\prime}})\in(\mathbb{F}_{p}^{d})^{k+k^{\prime}}\colon(n_{1},\dots,n_{k}),(n_{1},\dots,n_{k-k^{\prime}},n_{k+1},\dots,n_{k+k^{\prime}})\in\Omega\\}$

admits a standard $M$-representation with dimension vector
$(r_{1},\dots,r_{k^{\prime}},r_{k+1},\dots,r_{k^{\prime}})$.

  6. (vi)

Assume that $\Omega$ admits a standard $M$-representation with dimension
vector $(r_{1},\dots,$ $r_{k})$. For $I=\\{1,\dots,k^{\prime}\\}$ for some
$1\leq k^{\prime}\leq k$, the $I$-projection $\Omega_{I}$ of $\Omega$ admits a
standard $M$-representation with dimension vector
$(r_{1},\dots,r_{k^{\prime}})$.

  7. (vii)

If $\Omega$ is a nice and consistent $M$-set or a pure and consistent $M$-set,
then $r_{M}(\Omega)\leq\binom{k+1}{2}$.

###### Proof.

Part (i) is a consequence of Theorem C.3 (i). Part (ii) can be proved using
the method similar to the proof of Corollary B.2. Parts (iii) and (iv) follow
from Proposition B.3 (i) and (iii). To prove Part (v), let $(F_{i,j}\colon
1\leq i\leq k,1\leq j\leq r_{i})$ be a standard $M$-representation of
$\Omega$. Then by the property of standard $M$-representations, all of
$F_{i,j}\colon k-k^{\prime}+1\leq i\leq k,1\leq j\leq r_{i}$ are independent
of $n_{1},\dots,n_{k^{\prime}}$, and no nontrivial linear combination of
$F_{i,j}\colon k-k^{\prime}+1\leq i\leq k,1\leq j\leq r_{i}$ is a constant.
The conclusion now follows from Proposition B.3 (iv).

Part (vi) is a consequence of Theorem C.3 (i) and (ii). Part (vii) follows
from Lemma B.1 and the fact that there are in total $\binom{k+1}{2}$ quadratic
terms of the form $n_{i}n_{j},1\leq i,j\leq k$. ∎

##  Appendix D Irreducibility for Nice $M$-sets

We present the proof of Theorem 9.14 in this appendix. We restate this theorem
below for convenience.

######  Theorem D.1 (Nice and consistent $M$-sets are irreducible).

Let $d,K\in\mathbb{N}_{+},s\in\mathbb{N}$, $p$ be a prime, and $\delta>0$. Let
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a non-degenerate quadratic
form and $\Omega\subseteq(\mathbb{F}_{p}^{d})^{K}$ be a nice and consistent
$M$-set. If $d\geq\max\\{2r_{M}(\Omega)+1,4K-1\\}$ and
$p\gg_{d,s}\delta^{-O_{d,s}(1)}$, then

  1. (i)

$\Omega$ is $\delta$-irreducible up to degree $s$;

  2. (ii)

$\tau(\Omega)$ is weakly $(\delta,p)$-irreducible up to degree $s$;

  3. (iii)

$\tau(\Omega)$ is strongly $(\delta,p)$-irreducible up to degree $s$.

###  D.1. Irreducible property for a sample $M$-set

The proof of Theorem D.1 is very technical. So we begin with the following
special case of Theorem D.1 to explain the main ideas:

######  Proposition D.2.

Let $d\in\mathbb{N}_{+},s\in\mathbb{N}$, $p$ be a prime, and $\delta>0$. Let
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a non-degenerate quadratic
form given by $M(n):=n\cdot n$. If $d\gg_{s}1$ and
$p\gg_{d}\delta^{-O_{d}(1)}$, then the set $\Box_{3}(V(M))$ is
$\delta$-irreducible up to degree $s$.

We will only provide a sketch of the proof of Proposition D.2 to explain the
main idea, as the rigorous proof of Theorem D.1 will be provided in later
sections. Note that $(n,h_{1},h_{2},h_{3})\in\Box_{3}(V(M))$ if and only if
$(n,h_{1},h_{2})\in\Box_{2}(V(M))$ and $M(n+h_{3})=h_{1}\cdot h_{3}=h_{2}\cdot
h_{3}=0.$ Suppose we have shown that $\Box_{2}(V(M))$ is $\delta$-irreducible
for all $\delta>0$ if $p\gg_{d}\delta^{-O_{d}(1)}$ and we wish to show that
the same holds from $\Box_{3}(V(M))$. Let
$P\colon(\mathbb{F}_{p}^{d})^{4}\to\mathbb{F}_{p}$ be a polynomial of degree
$s$ such that $|V(P)\cap\Box_{3}(V(M))|>\delta|\Box_{3}(V(M))|$.

Step 1: a parametrization for the last variable. We first denote
$x:=(n,h_{1},h_{2})\in\Box_{2}(V(M))$ and express $h_{3}$ as a function of
$x$. For convenience denote $h_{i}=(h_{i,1},h_{i,2},h^{\prime}_{i})$ for some
$h_{i,1},h_{i,2}\in\mathbb{F}_{p}$ and $h^{\prime}_{i}\in\mathbb{F}_{p}^{d-2}$
for $i=1,2,3$. If
$\Delta_{1,2}(h_{1},h_{2}):=\begin{vmatrix}h_{1,1}&h_{1,2}\\\
h_{2,1}&h_{2,2}\end{vmatrix}\neq 0$, then let
$\phi_{x}\colon\mathbb{F}_{p}^{d-2}\to\mathbb{F}_{p}^{d}$ denote the linear
transformation given by

$\phi_{x}(h^{\prime}_{3})=\Bigl{(}\frac{\begin{vmatrix}-h^{\prime}_{1}\cdot
h^{\prime}_{3}&h_{1,2}\\\ -h^{\prime}_{2}\cdot
h^{\prime}_{3}&h_{2,2}\end{vmatrix}}{\Delta_{1,2}(h_{1},h_{2})},\frac{\begin{vmatrix}h_{1,1}&-h^{\prime}_{1}\cdot
h^{\prime}_{3}\\\ h_{2,1}&-h^{\prime}_{2}\cdot
h^{\prime}_{3}\end{vmatrix}}{\Delta_{1,2}(h_{1},h_{2})},h^{\prime}_{3}\Bigr{)}.$

It is not hard to see that $h_{1}\cdot h_{3}=h_{2}\cdot h_{3}=0$ if and only
if $h_{3}=\phi_{x}(w)$ for some $w\in\mathbb{F}_{p}^{d-2}$. Then for all
$x\in\Box_{2}(V(M))$ with $\Delta_{1,2}(h_{1},h_{2})\neq 0$,
$(x,\phi_{x}(w))\in\Box_{3}(V(M))\cap V(P)$ if and only if
$P(x,\phi_{x}(w))=M(n+\phi_{x}(w))=0$.

Note that $M(n+\phi_{x}(\cdot))$ is a non-degenerate quadratic form for most
of $x\in\Box_{2}(V(M))$. We may write

$M(n+\phi_{x}(w_{3},\dots,w_{d}))=\sum_{3\leq i\leq j\leq
d}\Delta_{1,2}(h_{1},h_{2})^{-2}G_{1,2,i,j}(x)w_{i}w_{j}$

for some polynomials $G_{1,2,i,j}$ of degree $O(1)$.

Step 2: a factorization for the target polynomial. Next we treat $P(x,\cdot)$
as a polynomial of $h_{3}$ to derive some properties for $P$ using the results
from Section 6. Since $|\Box_{2}(V(M))|=O(p^{2d-4})$ and
$|\Box_{3}(V(M))|=O(p^{3d-7})$ by Corollary C.7, the fact
$|V(P)\cap\Box_{3}(V(M))|>\delta|\Box_{3}(V(M))|$ implies that
$|V(P(x,\phi_{x}(\cdot))\cap V(M(n+\phi_{x}(\cdot)))|>\delta p^{d-3}$ for many
$x\in\Box_{1}(V(M))$. By Lemma 6.1, we have that
$V(M(n+\phi_{x}(\cdot)))\subseteq V(P(x,\phi_{x}(\cdot)))$ for many of
$x\in\Box_{2}(V(M))$. By Proposition 6.3 and a change of variable, if
$G_{1,2,i,j}(x)\neq 0$, then $M(n+\phi_{x}(\cdot))$ divides
$P(x,\phi_{x}(\cdot))$ with respect to the $B_{i,j}$-standard long division
algorithm. So we may write

(D.1) $P(x,\phi_{x}(w))=M(n+\phi_{x}(w))R_{x}(w)$

for some polynomial $R_{x}$ of degree at most $s-2$. Since every coefficient
of $P(x,\phi_{x}(\cdot))$ can be written as a polynomial in $x$ of degree
$O(s)$ divided by $\Delta_{1,2}(h_{1},h_{2})^{s}$ and every coefficient of
$M(n+\phi_{x}(w))$ can be written as a polynomial in $x$ of degree $O(1)$
divided by $\Delta_{1,2}(h_{1},h_{2})^{2}$, we have that $R_{x}$ takes the
form (assuming that $s\geq 2$)

$R_{x}(w)=R(x,w)/(G_{1,2,i,j}(x)\Delta_{1,2}(h_{1},h_{2}))^{s}$

for some polynomial $R$ of degree $O(s)$. By (D.1), we have that

(D.2)
$(G_{1,2,i,j}(x)\Delta_{1,2}(h_{1},h_{2}))^{s}P(x,\phi_{x}(w))-M(n+\phi_{x}(w))R(x,w)=0$

for many $x\in\Box_{2}(V(M))$ for all $w\in\mathbb{F}_{p}^{d-2}$. Note that
the left hand side of (D.2) can be written as
$\sum_{i\in\mathbb{N}^{d-2}}C_{i}(x)w^{i}$ for some polynomial $C_{i}$. So
$C_{i}(x)=0$ for many $x\in\Box_{2}(V(M))$ for all $i\in\mathbb{N}^{d-2}$. By
induction hypothesis, we have that $C_{i}\equiv 0$ and thus (D.2) holds for
all $x\in\Box_{2}(V(M))$ and $w\in\mathbb{F}_{p}^{d-2}$.

Note that if $\Delta_{1,2}(h_{1},h_{2})\neq 0$, then

$\frac{\begin{vmatrix}-h^{\prime}_{1}\cdot h^{\prime}_{3}&h_{1,2}\\\
-h^{\prime}_{2}\cdot
h^{\prime}_{3}&h_{2,2}\end{vmatrix}}{\Delta_{1,2}(h_{1},h_{2})}-h_{3,1}=\frac{\begin{vmatrix}-h_{1}\cdot
h_{3}&h_{1,2}\\\ -h_{2}\cdot
h_{3}&h_{2,2}\end{vmatrix}}{\Delta_{1,2}(h_{1},h_{2})}\text{ and
}\frac{\begin{vmatrix}h_{1,1}&-h^{\prime}_{1}\cdot h^{\prime}_{3}\\\
h_{2,1}&-h^{\prime}_{2}\cdot
h^{\prime}_{3}\end{vmatrix}}{\Delta_{1,2}(h_{1},h_{2})}-h_{3,2}=\frac{\begin{vmatrix}h_{1,1}&-h_{1}\cdot
h_{3}\\\ h_{2,1}&-h_{2}\cdot h_{3}\end{vmatrix}}{\Delta_{1,2}(h_{1},h_{2})}.$

So $P(x,\phi_{x}(h^{\prime}_{3}))-P(x,h_{3})$ can be written as
$\Delta_{1,2}(h_{1},h_{2})^{-s}((h_{1}\cdot
h_{3})P^{\prime}_{1}(x,h_{3})+(h_{2}\cdot h_{3})P^{\prime}_{2}(x,h_{3}))$ for
some polynomials $P^{\prime}_{1}$ and $P^{\prime}_{2}$ of degree $O(s)$, and
$M(n+\phi_{x}(h^{\prime}_{3}))-M(h_{3})$ can be written as
$\Delta_{1,2}(h_{1},h_{2})^{-2}((h_{1}\cdot
h_{3})M^{\prime}_{1}(x,h_{3})+(h_{2}\cdot h_{3})M^{\prime}_{2}(x,h_{3}))$ for
some polynomials $P^{\prime}_{1}$ and $P^{\prime}_{2}$ of degree $O(1)$. By
(D.2), we have that

$(G_{1,2,i,j}(x)\Delta_{1,2}(h_{1},h_{2}))^{s}P(x,h_{3})=M(n+h_{3})R_{0}(x,h_{3})+(h_{1}\cdot
h_{3})R_{1}(x,h_{3})+(h_{2}\cdot h_{3})R_{2}(x,h_{3})$

for some polynomials $R_{1},R_{2},R_{3}$ of degree $O(s)$ for all
$x\in\Box_{2}(V(M))$ with $\Delta_{1,2}(h_{1},h_{2})\neq 0$ and for all
$h_{3}\in\mathbb{F}_{p}^{d}$. So

(D.3)
$(G_{1,2,i,j}(n,h_{1},h_{2},h_{3})\Delta_{1,2}(h_{1},h_{2}))^{s}P(n,h_{1},h_{2},h_{3})=0$

for all $(n,h_{1},h_{2},h_{3})\in\Box_{3}(V(M))$ with
$\Delta_{1,2}(h_{1},h_{2})\neq 0$. Moreover, it is not hard to see that (D.3)
also holds if $\Delta_{1,2}(h_{1},h_{2})=0$.

Step 3: removing the $(G_{1,2,i,j}(x)\Delta_{1,2}(h_{1},h_{2}))^{s}$ term
using a parametrization trick. It follows from (D.3) that for all
$(n,h_{1},h_{2},h_{3})\in\Box_{3}(V(M))$, either $P(n,h_{1},h_{2},h_{3})=0$ or
$G_{1,2,i,j}(x)\Delta_{1,2}(h_{1},h_{2})=0$ for all $3\leq i\leq j\leq d$.
Since $M(n+\phi_{x}(\cdot))$ is non-degenerate, at least one of
$G_{1,2,i,j}(x)$ is nonzero. So we have that for all
$(n,h_{1},h_{2},h_{3})\in\Box_{3}(V(M))$, either $P(n,h_{1},h_{2},h_{3})=0$ or
$\Delta_{1,2}(h_{1},h_{2})=0$ for all $3\leq i\leq j\leq d$. We are close to
the conclusion that $\Box_{3}(V(M))\subseteq V(P)$. However, we need some more
effort dealing with the $\Delta_{1,2}(h_{1},h_{2})$ term.

Denote $\Delta_{i,j}(h_{1},h_{2}):=\begin{vmatrix}h_{1,i}&h_{1,j}\\\
h_{2,i}&h_{2,j}\end{vmatrix}$ for all $1\leq i<j\leq d$. Using a similar
argument as above, we have that for all
$(n,h_{1},h_{2},h_{3})\in\Box_{3}(V(M))$, either $P(n,h_{1},h_{2},h_{3})=0$ or
$\Delta_{i,j}(h_{1},h_{2})=0$ for all $1\leq i<j\leq d$. This is equivalent of
saying that $P(n,h_{1},h_{2},h_{3})=0$ unless $h_{1}$ is parallel to $h_{2}$.
To deal with the case when $h_{1}$ is parallel to $h_{2}$, we use a
parametrization trick. Fix any such $(n,h_{1},h_{2},h_{3})$ and define
$f(t):=P(n,h_{1}+tv,h_{2},h_{3})$ for all $t\in\mathbb{F}_{p}$, where
$v\in\mathbb{F}_{p}^{d}$ is any vector not parallel to $h_{2}$. Then
$f\colon\mathbb{F}_{p}\to\mathbb{F}_{p}$ is a polynomial of degree at most
$s$. Note that $h_{1}+tv,h_{2}$ is not parallel to $h_{2}$ unless $t=0$. So
$f(t)=0$ for all $t\in\mathbb{F}_{p}\backslash\\{0\\}$. By Lemma 4.10, this
implies that $f\equiv 0$ and thus $f(0)=P(n,h_{1},h_{2},h_{3})=0$. This
completes the proof of Proposition D.2.

###  D.2. Some preliminary reductions

We start with some reductions before proving Theorem D.1. In the rest of this
section, if $f(n_{1},\dots,n_{K})$ is a function depending only on
$n_{1},\dots,n_{i}$ for some $i\leq K$, then we write
$f(n_{1},\dots,n_{i})=f(n_{1},\dots,n_{K})$ for convenience. Throughout we
assume that $p\gg_{d,s}\delta^{-O_{d,s}(1)}$.

By Propositions B.3 (iii), 9.11 and 9.13, we may assume without loss of
generality that $\Omega=V(\mathcal{J})$ for some nice and consistent
$(M,K)$-family $\mathcal{J}$.

Let $A$ be the matrix associated with $M$. Since $A$ is non-degenerate and
symmetric, there exists a $d\times d$ invertible matrix $B$ such that
$BAB^{T}$ is symmetric, diagonal and non-degenerate. Note that if
$F\colon(\mathbb{F}_{p}^{d})^{K}\to\mathbb{F}_{p}$ is a nice $(M,K)$-integral
quadratic function, then
$F^{\prime}(n_{1},\dots,n_{K}):=F(n_{1}B,\dots,n_{K}B)$ is a nice
$(M^{\prime},K)$-integral quadratic function, where $M^{\prime}$ is any
quadratic form associated with the matrix $BAB^{T}$. Moreover, the set of
$(n_{1},\dots,n_{K})\in(\mathbb{F}_{p}^{d})^{K}$ such that
$(n_{1}B,\dots,n_{K}B)\in\Omega$ is a nice and consistent $M$-set of total co-
dimension $r_{M}(\Omega)$. So by Proposition 9.13, it suffices to prove
Theorem D.1 under the assumption that $A$ is diagonal.

By Lemma B.1, $\Omega$ admits a nice and standard $M$-representation
$(F_{i,j},1\leq i\leq K,1\leq j\leq r_{i})$ for some $0\leq r_{i}\leq i$ with
$r_{1}+\dots+r_{i}=r_{M}(\Omega)$. Assume that

(D.4) $F_{i,1}(n_{1},\dots,n_{K})=c_{i}(n_{i}A)\cdot n_{i}+(n_{i}A)\cdot
L_{i,1}(n_{1},\dots,n_{i-1})+u_{i,0}$

and that

(D.5) $F_{i,j}(n_{1},\dots,n_{K})=(n_{i}A)\cdot
L_{i,j}(n_{1},\dots,n_{i-1})+u_{i,j}$

for all $1\leq i\leq K$ and $2\leq j\leq r_{i}$ for some $c_{i}\in\\{0,1\\}$,
some $u_{i,j}\in\mathbb{F}_{p}$ and some $d$-integral linear transformations
$L_{i,j}\colon(\mathbb{F}_{p}^{d})^{i-1}\to\mathbb{F}_{p}^{d}$ given by

$L_{i,j}(n_{1},\dots,n_{i-1})=u_{i,j,i-1}n_{i-1}+\dots+u_{i,j,1}n_{1}$

for some $u_{i,j,\ell}\in\mathbb{F}_{p}$ such that the $r_{i}\times i$ matrix
$\begin{bmatrix}c_{i}&u_{i,1,i-1}&\dots&u_{i,1,1}\\\
0&u_{i,2,i-1}&\dots&u_{i,2,1}\\\ \dots&\dots&\dots&\dots\\\
0&u_{i,r_{i},i-1}&\dots&u_{i,r_{i},1}\end{bmatrix}$ is in the reduced row
echelon form and is of rank $r_{i}$. In particular,
$L_{i,2},\dots,L_{i,r_{i}}$ are linearly independent if $c_{i}=1$, and
$L_{i,1},\dots,L_{i,r_{i}}$ are linearly independent if $c_{i}=0$. For
convenience we say that $(c_{1},\dots,c_{K})\in\\{0,1\\}^{K}$ is the _type_ of
$\Omega$.

We first prove Part (i) of Theorem D.1. For $1\leq k\leq K$, denote
$\Omega_{k}:=\cap_{i=1}^{k}\cap_{j=1}^{r_{i}}V(F_{i,j})$. We prove by
induction that Part (i) of Theorem D.1 holds for $\Omega_{k}$ for all $1\leq
k\leq K$.

Suppose we have proved that Part (i) of Theorem D.1 holds for $\Omega_{k-1}$
for some $k\geq 1$. We prove that Part (i) of Theorem D.1 holds for
$\Omega_{k}$ (when $k=0$, we prove that Part (i) of Theorem D.1 holds for
$\Omega_{1}$ without any induction hypothesis). If $r_{k}=0$, then
$\Omega_{k}=\Omega_{k-1}\times\mathbb{F}_{p}^{d}$ and so Part (i) of Theorem
D.1 follows from Proposition 9.12 and the induction hypothesis. So we assume
that $r_{k}\geq 1$.

For convenience denote $r:=r_{M}(\Omega_{k})=r_{1}+\dots+r_{k}\leq
r_{M}(\Omega)$. Write $\mathbb{n}^{\prime}=(n_{1},\dots,n_{k-1})$ and
$n_{i}=(n_{i,1},\dots,n_{i,d})$ for some $n_{i,j}\in\mathbb{F}_{p}$ for all
$1\leq i\leq k$. For $1\leq i\leq k$ and $I\subseteq\\{1,\dots,d\\}$, write
$n_{i,I}:=(n_{i,j})_{j\in I}$. For
$\mathbb{n}^{\prime}\in(\mathbb{F}_{p}^{d})^{k-1}$, let
$\Omega_{k}(\mathbb{n}^{\prime})$ denote the set of
$n_{k}\in\mathbb{F}_{p}^{d}$ such that $F_{k,j}(\mathbb{n}^{\prime},n_{k})=0$
for all $0\leq j\leq r_{k}$. It is clear that
$(\mathbb{n}^{\prime},n_{k})\in\Omega_{k}$ if and only if
$\mathbb{n}^{\prime}\in\Omega_{k-1}$ and
$n_{k}\in\Omega_{k}(\mathbb{n}^{\prime})$.

###  D.3. Proof of Part (i) of Theorem D.1 for the non-degenerate case

We follow the steps similar to Proposition D.2. Depending only whether
$c_{k}=0$ or 1, the proofs are slightly different. We start with the case when
$c_{k}=1$. In this case $r_{k}\leq k$.

Step 1: a parametrization for the last variable. Write

$L_{k,j}(\mathbb{n}^{\prime})A=(S_{k,j,1}(\mathbb{n}^{\prime}),\dots,S_{k,j,d}(\mathbb{n}^{\prime}))$

for some polynomials
$S_{k,j,1},\dots,S_{k,j,d}\colon(\mathbb{F}_{p}^{d})^{k-1}\to\mathbb{F}_{p}$
of degree at most 1. Since $A$ is diagonal, for all $1\leq\ell\leq d$,
$S_{k,j,\ell}(\mathbb{n}^{\prime})$ is dependent only on $n_{i,\ell},1\leq
i\leq k-1$. Then we may rewrite (D.5) as

(D.6)
$F_{k,j}(\mathbb{n}^{\prime},n_{k})=\sum_{\ell=1}^{d}n_{k,\ell}S_{k,j,\ell}(\mathbb{n}^{\prime})+u_{k,j},$

for all $2\leq j\leq r_{i}$.

For $I\subseteq\\{1,\dots,d\\}$ with $|I|=r_{k}-1>0$, let
$\Delta_{k,I}(\mathbb{n}^{\prime})$ denote the determinant of the
$(r_{k}-1)\times(r_{k}-1)$ matrix $(S_{k,j,\ell}(\mathbb{n}^{\prime}))_{2\leq
j\leq r_{k},\ell\in I}$. If $r_{k}=1$ and $I=\emptyset$, then let
$\Delta_{k,I}(\mathbb{n}^{\prime})\equiv 1$. Then $\Delta_{k,I}$ is a
polynomial from $(\mathbb{F}_{p}^{d})^{k}$ to $\mathbb{F}_{p}$ of degree at
most $r_{k}-1$ depending only on $n_{i,\ell},1\leq i\leq k-1,\ell\in I$ (since
$A$ is diagonal). For convenience denote $I^{c}:=\\{1,\dots,d\\}\backslash I$.
Fix any $\mathbb{n}^{\prime}\in\Omega_{k-1}$ with
$\Delta_{k,I}(\mathbb{n}^{\prime})\neq 0$. Then
$L_{k,j}(\mathbb{n}^{\prime})A,2\leq j\leq r_{k}$ are linearly independent. By
(D.6) and the knowledge of linear algebra,
$F_{k,2}(\mathbb{n}^{\prime},n_{k})=\dots=F_{k,r_{k}}(\mathbb{n}^{\prime},n_{k})=0$
if and only if for all $\ell^{\prime}\in I$,

(D.7)
$n_{k,\ell^{\prime}}=\frac{R_{k,I,\ell^{\prime}}(\mathbb{n}^{\prime},n_{k,I^{c}})}{\Delta_{k,I}(\mathbb{n}^{\prime})},$

where $R_{k,I,\ell^{\prime}}(\mathbb{n}^{\prime},n_{k,I^{c}})$ is the
determinant of the $(r_{k}-1)\times(r_{k}-1)$ matrix obtained by replacing the
column $(S_{k,j,\ell^{\prime}}(\mathbb{n}^{\prime}))_{2\leq j\leq r_{k}}$ from
$(S_{k,j,\ell^{\prime\prime}}(\mathbb{n}^{\prime}))_{2\leq j\leq
r_{k},\ell^{\prime\prime}\in I}$ by
$(R_{k,I,j,\ell^{\prime}}(\mathbb{n}^{\prime},n_{k,I^{c}}))_{2\leq j\leq
r_{k}}$ where

(D.8)
$R_{k,I,j,\ell^{\prime}}(\mathbb{n}^{\prime},n_{k,I^{c}})=-u_{k,j}-\sum_{\ell\in
I^{c}}n_{k,\ell}S_{k,j,\ell}(\mathbb{n}^{\prime})=-F_{k,j}(\mathbb{n}^{\prime},n_{k})+\sum_{\ell\in
I}n_{k,\ell}S_{k,j,\ell}(\mathbb{n}^{\prime}).$

Let $\Delta_{k,I,\ell,\ell^{\prime}}(\mathbb{n}^{\prime})$ be the determinant
of the $(r_{k}-1)\times(r_{k}-1)$ matrix obtained by replacing the column
$(S_{k,j,\ell^{\prime}}(\mathbb{n}^{\prime}))_{2\leq j\leq r_{k}}$ from
$(S_{k,j,\ell^{\prime\prime}}(\mathbb{n}^{\prime}))_{2\leq j\leq
r_{k},\ell^{\prime\prime}\in I}$ by the column
$(S_{k,j,\ell}(\mathbb{n}^{\prime}))_{2\leq j\leq r_{k}}$, and let
$Q_{k,I,\ell^{\prime}}(\mathbb{n}^{\prime})$ be the determinant of the
$(r_{k}-1)\times(r_{k}-1)$ matrix obtained by replacing the column
$(S_{k,j,\ell^{\prime}}(\mathbb{n}^{\prime}))_{2\leq j\leq r_{k}}$ from
$(S_{k,j,\ell^{\prime\prime}}(\mathbb{n}^{\prime}))_{2\leq j\leq
r_{k},\ell^{\prime\prime}\in I}$ by the column $(-u_{k,j})_{2\leq j\leq
r_{k}}$. It follows from (D.8) that

(D.9)
$\begin{split}R_{k,I,\ell^{\prime}}(\mathbb{n}^{\prime},n_{k,I^{c}})=Q_{k,I,\ell^{\prime}}(\mathbb{n}^{\prime})-\sum_{\ell\in
I^{c}}n_{k,\ell}\Delta_{k,I,\ell,\ell^{\prime}}(\mathbb{n}^{\prime}).\end{split}$

For convenience we regard $\mathbb{F}_{p}^{d-r_{k}+1}$ as the set of
$n_{k,I^{c}}=(n_{k,\ell})_{\ell\in I^{c}},n_{k,\ell}\in\mathbb{F}_{p}$, i.e.
the coordinates in $\mathbb{F}_{p}^{d-r_{k}+1}$ are not labeled by
$\\{1,\dots,d-r_{k}+1\\}$, but by $I^{c}$. Let
$\phi_{k,I,\mathbb{n}^{\prime}}\colon\mathbb{F}_{p}^{d-r_{k}+1}\to\mathbb{F}_{p}^{d}$,
be the map from $n_{k,I^{c}}$ to $(m_{\ell})_{1\leq\ell\leq d}$ given by
$m_{\ell}=n_{k,\ell}$ for $\ell\in I^{c}$, and $m_{\ell}$ be the quantity
$n_{k,\ell}$ defined in (D.7) for all $\ell\in I$. Then
$\phi_{k,I,\mathbb{n}^{\prime}}$ is a polynomial of degree at most 1 of with
respect to $n_{k,\ell}$ for all $\ell\in I^{c}$. By (D.4), we may denote

(D.10)
$F_{I,k,1}(\mathbb{n}^{\prime},m):=F_{k,1}(\mathbb{n}^{\prime},\phi_{k,I,\mathbb{n}^{\prime}}(m))=(\phi_{k,I,\mathbb{n}^{\prime}}(m)A)\cdot\phi_{k,I,\mathbb{n}^{\prime}}(m)+L_{k,1}(\mathbb{n}^{\prime})A\cdot\phi_{k,I,\mathbb{n}^{\prime}}(m)+u_{k,1}$

for all $\mathbb{n}^{\prime}\in\Omega_{k-1}$ with
$\Delta_{k,I}(\mathbb{n}^{\prime})\neq 0$ and $m\in\mathbb{F}_{p}^{d-r_{k}+1}$
(recall that $c_{k}=1$). Then for all $\mathbb{n}^{\prime}\in\Omega_{k-1}$
with $\Delta_{k,I}(\mathbb{n}^{\prime})\neq 0$ and
$n_{k}\in\mathbb{F}_{p}^{d}$,

(D.11) $n_{k}\in\Omega_{k}(\mathbb{n}^{\prime})$ $\Leftrightarrow$
$n_{k}=\phi_{k,I,\mathbb{n}^{\prime}}(m)$ for some
$m\in\mathbb{F}_{p}^{d-r_{k}+1}$ with $F_{I,k,1}(\mathbb{n}^{\prime},m)=0$.

Assume that the diagonal of the matrix $A$ is $(a_{1},\dots,a_{d})$. It
follows from (D.7), (D.9), and (D.10) that
$F_{I,k,1}(\mathbb{n}^{\prime},n_{k,I^{c}})$ equals to

$\begin{split}\sum_{\ell\in
I^{c}}a_{\ell}n_{k,\ell}^{2}+\sum_{\ell^{\prime}\in
I}a_{\ell^{\prime}}(\Delta_{k,I}(\mathbb{n}^{\prime}))^{-2}\Bigl{(}Q_{k,I,\ell^{\prime}}(\mathbb{n}^{\prime})-\sum_{\ell\in
I^{c}}n_{k,\ell}\Delta_{k,I,\ell,\ell^{\prime}}(\mathbb{n}^{\prime})\Bigr{)}^{2}\end{split}$

plus a polynomial which is of degree at most 1 in the variable $n_{k,I^{c}}$.
Since $S_{k,j,\ell}$ are of degree at most 1, we have that
$Q_{k,I,\ell^{\prime}}$ and
$\Delta_{k,I,\ell,\ell^{\prime}}(\mathbb{n}^{\prime})$ are polynomials of
degrees at most $r_{k}-1$. Since $S_{k,j,\ell}(\mathbb{n}^{\prime})$ is
dependent only on $n_{i,\ell}$ for $1\leq i\leq k-1$, we have that
$\Delta_{k,I,\ell,\ell^{\prime}}(\mathbb{n}^{\prime})$ is dependent only on
$n_{i,j},1\leq i\leq k-1,j\in(I\cup\\{\ell\\})\backslash\\{\ell^{\prime}\\}$.
Therefore, for all $\ell,\ell^{\prime}\in I^{c}$, the coefficient of the
$n_{k,\ell}n_{k,\ell^{\prime}}$ term of $F_{I,k,0}(\mathbb{n}^{\prime},\cdot)$
can be written in the form

(D.12)
$\begin{split}\text{$2G_{k,I,\ell,\ell^{\prime}}(\mathbb{n}^{\prime})(\Delta_{I}(\mathbb{n}^{\prime}))^{-2}$
if $\ell\neq\ell^{\prime}$ and
$G_{k,I,\ell,\ell}(\mathbb{n}^{\prime})(\Delta_{I}(\mathbb{n}^{\prime}))^{-2}$
if $\ell=\ell^{\prime}$}\end{split}$

for some polynomial $G_{k,I,\ell,\ell^{\prime}}$ of degree at most $2r_{k}$
which depends only on $n_{i,j},1\leq i\leq k-1,j\in
I\cup\\{\ell,\ell^{\prime}\\}$. If $I=\emptyset$, then we denote
$G_{k,I,\ell,\ell^{\prime}}\equiv 1$.

Note that $\\{\phi_{k,I,\mathbb{n}^{\prime}}(m)\colon
m\in\mathbb{F}_{p}^{d-r_{k}+1}\\}$ is an affine subspace of
$\mathbb{F}_{p}^{d}$ of co-dimension $r_{k}-1$, by Proposition 4.8,
$F_{I,k,1}(\mathbb{n}^{\prime},\cdot)$ is a quadratic form of rank at least
$d-2(r_{k}-1)\geq 3$. Let $A_{k,I,\mathbb{n}^{\prime}}$ be the
$(d-r_{k}+1)\times(d-r_{k}+1)$ matrix associated to
$F_{I,k,1}(\mathbb{n}^{\prime},\cdot)$. Let $i_{\ast}$ be the smallest element
in $I^{c}$. For $i_{1}\in I^{c}$, let
$\phi_{I,i_{1},i_{1}}\colon\mathbb{F}_{p}^{d-r_{k}+1}\to\mathbb{F}_{p}^{d-r_{k}+1}$
denote the bijective linear transformations given by switching the $i_{1}$-th
and $i_{\ast}$-th components of $n_{k,I^{c}}$. For $i_{1},i_{2}\in
I^{c},i_{1}<i_{2}$, let
$\phi_{I,i_{1},i_{2}}\colon\mathbb{F}_{p}^{d-r_{k}+1}\to\mathbb{F}_{p}^{d-r_{k}+1}$
denote the bijective linear transformation which maps
$n_{k,I^{c}}=(n_{k,\ell})_{\ell\in I^{c}}$ to a vector whose first component
(i.e. the $i_{\ast}$-th component) equals to
$\frac{1}{2}(n_{k,i_{1}}+n_{k,i_{2}})$, second component equals to
$\frac{1}{2}(n_{k,i_{1}}-n_{k,i_{2}})$, and the remaining comments equal to
$(n_{k,\ell})_{\ell\in(I\cup\\{i_{1},i_{2}\\})^{c}}$ ordered in an arbitrary
way. Let $B_{I,i_{1},i_{2}}$ be the $(d-r_{k}+1)\times(d-r_{k}+1)$ matrix
induced by the bijective linear transformation $\phi_{I,i_{1},i_{2}}$. This
construction is similar the $B_{i,j}$-standard matrix defined in Lemma 6.2. We
have that for all $i_{1},i_{2}\in I^{c}$, $B_{I,i_{1},i_{2}}$ is an
$(d-r_{k}+1)\times(d-r_{k}+1)$ invertible matrix such that the
$(i_{\ast},i_{\ast})$-th entry of
$B_{I,i_{1},i_{2}}A_{k,I,\mathbb{n}^{\prime}}B^{T}_{k,I,i_{1},i_{2}}$ equals
to the $(i_{1},i_{2})$-th entry of $A_{k,I,\mathbb{n}^{\prime}}$.

It is not hard to see from (D.12) that for all $i_{1},i_{2}\in I^{c},i_{1}\leq
i_{2}$, the coefficient of the $(i_{\ast},i_{\ast})$-entry of
$B_{I,i_{1},i_{2}}A_{k,I,\mathbb{n}^{\prime}}B^{T}_{I,i_{1},i_{2}}$ can be
written as
$G_{k,I,i_{1},i_{2}}(\mathbb{n}^{\prime})/(\Delta_{I}(\mathbb{n}^{\prime}))^{2}$.
Since $f_{I,k,1}(\mathbb{n}^{\prime},\cdot)$ is not constant zero (recall that
$F_{I,k,1}(\mathbb{n}^{\prime},\cdot)$ is of rank at least 3), we have:

######  Lemma D.3.

For every $1\leq k\leq K$, every $I\subseteq\\{1,\dots,d\\}$ with
$|I|=r_{k}-1$ and every $\mathbb{n}^{\prime}\in(\mathbb{F}_{p}^{d})^{k-1}$,
there exist $i_{1},i_{2}\in I^{c},i_{1}\leq i_{2}$ such that
$G_{k,I,i_{1},i_{2}}(\mathbb{n}^{\prime})\neq 0$.

Let $Z_{k,I,i_{1},i_{2}}$ denote the set of
$(\mathbb{n}^{\prime},n_{k})\in(\mathbb{F}_{p}^{d})^{k}$ such that
$\Delta_{k,I}(\mathbb{n}^{\prime}),G_{k,I,i_{1},i_{2}}(\mathbb{n}^{\prime})\neq
0$. We need the following estimate.

######  Lemma D.4.

If $G_{k,I,i_{1},i_{2}}$ is not constant zero, then we have that
$|{Z}^{c}_{k,I,i_{1},i_{2}}\cap\Omega_{k}|\leq\delta p^{dk-r}/2$.

###### Proof.

Let $Z^{\prime}$ denote the set of $\mathbb{n}^{\prime}\in\Omega_{k-1}$ such
that either $G_{k,I,i_{1},i_{2}}(\mathbb{n}^{\prime})=0$ or
$\Delta_{k,I}(\mathbb{n}^{\prime})=0$. Let $Z$ be the set of
$\mathbb{n}^{\prime}\in\Omega_{k-1}$ such that
$|\Omega_{k}(\mathbb{n}^{\prime})|$ is not $p^{d-r_{k}}(1+O_{k}(p^{-1/2}))$.
By Theorem C.3 (ii), (setting $k^{\prime}=k-1,r^{\prime}_{k^{\prime}}=r_{k}$
and $\text{rank}(M)=d$), we have that $|Z|=O_{k}(p^{d(k-2)+r_{k}-1})$. Again
by Theorem C.3, we have that

$\begin{split}&\quad|{Z}^{c}_{k,I,i_{1},i_{2}}\cap\Omega_{k}|=\sum_{\mathbb{n}^{\prime}\in
Z^{\prime}\backslash
Z}|\Omega_{k}(\mathbb{n}^{\prime})|+\sum_{\mathbb{n}^{\prime}\in
Z^{\prime}\cap Z}|\Omega_{k}(\mathbb{n}^{\prime})|\\\ &\leq|Z^{\prime}|\cdot
p^{d-r_{k}}(1+O_{k}(p^{-1/2}))+O_{k}(p^{d(k-1)+r_{k}-1}).\end{split}$

Since $d\geq 2r+1$, we have $d(k-1)+r_{k}-1<dk-r$. So it suffices to show that
$|Z^{\prime}|\leq\delta p^{d(k-1)-(r-r_{k})}/4$. If not, then one of
$|V(G_{k,I,i_{1},i_{2}})\cap\Omega_{k-1}|$ and
$|V(\Delta_{k,I})\cap\Omega_{k-1}|$ is larger than $\delta
p^{d(k-1)-(r-r_{k})}/8$. Applying Theorem C.3 to compute the cardinality of