THE DISTRIBUTION OF SPACINGS BETWEEN SMALL POWERS OF A PRIMITIVE ROOT

ZEÉV RUDNICK AND ALEXANDRU ZAHARESCU

1. introduction

Let p be a (large) prime, and g a primitive root modulo p. It is well established that the discrete exponential map n ↦ g^{n} mod p is a “random” map, and this is used by random number generators which use the linear congruential method [2]. For instance, if we denote by {x} the fractional part of a real number x, then it is well known that the sequence of fractional parts

N = \{\{\frac{g^{n}}{p} \}, 1 ≤ n ≤ N\}

is uniformly distributed modulo 1 for N ≫ p^{1/2+ϵ}, and one believes this is still so for N ≫ p^{ϵ}.

We will study a different aspect of randomness - the distribution of spacings between consecutive members of the sequence N as p → ∞ and N grows with p. If N ≥ p − 1, then we get all numbers a/p, 1 ≤ a ≤ p − 1 and so the spacings, being identically 1/p, are not interesting. We will thus assume that N ≪ p^{1−ϵ}. Since the sequence is uniformly distributed, the mean spacing between consecutive elements is 1/N. We “unfold” the sequence by setting x_{n} = N{g^{n}/p}, to get a sequence of levels N_{unf} with mean spacing unity. We will study the distribution of spacings between elements of this unfolded sequence.

Date: December 15, 1997.

Supported in part by grants from the U.S.-Israel Binational Science Foundation and the Israel Science Foundation. Z.R. thanks the Newton Institute where part of this work was carried out.

2 ZEÉV RUDNICK AND ALEXANDRU ZAHARESCU

The statistical model we use is of a sequence of uncorrelated levels - that is “Poisson statistics”. In our case, we conjecture that the spacings have Poisson statistics for N ≫ p^{ϵ} for any ϵ > 0. This means for instance that the distribution of nearest-neighbor spacings is exponential: P (s) = exp(−s).

All local statistics are determined by the m-level correlation functions. For m-tuples y = (y^{(1)}, …, y^{(m)}) of distinct y^{(i)} ∈ N_{unf}, set

Δ(y) = (y^{(1)} − y^{(2)}, y^{(2)} − y^{(3)}, …, y^{(m−1)} − y^{(m)}) ∈ R^{m−1}

The m-level correlation function measures the distribution of differences Δ(y) in R^{m−1}. Thus for each nice compact region I_{0} ⊂ R^{m−1}, we set

(1.1) R_{m}(I_{0}, N) = \frac{1}{N} #\{y ∈ N_{unf} distinct : Δ(y) ∈ I_{0}\}

We want a density R_{m}(x), the m-level correlation function, so that

lim_{N→∞} R_{m}(I_{0}, N) → ∫_{I_{0}} R_{m}(x)dx

For uncorrelated levels, the m-level correlation function is R_{m}^{pois}(x) ≡ 1. Thus we expect that for our sequence,

R_{m}(I_{0}, N) → V ol(I_{0})

as p → ∞, and p^{ϵ} ≪ N ≪ p^{1−ϵ}.

Our first statement is that this is so for N sufficiently large (but N ≪ p^{1−ϵ}):

Theorem 1. For each prime p choose a primitive root g modulo p. Then for m ≥ 2, R_{m}(I_{0}, N) → V ol(I_{0}) as p → ∞, provided N ≫ p^{1−1/2m+ϵ}.

As we will show in Section 2, Theorem 1 follows from counting the solutions of a system of congruences modulo p: For each a = (a_{1}, …, a_{m−1}) ∈ (Z/pZ)^{m−1}, let ν(N, a) be the number of solutions in 1 ≤ n_{i} ≤ N of the system

g^{n_{i}} − g^{n_{i+1}} = a_{i} mod p, 1 ≤ i ≤ m − 1

SPACINGS BETWEEN SMALL POWERS 3

with n_{i} distinct. To guess the size of ν(N, a), we can make the following heuristic: Since there are N^{m} numbers g^{n_{i}} mod p and p^{m−1} possible vectors a, we expect solutions if N^{m} ≫ p^{m−1} and that all solutions are equally likely. As it stands, this is not quite true. For instance, in the case a = (0, …, 0) we have the N “diagonal” solutions n_{1} = ⋯ = n_{m}. Thus we need to exclude a’s for which there are diagonal solutions. In any case, it is only such a that are relevant for us since we assume in advance that the m-tuples (n_{1}, …, n_{m}) are distinct. While we cannot get at the range N about p^{1−1/m}, we can show

Theorem 2. Suppose that a is such that all partial sums b_{j} := ∑_{k=j}^{m−1} a_{k}, 1 ≤ j ≤ m − 1, b_{m} := 0 are distinct modulo p. Then

ν(N, a) = \frac{N^{m}}{p^{m−1}} + O(p^{1/2} log^{m} p)

and in particular if N ≫ p^{1−1/2m+ϵ} then ν(N, a) > 0.

