latexYou have requested package

# Exploration on Incidence Geometry and Sum-Product Phenomena

Sung-Yi Liao1

(1National Center for Theoretical Sciences, Taiwan)

###### Abstract

In additive combinatorics, Erdös-Szemerédi Conjecture is an important
conjecture. It can be applied to many fields, such as number theory, harmonic
analysis, incidence geometry, and so on. Additionally, its statement is quite
easy to understand, while it is still an open problem. In this dissertation,
we investigate the Erdös-Szemerédi Conjecture and its relationship with
several well-known results in incidence geometry, such as the Szemerédi-
Trotter Incidence Theorem. We first study these problems in the setting of
real numbers and focus on the proofs by Elekes and Solymosi on sum-product
estimates. After introducing these theorems, our main focus is the Erdös-
Szemerédi Conjecture in the setting of $\mathbb{F}_{p}$. We aim to adapt
several ingenious techniques developed for real numbers to the case of finite
fields. Finally, we obtain a result in estimating the number of bisectors over
the ring $\mathbb{Z}/p^{3}\mathbb{Z}$ with $p$ a $4n+3$ prime.

##  1 Introduction

###  1.1 General settings

We first introduce the sum set and product set as follows:

######  Definition 1.1.1 (sum set, product set).

Given a ring $(R,+,\cdot)$ and two non-empty finite subsets $A,B\subseteq R$,
define their sum set

$A+B:=\\{a+b\mid a\in A,b\in B\\}$

and their product set

$A\cdot B:=\\{a\cdot b\mid a\in A,b\in B\\}.$

It is obvious that the sizes of the sum set $A+B$ and the product set $A\cdot
B$ share the same trivial upper bound $|A||B|$ and trivial lower bound
$\max\\{|A|,|B|\\}$ if both $A$ and $B$ contain at least one non-zero-divisor
where we use $|A|$ to denote the size of the set $A$. However, if there exists
no finite subring, one expects that the sizes of the sum set or product set
are much larger than the trivial lower bound. This motivated Erdös and
Szemerédi to make their well-known conjecture in the 1980s. Before we go into
more details, we first recall the useful Landau notation and Vinogradov
notation defined as follows:

######  Definition 1.1.2 (asymptotic notations).

Throughout this article, all the quantities are nonnegative. The Landau
notation and Vinogradov notation are defined as follows:

  1. 1.

We say $f=O(g)$, or equivalently $f\ll g$, if
$\lim\limits_{x\to\infty}\frac{f(x)}{g(x)}<\infty$.

  2. 2.

We say $f=o(g)$ if $\lim\limits_{x\to\infty}\frac{f(x)}{g(x)}=0$.

  3. 3.

We say $f=\Omega(g)$, or equivalently $f\gg g$, if
$\lim\limits_{x\to\infty}\frac{g(x)}{f(x)}<\infty$.

  4. 4.

We say $f=\omega(g)$ if $\lim\limits_{x\to\infty}\frac{g(x)}{f(x)}=0$.

  5. 5.

We say $f=\Theta(g)$ if
$\lim\limits_{x\to\infty}\frac{f(x)}{g(x)}\in(0,\infty)$.

  6. 6.

We say $f\sim g$ if $\lim\limits_{x\to\infty}\frac{f(x)}{g(x)}=1$.

  7. 7.

We say $f\lesssim g$ if there is an absolute $c\in\mathbb{R}$ such that
$f(x)\ll g(x)\log^{c}(x)$.

  8. 8.

We say $f\approx g$ if $f\lesssim g$ and $g\lesssim f$.

###  1.2 Erdös-Szemerédi Conjecture

Before we state the Erdös-Szemerédi Conjecture, let us first take a look at
the following examples:

######  Example 1.2.1.

Let $R=\mathbb{R}$.

  1. 1.

Consider $A=B=\\{1,2,\dotsc,n\\}$, an arithmetic progression of length $n$.
Then, one can direct compute to see

$|A+B|=\left|\\{2,3,\dotsc,2n\\}\right|=\Theta(|A|),$

which achieves the lower bound. However, the size of its product set

$|A\cdot B|\approx|A|^{2},$

which achieves the upper bound. (This result is known as Erdös Multiplicative
Table Problem and proved by Erdös.)

  2. 2.

On the other hand, consider $A=B=\\{2^{1},\dotsc,2^{n}\\}$, a geometric
progression. We have

$|A+B|\approx|A|^{2},$

which achieves the upper bound and its product set

$|A\cdot B|=\Theta(|A|),$

which achieves the lower bound.

Based on the above examples, we can see that there are sets whose either sum-
set or product-set almost achieves the upper bound. The well-known conjecture
of Erdös and Szemerédi states that not only arithmetic progressions or
geometric progressions can have either sum-set or product-set almost attain
the upper bound but for any finite sets. More precisely, they made the
conjecture below.

######  Conjecture 1.2.2 (Erdös-Szemerédi Conjecture, [1]).

For any finite subset $A\subseteq\mathbb{Z}$, one has

$\max\\{|A+A|,|A\cdot A|\\}\gg_{\delta}{|A|}^{2-\delta}$

for any constant $\delta>0$.

In order to support their conjecture, they proved the following theorem.

######  Theorem 1.2.3 (Theorem 1, [1]).

Given any finite subset $A\subseteq\mathbb{Z}$, we have

${|A|}^{1+\epsilon_{1}}\ll\max\\{|A+A|,|A\cdot
A|\\}\ll{|A|}^{2}\exp\left(-\epsilon_{2}\log|A|\log\log|A|\right)$

for some absolute constants $\epsilon_{1},\epsilon_{2}>0$.

Their theorem stimulated many subsequent works that either improved the
exponents or generalized it to other settings such as $\mathbb{F}_{p}$. The
conjecture is also widely believed to be true in integers, real numbers,
complex numbers, fields, and even arbitrary rings [2]. This conjecture
motivates numerous priceless research in various areas and has been extremely
important in various research areas. After decades, the conjecture has been
connected to other areas, such as Incidence Geometry [3], Harmonic Analysis
[4], Number Theory, etc.

##  2 Milestones in Real Number

In this section, we discuss the Sum-Product Phenomenon in real numbers. Recall
that the Erdös-Szemerédi Conjecture in real number is:

> For any finite subset $A\subseteq\mathbb{R}$, one has $\max\\{|A+A|,|A\cdot
> A|\\}\gg_{\delta}{|A|}^{2-\delta}$ for any $\delta>0$.

The conjecture is still open, and there have been several important results
that are shown in the following table on the next page:

Authors | Exponential Part
---|---
Erdös and Szemerédi (1983, [1]) |  $1+\epsilon$ for some $\epsilon>0$
Elekes (1997, [5]) | $1+\frac{1}{4}$
Solymosi (2009, [6]) |  $1+\frac{1}{3}-\delta$ for any $\delta>0$
Rudnev and Stevens (2020, [7]) |  $1+\frac{1}{3}+\frac{2}{1167}-\delta$ for any $\delta>0$

Let us first introduce the beautiful results of Elekes and Solymosi, which are
the two most crucial results overall. To start with, we introduce an important
notation in Incidence Geometry: Given a set of points
$\mathcal{P}\in\mathbb{R}^{2}$ and a collection $\mathcal{L}$ of lines in
$\mathbb{R}^{2}$, define their incidence number

$\mathcal{I}(\mathcal{P},\mathcal{L}):=\left|\left\\{(p,l)\in\mathcal{P}\times\mathcal{L}\mid
p\in l\right\\}\right|.$

###  2.1 Elekes’ result

We first recall the Szemerédi-Trotter Incidence Theorem, an extremely
important theorem in Incidence Geometry (Its proof will be provided in the
Appendix A. for the sake of self-containment).

######  Theorem 2.1.1 (Szemerédi-Trotter Incidence Theorem, [8]).

On Euclidean plane $\mathbb{R}^{2}$, given a point set $\mathcal{P}$ and a
line set $\mathcal{L}$, then the number of their incidences

$\mathcal{I}(\mathcal{P},\mathcal{L})=O\left({|\mathcal{P}|}^{\frac{2}{3}}{|\mathcal{L}|}^{\frac{2}{3}}+|\mathcal{P}|+|\mathcal{L}|\right).$

It is important to remark that the result is sharp, meaning there exists a
configuration of points $P$ and lines $\mathcal{L}$ whose incidence is
$\sim|P|^{2/3}|\mathcal{L}|^{2/3}$. In 1997, Elekes brilliantly applied the
result of Szemerédi-Trotter Theorem to the Sum-Product problem and obtained
the following theorem:

######  Theorem 2.1.2 (Elekes, [5]).

Given any finite subset $A\subseteq\mathbb{R}$,

$\max\\{|A+A|,|A\cdot A|\\}\gg{|A|}^{1+\frac{1}{4}}.$

###### Proof.

Consider the point set $\mathcal{P}=(A+A)\times(A\cdot A)$ and the line set

$\mathcal{L}=\\{l\mid l:y=a_{1}(x-a_{2}),a_{1},a_{2}\in A\\}.$

For any lines $l:y=a(x-a^{\prime})\in\mathcal{L}$ and $a^{\prime\prime}\in A$,
$(a^{\prime}+a^{\prime\prime},aa^{\prime\prime})\in\mathcal{P}$, so for every
line in $\mathcal{L}$, there are at least $|A|$ points in $\mathcal{P}$ lie on
it. In other words, by Theorem 2.1.1, we have

$\begin{split}&{|A|}^{3}=|A||\mathcal{L}|\leq\mathcal{I}(\mathcal{P},\mathcal{L})\ll{|A+A|}^{\frac{2}{3}}{|A\cdot
A|}^{\frac{2}{3}}{|A|}^{\frac{4}{3}}+|A+A||A\cdot A|+{|A|}^{2}\\\
&\Rightarrow{|A|}^{3}\ll\max\left\\{{|A+A|}^{\frac{2}{3}}{|A\cdot
A|}^{\frac{2}{3}}{|A|}^{\frac{4}{3}},|A+A||A\cdot A|\right\\}\\\
&\Rightarrow{|A|}^{\frac{5}{3}}\ll{|A+A|}^{\frac{2}{3}}{|A\cdot
A|}^{\frac{2}{3}}\\\
&\Rightarrow{|A|}^{\frac{5}{4}}\ll{|A+A|}^{\frac{1}{2}}{|A\cdot
A|}^{\frac{1}{2}}\leq\max\\{|A+A|,|A\cdot A|\\}.\\\ \end{split}$

This completes the proof. ∎

###  2.2 Solymosi’s result

To demonstrate Solymosi’s result, we need the following definition:

######  Definition 2.2.1 (additive energy, multiplicative energy).

Given two sets $A,B$, their additive energy is defined as

$E^{+}(A,B):=|\\{(a_{1},a_{2},b_{1},b_{2})\in A\times A\times B\times B\mid
a_{1}+b_{1}=a_{2}+b_{2}\\}|$ (1)

and their multiplicative energy is defined as

$E^{\times}(A,B):=|\\{(a_{1},a_{2},b_{1},b_{2})\in A\times A\times B\times
B\mid a_{1}b_{1}=a_{2}b_{2}\\}|.$

Especially, if $A=B$, define $E^{+}(A):=E^{+}(A,A)$ and
$E^{\times}(A):=E^{\times}(A,A)$.

Note that the additive energy (resp. multiplicative energy) indicates how many
redundant additive pairs (resp. multiplicative pairs) the sets have. In other
words, a set with large additive energy (resp. multiplicative energy) will
have a small sum set (resp. product set). This makes these energy estimates
useful for estimating sum and product sets. To be more specific, define

$r_{A+A}(z):=|\\{(a_{1},a_{2})\in A\times A\mid z=a_{1}+a_{2}\\}|.$

Then, by Cauchy-Schwarz inequality, we can see that

${|A|}^{4}={\left(\sum_{z\in A+A}r_{A+A}(z)\right)}^{2}\leq|A+A|\sum_{z\in
A+A}{r_{A+A}(z)}^{2}=|A+A|E^{+}(A).$ (2)

Therefore, we can obtain a lower bound of the sum set by an upper bound of
additive energy.

######  Theorem 2.2.2 (Solymosi, [6]).

Given any finite subset $A\subseteq\mathbb{R}$,

$\max\\{|A+A|,|A\cdot A|\\}\gg{|A|}^{1+\frac{1}{3}}.$

###### Proof.

Without loss of generality, we may assume that every element in $A$ is
positive. Let

$r_{A/A}(x):=\\{(a_{1},a_{2})\in A\times A\mid x=a_{1}/a_{2}\\},xA:=\\{xa\mid
a\in A\\}$

for any element $x$ and

$A/A:=\\{a/a^{\prime}\mid a,a^{\prime}\in A\\}.$

First, we have

$\begin{split}E^{\times}(A)&=\sum_{x\in A/A}{r_{A/A}(x)}^{2}=\sum_{x\in
A/A}{|xA\cap A|}^{2}\\\
&=\sum_{i=1}^{\lceil\log_{2}|A|\rceil}\sum_{\begin{subarray}{c}x:2^{i-1}\leq|xA\cap
A|<2^{i}\end{subarray}}{|xA\cap A|}^{2}.\end{split}$

Then, by the pigeonhole principle, there is an index $1\leq
i_{0}\leq\lceil\log_{2}|A|\rceil$ such that

$\frac{E^{\times}(A)}{\lceil\log_{2}|A|\rceil}\leq\sum_{x:2^{i_{0}-1}\leq|xA\cap
A|<2^{i_{0}}}{|xA\cap A|}^{2}.$ (3)

Let $D:=\\{x\mid 2^{i_{0}-1}\leq|xA\cap
A|<2^{i_{0}}\\}=\\{s_{1},\dotsc,s_{n}\\}$ with $|D|=n$ and
$s_{1}<\dotsb<s_{n}$. Set the line $l_{i}:y=s_{i}x$ for $i=1,\dotsc,n$ and
$l_{n+1}:x=a_{1}$ where $a_{1}$ is the smallest element in $A$. For
$i=1,\dotsc,n$, consider the point sets

$P_{i}:=\big{(}l_{i}\cap(A\times A)\big{)}+\big{(}l_{i+1}\cap(A\times
A)\big{)}\text{ and }P:=\bigsqcup_{i=1}^{n}P_{i}\subseteq(A\times A)+(A\times
A)$

where the addition symbol means vector addition and $A\times A$ means the
Cartesian product.

Next, since $|l_{i}\cap(A\times A)|\geq 2^{i_{0}-1}$,

$|P|=\sum_{i=1}^{n}|P_{i}|\geq n2^{i_{0}}.$

On the other hand,

$|P|\leq|(A+A)\times(A+A)|={|A+A|}^{2}\Rightarrow n2^{i_{0}}\leq{|A+A|}^{2}.$

Together with Equation (3), we get

$\frac{E^{\times}(A)}{\lceil\log_{2}|A|\rceil}\leq n2^{i_{0}}\leq{|A+A|}^{2}.$

Combining it with the multiplicative version of Equation (2), we get

$\frac{{|A|}^{4}}{|A\cdot
A|\lceil\log_{2}|A|\rceil}\leq\frac{E^{\times}(A)}{\lceil\log_{2}|A|\rceil}\leq{|A+A|}^{2}.$

Hence,

$\frac{{|A|}^{\frac{4}{3}}}{{\lceil\log_{2}|A|\rceil}^{\frac{1}{3}}}\leq{|A+A|}^{\frac{2}{3}}{|A\cdot
A|}^{\frac{1}{3}}\leq\max\\{|A+A|,|A\cdot A|\\},$

which completes this proof. ∎

Note that in the above proof, we use the pigeonhole principle to choose a
suitable index $i_{0}$ that satisfies Equation (3). This skill, called the
“dyadic argument,” is widely used in the proofs of many results of the Sum-
Product Phenomena [9].

##  3 Connection between Incidence Geometry and Sum-Product Phenomena in
$\mathbb{F}_{p}$

In this section, we will display several useful Incidence Geometry results in
$\mathbb{F}_{p}$ and especially focus on those that have strong connections
with Sum-Product estimates. In fact, the known result by Bourgain, Katz, and
Tao has established the first non-trivial bound for the point-line incidences
in the setting of $\mathbb{F}_{p}$, which was an application of their sum-
product estimate. However, there have been many improvements since then, which
we state below.

###  3.1 Szemerédi-Trotter type theorem

We start with a familiar example that we mentioned in Section 2.1. In the
proof of Theorem 2.1.2, the most important lemma is Theorem 2.1.1 (Szemerédi-
Trotter Theorem). Therefore, obtaining Szemerédi-Trotter type theorem in
$\mathbb{F}_{p}$, where $p$ is a prime, can also provide a non-trivial bound
for Erdös-Szemerédi Conjecture. Sophie Stevens and Frank De Zeeuw obtain an
explicit result as follows [10]. (Proof of the following theorem will be
provided in Appendix for the sake of self-containment.)

######  Theorem 3.1.1 (Szemerédi-Trotter type Theorem in $\mathbb{F}_{p}$,
[10]).

On $\mathbb{F}_{p}^{2}$ where $p$ is a prime, given a point set
$\mathcal{P}=A\times B$ and a line set $\mathcal{L}$ with

$|A|\leq|B|,|A|{|B|}^{2}\leq{|\mathcal{L}|}^{3}\text{, and
}|A||\mathcal{L}|\ll p^{2}$

then the number of their incidences

$\mathcal{I}(A\times
B,\mathcal{L})=O\left({|A|}^{\frac{3}{4}}{|B|}^{\frac{1}{2}}{|\mathcal{L}|}^{\frac{3}{4}}+|\mathcal{L}|\right).$

With this theorem, we can deduce the following theorem via an argument similar
to the proof of Theorem 2.1.2.

######  Corollary 3.1.2 (Corollary 9, [10]).

Given any subset $A\subseteq\mathbb{F}_{p}$ with $|A|\ll p^{\frac{2}{3}}$,

