A multidimensional version of a result of Davenport-Erdős

O-Yeat Chan, Geumlan Choi, and Alexandru Zaharescu Department of Mathematics University of Illinois 1409 West Green Street Urbana, IL 61801 USA ochan@math.uiuc.edu g-choi1@math.uiuc.edu zaharesc@math.uiuc.edu

Abstract

Davenport and Erdős showed that the distribution of values of sums of the form

S_{h}(x) = ∑_{m=x+1}^{x+h} (\frac{m}{p}) ,

where p is a prime and (\frac{m}{p}) is the Legendre symbol, is normal as h, p → ∞ such that \frac{log h}{log p} → 0. We prove a similar result for sums of the form

S_{h}(x_{1}, …, x_{n}) = ∑_{z_{1}=x_{1}+1}^{x_{1}+h} ⋯ ∑_{z_{n}=x_{n}+1}^{x_{n}+h} (\frac{z_{1} + ⋯ + z_{n}}{p} ) .

1. Introduction

Given a prime number p, an integer x and a positive integer h, we consider the sum

S_{h}(x) = ∑_{m=x+1}^{x+h} (\frac{m}{p}) ,

where here and in what follows (\frac{m}{p}) denotes the Legendre symbol. The expected value of

such a sum is \sqrt{h}. If p is much larger than h, it is a very difficult problem to show that there is any cancellation in an individual sum S_{h}(x) as above. The classical inequality of Pólya-Vinogradov (see [8], [10]) shows that S_{h}(x) = O(\sqrt{p} log p), and assuming the Generalized Riemann Hypothesis, Montgomery and Vaughan [7] proved that S_{h}(x) = O(\sqrt{p} log log p). The results of Burgess [2] provide cancellation in S_{h}(x) for smaller values of h, as small as p^{1/4}. One does expect to have cancellation in S_{h}(x) for h > p^{ϵ}, for fixed ϵ > 0 and p large. This would imply the well-known hypothesis of Vinogradov that the smallest positive quadratic nonresidue mod p is < p^{ϵ}, for any fixed ϵ > 0 and p large enough in terms of ϵ. We mention that Ankeny [1] showed that assuming the Generalized Riemann Hypothesis, the smallest positive quadratic nonresidue mod p is O(log^{2} p). It is much easier to obtain cancellation, even square root cancellation, if one averages S_{h}(x) over x. In fact, Davenport and Erdős [5] entirely solved the problem of the distribution of values of S_{h}(x), 0 ≤ x < p, as h, p → ∞ such that \frac{log h}{log p} → 0. Under these growth conditions they showed that the distribution becomes normal. Precisely, they proved that

\frac{1}{p}M_{p}(λ) → \frac{1}{\sqrt{2π}} ∫_{−∞}^{λ} e^{− \frac{1}{2} t^{2}}dt, as p → ∞,

where M_{p}(λ) is the number of integers x, 0 ≤ x < p, satisfying S_{h}(x) ≤ λh^{\frac{1}{2}} .

For a fixed n ≥ 2, we consider multidimensional sums of the form

S_{h}(x_{1}, …, x_{n}) = ∑_{z_{1}=x_{1}+1}^{x_{1}+h} ⋯ ∑_{z_{n}=x_{n}+1}^{x_{n}+h} (\frac{z_{1} + ⋯ + z_{n}}{p} ) ,  (1.1)

where p is a prime number, x_{1}, …, x_{n} are integer numbers, and h is a positive integer. Upper bounds for individual sums of this type have been provided by Chung [3]. In this paper we investigate the distribution of values of these sums, and obtain a result similar to that of Davenport and Erdős. Let

c_{n} := ∫_{0}^{n} f(t)^{2}dt,  (1.2)

where f(t) is the volume of the region in ℝ^{n−1} defined by

{(a_{1}, …, a_{n−1}) ∈ ℝ^{n−1} : 0 < a_{i} ≤ 1, i = 1, …, n − 1; t − 1 ≤ a_{1} + ⋯ + a_{n−1} < t}.