The analogues of Theorems 1 and 2 were proven in [4] for the sequence n^{2} mod q, n ≤ N in the context of understanding the spacings between the elements of the sequence of fractional parts {αn^{2}} for irrational α. Unlike that case, here we can do better than Theorem 1 for the pair correlation (m = 2) by non-trivially summing the result of Theorem 2 over a. We show

Theorem 3. Let g be a primitive root modulo p, and N ≪ p^{1−ϵ}.

i) The pair correlation function of the sequence g^{n} mod p is R_{2}(x) = 1 for N ≫ p^{5/7+ϵ}.

ii) Assuming the Generalized Riemann Hypothesis, this is so for N ≫ p^{2/3+ϵ}.

Unlike Theorem 1, which is essentially a result of using “convexity bounds” for character sums, Theorem 3 requires additional cancellation, hence the role of GRH. Part (i) of Theorem 3 does this unconditionally. This can be done more easily than the way we present, at a cost of getting a smaller improvement over the exponent 3/4 of Theorem 3. To get the exponent 5/7, we use delicate estimates for moments

4 ZEÉV RUDNICK AND ALEXANDRU ZAHARESCU

of character sums, due to Montgomery [3]. He studied a closely related problem - the number variance Σ^{2}(N , L) of the sequence N. This is the variance from its mean of the number n(L) of points of N in a randomly chosen interval of length L times the mean spacing. For uncorrelated levels, Σ^{2} = L, and Montgomery showed that this holds for our sequence provided N ≫ p^{5/7+ϵ}. While his result does not directly imply part (i) the methods are sufficiently powerful to be adapted for this purpose.

Theorem 3 (i) may be improved by averaging over the primitive root g, and in this way we recover the exponent 2/3 unconditionally. For this purpose, we emphasize the dependence of the pair correlation sums R_{2}(I_{0}, N) on the choice of primitive root g by denoting them by R_{2}(I_{0}, N; g). Then we can show (assuming as before N ≪ p^{1−ϵ}):

Theorem 4. Fix δ > 0. Then for each prime p there is an exceptional set E(p, δ) of size ≪_{δ} p^{1−δ} of primitive roots modulo p so that for g not in the exceptional set E(p, δ),

R_{2}(I_{0}, N; g) = Length(I_{0}) + O_{δ}(p^{−δ}), p → ∞

for all intervals I_{0} contained in [−p^{δ}, p^{δ}] and N ≫ p^{2/3+5δ}.

Thus for almost all choices of the primitive root g, the pair correlation function is Poissonian in the range N ≥ p^{2/3+δ}. It is also possible to obtain results of this type in a complementary range, when N is very small; we will treat this aspect of the problem in a subsequent article.

2. The m-level correlation functions

2.1. Proof of Theorem 1: We reduce the proof of Theorem 1 to that of Theorem 2. We recall the definition of the m-level correlation sums

R_{m}(I_{0}, N) = \frac{1}{N} #\{(x_{1}, …, x_{m}) distinct : N(\{\frac{g^{x_{i}}}{p} \} − \{\frac{g^{x_{i+1}}}{p} \}) ∈ I_{0}\}

If we write g^{x_{i}} = u_{i} + k_{i}p, 1 ≤ u_{i} ≤ p − 1, then we need

Δ(u) := (u_{1} − u_{2}, …, u_{m−1} − u_{m}) ∈ \frac{p}{N} I_{0}

Thus for each integer vector a ∈ \frac{p}{N} I_{0} in the dilate of the region I_{0}, we will count the number of solutions of the congruence

g^{x_{i}} − g^{x_{i+1}} = a_{i} mod p,  1 ≤ x_{i} ≤ N  1 ≤ i ≤ m − 1

with x_{i} distinct.

Now the assumption that x_{i} are distinct forces the u_{i} to also be distinct. Thus the possible vectors a are required to be of the form a_{i} = u_{i} − u_{i+1} mod p, with u_{i} ≠ u_{j} mod p. This happens if and only if the partial sums b_{i} = ∑_{k≥i} a_{k}, b_{m} = 0 are distinct, since a direct computation shows that u_{i} − u_{j} = b_{i} − b_{j}: Indeed if i < j then

u_{i} − u_{j} = ∑_{k=i}^{j−1} u_{k} − u_{k+1} = ∑_{k=i}^{j−1} a_{k} = b_{i} − b_{j}

In conclusion we find that

R_{m}(I_{0}, N) = \frac{1}{N} ∑_{a∈ \frac{p}{N} I_{0}}^{∗} ν(N, a)

where ν(N, a) is the number of solutions of the congruence

u_{i} − u_{i+1} = a_{i} mod p 1 ≤ i ≤ m − 1

and the sum ∑^{∗} is over those integer vectors a for which the partial sums b_{i} are distinct.

By a standard count of lattice points in a uniformly expanding region, the number of such vectors is (\frac{p}{N})^{m−1}V ol(I_{0}) + O((\frac{p}{N})^{m−2}) as \frac{p}{N} → ∞. Thus using Theorem 2 we see

