# Intersection patterns and incidence theorems

Thang Pham and Semin Yoo  University of Science, Vietnam National University,
Hanoi, Vietnam<EMAIL_ADDRESS>School of Computational Sciences,
Korea Institute for Advanced Study, Seoul, Republic of Korea
<EMAIL_ADDRESS>
###### Abstract.

Let $A$ and $B$ be sets in a finite vector space. In this paper, we study the
magnitude of the set $A\cap f(B)$, where $f$ runs through a set of
transformations. More precisely, we will focus on the cases that the set of
transformations is given by orthogonal matrices or orthogonal projections. One
of the most important contributions of this paper is to show that if
$A,B\subset\mathbb{F}_{q}^{d}$ satisfy some natural conditions then, for
almost every $g\in O(d)$, there are at least $\gg q^{d}$ elements
$z\in\mathbb{F}_{q}^{d}$ such that

$|A\cap(g(B)+z)|\sim\frac{|A||B|}{q^{d}}.$

This infers that $|A-gB|\gg q^{d}$ for almost every $g\in O(d)$. In the flavor
of expanding functions, with $|A|\leq|B|$, we also show that the image $A-gB$
grows exponentially. In two dimensions, the result simply says that if
$|A|=q^{x}$ and $|B|=q^{y}$, as long as $0<x\leq y<2$, then for almost every
$g\in O(2)$, we can always find $\epsilon=\epsilon(x,y)>0$ such that
$|A-gB|\gg|B|^{1+\epsilon}$. To prove these results, we need to develop new
and robust incidence bounds between points and rigid motions by using a number
of techniques including algebraic methods and discrete Fourier analysis. Our
results are essentially sharp in odd dimensions.

###### Key words and phrases:

Intersection, Group action, Rigid motion, Incidences, Distances

###### 2020 Mathematics Subject Classification:

52C10, 42B05, 11T23

###### Contents

  1. 1 Introduction
    1. 1.1 Intersection patterns I
    2. 1.2 Intersection patterns II
    3. 1.3 Incidences between points and rigid motions
    4. 1.4 Growth estimates under orthogonal matrices
    5. 1.5 Intersection pattern III
  2. 2 Preliminaries-key lemmas
    1. 2.1 Results over arbitrary finite fields
    2. 2.2 Results over prime fields
    3. 2.3 An extension for general sets
  3. 3 Warm-up incidence theorems
  4. 4 Incidence theorems: proofs
  5. 5 Intersection pattern I: proofs
  6. 6 Intersection pattern II: proofs
  7. 7 Growth estimates under orthogonal matrices: proofs
  8. 8 Intersection pattern III: proofs
  9. 9 Acknowledgements

##  1\. Introduction

Let $A$ and $B$ be compact sets in $\mathbb{R}^{d}$. One of the fundamental
problems in Geometric Measure Theory is to study the relations between the
Hausdorff dimensions of $A$, $B$, and $A\cap f(B)$, where $f$ runs through a
set of transformations.

This study has a long history in the literature. A classical theorem due to
Mattila [18, Theorem 13.11] or [19, Theorem 7.4] states that for Borel sets
$A$ and $B$ in $\mathbb{R}^{d}$ of Hausdorff dimension $s_{A}$ and $s_{B}$
with

$s_{A}+s_{B}>d~{}\mbox{and}~{}s_{B}>\frac{d+1}{2}$

and assume in addition that the Hausdorff measures satisfy
$\mathcal{H}^{s_{A}}(A)>0$ and $\mathcal{H}^{s_{B}}(B)>0$, then, for almost
every $g\in O(d)$, one has

$\mathcal{L}^{d}\left(\left\\{z\in\mathbb{R}^{d}\colon\dim_{H}(A\cap(z-gB))\geq
s_{A}+s_{B}-d\right\\}\right)>0.$

This result means that for almost every $g\in O(d)$, the set of $z$s such that
$\dim_{H}(A\cap(z-gB))\geq s_{A}+s_{B}-d$ has positive Lebesgue measure. This
has been extended for other sets of transformations, for instance, the group
generated by the orthogonal group and the homotheties [12, 17], the set of
translations restricted on Cantor sets [1, Chapter 1], and the set of
orthogonal projections [21]. A number of variants and applications can be
found in a series of papers [1, 4, 5, 7, 22] and references therein.

Let $\mathbb{F}_{q}$ be a finite field of order $q$, where $q$ is a prime
power. In this paper, we introduce the finite field analog of this type of
questions and study the primary properties with an emphasis on the group of
orthogonal matrices and the set of orthogonal projections. More precisely, we
consider the following three main questions in this paper.

######  Question 1.1.

Given $A,B\subset\mathbb{F}_{q}^{d}$ and $g\in O(d)$, under what conditions on
$A$, $B$, and $g$ can we have

(1.1) $|A\cap(g(B)+z)|\geq\frac{|A||B|}{q^{d}}$

or a stronger form

(1.2) $|A\cap(g(B)+z)|\sim\frac{|A||B|}{q^{d}}$

for almost every $z\in\mathbb{F}_{q}^{d}$?

######  Question 1.2.

Given $P\subset\mathbb{F}_{q}^{2d}$ and $g\in O(d)$, under what conditions on
$P$ and $g$ can we have

$|S_{g}(P)|:=|\\{x-gy\colon(x,y)\in P\\}|\gg q^{d}?$

######  Question 1.3.

Let $A,B\subset\mathbb{F}_{q}^{d}$ and $m$ be a positive integer.

  1. (1)

If $|A|,|B|>q^{m}$, then under what conditions on $A$ and $B$ can we have

$|\pi_{W}(A)\cap\pi_{W}(B)|\gg q^{m}$

for almost every $W\in G(d,m)$?

  2. (2)

If $|B|<q^{m}<|A|$, then under what conditions on $A$ and $B$ can we have

$|\pi_{W}(A)\cap\pi_{W}(B)|\gg|B|$

for almost every $W\in G(d,m)$?

Here $\pi_{W}(X)$ denotes the orthogonal projection of $X$ onto $W$.

Main ideas (sketch): This paper presents more than twenty new theorems on
these three questions, for the reader’s convenience, we want to briefly
explain the main steps at the beginning. Our study of the three above
questions relies mainly on incidence theorems. While an incidence bound
between points and affine subspaces due to Pham, Phuong, and Vinh [25] is
sufficient to prove sharp results on 1.3, we need to develop incidence
theorems between points and rigid-motions for the first two questions. In
$\mathbb{R}^{2}$, such an incidence structure has been studied intensively in
the breakthrough solution of the Erdős distinct distances problem [6, 8]. In
this paper, we present the reverse direction, namely, from the distance
problem to incidence theorems. This strategy allows us to take advantage of
recent developments on the distance topic, as a consequence, we are able to
establish a complete picture in any dimensions over finite fields. Our paper
provides two types of incidence results: over arbitrary fields
$\mathbb{F}_{q}$ and over prime fields $\mathbb{F}_{p}$. The method we use is
the discrete Fourier analysis in which estimates on the following sum

$\sum_{||m||=||m^{\prime}||}|\widehat{A}(m)|^{2}|\widehat{B}(m^{\prime})|^{2}~{}\text{
for any }A,B\subset\mathbb{F}_{q}^{d},$

play the crucial role. While we use results from the Restriction theory due to
Chapman, Erdogan, Hart, Iosevich, and Koh [2], and Iosevich, Koh, Lee, Pham,
and Shen [10] to bound this sum effectively over arbitrary finite fields, the
proofs of better estimates over prime fields are based on the recent $L^{2}$
distance estimate due to Murphy, Petridis, Pham, Rudnev, and Stevens [24]
which was proved by using algebraic methods and Rudnev’s point-plane incidence
bound [26]. This presents surprising applications of the Erdős-Falconer
distance problem. We would like to emphasize here that the approach we use to
bound the above sum over prime fields is also one of the novelties of this
paper, and that sum will have more applications in other topics.

###  1.1. Intersection patterns I

Let us recall the first question. See 1.1

We note that for any $g\in O(d)$, we have

$\sum_{z\in\mathbb{F}_{q}^{d}}|A\cap(g(B)+z)|=|A||B|.$

Thus, there always exists $z\in\mathbb{F}_{q}^{d}$ such that
$|A\cap(g(B)+z)|\geq\frac{|A||B|}{q^{d}}$.

Let us start with some examples.

Example 1: Let $A$ be a subspace of dimension $k$ with $1\leq k<d$, $A=B$, and
$\mathtt{Stab}(A)$ be the set of matrices $g\in O(d)$ such that $gA=A$. It is
well-known that $|\mathtt{Stab}(A)|\sim|O(d-k)|\sim q^{\binom{d-k}{2}}$. For
any $g\in\mathtt{Stab}(A)$, we have

$|A\cap(gB+z)|=\begin{cases}0~{}&\mbox{if}~{}z\not\in A\\\
|A|~{}&\mbox{if}~{}z\in A\end{cases}.$

Example 2: In $\mathbb{F}_{q}^{d}$ with $d$ odd, given $0<c<1$, for each $g\in
O(d)$, there exist $A,B\subset\mathbb{F}_{q}^{d}$ with
$|A|=|B|=cq^{\frac{d+1}{2}}$ and $|A-gB|\leq 2cq^{d}$. To see this, let
$A=\mathbb{F}_{q}^{\frac{d-1}{2}}\times\\{0\\}^{\frac{d-1}{2}}\times X$ where
$X$ is an arithmetic progression of size $cq$ and
$B=g^{-1}\left(\mathbb{F}_{q}^{\frac{d-1}{2}}\times\\{0\\}^{\frac{d-1}{2}}\times
X\right)$. It is clear that the number of $z$ such that
$A\cap(gB+z)\neq\emptyset$ is at most $|A-gB|\leq q^{d-1}|X-X|\leq 2cq^{d}$.

These two examples suggest that if we want

$|A\cap(g(B)+z)|\sim\frac{|A||B|}{q^{d}},$

for almost every $z\in\mathbb{F}_{q}^{d}$, then $A$ and $B$ cannot be small
and $g$ cannot be chosen arbitrary in $O(d)$. Our first theorem describes this
phenomenon in detail.

######  Theorem 1.4.

Let $A$ and $B$ be sets in $\mathbb{F}_{q}^{d}$. Then there exists $E\subset
O(d)$ with

$|E|\ll\frac{|O(d-1)|q^{2d}}{|A||B|},$

such that for any $g\in O(d)\setminus E$, there are at least $\gg q^{d}$
elements $z$ satisfying

$|A\cap(g(B)+z)|\sim\frac{|A||B|}{q^{d}}.$

This theorem is valid in the range $|A||B|\gg q^{d+1}$, since

$\frac{|O(d-1)|q^{2d}}{|A||B|}\ll|O(d)|~{}~{}\mbox{when}~{}~{}|A||B|\gg
q^{d+1}.$

The condition $|A||B|\gg q^{d+1}$ is sharp in odd dimensions for comparable
sets $A$ and $B$. A construction will be provided in Section 5. When one set
is of small size, we can hope for a better estimate, and the next theorem
presents such a result.

######  Theorem 1.5.

Let $A$ and $B$ be sets in $\mathbb{F}_{q}^{d}$. Assume in addition either
($d\geq 3$ odd) or ($d\equiv 2\mod 4,q\equiv 3\mod 4$). Then there exists
$E\subset O(d)$ such that for any $g\in O(d)\setminus E$, there are at least
$\gg q^{d}$ elements $z$ satisfying

$|A\cap(g(B)+z)|\sim\frac{|A||B|}{q^{d}}.$

In particular,

  1. (1)

If $|A|<q^{\frac{d-1}{2}}$, then one has
$|E|\ll\frac{q^{(d^{2}+d)/2}}{|A||B|}$.

  2. (2)

If $q^{\frac{d-1}{2}}\leq|A|\leq q^{\frac{d+1}{2}}$, then one has
$|E|\ll\frac{q^{(d^{2}+1)/2}}{|B|}$.

In Theorem 1.5, the roles of $A$ and $B$ are symmetric. In a reduced form, the
theorem says that if $|A|\leq|B|$, $|B|\gg q^{\frac{d+1}{2}}$, and $|A||B|\gg
q^{d}$, then

$|A\cap(g(B)+z)|\sim\frac{|A||B|}{q^{d}}.$

Our proof involves a number of results from Restriction theory in which the
conditions on $d$ and $q$ are necessary. We do not know if it is still true
for the case $d\equiv 2\mod 4$ and $q\equiv 1\mod 4$, so it is left as an open
question.

The sharpness construction of Theorem 1.4 can be modified to show that these
two statements are also optimal in odd dimensions. In even dimensions, there
is no evidence to believe that the above theorems are sharp. In the next
theorem, we present an improvement in two dimensions.

######  Theorem 1.6.

Assume that $q\equiv 3\mod{4}$. Let $A$ and $B$ be sets in
$\mathbb{F}_{q}^{2}$ with $|A|\leq|B|$. Then there exists $E\subset O(2)$ with

$|E|\ll\frac{q^{3}}{|A|^{1/2}|B|}$

such that for any $g\in O(2)\setminus E$, there are at least $\gg q^{2}$
elements $z$ satisfying

$|A\cap(g(B)+z)|\sim\frac{|A||B|}{q^{2}}.$

######  Remark 1.7.

Note that this theorem is stronger than Theorem 1.5 in the range $|A|\geq q$.
When $|A|\geq|B|$ we can switch between the roles of $A$ and $B$ to obtain a
similar result, namely, there exists $E\subset O(2)$ with

$|E|\ll\frac{q^{3}}{|A||B|^{1/2}}$

such that for any $g\in O(2)\setminus E$, there are at least $\gg q^{2}$
elements $z$ satisfying

$|A\cap(g(B)+z)|\sim\frac{|A||B|}{q^{2}}.$

If our sets lie on the plane over a prime field $\mathbb{F}_{p}$, then further
improvements can be made.

######  Theorem 1.8 ($\mathbf{\mbox{\bf Medium}~{}A}$).

Assume that $p\equiv 3\mod{4}$. Let $A$ and $B$ be sets in
$\mathbb{F}_{p}^{2}$ with $|A|\leq|B|$. Then there exists $E\subset O(2)$ such
that for any $g\in O(2)\setminus E$, there are at least $\gg p^{2}$ elements
$z$ satisfying

$|A\cap(g(B)+z)|\sim\frac{|A||B|}{p^{2}}.$

In particular,

  1. (1)

If $p\leq|A|\leq p^{5/4}$ and $p^{5/4}\leq|B|\leq p^{4/3}$, then
$|E|\ll\frac{p^{59/24}}{|A|^{2/3}|B|^{1/2}}.$

  2. (2)

If $p^{5/4}\leq|A|\leq p^{4/3}$ and $p^{5/4}\leq|B|\leq p^{4/3}$, then
$|E|\ll\frac{p^{9/4}}{|A|^{1/2}|B|^{1/2}}.$

######  Theorem 1.9 ($\mathbf{\mbox{\bf Large}~{}B}$).

Assume that $p\equiv 3\mod{4}$. Let $A$ and $B$ be sets in
$\mathbb{F}_{p}^{2}$ with $|A|\leq|B|$. Then there exists $E\subset O(2)$ such
that for any $g\in O(2)\setminus E$, there are at least $\gg p^{2}$ elements
$z$ satisfying

$|A\cap(g(B)+z)|\sim\frac{|A||B|}{p^{2}}.$

In particular,

  1. (1)

If $p\leq|A|\leq p^{5/4}$ and $|B|>p^{4/3}$, then
$|E|\ll\frac{p^{17/6}}{|A|^{2/3}|B|^{3/4}}.$

  2. (2)