We will see that this constant c_{n} naturally appears as a normalizing factor in our distribution result below. Let M_{n,p}(λ) be the number of lattice points (x_{1}, …, x_{n}) with 0 ≤ x_{1}, …, x_{n} < p, such that

S_{h}(x_{1}, …, x_{n}) ≤ λcn^{\frac{1}{2}}h^{n− \frac{1}{2}} .

Then we show that as h, p → ∞ such that \frac{log h}{log p} → 0, one has

\frac{1}{p^{n}} M_{n,p}(λ) → \frac{1}{\sqrt{2π}} ∫_{−∞}^{λ} e^{− \frac{t^{2}}{2}} dt.

2. Estimating the moments

We now proceed to estimate higher moments of our sums S_{h}(x_{1}, …, x_{n}).

Lemma 1. Let p be a prime number and let h and r be positive integers. Then

∑_{x_{1},...,x_{n}(mod p)} S_{h}^{2r}(x_{1}, …, x_{n}) = 1 · 3 ⋯ (2r − 3)(2r − 1)

· (c_{n}h^{2n−1} + O_{n,r}(h^{2n−2}))^{r} (p^{n} + O_{r}(p^{n−1})) + O_{r} (h^{2nr}p^{n− \frac{1}{2}} ) , (2.1)

and

∑_{x_{1},...,x_{n}(mod p)} S_{h}^{2r−1}(x_{1}, …, x_{n}) = O_{r} (h^{n(2r−1)}p^{n− \frac{1}{2}} ) .  (2.2)

Proof. Consider first the case when the exponent is 2r. We have

S_{h}(x_{1}, …, x_{n}) = ∑_{a_{1}=1}^{h} ⋯ ∑_{a_{n}=1}^{h} (\frac{x_{1} + ⋯ + x_{n} + a_{1} + ⋯ + a_{n}}{p} ) .

Therefore

S_{h}^{2r}(x_{1}, …, x_{n}) =

∑_{a_{1,1}=1}^{h} ⋯ ∑_{a_{n,1}=1}^{h} ⋯ ∑_{a_{1,2r}=1}^{h} ⋯ ∑_{a_{n,2r}=1}^{h} (\frac{(x_{1}+···+x_{n}+a_{1,1}+···+a_{n,1})···(x_{1}+···+x_{n}+a_{1,2r}+···+a_{n,2r})}{p})

and so

∑_{x_{1},...,x_{n}(mod p)} S_{h}^{2r}(x_{1}, …, , x_{n})

= ∑_{\begin{matrix}a_{i,j}=1 \\ 1≤i≤n \\ 1≤j≤2r \end{matrix}}^{h} ∑_{x_{1},...,x_{n}(mod p)} (\frac{(x_{1}+···+x_{n}+a_{1,1}+···+a_{n,1})···(x_{1}+···+x_{n}+a_{1,2r}+···+a_{n,2r})}{p}) .

Divide the sets of n-tuples {(a_{1,i}, …, a_{n,i}) : i = 1, …, 2r} into two types. If there exists an i such that the number of j ∈ {1, …, 2r} for which a_{1,i} + ⋯ + a_{n,i} = a_{1,j} + ⋯ + a_{n,j} is odd, we say that it is of type 1. The others will be of type 2. First consider the sum of terms of type 1. Since for each fixed x_{2}, …, x_{n}, the product (x_{1} + ⋯ + x_{n} + a_{1,1} + ⋯ + a_{n,1}) ⋯ (x_{1} + ⋯ + x_{n} + a_{1,2r} + ⋯ + a_{n,2r}), as a polynomial in x_{1}, is not congruent mod p to the square of another polynomial, by Weil’s bounds [11] we have

∑_{x_{2},...,x_{n}(mod p)} ∑_{x_{1}(mod p)} (\frac{(x_{1}+···+x_{n}+a_{1,1}+···+a_{n,1})···(x_{1}+···+x_{n}+a_{1,2r}+···+a_{n,2r})}{p})