R_{m}(I_{0}, N) = \frac{1}{N} ∑_{a∈ \frac{p}{N} I_{0}}^{∗}\{\frac{N^{m}}{p^{m−1}} + O(p^{1/2})\}

= \frac{1}{N} V ol(I_{0})(\frac{p}{N})^{m−1} \frac{N^{m}}{p^{m−1}} + O(\frac{1}{N} (\frac{p}{N})^{m−1}p^{1/2})

= V ol(I_{0}) + O(\frac{p^{m−1/2}}{N^{m}})

which gives Theorem 1 provided N ≫ p^{1−1/2m+ϵ}.

2.2. Computing ν(N, a). To compute ν(N, a),we use Fourier analysis on Z/(p − 1)Z. We set

h_{a}(x_{1}, …, x_{m}) = \begin{cases}1, & g^{x_{i}} − g^{x_{i+1}} = a_{i} mod p \\ 0, & else \end{cases}

Then h_{a} has period ϕ(p) = p − 1 and

ν(N, a) = ∑_{1≤x_{i}≤N} h_{a}(x)

We expand h_{a} in Fourier series

h_{a}(x) = ∑_{r} ĥ_{a}(r)e(\frac{r · x}{p − 1})

where

ĥ_{a}(r) = \frac{1}{(p − 1)^{m}} ∑_{x mod p−1} h_{a}(x)e(−\frac{r · x}{p − 1})

Then

ν(N, a) = ĥ_{a}(0)N^{m} + R(a) (2.1)

with

\begin{aligned}R(a) & = ∑_{r≠0} ĥ_{a}(r) ∑_{1≤x_{1},...,x_{m}≤N} e(\frac{∑_{i=1}^{m} r_{i}x_{i}}{p − 1} ) \\ & = ∑_{r≠0} ĥ_{a}(r) ∏_{i=1}^{m} ∑_{1≤x_{i}≤N} e(\frac{r_{i}x_{i}}{p − 1}) \end{aligned}

Lemma 5.

ĥ_{a}(0) = \frac{1}{p^{m−1}} + O(\frac{1}{p^{m}})

Proof. Setting u_{i} = g^{x_{i}}, we see that ĥ_{a}(0) = \frac{ν}{(p−1)^{m}}, where ν is the number of solutions of the system of congruences

u_{i} − u_{i+1} = a_{i} mod p,  u_{i} ≠ 0 mod p,  1 ≤ i ≤ m − 1

Without the restriction u_{i} ≠ 0, the linear system of equations has exactly p solutions. Since any one of the variables u_{i} determines the rest, the number of solutions with some u_{i} = 0 mod p is at most m. Thus |ν − p| ≤ m and we find ĥ_{a}(0) = p/(p − 1)^{m} + O(p^{−m}).

SPACINGS BETWEEN SMALL POWERS 7

Lemma 6. Suppose a is such that all b_{j}, 1 ≤ j ≤ m are distinct. If r ≠ 0 mod p − 1 then,

ĥ_{a}(r) ≪_{m} p^{−m+1/2}

Proof. As before, we set u_{i} = g^{x_{i}} and define the Dirichlet character

χ_{r}(u) = e(\frac{rx}{p − 1})

We then find that

(p − 1)^{m}ĥ_{a}(r) = ∑_{u_{i}−u_{i+1}=a_{i} mod p} ∏_{i=1}^{m} χ_{r_{i}}(u_{i})

We can express all the u′_{i}s in terms of u_{m} as

u_{j} = u_{j+1} + a_{j} = u_{m} + ∑_{k=j}^{m−1} a_{k}, 1 ≤ j ≤ m − 1

Thus we find: If r ≠ 0 mod p − 1 then

ĥ_{a}(r) = \frac{1}{(p − 1)^{m}} E(\{χ_{r_{i}}\}, b) (2.2)

where for any multiplicative characters χ = (χ_{1}, …, χ_{m}) and b = (b_{1}, …, b_{m}) the exponential sum is

E(χ, b) = ∑_{y mod p} χ_{1}(y + b_{1})χ_{2}(y + b_{2}) … χ_{m}(y + b_{m})

Thus we have reduced the estimation of ĥ_{a}(r) to the estimation of a one-variable character sum E_{m}(χ, b) where χ_{i} are Dirichlet characters modulo p, at least one of them nontrivial, and we further assume that all b_{i} are distinct. These sums came up in the work of J. Johnsen on chains of primitive roots [1]. Using the method of Hasse, and Weil’s proof of the Riemann Hypothesis for a function field over a finite field, Johnsen showed

E_{m}(χ, b) ≤ (m − m_{0} + 1)p^{1/2} + m_{0} + 1 (2.3)

where m_{0} is the number of trivial characters among the χ_{i}.

We saw (2.2) that ĥ_{a}(r) = (p−1)^{−m}E(χ_{ri}, b). If all the b_{i} are distinct then since at least one of the characters χ_{r_{i}} is nontrivial (since r ≠ 0), then by Johnsen’s estimate 2.3, |E(χ_{ri}, b)| ≤ (m − 1)p^{1/2} + O(1), and the lemma follows.