$\max\\{|A+A|,|A\cdot A|\\}\gg{|A|}^{1+\frac{1}{5}}.$

###### Proof.

For a subset $A$, divide it into two cases:

  1. 1.

If $|A+A|\leq|A\cdot A|$, then set

$\mathcal{L}:=\\{l:y=a(x-a^{\prime})\mid a,a^{\prime}\in
A\\},A^{\prime}=A+A\text{, and }B^{\prime}=A\cdot A.$

We will find that $A^{\prime},B^{\prime}$, and $\mathcal{L}$ satisfy the
assumption of Theorem 3.1.1. Additionally, for any line $l:y=a(x-a^{\prime})$
in $\mathcal{L}$ and $a^{\prime\prime}\in A$,

$(a^{\prime}+a^{\prime\prime},aa^{\prime\prime})\in(A^{\prime}\times
B^{\prime})\cap l.$

In other words, by Theorem 3.1.1,

$\begin{split}&{|A|}^{3}=|A||\mathcal{L}|\leq I(A^{\prime}\times
B^{\prime},\mathcal{L})\ll{|A+A|}^{\frac{3}{4}}{|A\cdot
A|}^{\frac{1}{2}}{|A|}^{\frac{3}{2}}+{|A|}^{2}\\\
&\Rightarrow{|A|}^{6}\ll{|A+A|}^{3}{|A\cdot A|}^{2}\\\
&\Rightarrow{|A|}^{1+\frac{1}{5}}\ll\max\\{|A+A|,|A\cdot A|\\}.\end{split}$

  2. 2.

On the other hand, if $|A+A|>|A\cdot A|$, then set

$\mathcal{L}:=\\{l:a(y-a^{\prime})=x\mid a,a^{\prime}\in
A\\},A^{\prime}=A\cdot A\text{, and }B^{\prime}=A+A.$

We can see that $\mathcal{L},A^{\prime},B^{\prime}$ satisfy the assumptions of
Theorem 3.1.1. Moreover, for any line $l:a(y-a^{\prime})=x$ in $\mathcal{L}$
and $a^{\prime\prime}\in A$,

$(aa^{\prime\prime},a^{\prime}+a^{\prime\prime})\in(A^{\prime}\times
B^{\prime})\cap l.$

That is,

$\begin{split}&{|A|}^{3}=|A||\mathcal{L}|\leq\mathcal{I}(A^{\prime}\times
B^{\prime},\mathcal{L})\ll{|A\cdot
A|}^{\frac{3}{4}}{|A+A|}^{\frac{1}{2}}{|A|}^{\frac{3}{2}}+{|A|}^{2}\\\
&\Rightarrow{|A|}^{6}\ll{|A\cdot A|}^{3}{|A+A|}^{2}\\\
&\Rightarrow{|A|}^{1+\frac{1}{5}}\ll\max\\{|A+A|,|A\cdot A|\\}.\end{split}$

To sum up, in both cases, our statement holds. ∎

######  Corollary 3.1.3.

In the above proof, we can see that

${|A|}^{6}\ll\min\\{{|A+A|}^{3}{|A\cdot A|}^{2},{|A\cdot
A|}^{3}{|A+A|}^{2}\\}.$

Thus, in the extremal cases, we have the following bounds:

  1. 1.

If $|A+A|=\Theta(|A|)$, then $|A\cdot A|\gg{|A\cdot A|}^{1+\frac{1}{2}}$.

  2. 2.

If $|A\cdot A|=\Theta(|A|)$, then $|A+A|\gg{|A+A|}^{1+\frac{1}{2}}$.

###  3.2 Estimation of a special kind of energy

In this part, we will focus on the estimation of a special kind of energy,
which is first considered in [11]. After the estimation, we will see that this
energy will provide another brilliant bound for Erdös-Szemerédi Conjecture.

######  Definition 3.2.1 (variant-slope set, $r_{Q}$, restricted variant-slope
energy).

Let $Z,A_{1},A_{2}$ be subsets of $\mathbb{F}_{p}$. Define variant-slope set

$Q:=(A_{1}+A_{2})/(A_{1}+A_{2})=\left\\{\frac{a_{1}+a_{2}}{a_{1}^{\prime}+a_{2}^{\prime}}\,\middle|\,a_{1},a_{1}^{\prime}\in
A_{1},a_{2},a_{2}^{\prime}\in A_{2}\right\\},$

a function

$r_{Q}(z):=\left\\{(a_{1},a_{1}^{\prime},a_{2},a_{2}^{\prime})\in A_{1}\times
A_{1}\times A_{2}\times
A_{2}\,\middle|\,z=\frac{a_{1}+a_{2}}{a_{1}^{\prime}+a_{2}^{\prime}}\right\\},$

and the restricted variant-slope energy

$\begin{split}R(Z,A_{1},A_{2}):=&\sum_{z\in Z}{r_{Q}(z)}^{2}\\\ =&\text{ the
number of solutions to
}``z=\frac{a_{1,1}+a_{2,1}}{a_{1,2}+a_{2,2}}=\frac{a_{1,3}+a_{2,3}}{a_{1,4}+a_{2,4}}"\\\
&\text{ where }z\in Z,a_{i,j}\in A_{i}\text{ for all
}i=1,2,j=1,2,3,4.\end{split}$

Note that subtractive energy, defined as

$E^{-}(A):=\\{a_{1},a_{2},a_{3},a_{4}\in A\times A\times A\times A\mid
a_{1}-a_{2}=a_{3}-a_{4}\\},$

is as same as additive energy, so a subtraction acts similar way as an
addition from the perspective of energy. Also, notice that the collection of
slopes of lines passing both $A_{1}\times A_{1}$ and $A_{2}\times A_{2}$ is

$\frac{A_{1}-A_{2}}{A_{1}-A_{2}}=\left\\{\frac{a_{1}-a_{2}}{a_{1}^{\prime}-a_{2}^{\prime}}\,\middle|\,a_{1},a_{1}^{\prime}\in
A_{1},a_{2},a_{2}^{\prime}\in A_{2}\right\\},$

which is a dual version of $Q=(A_{1}+A_{2})/(A_{1}+A_{2})$. In other words,
$Q$ is the collection of variant slopes from the energy’s point of view.
Furthermore, compared to Equation (1), when we take
$Z=(A_{1}-A_{2})/(A_{1}-A_{2})$ or $Z=\mathbb{F}_{p}$, the definition of
$R(Z,A_{1},A_{2})$ is in energy form. For general $Z$, since the value of
variant-slope is restricted in $Z$, we call $R(Z,A_{1},A_{2})$ restricted
variant-slope energy, and it gives us a non-trivial bound for Erdös-Szemerédi
Conjecture in $\mathbb{F}_{p}$.

First, without loss of generality, assume $|A_{1}|\leq|A_{2}|$. Then, there is
a trivial upper bound

$R(Z,A_{1},A_{2})\leq
R(\mathbb{F}_{p},A_{1},A_{2})\leq{|A_{1}|}^{4}{|A_{2}|}^{3}.$

Next, we want to improve the upper bound of $R(Z,A_{1},A_{2})$. Boqing Xue
(2021, [13]) solved a similar case in the real number for this question.
Following the pace of Xue, Dung (2022, [12]) proved the following two upper
bounds in $\mathbb{F}_{p}$:

######  Lemma 3.2.2 ([12]).

Let $Z,A_{1},A_{2}\subseteq\mathbb{F}_{p}$ with
$|A_{1}|\leq|A_{2}|,|Z|\leq{|A_{1}|}^{2}$, and ${|A_{1}|}^{3}\ll p^{2}$. Then,

$\sum_{z\in
Z}r_{Q}(z)\lesssim{|Z|}^{\frac{1}{2}}{|A_{1}|}^{\frac{33}{16}}{|A_{2}|}^{\frac{5}{4}}.$
(4)

Additionally, we have

$R(Z,A_{1},A_{2})\lesssim{|A_{1}|}^{\frac{33}{8}}{|A_{2}|}^{\frac{5}{2}}.$ (5)

###### Proof.

To prove this claim, note that

$\begin{split}&\sum_{z\in Z}r_{Q}(z)\\\ &=\sum_{z\in
Z}\sum_{y\in\mathbb{F}_{p}}\left|\left\\{(a_{1},a_{1}^{\prime},a_{2},a_{2}^{\prime})\,\middle|\,a_{1}-a_{1}^{\prime}z=a_{2}^{\prime}z-a_{2}=y,a_{i},a_{i}^{\prime}\in
A_{i}\right\\}\right|\\\
&=\sum_{(z,y)\in\mathcal{P}}r_{1}(z,y)r_{2}(z,y)\end{split}$ (6)

where

$\mathcal{P}:=\\{(z,y)\mid z\in Z,y\in(A_{1}-zA_{1})\cap(A_{2}-zA_{2})\\},$
$r_{1}(z,y):=\left|\left\\{(a,a^{\prime})\in A_{1}\times A_{1}\mid
a-a^{\prime}z=y\right\\}\right|,$

and

$r_{2}(z,y):=\left|\left\\{(a,a^{\prime})\in A_{2}\times A_{2}\mid
a^{\prime}z-a=y\right\\}\right|.$

Next, we split the summation in Equation (6) into four parts
$S_{1,1},S_{2,1},S_{2,2}$, and $S_{1,2}$ with

$S_{j_{1},j_{2}}:=\sum_{\begin{subarray}{c}(z,y)\in\mathcal{P}\\\
r_{1}(z,y)\in I_{j_{1}}\\\ r_{2}(z,y)\in
I_{j_{2}}\end{subarray}}r_{1}(z,y)r_{2}(z,y)$

where $j_{1},j_{2}\in\\{1,2\\}$ and $I_{1}=\\{1\\},I_{2}=\\{2,3,\dotsc\\}$.
Now, we will bound $S_{1,1},S_{2,1},S_{2,2}$, and $S_{1,2}$, separately:

  1. 1.

For $S_{1,1}$, we know that

$S_{1,1}\leq|\mathcal{P}|\leq|Z|{|A_{1}|}^{2}.$ (7)

  2. 2.

For $S_{2,1}$, we obtain

$\begin{split}S_{2,1}&\leq\sum_{(z,y)\in\mathcal{P}}r_{1}(z,y)\leq|\\{(z,y,a_{1},a_{1}^{\prime})\in
Z\times\mathbb{F}_{p}\mid a_{1}-a_{1}^{\prime}z=y\\}|\\\
&=|Z|{|A_{1}|}^{2}.\end{split}$ (8)

  3. 3.

For $S_{2,2}$, applying Hölder inequality several times, we see that

$\begin{split}S_{2,2}&=\sum_{\begin{subarray}{c}(z,y)\in\mathcal{P}\\\
r_{1}(z,y),r_{2}(z,y)\geq 2\end{subarray}}r_{1}(z,y)r_{2}(z,y)\\\
&\leq{\left(\sum_{\begin{subarray}{c}(z,y)\in\mathcal{P}\\\
r_{1}(z,y),r_{2}(z,y)\geq
2\end{subarray}}{r_{1}(z,y)}^{\frac{4}{3}}\right)}^{\frac{3}{4}}{\left(\sum_{\begin{subarray}{c}(z,y)\in\mathcal{P}\\\
r_{2}(z,y)\geq 2\end{subarray}}{r_{2}(z,y)}^{4}\right)}^{\frac{1}{4}}\\\
&\leq{\left(\sum_{(z,y)\in\mathcal{P}}r_{1}(z,y)\right)}^{\frac{1}{2}}{\left(\sum_{(z,y)\in\mathcal{P}}{r_{1}(z,y)}^{2}\right)}^{\frac{1}{4}}{\left(\sum_{(z,y)\in\mathcal{P}}{r_{2}(z,y)}^{4}\right)}^{\frac{1}{4}}\end{split}$
(9)

Next, we separately estimate these three parts:

    1. (a)

For the first part, we have

$\sum_{(z,y)\in\mathcal{P}}r_{1}(z,y)\leq|Z|{|A_{1}|}^{2}.$ (10)

    2. (b)

Secondly, for $a\in A_{1}$, we define

$r_{1,a}(z):=\left|\left\\{(a_{1},a_{1}^{\prime},a_{1}^{\prime\prime})\in
A\times A\times
A\,\middle|\,a_{1}^{\prime\prime}-a_{1}^{\prime}=z(a_{1}-a)\right\\}\right|.$

Then,

$\sum_{y\in\mathbb{F}_{p}}{r_{1}(z,y)}^{2}=\sum_{a\in A_{1}}r_{1,a}(z).$

According to the relation between $|A_{1}|$ and $|Z|$, divide it into two
cases:

      1. i.

Assume $|A_{1}|\leq|Z|$:

For a fixed $a\in A_{1}$, let $\mathcal{L}_{a}$ be the collection of lines of
the form $l:a_{1}^{\prime}-x=y(a-a_{1})$ where $(a_{1},a_{1}^{\prime})\in
A_{1}\times A_{1}$. Set $A:=A_{1},B:=Z,\mathcal{L}:=\mathcal{L}_{a}$ and
notice that $A,B,\mathcal{L}_{a}$ satisfy the assumptions of Theorem 3.1.1.
Thus,

$\begin{split}\sum_{(z,y)\in\mathcal{P}}{r_{1}(z,y)}^{2}&=\sum_{z\in
Z}\sum_{a\in A_{1}}r_{1,a}(z)\leq\sum_{a\in A_{1}}\mathcal{I}(A_{1}\times
Z,\mathcal{L}_{a})\\\ &\ll\sum_{a\in
A_{1}}{|A_{1}|}^{\frac{3}{4}}{|Z|}^{\frac{1}{2}}{|A_{1}|}^{\frac{3}{2}}+{|A_{1}|}^{2}\\\
&\ll{|Z|}^{\frac{1}{2}}{|A_{1}|}^{\frac{13}{4}}.\end{split}$ (11)

      2. ii.

On the other hand, assume $|A_{1}|\geq|Z|$:

The proving technique is similar to the above. But this time, define
$\mathcal{L}_{a}$ as the family of lines in the form
$l:a_{1}^{\prime}-y=x(a_{1}-a)$ where $a_{1},a_{1}^{\prime}\in A_{1}$ and set
$A:=Z,B:=A_{1},\mathcal{L}:=\mathcal{L}_{a}$. Applying Theorem 3.1.1, we
obtain

$\begin{split}\sum_{(z,y)\in\mathcal{P}}{r_{1}(z,y)}^{2}&\leq\sum_{z\in
Z}\sum_{a\in A_{1}}r_{1,a}(z)\leq\sum_{a\in A_{1}}\mathcal{I}(Z\times
A_{1},\mathcal{L}_{a})\\\ &\ll\sum_{a\in
A_{1}}{|Z|}^{\frac{3}{4}}{|A_{1}|}^{\frac{1}{2}}{|A_{1}|}^{\frac{3}{2}}+{|A_{1}|}^{2}\\\
&\ll{|Z|}^{\frac{3}{4}}{|A_{1}|}^{3}\leq{|Z|}^{\frac{1}{2}}{|A_{1}|}^{\frac{13}{4}}.\end{split}$
(12)

Hence, by Equation (11) and (12), we have

$\sum_{(z,y)\in\mathcal{P}}{r_{1}(z,y)}^{2}\ll{|Z|}^{\frac{1}{2}}{|A_{1}|}^{\frac{13}{4}}.$
(13)

    3. (c)

As for the last part, let
$\mathcal{L}=\\{l_{z_{0},y_{0}}:y=z_{0}x+y_{1}\mid(z_{0},y_{0})\in\mathcal{P}\\}$.
For $2\leq k\leq|A_{i}|$, let $\mathcal{L}_{i,k}$ be the set of lines in
$\mathcal{L}$ that contains at least $k$ points in $A_{i}\times A_{i}$. Using
Theorem 3.1.1, we obtain

$\begin{split}&k|\mathcal{L}_{i,k}|\leq\mathcal{I}(A_{i}\times
A_{i},\mathcal{L})\ll{|A_{i}|}^{\frac{3}{4}}{|A_{i}|}^{\frac{1}{2}}{|\mathcal{L}_{i,k}|}^{\frac{3}{4}}+|\mathcal{L}_{i,k}|\\\
&\Rightarrow|\mathcal{L}_{i,k}|\ll\frac{{|A_{i}|}^{5}}{k^{4}}.\end{split}$

Thus, by the above estimate, we get

$\begin{split}\sum_{\begin{subarray}{c}(z,y)\in\mathcal{P}\\\ r_{2}(z,y)\geq
2\end{subarray}}{r_{2}(z,y)}^{4}&=\sum_{2\leq
k\leq|A_{2}|}k^{4}\left|\left\\{(z,y)\in\mathcal{P}\mid
r_{2}(z,y)=k\right\\}\right|\\\ &\ll\sum_{2\leq
k\leq|A_{2}|}k^{3}|\mathcal{L}_{2,k}|\ll\sum_{2\leq
k\leq|A_{2}|}k^{-1}{|A_{2}|}^{5}\\\ &\lesssim{|A_{2}|}^{5}.\end{split}$ (14)

Combining Equation (9), (10),(13), and (14), we know that

$S_{2,2}\lesssim{\left(|Z|{|A_{1}|}^{2}\right)}^{\frac{1}{2}}{\left({|Z|}^{\frac{1}{2}}{|A_{1}|}^{\frac{13}{4}}\right)}^{\frac{1}{4}}{\left({|A_{2}|}^{5}\right)}^{\frac{1}{4}}={|Z|}^{\frac{5}{8}}{|A_{1}|}^{\frac{29}{16}}{|A_{2}|}^{\frac{5}{4}}.$
(15)

  4. 4.

For $S_{1,2}$, applying Cauchy-Schwarz inequality twice and Equation (14), we
get

