Erdös-Falconer distance problem, exponential sums, and Fourier analytic approach to incidence theorems in vector

spaces over finite fields

Alex Iosevich and Doowon Koh September 5, 2006

Abstract

We study the Erdos/Falconer distance problem in vector spaces over finite fields with respect to the cubic metric. Estimates for discrete Airy sums and Adolphson/Sperber estimates for exponential sums in terms of Newton polyhedra play a crucial role. Similar techniques are used to study the incidence problem between points and cubic and quadratic curves. As a result we obtain a non-trivial range of exponents that appear to be difficult to attain using combinatorial methods.

Contents

1 Introduction 2

1.1 The Erdös distance problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Previous results 3 3 Main results of this paper 4

3.1 Distances determined by a single set . . . . . . . . . . . . . . . . . . . . . . 4 3.2 Szemeredi-Trotter type Incidence theorems and distances between pairs of

8 Proof of Theorem 3.4 and Corollary 3.6 15

sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 4 Fourier analytic preliminaries and notation 6 5 Proof of the first part of Theorem 3.1 6 6 Proof of Theorem 5.1 8 7 Proof of the second part of Theorem 3.1 12 9 Application to sum/product formulas 15

1 Introduction

1.1 The Erdös distance problem

The Erdos distance conjecture in the Euclidean space says that if E is a finite subset of ℝ^{d}, d ≥ 2, then

#Δ(E) ⪆ (#E)^{\frac{2}{d}} ,  (1.1)

where

Δ(E) = {|x − y| : x, y ∈ E},

with |x − y|^{2} = (x_{1} − y_{1})^{2} + ⋯ + (x_{d} − y_{d})^{2} and here, and throughout the paper, X ≲ Y means that there exists C > 0 such that X ≤ CY, and X ⪅ Y, with the controlling parameter N, means that for every ϵ > 0 there exists C_{ϵ} > 0 such that X ≤ C_{ϵ}N^{ϵ}Y.

Taking E = ℤ^{d} ∩ [0, N^{\frac{1}{d}}]^{d} shows that (1.1) cannot in general be improved. The conjecture has not been solved in any dimension. See, for example, ([12]), ([1]), and the references contained therein for the description of the conjecture, background material, and a survey of recent results.

In this paper we study the Erdös distance problem in vector spaces over finite fields. This problem was recently addressed by Tao ([17]) who relates it to some interesting questions in combinatorics, and, more recently, by Iosevich and Rudnev. We shall describe these results later in the introduction.

Let 𝔽_{q} denote the finite field with q elements, q prime, and let 𝔽_{q}^{d} denote the d-dimensional vector space over this field. While our methods work in more general settings we shall operate in this format for the moment for the sake of clarity. Let E ⊂ 𝔽_{q}^{d}, d ≥ 2. Then the analog of the classical Erdös distance problem is to determine the smallest possible cardinality of the set

Δ_{n}(E) = {||x − y||_{n} = (x_{1} − y_{1})^{n} + ⋯ + (x_{d} − y_{d})^{n} : x, y ∈ E},

with n a positive integer ≥ 2, viewed as a subset of 𝔽_{q}.

In the finite field setting, the estimate (1.1) cannot hold without further restrictions. To see this, let E = 𝔽_{q}^{d}. Then #E = q^{d} and #Δ(E) = q. Furthermore, an interesting feature of the Erdös distance problem in the finite field setting with n = 2 is the existence of non-trivial spheres of 0 radius. These are sets of the form {x ∈ 𝔽_{q}^{d} : x_{1}^{2} + x_{2}^{2} + ⋯ + x_{d}^{2} = 0} and several assumptions in the statements of results below are there precisely to deal with issues created by the presence of this object. For example, suppose −1 is a square in 𝔽_{q}. Using spheres of radius 0 one can show, in even dimensions, that there exists a set of cardinality precisely q^{\frac{d}{2}} such that all the distances, (x_{1} − y_{1})^{2} + ⋯ + (x_{d} − y_{d})^{2} are 0. What’s more, suppose 𝔽_{q} is a finite field, such that q = p^{2}, where p is a prime. Then E = 𝔽_{p}^{d} is naturally embedded in 𝔽_{q}^{d}, has cardinality q^{\frac{d}{2}} , and determines only \sqrt{q} distances. If n > 2, the situation is equally fascinating. For example, if n = 3 and d = 2, the equation x_{1}^{3} + x_{2}^{3} = 0 always has at least q solutions, since cube root of −1 is −1. This equation may have as many as 3q solutions if the primitive cube root of −1 is in the field.

With these examples as guide, we generalize the conjecture originally stated in ([9]) in the case n = 2 as follows. Conjecture 1.1. Let E ⊂ 𝔽_{q}^{d} of cardinality ≥ Cq^{\frac{d}{2}} , with C sufficiently large. Then