2.3. Proof of Theorem 2: Since

ν(N, a) = ĥ_{a}(0)N^{m} + R(a) = \frac{N^{m}}{p^{m−1}} (1 + O(\frac{1}{p})) + R(a)

It suffices to show that for a such that all partial sums b_{i} are distinct,

R(a) ≪ p^{1/2} log^{m} p (2.4)

This will give

ν(N, a) = \frac{N^{m}}{p^{m−1}} + O(\frac{N^{m}}{p^{m}} + p^{1/2} log^{m} p)

Thus in particular for such a we get ν(N, a) ∼ \frac{N^{m}}{p^{m−1}} provided that N ≫ p^{1−1/2m+ϵ}.

To prove (2.4), we recall that

R(a) = ∑_{r≠0} ĥ_{a}(r) ∏_{i=1}^{m} F_{N}(r_{i})

where

F_{N}(r) = ∑_{1≤x≤N} e(\frac{xr}{p − 1}) (2.5)

This is a geometric progression, and can be estimated by

F_{N}(r) ≪ min(N, ||\frac{r}{p − 1}||^{−1}) (2.6)

where ||x|| is the distance to the nearest integer (we may assume that |r| ≤ (p − 1)/2 by replacing it with p − 1 − r). Using Lemma 6 to estimate the Fourier coefficient ĥ_{a}(r), we find

R(a) ≪ p^{−m+1/2} ∑_{r≠0} ∏_{i=1}^{m} |F_{N}(r_{i})|

SPACINGS BETWEEN SMALL POWERS 9

Now replacing the sum over r ≠ 0 by the sum over all r gives

R(a) ≪ p^{−m+1/2} ∏_{i=1}^{m} ∑_{r_{i}=0}^{p−2} |F_{N}(r_{i})|

≪ p^{−m+1/2}(N + ∑_{r=1}^{(p−1)/2} \frac{p − 1}{r})^{m}

≪ p^{−m+1/2}(N + p log p)^{m} ≪ p^{1/2} log^{m} p

as required. This proves (2.4) and we are done.

3. The Pair Correlation function

As a special case of the results of section 2, we have

R_{2}(I_{0}, N) = \frac{1}{N} ∑_{0≠a∈ \frac{p}{N} I_{0}} ν(N, a)

where ν(N, a) = #{x, y ≤ N : g^{x} − g^{y} = a mod p}. We saw (2.1) that ν(N, a) = N^{2}ĥ_{a}(0) + R(a), with

R(a) = ∑_{(r,s)≠(0,0) mod p−1} ĥ_{a}(r, s)F_{N}(r)F_{N}(s)

with F_{N}(r) given by (2.5). Thus

R_{2}(I_{0}, N) = M + E

with

M = N ∑_{0≠a∈ \frac{p}{N} I_{0}} ĥ_{a}(0)

and

E = \frac{1}{N} ∑_{0≠a∈ \frac{p}{N} I_{0}} R(a)

By Lemma 5, ĥ_{a}(0) = \frac{1}{p} + O(\frac{1}{p^{2}} ) and so

M = Length(I_{0}) + O(\frac{1}{p})

To estimate E, note that we saw in (2.2)

ĥ_{a}(r, s) = \frac{1}{(p − 1)^{2}} ∑_{y} χ_{r}(y)χ_{s}(y + a) = \frac{1}{(p − 1)^{2}} E(χ_{r}, χ_{s}; a)

10 ZEÉV RUDNICK AND ALEXANDRU ZAHARESCU

This is essentially a Jacobi sum and can be evaluated in terms of the Gauss sums

τ(χ) = ∑_{n mod p} χ(n)e(\frac{n}{p})

Lemma 7. We have for a ≠ 0 mod p

E(χ_{r}, χ_{s}; a) = \frac{1}{p}χ_{s}(−1)τ(χ_{r})τ(χ_{s})τ(χ_{r+s}^{−1}) · χ_{r+s}(a) (3.1)

This is seen by expanding χ(y) in Fourier series χ(y) = ∑_{n} χ̂(n)e(\frac{ny}{p}) and noting that χ̂(n) = \frac{τ(χ)}{p}χ^{−1}(−t).

This Lemma is crucial as it uncouples the dependence on a. Consequently we find

\begin{aligned}E & = \frac{1}{Np(p − 1)^{2}} ∑_{(r,s)≠(0,0) mod p−1} F_{N}(r)F_{N}(s)χ_{s}(−1)τ(χ_{r})τ(χ_{s})τ(χ_{r+s}^{−1}) \\ & · ∑_{0≠a∈ \frac{p}{n} I_{0}} χ_{r+s}(a) \end{aligned} (3.2)

We now use

|τ(χ_{t})| = \begin{cases}\sqrt{p}, & t ≠ 0 mod p − 1 \\ 1, & t = 0 mod p − 1 \end{cases}

and (see (2.6))

F_{N}(r) ≪ min(N, ∥\frac{r}{p − 1}∥^{−1})