If $p^{5/4}\leq|A|\leq p^{4/3}$ and $|B|>p^{4/3}$, then
$|E|\ll\frac{p^{21/8}}{|A|^{1/2}|B|^{3/4}}.$

######  Remark 1.10.

We do not believe the results in even dimensions are optimal, but proving
improvements is outside the realm of methods of this paper.

######  Remark 1.11.

In the above two theorems, the sets $A$ and $B$ cannot be both small since,
otherwise, it might lead to a contradiction from the inequalities that
$p^{2}\ll|A-gB|\ll|B|^{2}$. To compare to the theorems over arbitrary finite
fields, we include the following table.

| $|A|\leq p^{\frac{1}{2}}$ | $p^{\frac{1}{2}}<|A|\leq p^{\frac{3}{4}}$ | $p^{\frac{3}{4}}<|A|\leq p$ | $p<|A|\leq p^{\frac{5}{4}}$ | $p^{\frac{5}{4}}<|A|\leq p^{\frac{4}{3}}$
---|---|---|---|---|---
$|B|\leq p^{\frac{3}{4}}$ | $\diagup$ | $\diagup$ | $\diagup$ | $\diagup$ | $\diagup$
$p^{\frac{3}{4}}<|B|\leq p$ | $\diagup$ | $\diagup$ | $\diagup$ | $\diagup$ | $\diagup$
$p<|B|\leq p^{\frac{5}{4}}$ | $\diagup$ | $\diagup$ | $\mathtt{unknown}$ | $\varnothing$ | $\diagup$
$p^{\frac{5}{4}}<|B|\leq p^{\frac{4}{3}}$ | $\diagup$ | $\mathtt{unknown}$ | $\mathtt{unknown}$ | $\surd$ | $\surd$
$p^{\frac{4}{3}}<|B|$ | $\varnothing$ | $\varnothing$ | $\varnothing$ | $|B|^{3}<p^{2}|A|^{2}$ | $|B|<p^{\frac{3}{2}}$
Table 1. In this table, by $``\surd"$ we mean better result, by
$``\varnothing"$ we mean weaker result, by $``f(|A|,|B|)"$ we mean better
result under the condition $f(|A|,|B|)$, by “$\mathtt{unknown}$" we mean there
is no non-trivial result in this range yet, and by $``\diagup"$ we mean
invalid range corresponding to $|B|\leq|A|$ or $|A||B|\ll p^{2}$.

###  1.2. Intersection patterns II

For $g\in O(d)$, define the map
$S_{g}\colon\mathbb{F}_{q}^{2d}\to\mathbb{F}_{q}^{d}$ by

$S_{g}(x,y)=x-gy.$

The results in the previous subsection say that if $P=A\times B$ with
$A,B\subset\mathbb{F}_{q}^{d}$ and $|A||B|$ is larger than a certain
threshold, then for almost every $g\in O(d)$, one has $|S_{g}(P)|\gg q^{d}$.

In this subsection, we present a result for general sets
$P\subset\mathbb{F}_{q}^{2d}$. With the same approach, we have the following
theorem.

######  Theorem 1.12.

Given $P\subset\mathbb{F}_{q}^{2d}$, there exists $E\subset O(d)$ with $|E|\ll
q^{2d}|O(d-1)|/|P|$ such that, for all $g\in O(d)\setminus E$, we have
$|S_{g}(P)|\gg q^{d}$.

######  Remark 1.13.

We always have $|S_{g}(P)|q^{d}\geq|P|$, since for each $z\in S_{g}(P)$ and
for each $x\in\mathbb{F}_{q}^{d}$, there is at most one
$y\in\mathbb{F}_{q}^{d}$ such that $(x,y)\in P$. Thus,
$|S_{g}(P)|\geq|P|q^{-d}$ for all $g\in O(d)$.

###  1.3. Incidences between points and rigid motions

We now move to incidence theorems.

Let $P$ be a set of points in $\mathbb{F}_{q}^{d}\times\mathbb{F}_{q}^{d}$ and
$R$ be a set of rigid motions in $\mathbb{F}_{q}^{d}$, i.e. maps of the form
$gx+z$ with $g\in O(d)$ and $z\in\mathbb{F}_{q}^{d}$. We define the incidence
$I(P,R)$ as follows:

$I(P,R)=\\#\\{(x,y,g,z)\in P\times R\colon x=gy+z\\}.$

We first provide a universal incidence bound.

######  Theorem 1.14.

Let $P\subset\mathbb{F}_{q}^{d}\times\mathbb{F}_{q}^{d}$. Then we have

$\left|I(P,R)-\frac{|P||R|}{q^{d}}\right|\ll q^{(d^{2}-d+2)/4}\sqrt{|P||R|}.$

In this theorem and the next ones, the quantities $|P||R|/q^{d}$ and
$q^{(d^{2}-d+2)/4}\sqrt{|P||R|}$ are referred to the main and error terms,
respectively.

Under some additional conditions on $d$ and $q$, if one set is of pretty small
size compared to the other, then we can prove stronger incidence bounds.

######  Theorem 1.15.

Let $P=A\times B$ for $A,B\subset\mathbb{F}_{q}^{d}$. Assume in addition that
either ($d\geq 3$ odd) or ($d\equiv 2\mod 4$ and $q\equiv 3\mod 4$).

  1. (1)

If $|A|<q^{\frac{d-1}{2}}$, then

$\left|I(P,R)-\frac{|P||R|}{q^{d}}\right|\ll q^{(d^{2}-d)/4}\sqrt{|P||R|}.$

  2. (2)

If $q^{\frac{d-1}{2}}\leq|A|\leq q^{\frac{d+1}{2}}$, then

$\left|I(P,R)-\frac{|P||R|}{q^{d}}\right|\ll
q^{(d^{2}-2d+1)/4}\sqrt{|P||R||A|}.$

In terms of applications (Theorem 1.4 and Theorem 1.5), one can expect that
these two incidence theorems are sharp in odd dimensions. However, this is not
true for even dimensions, and the next theorems present improvements in two
dimensions.

######  Theorem 1.16.

Assume that $q\equiv 3\mod 4$. Let $P=A\times B$ for
$A,B\subset\mathbb{F}_{q}^{2}$. Then we have

$\left|I(P,R)-\frac{|P||R|}{q^{2}}\right|\ll
q^{1/2}|P|^{1/2}|R|^{1/2}\min\big{(}|A|^{1/4},|B|^{1/4}\big{)}.$

A direct computation shows that this incidence theorem is better than the
previous in the range $|A|\geq q$.

In the plane over prime fields, we have the following three major improvements
corresponding to three cases: $|A|\leq p~{}\mbox{and}~{}|B|\leq p^{4/3}$,
$|A|\geq p~{}\mbox{and}~{}|B|\leq p^{4/3}$, and $|B|>p^{4/3}$, respectively.

######  Theorem 1.17 ($\mathbf{|A|\leq p~{}\mbox{\bf and}~{}|B|\leq
p^{4/3}}$).

Assume that $p\equiv 3\mod{4}$. Let $P=A\times B$ for
$A,B\subset\mathbb{F}_{p}^{2}$ with $|A|\leq|B|$. The following hold.

  1. (1)

If $p^{3/4}\leq|A|\leq p$ and $p^{5/4}\leq|B|\leq p^{4/3}$, then

$\left|I(P,R)-\frac{|P||R|}{p^{2}}\right|\ll
p^{1/16}|P|^{3/4}|R|^{1/2}|A|^{1/12}.$

  2. (2)

If $|A|\leq p$ and $p\leq|B|\leq p^{5/4}$, then

$\left|I(P,R)-\frac{|P||R|}{p^{2}}\right|\ll
p^{3}|P|^{1/2}|R|^{1/2}\left(\frac{1}{p^{5}}+\frac{|P|^{1/3}|A|^{1/3}}{p^{17/3}}\right)^{1/2}.$

  3. (3)

If $|A|\leq p$ and $|B|\leq p$, then

$\left|I(P,R)-\frac{|P||R|}{p^{2}}\right|\ll
p^{3}|P|^{1/2}|R|^{1/2}\left(\frac{1}{p^{5}}+\frac{|P|^{2/3}}{p^{6}}\right)^{1/2}.$

######  Theorem 1.18 ($\mathbf{|A|\geq p~{}\mbox{\bf and}~{}|B|\leq
p^{4/3}}$).

Assume that $p\equiv 3\mod{4}$. Let $P=A\times B$ for
$A,B\subset\mathbb{F}_{p}^{2}$ with $|A|\leq|B|$. The following hold.

  1. (1)

If $p\leq|A|\leq p^{5/4}$ and $p\leq|B|\leq p^{5/4}$, then

$\left|I(P,R)-\frac{|P||R|}{p^{2}}\right|\ll p^{1/3}|P|^{2/3}|R|^{1/2}.$

  2. (2)

If $p\leq|A|\leq p^{5/4}$ and $p^{5/4}\leq|B|\leq p^{4/3}$, then

$\left|I(P,R)-\frac{|P||R|}{p^{2}}\right|\ll
p^{11/48}|P|^{2/3}|R|^{1/2}|B|^{1/12}.$

  3. (3)

If $p^{5/4}\leq|A|\leq p^{4/3}$ and $p^{5/4}\leq|B|\leq p^{4/3}$, then

$\left|I(P,R)-\frac{|P||R|}{p^{2}}\right|\ll p^{1/8}|P|^{3/4}|R|^{1/2}.$

######  Theorem 1.19 ($\mathbf{|B|>p^{4/3}}$).

Assume that $p\equiv 3\mod{4}$. Let $P=A\times B$ for
$A,B\subset\mathbb{F}_{p}^{2}$ with $|A|\leq|B|$. The following hold.

  1. (1)

If $p\leq|A|\leq p^{5/4}$ and $|B|>p^{4/3}$, then

$\left|I(P,R)-\frac{|P||R|}{p^{2}}\right|\ll
p^{5/12}|P|^{5/8}|R|^{1/2}|A|^{1/24}.$

  2. (2)

If $p^{5/4}\leq|A|\leq p^{4/3}$ and $|B|>p^{4/3}$, then

$\left|I(P,R)-\frac{|P||R|}{p^{2}}\right|\ll
p^{5/16}|P|^{5/8}|R|^{1/2}|A|^{1/8}.$

We now include a comparison to the results in $\mathbb{F}_{q}^{2}$ offered by
Theorem 1.15 and Theorem 1.16.

| $|A|\leq p^{\frac{1}{2}}$ | $p^{\frac{1}{2}}<|A|\leq p^{\frac{3}{4}}$ | $p^{\frac{3}{4}}<|A|\leq p$ | $p<|A|\leq p^{\frac{5}{4}}$ | $p^{\frac{5}{4}}<|A|\leq p^{\frac{4}{3}}$
---|---|---|---|---|---
$|B|\leq p^{\frac{3}{4}}$ | $=$ | $\surd$ | $\diagup$ | $\diagup$ | $\diagup$
$p^{\frac{3}{4}}<|B|\leq p$ | $=$ | $|A|^{3}>|B|^{2}$ | $\surd$ | $\diagup$ | $\diagup$
$p<|B|\leq p^{\frac{5}{4}}$ | $\varnothing$ | $|A|>(p|B|)^{\frac{1}{3}}$ | $\surd$ | $\surd$ | $\diagup$
$p^{\frac{5}{4}}<|B|\leq p^{\frac{4}{3}}$ | $\varnothing$ | $\varnothing$ | $|B|<p^{\frac{3}{4}}|A|^{\frac{2}{3}}$ | $\surd$ | $\surd$
$p^{\frac{4}{3}}<|B|$ | $\varnothing$ | $\varnothing$ | $\varnothing$ | $|B|^{3}<p^{2}|A|^{2}$ | $|B|<p^{\frac{3}{2}}$
Table 2. In this table, by $``="$ we mean the same result, by $``\surd"$ we
mean better result, by $``\varnothing"$ we mean weaker result, by
$``f(|A|,|B|)"$ we mean better result under the condition $f(|A|,|B|)$, and by
$``\diagup"$ we mean invalid range corresponding to $|B|\leq|A|$.

######  Remark 1.20.

The incidence theorems in two dimensions offer both the upper and lower bounds
which depend simultaneously on the exponents of $p$, $|P|$, and $|R|$. Hence,
it is very difficult to come up with a conjecture that is sharp for most
ranges.

###  1.4. Growth estimates under orthogonal matrices

For $A,B\subset\mathbb{F}_{q}^{d}$, we have seen that there exists a set
$E\subset O(d)$ such that for all $g\in O(d)\setminus E$, one has $|A-gB|\gg
q^{d}$. In this subsection, we represent this type of results in the language
of expanding functions, namely, assume $|A|\leq|B|$, we want to have a weaker
conclusion of the form $|A-gB|\gg|B|^{1+\epsilon}$ for a given $\epsilon>0$.
Note that in this setting, we can obtain non-trivial results for small sets
$A$ and $B$. With the same proof, we have the following theorems.

######  Theorem 1.21.

Let $\epsilon>0$. Given $A,B\subset\mathbb{F}_{q}^{d}$ with $|A|\leq|B|$ and
$|B|^{1+\epsilon}<q^{d}/2$, there exists $E\subset O(d)$ with

$|E|\ll\frac{|O(d-1)|q^{d}|B|^{\epsilon}}{|A|}$

such that for all $g\in O(d)\setminus E$, we have

$|A-gB|\gg|B|^{1+\epsilon}.$

######  Theorem 1.22.

Let $\epsilon>0$. Assume either ($d\geq 3$ odd) or ($d\equiv 2\mod 4,q\equiv
3\mod 4$). Given $A,B\subset\mathbb{F}_{q}^{d}$ with $|A|\leq|B|$ and
$|B|^{1+\epsilon}<q^{d}/2$, there exists $E\subset O(d)$ such that for all
$g\in O(d)\setminus E$, we have

$|A-gB|\gg|B|^{1+\epsilon}.$

In particular,

  1. (1)

If $|A|<q^{\frac{d-1}{2}}$, then one has
$|E|\ll\frac{q^{\frac{d^{2}-d}{2}}|B|^{\epsilon}}{|A|}$.

  2. (2)

If $q^{\frac{d-1}{2}}\leq|A|\leq q^{\frac{d+1}{2}}$, then one has $|E|\ll
q^{\frac{d^{2}-2d+1}{2}}|B|^{\epsilon}$.

The two above theorems say that when the sizes of $A$ and $B$ belong to
certain ranges, then the image $A-gB$ grows exponentially for almost every
$g\in O(d)$. However, in two dimensions, the statement is much more beautiful:
if $|A|=q^{x}$ and $|B|=q^{y}$, as long as $0<x\leq y<2$, then for almost
every $g\in O(2)$, we can always find $\epsilon=\epsilon(x,y)>0$ such that
$|A-gB|\gg|B|^{1+\epsilon}$.

######  Theorem 1.23.

Let $\epsilon>0$. Assume that $q\equiv 3\mod{4}$. Given
$A,B\subset\mathbb{F}_{q}^{2}$ with $|A|\leq|B|$ and
$|B|^{1+\epsilon}<q^{2}/2$, there exists $E\subset O(2)$ with

$|E|\ll\frac{q|B|^{\epsilon}}{|A|^{1/2}}$

such that for all $g\in O(2)\setminus E$, we have

$|A-gB|\gg|B|^{1+\epsilon}.$

In this paper, we do not compute the exponent $\epsilon(x,y)$ explicitly in
terms of $x$ and $y$, but it can be improved when we replace $\mathbb{F}_{q}$
by $\mathbb{F}_{p}$. The ranges of improvements are the same as those
indicated in Table 2.

######  Theorem 1.24 (Small $A$).