= ∑_{x_{2},··· ,x_{n}(mod p)} O_{r}(p^{1/2}) = O_{r}(p^{n− \frac{1}{2}} ).

So the sum of terms of type 1 is O_{r} (h^{2nr}p^{n− \frac{1}{2}} ). Now consider the sum of terms of type 2. Since the polynomial (x_{1} + ⋯ + x_{n} + a_{1,1} + ⋯ + a_{n,1}) ⋯ (x_{1} + ⋯ + x_{n} + a_{1,2r} + ⋯ + a_{n,2r}) is a perfect square in this case, the Legendre symbol is 1, except for those values of x_{1}, …, x_{n} for which this product vanishes mod p. Since the product has at most r distinct factors, for any values of x_{2}, …, x_{n} there are at most r values of x_{1} for which the product vanishes mod p. Thus the sum over x_{1}, …, x_{n} is at most p^{n}, and at least (p − r)p^{n−1}. Hence the contribution of terms of type 2 is

F (h, n, r) (p^{n} + O_{r}(p^{n−1})) ,

where F (h, n, r) is the number of sets {(a_{1,i}, …, a_{n,i}) : i = 1, …, 2r} yielding multinomials of type 2, i.e., sets for which each value of a_{1,i}+⋯+a_{n,i} occurs an even number of times, as i runs over the set {1, 2, …, 2r}. For any integer m with n ≤ m ≤ nh, let N_{m}(h, n) be the number of n-tuples (a_{1,i}, …, a_{n,i}) for which 1 ≤ a_{1,i}, …, a_{n,i} ≤ h and a_{1,i} + ⋯ + a_{n,i} = m. Then the number of pairs of n-tuples (a_{1,i}, …, a_{n,i}), (a_{1,j}, …, a_{n,j}), with a_{1,i}+⋯+a_{n,i} = a_{1,j}+⋯+a_{n,j}, is ∑_{m} (N_{m}(h, n))^{2}. In what follows we write simply N_{m} instead of N_{m}(h, n). The number of ways to choose r such pairs of n-tuples (not necessarily distinct) is (∑_{m} N_{m}^{2})^{r}, and the number of ways to arrange these pairs in 2r places is (2r − 1)(2r − 3) ⋯ 3 · 1. Hence,

F (h, n, r) ≤ 1 · 3 ⋯ (2r − 3)(2r − 1) (∑_{m} N_{m}^{2})^{r} .

On the other hand, the number of ways of choosing r pairs of distinct sums is at least

(∑_{m} N_{m}^{2}) (∑_{m} N_{m}^{2} − max_{m}{N_{m}^{2}}) ⋯ (∑_{m} N_{m}^{2} − (r − 1) max_{m}{N_{m}^{2}})

≥ (∑_{m} N_{m}^{2} − r max_{m}{N_{m}^{2}})^{r} ,

and the number of different ways to arrange them in 2r places is (2r − 1)(2r − 3) ⋯ 3 · 1. Thus

1 · 3 ⋯ (2r − 3)(2r − 1) (∑_{m} N_{m}^{2} − r max_{m} N_{m}^{2})^{r} ≤ F (h, n, r)

≤ 1 · 3 ⋯ (2r − 3)(2r − 1) (∑_{m} N_{m}^{2})^{r} .

Next, we estimate the number N_{m}(h, n) = N_{m}. It is clear that for any m with 0 < m ≤ nh, N_{m} is the number of lattice points in the region R_{m} in ℝ^{n−1} given by

R_{m} := \begin{cases}0 < a_{i} ≤ h, for i = 1, …, n − 1; \\ m − h ≤ a_{1} + ⋯ + a_{n−1} < m. \end{cases}

We send the region R_{m} to the unit cube in ℝ^{n−1} via the map x ↦ \frac{x}{h}. Then we have