#Δ_{n}(E) ⪆ q.

The authors conjecture in ([9]) that the constant C that appears above may be taken to be one in the case n = 2. It is interesting to note that if n > 2, the situation becomes more complicated. For example, as we pointed out above, if n = 3 and d = 2, the number of points on the curve x_{1}^{3} + x_{2}^{3} = 0 may be as high as 3q, depending on whether or not the primitive cube root of −1 is in the field. Thus a corresponding conjecture in the case n > 2 must be designed with these issues in mind.

2 Previous results

A Euclidean plane argument due to Erdös ([5]) can be applied to the finite field set-up under the assumption of Conjecture 1.1 to show that if d = 2 and #E ≥ Cq, with C sufficiently large, then

#Δ_{n}(E) ≳ (#E)^{\frac{1}{2}} .  (2.1)

This result was improved by Bourgain, Katz and Tao ([3]) who showed using intricate incidence geometry that for every ϵ > 0, there exists δ > 0, such that if #E ≲ q^{2−ϵ}, then

#Δ_{2}(E) ≳ q^{\frac{1}{2} +δ}.

The relationship between ϵ and δ in the above argument is difficult to determine. Moreover, matters are even more subtle in higher dimensions the context of vector spaces over finite fields because intersection of analogs of spheres, both quadratic and cubic, in 𝔽_{q}^{d} may be quite complicated, and the standard induction on the dimension argument in ℝ^{d} (see e.g. [1]) that allows one to bootstrap the estimate (2.1) into the estimate

#Δ_{ℝ^{d}}(E) ≳ (#E)^{\frac{1}{d}}  (2.2)

does not immediately go through. We establish the finite field analog of the estimate (2.2) below using Fourier analytic methods and number theoretic properties of Kloosterman sums and its more general analogs.

Another way of thinking of Conjecture 1.1 is in terms of the Falconer distance conjecture ([6]) in the Euclidean setting which says that if the Hausdorff dimension of a set in ℝ^{d} exceeds \frac{d}{2}, then the Lebesgue measure of the distance set is positive. Conjecture 1.1 implies that if the size of the set is greater than q^{\frac{d}{2}} , then the distance set contains a positive proportion of all the possible distances, an analogous statement.

In ([9]) the authors proved the following result.

Theorem 2.1. Let E ⊂ 𝔽_{q}^{d}, d ≥ 2, such that #E ≥ Cq^{\frac{d+1}{2}} . Then if C is sufficiently large, Δ_{2}(E) contains every element of 𝔽_{q}.

3 Main results of this paper

3.1 Distances determined by a single set

Our first result is the version of Theorem 2.1 for cubic metrics.

Theorem 3.1. Suppose that q is a prime number congruent to 1 modulo 3. Let E ⊂ 𝔽_{q}^{d}, such that #E ≥ Cq^{\frac{d+1}{2}} . Then if C is sufficiently large, Δ_{3}(E) contains every element of 𝔽_{q}.

Suppose that d = 2, and n ≥ 2. Then if #E ≥ Cq^{\frac{3}{2}} for C sufficiently large, then Δ_{n}(E) contains every elements of 𝔽_{q}.

Corollary 3.2. Suppose that q is a prime number congruent to 1 modulo 3. Let E ⊂ 𝔽_{q}^{d}, d ≥ 2, such that #E = Cq^{\frac{d+1}{2}} . Then if C is sufficiently large,

#Δ_{3}(E) ≈ (#E)^{\frac{2}{d+1}} .

In two dimensions, the same conclusions, with d = 2, holds for any n ≥ 2.

Note that in the case d = 2, the exponent \frac{2}{3} obtained via the corollary, for the given range of parameters, is a much better exponent than the one obtained by the incidence argument due to Erdos described in (2.1) above. Also, we point out once more that Erdos’ argument does not generalize to higher dimensions, at least not very easily, due to the possibly complicated intersection properties of cubic varieties.

3.2 Szemeredi-Trotter type Incidence theorems and distances between pairs of sets

As in the case n = 2, the proof of Theorem 3.1 can be modified to yield a good upper bound on the number of incidences between points and cubic surfaces in vector spaces over finite fields. It is an analog, and a higher dimensional generalization, of the following classical result due to Szemeredi and Trotter.

Theorem 3.3. The number of incidences between N points and M lines (or circles of the same radius) in the plane is

≲ N + M + (NM)^{\frac{2}{3}} .

Our incident estimate is the following.

Theorem 3.4. Suppose that q is a prime number congruent to 1 modulo 3. Let E, F ⊂ 𝔽_{q}^{d}, d ≥ 2. Then if j ≠ 0,

#{(x, y) ∈ E × F : (x_{1} − y_{1})^{3} + ⋯ + (x_{d} − y_{d})^{3} = j}
≲ #E · #F · q^{−1} + q^{\frac{d−1}{2}} · (#E)^{\frac{1}{2}} · (#F)^{\frac{1}{2}} .