Let $\epsilon>0$. Assume that $p\equiv 3\mod{4}$. Given
$A,B\subset\mathbb{F}_{p}^{2}$ with $|A|\leq|B|$ and
$|B|^{1+\epsilon}<p^{2}/2$, there exists $E\subset O(2)$ such that for all
$g\in O(2)\setminus E$, we have

$|A-gB|\gg|B|^{1+\epsilon}.$

In particular,

  1. (1)

If $p^{3/4}\leq|A|\leq p$ and $p^{5/4}\leq|B|\leq p^{4/3}$, then
$|E|\ll\frac{p^{1/8}|B|^{1/2+\epsilon}}{|A|^{1/3}}$.

  2. (2)

If $|A|\leq p$ and $p\leq|B|\leq p^{5/4}$, then
$|E|\ll\frac{p|B|^{\epsilon}+p^{1/3}|B|^{\epsilon}|P|^{1/3}|A|^{1/3}}{|A|}$.

  3. (3)

If $|A|\leq p$ and $|B|\leq p$, then
$|E|\ll\frac{|B|^{\epsilon}|P|^{2/3}}{|A|}$.

######  Theorem 1.25 (Medium $A$).

Let $\epsilon>0$. Assume that $p\equiv 3\mod{4}$. Given
$A,B\subset\mathbb{F}_{p}^{2}$ with $|A|\leq|B|$ and
$|B|^{1+\epsilon}<p^{2}/2$, there exists $E\subset O(2)$ such that for all
$g\in O(2)\setminus E$, we have

$|A-gB|\gg|B|^{1+\epsilon}.$

In particular,

  1. (1)

If $p\leq|A|\leq p^{5/4}$ and $p\leq|B|\leq p^{5/4}$, then
$|E|\ll\frac{p^{2/3}|B|^{1/3+\epsilon}}{|A|^{2/3}}$.

  2. (2)

If $p\leq|A|\leq p^{5/4}$ and $p^{5/4}\leq|B|\leq p^{4/3}$, then
$|E|\ll\frac{p^{11/24}|B|^{1/2+\epsilon}}{|A|^{2/3}}$.

  3. (3)

If $p^{5/4}\leq|A|\leq p^{4/3}$ and $p^{5/4}\leq|B|\leq p^{4/3}$, then
$|E|\ll\frac{p^{1/4}|B|^{1/2+\epsilon}}{|A|^{1/2}}$.

######  Theorem 1.26 (Large $B$).

Let $\epsilon>0$. Assume that $p\equiv 3\mod{4}$. Given
$A,B\subset\mathbb{F}_{p}^{2}$ with $|A|\leq|B|$ and
$|B|^{1+\epsilon}<p^{2}/2$, there exists $E\subset O(2)$ such that for all
$g\in O(2)\setminus E$, we have

$|A-gB|\gg|B|^{1+\epsilon}.$

In particular,

  1. (1)

If $p\leq|A|\leq p^{5/4}$ and $|B|>p^{4/3}$, then
$|E|\ll\frac{p^{5/6}|B|^{1/4+\epsilon}}{|A|^{2/3}}$.

  2. (2)

If $p^{5/4}\leq|A|\leq p^{4/3}$ and $|B|>p^{4/3}$, then
$|E|\ll\frac{p^{5/8}|B|^{1/4+\epsilon}}{|A|^{1/2}}$.

###  1.5. Intersection pattern III

For a finite set $E\subset\mathbb{R}^{d}$ and a subspace $V$ of
$\mathbb{R}^{d}$, the orthogonal projection of $E$ onto $V$ is defined by

(1.3) $\pi_{V}(E):=\left\\{x\in V\colon(x+V^{\perp})\cap
E\neq\emptyset\right\\},$

where $V^{\perp}$ denotes the orthogonal complement of $V$.

In $\mathbb{F}_{q}^{d}$ or vector spaces over arbitrary finite fields, due to
the fact that there exist null-vectors, i.e. vectors $v$ with $v\cdot v=0$,
the orthogonal projection of $E$ onto $V$ is defined by

$\pi_{V}(E):=\\{x+V^{\perp}\colon(x+V^{\perp})\cap
E\neq\emptyset,~{}x\in\mathbb{F}_{p}^{d}\\}.$

The elements of $\pi_{V}(E)$ are $(d-m)$-dimensional affine planes of
$\mathbb{F}_{q}^{d}$ when dim$V=m$. We also note that as in the Euclidean we
have the property that

$\dim(V)+\dim(V^{\perp})=d,$

for all subspaces $V\subset\mathbb{F}_{q}^{d}$.

Chen [3] proved the following result.

######  Theorem 1.27.

[3, Theorem 1.2.] Let $E\subset\mathbb{F}_{q}^{d}$.

  1. (1)

For any $N<\frac{|E|}{2}$,

$|\\{W\in G(d,m)\colon|\pi_{W}(E)|\leq N\\}|\leq 4q^{(d-m)m-m}N.$

  2. (2)

For any $\delta\in(0,1)$,

$|\\{W\in G(d,m)\colon|\pi_{W}(E)|\leq\delta q^{m}\\}|\leq
2\left(\frac{\delta}{1-\delta}\right)q^{m(d-m)+m}|E|^{-1}.$

######  Corollary 1.28.

[3, Corollary 1.3.] Let $E\subset\mathbb{F}_{q}^{d}$ with $|E|=q^{s}$.

  1. (1)

If $s\leq m$ and $t\in(0,s]$, then

$|\\{W\in G(d,m)\colon|\pi_{W}(E)|\leq
q^{t}/10\\}|\leq\frac{1}{2}q^{m(d-m-1)+t}.$

  2. (2)

If $s>m$, then

$|\\{W\in G(d,m)\colon|\pi_{W}(E)|\leq
q^{m}/10\\}|\leq\frac{1}{2}q^{m(d-m+1)-s}.$

  3. (3)

If $s>2m$, then

$\\{W\in G(d,m)\colon|\pi_{W}(E)|\neq q^{m}\\}\leq 4q^{(d-m)(m+1)-s}.$

As mentioned earlier, we study the following question.

######  Question 1.29.

Let $A,B\subset\mathbb{F}_{q}^{d}$ and $m$ be a positive integer.

  1. (1)

If $|A|,|B|>q^{m}$, then under what conditions on $A$ and $B$ can we have

$|\pi_{W}(A)\cap\pi_{W}(B)|\gg q^{m}$

for almost every $W\in G(d,m)$?

  2. (2)

If $|B|<q^{m}<|A|$, then under what conditions on $A$ and $B$ can we have

$|\pi_{W}(A)\cap\pi_{W}(B)|\gg|B|$

for almost every $W\in G(d,m)$?

The next theorem provides a partial optimal solution to this question.

######  Theorem 1.30.

Let $A,B\subset\mathbb{F}_{q}^{d}$ and $m$ be a positive integer.

  1. (1)

If $|A|,|B|>q^{m}$, then there are at least $\gg q^{m(d-m)}$ subspaces $W\in
G(d,m)$ such that

$|\pi_{W}(A)\cap\pi_{W}(B)|\gg q^{m}.$

  2. (2)

If $|A|,|B|>q^{2m}$, then there there are at least $\gg q^{m(d-m)}$ subspaces
$W\in G(d,m)$ such that

$|\pi_{W}(A)\cap\pi_{W}(B)|=q^{m}.$

  3. (3)

Let $m\geq d/2$. If $|A|>100q^{m}$, $|B|<q^{m}/2$, and $|A||B|>160q^{2m}$,
then there there are at least $\gg q^{m(d-m)}$ subspaces $W\in G(d,m)$ such
that

$|\pi_{W}(A)\cap\pi_{W}(B)|\gg|B|.$

We now discuss the sharpness of this theorem. In the first statement, it is
clear that the condition $|A|,|B|>q^{m}$ can not be replaced by
$|A|,|B|>q^{m-\epsilon}$ for any $\epsilon>0$. The second statement is sharp
when $d=2$ and $m=1$. To see this, let $K$ be a Kakeya set in
$\mathbb{F}_{q}^{2}$ of size $\frac{q^{2}-1}{2}+q$, i.e. a set contains a full
line in all directions, such an example can be found in [23]. Set
$A=B=\mathbb{F}_{q}^{2}\setminus K$. It is clear that
$|\pi_{W}(A)|,|\pi_{W}(B)|\neq q$ for all directions $W$. The third statement
is also sharp in $\mathbb{F}_{q}^{2}$ in the following sense: for any
$\epsilon>0$ and any positive constant $c$, there exist
$A,B\subset\mathbb{F}_{q}^{2}$, $|A||B|=q^{2-\epsilon}$, and there are at most
$cq^{m(d-m)}$ subspaces $W\in G(d,m)$ such that
$|\pi_{W}(A)\cap\pi_{W}(B)|\gg|B|$. This is a long construction, so we omit it
here and present it in detail in Section 8. When $m>1$, we do not have any
examples for its sharpness.

To keep this paper not too long, we do not want to make a full comparison
between the results in this paper and those in the fractal. There is one
crucial point we have to mention here that while Theorem 1.4, Theorem 1.5, and
Theorem 1.12 are directly in line with Mattila’s results in [18, Theorem
13.11] and [20], we are not aware of any results in the continuous setting
that are similar to those in $\mathbb{F}_{q}^{2}$ or $\mathbb{F}_{p}^{2}$.
This suggests that there might be room for improvements in $\mathbb{R}^{2}$.

##  2\. Preliminaries-key lemmas

Let $f\colon\mathbb{F}_{q}^{n}\to\mathbb{C}$ be a complex valued function. The
Fourier transform $\widehat{f}$ of $f$ is defined by

$\widehat{f}(m):=q^{-n}\sum_{x\in\mathbb{F}_{q}^{n}}\chi(-m\cdot x)f(x),$

here, we denote by $\chi$ a non-trivial additive character of
$\mathbb{F}_{q}$. Note that $\chi$ satisfies the following orthogonality
property

