Intersection patterns and incidence theorems

Thang Pham and Semin Yoo University of Science, Vietnam National University, Hanoi, Vietnam [email protected] School of Computational Sciences, Korea Institute for Advanced Study, Seoul, Republic of Korea [email protected]

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

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)

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)

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)

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

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)

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}$ ).

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

In particular,

(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)

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|

|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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

If $|A|<q^{\frac{d-1}{2}}$ , then one has $|E|\ll\frac{q^{\frac{d^{2}-d}{2}}|B|^{\epsilon}}{|A|}$ .
(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)

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)

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)

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

Theorem 1.25 (Medium $A$ ).

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

In particular,

(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)

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)

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$ ).

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

In particular,

(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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

If $d=2$ , then $M^{*}(A)\ll q^{-3}|A|^{3/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)

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)

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)

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)

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

If $p\leq|A|\leq p^{5/4}$ , then $N(P)\leq p^{-1}|A|^{4}+Cp^{2/3}|A|^{8/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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

If $|A|\leq p$ , then Corollary 2.9 gives $I_{A,A}\ll p|A|^{2}+|A|^{10/3}.$
(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)

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)

If $|B|\leq p$ , then Corollary 2.9 gives $I_{B,B}\ll p|B|^{2}+|B|^{10/3}.$
(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)

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)

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

$\widehat{V}(m,m^{\prime})=\frac{1}{q}+\frac{q^{d}(q-1)}{q^{2d+1}}.$
(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)

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)

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)

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)

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.

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

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

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

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

Intersection patterns and incidence theorems

Abstract.

Key words and phrases:

2020 Mathematics Subject Classification:

1. Introduction

Question 1.1.

Question 1.2.

Question 1.3.

1.1. Intersection patterns I

Theorem 1.4.

Theorem 1.5.

Theorem 1.6.

Remark 1.7.

Theorem 1.8 (Medium​𝐀\mathbf{\mbox{\bf Medium}~{}A}).

Theorem 1.9 (Large​𝐁\mathbf{\mbox{\bf Large}~{}B}).

Remark 1.10.

Remark 1.11.

1.2. Intersection patterns II

Theorem 1.12.

Remark 1.13.

1.3. Incidences between points and rigid motions

Theorem 1.14.

Theorem 1.15.

Theorem 1.16.

Theorem 1.17 (|𝐀|≤𝐩​and​|𝐁|≤𝐩𝟒/𝟑\mathbf{|A|\leq p~{}\mbox{\bf and}~{}|B|\leq p^{4/3}}).

Theorem 1.18 (|𝐀|≥𝐩​and​|𝐁|≤𝐩𝟒/𝟑\mathbf{|A|\geq p~{}\mbox{\bf and}~{}|B|\leq p^{4/3}}).

Theorem 1.19 (|𝐁|>𝐩𝟒/𝟑\mathbf{|B|>p^{4/3}}).

Remark 1.20.

1.4. Growth estimates under orthogonal matrices

Theorem 1.21.

Theorem 1.22.

Theorem 1.23.

Theorem 1.24 (Small AA).

Theorem 1.25 (Medium AA).

Theorem 1.26 (Large BB).

1.5. Intersection pattern III

Theorem 1.27.

Corollary 1.28.

Question 1.29.

Theorem 1.30.

2. Preliminaries-key lemmas

2.1. Results over arbitrary finite fields

Theorem 2.1.

Lemma 2.2.

Theorem 2.3.

Theorem 2.4.

Theorem 2.5.

Proof.

Theorem 2.6.

Proof.

2.2. Results over prime fields

Theorem 2.7.

Proof.

Theorem 2.8.

Corollary 2.9.

Remark 2.10.

Theorem 2.11.

Proof.

2.3. An extension for general sets

Theorem 2.12.

Lemma 2.13.

Lemma 2.14.

Lemma 2.15.

Proof.

Lemma 2.16.

Proof.

Theorem 2.17.

Remark 2.18.

Proof.

Proof of Theorem 2.12.

3. Warm-up incidence theorems

Theorem 3.1.

Proof.

Theorem 3.2.

Theorem 3.3.

4. Incidence theorems: proofs

5. Intersection pattern I: proofs

Proof of Theorem 1.4.

Proof of Theorem 1.5.

Proof of Theorem 1.6.

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

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

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

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

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

Theorem 1.24 (Small $A$ ).

Theorem 1.25 (Medium $A$ ).

Theorem 1.26 (Large $B$ ).