and separate out the contribution of the terms with r = 0 or s = 0:

\begin{aligned}E & ≪ \frac{1}{Np(p − 1)^{2}} ∑_{r=1}^{p−2} N|F_{N}(r)|p|S(χ_{r})| \\ & + \frac{1}{Np(p − 1)^{2}} ∑_{r,s=1}^{p−2} |F_{N}(r)F_{N}(s)|p^{3/2}|S(χ_{r+s})| \end{aligned} (3.3)

where S(χ) denotes the incomplete character sum

S(χ) = ∑_{a∈ \frac{p}{N} I_{0}} χ(a)

The contribution of the terms with r = 0 or s = 0 (the first summand above) is estimated by using the trivial bound |S(χ)| ≤ \frac{p}{N} to be at most

\frac{1}{Np^{3}} Np\frac{p}{N} ∑_{r=1}^{p−2} |F_{N}(r)| ≪ \frac{log p}{N}

which is negligible in the range considered. Thus up to terms which vanish as p/N → ∞, we get

E ≪ \frac{1}{Np^{3/2}} ∑_{m=0}^{p−2} C_{m}|S(χ_{m})| (3.4)

where

C_{m} = ∑_{r+s=m,r,s≠0} |F_{N}(r)F_{N}(s)|

Lemma 8.

C_{m} ≪ \begin{cases}\frac{p^{2} log p}{m}, & \frac{p}{N} < |m| ≤ \frac{p−1}{2} \\ pN, & 0 ≤ |m| ≤ \frac{p}{N} \end{cases}

Proof. For any m we have

C_{m} ≪ ∑_{r+s=m mod p−1} |F_{N}(r)|^{2} + |F_{N}(s)|^{2} ≪ ∑_{r mod p−1} |F_{N}(r)|^{2} ≪ pN

On the other hand, for individual r ≠ 0 mod p − 1 (which we can take to satisfy |r| ≤ (p − 1)/2), we can use (2.6)

F_{N}(r) ≪ min(N, ∥\frac{r}{p − 1}∥^{−1})

Thus for any m ≠ 0 mod p − 1 and r, s as above, such that r + s = m mod p − 1, one has

|F_{N}(r)F_{N}(s)| ≪ \frac{p^{2}}{|r||s|} = p^{2}(\frac{1}{|r|} + \frac{1}{|s|})\frac{1}{|r| + |s|} ≤ p^{2}(\frac{1}{|r|} + \frac{1}{|s|})\frac{1}{|m|}

Summing over r, s gives C_{m} ≪ p^{2} log p/|m|.

Thus we find that

E ≪ p^{−1/2} ∑_{m=1}^{p/N} |S(χ_{m})| + \frac{p^{1/2} log p}{N} ∑_{m=p/N}^{p−2} \frac{1}{m}|S(χ_{m})| (3.5)

12 ZEÉV RUDNICK AND ALEXANDRU ZAHARESCU

Under the Generalized Riemann Hypothesis,

S(χ_{m}, I) ≪ p^{ϵ}|I|^{1/2} (3.6)

for all ϵ > 0. Inserting into (3.5) we see that under GRH,

E ≪ \frac{p^{1/2}}{N} + \frac{p^{1/2} log p}{N} ∑_{m=1}^{p−2} \frac{1}{m}(\frac{p}{N})^{1/2}p^{ϵ} ≪ \frac{p^{1+ϵ}}{N^{3/2}}

and therefore

R_{2}(N, I_{0}) = Length(I_{0}) + O(\frac{p^{1+ϵ}}{N^{3/2}} )

Thus using GRH, R_{2}(N, I_{0}) → Length(I_{0}) if N ≫ p^{2/3+ϵ}. This proves part (ii) of Theorem 3.

4. Unconditional results

To prove Part (i) of Theorem 3, we use the expression (3.5) for the error E. On summing by parts, it is clear that we will gain if we can estimate moments of the character sums S(χ_{m}): Recall that we denote by I = \frac{p}{N} I_{0} our dilated interval, and

S(χ_{m}, I) = ∑_{n∈I} χ_{m}(n)

We define moments of these character sums by

m_{k}(R, I) := ∑_{r=1}^{R} |S(χ_{r}, I)|^{k} , 1 ≤ R ≤ p − 2

We will show that the first moment (k = 1) is bounded by

m_{1}(R, I) ≪ p^{ϵ} (R^{3/4}|I| + R^{7/8}p^{1/4} + R|I|p^{−1/8}) (4.1)

Inserting (4.1) into (3.5) and applying summation by parts gives

E ≪ \frac{p^{11/8}}{N^{2}} + \frac{p^{5/8}}{N^{7/8}} + \frac{p^{5/4}}{N^{7/4}}

and so if N ≫ p^{5/7+ϵ}, we get E = o(1) as p → ∞ so that we get part (i) of Theorem 3.

SPACINGS BETWEEN SMALL POWERS 13

In the proof of the moment bound (4.1) we closely follow Montgomery ([3]), who proved a similar estimate for the first moment of the weighted character sums