$\sum_{\alpha\in\mathbb{F}_{q}^{n}}\chi(\beta\cdot\alpha)=\left\\{\begin{array}[]{ll}0&\mbox{if}\quad\beta\neq(0,\ldots,0),\\\
q^{n}&\mbox{if}\quad\beta=(0,\ldots,0).\end{array}\right.$

We also have the Fourier inversion formula as follows

$f(x)=\sum_{m\in\mathbb{F}_{q}^{n}}\chi(m\cdot x)\widehat{f}(m).$

With these notations in hand, the Plancherel theorem states that

$\sum_{m\in\mathbb{F}_{q}^{n}}|\widehat{f}(m)|^{2}=q^{-n}\sum_{x\in\mathbb{F}_{q}^{n}}|f(x)|^{2}.$

In this paper, we denote the quadratic character of $\mathbb{F}_{q}$ by
$\eta$, precisely, for $s\neq 0$, $\eta(s)=1$ if $s$ is a square and $-1$
otherwise. The convention that $\eta(0)=0$ will be also used in this paper.

This section is devoted to proving upper bounds of the following sum

$\sum_{||m||=||m^{\prime}||}|\widehat{A}(m)|^{2}|\widehat{B}(m^{\prime})|^{2}~{}\text{
for any }A,B\subset\mathbb{F}_{q}^{d},$

which is the key step in our proofs of incidence theorems.

###  2.1. Results over arbitrary finite fields

We first start with a direct application of the Plancherel theorem.

######  Theorem 2.1.

Let $A,B$ be sets in $\mathbb{F}_{q}^{d}$. Then we have

$\sum_{||m||=||m^{\prime}||}|\widehat{A}(m)|^{2}|\widehat{B}(m^{\prime})|^{2}\leq\frac{|A||B|}{q^{2d}}.$

To improve this result, we need to recall a number of lemmas in the
literature.

For any $j\neq 0$, let $S_{j}$ be the sphere centered at the origin of radius
$j$ defined as follows:

$S_{j}:=\\{x\in\mathbb{F}_{q}^{d}\colon x_{1}^{2}+\cdots+x_{d}^{2}=j\\}.$

The next lemma provides the precise form of the Fourier decay of $S_{j}$ for
any $j\in\mathbb{F}_{q}$. A proof can be found in [9] or [13].

######  Lemma 2.2.

For any $j\in\mathbb{F}_{q}$, we have

$\widehat{S_{j}}(m)=q^{-1}\delta_{0}(m)+q^{-d-1}\eta^{d}(-1)G_{1}^{d}(\eta,\chi)\sum_{r\in{\mathbb{F}}_{q}^{*}}\eta^{d}(r)\chi\Big{(}jr+\frac{\|m\|}{4r}\Big{)},$

where $\eta$ is the quadratic character, and $\delta_{0}(m)=1$ if
$m=(0,\ldots,0)$ and $\delta_{0}(m)=0$ otherwise.

Moreover, for $m,m^{\prime}\in\mathbb{F}_{q}^{d}$, we have

$\sum_{j\in\mathbb{F}_{q}}\widehat{S_{j}}(m)\overline{\widehat{S_{j}(m^{\prime})}}=\frac{\delta_{0}(m)\delta(m^{\prime})}{q}+\frac{1}{q^{d+1}}\sum_{s\in\mathbb{F}_{q}^{*}}\chi(s(||m||-||m^{\prime}||)).$

For $A\subset\mathbb{F}_{q}^{d}$, define

$M^{*}(A)=\max_{j\neq 0}\sum_{m\in
S_{j}}|\widehat{A}(m)|^{2},~{}\mbox{and}~{}M(A)=\max_{j\in\mathbb{F}_{q}}\sum_{m\in
S_{j}}|\widehat{A}(m)|^{2}.$

We recall the following result from [13], which is known as the finite field
analog of the spherical average in the classical Falconer distance problem
[16, Chapter 3].

######  Theorem 2.3.

Let $A\subset\mathbb{F}_{q}^{d}$. We have

  1. (1)

If $d=2$, then $M^{*}(A)\ll q^{-3}|A|^{3/2}$.

  2. (2)

If $d\geq 4$ even, then
$M^{*}(A)\ll\min\left\\{\frac{|A|}{q^{d}},~{}\frac{|A|}{q^{d+1}}+\frac{|A|^{2}}{q^{\frac{3d+1}{2}}}\right\\}$.

  3. (3)

If $d\geq 3$ odd, then
$M(A)\ll\min\left\\{\frac{|A|}{q^{d}},~{}\frac{|A|}{q^{d+1}}+\frac{|A|^{2}}{q^{\frac{3d+1}{2}}}\right\\}$.

In some specific dimensions, a stronger estimate was proved in [10] for the
sphere of zero radius.

######  Theorem 2.4.

Let $A\subset\mathbb{F}_{q}^{d}$. Assume $d\equiv 2\mod{4}$ and $q\equiv
3\mod{4}$, then we have

$\sum_{m\in
S_{0}}|\widehat{A}(m)|^{2}\ll\frac{|A|}{q^{d+1}}+\frac{|A|^{2}}{q^{\frac{3d+2}{2}}}.$

We are now ready to improve Theorem 2.1.

######  Theorem 2.5.

Let $A,B$ be sets in $\mathbb{F}_{q}^{d}$. Assume that either ($d\geq 3$ odd)
or ($d\equiv 2\mod 4$ and $q\equiv 3\mod 4$), then the following hold.

  1. (1)

If $|A|\leq q^{\frac{d-1}{2}}$, then

$\sum_{||m||=||m^{\prime}||}|\widehat{A}(m)|^{2}|\widehat{B}(m^{\prime})|^{2}\leq\frac{|A||B|}{q^{2d+1}}.$

  2. (2)

If $q^{\frac{d-1}{2}}\leq|A|\leq q^{\frac{d+1}{2}}$, then

$\sum_{||m||=||m^{\prime}||}|\widehat{A}(m)|^{2}|\widehat{B}(m^{\prime})|^{2}\leq\frac{|A|^{2}|B|}{q^{\frac{5d+1}{2}}}.$

###### Proof.

The proof follows directly from Theorem 2.3 and Theorem 2.4. More precisely,

$\sum_{||m||=||m^{\prime}||}|\widehat{A}(m)|^{2}|\widehat{B}(m^{\prime})|^{2}\leq\max_{t\in\mathbb{F}_{q}}\sum_{m\in
S_{t}}|\widehat{A}(m)|^{2}\cdot\sum_{m^{\prime}\in\mathbb{F}_{q}^{d}}|\widehat{B}(m^{\prime})|^{2}\leq\max_{t\in\mathbb{F}_{q}}\sum_{m\in
S_{t}}|\widehat{A}(m)|^{2}\cdot\frac{|B|}{q^{d}}.$

This completes the proof. ∎

In two dimensions, we can obtain a better estimate as follows.

######  Theorem 2.6.

Let $A,B$ be sets in $\mathbb{F}_{q}^{2}$. Assume in addition that $q\equiv
3\mod 4$, then we have

$\sum_{||m||=||m^{\prime}||}|\widehat{A}(m)|^{2}|\widehat{B}(m^{\prime})|^{2}\ll\frac{|A||B|}{q^{5}}\cdot\min\\{|A|^{1/2},|B|^{1/2}\\}.$

###### Proof.

We note that when $q\equiv 3\mod{4}$, the circle of radius zero contains only
one point which is $(0,0)$, so

$|\widehat{A}(0,0)|^{2}|\widehat{B}(0,0)|^{2}=\frac{|A|^{2}|B|^{2}}{q^{8}}.$

Applying Theorem 2.3, as above, one has

$\sum_{||m||=||m^{\prime}||\neq
0}|\widehat{A}(m)|^{2}|\widehat{B}(m^{\prime})|^{2}\leq
M^{*}(A)\sum_{m}|\widehat{B}(m)|^{2}\ll\frac{|A|^{3/2}|B|}{q^{5}},$

and

$\sum_{||m||=||m^{\prime}||\neq
0}|\widehat{A}(m)|^{2}|\widehat{B}(m^{\prime})|^{2}\leq
M^{*}(B)\sum_{m}|\widehat{A}(m)|^{2}\leq\frac{|A||B|^{3/2}}{q^{5}}.$

Thus, the theorem follows. ∎

###  2.2. Results over prime fields

To improve Theorem 2.6 over prime fields, we need to introduce the following
notation.

For $P\subset\mathbb{F}_{q}^{2d}$. Define

$N(P):=\\#\\{(x,y,u,v)\in P\times P\colon||x-u||=||y-v||\\}.$

The following picture describes the case $P=A\times B$.

We note that $N(A\times B)$ counts the number of pairs in $A\times A$ and
$B\times B$ of the same distance. This quantity is not the same as the $L^{2}$
distance estimate of the set $A\times B$.

While the sum
$\sum_{||m||=||m^{\prime}||}|\widehat{A}(m)|^{2}|\widehat{B}(m^{\prime})|^{2}$
can be bounded directly over arbitrary finite fields, the strategy over prime
fields is different. More precisely, we will use a double counting argument to
bound $N(P)$. The first bound is proved in the next theorem which presents a
connection between the sum and the magnitude of $N(P)$. The second bound
(Theorem 2.8, Corollary 2.9) for $N(P)$ is due to Murphy, Petridis, Pham,
Rudnev, and Stevens [24] which was proved by using algebraic methods and
Rudnev’s point-plane incidence bound [26].

######  Theorem 2.7.

Let $P=A\times B$ for $A,B\subset\mathbb{F}_{q}^{d}$. Then we have

$N(P)=\frac{|P|^{2}}{q}-q^{3d-1}\sum_{||m||\neq||m^{\prime}||}|\widehat{A}(m)|^{2}|\widehat{B}(m^{\prime})|^{2}+q^{3d}\sum_{||m||=||m^{\prime}||}|\widehat{A}(m)|^{2}|\widehat{B}(m^{\prime})|^{2}.$

###### Proof.

For any $j\in\mathbb{F}_{q}$ and $A\subset\mathbb{F}_{q}^{d}$, we define

$\nu_{A}(j):=\\#\\{(x,y)\in A\times A\colon||x-y||=j\\}.$

Therefore, for any $j\neq 0$, we have

$\displaystyle\nu_{A}(j)$
$\displaystyle=\sum_{x,y\in\mathbb{F}_{q}^{d}}A(x)A(y)S_{j}(x-y)=\sum_{x,y\in\mathbb{F}_{q}^{d}}A(x)A(y)\sum_{m\in\mathbb{F}_{q}^{d}}\widehat{S_{j}}(m)\chi(m(x-y))$
$\displaystyle=q^{2d}\sum_{m\in\mathbb{F}_{q}^{d}}\widehat{S_{j}}(m)|\widehat{A}(m)|^{2}.$

Thus,

$N(P)=\sum_{t\in\mathbb{F}_{q}}\nu_{A}(t)\nu_{B}(t)=q^{4d}\sum_{m,m^{\prime}}|\widehat{A}(m)|^{2}|\widehat{B}(m^{\prime})|^{2}\sum_{t\in\mathbb{F}_{q}}\widehat{S_{t}}(m)\widehat{S_{t}}(m^{\prime}).$

Lemma 2.2 tells us that

$\sum_{t\in\mathbb{F}_{q}}\widehat{S_{t}}(m)\overline{\widehat{S_{t}}}(m^{\prime})=\frac{\delta_{0}(m)\delta_{0}(m^{\prime})}{q}+\frac{1}{q^{d+1}}\sum_{s\in\mathbb{F}_{q}^{*}}\chi(s(||m||-||m^{\prime}||)).$

Therefore,

$\displaystyle N(P)$
$\displaystyle=\frac{|A|^{2}|B|^{2}}{q}+q^{3d-1}\sum_{m,m^{\prime}}|\widehat{A}(m)|^{2}|\widehat{B}(m^{\prime})|^{2}\sum_{s\neq
0}\chi(s(||m||-||m^{\prime}||))$
$\displaystyle=\frac{|A|^{2}|B|^{2}}{q}-q^{3d-1}\sum_{||m||\neq||m^{\prime}||}|\widehat{A}(m)|^{2}|\widehat{B}(m^{\prime})|^{2}+q^{3d}\sum_{||m||=||m^{\prime}||}|\widehat{A}(m)|^{2}|\widehat{B}(m^{\prime})|^{2}.$

This completes the proof. ∎

######  Theorem 2.8.

For $A\subset\mathbb{F}_{p}^{2}$, $p\equiv 3\mod{4}$ with $|A|\ll p^{4/3}$,
and $P=A\times A$, we have

$N(P)=\\#\\{(x,y,z,w)\in
A^{4}\colon||x-y||=||z-w||\\}\leq\frac{|A|^{4}}{p}+C\min\left\\{p^{2/3}|A|^{8/3}+p^{1/4}|A|^{3},|A|^{10/3}\right\\},$

for some large constant $C>0$.

######  Corollary 2.9.

For $A\subset\mathbb{F}_{p}^{2}$, $p\equiv 3\mod{4}$ with $|A|\ll p^{4/3}$,
and $P=A\times A$, there exists a large constant $C$ such that the following
hold.

  1. (1)

If $|A|\leq p$, then $N(P)\leq C|A|^{10/3}$.

  2. (2)

If $p\leq|A|\leq p^{5/4}$, then $N(P)\leq p^{-1}|A|^{4}+Cp^{2/3}|A|^{8/3}$.

  3. (3)

If $p^{5/4}\leq|A|\leq p^{3/2}$, then $N(P)\leq
p^{-1}|A|^{4}+Cp^{1/4}|A|^{3}$.

######  Remark 2.10.

We want to add a remark here that [24, Theorem 4] presents a bound on the
number of isosceles triangles in $A$. This implies the bound for $N(P)$ as
stated in Theorem 2.8 since $N(P)$ is at most the number of isosceles
triangles times the size of $A$ by the Cauchy-Schwarz inequality.

######  Theorem 2.11.

Let $A,B\subset\mathbb{F}_{p}^{2}$ with $|A|\leq|B|$ and $p\equiv 3\mod 4$.
Define

$I_{A,B}:=p^{6}\sum_{||m||=||m^{\prime}||}|\widehat{A}(m)|^{2}|\widehat{B}(m^{\prime})|^{2}.$

Then the following hold.

  1. (1)

If $|A|\leq p$ and $p^{5/4}\leq|B|\leq p^{4/3}$, then $I_{A,B}\ll
p^{1/8}(p|A|^{2}+|A|^{10/3})^{1/2}|B|^{3/2}$.

  2. (2)

If $|A|\leq p$ and $p\leq|B|\leq p^{5/4}$,
$I_{A,B}\ll(p|A|^{2}+|A|^{10/3})^{1/2}\cdot p^{1/3}|B|^{4/3}$.

  3. (3)

If $|A|\leq p$ and $|B|\leq p$, then
$I_{A,B}\leq(p|A|^{2}+|A|^{10/3})^{1/2}\cdot(p|B|^{2}+|B|^{10/3})^{1/2}$.

  4. (4)

If $p\leq|A|\leq p^{5/4}$ and $p\leq|B|\leq p^{5/4}$, then $I_{A,B}\ll
p^{2/3}|A|^{4/3}|B|^{4/3}$.

  5. (5)

If $p\leq|A|\leq p^{5/4}$ and $p^{5/4}\leq|B|\leq p^{4/3}$, then $I_{A,B}\ll
p^{11/24}|A|^{4/3}|B|^{3/2}$.

  6. (6)

If $p^{5/4}\leq|A|\leq p^{4/3}$ and $p^{5/4}\leq|B|\leq p^{4/3}$, then
$I_{A,B}\ll p^{1/4}|A|^{3/2}|B|^{3/2}.$

  7. (7)

If $|A|\leq p$ and $|B|>p^{4/3}$, then $I_{A,B}\ll
p^{1/2}(p|A|^{2}+|A|^{10/3})^{1/2}|B|^{5/4}$.

  8. (8)

If $p\leq|A|\leq p^{5/4}$ and $|B|>p^{4/3}$, then $I_{A,B}\ll
p^{5/6}|A|^{4/3}|B|^{5/4}$.

  9. (9)

If $p^{5/4}\leq|A|\leq p^{4/3}$ and $|B|>p^{4/3}$, then $I_{A,B}\ll
p^{5/8}|A|^{3/2}|B|^{5/4}$.

To see how good this theorem is, we need to compare with the results obtained
by Theorem 2.5 and Theorem 2.6. More precisely, the two theorems give

$I_{A,B}\ll\begin{cases}q|A|^{3/2}|B|&~{}~{}\mbox{if}~{}|A|\geq q\\\
q^{1/2}|A|^{2}|B|&~{}~{}\mbox{if}~{}q^{\frac{1}{2}}\leq|A|<q\\\
q|A||B|&~{}~{}\mbox{if}~{}|A|<q^{\frac{1}{2}}\end{cases}.$

The following table gives the information we need.

| $|A|\leq p^{\frac{1}{2}}$ | $p^{\frac{1}{2}}<|A|\leq p^{\frac{3}{4}}$ | $p^{\frac{3}{4}}<|A|\leq p$ | $p<|A|\leq p^{\frac{5}{4}}$ | $p^{\frac{5}{4}}<|A|\leq p^{\frac{4}{3}}$
---|---|---|---|---|---
$|B|\leq p^{\frac{3}{4}}$ | $=$ | $\surd$ | $\diagup$ | $\diagup$ | $\diagup$
$p^{\frac{3}{4}}<|B|\leq p$ | $\varnothing$ | $|A|^{3}>|B|^{2}$ | $\surd$ | $\diagup$ | $\diagup$
$p<|B|\leq p^{\frac{5}{4}}$ | $\varnothing$ | $|A|>(p|B|)^{\frac{1}{3}}$ | $\surd$ | $\surd$ | $\diagup$
$p^{\frac{5}{4}}<|B|\leq p^{\frac{4}{3}}$ | $\varnothing$ | $\varnothing$ | $|B|<p^{\frac{3}{4}}|A|^{\frac{2}{3}}$ | $\surd$ | $\surd$
$p^{\frac{4}{3}}<|B|$ | $\varnothing$ | $\varnothing$ | $\varnothing$ | $|B|^{3}<p^{2}|A|^{2}$ | $|B|<p^{\frac{3}{2}}$
Table 3. In this table, by $``="$ we mean the same result, by $``\surd"$ we
mean better result, by $``\varnothing"$ we mean weaker result, by
$``f(|A|,|B|)"$ we mean better result under the condition $f(|A|,|B|)$, and by
$``\diagup"$ we mean invalid range corresponding to $|B|\leq|A|$.

###### Proof.

We have

$\displaystyle I_{A,B}$
$\displaystyle=p^{6}\sum_{t\in\mathbb{F}_{p}}\sum_{m,m^{\prime}\in
S_{t}}|\widehat{A}(m)|^{2}|\widehat{B}(m^{\prime})|^{2}=p^{6}\sum_{t\in\mathbb{F}_{p}}\left(\sum_{m\in
S_{t}}|\widehat{A}(m)|^{2}\right)\cdot\left(\sum_{m^{\prime}\in
S_{t}}|\widehat{B}(m^{\prime})|^{2}\right)$ $\displaystyle\leq
p^{6}\left(\sum_{t\in\mathbb{F}_{p}}\sum_{m,m^{\prime}\in
S_{t}}|\widehat{A}(m)|^{2}|\widehat{A}(m^{\prime})|^{2}\right)^{1/2}\cdot\left(\sum_{t\in\mathbb{F}_{p}}\sum_{m,m^{\prime}\in
S_{t}}|\widehat{B}(m)|^{2}|\widehat{B}(m^{\prime})|^{2}\right)^{1/2}$
$\displaystyle=I_{A,A}^{1/2}\cdot I_{B,B}^{1/2}.$

From Theorem 2.7, one has

$I_{A,A}=N(A\times
A)+p^{5}\sum_{||m||\neq||m^{\prime}||}|\widehat{A}(m)|^{2}|\widehat{A}(m^{\prime})|^{2}-\frac{|A|^{4}}{p},$

and

$I_{B,B}=N(B\times
B)+p^{5}\sum_{||m||\neq||m^{\prime}||}|\widehat{B}(m)|^{2}|\widehat{B}(m^{\prime})|^{2}-\frac{|B|^{4}}{p}.$

By the Plancherel, we know that

$p^{5}\sum_{||m||\neq||m^{\prime}||}|\widehat{A}(m)|^{2}|\widehat{A}(m^{\prime})|^{2}\leq
p|A|^{2},~{}p^{5}\sum_{||m||\neq||m^{\prime}||}|\widehat{B}(m)|^{2}|\widehat{B}(m^{\prime})|^{2}\leq
p|B|^{2}.$

Hence,

  1. (1)

If $|A|\leq p$, then Corollary 2.9 gives $I_{A,A}\ll p|A|^{2}+|A|^{10/3}.$

  2. (2)

If $p\leq|A|\leq p^{5/4}$, then Corollary 2.9 gives $I_{A,A}\ll
p|A|^{2}+p^{2/3}|A|^{8/3}\ll p^{2/3}|A|^{8/3}.$

  3. (3)

If $p^{5/4}\leq|A|\leq p^{4/3}$, then Corollary 2.9 gives $I_{A,A}\ll
p|A|^{2}+p^{1/4}|A|^{3}\ll p^{1/4}|A|^{3}$.

The sum $I_{B,B}$ is estimated in the same way, namely,

  1. (1)