\overline{R_{m}} := \begin{cases}0 < a_{i} ≤ 1, for i = 1, …, n − 1; \\ \frac{m}{h} − 1 ≤ a_{1} + ⋯ + a_{n−1} < \frac{m}{h}. \end{cases}

By the Lipschitz principle [4] we know that

N_{m} = vol(R_{m}) + O_{n}(h^{n−2}) = h^{n−1}vol(\overline{R}_{m}) + O_{n}(h^{n−2}).

With f defined as in the Introduction, we may write vol(\overline{R}_{m}) = f(\frac{m}{h}). Then

∑_{0<m≤nh} N_{m}^{2} = ∑_{0<m≤nh} h^{2n−2} (f (\frac{m}{h}))^{2} + ∑_{0<m≤nh} O_{n}(h^{2n−3})

= h^{2n−1} ∑_{0<m≤nh} (f (\frac{m}{h}))^{2} \frac{1}{h} + O_{n}(h^{2n−2})

= h^{2n−1} ∫_{0}^{n} (f(t))^{2} dt + O_{n}(h^{2n−2})

= h^{2n−1}c_{n} + O_{n}(h^{2n−2}), as h → ∞.

Hence

F (h, n, r) = 1 · 3 ⋯ (2r − 3)(2r − 1) (c_{n}h^{2n−1} + O_{n,r}(h^{2n−2}))^{r} ,

and (2.1) follows. It is clear that (2.2) holds, since there are no sets of type 2 in this case. This completes the proof of the lemma.

□

3. Main results

By using the estimates for the higher moments of S_{h}(x_{1}, …, x_{n}) given in Lemma 1, we show that under appropriate growth conditions on h, p, the distribution of our sums S_{h}(x_{1}, …, x_{n}) is normal.

Theorem 1. Let h be any function of p such that

h → ∞, \frac{log h}{log p} → 0 as p → ∞.  (3.1)

Let M_{n,p}(λ) denote the number of lattice points (x_{1}, …, x_{n}), 0 ≤ x_{1}, …, x_{n} < p, such that

S_{h}(x_{1}, …, x_{n}) ≤ λcn^{\frac{1}{2}}h^{n− \frac{1}{2}} ,

with S_{h}(x_{1}, …, x_{n}) defined by (1.1) and c_{n} defined by (1.2). Then

\frac{1}{p^{n}} M_{n,p}(λ) → \frac{1}{\sqrt{2π}} ∫_{−∞}^{λ} e^{− \frac{t^{2}}{2}} dt, as p → ∞.

Proof. We consider the sum

\frac{1}{p^{n}} ∑_{x_{1},...,x_{n}(mod p)} (\frac{1}{c_{n}^{1/2}h^{n−1/2}} S_{h}(x_{1}, …, x_{n}))^{r} .  (3.2)

It follows from the above lemma that for each fixed r and n, if r is even, then the quantity from (3.2) is

1 · 3 ⋯ (r − 3)(r − 1) (1 + O_{n,r} (\frac{1}{h}))^{r} (1 + O_{r} (\frac{1}{p})) + O_{n,r}(h^{\frac{r}{2}} p^{− \frac{1}{2}} ),

while if r is odd, the quantity from (3.2) is O_{n,r}(h^{\frac{r}{2}} p^{− \frac{1}{2}} ). Using (3.1), we have that for each positive integer r,

\frac{1}{p^{n}} ∑_{x_{1},...,x_{n}(mod p)} (\frac{1}{c_{n}^{1/2}h^{n−1/2}} S_{h}(x_{1}, …, x_{n}))^{r} → μ_{r}, as p → ∞,  (3.3)

where μ_{r} = \begin{cases}1 · 3 ⋯ (r − 1), & if r is even; \\ 0, & if r is odd. \end{cases}