S̃(χ_{r}, H) = ∑_{|h|≤H}(1 − \frac{|h|}{H})χ_{r}(h)

where we take H ∼ |I|. The k-th moment of these weighted sums is

M_{k}(R, H) := ∑_{r=1}^{R} | ∑_{|h|≤H}(1 − \frac{|h|}{H})χ_{r}(h)|^{k}

The bound (4.1) is analogous to the bound on M_{1}(R, H) given in [3]. We will derive it by appealing to Montgomery’s bound on the 4-th moment (see his proof of Lemma 5 in [3]):

M_{4}(R, H) ≪ p^{ϵ} (H^{4} + R^{1/2}p + H^{4}Rp^{−1/2}) (4.2)

To use this result, we first relate the even moments of S(χ, I) to the moments of the weighted sums S̃(χ_{m}, H).

Lemma 9. Let H > 0 be such that the interval [−\frac{H}{2} , \frac{H}{2} ] contains the interval I = \frac{p}{N} I_{0} (chosen so that H ∼ |I| ∼ \frac{p}{N}). Then

m_{2}(R, I) ≪ H^{2} + M_{2}(2R, H). (4.3)

Proof. To see this, we use

m_{2}(R, I) = ∑_{r=1}^{R} |∑_{n∈I} χ_{r}(n)|^{2}

≤ ∑_{r=1}^{R}(2 − \frac{r}{R}) |∑_{n∈I} χ_{r}(n)|^{2}

≤ \frac{1}{2R} ∑_{u,v=1}^{2R} |∑_{n∈I} χ_{u}(n)χ̄_{v}(n)|^{2}

where we have used χ_{u}(n)χ̄_{v}(n) = χ_{u−v}(n) and the number of ways of writing r = u − v with 1 ≤ u, v ≤ 2R is 2R − |r| for |r| ≤ 2R.

Expanding the squared sum and switching summation gives

m_{2}(R, I) ≤ \frac{1}{2R} ∑_{n,n′∈I} |∑_{r=1}^{2R} χ_{r}(n)χ̄_{r}(n′)|^{2} (4.4)

We now note that for n ∈ I ⊂ [−\frac{H}{2} , \frac{H}{2} ], we have 1 ≤ 2(1− \frac{|n|}{H}), so since all terms are positive, the RHS of (4.4) is bounded above by

\begin{matrix}≤ \frac{1}{2R} ∑_{|n|,|n′|} 2(1 − \frac{|n|}{H})2(1 − \frac{|n′|}{H}) |∑_{r=1}^{2R} χ_{r}(n)χ̄_{r}(n′)|^{2} \\ ≤ \frac{1}{2R} ∑_{u,v=1}^{2R} | ∑_{|n|≤H} 2(1 − \frac{|n|}{H})χ_{u}(n)χ̄_{v}(n)|^{2} \end{matrix}

where we have again expanded the squared sum and interchanged summation; using the same reasoning as before on the last term above, we find

m_{2}(R, I) ≤ \frac{1}{2R} ∑_{|r|≤2R−1}(2R − |r|) | ∑_{|n|≤H} 2(1 − \frac{|n|}{H})χ_{r}(n)|^{2}

≤ 4 ∑_{|r|≤2R−1} | ∑_{|n|≤H}(1 − \frac{|n|}{H})χ_{r}(n)|^{2}

= 4 | ∑_{|n|≤H}(1 − \frac{|n|}{H})|^{2} + 8 ∑_{r=1}^{2R−1} | ∑_{|n|≤H}(1 − \frac{|n|}{H})χ_{r}(n)|^{2}

≤ 4H^{2} + 8M_{2}(2R, H)

This concludes the proof of our lemma.

This lemma in combination with Cauchy’s inequality gives

\begin{aligned}m_{2}(R, I) & ≪ H^{2} + M_{2}(2R, H) ≪ H^{2} + R^{1/2}M_{4}(2R, H)^{1/2} \\ & ≪ R^{1/2}H^{2} + R^{3/4}p^{1/2} + H^{2}Rp^{−1/4} \end{aligned}

Combining this with Cauchy’s inequality m_{1}(R, I) ≤ R^{1/2}m_{2}(R, I)^{1/2} gives the bound (4.1).

SPACINGS BETWEEN SMALL POWERS 15

5. Proof of Theorem 4

Given δ > 0 and p a large prime we proceed to define the exceptional set E(p, δ). We first cut the entire range [p^{\frac{2}{3} +5δ}, p^{1−δ}] for N in dyadic blocks. So we consider the intervals [2^{i}, 2^{(i+1)}) for [(\frac{2}{3} + 5δ) log_{2} p] ≤ i ≤ [(1 − δ) log_{2} p] which cover the above range.

Next we cut the interval [−p^{δ}, p^{δ}] where all our intervals I_{0} are supported in intervals of length p^{−δ}, by means of the intervals J_{j} = [jp^{−δ}, (j + 1)p^{−δ}) for [−p^{2δ}] ≤ j ≤ [p^{2δ}] which cover the above range.