$\begin{split}S_{1,2}&\leq\sum_{\begin{subarray}{c}(z,y)\in\mathcal{P}\\\
r_{2}(z,y)\geq
2\end{subarray}}r_{2}(z,y)\leq{|\mathcal{P}|}^{\frac{1}{2}}{\left(\sum_{\begin{subarray}{c}(z,y)\in\mathcal{P}\\\
r_{2}(z,y)\geq 2\end{subarray}}{r_{2}(z,y)}^{2}\right)}^{\frac{1}{2}}\\\
&\leq{|\mathcal{P}|}^{\frac{3}{4}}{\left(\sum_{\begin{subarray}{c}(z,y)\in\mathcal{P}\\\
r_{2}(z,y)\geq
2\end{subarray}}{r_{2}(z,y)}^{4}\right)}^{\frac{1}{4}}\lesssim{|Z|}^{\frac{3}{4}}{|A_{1}|}^{\frac{3}{2}}{|A_{2}|}^{\frac{5}{4}}.\end{split}$
(16)

By the estimate of Equation (7), (8), (15), and (16), we get

$\begin{split}\sum_{z\in Z}r_{Q}(z)&=S_{1,1}+S_{1,2}+S_{2,1}+S_{2,2}\\\
&\lesssim|Z|{|A_{1}|}^{2}+|Z|{|A_{1}|}^{2}+{|Z|}^{\frac{5}{8}}{|A_{1}|}^{\frac{29}{16}}{|A_{2}|}^{\frac{5}{4}}+{|Z|}^{\frac{3}{4}}{|A_{1}|}^{\frac{3}{2}}{|A_{2}|}^{\frac{5}{4}}\\\
&\lesssim{|Z|}^{\frac{5}{8}}{|A_{1}|}^{\frac{29}{16}}{|A_{2}|}^{\frac{5}{4}}\lesssim{|Z|}^{\frac{1}{2}}{|A_{1}|}^{\frac{33}{16}}{|A_{2}|}^{\frac{5}{4}}\end{split}$
(17)

This completes the proof of Equation (4).

Next, to prove Equation (5), define

$Z_{t}:=\\{z\in Z\mid r_{Q}(z)\geq t\\}\text{ for any }t\geq 1.$

Note that

$|Z_{t}|\leq|Z|\leq{|A_{1}|}^{2}.$

Replacing $Z$ with $Z_{t}$ and applying (17), we have

$t|Z_{t}|\leq\sum_{z\in
Z_{t}}r_{Q}(z)\ll{|Z_{t}|}^{\frac{1}{2}}{|A_{1}|}^{\frac{33}{16}}{|A_{2}|}^{\frac{5}{4}}.$

That is,

$|Z_{t}|\ll\frac{{|A_{1}|}^{\frac{33}{8}}{|A_{2}|}^{\frac{5}{2}}}{t^{2}}.$

As a result,

$\begin{split}R(Z,A_{1},A_{2})&=\sum_{z\in
Z}{r_{Q}(z)}^{2}=\sum_{t\leq{|A_{1}|}^{2}|A_{2}|}t^{2}|\\{z\mid
r_{Q}(z)=t\\}|\\\
&\ll\sum_{t\leq{|A_{1}|}^{2}|A_{2}|}t|Z_{t}|\ll\sum_{t\leq{|A_{1}|}^{2}|A_{2}|}t^{-1}{|A_{1}|}^{\frac{33}{8}}{|A_{2}|}^{\frac{5}{4}}\\\
&\lesssim{|A_{1}|}^{\frac{33}{8}}{|A_{2}|}^{\frac{5}{4}},\end{split}$

which completes the proof of Equation (5). ∎

With Lemma 3.2.2, we can start to estimate the relation between the sum set
and the product set. The following results are also motivated by [11],[10],
and [13]. To be more specific, Xue studied Erdös-Szemerédi Conjecture in the
real number while Stevens and De Zeeuw proved several useful Incidence
Geometry results in arbitrary fields. Thus, we combine their works to obtain
Proposition 3.2.4 and Theorem 3.2.9, which are the $\mathbb{F}_{p}$-version of
Proposition 3.2 and Theorem 1.6 in [13].

######  Definition 3.2.3 ($n$th-order energy).

Previously, the energy we considered, which is called second-order energy, is
equal to

$\begin{split}E^{+}(A,B)&:=\left|\left\\{(a,a^{\prime},b,b^{\prime})\in
A\times A\times B\times B\mid a-a-b=a^{\prime}-b^{\prime}\right\\}\right|\\\
&=\sum_{z\in A-B}{r_{A-B}(z)}^{2}\end{split}$

where $r_{A-B}(z):=\left|\\{(a,b)\in A\times B\mid z=a-b\\}\right|$. Now, we
generalize this concept into $n$th-order energy, which is defined as follows:

$\begin{split}E_{n}^{+}(A,B)&:=\left|\left\\{(a_{1},\dotsc,a_{n},b_{1},\dotsc,b_{n})\in
A^{n}\times B^{n}\mid a_{1}-b_{1}=\dotsb=a_{n}-b_{n}\right\\}\right|\\\
&=\sum_{z\in A-B}{r_{A-B}(z)}^{n}.\end{split}$

######  Proposition 3.2.4.

Let $A,B\subseteq\mathbb{F}_{p}$. Suppose that $|A|\lesssim|B|\ll
p^{\frac{2}{5}}$. Then,

${E_{3}^{+}(A,B)}^{\frac{4}{3}}{|B|}^{-4}\lesssim|A\cdot A|.$

To prove this proposition, we will need the following Lemmas:

######  Lemma 3.2.5.

Let $A,B\subseteq\mathbb{F}_{p}$ with $|A|\leq|B|\ll p^{\frac{2}{5}}$ and

$\mathcal{L}:=\\{l_{a,b}:y=ax+b\mid(a,b)\in A\times B\\}.$

Then, for any $\mathcal{P}\subseteq\mathbb{F}_{p}^{2}$ with
$|A|{|B|}^{2}\leq{|\mathcal{P}|}^{3}$ and $|A||\mathcal{P}|\ll p^{2}$, we have

$\mathcal{I}(\mathcal{P},\mathcal{L})\ll{|A|}^{\frac{3}{4}}{|B|}^{\frac{1}{2}}{|\mathcal{P}|}^{\frac{3}{4}}+|\mathcal{P}|.$

###### Proof.

Define $\mathcal{P}^{\prime}:=A\times B$ and
$\mathcal{L}^{\prime}:=\\{l_{c,d}:-y=cx-d\mid(c,d)\in\mathcal{P}\\}$. Then,
$I(\mathcal{P},\mathcal{L})=I(\mathcal{P}^{\prime},\mathcal{L}^{\prime})$.
Thus, by theorem 3.1.1, we know that

$\mathcal{I}(\mathcal{P},\mathcal{L})=\mathcal{I}(\mathcal{P}^{\prime},\mathcal{L}^{\prime})\ll{|A|}^{\frac{3}{4}}{|B|}^{\frac{1}{2}}{|\mathcal{P}|}^{\frac{3}{4}}+|\mathcal{P}|.$

∎

######  Lemma 3.2.6.

Let $A,B,X\subseteq\mathbb{F}_{p}$ such that $|X|\leq|A||B|$ and
$|A|\leq|B|\ll p^{\frac{2}{5}}$. Then,

$\sum_{x\in
X}E^{+}(A,xB)\ll{|A|}^{\frac{5}{3}}{|B|}^{\frac{4}{3}}{|X|}^{\frac{2}{3}}.$

###### Proof.

Note that

$\sum_{x\in X}E^{+}(A,xB)=\sum_{x\in
X}\sum_{y\in\mathbb{F}_{p}}r_{A+xB}^{2}(y).$ (18)

######  Claim.

Let $R_{t}:=\\{(x,y)\mid r_{A+xB}(y)\geq t\\}$. Then, for any integer $2\leq
t\leq|A|$,

$|R_{t}|\ll\frac{{|A|}^{3}{|B|}^{2}}{t^{4}}.$

Note that for $t>|A|$, $R_{t}=\emptyset$. Define a collection of lines
$\mathcal{L}:=\\{l_{a,b}:y=ax+b\mid(a,b)\in A\times B\\}$. Since
$r_{A+xB}(y)=|\\{(a,b)\mid y=ax+b\\}|$. Thus, for every pair $(x,y)\in R_{t}$,
$|\\{l_{a,b}\mid(x,y)\in l_{a,b}\\}|\geq t$. Divide it into two cases:

  1. 1.

Assume $|A|{|B|}^{2}\leq{|R_{t}|}^{3}$ so that we can apply lemma 3.2.5. By
lemma 3.2.5,

$\begin{split}&t|R_{t}|\leq\mathcal{I}(R_{t},\mathcal{L})\ll{|A|}^{\frac{3}{4}}{|B|}^{\frac{1}{2}}{|R_{t}|}^{\frac{3}{4}}+|R_{t}|\\\
&\Rightarrow|R_{t}|\ll\frac{{|A|}^{3}{|B|}^{2}}{t^{4}}+\frac{|R_{t}|}{t}\ll\frac{{|A|}^{3}{|B|}^{2}}{t^{4}}\end{split}$

since $|R_{t}|\leq{|A|}^{2}{|B|}^{2}$. This completes the proof of the claim.

  2. 2.

Assume ${|R_{t}|}^{3}\leq|A|{|B|}^{2}$. Then, via this assumption,

$|R_{t}|\leq\underbrace{{|A|}^{\frac{1}{3}}{|B|}^{\frac{2}{3}}\times\frac{t^{4}}{{|A|}^{3}{|B|}^{2}}}_{=O(1)}\times\frac{{|A|}^{3}{|B|}^{2}}{t^{4}}\ll\frac{{|A|}^{3}{|B|}^{2}}{t^{4}},$

which also completes this proof of the claim.

Let $\Delta$ be a parameter to be determined later. Then, by equation (18),

$\begin{split}\sum_{x\in X}E^{+}(A,xB)&=\sum_{x\in
X}\sum_{y\in\mathbb{F}_{p}}r_{A+xB}^{2}(y)\\\
&=\sum_{\begin{subarray}{c}(x,y)\in X\times\mathbb{F}_{p}\\\
r_{A+xB}(y)\leq\Delta\end{subarray}}r_{A+xB}^{2}(y)+\sum_{\begin{subarray}{c}(x,y)\in
X\times\mathbb{F}_{p}\\\
r_{A+xB}(y)>\Delta\end{subarray}}r_{A+xB}^{2}(y)\end{split}$

  1. 1.

For the first term, observe that

$\sum_{\begin{subarray}{c}(x,y)\in\mathbb{F}_{p}\\\
r_{A+xB}(y)\leq\Delta\end{subarray}}r_{A+xB}^{2}(y)\leq\Delta\sum_{x\in
X}\sum_{y\in\mathbb{F}_{p}}r_{A+xB}(y)=\Delta|A||B||X|.$

  2. 2.

For the second term, by the above claim, we have

$\begin{split}\sum_{\begin{subarray}{c}(x,y)\in X\times\mathbb{F}_{p}\\\
r_{A+xB}(y)>\Delta\end{subarray}}r_{A+xB}^{2}(y)&=\sum_{j\geq
1}\sum_{\begin{subarray}{c}(x,y)\in X\times\mathbb{F}_{p}\\\
2^{j-1}\Delta<r_{A+xB}(y)\leq 2^{j}\Delta\end{subarray}}r_{A+xB}^{2}(y)\\\
&\ll\sum_{j\geq
1}\left(\frac{{|A|}^{3}{|B|}^{2}}{2^{4j-4}\Delta^{4}}\right)2^{2j}\Delta^{2}\ll\frac{{|A|}^{3}{|B|}^{2}}{\Delta^{2}}.\end{split}$

Let $\Delta\sim{|A|}^{\frac{2}{3}}{|B|}^{\frac{1}{3}}{|X|}^{-\frac{1}{3}}$.
Then, we know that

$\sum_{x\in
X}E^{+}(A,xB)\ll{|A|}^{\frac{5}{3}}{|B|}^{\frac{4}{3}}{|X|}^{\frac{2}{3}}.$

∎

######  Lemma 3.2.7.

Let $A,B$ be finite subsets of $\mathbb{F}_{p}$ with $|A|\ll|B|\ll
p^{\frac{2}{5}}$. Then,

$R(\mathbb{F}_{p},A,B)\lesssim{|A|}^{\frac{11}{3}}{|B|}^{3}.$

###### Proof.

Let $Q:=(A+B)/(A+B)$ and $Z_{t}:=\\{z\in\mathbb{F}_{p}\mid r_{Q}(z)\geq t\\}$.
Note that for any $t\geq 1$,

$t|Z_{t}|\leq\sum_{z\in Z_{t}}r_{Q}(z)\leq\sum_{z\in
Q}r_{Q}(z)={|A|}^{2}{|B|}^{2}.$

  1. 1.

Assume $|Z_{t}|\geq|A||B|$. Then,

$|A|B|\geq
t\Rightarrow|Z_{t}|\leq\frac{{|Z_{t}|}^{2}}{t}\leq\frac{{|A|}^{3}{|B|}^{3}}{t^{2}}.$

  2. 2.

On the other hand, suppose $|Z_{t}|\leq|A||B|$. Observe that every solution of
the equation

$z=\frac{a_{2}+b_{2}}{a_{1}+b_{1}}$

is a solution to

$b_{2}-za_{1}=zb_{1}-a_{2}=y\in\mathbb{F}_{p}.$

Thus,

$\begin{split}r_{Q}(z)&\leq\sum_{y\in\mathbb{F}_{p}}r_{B-zA}(y)r_{zB-A}(y)\leq\sum_{y\in\mathbb{F}_{p}}\frac{r_{B-zA}^{2}(y)+r_{zB-A}^{2}(y)}{2}\\\
&=\frac{1}{2}\left(E^{+}(B,zA)+E^{+}(zB,A)\right).\end{split}$

We sum over $z\in Z_{t}$ and get

$\begin{split}&t|Z_{t}|\leq\frac{1}{2}\sum_{z\in
Z_{t}}\left(E^{+}(B,zA)+E^{+}(zB,A)\right)\ll{|A|}^{\frac{5}{3}}{|B|}^{\frac{4}{3}}{|Z_{t}|}^{\frac{2}{3}}\\\
&\Rightarrow|Z_{t}|\ll\frac{{|A|}^{5}{|B|}^{4}}{t^{3}}\end{split}$

by lemma 3.2.6.

Therefore,

$\begin{split}R(\mathbb{F}_{p},A,B)&=\sum_{z\in
Q}r_{Q}^{2}(z)=\sum_{t=1}^{|Q|}t^{2}\left(|Z_{t}|-|Z_{t+1}|\right)\sim\sum_{t=1}^{|Q|}t|Z_{t}|\\\
&=\sum_{t:|Z_{t}|\geq|A||B|}t|Z_{t}|+\sum_{t:|Z_{t}|\leq|A||B|}t|Z_{t}|\\\
&\ll\sum_{t:|Z_{t}|\geq|A||B|}\frac{{|A|}^{3}{|B|}^{3}}{t}+\sum_{\begin{subarray}{c}t:|Z_{t}|<|A||B|\\\
t\leq{|A|}^{\frac{4}{3}}|B|\end{subarray}}t|Z_{t}|+\sum_{\begin{subarray}{c}t:|Z_{t}|<|A||B|\\\
t\geq{|A|}^{\frac{4}{3}}|B|\end{subarray}}\frac{{|A|}^{5}{|B|}^{4}}{t^{2}}\\\
&\lesssim{|A|}^{3}{|B|}^{3}+{|A|}^{\frac{11}{3}}{|B|}^{3}={|A|}^{\frac{11}{3}}{|B|}^{3}.\end{split}$

∎

######  Lemma 3.2.8.

Let $A\subseteq\mathbb{F}_{p}$ with $|A|\ll p^{\frac{1}{5}}$. Then, there is a
subset $A^{\prime}\subseteq A$ such that

$|A^{\prime}|\gtrsim{E_{3}^{+}(A)}^{\frac{1}{2}}{|A|}^{-1}\text{ and
}{E_{3}^{+}(A)}^{4}{E^{\times}(A^{\prime})}^{3}\ll{|A|}^{12}{|A^{\prime}|}^{12}.$

###### Proof.

Via a regular dyadic pigeonhole argument, there is a number $t\leq|A|$ and a
set of popular differences

$P:=\\{x\in A-A\mid t\leq r_{A-A}(x)<2t\\}\text{ such that
}E_{3}^{+}(A)\approx|P|t^{3}.$

Again, by applying dyadic argument, there is a $q_{1}\leq|A|$ and a set of
popular abscissae

$A_{1}=\\{a\in A\mid q_{1}\leq r_{P+A}(a)<2q_{1}\\}$

such that

$|A_{1}|q_{1}\approx\sum_{a\in A_{1}}r_{P+A}(a)\approx\sum_{x\in
P}r_{A-A}(x)\approx|P|t.$

Using dyadic argument once again, there is a $q_{2}\leq|A_{1}|$ and a set of
popular coordinates

$A_{2}=\\{b\in A\mid q_{2}\leq r_{A_{1}-P}(b)<2q_{2}\\}$

such that

$|A_{2}|q_{2}\approx\sum_{b\in A_{2}}r_{A_{1}-P}(b)\approx\sum_{a\in
A_{1}}r_{P+A}(a)\approx|A_{1}|q_{1}.$

Since $q_{2}\lesssim|A_{1}|$, either $q_{1}\lesssim|A_{1}|$ or
$q_{2}\lesssim|A_{1}|\lesssim q_{1}\lesssim|A_{2}|$. Assume

$q_{2}\lesssim|A_{1}|\lesssim q_{1}\lesssim|A_{2}|$

For the other case, the proof is similar. By construction, for any $b\in
A_{2}$, $|A\cap(P+b)|\approx q_{2}$. Now there are $E^{\times}(A_{2})$
quadruples $(b_{1},b_{2},b_{3},b_{4})\in{A_{2}}^{4}$ such that