If $|B|\leq p$, then Corollary 2.9 gives $I_{B,B}\ll p|B|^{2}+|B|^{10/3}.$

  2. (2)

If $p\leq|B|\leq p^{5/4}$, then Corollary 2.9 gives $I_{B,B}\ll
p|B|^{2}+p^{2/3}|B|^{8/3}\ll p^{2/3}|B|^{8/3}.$

  3. (3)

If $p^{5/4}\leq|B|\leq p^{4/3}$, then Corollary 2.9 gives $I_{B,B}\ll
p|B|^{2}+p^{1/4}|B|^{3}\ll p^{1/4}|B|^{3}$.

When $|B|>p^{4/3}$, we use Theorem 2.6 to get that $I_{B,B}\ll p|B|^{5/2}$.

Combining these estimates gives us the desired result. ∎

###  2.3. An extension for general sets

In this subsection, we want to bound the sum

(2.1) $\displaystyle\sum_{\begin{subarray}{c}(m,m^{\prime})\neq(0,0),\\\
||m||=||m^{\prime}||\end{subarray}}|\widehat{P}(m,m^{\prime})|^{2},$

where $P$ is a general set in $\mathbb{F}_{q}^{2d}$.

######  Theorem 2.12.

Let $P\subset\mathbb{F}_{q}^{d}\times\mathbb{F}_{q}^{d}$. We have

$q^{3d-1}(q-1)\sum_{\begin{subarray}{c}(m,m^{\prime})\neq(0,0),\\\
||m||=||m^{\prime}||\end{subarray}}|\widehat{P}(m,m^{\prime})|^{2}\ll
q^{d}|P|.$

To prove this result, as in the prime field case, we use a double counting
argument to bound $N(P)$. To prove a connection between $N(P)$ and the sum
2.1, a number of results on exponential sums are needed.

For each $a\in\mathbb{F}_{q}\setminus\\{0\\}$, the Gauss sum $\mathcal{G}_{a}$
is defined by

$\mathcal{G}_{a}=\sum_{t\in\mathbb{F}_{q}\setminus\\{0\\}}\eta(t)\chi(at).$

The next lemma presents the explicit form the Gauss sum which can be found in
[15, Theorem 5.15].

######  Lemma 2.13.

Let $\mathbb{F}_{q}$ be a finite field of order $q=p^{\ell}$, where $p$ is an
odd prime and $\ell\in{\mathbb{N}}.$ We have

$\mathcal{G}_{1}=\left\\{\begin{array}[]{ll}{(-1)}^{\ell-1}q^{\frac{1}{2}}&\mbox{if}\quad
p\equiv 1\mod 4\\\ {(-1)}^{\ell-1}i^{\ell}q^{\frac{1}{2}}&\mbox{if}\quad
p\equiv 3\mod 4.\end{array}\right.$

We also need the following simple lemma, its proof can be found in [14].

######  Lemma 2.14.

For $\beta\in\mathbb{F}_{q}^{k}$ and $s\in\mathbb{F}_{q}\setminus\\{0\\}$, we
have

$\sum_{\alpha\in\mathbb{F}_{q}^{k}}\chi(s\alpha\cdot\alpha+\beta\cdot\alpha)=\eta^{k}(s)\mathcal{G}_{1}^{k}\chi\left(\frac{\|\beta\|}{-4s}\right).$

Let $V\subset\mathbb{F}_{q}^{2d}$ be the variety defined by

$x_{1}^{2}+\cdots+x_{d}^{2}-y_{1}^{2}-\cdots-y_{d}^{2}=0.$

The Fourier transform of $V$ can be computed explicitly in the following
lemma.

######  Lemma 2.15.

Let $(m,m^{\prime})\in\mathbb{F}_{q}^{2d}$.

  1. (1)

If $(m,m^{\prime})=(0,0)$, then

$\widehat{V}(m,m^{\prime})=\frac{1}{q}+\frac{q^{d}(q-1)}{q^{2d+1}}.$

  2. (2)

If $(m,m^{\prime})\neq(0,0)$ and $||m||=||m^{\prime}||$, then

$\widehat{V}(m,m^{\prime})=\frac{q^{d}(q-1)}{q^{2d+1}}.$

  3. (3)

If $(m,m^{\prime})\neq(0,0)$ and $||m||\neq||m^{\prime}||$, then

$\widehat{V}(m,m^{\prime})=\frac{-1}{q^{d+1}}.$

###### Proof.

By Lemma 2.14, we have

$\displaystyle\widehat{V}(m,m^{\prime})=\frac{1}{q^{2d}}V(x,y)\chi(-x\cdot
m-y\cdot m^{\prime})$
$\displaystyle=\frac{1}{q^{2d+1}}\sum_{x,y\in\mathbb{F}_{q}^{d}}\sum_{s\in\mathbb{F}_{q}}\chi(s(x_{1}^{2}+\cdots+x_{d}^{2}-y_{1}^{2}-\cdots-
y_{d}^{2}))\chi(-x_{1}m_{1}-\cdots-
x_{d}m_{d})\chi(-y_{1}m_{1}^{\prime}-\cdots-y_{d}m_{d}^{\prime})$
$\displaystyle=\frac{1}{q^{2d+1}}\sum_{x,y}\chi(-x\cdot m)\chi(-y\cdot
m^{\prime})+\frac{1}{q^{2d+1}}\mathcal{G}_{1}^{2d}\eta^{d}(-1)\sum_{s\neq
0}\chi\left(\frac{1}{4s}(||m||-||m^{\prime}||)\right).$

By Lemma 2.13, we have $\mathcal{G}_{1}^{2d}\eta^{d}(-1)=q^{d}$. Thus, the
lemma follows from the orthogonality of the character $\chi$. ∎

In the following, we compute $N(P)$ explicitly which is helpful to estimate
the sum 2.1.

######  Lemma 2.16.

For $P\subset\mathbb{F}_{q}^{d}\times\mathbb{F}_{q}^{d}$, we have

$N(P)=\left(\frac{1}{q}+\frac{q-1}{q^{d+1}}\right)|P|^{2}+q^{3d-1}(q-1)\sum_{\begin{subarray}{c}(m,m^{\prime})\neq(0,0),\\\
||m||=||m^{\prime}||\end{subarray}}|\widehat{P}(m,m^{\prime})|^{2}-q^{3d-1}\sum_{||m||\neq||m^{\prime}||}|\widehat{P}(m,m^{\prime})|^{2}.$

###### Proof.

We have

$\displaystyle N(P)=\sum_{x,u,y,v}P(x,u)P(y,v)V(x-y,u-v)$
$\displaystyle=\sum_{x,u,y,v}P(x,u)P(y,v)\sum_{m,m^{\prime}}\widehat{V}(m,m^{\prime})\chi((x-y)m+(u-v)m^{\prime})$
$\displaystyle=q^{4d}\sum_{m,m^{\prime}}\widehat{V}(m,m^{\prime})|\widehat{P}(m,m^{\prime})|^{2}.$

By Lemma 2.15, we obtain

$N(P)=\left(\frac{1}{q}+\frac{q-1}{q^{d+1}}\right)|P|^{2}+q^{3d-1}(q-1)\sum_{\begin{subarray}{c}(m,m^{\prime})\neq(0,0),\\\
||m||=||m^{\prime}||\end{subarray}}|\widehat{P}(m,m^{\prime})|^{2}-q^{3d-1}\sum_{||m||\neq||m^{\prime}||}|\widehat{P}(m,m^{\prime})|^{2},$

and the lemma follows. ∎

We now bound $N(P)$ by a different argument.

######  Theorem 2.17.

For $P\subset\mathbb{F}_{q}^{d}\times\mathbb{F}_{q}^{d}$. We have

$\left|N(P)-\frac{|P|^{2}}{q}\right|\ll q^{d}|P|.$

######  Remark 2.18.

This theorem is sharp in odd dimensions. More precisely, it cannot be improved
to the form

$N(P)\ll\frac{|P|^{2}}{q}+q^{d-\epsilon}|P|,$

for any $\epsilon>0$. Since otherwise, it would say that any set
$A\subset\mathbb{F}_{q}^{d}$ with $|A|\gg
q^{\frac{d+1}{2}-\frac{\epsilon}{2}}$ has at least $\gg q$ distances. This is
not possible due to examples in [9, 11].

###### Proof.

To prove this lemma, we start with the following observation that

$||x-u||=||y-v||$

can be written as

$-2x\cdot u+2y\cdot v=||y||+||v||-||x||-||u||.$

We now write $N(P)$ as follows

$\displaystyle N(P)$
$\displaystyle=\frac{1}{q}\sum_{s\in\mathbb{F}_{q}}\sum_{\begin{subarray}{c}(x,y)\in
P,\\\ (u,v)\in P\end{subarray}}\chi\left(s(-2x\cdot u+2y\cdot
v-||y||-||v||+||x||+||u||)\right)$
$\displaystyle=\frac{|P|^{2}}{q}+\frac{1}{q}\sum_{s\neq
0}\sum_{\begin{subarray}{c}(x,y)\in P,\\\ (u,v)\in
P\end{subarray}}\chi\left(s(-2x\cdot u+2y\cdot
v-||y||-||v||+||x||+||u||)\right)$
$\displaystyle=\frac{|P|^{2}}{q}+\frac{1}{q}\sum_{s\neq
0}\sum_{\begin{subarray}{c}(x,y,||x||-||y||)\in P^{\prime}\\\ (u,v)\in
P\end{subarray}}\chi(s((x,y)\cdot(-2u,2v)-||y||-||v||+||x||+||u||))$
$\displaystyle=\frac{|P|^{2}}{q}+\mathtt{Error},$

here $P^{\prime}:=\\{(x,y,||x||-||y||)\colon(x,y)\in
P\\}\subset\mathbb{F}_{q}^{2d+1}.$ We now estimate the term $\mathtt{Error}$.

$\displaystyle\mathtt{Error}^{2}\leq\frac{|P|}{q^{2}}\sum_{(x,y,t)\in\mathbb{F}_{q}^{2d+1}}\sum_{s,s^{\prime}\neq
0}\sum_{\begin{subarray}{c}(u,v)\in P,\\\ (u^{\prime},v^{\prime})\in
P\end{subarray}}\chi\left(s(-2x\cdot u+2y\cdot
v-||y||-||v||+||x||+||u||)\right)$
$\displaystyle\cdot\chi\left(s^{\prime}(2x\cdot u^{\prime}-2y\cdot
v^{\prime}+||y||+||v^{\prime}||-||x||-||u^{\prime}||)\right)$
$\displaystyle=\frac{|P|}{q^{2}}\sum_{(x,y,t)\in\mathbb{F}_{q}^{2d+1}}\sum_{s,s^{\prime}\neq
0}\sum_{\begin{subarray}{c}(u,v)\in P,\\\ (u^{\prime},v^{\prime})\in
P\end{subarray}}\chi(x\cdot(-2su+2s^{\prime}u^{\prime}))\cdot\chi(y\cdot(2sv-2s^{\prime}v^{\prime}))\cdot\chi(t(s-s^{\prime}))$
$\displaystyle\cdot\chi(s(||u||-||v||)-s^{\prime}(||u^{\prime}||-||v^{\prime}||))$
$\displaystyle\leq|P|^{2}q^{2d}.$

In other words, we obtain

$N(P)\leq\frac{|P|^{2}}{q}+q^{d}|P|.$

This completes the proof. ∎

With Lemma 2.16 and Theorem 2.17 in hand, we are ready to prove Theorem 2.12.

###### Proof of Theorem 2.12.

Indeed, one has

$\displaystyle
q^{3d-1}(q-1)\sum_{\begin{subarray}{c}(m,m^{\prime})\neq(0,0),\\\
||m||=||m^{\prime}||\end{subarray}}|\widehat{P}(m,m^{\prime})|^{2}=N(P)-\frac{|P|^{2}}{q}-\frac{q-1}{q^{d+1}}|P|^{2}+q^{3d-1}\sum_{||m||\neq||m^{\prime}||}|\widehat{P}(m,m^{\prime})|^{2}.$

By Plancherel theorem, we have

$\sum_{||m||\neq||m^{\prime}||}|\widehat{P}(m,m^{\prime})|^{2}\leq\frac{|P|}{q^{2d}}.$

So, the theorem follows directly from Theorem 2.17. ∎

##  3\. Warm-up incidence theorems

In this section, we present direct incidence bounds which can be proved by
using the Cauchy-Schwarz inequality and the results on $N(P)$ from the
previous setion.

######  Theorem 3.1.

Let $P$ be a set of points in $\mathbb{F}_{q}^{d}\times\mathbb{F}_{q}^{d}$ and
$R$ be a set of rigid motions in $\mathbb{F}_{q}^{d}$. Then we have

$I(P,R)\ll|R|^{1/2}|O(d-1)|^{1/2}\left(\frac{|P|^{2}}{q}+Cq^{d}|P|\right)^{1/2}+|R|.$

###### Proof.

For each $r\in R$, denote $I(P,r)$ by $i(r)$. Then, it is clear that

(3.1) $I(P,R)=\sum_{r\in R}i(r)\leq|R|^{1/2}\left(\sum_{r\in
R}i(r)^{2}\right)^{1/2}.$

We observe that, for each $r\in R$, $i(r)^{2}$ counts the number of pairs
$(a_{1},b_{1}),(a_{2},b_{2})\in P$ on $r$. This infers
$||a_{1}-a_{2}||=||b_{1}-b_{2}||$. Thus, the sum $\sum_{r\in R}i(r)^{2}$ can
be bounded by

$|O(d-1)|N(P)+I(P,R),$

where we used the fact that the stabilizer of a non-zero element is at most
$|O(d-1)|$, and the term $I(P,R)$ comes from pairs
$(a_{1},b_{1}),(a_{2},b_{2})\in P$ with $a_{1}=a_{2}$ and $b_{1}=b_{2}$.
Therefore,

$\sum_{r\in R}i(r)^{2}\ll|O(d-1)|N(P)+I(P,R).$

Using Theorem 2.17, the theorem follows. ∎

If we use the trivial bound $N(P)\leq|P|^{2}$, then the next theorem is
obtained.

######  Theorem 3.2.

Let $P$ be a set of points in $\mathbb{F}_{q}^{d}\times\mathbb{F}_{q}^{d}$ and
$R$ be a set of rigid motions in $\mathbb{F}_{q}^{d}$. Then we have

$I(P,R)\ll|P||R|^{1/2}|O(d-1)|^{1/2}+|R|.$

Compared to Theorem 1.14 and Theorem 1.15, these two incidence theorems only
give weaker upper bounds and tell us nothing about the lower bounds.

In two dimensions over prime fields, if $P=A\times B$ with $|A|,|B|\leq p$,
then Corollary 2.9 says that $N(P)\ll|A|^{5/3}|B|^{5/3}$. As above, the next
theorem is a direct consequence.

######  Theorem 3.3.

Let $P=A\times B$ with $A,B\subset\mathbb{F}_{p}^{2}$ and $p\equiv 3\mod 4$.
Assume that $|A|,|B|\leq p$, then we have

$I(P,R)\ll|P|^{5/6}|R|^{1/2}+|R|.$

In particular, if $|P|=|R|=N$ then

$I(P,R)\ll N^{4/3}.$

##  4\. Incidence theorems: proofs

Let us present a framework that will work for most cases.

We have

$\displaystyle I(P,R)=\sum_{\begin{subarray}{c}(x,y)\in P,\\\ (g,z)\in
R\end{subarray}}1_{x=gy+z}=\frac{1}{q^{d}}\sum_{m\in\mathbb{F}_{q}^{d}}\sum_{\begin{subarray}{c}(x,y)\in
P,\\\ (g,z)\in R\end{subarray}}\chi\left(m\cdot(x-gy-z)\right)$
$\displaystyle=\frac{|P||R|}{q^{d}}+\frac{1}{q^{d}}\sum_{m\in\mathbb{F}_{q}^{d}\setminus\\{0\\}}\sum_{\begin{subarray}{c}(x,y)\in
P,\\\ (g,z)\in R\end{subarray}}\chi(m\cdot(x-gy-z))$
$\displaystyle=\frac{|P||R|}{q^{d}}+q^{d}\sum_{m\neq 0}\sum_{(g,z)\in
R}\widehat{P}(-m,gm)\chi(-mz)=:I+II,$

where $\widehat{P}(u,v)=q^{-4d}\sum_{(x,y)\in P}\chi(-xu-yv)$. We next bound
the second term. By the Cauchy-Schwarz inequality, we have

$\displaystyle II$ $\displaystyle\leq q^{d}|R|^{1/2}\left(\sum_{(g,z)\in
O(d)\times\mathbb{F}_{q}^{d}}\sum_{m_{1},m_{2}\neq
0}\widehat{P}(-m_{1},gm_{1})\overline{\widehat{P}(-m_{2},gm_{2})}\chi(z(-m_{1}+m_{2}))\right)^{1/2}$
$\displaystyle=q^{d}|R|^{1/2}\left(q^{d}\sum_{g\in O(d)}\sum_{m\neq
0}|\widehat{P}(m,-gm)|^{2}\right)^{1/2}$
$\displaystyle=q^{\frac{3d}{2}}|R|^{1/2}\left(\sum_{g\in O(d)}\sum_{m\neq
0}|\widehat{P}(m,-gm)|^{2}\right)^{1/2}.$

We now consider two cases.

Case $1$: If $P$ is a general set in $\mathbb{F}_{q}^{2d}$, then we have

$\sum_{g\in O(d)}\sum_{m\neq
0}|\widehat{P}(m,-gm)|^{2}\leq|O(d-1)|\sum_{\begin{subarray}{c}(m,m^{\prime})\neq(0,0),\\\
||m||=||m^{\prime}||\end{subarray}}|\widehat{P}(m,m^{\prime})|^{2},$

where we used the fact that the stabilizer of a non-zero element in
$\mathbb{F}_{q}^{d}$ is at most $|O(d-1)|$. From here, we apply Theorem 2.12
to obtain Theorem 1.14.

Case $2$: If $P$ is of the structure $A\times B$, where
$A,B\subset\mathbb{F}_{q}^{d}$, then

$\widehat{P}(m,-gm)=\widehat{A}(m)\widehat{B}(-gm).$

Thus,

$\displaystyle\sum_{g\in O(d)}\sum_{m\neq
0}|\widehat{P}(m,-gm)|^{2}=\sum_{g\in O(d)}\sum_{m\neq
0}|\widehat{A}(m)|^{2}|\widehat{B}(-gm)|^{2}$
$\displaystyle\leq|O(d-1)|\sum_{m\neq
0}|\widehat{A}(m)|^{2}\sum_{\begin{subarray}{c}m^{\prime}\neq 0,\\\
||m^{\prime}||=||m||\end{subarray}}|\widehat{B}(m^{\prime})|^{2}$
$\displaystyle\leq|O(d-1)|\sum_{||m||=||m^{\prime}||}|\widehat{A}(m)|^{2}|\widehat{B}(m^{\prime})|^{2},$

where we again used the fact that the stabilizer of a non-zero element in
$\mathbb{F}_{q}^{d}$ is at most $|O(d-1)|$.

From here, we apply Theorem 2.5, Theorem 2.6, and Theorem 2.11 to obtain
Theorem 1.15, Theorem 1.16, Theorem 1.17, Theorem 1.18, and Theorem 1.19,
except Theorem 1.17 (2) and (3).

To prove these two statements, we need to bound the sum
$\sum_{\begin{subarray}{c}g\in O(2),\\\ m\neq
0\end{subarray}}|\widehat{P}(m,-gm)|^{2}$ in a different way. More precisely,

$\displaystyle\sum_{\begin{subarray}{c}g\in O(2),\\\ m\neq
0\end{subarray}}|\widehat{P}(m,-gm)|^{2}=\frac{1}{p^{8}}\sum_{\begin{subarray}{c}g\in
O(d),\\\ m\neq
0\end{subarray}}\sum_{x_{1},y_{1},x_{2},y_{2}}P(x_{1},y_{1})P(x_{2},y_{2})\chi(m(x_{1}-gy_{1}-x_{2}+gy_{2}))$
$\displaystyle=\frac{1}{p^{8}}\left(p^{2}\sum_{g\in
O(2)}\sum_{x_{1},x_{2},y_{1},y_{2}}P(x_{1},y_{1})P(x_{2},y_{2})1_{x_{1}-x_{2}=g(y_{1}-y_{2})}-|O(2)||P|^{2}\right).$

Moreover,

$\displaystyle\sum_{g\in
O(2)}\sum_{x_{1},x_{2},y_{1},y_{2}}P(x_{1},y_{1})P(x_{2},y_{2})1_{x_{1}-x_{2}=g(y_{1}-y_{2})}\leq|O(2)||P|+|N(P)|.$

The first approach is equivalent to bound $N(P)$ by using Theorem 2.7 and
Theorem 2.11.

If $|A|\leq p$ and $p\leq|B|\leq p^{5/4}$, then Theorem 2.11 tells us that

$I_{A,B}\ll(p|A|^{2}+|A|^{10/3})^{1/2}\cdot p^{1/3}|B|^{4/3}.$

As a consequence, one has

$N(P)\leq\frac{|A|^{2}|B|^{2}}{p}+(p|A|^{2}+|A|^{10/3})^{1/2}\cdot
p^{1/3}|B|^{4/3}.$

However, when $|A|\leq p$ and $p\leq|B|\leq p^{5/4}$, by the Cauchy-Schwarz
inequality, a better upper bound can be obtained. Indeed, using Corollary 2.9,
we have

$N(P)\leq N(A\times A)^{1/2}N(B\times B)^{1/2}\ll p^{1/3}|A|^{5/3}|B|^{4/3}.$

Together with the above estimates, we obtain

$\sum_{\begin{subarray}{c}g\in O(2),\\\ m\neq
0\end{subarray}}|\widehat{P}(m,-gm)|^{2}\leq\frac{|P|}{p^{5}}+\frac{|P|^{4/3}|A|^{1/3}}{p^{17/3}}.$

This gives

$\left|I(P,R)-\frac{|P||R|}{p^{2}}\right|\ll
p^{3}|P|^{1/2}|R|^{1/2}\left(\frac{1}{p^{5}}+\frac{|P|^{1/3}|A|^{1/3}}{p^{17/3}}\right)^{1/2}.$

Similarly, if $|A|\leq p$ and $|B|\leq p$, we have

$N(P)\ll|A|^{5/3}|B|^{5/3},$

and

$\displaystyle\sum_{\begin{subarray}{c}g\in O(2),\\\ m\neq
0\end{subarray}}|\widehat{P}(m,-gm)|^{2}$
$\displaystyle\ll\frac{|P|}{p^{5}}+\frac{|P|^{5/3}}{p^{6}}.$

Hence,

$\left|I(P,R)-\frac{|P||R|}{p^{2}}\right|\ll
p^{3}|P|^{1/2}|R|^{1/2}\left(\frac{1}{p^{5}}+\frac{|P|^{2/3}}{p^{6}}\right)^{1/2}.$

Sharpness of Theorem 1.14 and Theorem 1.15 in odd dimensions:

We first show that Theorem 1.14 is sharp up to a constant factor.

Let $X$ be an arithmetic progression in $\mathbb{F}_{q}$, and let
$v_{1},\ldots,v_{\frac{d-1}{2}}$ be $(v-1)/2$ vectors in
$\mathbb{F}_{q}^{d-1}\times\\{0\\}$ such that $v_{i}\cdot v_{j}=0$ for all
$1\leq i\leq j\leq(d-1)/2$. The existence of such vectors can be found in
Lemma 5.1 in [9] when ($d=4k+1$) or ($d=4k+3$ with $q\equiv 3\mod 4$). Define

$A=B=\mathbb{F}_{q}\cdot v_{1}+\cdots+\mathbb{F}_{q}\cdot
v_{\frac{d-1}{2}}+X\cdot e_{d},$

here $e_{d}=(0,\ldots,0,1)$. Set $P=A\times B$. The number of quadruples
$(x,y,u,v)\in A\times A\times B\times B$ such that $||x-y||=||u-v||$, is at
least a constant times $|X|^{2}q^{2d-1}$, say, $|X|^{2}q^{2d-1}/2$. For each
$(g,z)\in O(d)\times\mathbb{F}_{q}^{d}$, let $i(g,z)=\\#\\{(u,v)\in A\times
B\colon gu+z=v\\}$. Define $\mathcal{Q}=\sum_{(g,z)}i(g,z)^{2}$. So,
$\mathcal{Q}\geq|X|^{2}q^{2d-1}|O(d-1)|/2$.