Now for any pair (i, j) as above we define an exceptional set by the condition that the RHS of (3.5), where N = 2^{i} and I_{0} = J_{j}, to be > p^{−3δ}. So we let E(p, δ, i, j) to be the set of those primitive roots g mod p for which we have:

p^{−1/2} ∑_{m=1}^{p/2^{i}} |S(χ_{m}, \frac{p}{2^{i}} J_{j})| + \frac{p^{1/2} log p}{2^{i}} ∑_{m=p/2^{i}}^{p−2} \frac{1}{m}|S(χ_{m}, \frac{p}{2^{i}} J_{j})| > p^{−3δ} (5.1)

The exceptional set E(p, δ) is then defined as the union of all these exceptional sets E(p, δ, i, j).

Lemma 10. The exceptional set satisfies #E(p, δ) ≪_{δ} p^{1−δ}.

Proof. Since the number of i’s is ≤ log_{2} p and the number of j’s is ≤ 2p^{2δ} it follows that the total number of pairs (i, j) is ≪_{δ} p^{3δ}. Therefore it is enough to show that for any pair (i, j) one has :

#E(p, δ, i, j) ≪_{δ} p^{1−4δ} (5.2)

In order to prove (5.2) we fix such a pair (i, j) and note that:

(5.3) #E(p, δ, i, j)p^{−3δ} ≤

∑_{g mod p} (p^{−1/2} ∑_{m=1}^{p/2^{i}} |S(χ_{m}, \frac{p}{2^{i}} J_{j})| + \frac{p^{1/2} log p}{2^{i}} ∑_{m=p/2^{i}}^{p−2} \frac{1}{m}|S(χ_{m}, \frac{p}{2^{i}} J_{j})|)

We now fix a primitive root g mod p and write any other primitive root in the form g^{l}, where 1 ≤ l ≤ p − 1 and (l, p − 1) = 1. Note that χ_{g^{l}} = (χ_{g})^{t} where tl = 1 mod p − 1. Hence the RHS of (5.3) equals:

∑_{(l,p−1)=1} (p^{−1/2} ∑_{m=1}^{p/2^{i}} |S(χ_{tm}, \frac{p}{2^{i}} J_{j})| + \frac{p^{1/2} log p}{2^{i}} ∑_{m=p/2^{i}}^{p−2} \frac{1}{m}|S(χ_{tm}, \frac{p}{2^{i}} J_{j})|) (5.4)

where l and t are related by lt = 1 mod p − 1. This sum is bounded above by:

\frac{p^{1/2} log p}{2^{i}} ∑_{(l,p−1)=1} ∑_{m=1}^{p−2} \frac{1}{m}|S(χ_{tm}, \frac{p}{2^{i}} J_{j})| (5.5)

In this sum we make the change of variable : n = tm mod p − 1, m = ln mod p − 1 and change the order of summation to see that the above sum equals:

\frac{p^{1/2} log p}{(p − 1)2^{i}} ∑_{n=1}^{p−2} |S(χ_{n}, \frac{p}{2^{i}} J_{j})| ∑_{(l,p−1)=1}\{\frac{nl}{p − 1}\}^{−1} (5.6)

where {.} denotes as usually the fractional part. To see this, note that since m is the smallest positive number which satisfies m = nl mod p − 1, we have \frac{m}{p−1} = \{\frac{nl}{p−1}\} so \frac{1}{m} = \frac{1}{p−1}\{\frac{nl}{p−1}\}^{−1}. To bound the inner sum above, let d = (n, p − 1), n = ad, p − 1 = bd. Then \{\frac{nl}{p−1}\} = \{\frac{al}{b}\}. If l would be allowed to take on all the values 1, 2, ..., p−1 then \{\frac{al}{b}\} would produce all the values 0, \frac{1}{b}, \frac{2}{b}, ..., \frac{b−1}{b} in a certain order, and this sequence will be repeated exactly d times. Since our l will assume only values which are relatively prime to (p − 1), \{\frac{al}{b}\} can not be zero. Therefore

∑_{(l,p−1)=1}\{\frac{nl}{p − 1}\}^{−1} ≤ d ∑_{j=1}^{b−1} (\frac{j}{b})^{−1} ≪ (p − 1) log p (5.7)

uniformly for n ≠ 0 mod p. It follows that the sum in (5.6) is

≪ \frac{p^{\frac{1}{2}} (log p)^{2}}{2^{i}} ∑_{n=1}^{p−2} |S(χ_{n}, \frac{p}{2^{i}} J_{j})| (5.8)

Hence one has:

#E(p, δ, i, j) ≪_{δ} \frac{p^{\frac{1}{2} +4δ}}{2^{i}} m_{1}(p − 2, \frac{p}{2^{i}} J_{j}) (5.9)

SPACINGS BETWEEN SMALL POWERS 17

To estimate the RHS of (5.9) we apply Cauchy’s inequality:

m_{1}(p − 2, \frac{p}{2^{i}} J_{j}) ≤ (p − 2)^{\frac{1}{2}} (m_{2}(p − 2, \frac{p}{2^{i}} J_{j}))^{\frac{1}{2}} (5.10)