Let N_{n,p}(s) be the number of n-tuples (x_{1}, …, x_{n}) with 0 ≤ x_{i} < p, i = 1, …, n such that S_{h}(x_{1}, …, x_{n}) ≤ s. Then N_{n,p}(s) is a non-decreasing function of s with discontinuities at certain integral values of s. We also note that N_{n,p}(s) = 0 if s < −h^{n}, N_{n,p}(s) = p^{n} if s ≥ h^{n},

and M_{n,p}(λ) = N_{n,p}(λcn^{\frac{1}{2}}h^{n− \frac{1}{2}} ). We write (3.3) in the form

\frac{1}{p^{n}} ∑_{s=−h^{n}}^{h^{n}} (\frac{s}{cn^{\frac{1}{2}}h^{n− \frac{1}{2}}} )^{r} (N_{n,p}(s) − N_{n,p}(s − 1)) → μ_{r}, as p → ∞.  (3.4)

This is similar to relation (26) of Davenport-Erdős [5]. Following their argument, if we set

Φ_{n,p}(t) = \frac{1}{p^{n}} N_{n,p}(tcn^{\frac{1}{2}}h^{n− \frac{1}{2}} ) = \frac{1}{p^{n}} M_{n,p}(t),

and

Φ(t) = \frac{1}{\sqrt{2π}} ∫_{−∞}^{t} e^{− \frac{1}{2} u^{2}}du,

we obtain

∫_{−∞}^{∞} t^{r}dΦ_{n,p}(t) → ∫_{−∞}^{∞} t^{r}dΦ(t), as p → ∞,  (3.5)

for any fixed positive integer r, which is the analogue of relation (28) from [5]. It now remains to show that, for each real number λ,

Φ_{n,p}(λ) → Φ(λ), as p → ∞.  (3.6)

The assertion of (3.6) follows from the well-known fact (see [6]) in the theory of probability that if F_{k} and F are probability distributions with finite moments m_{k,r}, m_{r} of all orders, respectively, and if F is the unique distribution with the moments m_{r} such that m_{k,r} → m_{r} for all r as k → ∞, then F_{k} → F as k → ∞. We give the outline of the proof following the argument of Davenport-Erdős [5]. Suppose that (3.6) fails for some λ. Then we can find a subsequence {Φ_{n,p′}} and a δ > 0 such that

|Φ_{n,p′}(λ) − Φ(λ)| ≥ δ, for all p′.  (3.7)

By the two theorems of Helly (see the introduction to [9]) there exists a subsequence {Φ_{n,p′′}} of {Φ_{n,p′}} which converges to a distribution Ψ at every point of continuity, and

∫_{−∞}^{∞} t^{r}dΨ(t) = lim_{p′′→∞} ∫_{−∞}^{∞} t^{r}dΦ_{n,p′′} = ∫_{−∞}^{∞} t^{r}dΦ(t).

Since Φ is the only distribution with these special moments μ_{1}, μ_{2}, …, we have Ψ(t) = Φ(t) for all t. This contradicts (3.7). Hence one concludes that, as p → ∞,

\frac{1}{p^{n}} M_{n,p}(λ) = Φ_{n,p}(λ) → Φ(λ) = \frac{1}{\sqrt{2π}} ∫_{−∞}^{λ} e^{− \frac{1}{2} t^{2}}dt,

which completes the proof of the theorem. □

We remark that c_{n} can be explicitly computed for any given value of n. The following proposition provides an equivalent formulation of c_{n}, which allows for easier computations in higher dimensions. For any n, consider the polynomial in two variables

g_{n}(X, Y) = ∑_{l=0}^{n−1} (∑_{k=0}^{l}(−1)^{k}\binom{n}{k}\binom{X + (l − k)Y + n − 1}{n − 1})^{2} .

Note that the total degree of g_{n}(X, Y) is at most 2n − 2.

Proposition 1. For any n,

c_{n} = ∑_{k=0}^{2n−2} \frac{a_{n,k}}{k + 1} ,

where a_{n,k} is the coefficient of X^{k}Y^{2n−2−k} in g_{n}(X, Y).

Proof. We know that for fixed n and h → ∞,