$\frac{b_{1}}{b_{2}}=\frac{b_{3}}{b_{4}}.$

Thus, for every such tuple $(b_{1},b_{2},b_{3},b_{4})$, there are
approximately ${q_{2}}^{4}$ choices of $(a_{1},a_{2},a_{3},a_{4})$ such that
$a_{i}\in A_{1}\cap(P+b_{i})$ and

$\frac{a_{1}-(a_{1}-b_{1})}{a_{2}-(a_{2}-b_{2})}=\frac{a_{3}-(a_{3}-b_{3})}{a_{4}-(a_{4}-b_{4})}.$

Denote $s_{i}=a_{i}-b_{i}\in P$. Then,

$E^{\times}(A_{2}){\left(\frac{|P|t}{|A_{2}|}\right)}^{4}\approx
E^{\times}(A_{2}){q_{2}}^{4}\ll N,$ (19)

where

$\begin{split}N&=\left|\left\\{(a_{1},\dotsc,a_{4},s_{1},\dotsc,s_{4})\in
A^{4}\times
P^{4}\,\middle|\,\frac{a_{1}-s_{1}}{a_{2}-s_{2}}=\frac{a_{3}-s_{3}}{a_{4}-s_{4}}\in
A_{2}/A_{2}\right\\}\right|\\\ &=R(Z,A,-P)\end{split}$

with $Z:=A_{2}/A_{2}$ and $-P:=\\{-s\mid s\in P\\}$. Denote

$r(z)=|\\{(a_{1},a_{2},s_{1},s_{2})\in A^{2}\times
P^{2}\mid(a_{1}-s_{1})=z(a_{2}-s_{2})\\}|\Rightarrow N\leq\sum_{z\in
Z}r^{2}(z).$

Divide it into two cases:

  1. 1.

Assume $|P|\leq|A|$. By lemma 3.2.7 and equation (19),

$\begin{split}&N=R(Z,A,-P)\ll{|A|}^{3}{|P|}^{\frac{11}{3}}\Rightarrow
E^{\times}(A_{2}){\left(\frac{|P|t}{|A_{2}|}\right)}^{4}\ll{|A|}^{3}{|P|}^{\frac{11}{3}}\\\
&\Rightarrow{|P|}^{\frac{1}{3}}t^{4}\ll\frac{{|A|}^{3}{|A_{2}|}^{4}}{E^{\times}(A_{2})}.\end{split}$

Thus,

$E_{3}^{+}(A)\approx|P|t^{3}\ll{|P|}^{\frac{3}{4}}{\left(\frac{{|A|}^{3}{|A_{2}|}^{4}}{E^{\times}(A_{2})}\right)}^{\frac{3}{4}}\ll\frac{{|A|}^{3}{|A_{2}|}^{3}}{{E^{\times}(A_{2})}^{\frac{3}{4}}}.$
(20)

  2. 2.

On the other hand, for $|P|>|A|$, it satisfies the assumption of Lemma 3.2.2.
Thus, by Lemma 3.2.2 and Equation (19),

$\begin{split}&N=R(Z,A,-P)\lesssim{|A|}^{\frac{33}{8}}{|A_{2}|}^{\frac{5}{2}}\Rightarrow
E^{\times}(A_{2}){\left(\frac{|P|t}{|A_{2}|}\right)}^{4}\lesssim{|A|}^{\frac{33}{8}}{|P|}^{\frac{5}{2}}\\\
&\Rightarrow{|P|}^{\frac{3}{2}}t^{4}\lesssim\frac{{|A|}^{\frac{33}{8}}{|A_{2}|}^{4}}{E^{\times}(A_{2})}.\end{split}$

Thus,

$E_{3}^{+}(A)\approx|P|t^{3}\lesssim{|P|}^{-\frac{1}{8}}{\left(\frac{{|A|}^{\frac{33}{8}}{|A_{2}|}^{4}}{E^{\times}(A_{2})}\right)}^{\frac{3}{4}}\ll\frac{{|A|}^{\frac{95}{32}}{|A_{2}|}^{3}}{{E^{\times}(A_{2})}^{\frac{3}{4}}}$
(21)

Combining equations (20) and (21), we get

$E_{3}^{+}(A)\lesssim\frac{{|A|}^{3}{|A_{2}|}^{3}}{{E^{\times}(A_{2})}^{\frac{3}{4}}}\Rightarrow{E_{3}^{+}(A)}^{4}{E^{\times}(A_{2})}^{3}\lesssim{|A|}^{12}{|A_{2}|}^{12}.$

Additionally, since $t\leq|A|$,

${|A_{2}|}^{2}\gtrsim|A_{2}|q_{2}\approx|P|t\approx\frac{E_{3}^{+}(A)}{t^{2}}\geq\frac{E_{3}^{+}(A)}{{|A|}^{2}}.$

Set $A^{\prime}=A_{2}$ and we get the conclusion. ∎

###### Proof of Proposition 3.2.4.

Similar to the proof of lemma 3.2.8, there is a number $t\leq|A|$ and a set of
popular differences

$P:=\\{x\in A-B\mid t\leq r_{A-B}(x)<2t\\}\text{ such that
}E_{3}^{+}(A,B)\approx|P|t^{3}.$

By dyadic decomposition again, there is a number $q\leq|A|$ and a set of
popular abscissae

$A_{1}:=\\{a\in A\mid q\leq r_{P+B}(a)<2q\\}$

such that

$|A_{1}|q\approx\sum_{a\in P+B}r_{P+B}(a)\approx\sum_{x\in
P}r_{A-B}(x)\approx|P|t.$

Divide it into two cases:

  1. 1.

If $|P|\leq|B|$, then

$\begin{split}&\frac{{|A_{1}|}^{4}}{|A_{1}\cdot
A_{1}|}\times\frac{{|P|}^{4}t^{4}}{{|A_{1}|}^{4}}\lesssim
E^{\times}(A_{1})q^{4}\approx
R(\mathbb{F}_{p},P,B)\lesssim{|P|}^{\frac{11}{3}}{|B|}^{3}\\\
&\Rightarrow{|P|}^{\frac{1}{3}}t^{4}\lesssim|A_{1}\cdot A_{1}|{|B|}^{3}.\\\
&\Rightarrow
E_{3}^{+}(A,B)\approx{|P|}^{\frac{3}{4}}{\left({|P|}^{\frac{1}{3}}t^{4}\right)}^{\frac{3}{4}}\lesssim{|P|}^{\frac{3}{4}}{|A_{1}\cdot
A_{1}|}^{\frac{3}{4}}{|B|}^{\frac{9}{4}}\lesssim{|A_{1}\cdot
A_{1}|}^{\frac{3}{4}}{|B|}^{3}.\end{split}$ (22)

  2. 2.

If $|P|>|B|$, then since $|A_{1}/A_{1}|\lesssim{|B|}^{2}$, we can apply Lemma
3.2.2 to get

$\frac{{|A_{1}|}^{4}}{|A_{1}\cdot
A_{1}|}\times\frac{{|P|}^{4}t^{4}}{{|A_{1}|}^{4}}\lesssim
E^{\times}(A_{1})q^{4}\approx
R(\mathbb{F}_{p},P,B)\lesssim{|B|}^{\frac{33}{8}}{|P|}^{\frac{5}{2}}.$

That is,

$\begin{split}&{|P|}^{\frac{3}{2}}t^{4}\lesssim|A\cdot
A|{|B|}^{\frac{33}{8}}\Rightarrow{\left(|P|t^{3}\right)}^{\frac{4}{3}}\lesssim{|P|}^{-\frac{1}{6}}|A\cdot
A|{|B|}^{\frac{33}{8}}\\\
&\Rightarrow{E_{3}^{+}(A,B)}^{\frac{4}{3}}\approx{\left(|P|t^{3}\right)}^{\frac{4}{3}}\lesssim|A\cdot
A|{|B|}^{\frac{95}{24}}\\\ &\Rightarrow E_{3}^{+}(A,B)\lesssim{|A\cdot
A|}^{\frac{3}{4}}{|B|}^{\frac{95}{32}}.\end{split}$ (23)

Combining equations (22) and (23), we get

$E_{3}^{+}(A,B)\lesssim{|A\cdot
A|}^{\frac{3}{4}}{|B|}^{3}\Rightarrow{E_{3}^{+}(A,B)}^{\frac{4}{3}}{|B|}^{-4}\lesssim|A\cdot
A|,$

which completes this proof. ∎

Finally, using the above lemmas, we obtain a new sum-product estimate in
$\mathbb{F}_{p}$.

######  Theorem 3.2.9.

Let $A\subseteq\mathbb{F}_{p}$ with $|A|\ll p^{\frac{2}{5}}$. Then,

${|A+A|}^{8}{|A\cdot A|}^{3}\gtrsim{|A|}^{12}.$

Especially, we have

$\max\\{|A+A|,|A\cdot A|\\}\gtrsim{|A|}^{1+\frac{1}{11}}.$

###### Proof.

By Hölder inequality,

${|A|}^{2}=\sum_{x\in A+A}r_{A+A}(x)\leq{|A+A|}^{\frac{2}{3}}{\left(\sum_{x\in
A+A}r_{A+A}^{3}(x)\right)}^{\frac{1}{3}}\Rightarrow|A+A|\geq\frac{{|A|}^{3}}{{E_{3}^{+}(A)}^{\frac{1}{2}}}.$

Together with Proposition 3.2.4, we have

