ON THE TWO-PARAMETER ERDŐS–FALCONER DISTANCE PROBLEM IN FINITE FIELDS

Abstract

Given $E \subseteq \mathbb {F}_q^d \times \mathbb {F}_q^d$ , with the finite field $\mathbb {F}_q$ of order q and the integer $d\,\ge \, 2$ , we define the two-parameter distance set $\Delta _{d, d}(E)=\{(\|x-y\|, \|z-t\|) : (x, z), (y, t) \in E \}$ . Birklbauer and Iosevich [‘A two-parameter finite field Erdős–Falconer distance problem’, Bull. Hellenic Math. Soc. 61 (2017), 21–30] proved that if $|E| \gg q^{{(3d+1)}/{2}}$ , then $ |\Delta _{d, d}(E)| = q^2$ . For $d=2$ , they showed that if $|E| \gg q^{{10}/{3}}$ , then $ |\Delta _{2, 2}(E)| \gg q^2$ . In this paper, we give extensions and improvements of these results. Given the diagonal polynomial $P(x)=\sum _{i=1}^da_ix_i^s\in \mathbb F_q[x_1,\ldots , x_d]$ , the distance induced by P over $\mathbb {F}_q^d$ is $\|x-y\|_s:=P(x-y)$ , with the corresponding distance set $\Delta ^s_{d, d}(E)=\{(\|x-y\|_s, \|z-t\|_s) : (x, z), (y, t) \in E \}$ . We show that if $|E| \gg q^{{(3d+1)}/{2}}$ , then $ |\Delta _{d, d}^s(E)| \gg q^2$ . For $d=2$ and the Euclidean distance, we improve the former result over prime fields by showing that $ |\Delta _{2,2}(E)| \gg p^2$ for $|E| \gg p^{{13}/{4}}$ .

1 Introduction

The general Erdős distance problem is to determine the number of distinct distances spanned by a finite set of points. In the Euclidean space, it is conjectured that for any finite set $E \subset \mathbb {R}^d$ , $d\ge 2$ , we have $|\Delta (E)| \gtrapprox |E|^{{2}/{d}}$ , where $\Delta (E)=\{\|x-y\| : x,y \in E\}$ . Here and throughout, $X\ll Y$ means that there exists $C>0$ such that $X\le CY$ , and $X\lessapprox Y$ with the parameter N means that for any $\varepsilon>0$ , there exists $C_{\varepsilon }>0$ such that $X\,\le \,C_{\varepsilon }N^{\varepsilon }Y$ .

The finite field analogue of the distance problem was first studied by Bourgain et al. [2] over prime fields. In this setting, the Euclidean distance between any two points $x=(x_1,\ldots , x_d), y=(y_1,\ldots ,y_d) \in \mathbb {F}_q^d$ , the d-dimensional vector space over the finite field $\mathbb F_q$ of order q, is $\|x-y\|=\sum _{i=1}^d(x_i-y_i)^2\in \mathbb F_q$ . For prime fields $\mathbb {F}_p$ with $p\equiv 1 \pmod 4$ , they showed that if $E \subset \mathbb {F}_p^2$ with $|E|=p^{\delta }$ for some $0<\delta <2$ , then the distance set satisfies $|\Delta (E)| \gg |E|^{{1}/{2}+\varepsilon }$ for some $\varepsilon>0$ depending only on $\delta $ .

This bound does not hold in general for arbitrary finite fields $\mathbb {F}_q$ , as shown by Iosevich and Rudnev [9]. In this general setting, they considered the Erdős–Falconer distance problem to determine how large $E \subset \mathbb {F}_q^d$ needs to be so that $\Delta (E)$ spans all possible distances or at least a positive proportion of them. More precisely, they proved that $\Delta (E)=\mathbb {F}_q$ if $|E|> 2q^{{(d+1)}/{2}}$ in the all distances case, and also conjectured that $|\Delta (E)| \gg q$ if $|E| \gg _{\varepsilon } q^{{d}/{2}+\varepsilon }$ in the positive proportion case. In [6], it was shown that the exponent in the all distances case is sharp for odd d, and the conjecture for the positive proportion case holds for all $E \subset \{x\in \mathbb {F}_q^d : \|x\|=1\}$ . It is conjectured that in even dimensions, the optimal exponent is ${d}/{2}$ for the all distances case. In particular for $d=2$ , it was shown in [3] that if $E \subseteq \mathbb {F}_q^2$ satisfies $|E| \gg q^{{4}/{3}}$ , then $|\Delta (E)| \gg q$ , improving the positive proportion case. The proofs in [3] use extension estimates for circles. Therefore, one would expect to get improvements for distance problems if one can obtain improved estimates for extension problems.