∑_{m} N_{m}^{2} = h^{2n−1}c_{n} + O_{n}(h^{2n−2}),

where N_{m} = N_{m}(h, n) is the number of n-tuples (a_{1}, …, a_{n}) such that a_{1} + ⋯ + a_{n} = m, with 1 ≤ a_{i} ≤ h. Replacing m by m′ = m − n and each a_{i} by b_{i} = a_{i} − 1, we get ∑_{m} N_{m}^{2} = ∑_{m′}(N′_{m′})^{2}, where N′_{m′} is the number of n-tuples (b_{1}, …, b_{n}) such that b_{1} + ⋯ + b_{n} = m′, with 0 ≤ b_{i} ≤ h − 1.

Now, the number of ways to obtain a sum of m′ from n non-negative integers, with no restrictions, is \binom{m′+n−1}{n−1}. If we restrict any fixed b_{i} to satisfy the inequality b_{i} ≥ h, then the number of ways drops to \binom{m′−h+n−1}{n−1}. If we restrict any two b_{i}, b_{j} to satisfy b_{i}, b_{j} ≥ h then we have \binom{m′−2h+n−1}{n−1} ways, and so on.

Since for each k, there are \binom{n}{k} ways to choose exactly k of the b_{i}’s to be greater than h, we obtain by the inclusion-exclusion principle,

N′_{m′} = ∑_{0≤k≤m′/h}(−1)^{k}\binom{n}{k}\binom{m′ − kh + n − 1}{n − 1}.

So we have, for lh ≤ m′ < (l + 1)h, 0 ≤ l ≤ n − 1,

N′_{m′} = ∑_{k=0}^{l}(−1)^{k}\binom{n}{k}\binom{m′ − kh + n − 1}{n − 1}.

Replacing m′ by s + lh, with 0 ≤ s ≤ h − 1, we get

N′_{s+lh} = ∑_{k=0}^{l}(−1)^{k}\binom{n}{k}\binom{s + (l − k)h + n − 1}{n − 1}.

Therefore

∑_{m′}(N′_{m′})^{2} = ∑_{s=0}^{h−1} ∑_{l=0}^{n−1} ( ∑_{k=0}^{l}(−1)^{k}\binom{n}{k}\binom{s + (l − k)h + n − 1}{n − 1})^{2}

= ∑_{s=0}^{h−1} g_{n}(s, h).

It follows that

∑_{s=0}^{h−1} g_{n}(s, h) = h^{2n−1}c_{n} + O_{n}(h^{2n−2}).  (3.8)

Now, the main contribution in g_{n}(s, h) comes from the terms where the exponents of s and h add up to 2n − 2. Since for any 0 ≤ k ≤ 2n − 2,

∑_{s=0}^{h−1} s^{k} = \frac{1}{k + 1}h^{k+1} + O_{n}(h^{k}),

we obtain

∑_{s=0}^{h−1} g_{n}(s, h) = ∑_{s=0}^{h−1} (∑_{k=0}^{2n−2} a_{n,k}s^{k}h^{2n−2−k} + lower order terms)

= ∑_{k=0}^{2n−2} ∑_{s=0}^{h−1} a_{n,k}s^{k}h^{2n−2−k} + O_{n}(h^{2n−2})

= ∑_{k=0}^{2n−2} \frac{a_{n,k}}{k + 1}h^{2n−1} + O_{n}(h^{2n−2}).

By combining this with (3.8), we obtain the desired result. □

For n = 2, 3, 4, 5, 6, one finds that c_{2} = \frac{2}{3}, c_{3} = \frac{11}{20}, c_{4} = \frac{151}{315}, c_{5} = \frac{15619}{36288}, c_{6} = \frac{655177}{1663200}. The numerator and the denominator of c_{n} grow rapidly as n increases. For instance, for n = 10 and n = 25 we have

c_{10} = \frac{37307713155613}{121645100408832} ,

and

