# Spherical higher order Fourier analysis over finite fields II: additive
combinatorics for shifted ideals

Wenbo Sun  Department of Mathematics, Virginia Tech, 225 Stanger Street,
Blacksburg, VA, 24061, USA<EMAIL_ADDRESS>
###### Abstract.

This paper is the second part of the series _Spherical higher order Fourier
analysis over finite fields_ , aiming to develop the higher order Fourier
analysis method along spheres over finite fields, and to solve the geometric
Ramsey conjecture in the finite field setting.

In this paper, we study additive combinatorial properties for shifted ideals,
i.e. the structure of sets of the form $E\pm E$, where $E$ is a collection of
shifted ideals of the polynomial ring $\mathbb{F}_{p}[x_{1},\dots,x_{d}]$ and
we identify two ideals if their difference contains the zero polynomial. We
show that under appropriate definitions, the set $E\pm E$ enjoys properties
similar to the conventional setting where $E$ is a subset of an abelian group.
In particular, among other results, we prove the Balog-Gowers-Szemerédi
theorem, the Rusza’s quasi triangle inequality and a weak form of the
Plünnecke-Rusza theorem in the setting of shifted ideals. We also show that
for a special class of maps $\xi$ from $\mathbb{F}_{p}^{d}$ to the collection
of all shifted ideals of $\mathbb{F}_{p}[x_{1},\dots,x_{d}]$, if the set
$\xi(\mathbb{F}_{p}^{d})+\xi(\mathbb{F}_{p}^{d})$ has large additive energy,
then $\xi$ is an almost linear Freiman homomorphism. This result is the
crucial additive combinatorial input we need to prove the spherical Gowers
inverse theorem in later parts of the series.

The author was partially supported by the NSF Grant DMS-2247331

###### Contents

  1. 1 Introduction
    1. 1.1 Additive combinatorics for affine subspaces and shifted ideals
    2. 1.2 Organizations and notations
  2. 2 The relation graph for additive tuples
    1. 2.1 A non-transitive relation for shifted $M$-ideals
    2. 2.2 The relation graph of a subset of $\Gamma^{s}(M)$
    3. 2.3 Outline of the proof of Theorem 1.5
  3. 3 Intersection property for $M$-ideals
  4. 4 Solutions to Freiman equations
    1. 4.1 Statement of the theorem
    2. 4.2 Solutions to some fundamental equations
    3. 4.3 Properties for super polynomials
    4. 4.4 Solutions to some special equations
    5. 4.5 Proof of Theorem 4.3
  5. 5 Structures for sets with small density dependence numbers
    1. 5.1 Two notions of equivalence classes
    2. 5.2 The $M$-energy graph
    3. 5.3 The Balog-Gowers-Szemerédi theorem
    4. 5.4 Ruzsa’s triangle inequality
    5. 5.5 Plünnecke-Rusza theorem
  6. 6 Decomposition results for relation graphs
  7. 7 Properties for Freiman $M$-homomorphisms of order 16
  8. 8 Structure-obstacle decomposition
  9. 9 Proof of the main theorem
  10. 10 Open questions
  11. A Basic properties for quadratic forms
    1. A.1 The rank of quadratic forms
    2. A.2 Some basic counting properties
    3. A.3 Irreducible properties for quadratic forms

##  1\. Introduction

###  1.1. Additive combinatorics for affine subspaces and shifted ideals

This paper is the second part of the series _Spherical higher order Fourier
analysis over finite fields_ [7, 8, 9]. The purpose of this paper is to
provide the additive combinatorial results we need for the proof of the
spherical Gowers inverse theorem in [8]. Let $G$ be a discrete abelian group.
A central topic in additive combinatorics is to study the structure of subsets
$E$ of $G$ with large additive energy (meaning that the set $\\{(a,b,c,d)\in
E^{4}\colon a+b=c+d\\}$ has cardinality $O(|E|^{3})$) or with small doubling
constant (meaning that $|E+E|=O(|E|)$). Such sets are known to have structures
related to arithmetic progressions. We refer the readers to [10] for more
details. Based on the existing knowledge in additive combinatorics, it was
shown in Lemma F.1 of [4] that if a function
$f\colon\\{0,\dots,N-1\\}\to\mathbb{T}$ has large additive energy, then $f$
must have an almost linear structure in the sense that

$f(h)=C+\sum_{k=1}^{K}\\{\alpha_{k}h\\}\beta_{k}\mod\mathbb{Z}$

for a large set of $h\in\\{0,\dots,N-1\\}$ for some $K\in\mathbb{N}$ and
$C,\alpha_{k},\beta_{k}\in\mathbb{R}$. This linearization result plays an
important role in the proof of the Gowers inverse theorem in [4].

In order to prove the spherical Gowers inverse theorem in [8], we also need a
linearization result in the spherical setting. In our context, the structure
for functions with large additive energy is characterized by the following
definition (recall that $\tau\colon\mathbb{F}_{p}\to\\{0,\dots,p-1\\}$ and
$\iota\colon\\{0,\dots,p-1\\}\to\mathbb{F}_{p}$ are the natural embeddings):

######  Definition 1.1 (Almost linear function and Freiman homomorphism).

Let $d,K\in\mathbb{N}_{+}$, $p$ be a prime, $H$ be a subset of
$\mathbb{F}_{p}^{d}$, and $\xi\colon H\to\mathbb{Z}/p$ be a map. We say that
$\xi$ is a _$p$ -almost linear function_ of _complexity_ at most $K$ if there
exist $\alpha_{i}\in(\mathbb{Z}/p)^{d}$ and $\beta_{i}\in\mathbb{Z}/p$ for all
$1\leq i\leq K$ such that for all $h\in H$,

$\xi(h):=\sum_{i=1}^{K}\\{\alpha_{i}\cdot\tau(h)\\}\beta_{i}.$

We say that a $p$-almost linear function $\xi$ is a _$p$ -almost linear
Freiman homomorphism_ if for all $h_{1},h_{2},h_{3},h_{4}\in H$ with
$h_{1}+h_{2}=h_{3}+h_{4}$, we have that

$\xi(h_{1})+\xi(h_{2})\equiv\xi(h_{3})+\xi(h_{4})\mod\mathbb{Z}.$

We say that a map $\xi\colon H\to\mathbb{F}_{p}$ is an _almost linear
function/Freiman homomorphism_ of complexity at most $K$ if there exists a
$p$-almost linear function/Freiman homomorphism $\xi^{\prime}\colon
H\to\mathbb{Z}/p$ of complexity at most $K$ such that
$\xi(h)=\iota(p\xi^{\prime}(h))$ for all $h\in H$.

In order to prove the 3-step spherical Gowers inverse theorem, the following
linearization result is needed in [8].222The linearization result is not
necessary for the proof of 2 or less step spherical Gowers inverse theorems.

######  Proposition 1.2 (Linearization result for affine supsaces).

Let $d\in\mathbb{N}_{+}$ with $d\gg 1$, $\delta>0$ and $p\gg_{\delta,d}1$ be a
prime. Let $H\subseteq\mathbb{F}_{p}^{d}$ with $|H|>\delta p^{d}$, and
$\xi_{i}$ be a map from $H$ to $\mathbb{F}_{p}^{d}$ for $1\leq i\leq 4$.
Suppose that there exists $U\subseteq\\{(h_{1},h_{2},h_{3},h_{4})\in
H^{4}\colon h_{1}+h_{2}=h_{3}+h_{4}\\}$ with $|U|>\delta|H|^{3}$ such that for
all $(h_{1},h_{2},h_{3},h_{4})\in U$,

(1.1)
$\xi_{1}(h_{1})+\xi_{2}(h_{2})-\xi_{3}(h_{3})-\xi_{4}(h_{4})\in\text{span}_{\mathbb{F}_{p}}\\{h_{1},h_{2},h_{3}\\}.$

Then there exist $H^{\prime}\subseteq H$ with
$|H^{\prime}|\gg_{\delta,d}p^{d}$, some $g\in\mathbb{F}_{p}$, and a map
$T\colon H^{\prime}\to\mathbb{F}_{p}^{d}$ whose projection to each of the $d$
coordinates is an almost linear Freiman homomorphism of complexity
$O_{\delta,d}(1)$ such that

$\xi_{1}(h)-T(h)-g\in\text{span}_{\mathbb{F}_{p}}\\{h\\}\text{ for all $h\in
H^{\prime}$.}$

An alternative way to interpret Proposition 1.2 is as follows. For affine
subspaces $V+c$ and $V^{\prime}+c^{\prime}$ of $\mathbb{F}_{p}^{d}$, we
informally write $V+c\sim V^{\prime}+c^{\prime}$ if $c-c^{\prime}\in
V+V^{\prime}$ (see Section 2.1 for the precise definitions). Roughly speaking,
Proposition 1.2 claims that if the maps

$\tilde{\xi}_{i}\colon h\mapsto\xi_{i}(h)+\text{span}_{\mathbb{F}_{p}}\\{h\\}$

from $\mathbb{F}_{p}^{d}$ to at most one dimensional affine subspaces of
$\mathbb{F}_{p}^{d}$ has large additive energy in the sense that

$\tilde{\xi}_{1}(h_{1})+\tilde{\xi}_{2}(h_{2})\sim\tilde{\xi}_{3}(h_{3})+\tilde{\xi}_{4}(h_{4})$

for all $(h_{1},h_{2},h_{3},h_{4})\in U$, then $\tilde{\xi}_{i}(h)$ equals to
an almost linear Freiman homomorphism plus a constant modulo
$\text{span}_{\mathbb{F}_{p}}\\{h\\}$.

In order to study the higher-step spherical Gowers inverse theorem, we need to
replaces the functions $\xi_{i}$ in Proposition 1.2 by functions taking values
in the ring of polynomials. Let $\text{HP}_{d}(s)$ denote the set of
homogeneous polynomial in $\mathbb{F}_{p}[x_{1},\dots,x_{d}]$ of degree $s$.
We say that a map $h\mapsto f_{h}$ from $H$ to $\text{HP}_{d}(s)$ is an
_almost linear function/Freiman homomorphism_ of _complexity_ at most $K$ if
the map $h\mapsto f_{m,h}$ is an almost linear function/Freiman homomorphism
of complexity at most $K$ for all $m\in\mathbb{N}^{d},|m|=s$, where
$f_{m,h}\in\mathbb{F}_{p}$ is the coefficient of the $n^{m}$ term of
$f_{h}(n)$.

######  Convention 1.3.

In this paper, the zero polynomial is considered as a degree $s$ polynomial
for any $s\in\mathbb{Z}$. In particular, the zero polynomial belongs to
$\text{HP}_{d}(s)$ for any $s\in\mathbb{N}$. For convenience, if $s<0$, then
we use $\text{HP}_{d}(s)$ to denote the set consisting only the zero
polynomial.

In order to generalize (1.1) to $\text{HP}_{d}(s)$-valued functions, we also
need to extend the concept of subspaces of $\mathbb{F}_{p}^{d}$ accordingly:

######  Definition 1.4 ($M$-ideal).

Let $d\in\mathbb{N}_{+},p$ be a prime and
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a quadratic form associated
with the matrix $A$ (see Section 1.2 for definitions). We say that an ideal
$I$ of the polynomial ring $\mathbb{F}_{p}[x_{1},\dots,x_{d}]$ is an _$M$
-ideal_ if $I=\langle(nA)\cdot n,(h_{1}A)\cdot n,\dots,(h_{k}A)\cdot n\rangle$
(which are viewed as polynomials in the variable $n$) for some
$k\in\mathbb{N}$ and $h_{1},\dots,h_{k}\in\mathbb{F}_{p}^{d}$. The _rank_ of
an $M$-ideal $I$, denoted by $\text{rank}(I)$, is the smallest such integer
$k$ (here we allow $k$ to be 0). For convenience we denote

$J^{M}:=\langle(nA)\cdot n\rangle\text{ and
}J^{M}_{h_{1},\dots,h_{k}}:=\langle(nA)\cdot n,(h_{1}A)\cdot
n,\dots,(h_{k}A)\cdot n\rangle.$

For a subspace $V$ of $\mathbb{F}_{p}^{d}$, denote

$J^{M}_{V}:=\langle(nA)\cdot n,(hA)\cdot n\colon h\in V\rangle.$

Clearly, $J^{M}_{V}=J^{M}_{h_{1},\dots,h_{k}}$ if
$\text{span}_{\mathbb{F}_{p}}\\{h_{1},\dots,h_{k}\\}=V$. We also have that
$J^{M}_{V}+J^{M}_{V^{\prime}}=J^{M}_{V+V^{\prime}}$.

For convenience, in the rest of the paper, we denote

(1.2) $N(s):=(2s+16)(15s+453)\text{ for all }s\in\mathbb{Z}.$

The following is the additive combinatorial property we need in order to prove
the general spherical Gowers inverse theorem in [8], which is also the main
result of this paper.

######  Theorem 1.5 (Linearization result for shifted ideals).

Let $d,s\in\mathbb{N}_{+}$, with $d\geq N(s)$, $\delta>0$ and $p$ be a prime,
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a non-degenerate quadratic
form, $H\subseteq\mathbb{F}_{p}^{d}$ with $|H|>\delta p^{d}$, and $\xi_{i}$ be
a map from $H$ to $\text{HP}_{d}(s)$ for $1\leq i\leq 4$. Suppose that there
exists $U\subseteq\\{(h_{1},h_{2},h_{3},h_{4})\in H^{4}\colon
h_{1}+h_{2}=h_{3}+h_{4}\\}$ with $|U|>\delta|H|^{3}$ such that for all
$(h_{1},h_{2},h_{3},h_{4})\in U$,

$\xi_{1}(h_{1})+\xi_{2}(h_{2})-\xi_{3}(h_{3})-\xi_{4}(h_{4})\in
J^{M}_{h_{1},h_{2},h_{3}}.$

If $p\gg_{\delta,d}1$, then there exist $H^{\prime}\subseteq H$ with
$|H^{\prime}|\gg_{\delta,d}p^{d}$, some $g\in\text{HP}_{d}(s)$, and an almost
linear Freiman homomorphism $T\colon H^{\prime}\to\text{HP}_{d}(s)$ of
complexity $O_{\delta,d}(1)$ such that

$\xi_{1}(h)-T(h)-g\in J^{M}_{h}\text{ for all $h\in H^{\prime}$.}$

We will make essential use of Theorem 1.5 in the Furstenburg-Weiss type
argument in [8], which is an intermediate step towards the proof of the
spherical Gowers inverse theorem. We refer the readers to Steps 2 and 3 of
Section 1.2 of [8] for details.

######  Remark 1.6.

Note that if $s=1$ and $M(n)=n\cdot n$, then there is a natural group
homomorphism $\sigma$ between $(\mathbb{F}_{p}^{d},+)$ and
$(\text{HP}_{d}(1),+)$ given by $\sigma(h)(n):=n\cdot h$, which maps
$\text{span}_{\mathbb{F}_{p}}\\{h\\}$ to $J^{M}_{h}\cap\text{HP}_{d}(1)$ since
all polynomials in $J^{M}_{h}\cap\text{HP}_{d}(1)$ are multiples of $h\cdot
n$. Moreover, for all $v\in\mathbb{F}_{p}^{d}$ and subspace $V$ of
$\mathbb{F}_{p}^{d}$, we have $v\in V$ if and only if $\sigma(v)\in
J^{M}_{V}$. So (1.1) is equivalent to

$\xi^{\prime}_{1}(h_{1})+\xi^{\prime}_{2}(h_{2})-\xi^{\prime}_{3}(h_{3})-\xi^{\prime}_{4}(h_{4})\in
J^{M}_{h_{1},h_{2},h_{3}},$

where $\xi_{i}^{\prime}:=\sigma\circ\xi_{i}$ is a map from $H$ to
$\text{HP}_{d}(1)$. Therefore, Proposition 1.2 is a special case of Theorem
1.5 when $s=1$.

While additive combinatorial properties for abelian groups have been studied
extensively in literature, very little is known for additive combinatorial
properties of affine subspaces or shifted ideals. In particular, all the
powerful tools in additive combinatoric are unavailable. In order to prove
Theorem 1.5, we need to establish foundational tools in analogous to the
abelian group setting from scratch. An interesting feature of this paper is
that we use many tools in graph theory to study additive combinatorial
properties for shifted ideals (especially in Section 5).

Since the proof of Theorem 1.5 is very technical, when reading this paper for
the first time, the readers are recommended to focus on the case $s=1$
throughout, which captures almost all the main idea of the proof of the
general case. In this case $\xi_{i}$ can be viewed as a map from $H$ to
$\mathbb{F}_{p}^{d}$, and $J^{M}_{h_{1},\dots,h_{k}}$ can be interpreted as
$\text{span}_{\mathbb{F}_{p}}\\{h_{1},\dots,h_{k}\\}$ (if $d\gg_{k}1$).

###  1.2. Organizations and notations

In Section 2, we define a non-transitive relation for shifted ideals, and
introduce some terminologies in graph theory which will be used later to prove
Theorem 1.5. We also provide an outline of the proof Theorem 1.5 with the help
of these new languages. In Section 3, we prove an intersection property for
$M$-ideals, which is an approach that will be used frequently later in this
paper to study the intersections of different $M$-ideals sharing a common
factor. Sections 4–9 are devoted to the proof of Theorem 1.5. We refer the
readers to Section 2.3 for a more details explanation for the roles these
sections play in the proof of Theorem 1.5 (after introducing all the relevant
definitions). In Section 10, we collect some open questions. In Appendix A, we
recall some definitions and propositions from [7] which are used in this
paper.

Below are the notations we use in this paper:

  * •

Let
$\mathbb{N},\mathbb{N}_{+},\mathbb{Z},\mathbb{Q},\mathbb{R},\mathbb{R}+,\mathbb{C}$
denote the set of non-negative integers, positive integers, integers, rational
numbers, real numbers, positive real numbers, and complex numbers,
respectively. Denote $\mathbb{T}:=\mathbb{R}/\mathbb{Z}$. Let $\mathbb{F}_{p}$
denote the finite field with $p$ elements.

  * •

Throughout this paper, $d$ is a fixed positive integer and $p$ is a prime
number.

  * •

Throughout this paper, unless otherwise stated, all vectors are assumed to be
horizontal vectors.

  * •

Throughout this paper, we use $\tau\colon\mathbb{F}_{p}\to\\{0,\dots,p-1\\}$
to denote the natural bijective embedding, and use
$\iota\colon\mathbb{Z}\to\mathbb{F}_{p}$ to denote the map given by
$\iota(n):=\tau^{-1}(n\mod p\mathbb{Z})$. We also use $\tau$ to denote the map
from $\mathbb{F}_{p}^{k}$ to $\mathbb{Z}^{k}$ given by
$\tau(x_{1},\dots,x_{k}):=(\tau(x_{1}),\dots,\tau(x_{k}))$, and $\iota$ to
denote the map from $\mathbb{Z}^{k}$ to $\mathbb{F}_{p}^{k}$ given by
$\iota(x_{1},\dots,x_{k}):=(\iota(x_{1}),\dots,$ $\iota(x_{k}))$.

  * •

Let $\mathcal{C}$ be a collection of parameters and $A,B,c\in\mathbb{R}$. We
write $A\gg_{\mathcal{C}}B$ if $|A|\geq K|B|$ and $A=O_{\mathcal{C}}(B)$ if
$|A|\leq K|B|$ for some $K>0$ depending only on the parameters in
$\mathcal{C}$. In the above definitions, we allow the set $\mathcal{C}$ to be
empty. In this case $K$ will be a universal constant.

  * •

For $x\in\mathbb{R}$, let $\lfloor x\rfloor$ denote the largest integer which
is not larger than $x$, and $\lceil x\rceil$ denote the smallest integer which
is not smaller than $x$. Denote $\\{x\\}:=x-\lfloor x\rfloor$.

  * •

Let $X$ be a finite set and $f\colon X\to\mathbb{C}$ be a function. Denote
$\mathbb{E}_{x\in X}f(x):=\frac{1}{|X|}\sum_{x\in X}f(x)$, the average of $f$
on $X$.

  * •

For $F=\mathbb{Z}^{k}$ or $\mathbb{F}_{p}^{k}$, and
$x=(x_{1},\dots,x_{k}),y=(y_{1},\dots,y_{k})\in F$, let $x\cdot
y\in\mathbb{Z}$ or $\mathbb{F}_{p}$ denote the dot product given by $x\cdot
y:=x_{1}y_{1}+\dots+x_{k}y_{k}.$

  * •

We write affine subspaces of $\mathbb{F}_{p}^{d}$ as $V+c$, where $V$ is a
subspace of $\mathbb{F}_{p}^{d}$ passing through $\mathbb{0}$, and
$c\in\mathbb{F}_{p}^{d}$.

We also need to recall the notations regarding quadratic forms defined in [7].

######  Definition 1.7.

We say that a function $M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ is a
_quadratic form_ if

$M(n)=(nA)\cdot n+n\cdot u+v$

for some $d\times d$ symmetric matrix $A$ in $\mathbb{F}_{p}$, some
$u\in\mathbb{F}_{p}^{d}$ and $v\in\mathbb{F}_{p}$. We say that $A$ is the
matrix _associated to_ $M$. We say that $M$ is _pure_ if $u=\mathbb{0}$. We
say that $M$ is _homogeneous_ if $u=\mathbb{0}$ and $v=0$. We say that $M$ is
_non-degenerate_ if $M$ is of rank $d$, or equivalently, $\det(A)\neq 0$.

We use $\text{rank}(M):=\text{rank}(A)$ to denote the _rank_ of $M$. Let $V+c$
be an affine subspace of $\mathbb{F}_{p}^{d}$ of dimension $r$. There exists a
(not necessarily unique) bijective linear transformation
$\phi\colon\mathbb{F}_{p}^{r}\to V$. We define the _rank_
$\text{rank}(M|_{V+c})$ of $M$ restricted to $V+c$ as the rank of the
quadratic form $M(\phi(\cdot)+c)$. It was proved in [7] that
$\text{rank}(M|_{V+c})$ is independent of the choice of $\phi$.

We also need to use the following notions.

  * •

For a polynomial $P\in\text{poly}(\mathbb{F}_{p}^{k}\to\mathbb{F}_{p})$, let
$V(P)$ denote the set of $n\in\mathbb{F}_{p}^{k}$ such that $P(n)=0$.

  * •

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