We call $g$ $\mathbf{type-k}$, $0\leq k\leq(d-1)/2$, if the rank of the system

$\left\\{v_{1},\ldots,v_{(d-1)/2},e_{d},gv_{1},\ldots,gv_{(d-1)/2}\right\\}$

is $d-k$.

For any pair $(g,z)$, where $g$ is $\mathbf{type-0}$, the number of $(u,v)\in
A\times B$ such that $gu+z=v$ is at most $|X|$.

For $0<k\leq(d-1)/2$, if $g$ is $\mathbf{type-k}$, then, assume,

$gv_{1},\ldots,gv_{k}\in\mathtt{Span}(gv_{k+1},\ldots,gv_{\frac{d-1}{2}},v_{1},\ldots,v_{\frac{d-1}{2}},e_{d}).$

Let $N(k)$ be the contribution to $\mathcal{Q}$ of pairs $(g,z)$ such that $g$
is $\mathbf{type-k}$. We have $N(k)$ is at most the number of
$\mathbf{type-k}$ $g$s times $|A|^{2}$. For each $k$, to count the number of
$\mathbf{type-k}$ $g$s, we observe that $||v_{i}||=0$, so $||gv_{i}||=0$. The
number of elements of norm zero in
$\mathtt{Span}(gv_{k+1},\ldots,gv_{\frac{d-1}{2}},v_{1},\ldots,v_{\frac{d-1}{2}},e_{d})$
is at most $q^{d-k}$. So, the total number of $\mathbf{type-k}$ $g$s such that

$gv_{1}\in\mathtt{Span}(gv_{k+1},\ldots,gv_{\frac{d-1}{2}},v_{1},\ldots,v_{\frac{d-1}{2}},e_{d})$

is at most $q^{d-k}|O(d-1)|$, which is, of course, larger than the number of
$g$ satisfying

$gv_{1},\ldots,gv_{k}\in\mathtt{Span}(gv_{k+1},\ldots,gv_{\frac{d-1}{2}},v_{1},\ldots,v_{\frac{d-1}{2}},e_{d}).$

Summing over all $k\geq 1$ and the corresponding $\mathbf{type-k}$ $g$s, the
contribution to $\mathcal{Q}$ is at most
$|X|^{2}q^{d-1}q^{d-k}|O(d-1)|\leq|X|^{2}q^{d}|O(d)|q^{-k}$. So, the pairs
$(g,z)$, where $g$ is $\mathbf{type-k}$ and $k\geq 1$, contribute at most
$\ll|X|^{2}q^{d-1}|O(d-1)|$ which is much smaller than $\mathcal{Q}/2$. Thus,
we can say that the contribution of $\mathcal{Q}$ mainly comes from
$\mathbf{type-0}$ $g$s.

Let $R$ be the set of pairs $(g,z)\in O(d)\times\mathbb{F}_{q}^{d}$ such that
$i(g,z)\geq 2$ and $g$ is $\mathbf{type-0}$.

Whenever $|X|=cq$, $0<c<1$, by a direct computation, Theorem 1.14 shows that

$I(P,R)\leq
Cq^{\frac{d^{2}-d+2}{4}}\sqrt{|P||R|}=Cq^{\frac{d^{2}+d}{4}}|X|\sqrt{|R|}\leq
C|X||O(d)|q^{d},$

for some positive constant $C$. This gives $\mathcal{Q}\leq
C|X|^{2}|O(d)|q^{d}$. This matches the lower bound of $|X|^{2}q^{d}|O(d)|/2$
up to a constant factor.

We note that this example can also be used to show the sharpness of Theorem
1.15(2) in the same way.

For the sharpness of Theorem 1.15(1), let $X\subset\mathbb{F}_{q}$ with
$|X|=cq$, $0<c<1$. Set

$A=X\cdot v_{1}+\cdots+X\cdot v_{\frac{d-1}{2}},~{}B=X\cdot
v_{1}+\cdots+X\cdot v_{\frac{d-1}{2}}+X\cdot e_{d},$

where $e_{d}=(0,\ldots,0,1)$. Since any vector in $A-gB$ is of the form

$-g(x_{1}v_{1}+\cdots+x_{\frac{d-1}{2}}v_{\frac{d-1}{2}})+y_{1}v_{1}+\cdots+y_{\frac{d-1}{2}}v_{\frac{d-1}{2}}-x_{\frac{d+1}{2}}ge_{d},$

where $x_{i},y_{i}\in X$, we have $|A-gB|\leq|X|^{d}\leq c^{d}q^{d}$ for all
$g\in O(d)$. Let $R$ be the set of $(g,z)$ such that $z\in A-gB$. Then, we
have $|R|\leq c^{d}q^{d}|O(d)|$. Theorem 1.15(1) gives

$I(P,R)\leq Cq^{\frac{d^{2}-d}{4}}\sqrt{|P||R|}\leq
Cc^{d}q^{\frac{d^{2}+d}{2}},$

for some positive constant $C$.

On the other hand, by the definitions of $A$, $B$, and $R$, we have

$I(P,R)=|O(d)||P|=c^{d}q^{d}|O(d)|=c^{d}q^{\frac{d^{2}+d}{2}}.$

This matches the incidence bound up to a constant factor.

##  5\. Intersection pattern I: proofs

In this section, we prove Theorem 1.4, Theorem 1.5, and Theorem 1.6.

###### Proof of Theorem 1.4.

Set

$\displaystyle E_{1}$ $\displaystyle=\left\\{g\in
O(d)\colon\\#\\{z\in\mathbb{F}_{q}^{d}\colon|A\cap(g(B)+z)|\leq\frac{|A||B|}{2q^{d}}\\}\geq
cq^{d}\right\\}$ $\displaystyle E_{2}$ $\displaystyle=\left\\{g\in
O(d)\colon\\#\\{z\in\mathbb{F}_{q}^{d}\colon|A\cap(g(B)+z)|\geq\frac{3|A||B|}{2q^{d}}\\}\geq
cq^{d}\right\\}$

for some $c\in(0,1)$.

We first show that $|E_{1}|\ll\frac{|O(d-1)|q^{2d}}{c|A||B|}$. Indeed, let
$R_{1}$ be the set of pairs $(g,z)$ with $g\in E_{1}$ and
$|A\cap(g(B)+z)|\leq|A||B|/2q^{d}$. It is clear that $I(A\times
B,R_{1})\leq\frac{|A||B||R_{1}|}{2q^{d}}$. On the other hand, Theorem 1.14
also tells us that

$I(A\times
B,R_{1})\geq\frac{|A||B||R_{1}|}{q^{d}}-C|O(d-1)|^{1/2}q^{d/2}\sqrt{|A||B||R_{1}|},$

for some positive constant $C$. Thus, we have

$|R_{1}|\leq\frac{4C^{2}|O(d-1)|q^{3d}}{|A||B|}.$