Similarly, if q is a prime number and j ≠ 0, then

#{(x, y) ∈ E × F : (x_{1} − y_{1})^{2} + ⋯ + (x_{d} − y_{d})^{2} = j}
≲ #E · #F · q^{−1} + q^{\frac{d−1}{2}} · (#E)^{\frac{1}{2}} · (#F)^{\frac{1}{2}} .

In two dimensions, the same result holds, with d = 2, with Δ_{3} replaced by Δ_{n} for any n ≥ 2. Remark 3.5. In particular, that if #E ≈ #F ≈ q^{\frac{d+1}{2}} , then the number of incidences between points in E and ”spheres”, quadratic or cubic, centered at elements of F is ≲ q^{d}.

To make the numerology more transparent, Theorem 3.4 says that if N ≈ q^{\frac{d+1}{2}} , the number of incidences between ≈ N points and ≈ N spheres, cubic or quadratic, in 𝔽_{q}^{d} is ≲ q^{d} =

N^{\frac{2d}{d+1}} . In two dimensions this says that the number of incidences between N points and N circles is ≲ N^{\frac{4}{3}} , provided that N ≈ q^{\frac{d+1}{2}} , matching in this setting the exponent in the following celebrated result due to Szemeredi and Trotter in the Euclidean plane.

An easy modification of the method used to prove Theorem 3.4 above yields the following distance set result.

Corollary 3.6. Let E, F ⊂ 𝔽_{q}^{d}, d ≥ 2. Suppose that q is a prime number congruent to 1 modulo 3 and #E · #F ≥ Cq^{d+1}. Let Δ_{3}(E, F) = {||x − y||_{3} : x ∈ E, y ∈ F }. Then if C is sufficiently large, then Δ_{3}(E, F) contains every element of 𝔽_{q}.

As before, in two dimensions the same conclusion holds, with d = 2, with Δ_{3} replaced by Δ_{n}(E).

An analogous version of this result was independently obtained by Shparlinski in [15].

4 Fourier analytic preliminaries and notation

Let 𝔽_{q} be a finite field with q elements, where q is a prime number. Let

χ(t) = e^{\frac{2πi}{q} t}.

Given a complex valued function f on 𝔽_{q}^{d}, define the Fourier transform of f by the equation

f̂(m) = q^{−d} ∑_{x∈𝔽_{q}^{d}} χ(−x · m)f(x).

And, perhaps the most important identity in mathematics :) is the following. Let f be as above. Then

∑_{m∈𝔽_{q}^{d}} |f̂(m)|^{2} = q^{−d} ∑_{x∈𝔽_{q}^{d}} |f(x)|^{2}.

5 Proof of the first part of Theorem 3.1

Let χ(s) = e^{\frac{2πi}{q} s}. Let S_{j} denote the characteristic function of the cubic ”sphere”

{x ∈ 𝔽_{q}^{d} : ||x||_{3} = j},

where, as above,

||x||_{3} = x_{1}^{3} + ⋯ + x_{d}^{3}.

The key estimate of the paper is the following.

Theorem 5.1. Let ||x||_{3} = x_{1}^{3} + ⋯ + x_{d}^{3}. Suppose that q is a prime number congruent to 1 modulo 3 and j ≠ 0. Then if m ≠ (0, …, 0), then

|Ŝ_{j}(m)| = |q^{−d} ∑_{\{x∈𝔽_{q}^{d}:||x||_{3}=j\}}χ(x · m)| ≲ q^{− \frac{d+1}{2}} ,

and if m = (0, …, 0), then

Ŝ_{j}(m) = q^{−1} + O(q^{− \frac{d+1}{2}} )
≈ q^{−1}.

For j ≠ 0, consider #{(x, y) ∈ E × E : ||x − y||_{3} = j}

= ∑_{x,y∈𝔽_{q}^{d}} E(x)E(y)S_{j}(x − y)

= q^{2d} ∑_{m} |Ê(m)|^{2}Ŝ_{j}(m) = I + II,

where

I = q^{2d}|Ê(0, …, 0)|^{2}Ŝ_{j}(0, …, 0),

and

II = q^{2d} ∑_{m≠(0,...,0)} |Ê(m)|^{2}Ŝ_{j}(m).

Using the second part of Theorem 5.1,