Now the second moment can be estimated accurately:

m_{2}(p − 2, \frac{p}{2^{i}} J_{j}) ≤ m_{2}(p − 1, \frac{p}{2^{i}} J_{j}) = ∑_{m=1}^{p−1} |S(χ_{m}, \frac{p}{2^{i}} J_{j})|^{2} =

= ∑_{m=1}^{p−1} ∑_{n_{1},n_{2}∈p2^{−i}J_{j}} χ_{m}(n_{1})χ̄_{m}(n_{2})

Here we change the order of summation and then note that the inner sum equals p − 1 if n_{1} = n_{2} and is zero if n_{1} ≠ n_{2}.

Hence m_{2}(p − 1, \frac{p}{2^{i}} J_{j}) = (p − 1)#(\frac{p}{2^{i}} J_{j}) which in combination with (5.9) and (5.10) gives (5.2).

We now proceed to show that

R_{2}(I_{0}, N; g) = Length(I_{0}) + O_{δ}(p^{−δ}) (5.11)

for all I_{0} , N and g as in the statement of Theorem 4.

Fix I_{0}, N and g as above and let i_{0} be such that 2^{i_{0}} ≤ N < 2^{i_{0}+1}. We cut the interval I_{0} in intervals of length N2^{−i_{0}}p^{−δ}. More precisely let I_{1} be the largest subinterval of I_{0} which is a union of intervals of the form N2^{−i_{0}}J_{j}, I_{1} = ⋃_{j=j_{1}}^{j_{2}} N2^{−i_{0}}J_{j}, say. Denote I_{2} = ⋃_{j=j_{1}−1}^{j_{2}+1} N2^{−i_{0}}J_{j}. Then I_{0} ⊂ I_{2}. Recall that |j_{1}|, |j_{2}| ≪ p^{2δ}.

From the definition of pair correlations it is clear that:

R_{2}(I_{1}, N; g) = ∑_{j=j_{1}}^{j_{2}} R_{2}(\frac{N}{2^{i_{0}}} J_{j}, N; g) (5.12)

and similarly for R_{2}(I_{2}, N; g). For any term in the RHS of (5.12) we apply (3.5), noting that for these new intervals we have \frac{p}{N} \frac{N}{2^{i_{0}}} J_{j} = \frac{p}{2^{i_{0}}} J_{j}:

\begin{aligned}|R_{2}(\frac{N}{2^{i_{0}}} J_{j}, N; g) − Length(\frac{N}{2^{i_{0}}} J_{j})| & ≪ p^{−1/2} ∑_{m=1}^{p/N} |S(χ_{m}, \frac{p}{2^{i_{0}}} J_{j})| \\ & + \frac{p^{1/2} log p}{N} ∑_{m=p/N}^{p−2} \frac{1}{m}|S(χ_{m}, \frac{p}{2^{i_{0}}} J_{j})| \end{aligned} (5.13)

18 ZEÉV RUDNICK AND ALEXANDRU ZAHARESCU

Now the point is that the character sums that appear on the RHS of (5.13) do not depend on N but only on i_{0}. Moreover, the weights that appear on the RHS of (5.13) will still have about the same size if we replace N by 2^{i_{0}}. Therefore the entire RHS of (5.13) has about the same size as the LHS of (5.1) which is ≤ p^{−3δ} since our g is not in E(p, δ, i, j).

Summing the inequalities (5.13) for j_{1} ≤ j ≤ j_{2} we obtain : |R_{2}(I_{1}, N; g) − Length(I_{1})| ≪_{δ} p^{−δ} (5.14) Similarly one has: |R_{2}(I_{2}, N; g) − Length(I_{2})| ≪_{δ} p^{−δ}. (5.15)

On the other hand, from the definition of pair correlations (1.1) it is clear that since I_{1} ⊂ I_{0} ⊂ I_{2}, we have : R_{2}(I_{1}, N; g) ≤ R_{2}(I_{0}, N; g) ≤ R_{2}(I_{2}, N; g) (5.16) Moreover, the difference between the length of either interval I_{1}, I_{2} from the length of I_{0} is at most 4p^{−δ}. On combining this with (5.14), (5.15), and (5.16) we obtain (5.11) which completes the proof of Theorem 4.

References

1. J. Johnsen On the distribution of powers in finite fields, J. Reine Angew. Math. 251 (1971), 10–19.

2. D. Knuth The Art of Computer Programming, 2nd edition, Addison-Wesley, Reading, Mass. 1973.

3. H. Montgomery Distribution of Small Powers of a Primitive Root, Advances in Number Theory (Kingston, ON, 1991), Oxford Sci. Publ., Oxford Univ. Press, New York, 1993, 137–149.

4. Z. Rudnick, P. Sarnak and A. Zaharescu, in preparation.

Raymond and Beverly Sackler School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel

Department of Mathematics, Massachusetts Institute of Technology, 77 Mass. Avenue, Cambridge, MA 02139, USA