$\begin{split}&\left\\{\begin{array}[]{l}{E_{3}^{+}(A)}^{\frac{4}{3}}{|A|}^{-4}\lesssim|A\cdot
A|\\\
{E_{3}^{+}(A)}^{-\frac{1}{2}}{|A|}^{3}\leq|A+A|\end{array}\right.\Rightarrow\left\\{\begin{array}[]{l}{E_{3}^{+}(A)}^{4}{|A|}^{-12}\lesssim{|A\cdot
A|}^{3}\\\ {E_{3}^{+}(A)}^{-4}{|A|}^{24}\leq{|A+A|}^{8}\end{array}\right.\\\
&\Rightarrow{|A|}^{12}\lesssim{|A+A|}^{8}{|A\cdot A|}^{3},\end{split}$

which completes the proof. ∎

######  Remark 3.2.10.

Although we can see that if we compare Theorem 3.2.9 and Theorem 3.1.2, the
latter is stronger in general, the proving technique of Theorem 3.2.9 is
totally different from Elekes’ method, so this provides a new perspective to
Erdös-Szemerédi Conjecture in $\mathbb{F}_{p}$.

###  3.3 A better estimate of additive energy in $\mathbb{F}_{p}$

In this part, we use “the point-plane incidence” bound, proved in [14], to
give another estimate. This is also a piece of evidence to show the strong
connection between Incidence Geometry and sum-product estimate.

######  Theorem 3.3.1 (Theorem 3, [14]).

Let $\mathcal{P},\Pi$ be sets of points and planes, of cardinalities
respectively $m$ and $n$ in $\mathbb{F}_{p}$. Suppose that $m\geq n$ and
$n=O(p^{2})$. Let $k$ be the maximum number of collinear planes. Then,

$|\mathcal{I}(\mathcal{P},\Pi)|=O(m\sqrt{n}+km).$

Using this bound, we prove the following theorem.

######  Theorem 3.3.2.

Let $A\subseteq\mathbb{F}_{p}$ with $|A|\ll p^{\frac{1}{2}}$. Then,

${|A+A|}^{2}{|A\cdot A|}^{3}\gtrsim{|A|}^{6}.$

Especially, we have

$\max\\{|A+A|,|A\cdot A|\\}\gtrsim{|A|}^{1+\frac{1}{5}}.$

###### Proof.

Notice that

$\begin{split}E^{+}(A)&=\left|\left\\{(a_{1},a_{2},a_{3},a_{4})\in
A^{4}\,\middle|\,a_{1}+a_{2}=a_{3}+s_{4}\right\\}\right|\\\
&={|A|}^{-2}N_{1}\leq{|A|}^{-2}N_{2}\end{split}$ (24)

where

$N_{1}:=\left|\left\\{(a_{1},a_{2},a_{3},a_{4},a_{5},a_{6})\in
A^{6}\,\middle|\,(a_{1}a_{2}){a_{2}}^{-1}+a_{5}=(a_{3}a_{4}){a_{4}}^{-1}+a_{6}\right\\}\right|$

and $N_{2}$ is defined as

$\left|\left\\{(u_{1},u_{2},v_{1},v_{2},a_{1},a_{2})\in{(A\cdot
A)}^{2}\times{\left(A^{-1}\right)}^{2}\times
A^{2}\,\middle|\,u_{1}v_{1}+a_{1}=u_{2}v_{2}+a_{2}\right\\}\right|.$

Consider

$\mathcal{P}:=\\{(u_{1},a_{1},v_{2})\in(A\cdot A)\times A\times A^{-1}\\}$

and

$\Pi:=\\{\pi:ax+y=bz+c\mid a\in A^{-1},b\in A\cdot A,c\in A\\}.$

Note that $|\mathcal{P}|=|\Pi|=|A\cdot A|{|A|}^{2}\ll p^{2}$ and

$\mathcal{I}(\mathcal{P},\Pi):=|\\{(p,\pi)\in\mathcal{P}\times\Pi\mid
p\in\pi\\}|=N_{2}.$

For any line

$l=\\{(x,y,z)=(x_{0}+\alpha t,y_{0}+\beta t,z_{0}+\gamma t)\mid
t\in\mathbb{F}_{p}\\},$

define

$\Pi_{l}:=\\{\pi\in\Pi\mid l\in\pi\\}.$

Then, $k=\max_{l}|\Pi_{l}|$. For a plane $\pi:ax+y=bz+c\in\Pi_{l}$, we have

$\left\\{\begin{array}[]{l}ax_{0}+y_{0}=bz_{0}+c\\\
a\alpha+\beta=b\gamma\end{array}\right.\Rightarrow\left\\{\begin{array}[]{l}b=b(a)\\\
c=c(a)\end{array}\right.\text{ if such }b,c\text{ exist.}$

That is, $|\Pi_{l}|\leq|A|\Rightarrow k\leq|A|$. Therefore, by equation (24)
and Theorem 3.3.1, we know that

$\begin{split}E^{+}(A)&\leq{|A|}^{-2}N_{2}={|A|}^{-2}\mathcal{I}(\mathcal{P},\Pi)\\\
&\ll{|A|}^{-2}\left({|A\cdot A|}^{\frac{3}{2}}{|A|}^{3}+|A||A\cdot
A|{|A|}^{2}\right)\ll|A|{|A\cdot A|}^{\frac{3}{2}}.\end{split}$

Applying Cauchy-Schwarz inequality, we have

$\frac{{|A|}^{4}}{|A+A|}\ll|A|{|A\cdot
A|}^{\frac{3}{2}}\Rightarrow{|A|}^{6}\ll{|A+A|}^{2}{|A\cdot A|}^{3}.$

∎

######  Remark 3.3.3.

In this theorem, we can see that the exponential part, $1+\frac{1}{5}$ is as
same as Corollary 3.1.2. Therefore, in this sense, we obtained a result as
good as Stevens did. However, in Corollary 3.1.3, we can see that in extremal
cases, Corollary 3.1.3 is still better than our result. In spite of this, the
idea of adapting point-plane incidence to proofs of sum-product theorems is
still valueless.

##  4 Other Incidence Geometry Problems

In the previous sections, we already realize how powerful an Incidence
Geometry result can be in the sum-product estimate. Therefore, this section
will focus on several kinds of Incidence Geometry problems whose connection to
sum-product estimate is more implicit than previous ones and briefly introduce
their relation to sum-product estimate.

###  4.1 Collinear lines in grids

In the proof of Theorem 6.2 in [15], Bourgain, Katz, and Tao observed that if
the point-line incidence $\mathcal{I}(\mathcal{P},\mathcal{L})$ is large, then
the point set should contain several large grid-like structures. Hence, to
improve the upper bound of $\mathcal{I}(\mathcal{P},\mathcal{L})$, a more
delicate result about the incidence relation between lines and grids must be
needed. Additionally, Xue (2020, [13]) already applied this idea in the real
number, and this section will extend his skill to the finite field
$\mathbb{F}_{p}$. To start with, we define an incidence amount as follows.

######  Definition 4.1.1 ($T^{o},T$).

For any three subsets $A,B,C\subseteq\mathbb{F}_{p}$, define

$\begin{split}&T^{o}(A,B,C)\\\ &:=\left|\\{(u_{1},u_{2},u_{3})\in A^{2}\times
B^{2}\times C^{2}\mid\\{u_{1},u_{2},u_{3}\\}\text{ are collinear and
distinct}\\}\right|\end{split}$

and

$\begin{split}T(A,B,C):=&\text{ the number of tuples
}(a_{1},a_{2},b_{1},b_{2},c_{1},c_{2})\in A^{2}\times B^{2}\times C^{2}\\\
&\text{ with
}(b_{1}-a_{1})(c_{2}-a_{2})=(c_{1}-a_{1})(b_{2}-a_{2}).\end{split}$

Now, we want to bound $T(A,B,C)$, but before that, we need the following Lemma
4.1.2 and 4.1.3 to obtain an upper bound for $T^{o}(A,B,C)$ and use the
relation between $T$ and $T^{o}$ to get the desired upper bound in Proposition
4.1.4.

######  Lemma 4.1.2.

Let $A,B$ be subsets of $\mathbb{F}_{p}$ with $|A|\leq|B|\ll p^{\frac{2}{5}}$
and $\mathcal{P}=A\times B$. Then,

$|\mathcal{L}|\ll\min\left\\{\frac{{|A|}^{3}{|B|}^{2}}{k^{4}},\frac{{|A|}^{2}{|B|}^{2}}{k^{2}}\right\\}+\frac{|\mathcal{L}|}{k}$

with

$\mathcal{L}:=\\{l:\text{a line in }{\mathbb{F}_{p}}^{2}\mid|l\cap(A\times
B)|\geq k\\}.$

###### Proof.

Let $\mathcal{L}$ be the collection of lines $l$ with $|l\cap(A\times B)|\geq
k$. Thus,

$k|\mathcal{L}|\leq\mathcal{I}(A\times B,\mathcal{L}).$

If ${|\mathcal{L}|}^{3}<|A|{|B|}^{2}$, this lemma holds. i.e. We may assume
${|\mathcal{L}|}^{3}\geq|A|{|B|}^{2}$. Additionally,

$|A||\mathcal{L}|\ll|A|{|A\times B|}^{2}\ll p^{2},$

so we can apply theorem 3.1.1. By theorem 3.1.1,

$\mathcal{I}(A\times
B,\mathcal{L})\ll{|A|}^{\frac{3}{4}}{|B|}^{\frac{1}{2}}{|\mathcal{L}|}^{\frac{3}{4}}+|\mathcal{L}|\Rightarrow|\mathcal{L}|\ll\frac{{|A|}^{3}{|B|}^{2}}{k^{4}}+\frac{|\mathcal{L}|}{k}.$
(25)

Moreover, by Cauchy-Schwarz incidence bound,

$k|\mathcal{L}|\leq\mathcal{I}(A\times
B,\mathcal{L})\ll|A||B|{|\mathcal{L}|}^{\frac{1}{2}}+|\mathcal{L}|\Rightarrow|\mathcal{L}|\ll\frac{{|A|}^{2}{|B|}^{2}}{k^{2}}+\frac{|\mathcal{L}|}{k}.$
(26)

We complete the proof by combining equations (25) and (26). ∎

######  Lemma 4.1.3.

Suppose that $A_{1},A_{2},A_{3}\subset\mathbb{F}_{p}$ with
$|A_{1}|\leq|A_{2}|\leq|A_{3}|\ll p^{\frac{2}{5}}$. Let $\mathcal{L}$ be the
collection of lines such that $l\in\mathcal{L}$ if and only if $l$ contains
three distinct points $u_{1},u_{2},u_{3}$ with $u_{i}\in{A_{i}}^{2}$. For each
$l\in\mathcal{L}$ and $i=1,2,3$, define $\alpha_{i,l}=|l\cap(A_{i}\times
A_{i})|$. For $1\leq k\leq|A_{i}|$, define
$\mathcal{L}_{i,k}:=\\{l\in\mathcal{L}\mid\alpha_{i,l}\geq k\\}$. Then, we
have

$\sum_{l\in\mathcal{L}_{i,2}}{\alpha_{i,l}}^{s}\lesssim{|A_{i}|}^{4}+{|A_{i}|}^{\frac{s}{2}+3}+{|A_{i}|}^{s+1}\text{
for }i=1,2,3\text{ and }s>1.$

###### Proof.

Note that

$\begin{split}\sum_{l\in\mathcal{L}_{i,2}}{\alpha_{i,l}}^{s}&=\sum_{2\leq
k\leq|A_{i}|}|\\{l\in\mathcal{L}_{i,2}\mid\alpha_{i,l}=k\\}|k^{s}\\\
&\approx\sum_{2\leq
k\leq|A_{i}|}\left(|\\{l\in\mathcal{L}_{i,2}\mid\alpha_{i,l}=k\\}|\sum_{2\leq
m\leq k}m^{s-1}\right)\\\ &=\sum_{2\leq
m\leq|A_{i}|}m^{s-1}\underbrace{\sum_{k\geq
m,k\leq|A_{i}|}|\\{l\in\mathcal{L}_{i,2}\mid\alpha_{i,l}=k\\}|}_{=|\\{l\in\mathcal{L}_{i,2}\mid\alpha_{i,l}\geq
m\\}|}\\\ &\approx\sum_{2\leq
m\leq|A_{i}|}m^{s-1}|\\{l\in\mathcal{L}_{i,2}\mid\alpha_{i,l}\geq
m\\}|=\sum_{2\leq m\leq|A_{i}|}m^{s-1}|\mathcal{L}_{i,m}|.\end{split}$

Divide it into three parts:

  1. 1.

For $2\leq m\leq\log|A_{i}|$, via lemma 4.1.2,

$|\mathcal{L}_{i,m}|\lesssim\frac{{|A_{i}|}^{4}}{m^{2}}+\frac{|\mathcal{L}|}{m}\lesssim
m^{-1}{|A_{i}|}^{4}.$

  2. 2.

Similarly, for $\log|A_{i}|\leq m\leq{|A_{i}|}^{\frac{1}{2}}$, we can get

$|\mathcal{L}_{i,m}|\lesssim m^{-2}{|A_{i}|}^{4}.$

  3. 3.

As for ${|A_{i}|}^{\frac{1}{2}}\leq m\leq|A_{i}|$, we obtain

$|\mathcal{L}_{i,m}|\lesssim\frac{{|A_{i}|}^{5}}{m^{4}}+\frac{|\mathcal{L}|}{m}\lesssim
m^{-4}{|A_{i}|}^{5}.$

To sum up, we have

$\begin{split}\sum_{l\in\mathcal{L}_{i,2}}{\alpha_{i,l}}^{s}\lesssim&\sum_{2\leq
m\leq\log|A_{i}|}m^{s-2}{|A_{i}|}^{4}+\sum_{\log|A_{i}|\leq
m\leq{|A_{i}|}^{\frac{1}{2}}}m^{s-3}{|A_{i}|}^{4}\\\
&+\sum_{{|A_{i}|}^{\frac{1}{2}}\leq m\leq|A_{i}|}m^{s-5}{|A_{i}|}^{5}\\\
\lesssim&{|A_{i}|}^{4}+\left(1+{|A_{i}|}^{\frac{s-2}{2}}\right){|A_{i}|}^{4}+\left({|A_{i}|}^{\frac{s-4}{2}}+{|A_{i}|}^{s-4}\right){|A_{i}|}^{5}\\\
\lesssim&{|A_{i}|}^{4}+{|A_{i}|}^{\frac{s}{2}+3}+{|A_{i}|}^{s+1}.\end{split}$

∎

######  Proposition 4.1.4.

Suppose that $A_{1},A_{2},A_{3}$ are three finite subsets of $\mathbb{F}_{p}$
with $|A_{1}|\leq|A_{2}|\leq|A_{3}|\ll p^{\frac{2}{5}}$. Then,

$\begin{split}T^{o}(A_{1},A_{2},A_{3})\lesssim&\min\left\\{|A_{1}|{|A_{2}|}^{\frac{9}{4}}{|A_{3}|}^{\frac{5}{4}},{|A_{1}|}^{\frac{1}{2}}{|A_{2}|}^{\frac{5}{2}}{|A_{3}|}^{\frac{5}{4}},{|A_{2}|}^{2}{|A_{3}|}^{2}\right\\}\\\
&+{|A_{1}|}^{2}{|A_{2}|}^{\frac{5}{4}}{|A_{3}|}^{\frac{5}{4}}+{|A_{1}|}^{\frac{3}{2}}{|A_{2}|}^{\frac{3}{2}}{|A_{3}|}^{\frac{5}{4}}\end{split}$

and

$T(A_{1},A_{2},A_{3})\lesssim
T^{o}(A_{1},A_{2},A_{3})+{|A_{1}|}^{2}{|A_{3}|}^{2}.$

###### Proof.

It is clear that

$T^{o}(A_{1},A_{2},A_{3})\leq\sum_{l\in\mathcal{L}}\alpha_{1,l}\alpha_{2,l}\alpha_{3,l}.$

Denote $I_{1}=\\{1\\}$ and $I_{2}=\mathbb{N}\setminus\\{1\\}$ and for
$(j_{1},j_{2},j_{3})\in{\\{1,2\\}}^{3}$, define

$S_{j_{1},j_{2},j_{3}}:=\sum_{\begin{subarray}{c}l\in\mathcal{L}\\\
\alpha_{i,l}\in I_{j_{i}}\end{subarray}}\alpha_{1,l}\alpha_{2,l}\alpha_{3,l}.$

By Cauchy-Schwarz inequality and Lemma 4.1.3, we have

$\begin{split}S_{1,2,2}&\leq\sum_{l\in\left(\mathcal{L}_{2,2}\cap\mathcal{L}_{3,2}\right)\setminus\mathcal{L}_{1,2}}\alpha_{2,l}\alpha_{3,l}\leq{|\mathcal{L}|}^{\frac{1}{2}}{\left(\sum_{l\in\mathcal{L}_{2,2}\cap\mathcal{L}_{3,2}}{\left(\alpha_{2,l}\alpha_{3,l}\right)}^{2}\right)}^{\frac{1}{2}}\\\
&\ll{\left({|A_{1}|}^{2}{|A_{2}|}^{2}\right)}^{\frac{1}{2}}{\left({\left(\sum_{l\in\mathcal{L}_{2,2}}{\left({\alpha_{2,l}}^{2}\right)}^{2}\right)}^{\frac{1}{2}}{\left(\sum_{l\in\mathcal{L}_{3,2}}{\left({\alpha_{3,l}}^{2}\right)}^{2}\right)}^{\frac{1}{2}}\right)}^{\frac{1}{2}}\\\
&\ll|A_{1}|{|A_{2}|}^{\frac{9}{4}}{|A_{3}|}^{\frac{5}{4}}.\end{split}$

Also, by Lemma 4.1.3,

$\begin{split}S_{1,2,2}&\leq\sum_{l\in\mathcal{L}_{2,2}\cap\mathcal{L}_{3,2}}\alpha_{2,l}\alpha_{3,l}\leq{\left(\sum_{l\in\mathcal{L}_{2,2}}{\alpha_{2,l}}^{2}\right)}^{\frac{1}{2}}{\left(\sum_{l\in\mathcal{L}_{3,2}}{\alpha_{3,l}}^{2}\right)}^{\frac{1}{2}}\\\
&\leq{\left(\sum_{l\in\mathcal{L}_{2,2}}{\alpha_{2,l}}^{2}\right)}^{\frac{1}{2}}{\left({|\mathcal{L}_{3,2}|}^{\frac{1}{2}}{\left(\sum_{l\in\mathcal{L}_{3,2}}{\left({\alpha_{3,l}}^{2}\right)}^{2}\right)}^{\frac{1}{2}}\right)}^{\frac{1}{2}}\\\
&\lesssim{|A_{2}|}^{2}{\left({|A_{1}|}^{2}{|A_{2}|}^{2}\right)}^{\frac{1}{4}}{|A_{3}|}^{\frac{5}{4}}\lesssim{|A_{1}|}^{\frac{1}{2}}{|A_{2}|}^{\frac{5}{2}}{|A_{3}|}^{\frac{5}{4}}.\end{split}$

Moreover,

$S_{1,2,2}\leq\sum_{l\in\mathcal{L}_{2,2}\cap\mathcal{L}_{3,2}}\alpha_{2,l}\alpha_{3,l}\leq{\left(\sum_{l\in\mathcal{L}_{2,2}}{\alpha_{2,l}}^{2}\right)}^{\frac{1}{2}}{\left(\sum_{l\in\mathcal{L}_{3,2}}{\alpha_{3,l}}^{2}\right)}^{\frac{1}{2}}\ll{|A_{2}|}^{2}{|A_{3}|}^{2}.$

Thus, combining the above three bounds, we get

$S_{1,2,2}\ll\min\left\\{|A_{1}|{|A_{2}|}^{\frac{9}{4}}{|A_{3}|}^{\frac{5}{4}},{|A_{1}|}^{\frac{1}{2}}{|A_{2}|}^{\frac{5}{2}}{|A_{3}|}^{\frac{5}{4}},{|A_{2}|}^{2}{|A_{3}|}^{2}\right\\}.$
(27)

Note that for $i=2,3$,

$\sum_{\begin{subarray}{c}l\in\mathcal{L}\\\
\alpha_{i,l}=1\end{subarray}}{\alpha_{i,l}}^{s}\leq|\mathcal{L}|\leq{|A_{1}|}^{2}{|A_{2}|}^{2}\leq{|A_{i}|}^{4}.$

Thus, by Cauchy-Schwarz inequality and Lemma 4.1.3, we have

$\begin{split}S_{2,j_{2},j_{3}}\leq&{\left(\sum_{l\in\mathcal{L}_{1,2}}{\alpha_{1,l}}^{2}\right)}^{\frac{1}{2}}{\left(\sum_{\begin{subarray}{c}l\in\mathcal{L}\\\
\alpha_{2,l}\in I_{j_{2}},\alpha_{3,l}\in
I_{j_{3}}\end{subarray}}{\left(\alpha_{2,l}\alpha_{3,l}\right)}^{2}\right)}^{\frac{1}{2}}\\\
\leq&{\left(\sum_{l\in\mathcal{L}_{1,2}}{\alpha_{1,l}}^{2}\right)}^{\frac{1}{2}}{\left({\left(\sum_{\begin{subarray}{c}l\in\mathcal{L}\\\
\alpha_{2,l}\in
I_{j_{2}}\end{subarray}}{\left({\alpha_{2,l}}^{2}\right)}^{2}\right)}^{\frac{1}{2}}{\left(\sum_{\begin{subarray}{c}l\in\mathcal{L}\\\
\alpha_{3,l}\in
I_{j_{3}}\end{subarray}}{\left({\alpha_{3,l}}^{2}\right)}^{2}\right)}^{\frac{1}{2}}\right)}^{\frac{1}{2}}\\\
=&{\left(\sum_{l\in\mathcal{L}_{1,2}}{\alpha_{1,l}}^{2}\right)}^{\frac{1}{2}}{\left(\sum_{\begin{subarray}{c}l\in\mathcal{L}\\\
\alpha_{2,l}\in
I_{j_{2}}\end{subarray}}{\alpha_{2,l}}^{4}\right)}^{\frac{1}{4}}{\left(\sum_{\begin{subarray}{c}l\in\mathcal{L}\\\
\alpha_{3,l}\in
I_{j_{3}}\end{subarray}}{\alpha_{3,l}}^{4}\right)}^{\frac{1}{4}}\\\
\ll&{|A_{1}|}^{2}{|A_{2}|}^{\frac{5}{4}}{|A_{3}|}^{\frac{5}{4}}\end{split}$
(28)

Similarly, for $S_{1,1,j_{3}}$ and $S_{1,2,1}$, we have the following
estimates:

$\begin{split}S_{1,1,j_{3}}&\leq\sum_{\begin{subarray}{c}l\in\mathcal{L}\\\
\alpha_{3,l}\in
I_{j_{3}}\end{subarray}}\alpha_{3,l}\leq{|\mathcal{L}|}^{\frac{3}{4}}{\left(\sum_{\begin{subarray}{c}l\in\mathcal{L}\\\
\alpha_{3,l}\in
I_{j_{3}}\end{subarray}}{\alpha_{3,l}}^{4}\right)}^{\frac{1}{4}}\\\
&\lesssim{\left({|A_{1}|}^{2}{|A_{2}|}^{2}\right)}^{\frac{3}{4}}{\left({|A_{3}|}^{5}\right)}^{\frac{1}{4}}={|A_{1}|}^{\frac{3}{2}}{|A_{2}|}^{\frac{3}{2}}{|A_{3}|}^{\frac{5}{4}}\end{split}$
(29)

and

$\begin{split}S_{1,2,1}&\leq\sum_{l\in\mathcal{L}_{2,2}}\alpha_{2,l}\leq{|\mathcal{L}|}^{\frac{3}{4}}{\left(\sum_{\begin{subarray}{c}l\in\mathcal{L}\\\
\alpha_{2,l}\in
I_{j_{2}}\end{subarray}}{\alpha_{2,l}}^{4}\right)}^{\frac{1}{4}}\lesssim{\left({|A_{1}|}^{2}{|A_{2}|}^{2}\right)}^{\frac{3}{4}}{\left({|A_{2}|}^{5}\right)}^{\frac{1}{4}}\\\
&\ll{|A_{1}|}^{\frac{3}{2}}{|A_{2}|}^{\frac{11}{4}}\end{split}$ (30)

To sum up, by equation (27), (28), (29), and (30), we know that

$\begin{split}T^{o}(A_{1},A_{2},A_{3})\leq&\sum_{j_{1},j_{2},j_{3}}S_{j_{1},j_{2},j_{3}}\\\
\lesssim&\min\left\\{|A_{1}|{|A_{2}|}^{\frac{9}{4}}{|A_{3}|}^{\frac{5}{4}},{|A_{1}|}^{\frac{1}{2}}{|A_{2}|}^{\frac{5}{2}}{|A_{3}|}^{\frac{5}{4}},{|A_{2}|}^{2}{|A_{3}|}^{2}\right\\}\\\
&+{|A_{1}|}^{2}{|A_{2}|}^{\frac{5}{4}}{|A_{3}|}^{\frac{5}{4}}+{|A_{1}|}^{\frac{3}{2}}{|A_{2}|}^{\frac{3}{2}}{|A_{3}|}^{\frac{5}{4}}+{|A_{1}|}^{\frac{3}{2}}{|A_{2}|}^{\frac{11}{4}}\\\
\lesssim&\min\left\\{|A_{1}|{|A_{2}|}^{\frac{9}{4}}{|A_{3}|}^{\frac{5}{4}},{|A_{1}|}^{\frac{1}{2}}{|A_{2}|}^{\frac{5}{2}}{|A_{3}|}^{\frac{5}{4}},{|A_{2}|}^{2}{|A_{3}|}^{2}\right\\}\\\
&+{|A_{1}|}^{2}{|A_{2}|}^{\frac{5}{4}}{|A_{3}|}^{\frac{5}{4}}+{|A_{1}|}^{\frac{3}{2}}{|A_{2}|}^{\frac{3}{2}}{|A_{3}|}^{\frac{5}{4}}.\end{split}$

As for the estimate of $T(A_{1},A_{2},A_{3})$, consider those terms which are
counted by $T(A_{1},A_{2},A_{3})$ but not by $T^{o}(A_{1},A_{2},A_{3})$. For
$(a_{1},a_{2})\in{A_{1}}^{2},(b_{1},b_{2})\in{A_{2}}^{2},(c_{1},c_{2})\in{A_{3}}^{2}$
with

$(b_{1}-a_{1})(c_{2}-a_{2})=(c_{1}-a_{1})(b_{2}-a_{2}),$ (31)

if they are distinct and collinear, then $a_{1}\neq b_{1},a_{1}\neq c_{1}$,
and $b_{1}\neq c_{1}$. On the other hand, if $a_{1}=b_{1}$, there are at most

$|A_{1}\cap A_{2}\cap A_{3}||A_{1}||A_{2}||A_{3}|+{|A_{1}\cap
A_{2}|}^{2}{|A_{3}|}^{2}$

solutions to the equation (31). For the case $a_{1}=c_{1}$ and $b_{1}=c_{1}$,
we have the bound

$|A_{1}\cap A_{2}\cap A_{3}||A_{1}||A_{2}||A_{3}|+{|A_{1}\cap
A_{3}|}^{2}{|A_{2}|}^{2}$

and

$|A_{1}\cap A_{2}\cap A_{3}||A_{1}||A_{2}||A_{3}|+{|A_{2}\cap
A_{3}|}^{2}{|A_{1}|}^{2}\text{, respectively.}$

To sum up, we have
$T(A_{1},A_{2},A_{3})-T^{o}(A_{1},A_{2},A_{3})\ll{|A_{1}|}^{2}{|A_{3}|}^{2}$.
∎

###  4.2 The number of bisectors in a subset of
${\left(\faktor{\mathbb{Z}}{p^{3}\mathbb{Z}}\right)}^{2}$

While working on problems about distances between pairs of points in a given
point set $\mathcal{P}\subseteq\mathbb{R}^{2}$, it is natural to ask the total
number of possible bisectors and the incidence relation between them.
Moreover, Hanson, Lund, and Roche-Newton generalized this question in
$\mathbb{F}_{p}^{2}$ in [17]. To start with, for a vector
$x=(x_{1},x_{2})\in\mathbb{F}_{p}^{2}$, define

$\|x\|\equiv{x_{1}}^{2}+{x_{2}}^{2}\mod p$

and for two points $x,y\in\mathbb{F}_{p}^{2}$, call $\|x-y\|$ as the
“distance” between them. Notice that although this distance is not a norm
(even not a metric) in the mathematical sense, it still preserves several
structures of $\mathbb{F}_{p}^{2}$. Next, the authors defined the
“perpendicular bisector” between two points $x,y\in\mathbb{F}_{p}^{2}$ to be

$B(x,y):=\\{z\in\mathbb{F}_{p}^{2}\mid\|z-x\|=\|z-y\|\\}$

and for a point set $\mathcal{P}\subseteq\mathbb{F}_{p}^{2}$, define

$B(\mathcal{P}):=\\{B(x,y)\mid x,y\in\mathcal{P}\\}.$

After these settings, in [17], the authors proved the following theorem:

######  Theorem 4.2.1 (Theorem 1, [17]).

If a point set $\mathcal{P}\subseteq\mathbb{F}_{p}^{2}$ with $|\mathcal{P}|\gg
p^{\frac{3}{2}}$, then

$|B(\mathcal{P})|\gg p^{2}.$

In other words, the order of their perpendicular bisector is as large as the
order of all lines.

One of my research projects is to extend this result to more general settings.
However, it turns out it is a difficult problem to obtain a similar result as
in $\mathbb{F}_{p}$ because losing the structure of being a field creates many
difficult problems. We now consider point sets in
${\left(\faktor{\mathbb{Z}}{p^{3}\mathbb{Z}}\right)}^{2}$ where $p$ is a
Gaussian prime, instead of in $\mathbb{F}_{p}^{2}$. In the following text, we
denote $\faktor{\mathbb{Z}}{p^{3}\mathbb{Z}}$ as $\mathbb{Z}_{p^{3}}$ or
$\mathbb{Z}_{q}$, where $q=p^{3}$, for simplicity. The reason why we choose
$\mathbb{Z}_{q}^{2}$ out of the general case
${\left(\faktor{\mathbb{Z}}{n\mathbb{Z}}\right)}^{2}$ is that we want to
reduce the number of solutions to $\|x\|=0$, which would be very annoying if
there are too many solutions. Notice that the above definition of $\|\cdot\|$,
“distance,” and “perpendicular bisector” are also valid in the case of
$\mathbb{Z}_{q}^{2}$. Our study in this scope is the following result in
$\operatorname{\mathbb{Z}}_{q}^{2}$ which is based on a conjecture that I made
which I believe to be true.

######  Theorem 4.2.2.

Assume that Conjecture 4.2.10 holds. For any $m>\frac{5}{3}$ and point set
$\mathcal{P}\subseteq\operatorname{\mathbb{Z}}_{q}^{2}$ with $|\mathcal{P}|\gg
q^{m}$, we have

$|B(\mathcal{P})|\gg q^{2(m-1)}.$

To prove this theorem, let us start with several fundamental geometric
definitions in $\mathbb{Z}_{q}^{2}$.

######  Definition 4.2.3 (rotation, reflection, and translation).

  1. 1.

A matrix of the form

$\begin{pmatrix}a&-b\\\ b&a\end{pmatrix},a^{2}+b^{2}=1$

is called a rotation matrix. For $u\in\mathbb{Z}_{q}^{2}$ and $R$ is a
rotation matrix, then a rotation about $u$ is an affine map of the form

$\mathcal{R}:v\mapsto R(v-u)+u.$

  2. 2.

A matrix of the form

$\begin{pmatrix}a&b\\\ b&-a\end{pmatrix},a^{2}+b^{2}=1$

is called a reflection matrix. A reflection about $u$ by a reflection matrix
$S$ is an affine map of the form

$\mathcal{S}:v\mapsto S(v-u)+u.$

  3. 3.

A translation by $u$ is an affine map of the form

$\mathcal{T}:v\mapsto v+u.$

We call a translation non-trivial if $u\neq 0$.

######  Definition 4.2.4 (non-isotropic).

A line $l:ax+by=c$ is called non-isotropic if $a,b$, and $a^{2}+b^{2}$ are
units. Otherwise, it is isotropic.

Based on these definitions above, we followed the steps of Hanson, Lund, and
Roche-Newton and modified their proving techniques to generalize their results
into the case of $\operatorname{\mathbb{Z}}_{q}^{2}$. To prove the main
theorem, we need the following Lemma 4.2.5 to Lemma 4.2.8. However, because
their proof will need more fundamental lemmas, we move their proofs to
Appendix C. for the sake of fluency.

######  Lemma 4.2.5.

For $d\in\operatorname{\mathbb{Z}}_{q}$, let $Q(d)$ be the number of solutions
to $x^{2}\equiv d\mod q$.

$Q(d)=\begin{cases}2&\text{if }\genfrac{(}{)}{}{}{d}{p}=1\\\ 0&\text{if
}\genfrac{(}{)}{}{}{d}{p}=-1\\\ 0&\text{if }p\mid d\text{ and }p^{2}\nmid d\\\
2p&\text{if }p^{2}\mid d\text{ and }\genfrac{(}{)}{}{}{d/p^{2}}{p}=1\\\
0&\text{if }p^{2}\mid d\text{ and }\genfrac{(}{)}{}{}{d/p^{2}}{p}=-1\\\
p&\text{if }d=0\end{cases}$

where $\genfrac{(}{)}{}{}{d}{p}$ is the Legendre symbol.

######  Lemma 4.2.6.

If $x,y,z,w\in\mathbb{Z}_{q}^{2}$ are such that $B=B(x,z)=B(y,w)$ is non-
isotropic then

$\|x-y\|=\|z-w\|.$

######  Lemma 4.2.7.

For a given point $u\in\mathbb{Z}_{q}^{2}$ with $q=p^{3}$, there are
$p^{3}-p^{2}$ non-isotropic lines passing $u$.

######  Lemma 4.2.8.

Suppose $u\in\mathbb{Z}_{q}^{2}$ and $\rho\in\mathbb{Z}_{q}$. Then, we have:

$|C_{\rho}(u)|=\begin{cases}p^{2}&\text{if }\rho\equiv 0,\\\
p^{3}+p^{2}&\text{if }\rho\in p^{2}\operatorname{\mathbb{Z}}_{q}^{*},\\\
0&\text{if }\rho\in p\operatorname{\mathbb{Z}}_{q}^{*},\\\
p^{3}+p^{2}&\text{if }\rho\in\operatorname{\mathbb{Z}}_{q}^{*}.\end{cases}$

Define $D_{q,\rho}$ as the number of pairs
$(u_{1},u_{2})\in\operatorname{\mathbb{Z}}_{q}^{2}\times\operatorname{\mathbb{Z}}_{q}^{2}$
such that $\|u_{1}-u_{2}\|\equiv\rho$. Then, we have

$D_{q,\rho}=\begin{cases}p^{8}&\text{if }\rho\equiv 0,\\\ p^{9}+p^{8}&\text{if
}\rho\in p^{2}\operatorname{\mathbb{Z}}_{q}^{*},\\\ 0&\text{if }\rho\in
p\operatorname{\mathbb{Z}}_{q}^{*},\\\ p^{9}+p^{8}&\text{if
}\rho\in\operatorname{\mathbb{Z}}_{q}^{*}.\end{cases}$

After proving these lemmas, we faced a major problem that is much more
complicated when considering $\operatorname{\mathbb{Z}}_{q}^{2}$ rather than
$\operatorname{\mathbb{F}}_{p}^{2}$. To be more specific, in
$\operatorname{\mathbb{F}}_{p}^{2}$, Hanson, Lund, and Roche-Newton proved the
following lemma:

######  Lemma 4.2.9 (Lemma 7, [17]).

Given any point pairs
$x=(x_{1},x_{2})\in\mathbb{F}_{p}^{2}\times\mathbb{F}_{p}^{2}$ and
$y=(y_{1},y_{2})\in\mathbb{F}_{p}^{2}\times\mathbb{F}_{p}^{2}$ with
$\|x_{1}-x_{2}\|=\|y_{1}-y_{2}\|$, define $\mathcal{N}(x,y)$ to be the number
of pairs $(\mathcal{R}_{1},\mathcal{R}_{2})$ of reflections with
$y_{i}=\mathcal{R}_{2}\circ\mathcal{R}_{1}(x_{i})$ for $i=1,2$. Then,

$\mathcal{N}(x,y)=\begin{cases}p-1&\text{if }x_{1}-x_{2}\neq y_{1}-y_{2}\text{
and }p\equiv 1\mod 4,\\\ p+1&\text{if }x_{1}-x_{2}\neq y_{1}-y_{2}\text{ and
}p\equiv 3\mod 4,\\\ p&\text{if }x_{1}-x_{2}=y_{1}-y_{2}\text{ and
}\|x_{1}-y_{1}\|\neq 0,\\\ 0&\text{if }x_{1}-x_{2}=y_{1}-y_{2}\text{ and
}\|x_{1}-y_{1}\|=0.\end{cases}$

However, in $\operatorname{\mathbb{Z}}_{q}^{2}$, we have no criterion for the
$\mathcal{N}(x,y)$ value. This problem also explicitly shows how the structure
of $\operatorname{\mathbb{Z}}_{q}^{2}$ differs from the structure of
$\operatorname{\mathbb{F}}_{p}^{2}$. Fortunately, with the help of a computer
program, we directly calculated the distribution of $\mathcal{N}(x,y)$ for
small $p$ and made the conjecture as follows.

######  Conjecture 4.2.10.

Given any point pairs
$x=(x_{1},x_{2})\in\operatorname{\mathbb{Z}}_{q}^{2}\times\operatorname{\mathbb{Z}}_{q}^{2}$
and
$y=(y_{1},y_{2})\in\operatorname{\mathbb{Z}}_{q}^{2}\times\operatorname{\mathbb{Z}}_{q}^{2}$,
define $\mathcal{N}(x,y)$ to be the number of pairs
$(\mathcal{R}_{1},\mathcal{R}_{2})$ of reflections with
$y_{i}=\mathcal{R}_{2}\circ\mathcal{R}_{1}(x_{i})$ for $i=1,2$ and let

$\mathcal{A}_{x}(n):=\left|\\{y\mid\mathcal{N}(x,y)=n\\}\right|.$

Then, we have

$\begin{array}[]{lll}\mathcal{A}_{x}(p^{3}-3p^{2})=p^{9}-p^{8},&\mathcal{A}_{x}(p^{3}-p^{2})=p^{8},&\mathcal{A}_{x}(p^{3})=p^{8}-2p^{7}+p^{6},\\\
\mathcal{A}_{x}(p^{4}-p^{3})=p^{6}-p^{5},&\mathcal{A}_{x}(p^{4})=p^{5}-2p^{4}+p^{3},&\mathcal{A}_{x}(p^{5}-p^{4})=p^{3}-p^{2},\\\
\mathcal{A}_{x}(p^{5})=p^{2}-2p+1,&\mathcal{A}_{x}(p^{6}-p^{5})=1,&\mathcal{A}_{x}(n)=0\end{array}$

for all $n$ not mentioned above.

Assume that the above conjecture is true. Now, we introduce two well-known
theorems in graph theory and linear algebra that help us to finish the proof
of our main result.

######  Theorem 4.2.11 (Expander Mixing Lemma, [17]).

Let $G=(V,E)$ be a $\delta$-regular graph with $|V|=n$, and let $A$ be the
adjacency matrix for $G$. Suppose that the absolute values of all but the
largest eigenvalue of $A$ are bounded by $\lambda$. Suppose that $f,g\in
L^{2}(V)$. Then, we have

$|\langle f,Ag\rangle-\delta
n\mathbb{E}(f)\mathbb{E}(g)|\leq\lambda\|f\|\|g\|.$

Especially, for any $S,T\subseteq V$,

$\left|E(S,T)-\frac{\delta|S||T|}{n}\right|\leq\lambda\sqrt{|S||T|}$

where $E(S,T)$ is the number of edges between $S$ and $T$.

######  Theorem 4.2.12 (Gershgorin Circle Theorem, [18]).

Let $A=[A_{ij}]$ be an $n\times n$ matrix, and let
$r_{i}=\sum_{j=1}^{n}|a_{ij}|$ be the sum of the absolute values of the $i$-th
row of $A$. Then, for any eigenvalue $\lambda$ of $A$, there is a $1\leq i\leq
n$ such that $|\lambda-a_{ii}|\leq r_{i}$.

For simplicity, we declare some notations used in the later context:

######  Definition 4.2.13
($\widetilde{P},Q^{\prime},Q_{d}^{\prime},\Pi_{d}^{\prime}$).

Given a point set $P\subseteq\operatorname{\mathbb{Z}}_{q}^{2}$ and
$d\in\operatorname{\mathbb{Z}}_{q}^{*}$, define

$\begin{split}\widetilde{P}&:=\\{(x,y)\in P^{2}\mid x-y=(a_{1},a_{2})\text{
with }a_{1},a_{2}\in\operatorname{\mathbb{Z}}_{q}^{*}\\},\\\
Q^{\prime}=Q^{\prime}(P)&:=\\{(x,y,z,w)\in\widetilde{P}^{2}\mid
B(x,z)=B(y,w),B(x,z)\text{ is non-isotropic}\\},\\\
Q_{d}^{\prime}=Q_{d}^{\prime}(P)&:=\\{(x,y,z,w)\in
Q^{\prime}\mid\|x-y\|=\|z-w\|=d\\},\\\
\Pi_{d}^{\prime}=\Pi_{d}^{\prime}(P)&:=\\{(x,y)\in\widetilde{P}\mid\|x-y\|=d\\}.\end{split}$

With this notation and the assumption of Conjecture 4.2.10, we can prove the
following proposition, which is the most important part of the proof of the
main theorem. A similar result for the $\operatorname{\mathbb{F}}_{p}^{2}$
case can be found in Proposition 12 in [17].

######  Proposition 4.2.14.

If Conjecture 4.2.10 is correct, for any
$d\in\operatorname{\mathbb{Z}}_{q}^{*}$, we have

$|Q_{d}^{\prime}|\ll\frac{{|\Pi_{d}^{\prime}|}^{2}}{p^{3}}+p^{5}|\Pi_{d}^{\prime}|.$

###### Proof.

Let $G=(V,E)$ be a graph with

$V:=\\{x=(x_{1},x_{2})\in\operatorname{\mathbb{Z}}_{q}^{2}\times\operatorname{\mathbb{Z}}_{q}^{2}\mid\|x_{1}-x_{2}\|=d\\}\Rightarrow|V|=p^{9}+p^{8}$

and

$\begin{split}E:=\\{\\{x,y\\}\mid&\hskip
5.0ptx=(x_{1},x_{2}),y=(y_{1},y_{2})\\\ &\hskip 10.00002pt\text{ with
}B(x_{1},y_{1})=B(x_{2},y_{2})\text{ is non-isotropic}\\}.\end{split}$

For a vertex $x\in V$, define $\Gamma(x)$ to be the neighborhood of $x$ and
notice that for any $x$, $|\Gamma(x)|$ is equal to the number of non-isotropic
lines. That is, $G$ is a $(p^{6}-p^{5})$-regular graph. Additionally, notice
that

$|\Gamma(x)\cap\Gamma(y)|=|\\{z\in\Gamma(x)\mid
y\in\Gamma(z)\\}|=\mathcal{N}(x,y).$

Let $A$ be the adjacency matrix of $G$. Then, the $(x,y)$-th entry of $A^{2}$

${(A^{2})}_{xy}=|\Gamma(x)\cap\Gamma(y)|=\mathcal{N}(x,y).$

By Conjecture 4.2.10, $A^{2}$ is a regular matrix. That is, for every row of
$A^{2}$, the sum of the absolute value of the entries in that row is the same.
Let $J$ be the all-1s matrix, $I$ be the identity matrix, and $E$ be the error
matrix with

$A^{2}=(p^{3}-3p^{2})J+(p^{6}-p^{5}-p^{3}+3p^{2})I+E.$

For the $x$-th row of $E$, the absolute row sum is

$\begin{split}\sum_{y\in
V}|E_{xy}|=&\left|{(A^{2})}_{xy}-(p^{3}-3p^{2})-(p^{6}-p^{5}-p^{3}+3p^{2})\delta_{x,y}\right|\\\
=&2p^{2}\times p^{8}+3p^{2}\times(p^{8}-2p^{7}+p^{6})\\\
&+(p^{4}-2p^{3}+3p^{2})\times(p^{6}-p^{5})\\\
&+(p^{4}-p^{3}+3p^{2})\times(p^{5}-2p^{4}+p^{3})\\\
&+(p^{5}-p^{4}-p^{3}+3p^{2})\times(p^{3}-p^{2})\\\
&+(p^{5}-p^{3}+3p^{2})\times(p^{2}-2p+1)\\\
&+(p^{3}-3p^{2})\times(2p^{7}-2p^{6}+2p^{4}-2p^{3}+2p-2)\\\
=&\Theta(p^{10}).\end{split}$

Additionally, every diagonal entry of $E$ vanishes, so for any eigenvalue
$\lambda_{E}$ of $E$, we have

$|\lambda_{E}|\ll p^{10}$ (32)

by Theorem 4.2.12.

Since $A$ is a regular matrix, the all-1s vector is an eigenvector of $A$.
Suppose that $v$ is an eigenvector of $A$, which is orthogonal to the all-1s
vector and $Av=\lambda v$. Then,

$Ev=(A^{2}-(p^{3}-3p^{2})J-(p^{6}-p^{5}-p^{3}+3p^{2})I)v=(\lambda^{2}-p^{6}+p^{5}+p^{3}-3p^{2})v.$

In other words, $v$ is an eigenvector of $E$ with eigenvalue
$\lambda^{2}-p^{6}+p^{5}+p^{3}-3p^{2}$. By Equation 32, we know that

$|\lambda^{2}-p^{6}+p^{5}+p^{3}-3p^{2}|\ll p^{10}\Rightarrow\lambda\ll p^{5}.$

Finally, we can use Theorem 4.2.11. Taking $S=T=\Pi_{d}^{\prime}$, we have

$E(\Pi_{d}^{\prime},\Pi_{d}^{\prime})\ll\frac{(p^{6}-p^{5}){|\Pi_{d}^{\prime}|}^{2}}{p^{9}+p^{8}}+p^{5}|\Pi_{d}^{\prime}|\ll\frac{{|\Pi_{d}^{\prime}|}^{2}}{p^{3}}+p^{5}|\Pi_{d}^{\prime}|.$

In the end, by definition, we have
$|Q_{d}^{\prime}|=E(\Pi_{d}^{\prime},\Pi_{d}^{\prime})$, so we finish the
proof. ∎

Next, the following lemma also demonstrates another difference between
$\operatorname{\mathbb{Z}}_{q}^{2}$ and $\mathbb{F}_{p}^{2}$. After the proof
of Lemma 4.2.15, we will discuss the difference in the remark in detail.

######  Lemma 4.2.15.

For any point set $\mathcal{P}\subseteq\operatorname{\mathbb{Z}}_{q}^{2}$, we
have

$\sum_{d\in\operatorname{\mathbb{Z}}_{q}^{*}}{|\Pi_{d}^{\prime}(\mathcal{P})|}^{2}\ll\frac{{|\mathcal{P}|}^{4}}{q}+q^{3}{|\mathcal{P}|}^{2}.$

###### Proof.

For a $d\in\operatorname{\mathbb{Z}}_{q}^{*}$, consider a graph
$G_{d}=(V_{d},E_{d})$ with

$V_{d}=\operatorname{\mathbb{Z}}_{q}^{2}\times\operatorname{\mathbb{Z}}_{q}^{2}\text{
and }E_{d}=\\{\\{(x_{1},x_{2}),(y_{1},y_{2})\\}\subset
V\mid\|x_{1}-y_{1}\|=\|x_{2}-y_{2}\|=d\\}.$

Notice that by definition, we have
${|\Pi_{d}^{\prime}|}^{2}=E(\mathcal{P}\times\mathcal{P},\mathcal{P}\times\mathcal{P})$.
Now, we want to use Theorem 4.2.11 to obtain an upper bound of
$E(\mathcal{P}\times\mathcal{P},\mathcal{P}\times\mathcal{P})$. First, note
that $|V|=q^{4}$ and $G_{d}$ is a
${|C_{d}(0)|}^{2}={(p^{3}+p^{2})}^{2}$-regular graph by Lemma 4.2.8. Let $A$
be the adjacency matrix of $G$. By Theorem 4.2.12, every eigenvalue of $A$ is
bounded by

$\sum_{y\in A}|A_{xy}|={(p^{3}+p^{2})}^{2}.$

Combining them together, we obtain that

$\begin{split}&{|\Pi_{d}^{\prime}(\mathcal{P})|}^{2}\ll\frac{{(p^{3}+p^{2})}^{2}{|\mathcal{P}|}^{4}}{q^{4}}+{(p^{3}+p^{2})}^{2}{|\mathcal{P}|}^{2}\\\
&\Rightarrow\sum_{d\in\operatorname{\mathbb{Z}}_{q}^{*}}{|\Pi_{d}^{\prime}(\mathcal{P})|}^{2}\ll\frac{{|\mathcal{P}|}^{4}}{q}+q^{3}{|\mathcal{P}|}^{2}.\end{split}$

This completes our proof. ∎

######  Remark 4.2.16.

It is easy to see that in the above proof, the bound of the second-largest
eigenvalue of $A$ is quite bad. ${(p^{3}+p^{2})}^{2}$ is its largest
eigenvalue, which is also the trivial one. However, due to the structure of
$G_{d}$, it is difficult to apply the skill we used in Proposition 4.2.14.
That is, decomposing $A^{2}$ into the linear combination of $J,I$, and an
error matrix $E$ (as Hanson, Lund, and Roche-Newton did in [17]) does not help
us. For a reason, in short, both the numbers of entries in a given row of
$A^{2}$ equal to 0 and 2, respectively, are about $q^{2}$. Since they have
almost the same amount, we cannot set a proper coefficient for $J$ such that
the row sum of the error matrix is properly bounded. Therefore, the technique
improves nothing more than coefficients.

As a result, I am looking for another skill to obtain a statement like

$\sum_{d\in\operatorname{\mathbb{Z}}_{q}^{*}}{|\Pi_{d}^{\prime}(\mathcal{P})|}^{2}\ll\frac{{|\mathcal{P}|}^{4}}{q}+q^{3-\epsilon}{|\mathcal{P}|}^{2},\forall\,\mathcal{P}\subseteq\operatorname{\mathbb{Z}}_{q}^{*}$

for some constant $\epsilon>0$. If such a statement and Conjecture 4.2.10
hold, we could get a theorem in the same form as Theorem 4.2.1:

> For any $\mathcal{P}\subseteq\operatorname{\mathbb{Z}}_{q}^{2}$ with
> $|\mathcal{P}|\gg q^{\alpha}$, we have $B(\mathcal{P})\gg q^{2}$ for some
> non-trivial constant $\alpha$. i.e. $\alpha<2$.

Now, with the help of Lemma 4.2.15, we can prove the following lemma. This
lemma is the final step before proving our main goal in this section, Theorem
4.2.2.

######  Lemma 4.2.17.

If Conjecture 4.2.10 is correct, then for any point set
$\mathcal{P}\subset\operatorname{\mathbb{Z}}_{q}^{2}$,

$|Q^{\prime}(\mathcal{P})|\ll\frac{{|\mathcal{P}|}^{4}}{q^{2}}+q^{2}{|\mathcal{P}|}^{2}.$

###### Proof.

By definition of $Q^{\prime}$, we know that

$|Q^{\prime}|=\sum_{d\in\operatorname{\mathbb{Z}}_{q}^{*}}|Q_{d}^{\prime}|.$

Together with Proposition 4.2.14 and Lemma 4.2.15, we get

$\begin{split}|Q^{\prime}|\ll\sum_{d\in\operatorname{\mathbb{Z}}_{q}^{*}}\left(\frac{{|\Pi_{d}^{\prime}|}^{2}}{q}+q^{\frac{5}{3}}|\Pi_{d}^{\prime}|\right)\ll\frac{{|\mathcal{P}|}^{4}}{q^{2}}+q^{2}{|\mathcal{P}|}^{2}+q^{\frac{5}{3}}{|\mathcal{P}|}^{2}\ll\frac{{|\mathcal{P}|}^{4}}{q^{2}}+q^{2}{|\mathcal{P}|}^{2}.\end{split}$

∎

Finally, everything is ready. Let us demonstrate the proof of our main goal.

###### Proof of Theorem 4.2.2.

For a non-isotropic line $l\in B(\mathcal{P})$, define its multiplicity $w(l)$
to be the number of pairs $(x,y)\in\mathcal{P}^{2}$ with $B(x,y)=l$. Then we
know that

$\sum_{l\in B(P)}w(l)=\left|\widetilde{\mathcal{P}}\right|.$

Since $|\mathcal{P}|\gg q^{\frac{5}{3}}$,
$\left|\widetilde{\mathcal{P}}\right|=\Theta\left({|\mathcal{P}|}^{2}\right)$.
Therefore, by Cauchy-Schwarz inequality, we have

${|\mathcal{P}|}^{4}\ll{\left(\sum_{l\in
B(\mathcal{P})}w(l)\right)}^{2}\leq|B(\mathcal{P})|\left(\sum_{l\in
B(\mathcal{P})}{w(l)}^{2}\right)=|B(\mathcal{P})||Q^{\prime}(\mathcal{P})|.$

Together with Lemma 4.2.17, we have

$|B(\mathcal{P})|\gg\frac{{|\mathcal{P}|}^{4}}{\frac{{|\mathcal{P}|}^{4}}{q^{2}}+q^{2}{|\mathcal{P}|}^{2}}\Rightarrow|B(\mathcal{P})|\gg
q^{-2}{|\mathcal{P}|}^{2}\gg q^{2(m-1)}.$

∎

## Appendix A. Proof of Szemerédi-Trotter Theorem

######  Recall (Szemerédi-Trotter Theorem).

On Euclidean plane $\mathbb{R}^{2}$, given a point set $\mathcal{P}$ and a
line set $\mathcal{L}$, then the number of their incidences

$\mathcal{I}(\mathcal{P},\mathcal{L})=O\left({|\mathcal{P}|}^{\frac{2}{3}}{|\mathcal{L}|}^{\frac{2}{3}}+|\mathcal{P}|+|\mathcal{L}|\right).$

Theorem 2.1.1 is first proved by Szemerédi and Trotter in 1983. But the
technique is so complicated, so we decide to use another way to prove it. The
following proof is provided by Székely (1997, [16]).

###### Proof of Theorem 2.1.1.

First, we may discard lines that contain two or fewer points since they can
provide at most $2|\mathcal{L}|$ incidences in total. For any line
$l\in\mathcal{L}$ containing $k_{l}$ points in $\mathcal{P}$, these $k_{l}$
points will cut the line into $k_{l}-1$ segments.

Consider a graph $G=(V,E)$ with $V=\mathcal{P}$ and for any $x,y\in V$,
$\\{x,y\\}\in E$ if and only if $x,y$ are two endpoints of a segment mentioned
above. Notice that any two lines intersect in at most one point, so the
crossing number of $G$ is at most $\frac{|\mathcal{L}|(|\mathcal{L}|-1)}{2}$.
By the crossing number inequality, we know that

$\frac{|\mathcal{L}|(|\mathcal{L}|-1)}{2}\geq\frac{{|E|}^{3}}{64{|V|}^{2}}\text{
or }|E|\leq 4|\mathcal{P}|.$ (33)

By construction, we know that

$|E|=\sum_{l\in\mathcal{L}}(k_{l}-1)\geq\frac{1}{2}\sum_{l\in\mathcal{L}}k_{l}=\frac{1}{2}\mathcal{I}(\mathcal{P},\mathcal{L}).$

Together with Equation (33), we have

$\mathcal{I}(\mathcal{P},\mathcal{L})\leq
2|E|\ll|\mathcal{P}|+{|\mathcal{L}|}^{\frac{2}{3}}{|\mathcal{P}|}^{\frac{2}{3}}.$

This completes our proof. ∎

## Appendix B. Proof of Szemerédi-Trotter Type Theorem in Finite Field

######  Recall (Szemerédi-Trotter type Theorem in $\mathbb{F}_{p}$, [10]).

On $\mathbb{F}_{p}^{2}$ where $p$ is a prime, given a point set
$\mathcal{P}=A\times B$ and a line set $\mathcal{L}$ with

$|A|\leq|B|,|A|{|B|}^{2}\leq{|\mathcal{L}|}^{3}\text{, and
}|A||\mathcal{L}|\ll p^{2}$

then the number of their incidences

$\mathcal{I}(A\times
B,\mathcal{L})=O\left({|A|}^{\frac{3}{4}}{|B|}^{\frac{1}{2}}{|\mathcal{L}|}^{\frac{3}{4}}+|\mathcal{L}|\right).$

###### Proof of Theorem 3.1.1.

First, because of the order of the upper bound, we can modify $\mathcal{L}$ as
follows: (In other words, we can remove or add these lines without affecting
the correctness of the statement.)

  1. 1.

Remove all vertical lines in $\mathcal{L}$:
For those vertical lines in $\mathcal{L}$, they at most contribute $|A||B|$
incidences. Since $|A|{|B|}^{2}\leq{|\mathcal{L}|}^{3}$,
$|A||B|\leq{|A|}^{\frac{3}{4}}{|B|}^{\frac{1}{2}}{|\mathcal{L}|}^{\frac{3}{4}}$.
Thus, the incidence made by vertical lines will not play a crucial role.

  2. 2.

We may assume ${|B|}^{2}\leq|A||\mathcal{L}|$:
Since there is no vertical line, we have $\mathcal{I}(A\times
B,\mathcal{L})\leq|A||\mathcal{L}|$. Assume ${|B|}^{2}>|A||\mathcal{L}|$. Then
it is clear that

$\mathcal{I}(A\times
B,\mathcal{L})\leq|A||\mathcal{L}|\leq{|A|}^{\frac{3}{4}}{|B|}^{\frac{1}{2}}{|\mathcal{L}|}^{\frac{3}{4}}$

and thus the Theorem 3.1.1 holds.

  3. 3.

At most ${|A|}^{\frac{1}{2}}{|\mathcal{L}|}^{\frac{1}{2}}$ lines are parallel
or concurrent (i.e. passing the same point):
We iteratively remove a set of parallel or concurrent lines with a size
greater than ${|A|}^{\frac{1}{2}}{|\mathcal{L}|}^{\frac{1}{2}}$. Suppose that
in $i$-th step, we remove $n_{i}$ lines. Then, these $n_{i}$ lines contribute
at most $|A||B|+n_{i}$ incidences and we need at most
$\frac{|\mathcal{L}|}{{|A|}^{\frac{1}{2}}{|\mathcal{L}|}^{\frac{1}{2}}}=\frac{{|\mathcal{L}|}^{\frac{1}{2}}}{{|A|}^{\frac{1}{2}}}$
steps. After these steps, we remove at most

$\frac{{|\mathcal{L}|}^{\frac{1}{2}}}{{|A|}^{\frac{1}{2}}}\times|A||B|+\sum
n_{i}\ll{|A|}^{\frac{3}{4}}{|B|}^{\frac{1}{2}}{|\mathcal{L}|}^{\frac{3}{4}}+|\mathcal{L}|$

incidences since ${|B|}^{2}\leq|A||\mathcal{L}|$.

Since $\mathcal{L}$ has no vertical lines, the affine dual

$\mathcal{L}^{*}:=\\{(c,d)\in\mathbb{F}_{p}^{2}\mid l:y=cx+d\in\mathcal{L}\\}$

of $\mathcal{L}$ is well-defined. Then, we have the relation

$\mathcal{I}(\mathcal{P},\mathcal{L})=\left|\\{(a,b,c,d)\in A\times
B\times\mathcal{L}^{*}\mid b=ca+d\\}\right|.$

If we set

$E:=\\{(a,c,d,a^{\prime},c^{\prime},d^{\prime})\in{(A\times\mathcal{L}^{*})}^{2}\mid
ca+d=c^{\prime}a^{\prime}+d^{\prime}\\},$

then by Cauchy-Schwarz inequality and the above relation, we have

$\mathcal{I}(\mathcal{P},\mathcal{L})\leq{|B|}^{\frac{1}{2}}{|E|}^{\frac{1}{2}}.$

Next, we will bound $|E|$ with Theorem 3.3.1. Define a point set and a plane
set by

$\mathcal{P}^{\prime}=\\{(a,c,d)\in
A\times\mathcal{L}^{*}\\},\Pi=\\{\pi:cx+d=ay+z\mid a\in
A,(c,d)\in\mathcal{L}^{*}\\}.$

Then, we have $|\mathcal{P}^{\prime}|=\Pi=|A||\mathcal{L}|$ and
$|E|=\mathcal{I}(\mathcal{P}^{\prime},\Pi)$. Now, via our modification above,
$\mathcal{P}^{\prime}$ and $\mathcal{L}$ satisfy the condition mentioned in
Theorem 3.3.1 with

$k\leq{|A|}^{\frac{1}{2}}{|\mathcal{L}|}^{\frac{1}{2}}.$

Hence, by Theorem 3.3.1,

$\mathcal{I}(\mathcal{P}^{\prime},\Pi)\ll{|A|}^{\frac{3}{2}}{|\mathcal{L}|}^{\frac{3}{2}}.$

To sum up, we know that

$\mathcal{I}(\mathcal{P},\mathcal{L})\leq{|B|}^{\frac{1}{2}}{|E|}^{\frac{1}{2}}\ll{|A|}^{\frac{3}{4}}{|B|}^{\frac{1}{2}}{|\mathcal{L}|}^{\frac{3}{4}},$

which completes the proof. ∎

## Appendix C. Proofs of Lemmas Describing Properties about
$\operatorname{\mathbb{Z}}_{q}$

In this Appendix, we will introduce Lemma C.1 to Lemma C.3 and use them to
prove Lemma 4.2.5 to Lemma 4.2.8 in Section 4.2.

###### Lemma C.1.

Suppose that $x\in\operatorname{\mathbb{Z}}_{q}^{2}$ and $\mathcal{S}$ is a
reflection that does not fix $x$. Then the fixed line of $\mathcal{S}$ is
$B(x,\mathcal{S}(x))$. Moreover, a good line $l$ is the fixed line of a unique
reflection if and only if it is non-isotropic. If
$y\in\operatorname{\mathbb{Z}}_{q}^{2}$ is any point such that
$\|x-y\|\not\equiv 0$ and the line passing $x$ and $y$ is good, then $B(x,y)$
is non-isotropic, and there is a unique reflection $\mathcal{S}$ such that
$\mathcal{S}(x)=y$ which fixes $B(x,y)$.

###### Proof.

Observe that if $u$ is fixed by $\mathcal{S}$ then

$\|x-u\|=\|\mathcal{S}(x)-\mathcal{S}(u)\|=\|\mathcal{S}(x)-u\|$

so that $u\in B\big{(}x,\mathcal{S}(x)\big{)}$. Additionally, the fixed part
of $\mathcal{S}$ formed a line, so the fixed part of $\mathcal{S}$ is
$B\big{(}x,\mathcal{S}(x)\big{)}$.

Let $u_{1}$ and $u_{2}$ be any distinct points on the line $l$, which is
assumed to be non-isotropic. Set $d=(d_{1},d_{2}):=u_{1}-u_{2}$. The
reflection $\mathcal{S}$ by

$\frac{1}{d_{1}^{2}+d_{2}^{2}}\begin{pmatrix}d_{1}^{2}-d_{2}^{2}&2d_{1}d_{2}\\\
2d_{1}d_{2}&d_{2}^{2}-d_{1}^{2}\end{pmatrix}$

about $u_{1}$ fixes $l$. If there is another reflection $\mathcal{S}^{\prime}$
fixing $l$, then $\mathcal{S}\circ\mathcal{S}^{\prime}$ would be either a
rotation or a translation and $\mathcal{S}\circ\mathcal{S}^{\prime}$ fixes a
line, so $\mathcal{S}=\mathcal{S}^{\prime}$. In other words, such reflection
is unique.

Finally, suppose that $y\in\operatorname{\mathbb{Z}}_{q}^{2}$ is distinct from
$x$ with the line $l$ passing $x$ and $y$ being good. Since $p\equiv 3\mod 4$,
$B(x,y)$ is always non-isotropic. ∎

###### Lemma C.2.

Let $x,y\in C_{\rho}(u)$ for elements
$x,y,u\in\operatorname{\mathbb{Z}}_{q}^{2}$ and
$\rho\in\operatorname{\mathbb{Z}}_{q}^{*}$. There is a unique rotation
$\mathcal{R}$ fixing $u$ and sending $x$ to $y$.

###### Proof.

After applying a translation, we may assume $u=0$. Then, we have
$\|x\|=\|y\|\in\operatorname{\mathbb{Z}}_{q}^{*}$. Let $x=(x_{1},x_{2})$ and
$y=(y_{1},y_{2})$. Solve a rotation matrix $R$ with

$Rx=y\Rightarrow\begin{pmatrix}a&-b\\\ b&a\end{pmatrix}\begin{pmatrix}x_{1}\\\
x_{2}\end{pmatrix}=\begin{pmatrix}y_{1}\\\
y_{2}\end{pmatrix}\Rightarrow\begin{pmatrix}x_{1}&-x_{2}\\\
x_{2}&x_{1}\end{pmatrix}\begin{pmatrix}a\\\
b\end{pmatrix}=\begin{pmatrix}y_{1}\\\ y_{2}\end{pmatrix}.$

Since $\|x\|\in\operatorname{\mathbb{Z}}_{q}^{*}$, there is a unique solution
$(a,b)$. Additionally,

$a^{2}+b^{2}=\frac{1}{\rho}\left({(ax_{1}-bx_{2})}^{2}+{(bx_{1}+ax_{2})}^{2}\right)=\frac{1}{\rho}(y_{1}^{2}+y_{2}^{2})=1.$

Thus, such a rotation exists. If there is another rotation $R^{\prime}$ with
the same property, then the rotation $R^{-1}\circ R^{\prime}$ fixes $x$ and
$u$, so $R=R^{\prime}$. That is, such rotation is unique. ∎

###### Lemma C.3.

Suppose that $x,y,z,w\in\operatorname{\mathbb{Z}}_{q}^{2}$ such that
$(x,y)\neq(z,w)$ and

$\|x-y\|=\|z-w\|\in\operatorname{\mathbb{Z}}_{q}^{*}.$

If $x-y\neq z-w$, then there is a unique rotation $\mathcal{R}$ with
$\mathcal{R}(x)=z$ and $\mathcal{R}(y)=w$. If $x-y=z-w$, then there is no
rotation $\mathcal{R}$ with $\mathcal{R}(x)=z$ and $\mathcal{R}(y)=w$.

###### Proof.

Divide it into two cases:

  1. 1.

Assume $x-y\neq z-w$. Let $\mathcal{T}$ be the translation by $z-x$. i.e.
$\mathcal{T}(x)=z$. Note that

$\|z-w\|=\|x-y\|=\|\mathcal{T}(x)-\mathcal{T}(y)\|=\|z-\mathcal{T}(y)\|.$

Thus, $\mathcal{T}(y)$ and $w$ are on a common circle with an invertible
radius and are centered at $z$. By Lemma Lemma, there is a non-trivial
rotation $\mathcal{R}$ with $\mathcal{R}\circ\mathcal{T}(y)=w$. Then
$\mathcal{R}^{\prime}=\mathcal{R}\circ\mathcal{T}$ is the desired rotation.
Additionally, if there is another non-trivial rotation
$\mathcal{R}^{\prime\prime}$ with $\mathcal{R}^{\prime\prime}(x)=z$ and
$\mathcal{R}^{\prime\prime}(y)=w$. Then,
${\mathcal{R}^{\prime}}^{-1}\circ\mathcal{R}^{\prime\prime}$ is a rotation fix
$x,y$. In other words, the rotation is unique.

  2. 2.

Assume $x-y=z-w$. Similarly, let $\mathcal{T}$ be the translation by $z-x$.
i.e. $\mathcal{T}(x)=z$ and $\mathcal{T}(y)=w$. Assume that $\mathcal{R}$ is a
rotation with $\mathcal{R}(x)=z$ and $\mathcal{R}(y)=w$. Then,
$\mathcal{R}^{-1}\circ\mathcal{T}$ is a non-trivial rotation fixing $x,y$,
which leads to a contradiction.

∎

###### Proof of Lemma 4.2.5.

Let $x=x_{1}p^{2}+x_{2}p+x_{3}$ with $x_{i}\in\operatorname{\mathbb{F}}_{p}$.
Notice that

$x^{2}\equiv(2x_{1}x_{3}+{x_{2}}^{2})p^{2}+2x_{2}x_{3}p+{x_{3}}^{2}\mod q.$

Divide it into six cases:

  1. 1.

If $\genfrac{(}{)}{}{}{d}{p}=1$, then there are two nonzero solutions to
${x_{3}}^{2}\equiv d\mod p$. Next, fixed $x_{3}$, there is a unique solution
for $x_{2}$ to

$2x_{2}x_{3}+\left\lfloor\frac{{x_{3}}^{2}}{p}\right\rfloor\equiv\left\lfloor\frac{d}{p}\right\rfloor\mod
p.$

In the end, fixed $x_{2},x_{3}$, there is also a unique solution for $x_{1}$
to

$2x_{1}x_{3}+{x_{2}}^{2}+\left\lfloor\frac{2x_{2}x_{3}p+{x_{3}}^{2}}{p^{2}}\right\rfloor\equiv\left\lfloor\frac{d}{p^{2}}\right\rfloor\mod
p.$

To sum up, there are two solutions to $x^{2}\equiv d\mod q$.

  2. 2.

If $\genfrac{(}{)}{}{}{d}{p}=-1$, then there is no solution to
${x_{3}}^{2}\equiv d\mod p$ and thus $Q(d)=0$.

  3. 3.

If $p\mid d$ and $p^{2}\nmid d$, then note that

$x^{2}\equiv 2x_{2}x_{3}p+{x_{3}}^{2}\equiv d\mod p^{2}.$

Since $x_{3}=0$, $d\equiv 0\mod p^{2}$. This results in a contradiction, so
$Q(d)=0$.

  4. 4.

If $p^{2}\mid d$ and $\genfrac{(}{)}{}{}{d/p^{2}}{p}=1$, then solve
${x_{3}}^{2}\equiv d\mod p$. We know that $x_{3}=0$. Also, solve

$\begin{split}&2x_{1}x_{3}+{x_{2}}^{2}+\left\lfloor\frac{2x_{2}x_{3}p+{x_{3}}^{2}}{p^{2}}\right\rfloor\equiv\frac{d}{p^{2}}\mod
p\\\ &\Rightarrow{x_{2}}^{2}\equiv\frac{d}{p^{2}}\mod p\end{split}$

This has 2 solutions for $x_{2}$; for both values, $x_{1}$ can take arbitrary
value in $\operatorname{\mathbb{F}}_{p}$, so there are $2p$ solutions in
total.

  5. 5.

If $p^{2}\mid d$ and $\genfrac{(}{)}{}{}{d/p^{2}}{p}=-1$, then consider

$\begin{split}&2x_{1}x_{3}+{x_{2}}^{2}+\left\lfloor\frac{2x_{2}x_{3}p+{x_{3}}^{2}}{p^{2}}\right\rfloor\equiv\frac{d}{p^{2}}\mod
p\\\ &\Rightarrow{x_{2}}^{2}\equiv\frac{d}{p^{2}}\mod p\end{split}$

This has no solution for $x_{2}$ in $\operatorname{\mathbb{F}}_{p}$.

  6. 6.

If $d=0$, then consider

$(2x_{1}x_{3}+{x_{2}}^{2})p^{2}+2x_{2}x_{3}p+{x_{3}}^{2}\equiv 0\mod q.$

Then, we have $x_{3}=0,x_{2}=0$, and $x_{1}$ can be arbitrary elements in
$\operatorname{\mathbb{F}}_{p}$, so there are $p$ solutions in total.

∎

###### Proof of Lemma 4.2.6.

Assume that the bisector $B:ax+by=c$. After rescaling and shifting, we may
also assume that $c=0$ and $a^{2}+b^{2}=1$. Let $\mathcal{S}$ be the
reflection according to $B$. Then, we know that $x=\mathcal{S}(z)$ and
$y=\mathcal{B}(w)$, so

$\|x-y\|=\|\mathcal{S}(z)-\mathcal{S}(w)\|=\|\mathcal{S}(z-w)\|=\|z-w\|.$

∎

###### Proof of Lemma 4.2.7.

For a good line $l$, its parametric form is $u+t(1,a)$ with
$t\in\mathbb{Z}_{q}$ and $a\in\operatorname{\mathbb{Z}}_{q}$ is a unit. Since
there are $p^{3}-p^{2}$ units in $\operatorname{\mathbb{Z}}_{q}$, there are
$p^{3}-p^{2}$ good lines. Furthermore, since $p\equiv 3\mod 4$, there is no
isotropic line. ∎

###### Proof of Lemma 4.2.8.

Divide it into three cases:

  1. 1.

Suppose that $\rho=0$. Consider the equation

$x^{2}+y^{2}\equiv 0\text{ where }x,y\in\operatorname{\mathbb{Z}}_{q}.$

Let $x=x_{1}p^{2}+x_{2}p+x_{3}$ and $y=y_{1}p^{2}+y_{2}p+y_{3}$ with
$x_{i},y_{i}\in\operatorname{\mathbb{F}}_{p}$. Then, we get $x_{3}\equiv
y_{3}\equiv 0$, $x_{2}\equiv y_{2}\equiv 0$, and $x_{1},y_{1}$ can be
arbitrary elements in $\operatorname{\mathbb{F}}_{p}$. Thus,

$|C_{0}(u)|=p^{2}$

  2. 2.

Suppose that $\rho=n_{1}p^{2}+n_{2}p$ with
$n_{i}\in\operatorname{\mathbb{F}}_{p}$ and at least one of them are non-zero.
Consider the equation

$x^{2}+y^{2}\equiv\rho\text{ where }x,y\in\operatorname{\mathbb{Z}}_{q}.$

Let $x=x_{1}p^{2}+x_{2}p+x_{3}$ and $y=y_{1}p^{2}+y_{2}p+y_{3}$ with
$x_{i},y_{i}\in\operatorname{\mathbb{F}}_{p}$. Then, we get $x_{3}\equiv
y_{3}\equiv 0$, and thus $n_{2}$ must be 0. To sum up,

$|C_{\rho}(u)|=\begin{cases}p^{3}+p^{2}&\text{if }n_{2}\equiv 0\\\ 0&\text{if
}n_{2}\not\equiv 0.\end{cases}$

  3. 3.

Suppose that $\rho=n_{1}p^{2}+n_{2}p+n_{3}$ with $n_{3}\not\equiv 0$. Consider
the equation

$x^{2}+y^{2}\equiv\rho\text{ where }x,y\in\operatorname{\mathbb{Z}}_{q}.$

Let $x=x_{1}p^{2}+x_{2}p+x_{3}$ and $y=y_{1}p^{2}+y_{2}p+y_{3}$ with
$x_{i},y_{i}\in\operatorname{\mathbb{F}}_{p}$. Then, there are $p+1$ pairs
$(x_{3},y_{3})$ satisfying

${x_{3}}^{2}+{y_{3}}^{2}\equiv n_{3}\mod p;$

there are $p$ pairs $(x_{2},y_{2})$ satisfying

$x_{2}x_{3}+y_{2}y_{3}+\left\lfloor\frac{{x_{3}}^{2}+{y_{3}}^{2}}{p}\right\rfloor\equiv
n_{2}\mod p$

if the rest coefficients are fixed (and $(x_{3},y_{3})\not\equiv(0,0)$); there
are $p$ pairs $(x_{1},y_{1})$ satisfying

$2x_{1}x_{3}+2y_{1}y_{3}+{x_{2}}^{2}+{y_{2}}^{2}+\left\lfloor\frac{2x_{2}x_{3}p+2y_{2}y_{3}p+{x_{3}}^{2}+{y_{3}}^{2}}{p^{2}}\right\rfloor\equiv
n_{1}\mod p$

if the rest coefficients are fixed (and $(x_{3},y_{3})\not\equiv(0,0)$). To
sum up,

$|C_{\rho}(u)|=p^{3}+p^{2}.$

∎

## References

  * [1] Erdős, P., & Szemerédi, E. (1983). On sums and products of integers. Studies in pure mathematics: to the memory of Paul Turán, 213-218.
  * [2] Tao, T. (2008). The sum-product phenomenon in arbitrary rings. arXiv preprint arXiv:0806.2497.
  * [3] Chang, M. C., & Solymosi, J. (2007). Sum-product theorems and incidence geometry. Journal of the European Mathematical Society, 9(3), 545-560.
  * [4] Shkredov, I. D. (2023). On some multiplicative properties of large difference sets. arXiv preprint arXiv:2301.09206.
  * [5] Elekes, G. (1997). On the number of sums and products. Acta Arithmetica, 81(4), 365-367.
  * [6] Solymosi, J. (2009). Bounding multiplicative energy by the sumset. Advances in mathematics, 222(2), 402-408.
  * [7] Rudnev, M., & Stevens, S. (2022). An update on the sum-product problem. In Mathematical Proceedings of the Cambridge Philosophical Society (Vol. 173, No. 2, pp. 411-430). Cambridge University Press.
  * [8] Szemerédi, E., & Trotter, W. T. (1983). Extremal problems in discrete geometry. Combinatorica, 3, 381-392.
  * [9] Tao, T., & Vu, V. H. (2006). Additive combinatorics (Vol. 105). Cambridge University Press.
  * [10] Stevens, S., & De Zeeuw, F. (2017). An improved point‐line incidence bound over arbitrary fields. Bulletin of the London Mathematical Society, 49(5), 842-858.
  * [11] Murphy, B., Roche-Newton, O., & Shkredov, I. (2015). Variations on the sum-product problem. SIAM Journal on Discrete Mathematics, 29(1), 514-540.
  * [12] Dung, H. M. (2022). Reu report no. 5. unpublished.
  * [13] Xue, B. (2020). Asymmetric estimates and the sum-product problems. arXiv preprint arXiv:2005.09893.
  * [14] Rudnev, M. (2018). On the number of incidences between points and planes in three dimensions. Combinatorica, 38, 219-254.
  * [15] Bourgain, J., Katz, N., & Tao, T. (2004). A sum-product estimate in finite fields, and applications. Geometric & Functional Analysis GAFA, 14(1), 27-57.
  * [16] Székely, L. A. (1997). Crossing numbers and hard Erdős problems in discrete geometry. Combinatorics, Probability and Computing, 6(3), 353-358.
  * [17] Hanson, B., Lund, B., & Roche-Newton, O. (2016). On distinct perpendicular bisectors and pinned distances in finite fields. Finite Fields and Their Applications, 37, 240-264.
  * [18] Brualdi, R. A., & Mellendorf, S. (1994). Regions in the complex plane containing the eigenvalues of a matrix. The American Mathematical Monthly, 101(10), 975-985.