I ≈ q^{2d}q^{−2d}(#E)^{2} · q^{−1}.

Whereas using the first part of Theorem 5.1,

|II| ≲ q^{2d}q^{− \frac{d+1}{2}} ∑_{m≠(0,··· ,0)} |Ê(m)|^{2}

≲ q^{2d}q^{− \frac{d+1}{2}} q^{−2} ∑_{x∈𝔽_{q}^{d}} E^{2}(x)

= q^{\frac{d−1}{2}} · #E.

We therefore obtain that

#{(x, y) ∈ E × E : ||x − y||_{3} = j} = I + II, where

I ≳ (#E)^{2}q^{−1},

and

|II| ≲ #E · q^{\frac{d−1}{2}} .

We conclude that if #E ≥ Cq^{\frac{d+1}{2}} , with C sufficiently large, then

#{(x, y) ∈ E × E : ||x − y||_{3} = j} > 0

for each j ≠ 0. This completes the proof of Theorem 3.1.

6 Proof of Theorem 5.1

We have

Ŝ_{j}(m) = q^{−d} ∑_{{x∈𝔽_{q}^{d}:||x||_{3}=j}}χ(−x · m)

= q^{−1}δ(m) + q^{−d−1} ∑_{x} ∑_{t∈𝔽_{q}^{∗}} χ(t(||x||_{3} − j))χ(−x · m),

where δ(m) = 1 if m = (0, …, 0) and 0 otherwise. Lemma 6.1. Let χ be a nontrivial additive character of F_{q} with q ≡ 1 mod (3). Suppose that m = (m_{1}, ⋯, m_{l}) ∈ (𝔽_{q}^{∗})^{l}. Then for any multiplicative character ψ of F_{q} of order 3 and t ≠ 0, we have

∏_{j=1}^{l} ∑_{s_{j}∈F_{q}} χ(−s_{j}m_{j} + s_{j}^{3}t)

= ψ^{−l}(t) ∑_{s_{1},··· ,s_{l}∈F_{q}^{∗}} χ(s_{1} + ⋯ + s_{l} + m_{1}^{3}t^{−1}s_{1}^{−1} + ⋯ + m_{l}^{3}t^{−1}s_{l}^{−1})ψ(s_{1}) ⋯ ψ(s_{l}),

where 3^{−3}m_{j}^{3} is denoted by m_{j}^{3} in the right-hand side of the equation. We shall also need the following result due to Duke and Iwaniec ([4]). Theorem 6.2. Suppose that q ≡ 1 mod (3) and let ψ be a multiplicative character of order three. Then

∑_{s∈𝔽_{q}} χ(as^{3} + s) = ∑_{s∈𝔽_{q}^{∗}} ψ(sa^{−1})χ(s − (3^{3}as)^{−1}),

for any a ∈ 𝔽_{q}^{∗}.

It follows that

∑_{s∈𝔽_{q}} χ(−sm_{j} + s^{3}t) = ∑_{s∈𝔽_{q}} χ(s − s^{3}tm_{j}^{−3})

= ∑_{s∈𝔽_{q}^{∗}} ψ(st^{−1})χ(s + m_{j}^{3}t^{−1}3^{−3}s^{−1}).

since ψ is a multiplicative character of F_{q} of order three and m_{j} ≠ 0. Absorbing 3^{−3} into m_{j} to make the notations simple, we complete the proof of Lemma 6.1.

Lemma 6.3. Let χ be a nontrivial additive character of F_{q} with q ≡ 1 mod (3). Then for any multiplicative character ψ of F_{q} of order 3 and t ≠ 0, we have

( ∑_{s∈F_{q}} χ(ts^{3}))^{l} = ∑_{r=0}^{l} ( \begin{matrix}l \\ r \end{matrix} ) q^{l} ψ^{−(l+r)}(t)(ψ̂(−1))^{l−r} (ψ̂^{2}(−1))^{r},

where ( \begin{matrix}. \\ . \end{matrix} ) is a binomial coefficient , l is a positive integer, and the Fourier transform of

a multiplicative characer ψ of 𝔽_{q} is given by

ψ̂(v) = q^{−1} ∑_{s∈𝔽_{q}^{∗}} χ(−vs)ψ(s).

Remark 6.4. ψ̂(v) = O(q^{− \frac{1}{2}} ) for v ≠ 0.

To prove Lemma 6.3 , we need the following theorem. For the proof, see the ([19], page 217, Theorem 5.30).

Theorem 6.5. Let χ be a nontrivial additive character of F_{q}, n ∈ ℕ, and ψ a multiplicative character of F_{q} of order h =gcd(n, q − 1). Then

∑_{s∈F_{q}} χ(ts^{n} + b) = χ(b) ∑_{k=1}^{h−1} ψ^{−k}(t) G(ψ^{k}, χ)

for any t, b ∈ F_{q} with t ≠ 0, where G(ψ^{k}, χ) = ∑_{s∈F_{q}^{∗}} ψ^{k}(s)χ(s).

By using Theorem 6.5, we see that for any multiplicative character ψ of order three,

( ∑_{s∈F_{q}} χ(ts^{3}))^{l}

= ( ∑_{k=1}^{2} ψ^{−k}(t) ∑_{s∈F_{q}^{∗}} ψ^{k}(s) χ(s))^{l}

= (ψ^{−1}(t) ∑_{s∈F_{q}^{∗}} ψ(s) χ(s) + ψ^{−2}(t) ∑_{s∈F_{q}^{∗}} ψ^{2}(s)χ(s))^{l}

= (G_{1}(t) + G_{2}(t))^{l}

= ∑_{r=0}^{l} ( \begin{matrix}l \\ r \end{matrix} ) G_{1}(t)^{l−r}G_{2}(t)^{r},

where

G_{1}(t) = ψ^{−1}(t) ∑_{s∈F_{q}^{∗}} ψ(s)χ(s)

and

G_{2}(t) = ψ^{−2}(t) ∑_{s∈F_{q}^{∗}} ψ^{2}(s)χ(s).

Note that G_{1}(t) = qψ^{−1}(t) ψ̂(−1) and G_{2}(t) = qψ^{−2}(t) ψ̂^{2}(−1). Thus we conclude that

( ∑_{s∈F_{q}} χ(ts^{3}))^{l} = ∑_{r=0}^{l} ( \begin{matrix}l \\ r \end{matrix} ) q^{l}ψ^{−(l+r)}(t)(ψ̂(−1))^{l−r}(ψ̂^{2}(−1))^{r}.

We are now ready to prove Theorem 5.1. First, we assume that m = (0, ⋯, 0) ∈ F_{q}^{d}. Then, using Lemma 6.3, we see that

Ŝ_{j}(0, ⋯, 0) = q^{−d} ∑_{{x∈𝔽_{q}^{d}:||x||_{3}=j}}1

= q^{−1} + q^{−d−1} ∑_{t∈𝔽_{q}^{∗}} χ(−tj) ∑_{x} χ(t(||x||_{3}))

= q^{−1} + q^{−d−1} ∑_{t∈𝔽_{q}^{∗}} χ(−tj) ∑_{r=0}^{d} ( \begin{matrix}d \\ r \end{matrix} ) q^{d}ψ^{−(d+r)}(t)(ψ̂(−1))^{d−r}(ψ̂^{2}(−1))^{r}

= q^{−1} + q^{−1} ∑_{r=0}^{d} ( \begin{matrix}d \\ r \end{matrix} ) (ψ̂(−1))^{d−r} (ψ̂^{2}(−1))^{r} ∑_{t∈𝔽_{q}^{∗}} χ(−tj)ψ^{−(d+r)}(t)

= q^{−1} + q^{−1} ∑_{r=0}^{d} ( \begin{matrix}d \\ r \end{matrix} ) (ψ̂(−1))^{d−r} (ψ̂^{2}(−1))^{r}q{ \atop ψ^{−(d+r)}}(j)

= q^{−1} + O(q^{− \frac{d+1}{2}} ) ≈ q^{−1}.

In the last equality, we used the fact that ψ̂(v) = O(q^{− \frac{1}{2}} ) for any multiplicative character of F_{q} with v ≠ 0. Thus the second part of Theorem 5.1 is proved.

In order to prove the first part of Theorem 5.1, we shall deal with the problem in case m = (m_{1}, ⋯, m_{d}) ≠ (0, ⋯, 0). Suppose that m_{j} ≠ 0 for j ∈ J ⊂ {1, 2, ⋯, d} and m_{j} = 0 for j ∈ {1, 2, ⋯, d} \ J = J′. Without loss of generality, we may assume that J = {1, 2, ⋯, l} and J′ = {l + 1, ⋯, d} for some l = 1, 2, ⋯, d. Using Lemma 6.1 and Lemma 6.3, we see that

Ŝ_{j}(m) = q^{−d−1} ∑_{t∈F_{q}^{∗}} χ(−tj) ∑_{x∈F_{q}^{d}} χ(t||x||_{3} − m · x)

= q^{−d−1} ∑_{t∈F_{q}^{∗}} χ(−tj)( ∏_{k=1}^{l} ∑_{s_{k}∈F_{q}} χ(ts_{k}^{3} − m_{k}s_{k}))( ∏_{k=l+1}^{d} ∑_{s_{k}∈F_{q}} χ(ts_{k}^{3}))

= q^{−d−1} ∑_{t∈F_{q}^{∗}} χ(−tj)ψ^{−l}(t) ∑_{s_{1},··· ,s_{l}∈F_{q}^{∗}} χ(s_{1}+⋯+s_{l}+m_{1}^{3}t^{−1}s_{1}^{−1}+⋯+m_{l}^{3}t^{−1}s_{l}^{−1})ψ(s_{1}) ⋯ ψ(s_{l})

× ∑_{r=0}^{d−l} ( \begin{matrix}d − l \\ r \end{matrix} ) q^{d−l}ψ^{−(d−l+r)}(t)(ψ̂(−1))^{d−l−r}(ψ̂^{2}(−1))^{r}

= q^{−1−l} ∑_{r=0}^{d−l} ( \begin{matrix}d − l \\ r \end{matrix} ) (ψ̂(−1))^{d−l−r}(ψ̂^{2}(−1))^{r} ∑_{t∈F_{q}^{∗}} χ(−tj)ψ^{−(d+r)}(t)

× ∑_{s_{1},··· ,s_{l}∈F_{q}^{∗}} χ(s_{1} + ⋯ + s_{l} + m_{1}^{3}t^{−1}s_{1}^{−1} + ⋯ + m_{l}^{3}t^{−1}s_{l}^{−1})ψ(s_{1}) ⋯ ψ(s_{l}).

Since ( \begin{matrix}d − l \\ r \end{matrix} ) (ψ̂(−1))^{d−l−r}(ψ̂^{2}(−1))^{r} = O(q^{− \frac{1}{2} (d−l)}), we obtain that

|Ŝ_{j}(m)| ≲ q^{−1− \frac{d+l}{2}} ∑_{r=0}^{d−l} |A_{r}(χ, ψ)|,

where A_{r}(χ, ψ) is given by

∑_{t∈F_{q}^{∗}} χ(−tj)ψ^{−(d+r)}(t) ∑_{s_{1},··· ,s_{l}∈F_{q}^{∗}} χ(s_{1} + ⋯ + s_{l} + m_{1}^{3}t^{−1}s_{1}^{−1} + ⋯ + m_{l}^{3}t^{−1}s_{l}^{−1})ψ(s_{1}) ⋯ ψ(s_{l}).

We now apply the result of Adolphson and Sperber ([2], Theorem 4.2, Corollary 4.3) to see that for all r = 0, 1, ⋯, d − l,

|A_{r}(χ, ψ)| ≲ q^{\frac{l+1}{2}} .

This completes the proof.

7 Proof of the second part of Theorem 3.1

Similarly to the proof of the first part of Theorm 3.1, it suffices to prove the follwoing estimation. Theorem 7.1. Let ||x||_{n} = x_{1}^{n} + x_{2}^{n} for x ∈ 𝔽_{q}^{2} and n ≥ 2. Suppose that q is a prime number and j ≠ 0. Then if m ≠ (0, 0), then

|Ŝ_{j}(m)| = |q^{−2} ∑_{\{x∈𝔽_{q}^{2}:||x||_{n}=j\}}χ(−x · m)| ≲ q^{− \frac{3}{2}} ,

and if m = (0, 0),then

Ŝ_{j}(m) = q^{−1} + O(q^{− \frac{3}{2}} ) ≈ q^{−1}.

To prove Theorem 7.1, we observe that for j ≠ 0 and m ∈ 𝔽_{q}^{2},

Ŝ_{j}(m) = q^{−2} ∑_{{x∈𝔽_{q}^{2}:||x||_{n}=j}}χ(−x · m)

= q^{−1}δ(m) + q^{−3} ∑_{x} ∑_{t∈𝔽_{q}^{∗}} χ(t(||x||_{n} − j))χ(−x · m),

where δ(m) = 1 if m = (0, 0) and 0 otherwise.

First we shall prove the second part of Theorem 7.1. Using Theorem 6.5, we see that for a multi-index β = (β_{1}, ⋯, β_{h−1}),

( ∑_{s∈𝔽_{q}} χ(ts^{n}))^{2}

= ∑_{β_{1}+···+β_{h−1}=2} \frac{2!}{β_{1}! ⋯ β_{h−1}!}ψ^{−(β_{1}+···+(h−1)β_{h−1})}(t)q^{2}(ψ̂(−1))^{β_{1}} ⋯ ({ \atop ψ^{h−1}}(−1))^{β_{h−1}}

where ψ is a multiplicative character of 𝔽_{q} of order h = gcd(n, q − 1). It therefore follows that

Ŝ_{j}(0, 0) = q^{−1} + ∑_{β_{1}+···+β_{h−1}=2} \frac{2!}{β_{1}! ⋯ β_{h−1}!}{ \atop ψ^{−γ(h,β)}}(j)(ψ̂(−1))^{β_{1}} ⋯ ({ \atop ψ^{h−1}}(−1))^{β_{h−1}}

where γ(h, β) is given by β_{1} + 2β_{2} + ⋯ + (h − 1)β_{h−1}.

Since ψ̂(v) = O(q^{− \frac{1}{2}} ) for each multiplicative character ψ and v ∈ 𝔽_{q}^{∗}, we conclude

Ŝ(0, 0) = q^{−1} + O(q^{− \frac{3}{2}} ) ≈ q^{−1}.

This completes the proof of the second part of Theorem 7.1.

It remains to prove the first part of Theorem 7.1. The cohomological interpretation can be used to estimate the exponential sums. We now introduce the cohomology theory based on work of authors in [20] and [2]. Let g be a polynomial given by

g = ∑_{α∈J} A_{α}x^{α} ∈ 𝔽_{q}[x_{1}, ⋯, x_{d}],  (7.1)

where J is a finite subset of (ℕ ∪ {0})^{d}, and A_{α} ≠ 0 if α ∈ J. We denote by ∑(g) the Newton polyhedron of g which is the convex hull in ℝ^{d} of the set J ∪ (0, ⋯, 0). For any face σ (of any dimension) of ∑(g), we put

g_{σ} = ∑_{α∈σ∩J} A_{α}x^{α}.

Definition 7.2. Let g ∈ 𝔽_{q}[x_{1}, ⋯, x_{d}] be a polynomial as in (7.1). We say that g is nondegenerate with respect to ∑(g) if for every face σ of ∑(g) that does not contain the origin, the polynomials

\frac{∂g_{σ}}{∂x_{1}} , ⋯, \frac{∂g_{σ}}{∂x_{d}}

have no common zero in (𝔽̄_{q}^{∗})^{d} where 𝔽̄_{q} denotes an algebraic clousure of 𝔽_{q}. We say that g is commode with respect to ∑(g) if for each k = 1, 2, ⋯, d, g contains a term A_{k}x_{k}^{α_{k}} for some α_{k} > 0 and A_{k} ≠ 0.

The general version of the following theorem can be found in [20] (see Theorem 9.2).

Theorem 7.3. Let q be a prime number. Suppose that g : 𝔽_{q}^{d} → 𝔽_{q}, d ≥ 2, is commode and nondegenerate with respect to ∑(g). Then

∑_{x∈𝔽_{q}^{d}} χ(g(x)) = O(q^{\frac{d}{2}} ).

We now prove the first part of Theorem 7.1. Since m ≠ (0, 0), we have ∑_{x∈𝔽_{q}^{2}} χ(−x·m) = 0. We therefore see that for j ≠ 0,

Ŝ_{j}(m) = q^{−3} ∑_{(t,x_{1},x_{2})∈𝔽_{q}^{∗}×𝔽_{q}^{2}} χ(g(t, x_{1}, x_{2})) = q^{−3} ∑_{(t,x_{1},x_{2})∈𝔽_{q}^{3}} χ(g(t, x_{1}, x_{2})),

where g(t, x_{1}, x_{2}) = tx_{1}^{n} + tx_{2}^{n} − m_{1}x_{1} − m_{1}x_{2} − jt.

If m_{1} · m_{2} ≠ 0, then g is commode. By Theorem 7.3, it suffices to show that g is nondegenerate with respect to ∑(g). Note that ∑(g) has five zero-dimensional faces, eight one-dimensional faces and three two-dimensional faces which do not contain the origin. It is easy to show that for every face σ of ∑(g) that does not contain the origin, the polynomials

\frac{∂g_{σ}}{∂t} , \frac{∂g_{σ}}{∂x_{1}} , \frac{∂g_{σ}}{∂x_{2}}

have no common zero in (𝔽_{q}^{∗})^{3} because we may assume that q is sufficiently large and so n is not congruent to 0 modulo q. This implies that g is nondegenerate with respect to ∑(g). We now assume that m_{1} · m_{2} = 0. Without loss of generality, we may assume that m_{1} ≠ 0, and m_{2} = 0 because m ≠ (0, 0). By using Theorem 6.5, we obtain that for a multiplicative character ψ of 𝔽_{q} of order h = gcd(n, q − 1),

Ŝ_{j}(m) = q^{−3} ∑_{(t,x_{1})∈𝔽_{q}^{∗}×𝔽_{q}} χ(tx_{1}^{n} − m_{1}x_{1} − jt) ∑_{k=1}^{h−1} ψ^{−k}(t)qψ̂^{k}(−1)

= q^{−2} ∑_{k=1}^{h−1} ψ̂^{k}(−1) ∑_{(t,x_{1})∈𝔽_{q}^{∗}×𝔽_{q}} ψ^{−k}(t)χ(tx_{1}^{n} − m_{1}x_{1} − jt)

≲ q^{−2}q^{− \frac{1}{2}} ∑_{k=1}^{h−1} |R_{k}(ψ^{−k}, χ)|,

where R_{k}(ψ^{−k}, χ) is given by

∑_{(t,x_{1})∈𝔽_{q}^{∗}×𝔽_{q}} ψ^{−k}(t)χ(tx_{1}^{n} − m_{1}x_{1} − jt).

For each k = 1, 2, ⋯, h − 1, define ψ^{k}(0) = 0. Then we can obtain that

R_{k}(ψ^{−k}, χ) = ∑_{(t,x_{1})∈𝔽_{q}×𝔽_{q}} ψ^{−k}(t)χ(tx_{1}^{n} − m_{1}x_{1} − jt).

Applying Theorem 7.3, we have

R_{k}(ψ^{−k}, χ) = O(q).

This completes the proof.

8 Proof of Theorem 3.4 and Corollary 3.6

As we mentioned in the introduction, this is a simple variation on the proof of Theorem 3.1. Indeed,

#{(x, y) ∈ E × F : ||x − y||_{n} = j}

= q^{2d} ∑_{m} \overline{Ê(m)}F̂(m)Ŝ_{j}(m)

= #E · #F · Ŝ_{j}(0, ⋯, 0) + q^{2d} ∑_{m≠(0,...,0)} \overline{Ê(m)}F̂(m)Ŝ_{j}(m) = I + II.

By the second part of Theorem 5.1(or Theorem 7.1),

I ≲ #E · #F · q^{−1}.

Applying Cauchy-Schwartz, Theorem 5.1( or Theorem 7.1) and Plancherel, we see that

|II| ≲ q^{2d}q^{− \frac{d+1}{2}} ∑_{m≠(0,...,0)} |Ê(m)||F̂(m)|

≤ q^{2d}q^{− \frac{d+1}{2}} (∑_{m} |Ê(m)|^{2})^{\frac{1}{2}} · (∑_{m} |F̂(m)|^{2})^{\frac{1}{2}}

≤ q^{2d}q^{− \frac{d+1}{2}} q^{−d}(∑_{x} |E(x)|^{2})^{\frac{1}{2}} · (∑_{x} |F (x)|^{2})^{\frac{1}{2}}

= q^{\frac{d−1}{2}} · \sqrt{#E} · \sqrt{#F} .

This completes the proof of Theorem 3.4.

In order to prove Corollary 3.6, we observe that by the second part of Theorem 5.1(or Theorem 7.1),

I ≳ #E · #F · q^{−1}.

On the other hand, we have seen above that

|II| ≲ q^{\frac{d−1}{2}} · \sqrt{#E} · \sqrt{#F} ,

and the result follows by a direct comparison.

9 Application to sum/product formulas References

[1] J. Pach, and P. Agarwal, Combinatorial geometry, Wiley-Interscience Series in Discrete Mathematics and Optimization. A Wiley-Interscience Publication. John Wiley and Sons, Inc., New York (1995).

[2] A. Adolphson and S. Sperber, Exponential sums and Newton polyhedra: cohomology and estimates, (1989), 130, 367-406.

[3] J. Bourgain, N. Katz, and T. Tao, A sum-product estimate in finite fields, and applications, Geom. Funct. Anal. 14 (2004), 27-57.

[4] W. Duke and H. Iwaniec, A relation between cubic exponential and Kloosterman sums, Contemp. Math. 143, (1993), 255-258.

[5] P. Erdös On sets of distances of n points, Amer. Math. Monthly. 53 (1946), 248–250.

[6] K. J. Falconer. On the Hausdorff dimensions of distance sets. Mathematika 32 (1985), 206-212.

[7] B. J. Green, Restriction and Kakeya phonomena, Lecture notes (2003).

[8] H. Iwaniec, and E. Kowalski, Analytc Number Theory, Colloquium Publications 53 (2004).

[9] A. Iosevich and M. Rudnev, Erdos/Falconer distance problem in vector spaces over finite fields, TAMS (to appear), (2006).

[10] N. Katz, Gauss sums, Kloosterman sums, and monodromy groups, Ann. Math. Studies 116, Princeton (1988).

[11] M. Lacey and W. McClain, it On an argument of Shkredov in the finite field setting, (2006), On-line journal of analytic combinatorics (http://www.ojac.org).

[12] J. Matousek, Lectures on Discrete Geometry, Graduate Texts in Mathematics, Springer 202 (2002).

[13] G. Mockenhaupt, and T. Tao, Restriction and Kakeya phenomena for finite fields, Duke Math. J. 121 (2004), 35–74.

[14] H. Niederreiter, The distribution of values of Kloosterman sums, Arch. Math. 56 (1991), 270–277.

[15] I. Shparlinski, On the set of distances between two sets in vector spaces over finite fields, (2006), (preprint).

[16] E. Stein, and R. Shakarchi, Fourier analysis, Princeton Lectures in Analysis, (2003).

[17] T. Tao, Finite field analogues of Erdös, Falconer, and Furstenberg problems, preprint.

[18] A. Weil, On some exponential sums, Proc. Nat. Acad. Sci. U.S.A. 34 (1948), 204–207.

[19] R. Lidl and H. Niederreiter, Finite fields, Cambridge Univ. Press (1997).

[20] J. Denef, and F. Loeser,Weights of exponential sums, intersection cohomology, and Newton polyhedra, Invent. Math. 106 (1991), 275–294.