There have been a recent series of other improvements and generalisations on the Erdős–Falconer distance problem. In [7], a generalisation for subsets of regular varieties was studied. Extension theorems and their connection to the Erdős–Falconer problem are the main focus of [10]. The exponents ${(d+1)}/{2}$ and ${d}/{2}$ were improved in [13, 14] for subsets E with Cartesian product structure in the all distances case for $|\Delta (E)|$ and in the positive proportion case for the quotient distance set $|{\Delta (E)}/{\Delta (E)}|$ .

A two-parameter variant of the Erdős–Falconer distance problem for the Euclidean distance was studied by Birklbauer and Iosevich in [1]. More precisely, given $E \subseteq \mathbb {F}_q^d \times \mathbb {F}_q^d$ , where $d\ge 2$ , define the two-parameter distance set as

$$ \begin{align*} \Delta_{d, d}(E)=\{(\|x-y\|, \|z-t\|) : (x,z), (y,t) \in E \} \subseteq \mathbb{F}_q \times \mathbb{F}_q. \end{align*} $$

They proved the following results.

Theorem 1.1 [1]

Let E be a subset in $\mathbb {F}_q^d \times \mathbb {F}_q^d$ . If $|E| \gg q^{{(3d+1)}/{2}}$ , then $ |\Delta _{d, d}(E)| = q^2$ .

Theorem 1.2 [1]

Let E be a subset in $\mathbb {F}_q^2 \times \mathbb {F}_q^2$ . If $|E| \gg q^{{10}/{3}}$ , then $ |\Delta _{2, 2}(E)| \gg q^2$ .

In this short note, we provide an extension and an improvement of these results. Unlike [1], which relies heavily on Fourier analytic techniques, we use an elementary counting approach.

Let $P(x)=\sum _{i=1}^da_ix_i^s\in \mathbb F_q[x_1,\ldots , x_d]$ be a fixed diagonal polynomial in d variables of degree $s\ge 2$ . For $x=(x_1,\ldots ,x_d), y=(y_1,\ldots ,y_d) \in \mathbb {F}_q^d$ , we introduce

$$ \begin{align*} \|x-y\|_s:=P(x-y)=\sum_{i=1}^d a_i(x_i-y_i)^s\in\mathbb F_q. \end{align*} $$

For any set $E\subset \mathbb {F}_q^d\times \mathbb {F}_q^d$ , define

$$ \begin{align*} \Delta_{d, d}^s(E)=\{(\|x-y\|_s, \|z-t\|_s) : (x, z), (y, t) \in E \}\in\mathbb F_q\times\mathbb F_q. \end{align*} $$

Our first result reads as follows.

Theorem 1.3. Let E be a subset in $\mathbb {F}_q^d \times \mathbb {F}_q^d$ . If $|E| \gg q^{{(3d+1)}/{2}}$ , then $ |\Delta _{d, d}^s(E)| \gg q^2$ .

Our method also works for the multi-parameter distance set for $E \subseteq \mathbb {F}_q^{d_1+\cdots +d_k}$ , but we do not discuss such extensions here. For $d=2$ , we get an improved version of Theorem 1.2 for the Euclidean distance function over prime fields.

Theorem 1.4. Let $E \subseteq \mathbb {F}_p^2 \times \mathbb {F}_p^2$ . If $|E| \gg p^{{13}{/4}}$ , then $ |\Delta _{2,2}(E)| \gg p^2$ .

The continuous versions of Theorems 1.3 and 1.4 have been studied in [4, 5, 8]. We do not know whether our method can be extended to that setting. It follows from our approach that the conjectured exponent ${d}/{2}$ of the (one-parameter) distance problem would imply the sharp exponent for the two-parameter analogue, namely ${3d}/{2}$ , for even dimensions. We refer to [1] for constructions and more discussions.

2 Proof of Theorem 1.3

By using the following auxiliary result whose proof relies on Fourier analytic methods (see [15, Theorem 2.3] and [11, Corollaries 3.1 and 3.4]), we are able to give an elegant proof for Theorem 1.3. Compared with the method in [1], ours is more elementary.

Lemma 2.1. Let $X, Y \subseteq \mathbb {F}_q^d$ . Define $\Delta ^s(X, Y)=\{\|x-y\|_s\colon x\in X, y\in Y\}$ . If $|X||Y|\gg q^{d+1}$ , then $|\Delta ^s(X, Y)|\gg q$ .

Proof of Theorem 1.3

By assumption, $|E|\ge Cq^{d+{(d+1)}/{2}}$ for some constant $C>0$ . For $y\in \mathbb {F}_q^d$ , let $E_y:=\{x\in \mathbb F_q^d : (x, y)\in E\}$ and define

$$ \begin{align*} Y:=\big\{ y\in \mathbb{F}_q^d : |E_y|> \tfrac{1}{2}C q^{{(d+1)}/{2}} \big\}. \end{align*} $$

We first show that $ |Y|\,\ge \, \tfrac 12C q^{{(d+1)}/{2}}$ . Note that