$V(M)^{h_{1},\dots,h_{r}}:=\cap_{i=1}^{r}(V(M(\cdot+h_{i}))\cap V(M).$

##  2\. The relation graph for additive tuples

###  2.1. A non-transitive relation for shifted $M$-ideals

Before proving Theorem 1.5, we need to rephraze the problem using some new
terminology to be defined in this section. Throughout this paper, $p$ is a
prime, $d$ is the dimension of the vector field over $\mathbb{F}_{p}$, and $M$
is a non-degenerate quadratic form from $\mathbb{F}_{p}^{d}$ to
$\mathbb{F}_{p}$. For an $M$-ideal $I$ and a polynomial
$f\in\mathbb{F}_{p}[x_{1},\dots,x_{d}]$, we call $I+f$ a _shifted $M$-ideal_
of $\mathbb{F}_{p}[x_{1},\dots,x_{d}]$. The space of all shifted $M$-ideals of
$\mathbb{F}_{p}[x_{1},\dots,x_{d}]$ is denoted as $\mathcal{J}(M)$.

We may define an “additive” operation on $\mathcal{J}(M)$ as follows. For
$I+f,I^{\prime}+f^{\prime}\in\mathcal{J}(M)$, denote
$(I+f)\hat{+}(I^{\prime}+f^{\prime}):=I+I^{\prime}+f+f^{\prime}$ and
$(I+f)\hat{-}(I^{\prime}+f^{\prime}):=I-I^{\prime}+f-f^{\prime}$. Clearly,
both $(\mathcal{J}(M),\hat{+})$ and $(\mathcal{J}(M),\hat{-})$ are semi-
groups, but the operations $\hat{+}$ and $\hat{-}$ are not the inverse of each
other.444We write the operations as $\hat{+}$ and $\hat{-}$ instead of $+$ and
$-$ to emphasize that they are not invertible.

We also need to define a relation between elements in $\mathcal{J}(M)$ as
follows. Denote $I+f\sim I^{\prime}+f^{\prime}$ if $f-f^{\prime}\in
I+I^{\prime}$. Clearly, if $x\sim y$ and $x^{\prime}\sim y^{\prime}$, then
$x\hat{+}x^{\prime}\sim y\hat{+}y^{\prime}$ and $x\hat{-}x^{\prime}\sim
y\hat{-}y^{\prime}$. It is easy to see that $u\sim u$, and $u\sim v\Rightarrow
v\sim u$. However, the next example shows that $\sim$ is not transitive and so
is not an equivalence relation.

######  Example 2.1.

Let $M(n)=n\cdot n$. For all $x\in\mathbb{F}_{p}^{d}$, let
$L_{x}\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ denote the function given by
$L_{x}(n)=x\cdot n$. Let $e_{1},\dots,e_{d}$ be the standard unit vectors of
$\mathbb{F}_{p}^{d}$. Then $J^{M}_{e_{1}}+L_{e_{2}}\sim J^{M}_{e_{2}}$ and
$J^{M}_{e_{2}}\sim J^{M}_{e_{3}}$. However, by Lemma A.6 and Proposition A.8,
it is not hard to see that $J^{M}_{e_{1}}+L_{e_{2}}\not\sim J^{M}_{e_{3}}$ if
$d\gg 1$ and $p\gg_{d}1$. So $\sim$ is not transitive.

The above mentioned operations and relation can be extended naturally to the
set $\mathbb{F}_{p}^{d}\times\mathcal{J}(M)$. For
$(h,I+f),(h^{\prime},I^{\prime}+f^{\prime})\in\mathbb{F}_{p}^{d}\times\mathcal{J}(M)$,
denote
$(h,I+f)\hat{+}(h^{\prime},I^{\prime}+f^{\prime}):=(h+h^{\prime},I+I^{\prime}+f+f^{\prime})$
and
$(h,I+f)\hat{-}(h^{\prime},I^{\prime}+f^{\prime}):=(h+h^{\prime},I-I^{\prime}+f-f^{\prime})$.
We write $(h,I+f)\sim(h^{\prime},I^{\prime}+f^{\prime})$ if $h=h^{\prime}$ and
$I+f\sim I^{\prime}+f^{\prime}$.

######  Convention 2.2.

Throughout this paper, we use
$\pi\colon\mathbb{F}_{p}^{d}\times\mathcal{J}(M)\to\mathbb{F}_{p}^{d}$ to
denote the projection map.

In this paper, we are particularly interested in the non-transitive relation
$\sim$ on a special subset $\Gamma^{s}(M)$ of
$\mathbb{F}_{p}^{d}\times\mathcal{J}(M)$, which denotes the set of all
elements of the form $(h,J^{M}_{V}+f)$ for some $h\in\mathbb{F}_{p}^{d}$, some
$f\in\text{HP}_{d}(s)$, and some $M$-ideal $J^{M}_{V}$ for some subspace $V$
of $\mathbb{F}_{p}^{d}$ with $h\in V$. We also need to divide the set
$\Gamma^{s}(M)$ further according to the dimension of $V$. For
$k\in\mathbb{N}_{+},$ let $\Gamma^{s}_{k}(M)$ denote the set of all
$(h,J^{M}_{V}+f)\in\Gamma^{s}(M),h\neq\mathbb{0}$ with $\dim(V)\leq k$ union
the set of all $(\mathbb{0},J^{M}_{V}+f)\in\Gamma^{s}(M)$ with $\dim(V)\leq
k-1$. Equivalently, $\Gamma^{s}_{k}(M)$ is the set of all
$(h,J^{M}_{V}+f)\in\Gamma^{s}(M),h\in\mathbb{F}_{p}^{d}$ where $V$ can be
written as the span of $k$ vectors $h_{1},\dots,h_{k}\in\mathbb{F}_{p}^{d}$
with one of them being $h$. In particular, $\Gamma^{s}_{1}(M)$ consists of all
elements of the form
$(h,J^{M}_{h}+f),h\in\mathbb{F}_{p}^{d},f\in\text{HP}_{d}(s)$.

######  Example 2.3.

Let $\xi_{i}\colon H\to\text{HP}_{d}(s),1\leq i\leq 4$ be given as in Theorem
1.5. Let $\tilde{\xi}_{i}\colon H\to\Gamma^{s}_{1}(M)$ be the map given by
$\tilde{\xi}_{i}(h):=(h,\xi_{i}(h)+J^{M}_{h})$. Informally speaking, the
assumption in Theorem 1.5 is equivalent of saying that the “additive energy”
of $\tilde{\xi}_{i}(H)\hat{+}\tilde{\xi}_{i}(H)$ (i.e. the number of
quadraples $(h_{1},h_{2},h_{3},h_{4})\in H^{4}$ with
$\tilde{\xi}_{i}(h_{1})\hat{+}\tilde{\xi}_{i}(h_{2})\sim\tilde{\xi}_{i}(h_{3})\hat{+}\tilde{\xi}_{i}(h_{4})$)
is at least $\delta|H|^{3}$.

We summarize some basic properties for later uses. The following lemma is
straightforward:

######  Lemma 2.4.

Let $s\in\mathbb{N}$ and $k,k^{\prime}\in\mathbb{N}_{+}$. If
$a\in\Gamma^{s}_{k}(M)$ and $b\in\Gamma^{s}_{k^{\prime}}(M)$, then
$a\hat{+}b\in\Gamma^{s}_{k+k^{\prime}}(M)$.

###### Proof.

Assume that $a=(h,J^{M}_{V}+f)$ and
$b=(h^{\prime},J^{M}_{V^{\prime}}+f^{\prime})$ for some
$h,h^{\prime}\in\mathbb{F}_{p}^{d}$, $f,f^{\prime}\in\text{HP}_{d}(s)$ and
subspaces $V,V^{\prime}$ of $\mathbb{F}_{p}^{d}$ with $h\in V$ and
$h^{\prime}\in V^{\prime}$. Then $h+h^{\prime}\in V+V^{\prime}$.

If $h=\mathbb{0}$, then $\dim(V)\leq k-1$. Since $\dim(V^{\prime})\leq
k^{\prime}$, we have $\dim(V+V^{\prime})\leq(k+k^{\prime})-1$. Similarly,
$\dim(V+V^{\prime})\leq(k+k^{\prime})-1$ if $h^{\prime}=\mathbb{0}$. In both
cases, we have $a\hat{+}b\in\Gamma^{s}_{k+k^{\prime}}(M)$.

We now assume that $h,h^{\prime}\neq\mathbb{0}$. Then $\dim(V)\leq k$ and
$\dim(V^{\prime})\leq k^{\prime}$. Since $\dim(V+V^{\prime})\leq
k^{\prime}+k$, we have that $a\hat{+}b\in\Gamma^{s}_{k+k^{\prime}}(M)$ if
$h+h^{\prime}\neq\mathbb{0}$. If $h+h^{\prime}=\mathbb{0}$, then $V\cap
V^{\prime}\neq\\{\mathbb{0}\\}$ and so $\dim(V+V^{\prime})\leq
k^{\prime}+k-1$. So we still have that
$a\hat{+}b\in\Gamma^{s}_{k+k^{\prime}}(M)$. ∎

Although $\sim$ is not a transitive relation in general, for the following
special case it is:

######  Lemma 2.5.

Let $s\in\mathbb{N}$, $x_{1},x_{2}\in\Gamma^{s}(M)$ and
$y\in\Gamma^{s}_{1}(M)$. If $x_{1}\sim y$ and $x_{2}\sim y$, then $x_{1}\sim
x_{2}$. In particular, $\sim$ is an equivalence relation on
$\Gamma^{s}_{1}(M)$.

###### Proof.

Write $x_{i}=(v_{i},J^{M}_{V_{i}}+f_{i})$ for $i=1,2$ and let $u=\pi(y)$. If
$x_{1}\sim y$ and $x_{2}\sim y$, then $v_{1}=u=v_{2}$. Since $v_{i}\in V_{i}$,
we have that $u\in V_{1}\cap V_{2}$. So for $i=1,2$, $x_{i}\equiv y_{1}\mod
J^{M}_{V_{i}+\text{span}_{\mathbb{F}_{p}}\\{u\\}}=J^{M}_{V_{i}}$. So
$x_{1}\equiv y_{1}\equiv x_{2}\mod J^{M}_{V_{1}+V_{2}}$ and thus $x_{1}\sim
x_{2}$. ∎

###  2.2. The relation graph of a subset of $\Gamma^{s}(M)$

The level sets (i.e. sets of the form $\\{(a,a^{\prime})\in A\times A\colon
a+a^{\prime}=b\\}$ for some $b\in G$) play an important role in the study of
conventional additive combinatorics. In our setting, we do not have such a
convenience tool. This is because the operation $\hat{+}$ does not have the
cancellation property (i.e. $a\hat{+}b\sim a^{\prime}\hat{+}b\not\Rightarrow
a\sim a^{\prime}$), and the relation $\sim$ is not an equivalent relation. To
overcome this difficulty, we use a graph to characterize the relation $\sim$.

######  Definition 2.6 (Relation graph).

Let $X$ be a subset of $\Gamma^{s}(M)$. we say that a graph $G=(X,E)$ is the
_relation graph_ of $X$ if for all $u,v\in X,u\neq v$, $\\{u,v\\}\in E$ if and
only if $u\sim v$.

######  Remark 2.7.

The structure of relation graphs for the conventional additive combinatorics
on abelian groups is quite simple. In fact, if $\sim$ is an equivalence
relation on $X$, then the graph $G$ is a disjoint union of complete subgraphs,
each of which represent an equivalence class (or a level set). However, in our
setting, the behavior of the relation graph can be very complicated.

Since we need to frequently partition a relation graph into smaller
components, it is helpful to introduce the following notion.

######  Definition 2.8 (Graph partitions).

Let $G=(X,E)$ be a graph and $G_{i}=(X_{i},E_{i}),1\leq i\leq k$ be subgraphs
of $G$. We say that $G_{1},\dots,G_{k}$ is a _disjoint partition_ of $G$ if
$X_{1},\dots,X_{k}$ are pairwise disjoint, $X=\cup_{i=1}^{k}X_{i}$ and
$E=\cup_{i=1}^{k}E_{i}$.

Similarly, Let $G=(X,Y,E)$ be a bipartite graph and
$G_{i}=(X_{i},Y_{i},E_{i}),1\leq i\leq k$ be subgraphs of $G$. We say that
$G_{1},\dots,G_{k}$ is a _disjoint partition_ of $G$ if
$X_{1},\dots,X_{k},Y_{1},\dots,Y_{k}$ are pairwise disjoint,
$X=\cup_{i=1}^{k}X_{i}$, $Y=\cup_{i=1}^{k}Y_{i}$ and $E=\cup_{i=1}^{k}E_{i}$.

######  Convention 2.9.

Let $G=(X,E)$ be a graph and $X_{1},\dots,X_{k}$ be pairwise disjoint and
$X=\cup_{i=1}^{k}X_{i}$. When we say that $G_{i}=(X_{i},E_{i}),1\leq i\leq k$
is a disjoint partition of $G$, we implicitly indicate that $E_{i}$ is the set
of all edges in $E$ with both vertices coming from $X_{i}$.

Similarly, Let $G=(X,Y,E)$ be a bipartite graph and
$X_{1},\dots,X_{k},Y_{1},\dots,Y_{k}$ be pairwise disjoint,
$X=\cup_{i=1}^{k}X_{i}$ and $Y=\cup_{i=1}^{k}Y_{i}$. When we say that
$G_{i}=(X_{i},Y_{i},E_{i}),1\leq i\leq k$ is a disjoint partition of $G$, we
implicitly indicate that $E_{i}$ is the set of all edges in $E$ with one
vertex from $X_{i}$ and the other from $Y_{i}$.

######  Remark 2.10.

Let $X$ be a subset of $\Gamma^{s}(M)$. Note that for $u,v\in X$, we have that
$u\sim v$ only if $\pi(u)=\pi(v)$. Therefore, the relation graph $G=(X,E)$ has
a disjoint partition induced by the partition
$\cup_{h\in\mathbb{F}_{p}^{d}}\pi^{-1}(h)\cap X$ of $X$. So it is helpful to
think of $G$ as the union of $p^{d}$ disjoint smaller graphs.

Next we introduce two quantities for graphs which play important roles in this
paper. Recall that in graph theory, the _(vertex) independence number_ of a
graph is the maximum number of vertices which are pairwise disjoint. The first
quantity we need is a variation of the concept of independence number:

######  Definition 2.11 (Auxiliary graph and density dependence number).

Let $G=(X,E)$ be a graph and $G^{\prime}=(X,Y,E^{\prime})$ be a bipartite
graph, we say that $G^{\prime}$ is an _auxiliary graph_ of $G$ if for all
$x,x^{\prime}\in X$ and $y\in Y$, if $(x,y),(x^{\prime},y)\in E^{\prime}$,
then $\\{x,x^{\prime}\\}\in E$. For $\epsilon>0$, we say that $G^{\prime}$ is
_$\epsilon$ -dense_ if for every $x\in X$, there exist at least $\epsilon|Y|$
many $y\in Y$ such that $(x,y)\in E^{\prime}$.

Let $s\in\mathbb{N}$, $h\in\mathbb{F}_{p}^{d}$ and $G=(X,E)$ be the relation
graph of a subset $X$ of $\Gamma^{s}(M)$ such that $\pi(X)=\\{h\\}$. The
_density dependence number_ of $G$ (or $X$), denoted by ${\\#}_{\text{dd}}(G)$
(or ${\\#}_{\text{dd}}(X)$), is the smallest integer $C>0$ such that $G$
admits a $C^{-1}$-dense auxiliary graph.

For the relation graph $G=(X,E)$ of a general subset $X$ of $\Gamma^{s}(M)$.
We define ${\\#}_{\text{dd}}(G)$ (or ${\\#}_{\text{dd}}(X)$) as the maximum of
${\\#}_{\text{dd}}(\pi^{-1}(h)\cap X),h\in\mathbb{F}_{p}^{d}$.

By the Pigeonhole Principle, it is not hard to see that the independence
number of a graph $G$ is at most ${\\#}_{\text{dd}}(G)$. It is natural to ask
about the converse direction:

######  Question 2.12.

For any graph, is the independent number equal to ${\\#}_{\text{dd}}(G)$? If
not, then is the independent number bounded below by a constant depending on
${\\#}_{\text{dd}}(G)$?

The second quantity we need is one that describes the optimal way in which a
graph can be covered by cliques. Recall that in graph theory, a _clique_ of a
graph $G=(X,E)$ is a subset $S$ of $X$ such that the subgraph of $G$ induced
by $S$ is a complete graph. In this paper, we measure the largeness of graph
by looking at the minimal number of clique we need to cover all the vertices.

######  Definition 2.13 (Clique cover number).

Let $s\in\mathbb{N}$, $h\in\mathbb{F}_{p}^{d}$ and $G=(X,E)$ be the relation
graph of a subset $X$ of $\Gamma^{s}(M)$ such that $\pi(X)=\\{h\\}$. The
_clique cover number_ of $G$ (or $X$), denoted by ${\\#}_{\text{cc}}(G)$ (or
${\\#}_{\text{cc}}(X)$) is the smallest integer $C$ such that we may partition
$X$ into $\sqcup_{i=0}^{C}X_{i}$ such that each $X_{i}$ is a clique of $G$.

For the relation graph $G=(X,E)$ of a general subset $X$ of $\Gamma^{s}(M)$.
We define ${\\#}_{\text{cc}}(G)$ (or ${\\#}_{\text{cc}}(X)$) as the maximum of
${\\#}_{\text{cc}}(\pi^{-1}(h)\cap X),h\in\mathbb{F}_{p}^{d}$.

We summarize some properties on the clique cover number and density dependence
number of a graph for later uses. The following lemma is straightforward.

######  Lemma 2.14.

Let $s\in\mathbb{N}$ and $G=(X,E)$ be the relation graph of a non-empty subset
$X$ of $\Gamma^{s}(M)$. Then

  1. (i)

${\\#}_{\text{dd}}(G)$ is finite and
${\\#}_{\text{cc}}(G)\geq{\\#}_{\text{dd}}(G)\geq 1$;

  2. (ii)

for any subgraph $G^{\prime}$ of $G$, we have that
${\\#}_{\text{cc}}(G^{\prime})\leq{\\#}_{\text{cc}}(G)$ and
${\\#}_{\text{dd}}(G^{\prime})\leq{\\#}_{\text{dd}}(G)$;

  3. (iii)

if $\pi(X)=\\{h\\}$ for some $h\in\mathbb{F}_{p}^{d}$, then any subset
$X^{\prime}$ of $X$ contains a clique of size at least
$\lceil\frac{|X^{\prime}|}{{\\#}_{\text{dd}}(G)}\rceil$;

  4. (iv)

${\\#}_{\text{dd}}(G)=1\Leftrightarrow{\\#}_{\text{cc}}(G)=1\Leftrightarrow
u\sim v$ for all $h\in\mathbb{F}_{p}^{d}$ and $u,v\in\pi^{-1}(h)\cap X$.

###### Proof.

We first prove Part (i). Assume without loss of generality that
$\pi(X)=\\{h\\}$ for some $h\in\mathbb{F}_{p}^{d}$. Clearly,
${\\#}_{\text{dd}}(G)\geq 1$. Note that we may partition $X$ into
$\sqcup_{i=1}^{{\\#}_{\text{cc}}(G)}X_{i}$ such that each $X_{i}$ is a clique
of $G$. Let $G^{\prime}=(X,\\{1,\dots,{\\#}_{\text{cc}}(G)\\},E^{\prime})$ be
the bipartite graph given by $(x,i)\in E^{\prime}\Leftrightarrow x\in X_{i}$.
Since each $X_{i}$ is a clique of $G$, we have that $G^{\prime}$ is an
auxiliary graph of $G$. On the other hand, the density of this auxiliary graph
is $\frac{1}{{\\#}_{\text{cc}}(G)}$. So we have that ${\\#}_{\text{dd}}(G)$ is
finite and ${\\#}_{\text{cc}}(G)\geq{\\#}_{\text{dd}}(G)$.

Part (ii) is straightforward. For Part (iii), let
$G^{\prime}=(X,Y,E^{\prime})$ be an auxiliary graph of $G$ of density at least
${\\#}_{\text{dd}}(G)^{-1}$. Then there are at least
$\frac{|X^{\prime}|\cdot|Y|}{{\\#}_{\text{dd}}(G)}$ edges in $E^{\prime}$ with
one of the vertices coming from $X^{\prime}$. By the Pigeonhole Principle,
there exists $y\in Y$ which is connected by edges in $E^{\prime}$ to at least
$\lceil\frac{|X^{\prime}|}{{\\#}_{\text{dd}}(G)}\rceil$ vertices in
$X^{\prime}$. These vertices induces a clique in $G$ by the definition of
auxiliary graphs.

Part (iv) follows from the definitions and Part (iii). ∎

The next lemma allows us to expand an auxiliary graph without changing its
density.

######  Lemma 2.15.

Let $s\in\mathbb{N}$ and $X$ be a subset of $\Gamma^{s}(M)$ with
$\pi(X)=\\{h\\}$ for some $h\in\mathbb{F}_{p}^{d}$, $\epsilon>0$, and
$G^{\prime}=(X,Y,E^{\prime})$ be an $\epsilon$-dense auxiliary graph of $X$.
Then for all $N\in\mathbb{N}_{+}$ divisible by $|Y|$, $X$ admits an
$\epsilon$-dense auxiliary graph
$G^{\prime\prime}=(X,Y^{\prime},E^{\prime\prime})$ with $|Y^{\prime}|=N$.

###### Proof.

Denote $m:=N/|Y|$ and let $Y^{\prime}=\sqcup_{i=1}^{m}Y_{i}$ be $m$ identical
copies of $Y$ and let $\iota_{i}\colon Y_{i}\to Y$ be the bijection for $1\leq
i\leq m$. For $x\in X$ and $y\in Y^{\prime}$, set $(x,y)\in E^{\prime\prime}$
if and only if $y$ belongs to some $Y_{i}$ and $(x,\iota_{i}(y))\in
E^{\prime}$. It is not hard to see that $|Y^{\prime}|=N$ and
$G^{\prime\prime}=(X,Y^{\prime},E^{\prime\prime})$ is an $\epsilon$-dense
auxiliary graph of $X$. ∎

Let $X$ be a subset of $\Gamma^{s}(M)$. If we add an extra point $x$ to $X$
such that $x\not\sim y$ for all $y\in X$, then it is clear that the clique
cover number of $X$ is increased by 1. In this case, it turns out that the
density dependence number of $X$ is also increased by 1.

######  Lemma 2.16.

Let $s\in\mathbb{N}$ and $X$ be a subset of $\Gamma^{s}(M)$ with
$\pi(X)=\\{h\\}$ for some $h\in\mathbb{F}_{p}^{d}$. Let $y\in\Gamma^{s}(M)$
with $\pi(y)=h$ be such that $x\not\sim y$ for all $x\in X$. Then
${\\#}_{\text{dd}}(X\cup\\{y\\})={\\#}_{\text{dd}}(X)+1$.

###### Proof.

For convenience denote $C:={\\#}_{\text{dd}}(X)$ and
$D:={\\#}_{\text{dd}}(X\cup\\{y\\})$. Then $X\cup\\{y\\}$ admits a
$D^{-1}$-dense auxiliary graph $G^{\prime}=(X\cup\\{y\\},Z,E^{\prime})$. Let
$Z^{\prime}:=\\{z\in Z\colon(y,z)\in E^{\prime}\\}$ and
$Z^{\prime\prime}:=Z\backslash Z^{\prime}$. Then $|Z^{\prime}|\geq D^{-1}|Z|$.
Since $y\not\sim x$ for all $x\in X$, we have that $(x,z)\notin E^{\prime}$
for all $x\in X$ and $z\in Z^{\prime}$. Consider the bipartite graph
$G^{\prime\prime}=(X,Z^{\prime\prime},E^{\prime\prime})$ induced by
$G^{\prime}$. Since $(x,z)\notin E^{\prime}$ for all $x\in X$ and $z\in
Z^{\prime}$, it is not hard to see that $G^{\prime\prime}$ is an auxiliary
graph of $X$, and that the density of this auxiliary graph is at least

$\frac{D^{-1}|Z|}{|Z|-|Z^{\prime}|}\geq\frac{D^{-1}|Z|}{|Z|-D^{-1}|Z|}=(D-1)^{-1}.$

This implies that $C\leq D-1$.

Conversely, since ${\\#}_{\text{dd}}(X)=C$, $X$ admits a $C^{-1}$-dense
auxiliary graph $G^{\prime}=(X,Z,E^{\prime})$. By Lemma 2.15, we may assume
without loss of generality that $|Z|$ is divisible by $C$. Let $Z^{\prime}$ be
any set of cardinality $|Z|/C$ which is disjoint from $Z$, and let
$G^{\prime\prime}=(X\cup\\{y\\},Z\sqcup Z^{\prime},E^{\prime\prime})$ be the
bipartite graph such that for all $x\in X\cup\\{y\\}$ and $z\in Z\sqcup
Z^{\prime}$, $(x,z)\in E^{\prime\prime}$ if and only if either (i) $x\in X$,
$z\in Z$ and $(x,z)\in E^{\prime}$; or (ii) $x=y$ and $z\in Z^{\prime}$.
Clearly, $G^{\prime\prime}$ is an auxiliary graph of $X\cup\\{y\\}$. On the
other hand, the density of $G^{\prime\prime}$ is

$\frac{\min\\{C^{-1}|Z|,|Z^{\prime}|\\}}{|Z|+|Z^{\prime}|}=\frac{C^{-1}|Z|}{|Z|+C^{-1}|Z|}=(C+1)^{-1}.$

This implies that $D\leq C+1$.

Combining both directions, we have that $D=C+1$. ∎

###  2.3. Outline of the proof of Theorem 1.5

We are now ready to provide an overview for the proof of Theorem 1.5:

Step 0. Our first goal is to solve the _Freiman equation_ (see (4.3)) on a
generalized arithmetic progression (see Theorem 4.3). This can be viewed as a
special case of Theorem 1.5 when $U$ equals to
$\\{(h_{1},h_{2},h_{3},h_{4})\in H^{4}\colon h_{1}+h_{2}=h_{3}+h_{4}\\}$, $H$
is a generalized arithmetic progression, and
$\xi_{1}=\xi_{2}=\xi_{3}=\xi_{4}$. This result will be used later in Step 4 to
be described below. While the the Freiman equation for abelian groups (see
(4.2)) can be solved easily, the Freiman equation is the setting of shifted
ideals is much harder. This step is done in Section 4.

Step 1. We show that if the conditions of Theorem 1.5 are satisfied, then
there exists a large subset $H^{\prime}$ of $H$ such that
$\pi^{-1}(\mathbb{0})\cap(8\tilde{\xi}(H^{\prime})\hat{-}8\tilde{\xi}(H^{\prime}))$
has a small density dependence number, where
$\tilde{\xi}(h):=(h,J^{M}_{h}+\xi_{1}(h))\in\Gamma^{s}_{1}(M)$. To achieve
this, we need to extend many classical results in combinatorics to shifted
ideals, including the Balog-Gowers-Szemerédi Theorem, the Ruzsa triangle
inequality, the Green-Ruzsa inequality, and the Plünnecke-Rusza theorem. This
is done in Section 5.

Step 2. We show that if
$\pi^{-1}(\mathbb{0})\cap(8\tilde{\xi}(H^{\prime})\hat{-}8\tilde{\xi}(H^{\prime}))$
has a small density dependence number, then we may decompose the set
$\pi^{-1}(\mathbb{0})\cap(8\tilde{\xi}(H^{\prime})\hat{-}8\tilde{\xi}(H^{\prime}))$
into two parts. The first is the structure part with a small clique covering
number, and the second is the obstacle part which has nontrivial intersections
with an object with low dimension. This is done in Section 6. Unfortunately we
were unable to remove the obstacle part, and thus we need carry this error
term throughout the proof, which makes the proof of the remaining steps more
technical. This step is done in Section 6.

Step 3. We show that if
$\pi^{-1}(\mathbb{0})\cap(8\tilde{\xi}(H^{\prime})\hat{-}8\tilde{\xi}(H^{\prime}))$
has a decomposition described in Step 2, then for many “good” subspaces $V$ of
$\mathbb{F}_{p}^{d}$, there exists a large subset $H^{\prime\prime}$ of
$H^{\prime}$ such that $\xi$ is a Freiman $M$-homomorphism of order 16 on
$H^{\prime\prime}\cap V$. On the other hand, we show that
$8H^{\prime\prime}-8H^{\prime\prime}$ has rich generalized arithmetic
progression structures. The proof is inspired by the constructions of
appropriate Bohr sets introduced in [3]. This step is done in Section 7.

Step 4. If we could show that $\xi$ is a Freiman $M$-homomorphism of order 16
on a large subset $H^{\prime\prime}$ of $H^{\prime}$ (instead of on
$H^{\prime\prime}\cap V$), then one can directly apply the solutions to
Freiman equations obtained in Step 0 to conclude that $\xi$ is locally linear,
and thus Theorem 1.5 can be proved easily. Unfortunately the subspaces $V$ in
Step 3 can not be taken to be $\mathbb{F}_{p}^{d}$. To overcome this
difficulty, we first solve for $\xi$ on “good” subspaces $V$, and then combine
this information on different $V$ to conclude that $\xi$ is a Freiman
$M$-homomorphism of order 16 on a large subset $H^{\prime\prime}$ of
$H^{\prime}$, modulo an ideal of the form $J^{M}_{T}$ for some subspace $T$ of
$\mathbb{F}_{p}^{d}$. This is done is Section 8.

Step 5. By intersecting the Freiman $M$-homomorphism structure of $\xi$
obtained in Step 4 for many different $J^{M}_{T}$, we conclude that $\xi$ is a
genial Freiman $M$-homomorphism of order 16. We may then invoke Theorem 4.3 to
show that $\xi$ is locally linear and thus complete the proof of Theorem 1.5.
This is done is Section 9.

##  3\. Intersection property for $M$-ideals

We begin with the notation of linear independence for subspaces of
$\mathbb{F}_{p}^{d}$:

######  Definition 3.1 (Linearly independent subspaces).

Let $V_{1},\dots,V_{k}$ be subspaces of $\mathbb{F}_{p}^{d}$. We say that
$V_{1},\dots,V_{k}$ are _linearly independent_ if for all $v_{i}\in
V_{i},1\leq i\leq k$, $\sum_{i=1}^{k}v_{i}=\mathbb{0}$ implies that
$v_{1}=\dots=v_{k}=\mathbb{0}$. In this case we also say that
$(V_{1},\dots,V_{k})$ is a _linearly independent tuple_ (or a _linearly
independent pair_ if $k=2$).

Let $V_{1},\dots,V_{k}$ be subspaces of $\mathbb{F}_{p}^{d}$ and
$v_{1},\dots,v_{k^{\prime}}\in\mathbb{F}_{p}^{d}$. We say that
$v_{1},\dots,v_{k^{\prime}}$, $V_{1},\dots,V_{k}$ are _linearly independent_
if for all $c_{i}\in\mathbb{F}_{p},1\leq i\leq k$ and
$v^{\prime}_{i^{\prime}}\in V_{i^{\prime}},1\leq i^{\prime}\leq k^{\prime}$,
$\sum_{i=1}^{k}c_{i}v_{i}+\sum_{i^{\prime}=1}^{k^{\prime}}v^{\prime}_{i^{\prime}}=\mathbb{0}$
implies that $c_{1}=\dots=c_{k}=0$ and
$v^{\prime}_{1}=\dots=v^{\prime}_{k^{\prime}}=\mathbb{0}$. In this case we
also say that $(v_{1},\dots,v_{k^{\prime}},V_{1},\dots,V_{k})$ is a _linearly
independent tuple_ (or a _linearly independent pair_ if
$k+k^{\prime}=2$).555We caution the readers that according to our definition,
the zero vector $\mathbb{0}$ is linearly dependent with every subspace of
$\mathbb{F}_{p}^{d}$, while the trivial subspace $\\{\mathbb{0}\\}$ is
linearly independent with every subspace of $\mathbb{F}_{p}^{d}$. This
unconventional definition turns out to be convenient for this paper.

Let $V,V_{1},\dots,V_{k}$ be subspaces of $\mathbb{F}_{p}^{d}$ with
$V\subseteq\cap_{i=1}^{k}V_{i}$. We say that $V_{1},\dots,V_{k}$ are _linearly
independent modulo $V$_ if for all $v_{i}\in V_{i},1\leq i\leq k$,
$\sum_{i=1}^{k}v_{k}=\mathbb{0}$ implies that $v_{1},\dots,v_{k}\in V$.

In order to illustrate the main idea of this section, it is helpful to
consider the following motivative question:

######  Question 3.2.

Let $V$ be a subspace of $\mathbb{F}_{p}^{d}$ and $V_{1},\dots,V_{N}$ be
nontrivial linearly independent subspaces of $\mathbb{F}_{p}^{d}$. When do we
have that $\cap_{i=1}^{N}(V+V_{i})=V$?

For example, let $N=2$ and $V,V_{1}$ and $V_{2}$ be the $\mathbb{F}_{p}$-span
of $(1,0,\dots,0)$, $(0,1,0,\dots,0)$ and $(1,1,0,\dots,0)$ respectively. It
is clear that
$(V+V_{1})\cap(V+V_{2})=\text{span}_{\mathbb{F}_{p}}\\{e_{1},e_{2}\\}\neq
V=\text{span}_{\mathbb{F}_{p}}\\{e_{1}\\}$. However, if we add an addition
subspace $V_{3}=\text{span}_{\mathbb{F}_{p}}\\{h\\}$ with $V_{1},V_{2},V_{3}$
being linearly independent, then this will force $h$ not to belong to
$\text{span}_{\mathbb{F}_{p}}\\{e_{1},e_{2}\\}$, which implies that
$\cap_{i=1}^{3}(V+V_{i})=V$. Motivated by this example, it is natural to
expect that $\cap_{i=1}^{N}(V+V_{i})=V$ whenever $N$ is sufficiently large.
Indeed, we have

######  Proposition 3.3 (Intersection property for subspaces of
$\mathbb{F}_{p}^{d}$).

Let $V$ be a subspace of $\mathbb{F}_{p}^{d}$ and $V_{1},\dots,V_{N}$ be
linearly independent subspaces of $\mathbb{F}_{p}^{d}$. If $N\geq\dim(V)+2$,
then $\cap_{i=1}^{N}(V+V_{i})=V$.

Informally, one can think of the unions of $V+V_{i}$ as a “sunflower” with $V$
being its “core” and $V_{i}$ being its “petals”. The philosophy behind
Proposition 3.3 is that if we take the intersection of sufficiently many
linearly independent “petals”, then eventually the intersection will decrease
to $V$. Therefore, we call Proposition 3.3 the _intersection property_ for
subspaces.

To prove Proposition 3.3, it suffices to show the following lemma (and then
set $s=2$):

######  Lemma 3.4.

Let $m,s\in\mathbb{N}$, $d,N\in\mathbb{N}_{+}$, $p$ be a prime, and
$V,V_{1},\dots,V_{N}$ be subspaces of $\mathbb{F}_{p}^{d}$ such that
$\dim(V)=m$. Suppose that $V_{1},\dots,V_{N}$ are linearly independent and
$N\geq m+s$, then there exist
$\\{i_{1},\dots,i_{s}\\}\subseteq\\{1,\dots,N\\}$ such that
$V,V_{i_{1}},\dots,V_{i_{s}}$ are linearly independent.

###### Proof.

There is nothing to prove when $s=0$. Suppose that the conclusion holds for
some $s\in\mathbb{N}$ when $N\geq m+s$. We prove that the conclusion holds for
$s+1$ when $N\geq m+s+1$.

By induction hypothesis, if $N\geq m+s$, then we may assume without loss of
generality that $V,V_{1},\dots,V_{s}$ are linearly independent. Suppose that
for all $1\leq i\leq N$, $V,V_{1},\dots,V_{s},V_{i}$ are not linearly
independent. Then there exists a nontrivial $v_{i}\in
V_{i}\cap(V+V_{1}+\dots+V_{s})$ for all $s+1\leq i\leq N$. Since $\dim(V)=m$,
if $N-s\geq m+1$, then there exist $c_{s+1},\dots,c_{N}\in\mathbb{F}_{p}$ not
all equal to 0 such that $\sum_{i=s+1}^{N}c_{i}v_{i}\in V_{1}+\dots+V_{s}$.
Since $V_{1},\dots,V_{N}$ are linearly independent, we have that $c_{i}=0$ for
all $s+1\leq i\leq N$, a contradiction. Therefore, if $N\geq m+s+1$, then
there must be some $1\leq j\leq N$ such that $V,V_{1},\dots,V_{s},V_{j}$ are
linearly independent. ∎

######  Remark 3.5.

We remark that the lower bound $N\geq m+s$ in Lemma 3.4 is optimal. To see
this, let $V=\text{span}_{\mathbb{F}_{p}}\\{e_{1},\dots,e_{m}\\}$ and
$V_{i}=\text{span}_{\mathbb{F}_{p}}\\{e_{i}\\}$ for $1\leq i\leq m+s-1$, where
$e_{j}$ is the $j$-th standard unit vector. Then $V_{1},\dots,V_{m+s-1}$ are
linearly independent, but for any $s$ of $V_{1},\dots,V_{m+s-1}$, since at
least one of them comes from $V_{1},\dots,V_{m}$, it has nontrivial
intersection with $V$.

Following the philosophy of Proposition 3.3, it is natural to ask for the
intersection property for shifted ideals. We have the following, which is the
main result of this section.

######  Proposition 3.6 (Intersection property for weakly independent
$M$-ideals).

Let $m,s\in\mathbb{N}$, $d,N,r\in\mathbb{N}_{+}$, $p\gg_{d}1$ be a prime,
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a non-degenerate quadratic
form, and $V,V_{1},\dots,V_{N}$ be subspaces of $\mathbb{F}_{p}^{d}$ with
$V_{1},\dots,V_{N}$ being linearly independent such that $\dim(V)=m$ and
$\dim(V_{i})\leq r,1\leq i\leq N$. Suppose that $N\geq s+m+1$ and that either
$\text{rank}(M|_{V^{\perp_{M}}})\geq 2N(r-1)+7$ or $d\geq 2m+2N(r-1)+7$.666See
Appendix A.1 for definitions. Then for all
$f\in\mathbb{F}_{p}[x_{1},\dots,x_{d}]$ of degree at most $s$, we have that

$f\in\cap_{i=1}^{N}J^{M}_{V+V_{i}}\Leftrightarrow f\in J^{M}_{V}.$

It is an interesting question to ask what is the best lower bound of $d$ for
Proposition 3.6. although we do not pursuit this in the paper.

By Lemma 3.4, to prove Proposition 3.6, it suffices to show follows the
following weaker version of it:

######  Proposition 3.7 (Intersection property for strongly independent
$M$-ideals).

Let $m,s\in\mathbb{N}$, $d,N,r\in\mathbb{N}_{+}$, $p\gg_{d}1$ be a prime,
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a non-degenerate quadratic
form, and $V,V_{1},\dots,V_{N}$ be linearly independent subspaces of
$\mathbb{F}_{p}^{d}$ such that $\dim(V)=m$ and $\dim(V_{i})\leq r,1\leq i\leq
N$. Suppose that $N\geq s+1$ and that either
$\text{rank}(M|_{V^{\perp_{M}}})\geq 2N(r-1)+7$ or $d\geq 2m+2N(r-1)+7$. Then
for all $f\in\mathbb{F}_{p}[x_{1},\dots,x_{d}]$ of degree at most $s$, we have
that

$f\in\cap_{i=1}^{N}J^{M}_{V+V_{i}}\Leftrightarrow f\in J^{M}_{V}.$

We need some preparation before proving Proposition 3.7. The next lemma says
that if $h,h_{1},\dots,h_{k}\in\mathbb{F}_{p}^{d}$ are linearly independent,
then the degree 1 polynomial $n\mapsto(nA)\cdot h$ is “irreducible” in
$J^{M}_{h_{1},\dots,h_{k}}$.

######  Lemma 3.8.

Let $d\in\mathbb{N}_{+}$, $k,s\in\mathbb{N}$, $p\gg_{d,k,s}1$ be a prime,
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a non-degenerate quadratic
form associated with the matrix $A$, and
$h,h_{1},\dots,h_{k}\in\mathbb{F}_{p}^{d}$ be linearly independent vectors.
Let $f\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a polynomial of degree $s$
such that $((nA)\cdot h)f(n)\in J^{M}_{h_{1},\dots,h_{k}}$. If
$\text{rank}(M|_{\text{span}_{\mathbb{F}_{p}}\\{h,h_{1},\dots,h_{k}\\}^{\perp_{M}}})\geq
3$ or $d\geq 2k+5$, then we have that $f\in J^{M}_{h_{1},\dots,h_{k}}$.

###### Proof.

By Lemma A.1, $d\geq 2k+5$ implies that
$\text{rank}(M|_{\text{span}_{\mathbb{F}_{p}}\\{h,h_{1},\dots,h_{k}\\}^{\perp_{M}}})\geq
3$. So we only need to consider the case
$\text{rank}(M|_{\text{span}_{\mathbb{F}_{p}}\\{h,h_{1},\dots,h_{k}\\}^{\perp_{M}}})\geq
3$.

Let $V$ be the set of $n\in\mathbb{F}_{p}^{d}$ such that $(nA)\cdot
n=(nA)\cdot h_{1}=\dots=(nA)\cdot h_{k}=0$, and $V^{\prime}$ be the set of
$n\in V$ with $(nA)\cdot h=0$. Since
$\text{rank}(M|_{\text{span}_{\mathbb{F}_{p}}\\{h,h_{1},\dots,h_{k}\\}^{\perp_{M}}})\geq
3$, by Lemma A.5, $|V|\gg_{d,k,s}p^{d-k-1}$ and
$|V^{\prime}|=O_{d,k,s}(p^{d-k-2})$. So if $p\gg_{d,k,s}1$, then the number of
$n\in V$ with $f(n)=0$ is $\gg_{d,k,s}p^{d-k-1}$. By Proposition A.8, we have
that $f\in J^{M}_{h_{1},\dots,h_{k}}$. ∎

The key to the proof of Proposition 3.7 is the following Hilbert
Nullstellensatz type result for the intersection of $M$-deals.

######  Lemma 3.9.

Let $m,s\in\mathbb{N}$, $d,N,r\in\mathbb{N}_{+}$, $p\gg_{d,s}1$ be a prime,
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a non-degenerate quadratic
form, and $V,V_{1},\dots,V_{N}$ be linearly independent subspaces of
$\mathbb{F}_{p}^{d}$ such that $\dim(V)=m$ and $\dim(V_{i})=r_{i}\leq r$. Let
$h_{1},\dots,h_{m}$ be a basis of $V$, and for each $1\leq i\leq N$, let
$h_{i,1},\dots,h_{i,r_{i}}$ be a basis of $V_{i}$. For
$h\in\mathbb{F}_{p}^{d}$, let $L_{h}\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$
be the polynomial given by $L_{h}(n)=M(n+h)-M(n)$. Suppose that either
$\text{rank}(M|_{V^{\perp_{M}}})\geq 2N(r-1)+7$ or $d\geq 2m+2N(r-1)+7$. Then
for all $f\in\cap_{i=1}^{N}J_{V+V_{i}}^{M}$ of degree at most $s$, we may
write

(3.1) $f=Mf_{N}+\sum_{\ell=1}^{m}L_{h_{\ell}}f_{N,\ell}+\sum_{1\leq j_{t}\leq
r_{t},1\leq t\leq
N}\Bigl{(}\prod_{i=1}^{N}L_{h_{i,j_{i}}}\Bigr{)}g_{j_{1},\dots,j_{N}}$

for some $f_{N}$ of degree at most $s-2$, $f_{N,\ell}$ of degree at most
$s-1$, and $g_{j_{1},\dots,j_{N}}$ of degrees at most $s-N$. In particular, we
have that $f\in J^{M}_{V}+(\cap_{i=1}^{N}J^{M}_{V_{i}})$.

######  Remark 3.10.

By Convention 1.3, Lemma 3.9 is still valid if $s<N$. In this case, the
decomposition (3.1) is understood as

(3.2) $f=Mf_{N}+\sum_{\ell=1}^{m}L_{h_{\ell}}f_{N,\ell}.$

Moreover, if one of $r_{1},\dots,r_{N}$ is zero, then the summation
$\sum_{1\leq j_{t}\leq r_{t},1\leq t\leq N}$ in (3.1) is considered as non-
existing, and (3.1) is also understood as (3.2). If $m=0$, then the summation
$\sum_{\ell=1}^{m}L_{h_{\ell}}f_{N,\ell}$ in (3.1) is considered as non-
existing.

###### Proof of Lemma 3.9.

Throughout the proof we assume that $p\gg_{d,s}1$. By Lemma A.1 (iii), it
suffices to consider the case when $\text{rank}(M|_{V^{\perp_{M}}})\geq
2N(r-1)+7$. By Lemma A.2, $\text{rank}(M|_{(V+V_{1})^{\perp_{M}}})\geq 3$. If
one of $r_{1},\dots,r_{N}$ is zero, then $f$ belongs to $J^{M}_{V}$ and so the
conclusion follows from Proposition A.8.

So we assume that all of $r_{1},\dots,r_{N}$ are positive. Since
$\text{rank}(M|_{(V+V_{1})^{\perp_{M}}})\geq 3$, by Proposition A.8, the
conclusion holds for $N=1$. Suppose we have shown that the conclusion holds
for some $N\in\mathbb{N}_{+}$. We now show that the conclusion holds for
$N+1$. Pick any $f\in\cap_{i=1}^{N+1}J^{M}_{V+V_{i}}$ of degree at most $s$.
Since the conclusion holds for $N$, we may write

(3.3) $f=Mf_{N}+\sum_{\ell=1}^{m}L_{h_{\ell}}f_{N,\ell}+\sum_{1\leq j_{t}\leq
r_{t},1\leq t\leq
N}\Bigl{(}\prod_{i=1}^{N}L_{h_{i,j_{i}}}\Bigr{)}g_{j_{1},\dots,j_{N}}$

for some $f_{N}$ of degree at most $s-2$, $f_{N,\ell}$ of degree at most
$s-1$, and $g_{j_{1},\dots,j_{N}}$ of degrees at most $s-N$. By Lemma A.2,
$\text{rank}(M|_{(V+V_{N+1})^{\perp_{M}}})\geq 3$. Since $f\in
J^{M}_{V+V_{N+1}}$, by Proposition A.8, we may also write

$f=Mf^{\prime}+\sum_{\ell=1}^{m}L_{h_{\ell}}f^{\prime}_{\ell}+\sum_{j=1}^{r_{N+1}}L_{h_{N+1,j}}g^{\prime}_{j}$

for some $f^{\prime}$ of degree at most $s-2$, $f^{\prime}_{\ell}$ of degree
at most $s-1$, and $g^{\prime}_{j}$ of degrees at most $s-1$. In particular,
we may write $f$ as

(3.4)
$f=Mf^{\prime}+\sum_{\ell=1}^{m}L_{h_{\ell}}f^{\prime}_{\ell}+\sum_{1\leq
j_{t}\leq r_{t},1\leq t\leq
N+1}\Bigl{(}\prod_{i=1}^{N+1}L_{h_{i,j_{i}}}\Bigr{)}g^{\prime}_{j_{1},\dots,j_{N+1}}+\sum_{j=1}^{r_{N+1}}L_{h_{N+1,j}}g^{\prime}_{j}$

for some polynomials $g^{\prime}_{j_{1},\dots,j_{N+1}}$ of degree at most
$s-N-1$ (in fact we can simply take $g^{\prime}_{j_{1},\dots,j_{N+1}}\equiv
0$). Then combining (3.3) and (3.4), we have that

(3.5)
$Mf^{\prime\prime}+\sum_{\ell=1}^{m}L_{h_{\ell}}f^{\prime\prime}_{\ell}+\sum_{1\leq
j_{t}\leq r_{t},1\leq t\leq
N}\Bigl{(}\prod_{i=1}^{N}L_{h_{i,j_{i}}}\Bigr{)}g^{\prime\prime}_{j_{1},\dots,j_{N}}+\sum_{j=1}^{r_{N+1}}L_{h_{N+1,j}}g^{\prime}_{j}=0$

for some
$f^{\prime\prime},f^{\prime\prime}_{\ell},g^{\prime\prime}_{j_{1},\dots,j_{N+1}}$
of degrees at most $s-2$, $s-1$ and $s-N$ respectively. This implies that
$L_{h_{N+1,r_{N+1}}}g^{\prime}_{r_{N+1}}\in\cap_{i=1}^{N}J^{M}_{V+V^{\prime}+V_{i}}$,
where
$V^{\prime}=\text{span}_{\mathbb{F}_{p}}\\{h_{N+1,1},\dots,h_{N+1,r_{N+1}-1}\\}.$

Since $V,V_{1},\dots,V_{N+1}$ are linearly independent,

(3.6) the vectors $h_{\ell},h_{i,j},1\leq\ell\leq m,1\leq i\leq N+1,1\leq
j\leq r_{i}$ are linearly independent.

Since $\text{rank}(M|_{V^{\perp_{M}}})\geq 2(N+1)(r-1)+7\geq 4r+3$ and
$\dim(V^{\prime}+V_{i}+\text{span}_{\mathbb{F}_{p}}\\{h_{N+1,r_{N+1}}\\})\leq
2r$ for all $1\leq i\leq N$, by Lemma A.2, we have that

$\text{rank}(M|_{(V+V^{\prime}+V_{i}+\text{span}_{\mathbb{F}_{p}}\\{h_{N+1,r_{N+1}}\\})^{\perp_{M}}})\geq
3$

for all $1\leq i\leq N$. So by Lemma 3.8,
$g^{\prime}_{r}\in\cap_{i=1}^{N}J^{M}_{V+V^{\prime}+V_{i}}$.

Since $\text{rank}(M|_{V^{\perp_{M}}})\geq 2(N+1)(r-1)+7$, we have that
$\text{rank}(M|_{(V+V^{\prime})^{\perp_{M}}})\geq 2N(r-1)+7$ by Lemma A.2. By
(3.6), $V+V^{\prime},V_{1},\dots,V_{N}$ are linearly independent. Applying the
induction hypothesis for $V+V^{\prime},V_{1},\dots,V_{N}$, we may write
$g^{\prime}_{r}$ as

(3.7)
$g^{\prime}_{r}=M\tilde{f}_{N}+\sum_{\ell=1}^{m}L_{h_{\ell}}\tilde{f}_{N,\ell}+\sum_{1\leq
j_{t}\leq r_{t},1\leq t\leq
N}\Bigl{(}\prod_{i=1}^{N}L_{h_{i,j_{i}}}\Bigr{)}\tilde{g}_{j_{1},\dots,j_{N}}+\sum_{1\leq
j\leq r_{N+1}-1}L_{h_{N+1,j}}\tilde{g}_{j}$

for some $\tilde{f}_{N}$ of degree at most $s-3$, $\tilde{f}_{N,\ell}$ of
degree at most $s-2$, $\tilde{g}_{j_{1},\dots,j_{N}}$ of degrees at most
$s-N-1$, and $\tilde{g}_{j}$ of degree at most $s-2$. Substituting (3.7) in
(3.4), we may write $f$ as

(3.8)
$f=Mf^{\prime\prime\prime}+\sum_{\ell=1}^{m}L_{h_{\ell}}f^{\prime\prime\prime}_{\ell}+\sum_{1\leq
j_{t}\leq r_{t},1\leq t\leq
N+1}\Bigl{(}\prod_{i=1}^{N+1}L_{h_{i,j_{i}}}\Bigr{)}g^{\prime\prime\prime}_{j_{1},\dots,j_{N+1}}+\sum_{j=1}^{r_{N+1}-1}L_{h_{N+1,j}}g^{\prime\prime}_{j}$

for some
$f^{\prime\prime\prime},f^{\prime\prime\prime}_{\ell},g^{\prime\prime\prime}_{j_{1},\dots,j_{N+1}}$
and $g^{\prime\prime}_{j}$ of degrees at most $s-2,s-1,s-N-1$ and $s-1$
respectively. Comparing (3.3) and (3.8), we have that

(3.9)
$Mf^{\prime\prime\prime\prime}+\sum_{\ell=1}^{m}L_{h_{\ell}}f^{\prime\prime\prime\prime}_{\ell}+\sum_{1\leq
j_{t}\leq r_{t},1\leq t\leq
N}\Bigl{(}\prod_{i=1}^{N}L_{h_{i,j_{i}}}\Bigr{)}g^{\prime\prime\prime\prime}_{j_{1},\dots,j_{N}}+\sum_{j=1}^{r_{N+1}-1}L_{h_{N+1,j}}g^{\prime\prime}_{j}=0$

for some $f^{\prime\prime\prime\prime}$ of degree at most $s-2$,
$f^{\prime\prime\prime\prime}_{\ell}$ of degree at most $s-1$, and
$g^{\prime\prime\prime\prime}_{j_{1},\dots,j_{N}}(n)$ of degree at most $s-N$.

The differences between (3.4), (3.5) and (3.8), (3.9) is that we have one less
term in the expressions (3.8), (3.9). So we continue this argument to remove
the last summation in (3.8) and to conclude that the conclusion holds for
$N+1$. This finishes the proof. ∎

We are now ready to prove Proposition 3.7.

###### Proof of Proposition 3.7.

The $\Leftarrow$ direction is straightforward, and so we only need to prove
the $\Rightarrow$ direction.

Let $h_{1},\dots,h_{m}$ be a basis of $V$. Since
$f\in\cap_{i=1}^{s+1}J^{M}_{V+V_{i}}$, by Lemma 3.9, if $p\gg_{d}1$, then we
may write

$f=Mf+\sum_{\ell=1}^{m}L_{h_{\ell}}f_{\ell}$

for some $f$ of degree at most $s-1$ and $f_{\ell}$ of degree at most $s$
(recall that in this case $N=s+1>s$ and the $g_{j_{1},\dots,j_{s}}$ terms
disappears). This implies that $f\in J^{M}_{V}$ and we are done. ∎

We conclude this section with a density version of Proposition 3.6:

######  Proposition 3.11 (Intersection property for large collection of
$M$-ideals).

Let $m,k,s\in\mathbb{N}$, $d,d^{\prime}\in\mathbb{N}_{+}$, $\delta>0$,
$p\gg_{\delta,d,k}1$ be a prime, $M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$
be a non-degenerate quadratic form, $V,U_{1},\dots,U_{k}$ be subspaces of
$\mathbb{F}_{p}^{d}$ such that all of $U_{1},\dots,U_{k}$ have the same
dimension and that $(U_{i},V)$ is a linearly independent pair for all $1\leq
i\leq k$, and $P\subseteq\mathbb{F}_{p}^{d}$ be a subset with $|P|>\delta
p^{d^{\prime}}$. For convenience denote $U_{0}=\\{\mathbb{0}\\}$. Let
$f\in\mathbb{F}_{p}[x_{1},\dots,x_{d}]$ be of degree at most $s$. Suppose that
$f\in J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{h_{1},\dots,h_{m}\\}+V}$ for all
$h_{1},\dots,h_{m}\in P$ such that $(h_{1},\dots,h_{m},U_{i},V),0\leq i\leq k$
are linearly independent tuples.777We remark that the introduction to the
notation $U_{0}$ is redundant if $k\geq 1$, as the linear independence of
$(x,y,U_{1},V)$ implies that of $(x,y,V)$ and $(x,y,U_{0},V)$. We introduce
the notation $U_{0}$ in order to combine the results for the case $k=0$ and
the case $k\geq 1$. If
$d^{\prime}\geq\max\\{\dim(V)+m+s,\dim(U_{k})+\dim(V)+m,2\dim(V)+2m+5\\}$,
then we have that $f\in J^{M}_{V}.$

###### Proof.

Our strategy is to use the largeness of the set $P$ to iteratively find
subspaces of $\mathbb{F}_{p}^{d}$ satisfying the requirement of Proposition
3.6. Let $P_{1}$ denote the set of $h_{1}\in P$ such that
$(h_{1},U_{i},V),0\leq i\leq k$ are linearly independent tuples. For $2\leq
j\leq m$ and $h_{1},\dots,h_{j-1}\in P$ such that
$(h_{1},\dots,h_{j-1},U_{i},V),0\leq i\leq k$ are linearly independent tuples,
let $P_{j}(h_{1},\dots,h_{j-1})$ denote the set of $h_{j}\in P$ such that
$(h_{1},\dots,h_{j},U_{i},V),0\leq i\leq k$ are linearly independent tuples.
By assumption, we have that

(3.10) $f\in\cap_{h_{1}\in P_{1}}\cap_{h_{2}\in
P_{2}(h_{1})}\dots\cap_{h_{m}\in
P_{m}(h_{1},\dots,h_{m-1})}J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{h_{1},\dots,h_{m}\\}+V}.$

For $1\leq j\leq m$, we say that _Property- $j$_ holds if

$f\in\cap_{h_{1}\in P_{1}}\cap_{h_{2}\in P_{2}(h_{1})}\dots\cap_{h_{j}\in
P_{j}(h_{1},\dots,h_{j-1})}J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{h_{1},\dots,h_{j}\\}+V}.$

We say that _Property-0_ holds if $f\in J^{M}_{V}$. By (3.10), we have that
Property-$m$ holds. Suppose that we have shown that Property-$(j+1)$ holds for
some $0\leq j\leq m-1$. Then

$f\in\cap_{h_{1}\in P_{1}}\cap_{h_{2}\in P_{2}(h_{1})}\dots\cap_{h_{j+1}\in
P_{j+1}(h_{1},\dots,h_{j})}J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{h_{1},\dots,h_{j+1}\\}+V}.$

Fix any $h_{1},\dots,h_{j}\in P$ such that $(h_{1},\dots,h_{j},U_{i},V),0\leq
i\leq k$ are linearly independent tuples. Since
$d^{\prime}\geq\max\\{\dim(V)+m+s,\dim(U_{k})+\dim(V)+m\\}$, it is hot hard to
find linearly independent $x_{1},\dots,x_{\dim(V)+j+s+1}\in P$ such that
$(h_{1},\dots,h_{j},x_{j^{\prime}},U_{i},V),0\leq i\leq k,1\leq
j^{\prime}\leq\dim(V)+j+s+1$ are linearly independent tuples. Since
Property-$(j+1)$ holds, we have that

$f\in\cap_{i=1}^{\dim(V)+j+s+1}J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{h_{1},\dots,h_{j},x_{i}\\}+V}.$

Since $d^{\prime}\geq 2\dim(V)+2m+5$, applying Proposition 3.6 for $r=1$ and
$m=\dim(V)+j$, we have that $f\in
J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{h_{1},\dots,h_{j}\\}+V}$. Since
$h_{1},\dots,h_{j}$ are arbitrary, this implies that Property-$j$ holds.

Inductively, we conclude that Property-0 holds, meaning that $f\in J^{M}_{V}$.
∎

##  4\. Solutions to Freiman equations

###  4.1. Statement of the theorem

In additive combinatorics, subsets of a discrete abelian group with small
doubling constant has a strong connection with generalized arithmetic
progressions, which we recall as follows:

######  Definition 4.1 (Generalized arithmetic progression).

Let $G$ be an abelian group. We say that $P\subseteq G$ is a _generalized
arithmetic progression_ in $G$ if $P$ can be written as

(4.1)
$P=\\{a+\ell_{1}v_{1}+\dots+\ell_{D}v_{D}\colon\ell_{i}\in\mathbb{Z}\cap(-L_{i},L_{i})\text{
for all }1\leq i\leq D\\}$

for some $D\in\mathbb{N}_{+}$, $a,v_{1},\dots,v_{D}\in G$ and
$L_{1},\dots,L_{D}>0$. We abbreviate (4.1) as $P=a+(-L,L)\cdot v$, where
$L:=(L_{1},\dots,L_{D})$ and $v:=(v_{1},\dots,v_{D})$. We say that $a$ is the
_base point_ , $D$ the _rank_ , $v_{1},\dots,v_{D}$ the _generators_ , and
$L_{1},\dots,L_{D}$ the _lengths_ of $P$. If all sums in $P$ are district,
then we say that $P$ is _proper_. If $a=id_{G}$, then we say that $P$ is
_homogeneous_.

In this section, we focus on determine the solutions to Freiman equations. For
abelian groups, the _Freiman equation_ is of the form

(4.2) $F(h_{1})+F(h_{2})\equiv F(h_{3})+F(h_{4})\mod\mathbb{Z}\text{ for all
}h_{1},h_{2},h_{3},h_{4}\in P\text{ with }h_{1}+h_{2}=h_{3}+h_{4},$

where $P\subseteq G$ is a proper and homogeneous generalized arithmetic
progression in $G$ and $F\colon G\to\mathbb{R}$ is a function. Assume that $P$
is given by (4.1). Then it is not hard to see that the value of $F$ on $P$ is
determined by $F(\mathbb{0}),F(v_{i}),1\leq i\leq D$. So $F$ can be written as

(4.3) $F(\ell_{1}v_{1}+\dots+\ell_{D}v_{D})\equiv
c_{0}+\ell_{1}c_{1}+\dots+\ell_{D}c_{D}\mod\mathbb{Z}$

for some $c_{0},\dots,c_{D}\in\mathbb{R}$ for all
$\ell_{i}\in\mathbb{Z}\cap(-L_{i},L_{i}),1\leq i\leq D$.

In this paper, we need to understand the solutions to the Freiman equation for
shifted ideals. Let $M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a
quadratic form, $n\in\mathbb{N}_{+}$ and $H$ be a subset of
$\mathbb{F}_{p}^{d}$. We say that a map $\xi\colon H\to\text{HP}_{d}(s)$
(recall that $\text{HP}_{d}(s)$ is the set of degree-$s$ homogeneous
polynomials in $d$ variables) is a _Freiman $M$-homomorphism of order $2^{n}$_
on $H$ if for all $h_{1},\dots,h_{2^{n}}\in H$ with
$h_{1}+\dots+h_{2^{n-1}}=h_{2^{n-1}+1}+\dots+h_{2^{n}}$, we have that

$\xi(h_{1})+\dots+\xi(h_{2^{n-1}})\equiv\xi(h_{2^{n-1}+1})+\dots+\xi(h_{2^{n}})\mod
J^{M}_{h_{1},\dots,h_{2^{n}-1}}.$

In particular, $\xi$ is a Freiman $M$-homomorphism of order 4 (on $H$) if

(4.4) $\xi(h_{1})+\xi(h_{2})\equiv\xi(h_{3})+\xi(h_{4})\mod
J^{M}_{h_{1},h_{2},h_{3}}$

for all $h_{1},h_{2},h_{3},h_{4}\in H$ with $h_{1}+h_{2}=h_{3}+h_{4}$. 888We
remark that Freiman $M$-homomorphisms of order 4 is not the same as Freiman
homomorphisms introduced in Definition 1.1, since we are allowed to modulo
$J^{M}_{h_{1},\dots,h_{2^{n}-1}}$ for Freiman $M$-homomorphisms.

In order to describe the solution to Freiman $M$-homomorphisms, we need an
generalization for functions taking forms similar to (4.3):

######  Definition 4.2 (Locally linear function).

Let

$P=\\{\ell_{1}v_{1}+\dots+\ell_{D}v_{D}\colon\ell_{i}\in\mathbb{Z}\cap(-L_{i},L_{i}),1\leq
i\leq D\\}\subseteq\mathbb{F}_{p}^{d}$

be a proper and homogeneous generalized arithmetic progression. We say that a
map $\xi\colon P\to\text{HP}_{d}(s)$ is _locally linear_ if there exist
$f_{0},f_{1},\dots,f_{D}\in\text{HP}_{d}(s)$ such that

$\xi(\ell_{1}v_{1}+\dots+\ell_{D}v_{D})=f_{0}+\ell_{1}f_{1}+\dots+\ell_{D}f_{D}$

for all $\ell_{i}\in\mathbb{Z}\cap(-L_{i},L_{i}),1\leq i\leq D$.

Clearly, every locally linear map is a Freiman $M$-homomorphism of order 4.
The main result of this section shows that the converse also holds: any
Freiman $M$-homomorphism of order 4 is also locally linear when restricted to
an appropriate sub generalized arithmetic progression if the dimension $d$ is
large. For $0<c\leq 1$, let $P(c)$ denote the generalized arithmetic
progression

$P(c)=\\{\ell_{1}v_{1}+\dots+\ell_{D}v_{D}\colon\ell_{i}\in\mathbb{Z}\cap(-cL_{i},cL_{i}),1\leq
i\leq D\\}\subseteq\mathbb{F}_{p}^{d}.$

Since

$\frac{|\mathbb{Z}\cap(-cL,cL)|}{|\mathbb{Z}\cap(-L,L)|}\geq\frac{\max\\{2cL-1,1\\}}{2L+1}\geq\frac{2cL-1}{2L+1}\cdot\mathbb{1}_{L>1/c}+\frac{1}{2L+1}\cdot\mathbb{1}_{L\leq
1/c}\geq\frac{c}{c+2}$

for all $L>0$ and $0<c<1$. We have that

(4.5) $|P(c)|\geq(\frac{c}{c+2})^{D}|P|.$

We are now ready to state the main result of this section:

######  Theorem 4.3 (Solution to Freiman equations).

Let $d,D\in\mathbb{N}_{+}$, $s\in\mathbb{N}$ with
$d\geq\max\\{s+10,11\\}$,101010With a little more effort, one can release the
restriction to $d\geq s+10$ by studying the case $s=0$ more carefully. We
leave the details to interested readers. $\delta>0$, $p\gg_{\delta,d,D}1$ be a
prime, and $M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a non-degenerate
quadratic form. Let $P\subseteq\mathbb{F}_{p}^{d}$ be a proper and homogeneous
generalized arithmetic progression of dimension $D$ with $|P|>\delta p^{d}$.
If $\xi\colon P\to\text{HP}_{d}(s)$ is a Freiman $M$-homomorphism of order 4,
then there exist a constant $0<c\leq 1$ depending only on $s$ and a locally
linear map $T\colon P(c)\to\text{HP}_{d}(s)$ such that $\xi(h)\equiv T(h)\mod
J^{M}_{h}$ for all $h\in P(c)$.111111It is natural to ask that whether the
conclusion Theorem 4.3 holds for all $h\in P$ instead of for $h\in P(c)$. Such
as an improvement seems promising by applying another bootstrap argument on
Theorem 4.3, but in this paper we do not need such a general result.

######  Remark 4.4.

Note that Theorem 4.3 fails if the dimension $d$ is small. In particular,
Theorem 4.3 fails when $s=1$ and $\dim(P)=d=2$. Indeed, let
$\xi\colon\mathbb{F}_{p}^{2}\to\mathbb{F}_{p}^{2}$ be given by
$\xi(x,y)=xf(yx^{-1})$ for all $x,y\in\mathbb{F}_{p}^{2},x\neq 0$ and
$\xi(0,y)=0$, where $f\colon\mathbb{F}_{p}\to\mathbb{F}^{2}_{p}$ is arbitrary.
Then it is not hard to see that (4.4) holds for all
$h_{1},\dots,h_{4}\in\mathbb{F}_{p}^{2}$ (in fact, if $d=2$, then (4.4) holds
trivially when $h_{1},\dots,h_{4}$ spans $\mathbb{F}_{p}^{2}$, and holds by
the construction of $\xi$ when the span of $h_{1},\dots,h_{4}$ is of dimension
0 or 1). On the other hand, in general, $\xi$ does not coincides with a
locally linear map mod $J^{M}_{h}$. So it is an interesting question to ask
what the sharp lower bound of $d$ is for the conclusion of Theorem 4.3 to
hold.

###  4.2. Solutions to some fundamental equations

The rest of this section is devoted to proving Theorem 4.3. The proof of
Theorem 4.3 is rather intricate. Unlike in the abelian setting, for Theorem
4.3, the values of $\xi$ at $\mathbb{0},v_{i},1\leq i\leq D$ are far from
being enough to determine the entire function $\xi$. In order to prove Theorem
4.3, we begin with solving some (relatively) simple equations. Then we
gradually increase the complexity of the equations until we reach (4.4).

In the rest of this section, denote $L_{n}(x):=(nA)\cdot x$ for all
$x,n\in\mathbb{F}_{p}^{d}$, where $A$ is the matrix associated to $M$.

We start with the following trivial equation:

(4.6) $f(x)\equiv f(y)\mod\mathbb{Z}\text{ for all $x,y\in G$},$

where $f$ is a map from $G$ to $\mathbb{R}$ for some group $G$. It is obvious
that the solution to (4.6) is $f\equiv c\mod\mathbb{Z}$ for some
$c\in\mathbb{R}$. In the setting of shifted ideals, one can study a similar
equation:

(4.7) $F(x)\equiv F(y)\mod J^{M}_{x,y}\text{ for all
$x,y\in\mathbb{F}_{p}^{d}$},$

where $F$ is a map from $\mathbb{F}_{p}^{d}$ to $\text{HP}_{d}(s)$. Comparing
(4.6) with (4.7), it is natural to conjecture that the solution to (4.6) is
$F\equiv f\mod J^{M}_{x}$ for some $f\in\text{HP}_{d}(s)$. This is indeed the
case.

######  Proposition 4.5.

Let $d\in\mathbb{N}_{+}$, $s\in\mathbb{Z}$, and $p\gg_{d,s}1$ be a prime. Let
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a non-degenerate quadratic
form and $F\colon\mathbb{F}_{p}^{d}\to\text{HP}_{d}(s)$ be a map such that

$F(x)\equiv F(y)\mod J^{M}_{x,y}$

for all $x,y\in\mathbb{F}_{p}^{d}$. If $d\gg_{s}1$, then there exists
$G\in\text{HP}_{d}(s)$ such that

$F(x)\equiv G\mod J^{M}_{x}$

for all $x\in\mathbb{F}_{p}^{d}$.

Proposition 4.5 is a special case of the following result:

######  Proposition 4.6.

Let $d\in\mathbb{N}_{+}$, $k\in\mathbb{N},s\in\mathbb{Z}$, $\delta>0$,
$p\gg_{\delta,d,k}1$ be a prime, $H$ be a subset of $\mathbb{F}_{p}^{d}$ with
$|H|>\delta p^{d}$ and $M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a non-
degenerate quadratic form. Let $k\in\mathbb{N}$ and
$U_{1},\dots,U_{k},V\subseteq\mathbb{F}_{p}^{d}$ be (possibly trivial)
subspaces of $\mathbb{F}_{p}^{d}$ with $U_{1},\dots,U_{k}$ having the same
dimension such that $(U_{i},V)$ is a linearly independent pair for all $1\leq
i\leq k$. For convenience denote $U_{0}=\\{\mathbb{0}\\}$. Let
$F\colon\mathbb{F}_{p}^{d}\to\text{HP}_{d}(s)$ be a map such that

(4.8) $F(x)\equiv F(y)\mod J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{x,y\\}+V}$

for all $x,y\in H$ with $(x,y,U_{i},V)$ being a linearly independent tuple for
all $0\leq i\leq k$. If $d\geq s+\dim(U_{k})+2\dim(V)+8$, then there exists
$G\in\text{HP}_{d}(s)$ such that

(4.9) $F(x)\equiv G\mod J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{x\\}+V}$

for all $x\in H$ with $(x,U_{i},V)$ being a linearly independent tuple for all
$0\leq i\leq k$.

Note that Proposition 4.6 improves Proposition 4.5 in the following senses.
Firstly, we work on a large subset $H$ of $\mathbb{F}_{p}^{d}$ instead of
working on the entire $\mathbb{F}_{p}^{d}$. Secondly, we allow to quotient the
map $F$ by an ideal $J^{M}_{V}$. Finally, we allow (4.8) to fail on a set of
tuples of $(x,y)$ of cardinality $O(p^{2d-1})$ (at the cost that the
expression (4.9) will also fail on a set of cardinality $O(p^{d-1})$).
Proposition 4.6 is a key property that will be used frequently in the rest of
this section.

###### Proof of Proposition 4.6.

By Convention 1.3, there is nothing to prove when $s<0$. So we assume that
$s\in\mathbb{N}$. Throughout the proof we assume that $p\gg_{\delta,d,k}1$. If
$s=0$, then $F(x)$ is a constant polynomial for all $x\in\mathbb{F}_{p}^{d}$.
Since $J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{x,y\\}+V}$ is generated by
nontrivial homogeneous polynomials and $d\geq\dim(V)+4$, we have that $1\notin
J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{x,y\\}+V}$ and thus it follows from
(4.8) that $F(x)=F(y)$ for all $x,y\in H$ with $(x,y,U_{i},V),0\leq i\leq k$
being linearly independent tuples. On the other hand, if
$d\geq\dim(U_{k})+\dim(V)+2$, then for any $x,y\in H$ with
$(x,U_{i},V),(y,U_{i},V),0\leq i\leq k$ being linearly independent tuples,
there exists $z\in H$ such that $(x,z,U_{i},V),(y,z,U_{i},V),0\leq i\leq k$
are all linearly independent tuples (in fact, the number of $z$ such that this
condition fails is at most $O_{k}(p^{\dim(U_{1})+\dim(V)+1})$). So we have
that $F(x)=F(z)=F(y)$ and thus $F(x)$ is independent of $x$. This proves the
case $s=0$.

Suppose now the conclusion holds for $s-1$ for some $s\geq 1$. We prove that
the conclusion holds for $s$. For all $x,y\in H$ with $(x,y,U_{i},V),0\leq
i\leq k$ being linearly independent tuple, since $d\geq 2(\dim(V)+2)+3$, by
(4.8) and Proposition A.8, for all $x,y\in H$ with $(x,y,U_{i},V),0\leq i\leq
k$ being linearly independent tuples, there exist
$A_{x,y},B_{x,y}\in\text{HP}_{d}(s-1)$ such that

$F(x)-F(y)\equiv L_{x}A_{x,y}-L_{y}B_{x,y}\mod J^{M}_{V}.$

Using the identity $F(x)-F(z)=(F(x)-F(y))+(F(y)-F(z))$, we deduce that

$L_{x}(A_{x,y}-A_{x,z})+L_{y}(A_{y,z}-B_{x,y})+L_{z}(B_{x,z}-B_{y,z})\equiv
0\mod J^{M}_{V}$

for all $x,y,z\in H$ with $(x,y,z,U_{i},V),0\leq i\leq k$ being linearly
independent tuples. This implies that $L_{x}(A_{x,y}-A_{x,z})\in
J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{y,z\\}+V}$. By Lemma 3.8, if $d\geq
2\dim(V)+9$, then

(4.10) $A_{x,y}\equiv A_{x,z}\mod
J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{y,z\\}+V}$ if $(x,y,z,U_{i},V),0\leq
i\leq k$ are linearly independent tuples.

Similarly,

(4.11) $B_{x,z}\equiv B_{y,z}\mod
J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{x,y\\}+V}$ if $(x,y,z,U_{i},V),0\leq
i\leq k$ are linearly independent tuples.

and

(4.12) $A_{y,z}\equiv B_{x,y}\mod
J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{x,z\\}+V}$ if $(x,y,z,U_{i},V),0\leq
i\leq k$ are linearly independent tuples.

By (4.10) and the induction hypothesis, since $d\geq
s+\dim(U_{k})+2\dim(V)+8=(s-1)+(\dim(U_{k})+1)+2\dim(V)+8$, for all $x\in H$
with $(x,U_{i},V),0\leq i\leq k$ being linearly independent tuples, there
exists $G_{x}\in\text{HP}_{d}(s-1)$ such that $A_{x,y}\equiv G_{x}\mod
J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{y\\}+V}$ for all $y\in H$ with
$(y,x,U_{i},V),1\leq i\leq k$ being linearly independent tuples. Similarly, by
(4.11), there exists $G^{\prime}_{y}\in\text{HP}_{d}(s-1)$ such that
$B_{x,y}\equiv G^{\prime}_{y}\mod
J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{x\\}+V}$ for all $x,y\in H$ with
$(x,y,U_{i},V),0\leq i\leq k$ being linearly independent tuples.

Fix $y\in H$ with $(y,U_{i},V),0\leq i\leq k$ being linearly independent
tuples. By (4.12), for any $x,z\in H$ with $(x,y,z,U_{i},V),0\leq i\leq k$
being linearly independent tuples, we have that $G_{y}-G^{\prime}_{y}\equiv
A_{y,z}-B_{x,y}\equiv 0\mod J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{x,z\\}+V}$.
By Lemma 3.11, if
$d\geq\max\\{\dim(V)+s+2,\dim(U_{k})+\dim(V)+3,2\dim(V)+9\\}$, then
$G_{y}\equiv G^{\prime}_{y}\mod J^{M}_{V}.$

Now we have that

$F(x)-F(y)\equiv L_{x}A_{x,y}-L_{y}B_{x,y}\equiv
L_{x}G_{x}-L_{y}G^{\prime}_{y}\equiv L_{x}G_{x}-L_{y}G_{y}\mod J^{M}_{V}$

and so

$F^{\prime}(x)\equiv F^{\prime}(y)\mod J^{M}_{V}$

for all $x,y\in H$ with $(x,y,U_{i},V),0\leq i\leq k$ being linearly
independent tuples, where $F^{\prime}(x):=F(x)-L_{x}G_{x}$. So for all
$x,x^{\prime}\in H$ with $(x,U_{i},V),(x^{\prime},U_{i},V),0\leq i\leq k$
being linearly independent tuples, if $d\geq 2+\dim(U_{k})+\dim(V)$, then
there exists $y\in H$ such that $(x,y,U_{i},V),(x^{\prime},y,U_{i},V),0\leq
i\leq k$ are linearly independent tuples (to see this, note that $|H|>\delta
p^{d}$ and that the number of $y\in\mathbb{F}_{p}^{d}$ such that this
condition fails is at most $O_{k}(p^{1+\dim(U_{k})+\dim(V)})$). So

$F^{\prime}(x)\equiv F^{\prime}(y)\equiv F^{\prime}(x^{\prime})\mod
J^{M}_{V}.$

In other words, there exists $G\in\text{HP}_{d}(s)$ such that for all $x\in H$
with $(x,U_{i},V),0\leq i\leq k$ being linearly independent tuples,
$F(x)\equiv L_{x}G_{x}+G\mod J^{M}_{V}$ and thus $F(x)-G\in
J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{x\\}+V}$. ∎

As an immediate corollary of Proposition 4.6, we have

######  Corollary 4.7.

Let $d\in\mathbb{N}_{+}$, $k\in\mathbb{N},s\in\mathbb{Z}$, $\delta>0$,
$p\gg_{\delta,d,k}1$ be a prime, $H$ be a subset of $\mathbb{F}_{p}^{d}$ with
$|H|>\delta p^{d}$ and $M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a non-
degenerate quadratic form. Let $k\in\mathbb{N}$ and
$U_{1},\dots,U_{k},V\subseteq\mathbb{F}_{p}^{d}$ be (possibly trivial)
subspaces of $\mathbb{F}_{p}^{d}$ with $U_{1},\dots,U_{k}$ having the same
dimension such that $(U_{i},V)$ is a linearly independent pair for all $1\leq
i\leq k$. For convenience denote $U_{0}=\\{\mathbb{0}\\}$. Let
$F,F^{\prime}\colon\mathbb{F}_{p}^{d}\to\text{HP}_{d}(s)$ be maps such that

$F(x)\equiv F^{\prime}(y)\mod J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{x,y\\}+V}$

for all $x,y\in H$ with $(x,y,U_{i},V)$ being a linearly independent tuple for
all $0\leq i\leq k$. If $d\geq s+\dim(U_{k})+2\dim(V)+11$, then there exists
$G\in\text{HP}_{d}(s)$ such that

$F(x)\equiv F^{\prime}(x)\equiv G\mod
J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{x\\}+V}$

for all $x\in H$ with $(x,U_{i},V)$ being a linearly independent tuple for all
$0\leq i\leq k$.

###### Proof.

By Convention 1.3, there is nothing to prove when $s<0$. So we assume that
$s\in\mathbb{N}$. Throughout the proof we assume that $p\gg_{\delta,d,k}1$.
Fix any $x,y\in H$ with $(x,U_{i},V),(y,$ $U_{i},V)$ being linearly
independent tuples for all $0\leq i\leq k$. For any $z\in H$ with
$(x,y,z,U_{i},V)$ being linearly independent tuples for all $0\leq i\leq k$,
by assumption

(4.13) $F(x)\equiv F^{\prime}(z)\equiv F(y)\mod
J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{x,y,z\\}+V}.$

By Proposition 3.11, since
$d\geq\max\\{\dim(V)+s+3,\dim(U_{k})+\dim(V)+3,2\dim(V)+11\\}$, we have that

$F(x)\equiv F(y)\mod J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{x,y\\}+V}$

for all $x,y\in H$ with $(x,U_{i},V),(y,U_{i},V)$ being linearly independent
tuples for all $0\leq i\leq k$. By Proposition 4.6, there exists
$G\in\text{HP}_{d}(s)$ such that $F(x)\equiv G\mod
J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{x\\}+V}$ for all $x\in H$ with
$(x,U_{i},V),$ being linearly independent tuples for all $0\leq i\leq k$.
Similarly, there exists $G^{\prime}\in\text{HP}_{d}(s)$ such that
$F^{\prime}(y)\equiv G^{\prime}\mod
J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{y\\}+V}$ for all $y\in H$ with
$(y,U_{i},V),$ being linearly independent tuples for all $0\leq i\leq k$. Fix
any $x,y\in H$ with $(x,y,U_{i},V)$ being linearly independent tuples for all
$0\leq i\leq k$, we have that

$G\equiv F(x)\equiv F^{\prime}(y)\equiv G^{\prime}\mod
J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{x,y\\}+V}.$

By Proposition 3.11, since
$d\geq\max\\{\dim(V)+s+2,\dim(U_{k})+\dim(V)+2,2\dim(V)+9\\}$, we have that
$G\equiv G^{\prime}\mod J^{M}_{V}$ and we are done. ∎

######  Remark 4.8.

It is worth summarizing the idea of the proof of Corollary 4.7 briefly.
Ideally, we wish to arrive at the conclusion that

$F(x)\equiv F(y)\mod J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{x,y\\}+V}.$

directly from the hypothesis in the statement. However, due to a loss of
information, we were only able to deduce the weaker property (4.13) in the
first place, where we need to modulo an additional ideal $J^{M}_{z}$. In order
to overcome this difficulty, we apply (4.13) for many different $z$, and then
intersect all the ideals $J^{M}_{{\text{span}_{\mathbb{F}_{p}}\\{x,y,z\\}+V}}$
to recover the lost information. For convenience we refer to this method as
the _intersection approach_ , which will be frequently used in this paper.

We now move from (4.8) to the following slightly different equation:

(4.14) $F(x)\equiv F(y)\mod J^{M}_{x-y},$

in which case we can obtain a better description of the solutions than (4.8).
In order to state this result, we need to introduce the following notion:

######  Definition 4.9 (Super polynomials).

Let $d,k\in\mathbb{N}_{+}$ and $s\in\mathbb{N}$. We say that a map
$F\colon\text{HP}_{d}(1)^{k}\to\text{HP}_{d}(s)$ is a _super polynomial_ if
for all $i\in\mathbb{N}^{k}$ with $|i|\leq s$, there exists
$C_{i}\in\text{HP}_{d}(s-|i|)$ such that

$F(f_{1},\dots,f_{k})=\sum_{i=(i_{1},\dots,i_{k})\in\mathbb{N}^{k},|i|\leq
s}C_{i}f_{1}^{i_{1}}\cdot\dots\cdot f_{k}^{i_{k}}$

for all $f_{1},\dots,f_{k}\in\text{HP}_{d}(1)$. We say that $F$ is _symmetric_
if $F(f_{1},\dots,f_{k})=F(f_{\sigma(1)},\dots,f_{\sigma(k)})$ for all
permutation $\sigma\colon\\{1,\dots,k\\}\to\\{1,\dots,k\\}$. The _degree_ of
$F$ (denoted as $\deg(F)$) is the largest integer $t\in\mathbb{N}$ such that
$C_{i}\neq 0$ for some $i\in\mathbb{N}^{k}$ with $|i|=t$ (it is clear that
$\deg(F)\leq s$). For convenience we define the constant zero function to have
degree $s$ for any $s\in\mathbb{Z}$. We say that $F$ is _homogeneous_ if
$C_{i}\neq 0$ for all $i\in\mathbb{N}^{k}$ with $|i|\neq\deg(F)$.

Since $L_{x}-L_{y}=L_{x-y}\in J^{M}_{x-y}$, it is not hard to see that
$F(x)=G(L_{x})$ is a solution to (4.14) for any super polynomial
$G\colon\text{HP}_{d}(1)\to\text{HP}_{d}(s)$. The next proposition shows that
this is the only possibility.

######  Proposition 4.10.

Let $d\in\mathbb{N}_{+}$, $k\in\mathbb{N},s\in\mathbb{Z}$, $\delta>0$ and
$p\gg_{\delta,d,k}1$ be a prime. Let $H$ be a subset of $\mathbb{F}_{p}^{d}$
with $|H|>\delta p^{d}$ and $M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a
non-degenerate quadratic form. Let $U_{1},\dots,U_{k}$ be (possibly trivial)
subspaces of $\mathbb{F}_{p}^{d}$ of same dimensions. For convenience denote
$U_{0}=\\{\mathbb{0}\\}$. Let $F\colon\mathbb{F}_{p}^{d}\to\text{HP}_{d}(s)$
be a map such that

$F(x)\equiv F(y)\mod J^{M}_{x-y}$

for all $x,y\in H$ with $(x,y,U_{i})$ being linearly independent tuples for
all $0\leq i\leq k$. If $d\geq s+\dim(U_{k})+8$, then there exists a super
polynomial $G\colon\text{HP}_{d}(1)\to\text{HP}_{d}(s)$ such that

$F(x)\equiv G(L_{x})\mod J^{M}$

for all $x\in H$ with $(x,U_{i})$ being linearly independent tuples for all
$0\leq i\leq k$.

###### Proof.

By Convention 1.3, there is nothing to prove when $s<0$. So we assume that
$s\in\mathbb{N}$. Throughout the proof we assume that $p\gg_{\delta,d,k}1$. By
Proposition 4.6, since $d\geq s+\dim(U_{k})+8$, there exists
$G_{0}\in\text{HP}_{d}(s)$ such that $F(x)\equiv G_{0}\mod J^{M}_{x}$ for all
$x\in H$ with $(x,U_{i})$ being linearly independent tuples for all $0\leq
i\leq k$. By Proposition A.8, since $d\geq 5$, we may write

$F(x)\equiv G_{0}+L_{x}F_{1}(x)\mod J^{M}$

for all $x\in H$ with $(x,U_{i})$ being linearly independent tuples for all
$0\leq i\leq k$ for some $F_{1}(x)\in\text{HP}_{d}(s-1)$.

Suppose we have shown that for some $k\in\mathbb{N}$, there exist
$G_{i}\in\text{HP}_{d}(s-i),0\leq i\leq k$ and some map
$F_{k+1}\colon\mathbb{F}_{p}^{d}\to\text{HP}_{d}(s-k-1)$ such that

$F(x)\equiv L_{x}^{k+1}F_{k+1}(x)+\sum_{i=0}^{k}L_{x}^{i}G_{i}\mod J^{M}$

for all $x\in H$ with $(x,U_{i})$ being linearly independent tuples for all
$0\leq i\leq k$. We show that the same conclusion holds for $k+1$. Since
$F(x)\equiv F(y)\mod J^{M}_{x-y}$ for all $x,y\in H$ with $(x,y,U_{i})$ being
linearly independent tuples for all $0\leq i\leq k$, we have that

$L_{x}^{k+1}F_{k+1}(x)+\sum_{i=0}^{k}L_{x}^{i}G_{i}\equiv
L_{y}^{k+1}F_{k+1}(y)+\sum_{i=0}^{k}L_{y}^{i}G_{i}\mod J^{M}_{x-y}.$

Since $L_{x}-L_{y}=L_{x-y}$, this implies that
$L_{x}^{k+1}(F_{k+1}(x)-F_{k+1}(y))\in J^{M}_{x-y}$. Since $d\geq 7$, by
repeatedly using Lemma 3.8, we have that $F_{k+1}(x)-F_{k+1}(y)\in
J^{M}_{x-y}\subseteq J^{M}_{x,y}$ for all $x,y\in H$ with $(x,y,U_{i})$ being
linearly independent tuples for all $0\leq i\leq k$. By Proposition 4.6, there
exists $G_{k+1}\in\text{HP}_{d}(s-k-1)$ such that $F_{k+1}(x)\equiv
G_{k+1}\mod J^{M}_{x}$ for all $x\in H$ with $(x,U_{i})$ being linearly
independent tuples for all $0\leq i\leq k$. By Proposition A.8, we may write

$F_{k+1}(x)\equiv G_{k+1}+L_{x}F_{k+2}(x)\mod J^{M}$

for $x\in H$ with $(x,U_{i})$ being linearly independent tuples for all $0\leq
i\leq k$ for some $F_{k+2}(x)\in\text{HP}_{d}(s-k-2)$. Then

$F(x)\equiv L_{x}^{k+1}F_{k+1}(x)+\sum_{i=0}^{k}L_{x}^{i}G_{i}\equiv
L_{x}^{k+2}F_{k+2}(x)+\sum_{i=0}^{k+1}L_{x}^{i}G_{i}\mod J^{M}$

for all $x\in H$ with $(x,U_{i})$ being linearly independent tuples for all
$0\leq i\leq k$.

So by induction, there exist $G_{i}\in\text{HP}_{d}(s-i),0\leq i\leq s$ and
some map $F_{s+1}\colon\mathbb{F}_{p}^{d}\to\text{HP}_{d}(-1)$ (meaning that
$F_{s+1}\equiv 0$ by Convention 1.3) such that

$F(x)\equiv
L_{x}^{s+1}F_{s+1}(x)+\sum_{i=0}^{s}L_{x}^{i}G_{i}\equiv\sum_{i=0}^{s}L_{x}^{i}G_{i}\mod
J^{M}$

for all $x\in H$ with $(x,U_{i})$ being linearly independent tuples for all
$0\leq i\leq k$. This completes the proof by the definition of super
polynomials. ∎

###  4.3. Properties for super polynomials

Before moving from equation (4.14) to more sophisticated equations, we prove
some properties for super polynomials for later uses.

By Lemma A.4, if a polynomial
$P\in\text{poly}(\mathbb{F}_{p}^{d}\to\mathbb{F}_{p})$ takes value zero on a
large subset of $\mathbb{F}_{p}^{d}$, then $P\equiv 0$. A similar result holds
for super polynomials:

######  Proposition 4.11.

Let $d,k\in\mathbb{N}_{+}$, $s\in\mathbb{Z}$, $\delta>0$ and
$p\gg_{\delta,d}1$ be a prime. Let $U$ be a subspace of $\mathbb{F}_{p}^{d}$,
$H$ be a subset of $\mathbb{F}_{p}^{d}$ with $|H|>\delta p^{d}$,
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a non-degenerate quadratic
form, and $F\colon\text{HP}_{d}(1)^{k}\to\text{HP}_{d}(s)$ be a super
polynomial given by

$F(f_{1},\dots,f_{k})=\sum_{i=(i_{1},\dots,i_{k})\in\mathbb{N}^{k},|i|\leq
s}C_{i}f_{1}^{i_{1}}\cdot\ldots\cdot f_{k}^{i_{k}}.$

Suppose that $F(L_{x_{1}},\dots,L_{x_{k}})\equiv 0\mod J^{M}$ for all
$x_{1},\dots,x_{k}\in H$ with $(x_{1},\dots,x_{k},U)$ being a linearly
independent tuple. If $d\geq\max\\{s+1,\dim(U)+k,7\\}$, then $C_{i}\equiv
0\mod J^{M}$ for all $i\in\mathbb{N}^{k},|i|\leq s$.

###### Proof.

By Convention 1.3, there is nothing to prove when $s<0$. So we assume that
$s\in\mathbb{N}$. Throughout the proof we assume that $p\gg_{\delta,d}1$. It
suffices to prove Proposition 4.11 under the assumption that the conclusion
holds for $k-1$ (when $k=1$, then we prove Proposition 4.11 without any
induction hypothesis).

We may rewrite $F$ as

$F(f_{1},\dots,f_{k})=\sum_{0\leq i\leq s}F_{i}(f_{1},\dots,f_{k-1})f_{k}^{i}$

for some super polynomial
$F_{i}\colon\text{HP}_{d}(1)^{k-1}\to\text{HP}_{d}(s-i)$ (where $F_{i}$ is
regarded as a constant if $k=1$). For any $x_{1},\dots,x_{k}\in H$ with
$(x_{1},\dots,x_{k},U)$ being a linearly independent tuple, since
$F(L_{x_{1}},\dots,L_{x_{k}})\equiv 0\mod J^{M}$, we have that
$F_{0}(L_{x_{1}},\dots,L_{x_{k-1}})\equiv 0\mod J^{M}_{x_{k}}$. Note that the
set of $x_{k}\in H$ with $(x_{1},\dots,x_{k},U)$ not being a linearly
independent tuple is of cardinality $O(p^{\dim(U)+k-1})$ By Proposition 3.11
(setting $m=1$, $V=\\{\mathbb{0}\\}$, and
$U_{1}=\text{span}_{\mathbb{F}_{p}}\\{x_{1},\dots,x_{k-1}\\}+U$), since
$d\geq\max\\{s+1,\dim(U)+k,7\\}$, we have that
$F_{0}(L_{x_{1}},\dots,L_{x_{k-1}})\equiv 0\mod J^{M}$ for any
$x_{1},\dots,x_{k-1}\in H$ with $(x_{1},\dots,x_{k-1},U)$ being a linearly
independent tuple. By induction hypothesis, we have that $F_{0}$ takes values
in $J^{M}$. So for any $x_{1},\dots,x_{k}\in H$ with $(x_{1},\dots,x_{k},U)$
being a linearly independent tuple, the fact that
$F(L_{x_{1}},\dots,L_{x_{k}})\equiv 0\mod J^{M}$ implies that
$L_{x_{k}}F^{\prime}(L_{x_{1}},\dots,L_{x_{k}})\in J^{M}$, where

$F^{\prime}(f_{1},\dots,f_{k})=\sum_{1\leq i\leq
s}F_{i}(f_{1},\dots,f_{k-1})f_{k}^{i-1}.$

By Lemma 3.8, since $d\geq 5$, we have that
$F^{\prime}(L_{x_{1}},\dots,L_{x_{k}})\in J^{M}$. We may then repeat the
previous discussion to inductively show that all of $F_{0},\dots,F_{s}$ takes
values in $J^{M}$. The conclusion now follows from the induction hypothesis. ∎

The following technical proposition will be used in the next subsection.

######  Proposition 4.12.

Let $d\in\mathbb{N}_{+}$, $s\in\mathbb{Z}$, $\delta>0$ and $p\gg_{\delta,d}1$
be a prime. Let $H$ be a subset of $\mathbb{F}_{p}^{d}$ with $|H|>\delta
p^{d}$, $M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a non-degenerate
quadratic form, and $G_{x}\colon\text{HP}_{d}(1)\to\text{HP}_{d}(s)$ be a
super polynomial for all $x\in H\backslash\\{\mathbb{0}\\}$ such that

(4.15) $\begin{split}G_{x}(L_{y})\equiv G_{y}(L_{x})\mod J^{M}\end{split}$

for all linearly independent $x,y\in H$. If $d\geq s+11$, then there exists a
symmetric super polynomial
$Q\colon\text{HP}_{d}(1)\times\text{HP}_{d}(1)\to\text{HP}_{d}(s)$ such that

$G_{x}(L_{y})\equiv Q(L_{x},L_{y})\mod J^{M}$

for all linearly independent $x,y\in H$.

Before proving Proposition 4.12, we need a lemma:

######  Lemma 4.13.

Let $d\in\mathbb{N}_{+}$, $k,s\in\mathbb{N}$ with $k\leq s$, and $p\gg_{d,s}1$
be a prime. Let $M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a non-
degenerate quadratic form and $x,y\in\mathbb{F}_{p}^{d}$ be linearly
independent. Suppose that

(4.16) $\sum_{i=0}^{k}C_{i}L_{x}^{i}L_{y}^{k-i}\equiv
PL_{x}^{k+1}+QL_{y}^{k+1}\mod J^{M}$

for some $C_{i}\in\text{HP}_{d}(s-k)$ and some $P,Q\in\text{HP}_{d}(s-k-1)$.
If $d\geq 7$, then we have that $C_{i}\in J^{M}_{x,y}$ for all $0\leq i\leq
k$.

###### Proof.

Throughout the proof we assume that $p\gg_{d,s}1$. If $k=0$, then then it
follows from (4.16) that $C_{0}\equiv PL_{x}+QL_{y}\mod J^{M}$ and thus
$C_{0}\in J^{M}_{x,y}$. If $k=1$, then it follows from (4.16) that

$C_{0}L_{y}+C_{1}L_{x}\equiv PL_{x}^{2}+QL_{y}^{2}\mod J^{M}.$

It follows that $C_{0}L_{y}\equiv QL_{y}^{2}\mod J^{M}_{x}$. By Lemma 3.8,
since $d\geq 7$, we have that $C_{0}\equiv QL_{y}\mod J^{M}_{x}$ and thus
$C_{0}\in J^{M}_{x,y}$. Similarly, we have $C_{1}\in J^{M}_{x,y}$. So the
conclusion holds.

Now assume that the conclusion holds for $k-2$ for some $2\leq k\leq s$. We
prove that the conclusion holds for $k$. It follows from (4.16) that
$C_{0}L_{y}^{k}\equiv QL_{y}^{k+1}\mod J^{M}_{x}$. Since $d\geq 7$, by
repeatedly using Lemma 3.8, we have that $C_{0}\equiv QL_{y}\mod J^{M}_{x}$
and thus $C_{0}\in J^{M}_{x,y}$. By Proposition A.8, since $d\geq 7$, there
exist $P^{\prime},Q^{\prime}\in\text{HP}_{d}(s-k-1)$ such that $C_{0}\equiv
L_{x}P^{\prime}+L_{y}Q^{\prime}\mod J^{M}$. Similarly, there exist
$P^{\prime\prime},Q^{\prime\prime}\in\text{HP}_{d}(s-k-1)$ such that
$C_{k}\equiv L_{x}P^{\prime\prime}+L_{y}Q^{\prime\prime}\mod J^{M}$.
Substituting the expressions of $C_{0}$ and $C_{k}$ back to (4.16), we have
that

(4.17)
$L_{x}L_{y}(\sum_{i=0}^{k-2}C_{i+1}L_{x}^{i}L_{y}^{k-2-i})\equiv(P-P^{\prime\prime})L_{x}^{k+1}+(Q-Q^{\prime})L_{y}^{k+1}-P^{\prime}L_{x}L_{y}^{k}-Q^{\prime\prime}L_{x}^{k}L_{y}\mod
J^{M}.$

In particular, we have that $(P-P^{\prime\prime})L_{x}^{k+1}\in J^{M}_{y}$. By
Lemma 3.8, we have that $P-P^{\prime\prime}\mod J^{M}_{y}$. By Proposition
A.8, there exists $P^{\prime\prime\prime}\in\text{HP}_{d}(s-k-2)$ such that
$P-P^{\prime\prime}\equiv L_{y}P^{\prime\prime\prime}\mod J^{M}$. Similarly,
there exists $Q^{\prime\prime\prime}\in\text{HP}_{d}(s-k-2)$ such that
$Q-Q^{\prime}\equiv L_{x}Q^{\prime\prime\prime}\mod J^{M}$. Substituting these
back to (4.17), we have that

$L_{x}L_{y}(\sum_{i=0}^{k-2}C_{i+1}L_{x}^{i}L_{y}^{k-2-i})\equiv
L_{x}L_{y}(P^{\prime\prime\prime}L_{x}^{k}+Q^{\prime\prime\prime}L_{y}^{k}-P^{\prime}L_{y}^{k-1}-Q^{\prime\prime}L_{x}^{k-1})\mod
J^{M}.$

By repeatedly using Lemma 3.8, we have that

$\sum_{i=0}^{k-2}C_{i+1}L_{x}^{i}L_{y}^{k-2-i}\equiv(P^{\prime\prime\prime}L_{x}-Q^{\prime\prime})L_{x}^{k-1}+(Q^{\prime\prime\prime}L_{y}-P^{\prime})L_{y}^{k-1}\mod
J^{M}.$

By induction hypothesis, we have that $C_{i}\in J^{M}_{x,y}$ for all $1\leq
i\leq k-1$ and thus for all $0\leq i\leq k$. This completes the proof. ∎

###### Proof of Proposition 4.12.

By Convention 1.3, there is nothing to prove when $s<0$. So we assume that
$s\in\mathbb{N}$. Throughout the proof we assume that $p\gg_{\delta,d}1$. For
$0\leq k\leq s+1$, we say that _Property $k$_ holds if there exist a symmetric
super polynomial
$Q_{k}\colon\text{HP}_{d}(1)\times\text{HP}_{d}(1)\to\text{HP}_{d}(s)$, for
each $x\in H\backslash\\{\mathbb{0}\\}$ a homogeneous super polynomial
$Q_{k,x}\colon\text{HP}_{d}(1)\times\text{HP}_{d}(1)\to\text{HP}_{d}(s)$ of
degree $k$ and a super polynomial
$G_{k,x}\colon\text{HP}_{d}(1)\to\text{HP}_{d}(s-k-1)$ such that

(4.18) $\begin{split}G_{x}(L_{y})\equiv
Q_{k}(L_{x},L_{y})+Q_{k,x}(L_{x},L_{y})+L_{y}^{k+1}G_{k,x}(L_{y})\mod
J^{M}\end{split}$

for all linearly independent $x,y\in H$, where when $k=s+1$, (4.18) is
understood as

$G_{x}(L_{y})\equiv Q_{s+1}(L_{x},L_{y})\mod J^{M}.$

Assume that $G_{x}(f)=\sum_{i=0}^{s}C_{i,x}f^{i}$ for some
$C_{x,i}\in\text{HP}_{d}(s-i)$ for all $x\in H\backslash\\{\mathbb{0}\\}$. We
have that Property 0 holds by setting $Q_{0}\equiv 0$, $Q_{0,x}(f,g)\equiv
C_{i,0}$, and $G_{0,x}(f):=\sum_{i=1}^{s}C_{i,x}f^{i-1}$. Now assume that
Property $k$ holds for some $0\leq k\leq s$. We show that Property $k+1$
holds. By (4.15) and (4.18), we have that

(4.19) $\begin{split}Q_{k,x}(L_{x},L_{y})+L_{y}^{k+1}G_{k,x}(L_{y})\equiv
Q_{k,y}(L_{y},L_{x})+L_{x}^{k+1}G_{k,y}(L_{x})\mod J^{M}\end{split}$

for all linearly independent $x,y\in H$. Assume that

(4.20)
$\begin{split}Q_{k,x}(f,g)=\sum_{i=0}^{k}A_{x,i}f^{i}g^{k-i}\end{split}$

for some $A_{x,i}\in\text{HP}_{d}(s-k)$. It follows from (4.19) that

(4.21)
$\begin{split}\sum_{i=0}^{k}(A_{x,i}-A_{y,k-i})L_{x}^{i}L_{y}^{k-i}\equiv
L_{x}^{k+1}G_{k,y}(L_{x})-L_{y}^{k+1}G_{k,x}(L_{y})\mod J^{M}\end{split}$

for all linearly independent $x,y\in H$. By Lemma 4.13, since $d\geq 7$, we
have that $A_{x,i}\equiv A_{y,k-i}\mod J^{M}_{x,y}$ for all $0\leq i\leq k$
and linearly independent $x,y\in H$. By Corollary 4.7, since $d\geq s-k+11$,
for all $0\leq i\leq k$, there exists $A_{i}\in\text{HP}_{d}(s-k)$ such that

$A_{x,i}\equiv A_{i}\equiv A_{x,k-i}\equiv A_{k-i}\mod J^{M}_{x}$

for all $x\in H\backslash\\{\mathbb{0}\\}$. We may assume without loss of
generality that $A_{i}=A_{k-i}$. By Proposition A.8, since $d\geq 5$, we may
write

(4.22) $\begin{split}A_{x,i}\equiv A_{i}+L_{x}A^{\prime}_{x,i}\mod
J^{M}\end{split}$

for some $A^{\prime}_{x,i}\in\text{HP}_{d}(s-k-1)$. Note that we may write
$G_{k,x}$ as

(4.23) $\begin{split}G_{k,x}(f)=P_{x}+fG_{k+1,x}(f)\end{split}$

for some $P_{x}\in\text{HP}_{d}(s-k-1)$ and super polynomial
$G_{k+1,x}\colon\text{HP}_{d}(1)\to\text{HP}_{d}(s-k-2)$. By (4.18), (4.20),
(4.22) and (4.23), we have that

$\begin{split}G_{x}(L_{y})\equiv
Q_{k+1}(L_{x},L_{y})+Q_{k+1,x}(L_{x},L_{y})+L_{y}^{k+2}G_{k+1,x}(L_{y})\mod
J^{M}\end{split}$

for all linearly independent $x,y\in H$, where

$Q_{k+1}(f,g):=Q_{k}(f,g)+\sum_{i=0}^{k}A_{i}f^{i}g^{k-i}$

and

$Q_{k+1,x}(f,g):=P_{x}g^{k+1}+\sum_{i=0}^{k}A^{\prime}_{x,i}f^{i+1}g^{k-i}.$

Since $Q_{k}$ is symmetric and $A_{i}=A_{k-i}$, we have that $Q_{k+1}$ is also
symmetric. On the other hand, it is clear that $Q_{k+1,x}$ is a homogeneous
super polynomial of degree $k+1$. So Property $k+1$ holds.

By induction, we have that Property $s+1$ holds, meaning that

$G_{x}(L_{y})\equiv Q_{s+1}(L_{x},L_{y})\mod J^{M}$

for all linearly independent $x,y\in H$ for some symmetric super polynomial
$Q_{s+1}\colon\text{HP}_{d}(1)\times\text{HP}_{d}(1)\to\text{HP}_{d}(s)$. We
are done. ∎

###  4.4. Solutions to some special equations

Next, we move forward from equation (4.6) to the following more advanced
cocycle equation:

(4.24) $C(x,y)+C(y,z)\equiv C(x,z)\mod\mathbb{Z}\text{ for all $x,y,z\in G$},$

where $C$ is a map from $G\times G$ to $\mathbb{R}$ and $G$ is an abelian
group. Setting $z$ to be an arbitrary element in $G$, it is obvious that the
solution to (4.24) is $C(x,y)\equiv F(x)-F(y)\mod\mathbb{Z}$ for some map
$F\colon G\to\mathbb{R}$ for all $x,y\in G$. In the setting of shifted ideals,
one can study a similar equation:

(4.25) $C(x,y)+C(y,z)\equiv C(x,z)\mod J^{M}_{x-y,y-z}\text{ for all
$x,y,z\in\mathbb{F}_{p}^{d}$},$

where $C$ is a map from $\mathbb{F}_{p}^{d}$ to $\text{HP}_{d}(s)$. Comparing
(4.24) with (4.25), it is natural to conjecture that the solution to (4.25) is
$C(x,y)\equiv F(x)-F(y)\mod J^{M}_{x-y}$ for some
$F\colon\mathbb{F}_{p}^{d}\to\text{HP}_{d}(s)$. This is indeed the case at
least when $x,y$ are linearly independent.

######  Proposition 4.14.

Let $d\in\mathbb{N}_{+},s\in\mathbb{Z}$, $p\gg_{d,s}$ be a prime,
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a non-degenerate quadratic
form and $C\colon(\mathbb{F}_{p}^{d})^{2}\to\text{HP}_{d}(s)$ be a map such
that (4.25) holds. If $d\gg_{s}1$, then there exists a map
$F\colon\mathbb{F}_{p}^{d}\to\text{HP}_{d}(s)$ such that $C(x,y)\equiv
F(x)-F(y)\mod J^{M}_{x-y}$ for all linearly independent
$x,y\in\mathbb{F}_{p}^{d}$.

Again, instead of proving Proposition 4.14, we prove the following more
general result:

######  Proposition 4.15.

Let $d\in\mathbb{N}_{+},s\in\mathbb{Z}$, $\delta>0$, and $p\gg_{\delta,d}1$ be
a prime. Let $H$ be a subset of $\mathbb{F}_{p}^{d}$ with $|H|>\delta p^{d}$,
$U$ be a (possibly trivial) subspace of $\mathbb{F}_{p}^{d}$, and
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a non-degenerate quadratic
form. For all $x,y\in H$ with $(x,y,U)$ being a linearly independent tuple,
let $C(x,y)$ be an element in $\text{HP}_{d}(s)$. Suppose that for all
$x,y,z\in H$ with $(x,y,z,U)$ being a linearly independent tuple, we have

(4.26) $C(x,y)+C(y,z)\equiv C(x,z)\mod J^{M}_{x-y,y-z}.$

If $d\geq s+\dim(U)+9$, then there exist $\phi(x)\in\text{HP}_{d}(s)$ for all
$x\in H$ with $(x,U)$ being a linearly independent tuple such that

$C(x,y)\equiv\phi(x)-\phi(y)\mod J^{M}_{x-y}$

for all $x,y\in H$ with $(x,y,U)$ being a linearly independent tuple.

###### Proof.

By Convention 1.3, there is nothing to prove when $s<0$. So we assume that
$s\in\mathbb{N}$. Throughout the proof we assume that $p\gg_{\delta,d}1$.
Suppose that either $s=0$, or $s\geq 1$ and we have shown the conclusion holds
for $s-1$. We prove that the conclusion holds for $s$.

Applying Proposition A.8 to $J^{M}_{x-y,y-z}$, we have that if $d\geq 7$, then
for all $x,y,b\in H$ with $(x,y,b,U)$ being a linearly independent tuple,
there exists $P_{x,y,b}\in\text{HP}_{d}(s-1)$ such that

(4.27) $C(x,y)\equiv(C(x,b)-C(y,b))+L_{b-x}P_{x,y,b}\mod J^{M}_{x-y}.$

For all $x,y,z,b\in H$ with $(x,y,z,b,U)$ being a linearly independent tuple,
since $C(x,y)+C(y,z)\equiv C(x,z)\mod J^{M}_{x-y,y-z}$, it follows from (4.27)
that

$L_{b-x}(P_{x,y,b}+P_{y,z,b}-P_{x,z,b})\equiv
L_{b-x}P_{x,y,b}+L_{b-y}P_{y,z,b}-L_{b-x}P_{x,z,b}\equiv 0\mod
J^{M}_{x-y,y-z}.$

Since $(x,y,z,b,U)$ is a linearly independent tuple, by Lemma 3.8, if $d\geq
9$, then

(4.28) $P_{x,y,b}+P_{y,z,b}-P_{x,z,b}\equiv 0\mod J^{M}_{x-y,y-z}.$

We arrive at an equation similar to (4.26), except that $P_{x,y,b}$ are
elements in $\text{HP}_{d}(s-1)$ instead of $\text{HP}_{d}(s)$. Therefore, we
may use the induction hypothesis to obtain a description for $P_{x,y,b}$.

Claim 1. For any $b\in H$ with $(b,U)$ being a linearly independent tuple,
there exist $\psi_{b}(x)\in\text{HP}_{d}(s)$ for all $x\in H$ with $(x,b,U)$
being a linearly independent tuple such that

$C(x,y)\equiv\psi_{b}(x)-\psi_{b}(y)\mod J^{M}_{x-y}$

for all $x,y\in H$ with $(x,y,b,U)$ being a linearly independent tuple.

If $s=0$, then $P_{x,y,b}\equiv 0$ by Convention 1.3. Setting
$\psi_{b}(x):=C(x,b)$ for all $x\in H$ with $(x,b,U)$ being a linearly
independent tuple, it follows from (4.27) that
$C(x,y)=\psi_{b}(x)-\psi_{b}(y)\mod J^{M}_{x-y}$ whenever $(x,y,b,U)$ is a
linearly independent tuple.

If $s\geq 1$, then since $d\geq s+\dim(U)+9=(s-1)+(\dim(U)+1)+9$, we may apply
the induction hypothesis to (4.28) and $P_{x,y,b}$ to conclude that for all
$b\in H$ with $(b,U)$ being a linearly independent tuple, there exist
$\psi_{b}(x)\in\text{HP}_{d}(s-1)$ for all $x\in H$ with $(x,b,U)$ being a
linearly independent tuple such that

$P_{x,y,b}\equiv\psi_{b}(x)-\psi_{b}(y)\mod J^{M}_{x-y}$

for all $x,y\in H$ with $(x,y,b,U)$ being a linearly independent tuple.
Setting $\psi_{b}(x):=C(x,b)+L_{b-x}\psi_{b}(x)$, it follows from (4.27) that

$C(x,y)\equiv(C(x,b)-C(y,b))+L_{b-x}P_{x,y,b}\equiv\psi_{b}(x)-\psi_{b}(y)\mod
J^{M}_{x-y}$

for all $x,y\in H$ with $(x,y,b,U)$ being a linearly independent tuple. We
have thus proved Claim 1 in both cases.

In order to complete the proof of Proposition 4.15, we need to remove the
restriction that $x,y,b$ are linearly independent in the claim. Our strategy
is to apply the claim for many linearly independent $b$ and to obtain many
different maps $\psi_{b}$. Then by studying the interactions of these
$\psi_{b}$, we extend them to a universal map $\phi$ such that
$C(x,y)\equiv\phi(x)-\phi(y)\mod J^{M}_{x-y}$ holds for all $x,y\in H$ with
$(x,y,U)$ being a linearly independent tuple.

By Claim 1, for all $x,y,b,b^{\prime}\in H$ with $(x,y,b,U)$ and
$(x,y,b^{\prime},U)$ being linearly independent tuples, we have that

$(\psi_{b}-\psi_{b^{\prime}})(x)-(\psi_{b}-\psi_{b^{\prime}})(y)\equiv
C(x,y)-C(x,y)=0\mod J^{M}_{x-y}.$

By Proposition 4.10, if $d\geq s+\dim(U)+9$, then for all $b,b^{\prime}\in H$
with $(b,U)$ and $(b^{\prime},U)$ being linearly independent tuples, there
exists a super polynomial
$G_{b,b^{\prime}}\colon\text{HP}_{d}(1)\to\text{HP}_{d}(s)$ such that

$(\psi_{b}-\psi_{b^{\prime}})(x)\equiv G_{b,b^{\prime}}(L_{x})\mod J^{M}$

for all $x\in H$ with $(x,b,U)$ and $(x,b^{\prime},U)$ being linearly
independent tuples. So for all $x,b,b^{\prime},b^{\prime\prime}\in H$ with
$(x,b,U)$, $(x,b^{\prime},U)$ and $(x,b^{\prime\prime},U)$ being linearly
independent tuples, we have that

$G_{b,b^{\prime}}(L_{x})-G_{b,b^{\prime\prime}}(L_{x})\equiv(\psi_{b}-\psi_{b^{\prime}})(x)-(\psi_{b}-\psi_{b^{\prime\prime}})(x)\equiv
G_{b^{\prime\prime},b^{\prime}}(L_{x})\mod J^{M}.$

Let $B$ be a set of $d-\dim(U)$ vectors in $H$ which completes $U$ into a
basis of $\mathbb{F}_{p}^{d}$ (such $B$ exists since $|H|>\delta p^{d}$). For
$b\in B$, let $U_{b}$ be the set of $x\in H$ with $(x,b,U)$ being a linearly
independent tuple. Fix some $b_{0}\in B$. For $b\in B$ and $x\in U_{b}$,
define $\phi_{b_{0}}(x):=\psi_{b_{0}}(x)$ and
$\phi_{b}(x):=\psi_{b}(x)-G_{b,b_{0}}(L_{x})$ if $b\neq b_{0}$.

Claim 2. that $\phi_{b}(x)\equiv\phi_{b^{\prime}}(x)\mod J^{M}$ for all
$b,b^{\prime}\in B$ and $x\in U_{b}\cap U_{b^{\prime}}$.

Indeed, we may assume without loss of generality that $b\neq b^{\prime}$ and
$b\neq b_{0}$. If $b^{\prime}=b_{0}$, then

$\phi_{b}(x)-\phi_{b^{\prime}}(x)\equiv\psi_{b}(x)-G_{b,b_{0}}(L_{x})-\psi_{b_{0}}(x)\equiv
0\mod J^{M}.$

If $b^{\prime}\neq b_{0}$, then

$\begin{split}&\quad\phi_{b}(x)-\phi_{b^{\prime}}(x)\equiv(\psi_{b}(x)-G_{b,b_{0}}(L_{x}))-(\psi_{b^{\prime}}(x)-G_{b^{\prime},b_{0}}(L_{x}))\\\
&\equiv
G_{b,b^{\prime}}(L_{x})-G_{b,b_{0}}(L_{x})+G_{b^{\prime},b_{0}}(L_{x})\equiv
0\mod J^{M}.\end{split}$

This proves Claim 2.

By Claim 2, there exists $\phi(x)\in\text{HP}_{d}(s)$ for all $x\in\cup_{b\in
B}U_{b}$ such that

$\phi(x)\equiv\phi_{b}(x)\mod J^{M}$

for all $b\in B$ with $x\in U_{b}$. Note that for all $x,y\in H$ with
$(x,y,U)$ being a linearly independent tuple, since $d\geq\dim(U)+3$, there
exists $b\in B$ with $(x,y,b,U)$ being a linearly independent tuple. So
$x,y\in U_{b}$ and thus

$\phi(x)-\phi(y)\equiv\phi_{b}(x)-\phi_{b}(y)\equiv\psi_{b_{0}}(x)-\psi_{b_{0}}(y)\equiv
C(x,y)\mod J^{M}_{x-y}$

if $b=b_{0}$, and

$\phi(x)-\phi(y)\equiv\phi_{b}(x)-\phi_{b}(y)\equiv(\psi_{b}(x)-G_{b,b_{0}}(L_{x}))-(\psi_{b}(y)-G_{b,b_{0}}(L_{y}))\equiv
C(x,y)\mod J^{M}_{x-y}$

if $b\neq b_{0}$, where we used the fact that $G_{b,b_{0}}(L_{x})\equiv
G_{b,b_{0}}(L_{y})\mod J^{M}_{x-y}$ since $G_{b,b_{0}}$ is a super polynomial.
Finally, since $\cup_{b\in B}U_{b}$ consists of all $x\in H$ with $(x,U)$
being a linearly independent tuple, we are done. ∎

We need to explore the solutions to one more equation before proving Theorem
4.3.

######  Proposition 4.16.

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

$P=\\{\ell_{1}v_{1}+\dots+\ell_{D}v_{D}\colon\ell_{i}\in\mathbb{Z}\cap(-L_{i},L_{i})\text{
for all }1\leq i\leq D\\}\subseteq\mathbb{F}_{p}^{d}$

be a proper and homogeneous generalized arithmetic progression of dimension
$D$ with $|P|>\delta p^{d}$, $M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a
non-degenerate quadratic form and $F\colon P\to\text{HP}_{d}(s)$ be a map such
that

(4.29) $F(x)+F(y)\equiv F(x+y)\mod J^{M}_{x}\cap J^{M}_{y}$

for all linearly independent $x,y\in P(\frac{1}{2})$. If $d\geq s+9$, then
there exist a super polynomial $G\colon\text{HP}_{d}(1)\to\text{HP}_{d}(s-2)$
and a locally linear map $T\colon P(\frac{1}{32})\to\text{HP}_{d}(s)$ such
that

$F(x)\equiv L_{x}^{2}G(L_{x})+T(x)\mod J^{M}$

for all $x\in P(\frac{1}{32})\backslash\\{\mathbb{0}\\}$.

###### Proof.

By Convention 1.3, there is nothing to prove when $s<0$. So we assume that
$s\in\mathbb{N}$. Throughout the proof we assume that $p\gg_{\delta,d,D}1$,
and we implicitly use (4.5) for the estimate the cardinality of sets of the
form $P(c)$. We start with a reformulation of (4.29). Fix any linearly
independent $x,y\in P(\frac{1}{2})$. Since $F(x)+F(y)\equiv F(x+y)\mod
J^{M}_{x}$ and $d\geq 5$, by Proposition A.8, we have that $F(x)+F(y)\equiv
F(x+y)+L_{x}R^{\prime}(x,y)\mod J^{M}$ for some
$R^{\prime}(x,y)\in\text{HP}_{d}(s-1)$. Since $F(x)+F(y)\equiv F(x+y)\mod
J^{M}_{y}$, we have that $L_{x}R^{\prime}(x,y)\equiv 0\mod J^{M}_{y}$. By
Lemma 3.8, since $d\geq 7$, we have that $R^{\prime}(x,y)\equiv 0\mod
J^{M}_{y}$. So by Proposition A.8, we may write $R^{\prime}(x,y)\equiv
L_{y}R(x,y)\mod J^{M}$ for some $R(x,y)\in\text{HP}_{d}(s-2)$. In conclusion,
we have that

(4.30) $F(x)+F(y)\equiv F(x+y)+L_{x}L_{y}R(x,y)\mod J^{M}$

for some $R(x,y)\in\text{HP}_{d}(s-2)$ for all linearly independent $x,y\in
P(\frac{1}{2})$.

We first assume that $s\geq 2$. By symmetry, (4.30) implies that
$L_{x}L_{y}(R(x,y)-R(y,x))\in J^{M}$ for all linearly independent $x,y\in
P(\frac{1}{2})$. By Lemma 3.8, since $d\geq 5$, this implies that

(4.31) $\begin{split}R(x,y)\equiv R(y,x)\mod J^{M}\end{split}$

for all linearly independent $x,y\in P(\frac{1}{2})$.

Fix any linearly independent $x,y,z\in P(\frac{1}{4})$. Then (4.30) implies
that

(4.32) $\begin{split}&\quad F(x)+F(y)+F(z)-F(x+y+z)\\\
&=(F(y)+F(z)-F(y+z))+(F(x)+F(y+z)-F(x+y+z))\\\ &\equiv
L_{y}L_{z}R(y,z)+L_{x}L_{y+z}R(x,y+z)\mod J^{M}.\end{split}$

By symmetry, we also have that

(4.33) $\begin{split}F(x)+F(y)+F(z)-F(x+y+z)\equiv
L_{x}L_{z}R(x,z)+L_{y}L_{x+z}R(y,x+z)\mod J^{M}.\end{split}$

Comparing (4.32) and (4.33), we have that

(4.34) $\begin{split}&\quad
L_{y}L_{z}(R(y,z)-R(y,x+z))+L_{x}L_{y}(R(x,y+z)-R(y,x+z))\\\
&+L_{x}L_{z}(R(x,y+z)-R(x,z))\equiv 0\mod J^{M}.\end{split}$

In particular, $L_{y}L_{z}(R(y,z)-R(y,x+z))\in J^{M}_{x}$. By Lemma 3.8, since
$d\geq 7$, we have that $R(y,z)\equiv R(y,x+z)\mod J^{M}_{x}$. In other words,
for all linearly independent $x,y,z\in P(\frac{1}{8})$, we have that
$R(y,x)\equiv R(y,z)\mod J^{M}_{x-z}$. By Proposition 4.10, since $d\geq s+7$,
for all $y\in P(\frac{1}{8})\backslash\\{\mathbb{0}\\}$, there exists a super
polynomial $G_{y}\colon\text{HP}_{d}(1)\to\text{HP}_{d}(s-2)$ such that
$R(y,x)\equiv G_{y}(L_{x})\mod J^{M}$ for all $x\in P(\frac{1}{8})$ with $x,y$
being linearly independent. By (4.31), we have that

$\begin{split}G_{x}(L_{y})\equiv G_{y}(L_{x})\mod J^{M}\end{split}$

for all linearly independent $x,y\in P(\frac{1}{8})$. By Proposition 4.12,
since $d\geq s+9$, there exists a symmetric super polynomial
$Q\colon\text{HP}_{d}(1)\times\text{HP}_{d}(1)\to\text{HP}_{d}(s-2)$ such that

$R(x,y)=G_{x}(L_{y})\equiv Q(L_{x},L_{y})\mod J^{M}$

for all linearly independent $x,y\in P(\frac{1}{8})$. We may then write
$Q(f,g)=\sum_{k=0}^{s-2}Q_{k}(f,g)$ for some symmetric homogeneous super
polynomials
$Q_{k}\colon\text{HP}_{d}(1)\times\text{HP}_{d}(1)\to\text{HP}_{d}(s-2)$ of
degree $k$. Write

$Q_{k}(f,g)=\sum_{i=0}^{k}C_{k,i}f^{i}g^{k-i}$

for some $C_{k,i}\in\text{HP}_{d}(s-2-k)$. For convenience write $C_{k,-1}=0$.
Then we may rewrite (4.34) as

(4.35) $\begin{split}\sum_{k=0}^{s-2}\sum_{0\leq a,b,c\leq
k,a+b+c=k+2}L_{x}^{a}L_{y}^{b}L_{z}^{c}K(a,b,c)\equiv 0\mod J^{M},\end{split}$

where

$\begin{split}&\quad K(a,b,c)=-C_{k,b-1}\binom{k-(b-1)}{a}\mathbb{1}_{a\neq
0}+C_{k,a-1}\binom{k-(a-1)}{b-1}\\\ &\qquad-
C_{k,b-1}\binom{k-(b-1)}{a-1}+C_{k,a-1}\binom{k-(a-1)}{b}\mathbb{1}_{b\neq
0}.\end{split}$

Note that $K(a,b,c)=0$ if $a=0$ or $b=0$. If $a,b\neq 0$, then

$K(a,b,c)=C_{k,a-1}\binom{k+2-a}{b}-C_{k,b-1}\binom{k+2-b}{a}.$

So by (4.35) and Proposition 4.11, since $d\geq\max\\{s+1,7\\}$, we have that

$K(a+1,b+1,c)=C_{k,a}\binom{k+1-a}{b+1}-C_{k,b}\binom{k+1-b}{a+1}\equiv 0\mod
J^{M}$

for all $a,b,c\in\mathbb{N}$ with $a+b+c=k$. From this it is not hard to see
that there exists $C_{k}\in\text{HP}_{d}(s-2-k)$ such that
$C_{k,a}\equiv\binom{k+2}{a+1}C_{k}\mod J^{M}$ for all $0\leq a\leq k$.
Therefore,

$\begin{split}&\quad L_{x}L_{y}R(x,y)\equiv
L_{x}L_{y}\sum_{k=0}^{s-2}\sum_{i=0}^{k}\binom{k+2}{i+1}C_{k}L_{x}^{i}L_{y}^{k-i}\\\
&=\sum_{k=0}^{s-2}\sum_{i=1}^{k+1}\binom{k+2}{i}C_{k}L_{x}^{i}L_{y}^{k+2-i}=\sum_{k=0}^{s-2}C_{k}(L_{x+y}^{k+2}-L_{x}^{k+2}-L_{y}^{k+2})\mod
J^{M}.\end{split}$

So for all $x\in P(\frac{1}{8})$, writing
$F^{\prime}(x):=\sum_{k=0}^{s-2}C_{k}L_{x}^{k+2}$,
$G(f):=\sum_{k=0}^{s-2}C_{k}f^{k}$, and $T(x):=F(x)-F^{\prime}(x)$, we have
that $F^{\prime}(x)=L_{x}^{2}G(L_{x})\in J^{M}$ and

(4.36) $T(x)+T(y)\equiv T(x+y)\mod J^{M}$

for all linearly independent $x,y\in P(\frac{1}{8})$.

Now if $s<2$, then $R(x,y)\equiv 0$. Setting $G\equiv 0$ and $T:=F$, by (4.30)
, (4.36) still holds for all all linearly independent $x,y\in P(\frac{1}{8})$.

For convenience define $T(\mathbb{0}):=0$. It remains to show that $T$ is
locally linear.

Claim. We have that (4.36) holds for all (not necessarily linearly
independent) $x,y\in P(\frac{1}{32})$.

For all $x,y\in P(\frac{1}{16})\backslash\\{\mathbb{0}\\}$ with
$x+y\neq\mathbb{0}$, since $d\geq 2$, there exists $z\in P(\frac{1}{16})$ such
that $(x,z),(x+y,z)$ and $(y,x+z)$ are linearly independent pairs. So it
follows from (4.36) that

$(T(x)+T(z))+T(x+y+z)+(T(y)+T(x+z))\equiv T(x+z)+(T(x+y)+T(z))+T(x+y+z)\mod
J^{M},$

which implies that (4.36) holds for all $x,y\in
P(\frac{1}{16})\backslash\\{\mathbb{0}\\}$ with $x+y\neq\mathbb{0}$.

Since $T(\mathbb{0})=0$, (4.36) also holds for all $x,y\in P(\frac{1}{8})$
with $x=\mathbb{0}$ or $y=\mathbb{0}$. On the other hand, for all $x,y\in
P(\frac{1}{32})\backslash\\{\mathbb{0}\\}$, there exists $z\in
P(\frac{1}{32})$ such that $(x,z),(-x,x+z),(y,z)$ and $(-y,y+z)$ are linearly
independent pairs. So it follows from (4.36) that

$T(x)+T(-x)+T(z)\equiv T(-x)+T(x+z)\equiv T(z)\equiv T(y)+T(-y)+T(z)\mod
J^{M},$

which implies that $T(x)+T(-x)\equiv C\mod J^{M}$ for some $C\in J^{M}$ for
all $x\in P(\frac{1}{32})\backslash\\{\mathbb{0}\\}$. Since

$2C\equiv T(x)+T(-x)+T(y)+T(-y)\equiv T(x+y)+T(-x-y)\equiv C\mod J^{M}$

for all $x,y\in P(\frac{1}{64})\backslash\\{\mathbb{0}\\}$ with
$x+y\neq\mathbb{0}$, we have that $C\in J^{M}$ and thus

$T(x)+T(-x)\equiv 0\mod J^{M}$

for all $x\in P(\frac{1}{32})\backslash\\{\mathbb{0}\\}$. This completes the
proof of the claim since $T(\mathbb{0})=0$.

Since $\text{HP}_{d}(s)/(J^{M}\cap\text{HP}_{d}(s))$ is an
$\mathbb{F}_{p}$-vector space, it is not hard to see from the claim that
$T\mod J^{M}$ is determined by its values on the generators of $P$. So there
exist $f_{1},\dots,f_{D}\in\text{HP}_{d}(s)$ such that

$T(\ell_{1}v_{1}+\dots+\ell_{D}v_{D})\equiv\ell_{1}f_{1}+\dots+\ell_{D}f_{D}\mod
J^{M}$

for all $\ell_{i}\in\mathbb{Z}\cap(-L_{i}/32,L_{i}/32)$. So $T$ is a locally
linear map on $P(\frac{1}{32})$ and we are done. ∎

###  4.5. Proof of Theorem 4.3

We are now ready to prove Theorem 4.3. Throughout the proof we assume that
$p\gg_{\delta,d,D}1$, and we implicitly use (4.5) for the estimate the
cardinality of sets of the form $P(c)$. It is not hard to see that

(4.37) $P(c)+P(c^{\prime})\subseteq P(c+c^{\prime})\text{ for all
$0<c,c^{\prime}<1$ with $c+c^{\prime}\leq 1$.}$

Step 1: a preliminary description for $\xi(x)-\xi(y)$. We first show that
$\xi(x)-\xi(y)\mod J^{M}_{x,y}$ depends only on the difference $x-y$. For
$t\in P(\frac{1}{2})$, denote $\xi_{t}(x):=\xi(x+t)-\xi(x)$. By assumption, we
have that

$\xi_{t}(x)=\xi_{t}(y)\mod J^{M}_{x,y,t}$

for all linearly independent $x,y,t\in P(\frac{1}{2})$ (which ensures that
$x+t,y+t\in P$ by (4.37)). By Proposition 4.6, since $d\geq s+10$, there
exists $G_{t}\in\text{HP}_{d}(s)$ such that

$\xi_{t}(x)\equiv G_{t}\mod J^{M}_{x,t}$

for all linearly independent $x,t\in P(O(1)^{-1})$. In other words,

$\xi(x)-\xi(y)\equiv G_{x-y}\mod J^{M}_{x,y}$

for all linearly independent $x,y\in P(O(1)^{-1})$ (which enforces $x-y\in
P(O(1)^{-1})$ by (4.37)).

Applying Proposition A.8 to $J^{M}_{x,y}$, since $d\geq 7$, then we may write

(4.38) $\xi(x)-\xi(y)\equiv L_{x}A_{x,y}-L_{y}B_{x,y}+G_{x-y}\mod J^{M}$

for some $A_{x,y},B_{x,y}\in\text{HP}_{d}(s-1)$ for all linearly independent
$x,y\in P(O(1)^{-1})$.

Step 2: solutions to $A_{x,y}$ and $B_{x,y}$. Our next step is to use a
cocycle approach to solve $A_{x,y}$ and $B_{x,y}$ from (4.38). Using (4.38)
and the identity $\xi(x)-\xi(z)=(\xi(x)-\xi(y))+(\xi(y)-\xi(z))$, we have that

(4.39)
$L_{x}(A_{x,y}-A_{x,z})+L_{y}(A_{y,z}-B_{x,y})+L_{z}(B_{x,z}-B_{y,z})+(G_{x-y}+G_{y-z}-G_{x-z})\equiv
0\mod J^{M}$

for all linearly independent $x,y,z\in P(O(1)^{-1})$. For convenience denote

$\Delta_{t}A_{x,y}:=A_{x+t,y+t}-A_{x,y}\text{ and
}\Delta_{t}B_{x,y}:=B_{x+t,y+t}-B_{x,y}.$

Replacing $x,y,z$ by $x+t,y+t,z+t$ in (4.39) to cancel the term
$G_{x-y}+G_{y-z}-G_{x-z}$, we deduce that

(4.40) $\begin{split}&\quad
L_{x}(\Delta_{t}A_{x,y}-\Delta_{t}A_{x,z})+L_{y}(\Delta_{t}A_{y,z}-\Delta_{t}B_{x,y})+L_{z}(\Delta_{t}B_{x,z}-\Delta_{t}B_{y,z})\\\
&\equiv-
L_{t}((A_{x+t,y+t}+A_{y+t,z+t}-A_{x+t,z+t})-(B_{x+t,y+t}+B_{y+t,z+t}-B_{x+t,z+t}))\mod
J^{M}\end{split}$

for all linearly independent $x,y,z,t\in P(O(1)^{-1})$. In particular,
$L_{x}(\Delta_{t}A_{x,y}-\Delta_{t}A_{x,z})\in J^{M}_{y,z,t}$. Since $x,y,z,t$
are linearly independent and $d\geq 11$, by Lemma 3.8, we have that

$\Delta_{t}A_{x,y}\equiv\Delta_{t}A_{x,z}\mod J^{M}_{y,z,t}.$

By Proposition 4.6, since $d\geq s+10$, there exists
$C_{x,t}\in\text{HP}_{d}(s-1)$ such that

(4.41) $\Delta_{t}A_{x,y}\equiv C_{x,t}\mod J^{M}_{y,t}$

for all linearly independent $x,y,t\in P(O(1)^{-1})$.

We solve $C_{x,t}$ before solving $A_{x,y}$. Since
$\Delta_{t}A_{x,y}+\Delta_{s}A_{x+t,y+t}=\Delta_{t+s}A_{x,y}$ for all
$x,y,t,s\in P(O(1)^{-1})$, writing $C^{\prime}_{x,y}:=C_{x,y-x}$,
$a=x,b=x+t,c=x+s+t$, it follows from (4.41) that

$C^{\prime}_{a,b}+C^{\prime}_{b,c}\equiv C^{\prime}_{a,c}\mod
J^{M}_{a-b,b-c,y}$

for all linearly independent $a,b,c,y\in P(O(1)^{-1})$. By Proposition 3.11
(setting $k=1,\dim(U_{1})=1,\dim(V)=2$ and $m=1$), since
$d\geq\max\\{s+2,11\\}$, we have

$C^{\prime}_{a,b}+C^{\prime}_{b,c}\equiv C^{\prime}_{a,c}\mod J^{M}_{a-b,b-c}$

for all linearly independent $a,b,c\in P(O(1)^{-1})$. By Proposition 4.15,
since $d\geq s+8$, there exist $\phi(x)\in\text{HP}_{d}(s-1)$ for all $x\in
P(O(1)^{-1})$ such that

$C^{\prime}_{x,y}\equiv\phi(y)-\phi(x)\mod J^{M}_{x-y}$

for all linearly independent $x,y\in P(O(1)^{-1})$.

We now use the solution of $C^{\prime}_{x,y}$ to solve $A_{x,y}$. By (4.41),

$A_{x+t,y+t}-A_{x,y}=\Delta_{t}A_{x,y}\equiv
C_{x,t}=C^{\prime}_{x,x+t}\equiv\phi(x+t)-\phi(x)\mod J^{M}_{y,t}$

for all linearly independent $x,y,t\in P(O(1)^{-1})$. Writing
$y^{\prime}=y+t$, $z=x-y$ and $A^{\prime}_{z,y}:=A_{y+z,y}-\phi(y+z)$, we have
that

$A^{\prime}_{z,y}\equiv A^{\prime}_{z,y^{\prime}}\mod J^{M}_{y,y^{\prime}}$

for all linearly independent $y,y^{\prime},z\in P(O(1)^{-1})$. By Proposition
4.6, since $d\geq s+8$, there exist $f(z)\in\text{HP}_{d}(s-1)$ for all $z\in
P(O(1)^{-1})$ such that

$A^{\prime}_{z,y}\equiv f(z)\mod J^{M}_{y}$

for all linearly independent $y,z\in P(O(1)^{-1})$. So

(4.42) $A_{x,y}\equiv\phi(x)+f(x-y)\mod J^{M}_{y}$

for all linearly independent $x,y\in P(O(1)^{-1})$.

We may solve $B_{x,y}$ is a similar way and conclude that there exist
$\psi(y)\in\text{HP}_{d}(s-1)$ for all $y\in P(O(1)^{-1})$ and
$g(z)\in\text{HP}_{d}(s-1)$ for all $z\in P(O(1)^{-1})$ such that

(4.43) $B_{x,y}\equiv\psi(y)+g(x-y)\mod J^{M}_{x}$

for all linearly independent $x,y\in P(O(1)^{-1})$.

Step 3: a description for $\phi-\psi$. We next determine the connection
between $\phi$ and $\psi$. Applying Lemma 3.8 to the term
$L_{y}(\Delta_{t}A_{y,z}-\Delta_{t}B_{x,y})$ in (4.40), we have that

$\Delta_{t}A_{y,z}\equiv\Delta_{t}B_{x,y}\mod J^{M}_{x,z,t}$

for all linearly independent $x,y,z,t\in P(O(1)^{-1})$. This implies that

$\phi(y)-\psi(y)\equiv\phi(y+t)-\psi(y+t)\mod J^{M}_{x,z,t}$

for all linearly independent $x,y,z,t\in P(O(1)^{-1})$, which implies that

$\phi(y)-\psi(y)\equiv\phi(y^{\prime})-\psi(y^{\prime})\mod
J^{M}_{x,z,y-y^{\prime}}$

for all linearly independent $x,y,y^{\prime},z\in P(O(1)^{-1})$. By
Proposition 3.11 (setting $k=1,\dim(U_{1})=1,\dim(V)=1$ and $m=2$), since
$d\geq\max\\{s+2,11\\}$, we have that

$\phi(y)-\psi(y)\equiv\phi(y^{\prime})-\psi(y^{\prime})\mod
J^{M}_{y-y^{\prime}}$

for all linearly independent $y,y^{\prime}\in P(O(1)^{-1})$.

By Proposition 4.10, since $d\geq s+7$, there exists a super polynomial
$Q\colon\text{HP}_{d}(1)\to\text{HP}_{d}(s-1)$ such that
$\phi(y)-\psi(y)\equiv Q(L_{y})\mod J^{M}$ for all linearly independent $y\in
P(O(1)^{-1})$.

We now substitute the expression of $\phi(y)-\psi(y)$ to the previous
equations. Note that

$\psi(y)+g(x-y)-\phi(y)=Q(L_{y})+g(x-y)\equiv Q(L_{x-y})+g(x-y)\mod
J^{M}_{x}.$

So replacing $g(x-y)$ by $Q(L_{x-y})+g(x-y)$ if necessary, we may assume
without loss of generality that $Q\equiv 0$ and $\phi(x)=\psi(x)$ for all
$x\in P(O(1)^{-1})$. By Proposition A.8, (4.38), (4.42) and (4.43),

$\begin{split}&\quad\xi(x)-\xi(y)\equiv L_{x}A_{x,y}-L_{y}B_{x,y}+G_{x-y}\\\
&\equiv
L_{x}\phi(x)-L_{y}\phi(y)+L_{x}f(x-y)-L_{y}g(x-y)+G_{x-y}+L_{x}L_{y}R_{x,y}\mod
J^{M}\end{split}$

for some $R_{x,y}\in\text{HP}_{d}(s-2)$ for all linearly independent $x,y\in
P(O(1)^{-1})$. Writing

(4.44) $\begin{split}\xi^{\prime}(x):=\xi(x)-L_{x}\phi(x),\end{split}$

$F=f-g$ and $G^{\prime}_{z}:=G_{z}+L_{z}f(z)$, we have that

(4.45) $\begin{split}\xi^{\prime}(x)-\xi^{\prime}(y)\equiv
L_{y}F(x-y)+G^{\prime}_{x-y}+L_{x}L_{y}R_{x,y}\mod J^{M}\end{split}$

for all linearly independent $x,y\in P(O(1)^{-1})$.

Step 4: the elimination of $G^{\prime}_{x-y}$. Next we deal with the term
$G^{\prime}_{x-y}$ by using Proposition 4.16. Note that (4.45) implies that

$\xi^{\prime}(x)-\xi^{\prime}(y)\equiv G^{\prime}_{x-y}\mod J^{M}_{y}$

for all linearly independent $x,y\in P(O(1)^{-1})$. Using the identity
$\xi^{\prime}(x)-\xi^{\prime}(z)=(\xi^{\prime}(x)-\xi^{\prime}(y))-(\xi^{\prime}(y)-\xi^{\prime}(z))$,
we have that

$G^{\prime}_{x-y}+G^{\prime}_{y-z}\equiv G^{\prime}_{x-z}\mod J^{M}_{y,z}$

for all linearly independent $x,y,z\in P(O(1)^{-1})$. Writing $a=x-y$ and
$b=y-z$, we have that

$G^{\prime}_{a}+G^{\prime}_{b}\equiv G^{\prime}_{a+b}\mod J^{M}_{b,z}$

for all linearly independent $z,a,b\in P(O(1)^{-1})$ are linearly independent.
By Proposition 3.11 (setting $k=m=\dim(U_{1})=1,\dim(V)=1$), since
$d\geq\max\\{s+2,9\\}$, we have that

$G^{\prime}_{a}+G^{\prime}_{b}\equiv G^{\prime}_{a+b}\mod J^{M}_{b}.$

Similarly, $G^{\prime}_{a}+G^{\prime}_{b}\equiv G^{\prime}_{a+b}\mod
J^{M}_{a}$ and so

$G^{\prime}_{a}+G^{\prime}_{b}\equiv G^{\prime}_{a+b}\mod J^{M}_{a}\cap
J^{M}_{b}$

for all linearly independent $a,b\in P(O(1)^{-1})$. By Proposition 4.16, since
$d\geq s+9$, there exist a super polynomial
$R\colon\text{HP}_{d}(1)\to\text{HP}_{d}(s)$ with $R(0)=0$ and a locally
linear map $T\colon P(O(1)^{-1})\to\text{HP}_{d}(s)$ such that

(4.46) $\begin{split}G^{\prime}_{a}\equiv R(L_{a})+T(a)\mod J^{M}\end{split}$

for all $a\in P(O(1)^{-1})\backslash\\{\mathbb{0}\\}$. Since $R$ is a super
polynomial with $R(0)=0$, it is not hard to see that

(4.47) $\begin{split}R(L_{a})+R(L_{b})\equiv
R(L_{a+b})+L_{a}L_{b}R^{\prime}_{a,b}\mod J^{M}\end{split}$

for some $R^{\prime}_{a,b}\in\text{HP}_{d}(s-2)$ for all
$a,b\in\mathbb{F}_{p}^{d}$.

We now substitute the expression of $G^{\prime}_{x-y}$ to the previous
equations. By (4.45), (4.46) and (4.47), writing

(4.48)
$\begin{split}\xi^{\prime\prime}(x):=\xi^{\prime}(x)-T(x)-R(L_{x}),\end{split}$

we have that

(4.49) $\begin{split}\xi^{\prime\prime}(x)-\xi^{\prime\prime}(y)\equiv
L_{y}F(x-y)+L_{x}^{2}R_{1,x,y}+L_{x}L_{y}R_{2,x,y}+L^{2}_{y}R_{3,x,y}\mod
J^{M}\end{split}$

for some $R_{1,x,y},R_{2,x,y},R_{3,x,y}\in\text{HP}_{d}(s-2)$ for all linearly
independent $x,y\in P(O(1)^{-1})$.

Step 5: completion of the proof. It follows from (4.49) that
$\xi^{\prime\prime}(x)\equiv\xi^{\prime\prime}(y)\mod J^{M}_{x,y}$ for all
linearly independent $x,y\in P(O(1)^{-1})$. Since $d\geq s+8$, by Proposition
4.6, there exists $C\in\text{HP}_{d}(s)$ such that

(4.50) $\begin{split}\xi^{\prime\prime}(x)\equiv C\mod J^{M}\end{split}$

for all $x\in P(O(1)^{-1})\backslash\\{\mathbb{0}\\}$.

Combining (4.44), (4.48) and (4.50), we have that

$\xi(x)\equiv T(x)+C+R(L_{x})+L_{x}\phi(x)\mod J^{M}$

and thus

$\xi(x)\equiv T(x)+C\mod J^{M}_{x}$

for all $x\in P(O(1)^{-1})\backslash\\{\mathbb{0}\\}$ (since $R(0)=0$).

Note that for all $x\in P(O(1)^{-1})\backslash\\{\mathbb{0}\\}$,

$\begin{split}2\xi(\mathbb{0})\equiv\xi(x)+\xi(-x)\equiv(T(x)+C)+(T(-x)+C)=2T(\mathbb{0})+2C\mod
J^{M}_{x}.\end{split}$

By Proposition 3.11, since $d\geq\max\\{s+1,7\\}$, we have

$\xi(\mathbb{0})\equiv T(\mathbb{0})+C\mod J^{M}$

and thus $\xi(x)\equiv T(x)+C\mod J^{M}_{x}$ for all $x\in P(O(1)^{-1})$. This
completes the proof of Theorem 4.3.

##  5\. Structures for sets with small density dependence numbers

In this section, we extend some important results in additive combinatorics
for shifted ideals.

###  5.1. Two notions of equivalence classes

Although $\sim$ is not an equivalence relation
$\mathbb{F}_{p}^{d}\times\mathcal{J}(M)$, it is still possible to talk about
equivalence classes in the following way:

######  Definition 5.1 (Equivalence classes).

We say that a subset $X$ of $\Gamma^{s}(M)$ is an _equivalence class_ (or a
_weak equivalence class_) if $x\sim x^{\prime}$ for all $x,x^{\prime}\in X$.
Clearly, $\pi(x)$ is a constant for all $x\in X$, and so we denote this
constant by $\pi(X)$ when there is no confusion. We say that an equivalence
class $X\subseteq\Gamma^{s}(M)$ is a _strong equivalence class_ if there
exists $u\in\Gamma^{s}_{1}(M)$ such that $u\sim x$ for all $x\in X$.

######  Example 5.2.

Assume that $M(n)=n\cdot n$. For $x\in\mathbb{F}_{p}^{d}$, let
$L_{x}\in\text{HP}_{d}(1)$ be the map given by $L_{x}(n)=x\cdot n$. Let
$e_{1},\dots,e_{d}$ be the standard unit vectors of $\mathbb{F}_{p}^{d}$. Let
$x_{1}=(\mathbb{0},J^{M}_{e_{1}})$, $x_{2}=(\mathbb{0},J^{M}_{e_{2}})$ and
$x_{3}=(\mathbb{0},J^{M}_{e_{1}+e_{2}}+L_{e_{1}})$. It is not hard to check
that $\\{x_{1},x_{2},x_{3}\\}$ is a weak equivalence class in
$\Gamma^{1}_{2}(M)$. On the other hand, suppose that there exists
$x\in\Gamma^{1}_{1}(M)$ such that $x\sim x_{i}$ for all $1\leq i\leq 3$. Since
$x\in\Gamma^{1}_{1}(M)$, we may write $x=(\mathbb{0},J^{M}+L_{y})$ for some
$y\in\mathbb{F}_{p}^{d}$. Since $x\sim x_{i}$ for all $1\leq i\leq 3$, we have
that $y,y$ and $y-e_{1}$ are scalar multiples of $e_{1},e_{2}$ and
$e_{1}+e_{2}$ respectively, which is not possible. So
$\\{x_{1},x_{2},x_{3}\\}$ is not a strong equivalence class.

######  Example 5.3.

Let the notations be the same as Example 5.2. Let
$x_{4}=(\mathbb{0},J^{M}_{e_{1}-e_{2}})$. It is not hard to see that
$\\{x_{1},x_{2},x_{4}\\}$ is a strong equivalence class since
$(\mathbb{0},J^{M})\sim x_{i}$ for all $i=1,2,4$. If we add $x_{3}$ into this
set, then it is not hard to see that $\\{x_{1},x_{2},x_{3},x_{4}\\}$ is a weak
equivalence class. However, by Example 5.2, $\\{x_{1},x_{2},x_{3},x_{4}\\}$ is
no longer a strong equivalence class.

In conclusion, Example 5.2 shows that there exists a weak equivalence class
$X$ which is not a strong equivalence class. Example 5.3 shows that there is a
strong equivalent class $X$ and some $u\in\Gamma^{s}(M)$ such that $x\sim u$
for all $x\in X$, but the set $X\cup\\{u\\}$ is no longer a strong equivalent
class. In this paper, such equivalence classes $X$ are considered as abnormal.
In fact, the following proposition shows that “generic” equivalence classes do
not have the properties mentioned above.

######  Proposition 5.4.

Let $d,k,k^{\prime}\in\mathbb{N}_{+},k\geq 2$, $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
non-degenerate quadratic form. Let $X\subseteq\Gamma^{s}_{k}(M)$ with
$\pi(X)=\\{h\\}$ for some $h\in\mathbb{F}_{p}^{d}$.

If $h=\mathbb{0}$, then

  1. (i)

if $d\geq 2k+2(s+1)(k-2)+5$ and $X$ is a weak equivalence class, then either
$X$ is a strong equivalence class or there exists a subspace $Y$ of
$\mathbb{F}_{p}^{d}$ of dimension at most $(s+k-1)(k-1)$ such that $V\cap
Y\neq\\{\mathbb{0}\\}$ for all $(\mathbb{0},J^{M}_{V}+f)\in X$.

  2. (ii)

if $d\geq 2k^{\prime}+2(s+1)(k-2)+5$ and $X$ is a strong equivalence class,
then either there exists a subspace $Y$ of $\mathbb{F}_{p}^{d}$ of dimension
at most $(s+k^{\prime}-1)(k-1)$ such that $V\cap Y\neq\\{\mathbb{0}\\}$ for
all $(\mathbb{0},J^{M}_{V}+f)\in X$, or for all
$u\in\Gamma^{s}_{k^{\prime}}(M)$ such that $u\sim a$ for all $a\in X$, we have
that $X\cup\\{u\\}$ is also a strong equivalence class.

If $h\neq\mathbb{0}$, then

  1. (i)

if $d\geq 2k+2(s+1)(k-2)+7$ and $X$ is a weak equivalence class, then either
$X$ is a strong equivalence class or there exists a subspace $Y$ of
$\mathbb{F}_{p}^{d}$ of dimension at most $(s+k)(k-1)$ and containing $h$ such
that $V\cap Y\neq\text{span}_{\mathbb{F}_{p}}\\{h\\}$ for all
$(h,J^{M}_{V}+f)\in X$.

  2. (ii)

if $d\geq 2k^{\prime}+2(s+1)(k-2)+7$ and $X$ is a strong equivalence class,
then either there exists a subspace $Y$ of $\mathbb{F}_{p}^{d}$ of dimension
at most $(s+k^{\prime})(k-1)$ and containing $h$ such that $V\cap
Y\neq\text{span}_{\mathbb{F}_{p}}\\{h\\}$ for all $(h,J^{M}_{V}+f)\in X$, or
for all $u\in\Gamma^{s}_{k^{\prime}}(M)$ such that $u\sim a$ for all $a\in X$,
we have that $X\cup\\{u\\}$ is also a strong equivalence class.

Before proving Proposition 5.4, we need the following lemma from linear
algebra:

######  Lemma 5.5.

Let $d,k,m\in\mathbb{N}_{+},k^{\prime}\in\mathbb{N}$, $p$ be a prime, $U$ be a
subspace of $\mathbb{F}_{p}^{d}$ of dimension $k^{\prime}$ (possibly the
trivial subspace), and $\mathcal{U}$ be a collection of subspaces of
$\mathbb{F}_{p}^{d}$ of dimension at most $k$ containing $U$. Then either
there exist $V_{i}\in\mathcal{U},1\leq i\leq m$ such that $V_{1},\dots,V_{m}$
are linearly independent modulo $U$, or there exists a subspace $W$ of
$\mathbb{F}_{p}^{d}$ of dimension at most $k^{\prime}+(m-1)(k-k^{\prime})$
containing $U$ such that $W\cap V\neq U$ for all $V\in\mathcal{U}$.

###### Proof.

Pick any $V_{1}\in\mathcal{U}$. Suppose that we have chosen
$V_{i}\in\mathcal{U},1\leq i\leq r$ for some $1\leq r\leq m-1$ such that
$V_{1},\dots,V_{r}$ are linearly independent modulo $U$. If for all
$V\in\mathcal{U}$, $V\cap(V_{1}\dots+V_{r})\neq U$, then we are done since
$\dim(V_{1}\dots+V_{r})=k^{\prime}+r(k-k^{\prime})\leq
k^{\prime}+(m-1)(k-k^{\prime})$. If not, then we may find
$V_{r+1}\in\mathcal{U}$ such that $V_{1},\dots,V_{r+1}$ are linearly
independent modulo $U$.

In conclusion, either we are done or there exist $V_{i}\in\mathcal{U},1\leq
i\leq m$ such that $V_{1},\dots,V_{m}$ are linearly independent modulo $U$. ∎

###### Proof of Proposition 5.4.

We first consider the case $h=\mathbb{0}$. We start with Part (i). Denote
$K:=s+k$. By Lemma 5.5, either there exists a subspace $Y$ of
$\mathbb{F}_{p}^{d}$ of dimension at most $(K-1)(k-1)$ such that $V\cap
Y\neq\\{\mathbb{0}\\}$ for all $(\mathbb{0},J^{M}_{V}+f)\in X$, or there exist
$u_{i}=(\mathbb{0},J^{M}_{V_{i}}+f_{i})\in X,1\leq i\leq K$ such that
$V_{1},\dots,V_{K}$ are linearly independent. If it is the former case then we
are done. We now assume that it is the latter case.

Obviously $(\mathbb{0},J^{M}+f_{1})\in\Gamma^{s}_{1}(M)$ is equivalent to
$u_{1}$. Suppose that for some $1\leq n\leq s$, there exists
$u\in\Gamma^{s}_{1}(M)$ such that $u\sim u_{i}$ for all $1\leq i\leq n$. We
show that there exists $u^{\prime}\in\Gamma^{s}_{1}(M)$ such that
$u^{\prime}\sim u_{i}$ for all $1\leq i\leq n+1$. Assume that
$u=(\mathbb{0},J^{M}+f)$. Then for all $1\leq i\leq m$, since $X$ is an
equivalence class, we have that $u\sim u_{i}\sim u_{n+1}$. So $f\equiv
f_{i}\equiv f_{n+1}\mod J^{M}_{V_{n+1}+V_{i}}$ and thus $f\equiv
f_{n+1}\mod\cap_{i=1}^{n}J^{M}_{V_{n+1}+V_{i}}.$ Since $V_{1},\dots,V_{n+1}$
are linearly independent, and $\pi(X)=\\{\mathbb{0}\\}$, the dimensions of
$V_{1},\dots,V_{n+1}$ are at most $k-1$. Since $d\geq 2k+2s(k-2)+5$, by Lemma
3.9 (setting $V=V_{n+1}$, $m=k-1$, $r=k-1$, and $N=n$), we have that $f\equiv