Together this with $|R_{1}|\geq c|E_{1}|q^{d}$ implies the desired conclusion.

Similarly, for $E_{2}$, let $R_{2}$ be the set of pairs $(g,z)$ with $g\in
E_{2}$ and $|A\cap(g(B)+z)|\geq 3|A||B|/2q^{d}$. Then, $I(A\times
B,R_{2})\geq\frac{3|A||B||R_{2}|}{2q^{d}}$. By Theorem 1.14 again, we obtain

$I(A\times
B,R_{2})\leq\frac{|A||B||R_{2}|}{q^{d}}+C|O(d-1)|^{1/2}q^{d/2}\sqrt{|A||B||R_{2}|},$

and thus

$|R_{2}|\leq\frac{4C^{2}|O(d-1)|q^{3d}}{|A||B|}.$

The fact $|R_{2}|\geq c|E_{2}|q^{d}$ implies our desired result
$|E_{2}|\ll\frac{|O(d-1)|q^{2d}}{c|A||B|}$.

Next, note that for any $g\in O(d)\setminus(E_{1}\cup E_{2})$, by setting
$c=1/4$, we have

$\displaystyle\\#\\{z\in\mathbb{F}_{q}^{d}\colon|A\cap(g(B)+z)|\geq\frac{|A||B|}{2q^{d}}\\}\geq\frac{3}{4}q^{d}$
$\displaystyle\\#\\{z\in\mathbb{F}_{q}^{d}\colon|A\cap(g(B)+z)|\leq\frac{3|A||B|}{2q^{d}}\\}\geq\frac{3}{4}q^{d},$

implying that there at least $\geq q^{d}/2$ elements $z$ satisfying

$\frac{|A||B|}{2q^{d}}\leq\\#\\{z\in\mathbb{F}_{q}^{d}\colon|A\cap(g(B)+z)|\\}\leq\frac{3|A||B|}{2q^{d}}.$

∎

###### Proof of Theorem 1.5.

We consider the case when $|A|<q^{\frac{d-1}{2}}$, since other cases can be
treated in the same way. We use the same notations as in Theorem 1.4. By
Theorem 1.15, there exists $C>0$ such that

$I(A\times
B,R_{1})\geq\frac{|A||B||R_{1}|}{q^{d}}-Cq^{(d^{2}-d)/4}\sqrt{|A||B||R_{1}|},$

and

$I(A\times
B,R_{2})\leq\frac{|A||B||R_{2}|}{q^{d}}+Cq^{(d^{2}-d)/4}\sqrt{|A||B||R_{2}|}.$

This, together with $|R_{1}|\geq c|E_{1}|q^{d}$ and $|R_{2}|\geq
c|E_{2}|q^{d}$, implies that

$|E_{1}|,|E_{2}|\ll\frac{q^{(d^{2}+d)/2}}{|A||B|}.$

As similar to the proof of Theorem 1.4, the theorem follows. ∎

###### Proof of Theorem 1.6.

We use the same notations as in Theorem 1.4 for $d=2$. By Theorem 1.16, there
exists $C>0$ such that

$I(A\times
B,R_{1})\geq\frac{|A||B||R_{1}|}{q^{2}}-Cq^{1/2}\sqrt{|A||B||R_{1}|}|A|^{1/4},$

and

$I(A\times
B,R_{2})\leq\frac{|A||B||R_{2}|}{q^{2}}+Cq^{1/2}\sqrt{|A||B||R_{2}}||A|^{1/4}.$

This, together with $|R_{1}|\geq c|E_{1}|q^{2}$ and $|R_{2}|\geq
c|E_{2}|q^{2}$, gives that

$|E_{1}|,|E_{2}|\ll\frac{q^{3}}{|A|^{1/2}|B|}.$

As similar to the proof of Theorem 1.4, the theorem follows. ∎

Using Theorem 1.18 and Theorem 1.19 respectively, the proofs of Theorem 1.8
and Theorem 1.9 can be obtained by the same way.

Sharpness of Theorem 1.4 and Theorem 1.5:

The constructions we present here are similar to those in the previous
section. For the reader’s convenience, we reproduce the details here.

It follows from the proof of Theorem 1.4 that for any $0<c<1$, there exists
$C=C(c)$ such that if $|A||B|\geq Cq^{d+1}$, then there are at least
$(1-c)|O(d)|q^{d}$ pairs $(g,z)\in O(d)\times\mathbb{F}_{q}^{d}$ such that

(5.1) $\frac{|A||B|}{2q^{d}}\leq|A\cap(g(B)+z)|\leq\frac{3|A||B|}{2q^{d}}.$

We now show that this result is sharp in the sense that for $0<c<1$ small
enough, say, $8c<1/9(1-c)$, there exist $A,B\subset\mathbb{F}_{q}^{d}$ with
$|A|=|B|=|X|q^{\frac{d-1}{2}}$, $cq<|X|<1/9(1-c)q$, such that the number of
pairs $(g,z)\in O(d)\times\mathbb{F}_{q}^{d}$ satisfying 5.1 is at most
$(1-c)|O(d)|q^{d}$.

To be precise, let $X$ be an arithmetic progression in $\mathbb{F}_{q}$, and
let $v_{1},\ldots,v_{\frac{d-1}{2}}$ be $(v-1)/2$ vectors in
$\mathbb{F}_{q}^{d-1}\times\\{0\\}$ such that $v_{i}\cdot v_{j}=0$ for all
$1\leq i\leq j\leq(d-1)/2$. The existence of such vectors can be found in
Lemma 5.1 in [9] when ($d=4k+1$) or ($d=4k+3$ with $q\equiv 3\mod 4$). Define

$A=B=\mathbb{F}_{q}\cdot v_{1}+\cdots+\mathbb{F}_{q}\cdot
v_{\frac{d-1}{2}}+X\cdot e_{d},$

here $e_{d}=(0,\ldots,0,1)$.

We first note that the distance between two points in $A$ or $B$ is of the
form $(x-x^{\prime})^{2}$. By a direct computation and the fact that $X$ is an
arithmetic progression, the number of quadruples $(x,y,u,v)\in A\times A\times
A\times A$ such that $||x-y||=||u-v||$, is at least a constant times
$|X|^{3}q^{2d-2}$, say, $|X|^{3}q^{2d-2}/2$. For each $(g,z)\in
O(d)\times\mathbb{F}_{q}^{d}$, let $i(g,z)=\\#\\{(u,v)\in A\times B\colon
gu+z=v\\}$. Define $\mathcal{Q}=\sum_{(g,z)}i(g,z)^{2}$. So,
$\mathcal{Q}\geq|X|^{3}q^{2d-2}|O(d-1)|/2$.

We note that $|A|=|B|=|X|q^{\frac{d-1}{2}}$. If there were at least
$(1-c)|O(d)|q^{d}$ pairs $(g,z)\in O(d)\times\mathbb{F}_{q}^{d}$ satisfying
5.1, then we would bound $\mathcal{Q}$ in a different way, which leads to a
bound that much smaller than $|X|^{3}|O(d-1)|q^{2d-1}$, so we have a
contradiction.

Choose $(1-c)|O(d)|q^{d}$ pairs $(g,z)$ satisfying 5.1. The contribution of
these pairs is at most $\frac{9(1-c)}{4}|O(d)|q^{d}\frac{|X|^{4}}{q^{2}}$ to
$\mathcal{Q}$.

The number of remaining pairs $(g,z)$ is at most $c|O(d)|q^{d}$. We now
compute the contribution of these pairs to $\mathcal{Q}$. As before, we call
$g$ $\mathbf{type-k}$, $0\leq k\leq(d-1)/2$, if the rank of the system
$\\{v_{1},\ldots,v_{(d-1)/2},e_{d},gv_{1},\ldots,gv_{(d-1)/2}\\}$ is $d-k$.

For any pair $(g,z)$, where $g$ is $\mathbf{type-0}$, the number of $(u,v)\in
A\times B$ such that $gu+z=v$ is at most $|X|$. Thus, the contribution of
pairs with $\mathbf{type-0}$ $g$s is at most $c|O(d)|q^{d}|X|^{2}$.

As before, the contribution to $\mathcal{Q}$ of $\mathbf{type-k}$ $g$s, with
$k\geq 1$, is at most
$|X|^{2}q^{d-1}q^{d-k}|O(d-1)|\leq|X|^{2}q^{d}|O(d)|q^{-k}$. In other words,
we have

$\displaystyle\mathcal{Q}\leq\frac{9(1-c)}{4}|O(d)|q^{d}\frac{|X|^{4}}{q^{2}}+c|O(d)|q^{d}|X|^{2}+\sum_{k=1}^{\frac{d-1}{2}}|X|^{2}|O(d)|q^{d}\frac{1}{q^{k}}$
$\displaystyle=\frac{9(1-c)}{4}|O(d)|q^{d}\frac{|X|^{4}}{q^{2}}+2c|O(d)|q^{d}|X|^{2},$

when $q$ is large enough. By choosing $c$ small enough, we see that
$\mathcal{Q}<|X|^{3}q^{2d-2}|O(d-1)|/2$, a contradiction.

The second statement of Theorem 1.5 is valid in the range $|B|\gg
q^{\frac{d+1}{2}}$. This is also sharp in odd dimensions by the above
construction, since we can choose $|A|=|B|<q^{\frac{d+1}{2}}$ and the
conclusion fails.

The first statement of Theorem 1.5 is valid in the range $|A||B|\gg q^{d}$. To
see its sharpness, we construct two sets $A$ and $B$ with
$|A|=c^{\frac{d-1}{2}}q^{\frac{d-1}{2}}$,
$|B|=c^{\frac{d+1}{2}}q^{\frac{d+1}{2}}$, and the number of $z$ in
$\mathbb{F}_{q}^{d}$ such that $A\cap(gB+z)\neq\emptyset$ is at most
$|A-gB|\leq c^{d}q^{d}$ for any $g\in O(d)$. Let
$v_{1},\ldots,v_{\frac{d-1}{2}}$ are linearly independent vectors in
$\mathbb{F}_{q}^{d-1}\times\\{0\\}$. Let $X\subset\mathbb{F}_{q}$ with
$|X|=cq$. Set

$A=X\cdot v_{1}+\cdots+X\cdot v_{\frac{d-1}{2}},~{}B=X\cdot
v_{1}+\cdots+X\cdot v_{\frac{d-1}{2}}+X\cdot e_{d},$

where $e_{d}=(0,\ldots,0,1)$. Since any vector in $A-gB$ is of the form

$-g(x_{1}v_{1}+\cdots+x_{\frac{d-1}{2}}v_{\frac{d-1}{2}})+y_{1}v_{1}+\cdots+y_{\frac{d-1}{2}}v_{\frac{d-1}{2}}-x_{\frac{d+1}{2}}ge_{d},$

where $x_{i},y_{i}\in X$, we have $|A-gB|\leq|X|^{d}\leq c^{d}q^{d},$ for all
$g\in O(d)$.

##  6\. Intersection pattern II: proofs

In this section, we prove Theorem 1.12.

###### Proof of Theorem 1.12.

Let $E$ be the set of $g$ in $O(d)$ such that $|S_{g}(P)|<q^{d}/2$ and
$R=\\{(g,S_{g}(P))\colon g\in E\\}$. By Theorem 1.14, we first observe that

$I(P,R)\leq\frac{|P||R|}{q^{d}}+|O(d-1)|^{1/2}q^{d/2}|P|^{1/2}|R|^{1/2}.$

Note that $|R|<|E|q^{d}/2$ and $I(P,R)=|P||E|$. This infers

$|P||E|\leq q^{d}|O(d-1)|^{1/2}|P|^{1/2}|E|^{1/2}.$

So,

$|E|\ll\frac{q^{2d}|O(d-1)|}{|P|},$

as desired. ∎

##  7\. Growth estimates under orthogonal matrices: proofs

In this section, we prove Theorem 1.21, Theorem 1.22, Theorem 1.23, Theorem
1.24, Theorem 1.25, and Theorem 1.26.

###### Proof of Theorem 1.21.

Set $P=A\times B$. Let $\lambda=|B|^{1+\epsilon}$. Define

$E=\\{g\in O(d)\colon|A-gB|\leq\lambda\\}.$

Set $R=\\{(g,z)\colon z\in A-gB,g\in E\\}$. We observe that $I(P,R)=|P||E|$.
Applying Theorem 1.14, one has a constant $C>0$ such that

$|P||E|=I(P,R)\leq\frac{|P||R|}{q^{d}}+C\sqrt{|O(d-1)|}q^{d/2}|P|^{1/2}|R|^{1/2}.$

Using the fact that $|R|\leq\lambda|E|$ with $\lambda<q^{d}/2$, we have

$\frac{|P||E|}{2}\leq C\sqrt{|O(d-1)|}q^{d/2}|P|^{1/2}|R|^{1/2}.$

This implies

$|E|\ll\frac{|O(d-1)|\lambda q^{d}}{|A||B|}.$

This completes the proof. ∎

###### Proof of Theorem 1.22.

We use the same notations as in Theorem 1.21, and assume that
$|A|<q^{\frac{d-1}{2}}$, since the other case can be proved similarly. By
Theorem 1.15, one has a constant $C>0$ such that

$|P||E|=I(P,R)\leq\frac{|P||R|}{q^{d}}+Cq^{(d^{2}-d)/4}|P|^{1/2}|R|^{1/2}.$

Using the fact that $|R|\leq\lambda|E|$ with $\lambda<q^{d}/2$, we have

$\frac{\sqrt{|P||E|}}{2}\leq C\sqrt{\lambda}q^{(d^{2}-d)/4}.$

This implies

$|E|\ll\frac{\lambda q^{(d^{2}-d)/2}}{|A||B|},$

as desired. ∎

###### Proof of Theorem 1.23.

We use the same notations as in Theorem 1.21 for $d=2$. Applying Theorem 1.16,
there exists a constant $C>0$ such that

$|P||E|=I(P,R)\leq\frac{|P||R|}{q^{2}}+Cq^{1/2}|P|^{1/2}|R|^{1/2}|A|^{1/4}.$

Using the fact that $|R|\leq\lambda|E|$ with $\lambda<q^{d}/2$, we have

$\frac{\sqrt{|P||E|}}{2}\leq Cq^{1/2}\lambda^{1/2}|A|^{1/4}.$

This implies

$|E|\ll\frac{\lambda q}{|A|^{1/2}|B|},$

as desired. ∎

Theorem 1.24 (1) and (2), Theorem 1.25, and Theorem 1.26 are proved by the
same approach using Theorem 1.17, Theorem 1.18, and Theorem 1.19,
respectively.

For Theorem 1.24 (3), the same proof implies that if $|A|\leq p$ and $|B|\leq
p$, then $|E|\ll\frac{p|B|^{\epsilon}+|B|^{\epsilon}|P|^{2/3}}{|A|}$. However,
if we use Theorem 3.3, then we are able to get rid of the term
$p|B|^{\epsilon}$.

##  8\. Intersection pattern III: proofs

In this section, we prove Theorem 1.30. Let us start by introducing the
necessary theorem.

######  Theorem 8.1.

[25, Theorem 1.6] Let $\mathcal{K}$ be the set of $k$-planes and let
$\mathcal{H}$ be the set of $h$-planes in $\mathbb{F}_{q}^{d}$ with $h\geq
2k+1$. Then the number of incidences between $\mathcal{K}$ and $\mathcal{H}$
satisfies

$\left|I(\mathcal{K},\mathcal{H})-\frac{|\mathcal{K}||\mathcal{H}|}{q^{(d-h)(k+1)}}\right|\leq\sqrt{c_{k}(1+o(1))}q^{\frac{(d-h)h+k(2h-d-k+1)}{2}}\sqrt{|\mathcal{K}||\mathcal{H}}|,$