$$ \begin{align*}|E|=\sum_{y \in Y} |E_y| + \sum_{y \in \mathbb{F}^d_q\setminus Y} |E_y| \,\le\, q^d|Y| + \sum_{y \in \mathbb{F}^d_q\setminus Y} |E_y|, \end{align*} $$

where the last inequality holds since $|E_y|\,\le \,q^d$ for $y\in \mathbb {F}_q^d$ . Combining it with the assumption on $|E|$ gives the lower bound

$$ \begin{align*} \displaystyle\sum_{y \in \mathbb{F}^d_q\setminus Y} |E_y|\,\ge\, Cq^{d+{(d+1)}/{2}} - q^d|Y|. \end{align*} $$

However, by definition, $|E_y|\,\le \,\tfrac 12C q^{{(d+1)}/{2}}$ for $y \in \mathbb {F}^d_q\setminus Y$ , yielding the upper bound

$$ \begin{align*} \displaystyle\sum_{y \in \mathbb{F}^d_q\setminus Y} |E_y|\,\le\,\dfrac{1}{2}Cq^{d+{(d+1)}/{2}} .\end{align*} $$

These two bounds together give $Cq^{d+{(d+1)}/{2}} - q^d|Y|\,\le \,\tfrac 12C q^{d+{(d+1)}/{2}}$ , proving the claimed bound $|Y|\,\ge \, \tfrac 12C q^{{(d+1)}/{2}}$ .

In particular, Lemma 2.1 implies $|\Delta ^s(Y,Y)|\gg q$ , as $|Y||Y| \gg q^{d+1}$ . However, for each $u\in \Delta ^s(Y,Y)$ , there are $z, t\in Y$ such that $\|z-t\|_s=u$ . One has $|E_z|, |E_t|\gg q^{{(d+1)}/{2}}$ , therefore, again by Lemma 2.1, $|\Delta ^s(E_z, E_t)|\gg q$ . Furthermore, for $v\in \Delta ^s(E_z, E_t)$ , there are $x\in E_z$ and $y\in E_t$ satisfying $\|x-y\|_s=v$ . Note that $x\in E_z$ and $y\in E_t$ mean that $(x,z), (y,t)\in E$ . Thus, $(v,u)=(\|x-y\|_s, \|z-t\|_s)\in \Delta _{d, d}^s(E)$ . From this, we conclude that $|\Delta _{d, d}^s(E)|\gg q|\Delta ^s(Y,Y)|\gg q^2$ , which completes the proof.

3 Proof of Theorem 1.4

To improve the exponent over prime fields $\mathbb {F}_p$ , we strengthen Lemma 2.1 as shown in Lemma 3.1 below. Following the proof of Theorem 1.3 and using Lemma 3.1 proves Theorem 1.4.

Lemma 3.1. Let $X, Y \subseteq \mathbb {F}_p^2$ . If $|X|, |Y|\gg p^{5/4}$ , then $|\Delta (X, Y)|\gg p$ .

Proof. It is clear that if $X' \subseteq X$ and $Y' \subseteq Y$ , then $\Delta (X',Y')\subseteq \Delta (X,Y)$ . Thus, without loss of generality, we may assume that $|X|=|Y|=N$ with $N\gg p^{5/ 4}$ . Let Q be the number of quadruples $(x, y, x', y')\in X\times Y\times X\times Y$ such that $\|x-y\|=\|x'-y'\|$ . It follows easily from the Cauchy–Schwarz inequality that

$$ \begin{align*}|\Delta(X, Y)|\gg \frac{|X|^2|Y|^2}{Q}.\end{align*} $$

Let T be the number of triples $(x, y, y')\in X\times Y\times Y $ such that $\|x-y\|=\|x-y'\|$ . By the Cauchy–Schwarz inequality again, one gets $Q\ll |X|\cdot T$ . Next, we need to bound T. For this, denote $Z=X\cup Y$ , so that $N\le |Z|\le 2N$ . Let $T'$ be the number of triples $(a, b, c)\in Z\times Z\times Z$ such that $\|a-b\|=\|a-c\|$ . Obviously, $T\le T'$ . However, it was recently proved (see [12, Theorem 4]) that

$$ \begin{align*}T'\ll \frac{|Z|^3}{p}+p^{2 /3}|Z|^{ 5 /3}+p^{1 /4}|Z|^2,\end{align*} $$

which gives

$$ \begin{align*}T\ll \frac{N^3}{p}+p^{2 /3}N^{5 /3}+p^{1 /4}N^2,\end{align*} $$

and then $T\ll {N^3}/p$ (since $N\gg p^{5 /4}$ ). Putting all the bounds together, we obtain

$$ \begin{align*}\dfrac{N^3}{|\Delta(X,Y)|}=\dfrac{|X||Y|^2}{|\Delta(X,Y)|}\ll \dfrac Q{|X|}\ll T\ll \dfrac {N^3}p,\end{align*} $$

or equivalently, $|\Delta (X,Y)|\gg p$ , as required.