c_{25} = \frac{675361967823236555923456864701225753248337661154331976453}{3465993527260783822633915460520201577706853740052480000000} .

One can also work with boxes instead of cubes, and obtain similar distribution results. For example, in dimension two, we may consider the sum

S_{h,k}(x, y) = ∑_{u=x+1}^{x+h} ∑_{v=y+1}^{y+k} (\frac{u + v}{p} ) ,

where x, y are any integers and h, k are positive integers, with h ≥ k, say. Then, by using the same arguments as in the proof of Theorem 1, one can prove the following result.

Theorem 2. Let h, k be functions of p such that

h ≥ k, \frac{h}{k} → α, k → ∞, \frac{log k}{log p} → 0, as p → ∞.

Denote β = \sqrt{α − \frac{1}{3}} and β′ = \sqrt{1 − \frac{1}{3α}}. Let M_{p}(λ) be the number of pairs (x, y) with

0 ≤ x, y < p, x, y integers, such that S_{h,k}(x, y) ≤ λβk^{\frac{3}{2}} . Let M_{p}′(λ) be the number of pairs (x, y) with 0 ≤ x, y < p, x, y integers, such that S_{h,k}(x, y) ≤ λβ′h^{\frac{1}{2}} k. Then, as p → ∞,

\frac{1}{p^{2}} M_{p}(λ) → \frac{1}{\sqrt{2π}} ∫_{−∞}^{λ} e^{− \frac{1}{2} x^{2}}dx,

and

\frac{1}{p^{2}} M_{p}′(λ) → \frac{1}{\sqrt{2π}} ∫_{−∞}^{λ} e^{− \frac{1}{2} x^{2}}dx.

We remark that when h is much larger than k, S_{h,k}(x, y) is close to k times the 1dimensional sum S_{h}(x + y). Also, in this case α is large, β′ is close to 1, and the above statement for M_{p}′(λ) approaches the 1-dimensional result of Davenport and Erdős. Note also that in case α = 1, we have β = \sqrt{2/3} = \sqrt{c_{2}} , and the statement of Theorem 2 for M_{p}(λ) coincides with that of Theorem 1 for n = 2.

References

[1] N. C. Ankeny, The least quadratic nonresidue, Ann. of Math. (2) 55 (1952), 65–72.

[2] D. A. Burgess, On character sums and L-series. II, Proc. London Math. Soc. (3) 13 (1963), 524–536.

[3] F. R. K. Chung, Several generalizations of Weil sums, J. Number Theory 49 (1994), 95–106.

[4] H. Davenport, On a principle of Lipschitz, J. London Math. Soc. 26 (1951), 179–183.

[5] H. Davenport and P. Erdős, The distribution of quadratic and higher residues, Publ. Math. Debrecen 2 (1952), 252–265.

[6] W. Feller, An Introduction to Probalility Theory and Its Applications, Vol. 2, 2nd edition, Wiley, New York, 1971.

[7] H. L. Montgomery and R. C. Vaughan, Exponential sums with multiplicative coefficients, Invent. Math. 43 (1977), 69–82.

[8] G. Pólya, Uber die verteilung der quadratischen Reste und Nichtreste, Nachrichten K. Ges. Wiss. Göttingen (1918), 21–29.

[9] J. A. Shohat and J. D. Tamarkin, The Problem of Moments, Math. Surveys No. 1, Amer. Math. Soc., New York, 1943.

[10] I. M. Vinogradov, Sur la distribution des résidus et des non-résidus des puissances, J. Phys.-Math. Soc. Perm. 1 (1919), 94–98.

[11] A. Weil, On some exponential sums, Proc. Natl. Acad. Sci. USA 34 (1948), 204–207.

2000 Mathematics Subject Classification: Primary 11T99; Secondary 11A15. Keywords: Legendre symbol, normal distribution.

Received February 24, 2003; revised version received June 16, 2003. Published in Journal of Integer Sequences, July 9, 2003.

Return to Journal of Integer Sequences home page.