where $c_{k}=(2k+1)\binom{k}{\lfloor k/2\rfloor}$.

See 1.30

###### Proof of Theorem 1.30.

We proceed as follows.

  1. (1)

By applying Theorem 1.27(2), we have

$\\#\\{W\in G(d,m)\colon|\pi_{W}(E)|\leq\delta q^{m}\\}\leq
2\frac{\delta}{1-\delta}q^{m(d-m+1)-s},$

for any $E\subset\mathbb{F}_{q}^{d}$ with $|E|=q^{s}$ and $m<s<d$. Set
$\delta=\frac{3}{4}$. Then, the number of $m$-dimensional subspaces $W\in
G(d,m)$ such that $|\pi_{W}(A)|\leq\frac{3}{4}q^{m}$ is at most
$6q^{(d-m+1)m-s}$, where $|A|=q^{s}$ for some $s>m$. The same happens for the
set $B$. This implies that there are at most $12q^{(d-m+1)m-s}$
$m$-dimensional subspaces $W\in G(d,m)$ such that
$|\pi_{W}(A)|\leq\frac{3}{4}q^{m}$ or $|\pi_{W}(B)|\leq\frac{3}{4}q^{m}$,
where $q^{s}=\min\\{|A|,|B|\\}$. That is, there are at least
$(1+o(1))q^{m(d-m)}(1-12q^{m-s})$ $m$-dimensional subspaces $W\in G(d,m)$ such
that $|\pi_{W}(A)|>\frac{3}{4}q^{m}$ and $|\pi_{W}(B)|>\frac{3}{4}q^{m}$. We
note that

$\displaystyle|\pi_{W}(A)\cap\pi_{W}(B)|$
$\displaystyle=|\pi_{W}(A)|+|\pi_{W}(B)|-|\pi_{W}(A)\cup\pi_{W}(B)|$
$\displaystyle>\frac{3}{4}q^{m}+\frac{3}{4}q^{m}-|\pi_{W}(A)\cup\pi_{W}(B)|$
$\displaystyle\geq\frac{1}{2}q^{m}.$

The second inequality is from $|\pi_{W}(A)\cup\pi_{W}(B)|\leq q^{m}$ since the
dimension of $W$ is $m$. Therefore, there are at least
$(1+o(1))q^{m(d-m)}(1-12q^{m-s})$ $m$-dimensional subspaces $W\in G(d,m)$ such
that

$|\pi_{W}(A)\cap\pi_{W}(B)|\gg q^{m}.$

This completes the proof of Theorem 1.30(1).

  2. (2)

To prove the second part, we need to count the number of $W\in G(d,m)$ such
that

$|\pi_{W}(A)\cap\pi_{W}(B)|\neq q^{m},$

if $|A|,|B|>q^{2m}$. To do this, we first count the number of $W\in G(d,m)$
such that $|\pi_{W}(A)|\neq q^{m}$. Let $X:=\\{W\in
G(d,m)\colon|\pi_{W}(A)|\neq q^{m}\\}$ and $Y:=\\{W\in
G(d,m)\colon|\pi_{W}(B)|\neq q^{m}\\}$. By Corollary 1.28(3), we have that

$|X|=\\#\\{W\in G(d,m)\colon|\pi_{W}(A)|\neq q^{m}\\}\leq 4q^{m(d-m+2)-s},$

for $|A|=q^{s}$ with $s>2m$. Similarly, $|Y|\leq 4q^{(d-m)(m+2)-t}$ for
$|B|=q^{t}$ with $t>2m$. Thus, it suffices to show that $|X\cup Y|=\\#\\{W\in
G(d,m)\colon|\pi_{W}(A)\cap\pi_{W}(B)|\neq q^{m}\\}$ is smaller than the total
number of $m$-subspaces. Since $s,t>2m$, we have

$|X|\leq 4q^{(d-m)(m+2)-s}=o(q^{m(d-m)})\quad\text{and}\quad|Y|\leq
4q^{(d-m)(m+2)-t}=o(q^{m(d-m)}),$

which gives our desired result.

  3. (3)

Lastly, we prove the third part. By Corollary 1.28(1) and Corollary 1.28(2),
we have

$\\#\\{W\colon|\pi_{W}(A)|\leq
q^{m}/10\\}\leq\frac{1}{2|A|}q^{m(d-m+1)}\quad\text{and}\quad\\#\\{W\colon|\pi_{W}(B)|\leq|B|/10\\}\leq\frac{1}{2}|B|q^{m(d-m-1)}.$

Since $|A||B|>2q^{2m}$, we also have that

$\frac{1}{2|A|}q^{m(d-m+1)}\leq\frac{1}{4}|B|q^{m(d-m-1)}.$

Thus, this, together with $|B|<q^{m}/2$, implies that the number of
$m$-dimensional subspaces $W$ such that

$|\pi_{W}(A)|>q^{m}/10,\quad\text{and}\quad|\pi_{W}(B)|>|B|/10$

is at least
$(1+o(1))q^{m(d-m)}-|B|q^{m(d-m-1)}/4-|B|q^{m(d-m-1)}/2>(1+o(1))q^{m(d-m)}/2$.
From now on, we omit the term $1+o(1)$ and consider that $q$ is sufficiently
large. We denote the set of these $m$-dimensional subspaces $W$ by $D$. Then
we have $|D|>q^{m(d-m)}/2$.

Let $D^{\prime}\subset D$ be the set of $W\in D$ such that the number of
$(d-m)$-dimensional affine planes in $\pi_{W}(B)$ such that each contains at
least $|A|/(100q^{m})$ points from $A$ is at least $|B|/100$. If
$|D^{\prime}|\geq|D|/2$, then we are done.

Otherwise, by abuse of notation, we can assume that for any $W\in D$, there
are at least $|B|/10-|B|/100=9|B|/100>|B|/20$ $(d-m)$-dimensional affine
planes in $\pi_{W}(B)$ such that each contains at most $|A|/(100q^{m})$ points
from $A$. For each $W\in D$, let $V_{W}$ be the subset of $\pi_{W}(B)$ such
that each contains at most $|A|/(100q^{m})$ points from $A$, and $V=\cup_{W\in
D}V_{W}$. It is clear that $|V|\geq|D||V_{W}|>q^{m(d-m)}|B|/40$.

Using the incidence bound in Theorem 8.1, note that

$\left|I(V,A)-\frac{|V||A|}{q^{m}}\right|\leq
q^{\frac{m(d-m)}{2}}\sqrt{|V||A|}.$

Since $|V||A|\geq 4q^{(d-m)m+2m}$, then one has

$I(V,A)\geq\frac{|V||A|}{2q^{m}}=q^{m(d-m-1)}\frac{|A||B|}{80}.$

This means that there are at least $\gg q^{m(d-m)}$ subspaces $W\in D$ such
that

$I(V_{W},A)\geq\frac{|A||B|}{40q^{m}},$

since $|D|$ is at most $q^{m(d-m)}$ which is the total number of all
$m$-subspaces.

For each such $W$, let $M$ be the number of $m$-dimensional affine planes in
$V_{W}$ such that each contains at least one point from $A$. Note that

$\frac{M|A|}{100q^{m}}\geq I(V_{W},A).$

This implies that $M\geq\frac{5|B|}{2}$. Since $|\pi_{W}(A)\cap\pi_{W}(B)|\geq
M$, we have

$|\pi_{W}(A)\cap\pi_{W}(B)|\gg|B|.$

This completes the proof.

∎

As mentioned in the introduction, the following lemma is on the sharpness of
Theorem 1.30(3). This construction is similar to Example 4.1 in [21] in the
continuous.

######  Lemma 8.2.

Assume $q=p^{2}$. For any $0<c<1$, there exist sets
$A,B\subset\mathbb{F}_{q}^{2}$ with $|A||B|=cq^{2}$ and $L\subset G(2,1)$ with
$|L|\geq(1-c)q$ such that

$\pi_{W}(A)\cap\pi_{W}(B)=\emptyset\;\;\;\text{for any}~{}W\in L.$

###### Proof.

Let $A_{1}$ be the union of $cp$ disjoint cosets of $\mathbb{F}_{p}$. Then
$|A_{1}|=cq$. Let $B^{\prime}=A_{2}=\mathbb{F}_{p}$.

Let
$F\colon\mathbb{F}_{q}^{2}\setminus(\mathbb{F}_{q}\times\\{0\\})\to\mathbb{F}_{q}^{2}$
defined by

$F(x,y):=\left(\frac{x}{y},\frac{1}{y}\right).$

Set

$A=F^{-1}(A_{1}\times A_{2})~{}\mbox{and}~{}B=(-B^{\prime})\times\\{0\\}.$

It is clear that $|A||B|=cq^{2}$. We now construct $L\subset G(2,1)$ arbitrary
large such that

$\pi_{W}(A)\cap\pi_{W}(B)=\emptyset\;\;\;\text{for any}~{}W\in L.$

We denote the line of the form

$\mathbb{F}_{q}\cdot\begin{pmatrix}-b\\\ 1\end{pmatrix}+\begin{pmatrix}c\\\
0\end{pmatrix}$

by $\ell(-b,c)$.

Set $C=A_{1}+B^{\prime}A_{2}$. We first observe that if $(x,y)\in\ell(-b,c)$
with $b\in B^{\prime}$ and $c\in C$, then $x+yb=c$. This gives

$A_{1}\times A_{2}\subset\bigcap_{b\in B^{\prime}}\bigcup_{c\in C}\ell(-b,c).$

For any $(e_{1},e_{2})$ on the unit circle with $e_{2}\neq 0$, we have

$F\left(\mathbb{F}_{q}^{*}\cdot\begin{pmatrix}e_{1}\\\
e_{2}\end{pmatrix}+\begin{pmatrix}b\\\
0\end{pmatrix}\right)=\ell(b,e_{1}/e_{2}).$

Set $E=\\{(e_{1},e_{2})\colon e_{1}^{2}+e_{2}^{2}=1,~{}e_{1}/e_{2}\in C\\}.$
Then

$A=F^{-1}(A_{1}\times A_{2})\subset\bigcap_{b\in
B^{\prime}}\bigcup_{(e_{1},e_{2})\in
E}\left(\mathbb{F}_{q}^{*}\cdot\begin{pmatrix}e_{1}\\\
e_{2}\end{pmatrix}+\begin{pmatrix}b\\\ 0\end{pmatrix}\right).$

Since $|C|=cq$, we have $|E|\leq cq$. Define

$L:=G(2,1)\setminus\\{W^{\perp}\colon W\in E\\}.$

Here we identify each point $(e_{1},e_{2})$ on the unit circle with the line
containing it and the origin. So $|L|\geq q-|E|\geq(1-c)q$. By a direct
computation, one can check that

$\pi_{W}(A)\cap\pi_{W}(B)=\emptyset\;\;\;\text{for any}~{}W\in L.$

This completes the proof. ∎

##  9\. Acknowledgements

T. Pham would like to thank the Vietnam Institute for Advanced Study in
Mathematics (VIASM) for the hospitality and for the excellent working
condition. S. Yoo was supported by the KIAS Individual Grant (CG082701) at
Korea Institute for Advanced Study.

## References

  * [1] C. J. Bishop, and Y. Peres. Fractals in probability and analysis, Vol. 162. Cambridge University Press, 2017.
  * [2] J. Chapman, M. B. Erdoğan, D Hart, A. Iosevich, and D. Koh. Pinned distance sets, k-simplices, Wolff’s exponent in finite fields and sum-product estimates, Mathematische Zeitschrift, 271(1-2)(2012): 63–93.
  * [3] C. Chen, Projections in vector spaces over finite fields, Annales Academiæ Scientiarum Fennicæ Mathematica, 43(2018), 171–185.
  * [4] C. Donoven, and K. Falconer, Codimension formulae for the intersection of fractal subsets of Cantor spaces, Proceedings of the American Mathematical Society, 144(2)(2016), 651–663.
  * [5] M. Elekes, T. Keleti, and A. Máthé, Self-similar and self-affine sets: measure of the intersection of two copies, Ergodic Theory and Dynamical Systems, 30(2)(2010), 399–440.
  * [6] G. Elekes, and M. Sharir, Incidences in three dimensions and distinct distances in the plane, Combin. Probab. Comput., 20(4)(2011), 571–608.
  * [7] S. Eswarathasan, A. Iosevich, and K. Taylor, Intersections of sets and Fourier analysis, Journal d’Analyse Mathématique, 128(2016): 159–178.
  * [8] L. Guth, and N. H. Katz. On the Erdős distinct distances problem in the plane, Annals of mathematics (2015): 155–190.
  * [9] D. Hart, A. Iosevich, D. Koh, and M. Rudnev, Averages over hyperplanes, sum-product theory in vector spaces over finite fields and the Erdős-Falconer distance conjecture, Transactions of the American Mathematical Society, 363(6)(2011), 3255–3275.
  * [10] A. Iosevich, D. Koh, S. Lee, T. Pham, and C. Y. Shen, On restriction estimates for the zero radius sphere over finite fields, Canadian Journal of Mathematics, 73(3)(2021), 769–786.
  * [11] A. Iosevich, D. Koh, and F. Rakhmonov, The quotient set of the quadratic distance set over finite fields, arXiv:2301.12021 (2023).
  * [12] J.–P. Kahane, Sur la dimension des intersections [On the dimension of intersections] Aspects of Mathematics and its Applications, North-Holland Math. Library, 34(1986), 419–430.
  * [13] D. Koh, and H.S. Sun, Distance sets of two subsets of vector spaces over finite fields, Proceedings of the American Mathematical Society, 143(4)(2015): 1679–1692.
  * [14] D. Koh, S. Lee, and T. Pham, On the finite field cone restriction conjecture in four dimensions and applications in incidence geometry, International Mathematics Research Notices, 21(2022), 17079–17111.
  * [15] R. Lidl and H. Niederreiter, _Finite fields_ , Cambridge University Press, (1997).
  * [16] J. M. Marstrand, Some fundamental geometrical properties of plane sets of fractional dimensions, Proceeding of London Mathematical Society, 4(3)(1954), 257–302.
  * [17] P. Mattila, Hausdorff dimension and capacities of intersections of sets in n-space, Acta Math., 152(1984), 77–105.
  * [18] P. Mattila, Geometry of sets and measures in Euclidean spaces, Cambridge University Press, Volume 44, 1995.
  * [19] P. Mattila, Fourier analysis and Hausdorff dimension, Cambridge University Press, Volume 150, 2015.
  * [20] P. Mattila, Hausdorff dimension and projections related to intersections, Publicacions Matemàtiques, 66(1)(2022), 305–323.
  * [21] P. Mattila, and T. Orponen, Hausdorff dimension, intersections of projections and exceptional plane sections, Proceedings of the American Mathematical Society, 144(8)(2016), 3419–3430.
  * [22] C. G. T. de A. Moreira, and J-C. Yoccoz. Stable intersections of regular Cantor sets with large Hausdorff dimensions, Annals of Mathematics (2001): 45–96.
  * [23] A. Maschietti, Kakeya sets in finite affine spaces, Journal of Combinatorial Theory Series A, 118(1) (2011): 228–230.
  * [24] B. Murphy, G. Petridis, T. Pham, M. Rudnev, and S. Stevens, On the pinned distances problem over finite fields, Journal of London Mathematical Society, 105(1)(2022): 469–499.
  * [25] N. D. Phuong, T. Pham, and L. A. Vinh, Incidences between planes over finite fields, Proceedings of the American Mathematical Society, 147(5)(2019): 2185–2196.
  * [26] M. Rudnev, On the number of incidences between points and planes in three dimensions, Combinatorica, 38(2018): 219–254.