\documentclass[12pt,reqno]{amsart}

\usepackage[usenames]{color}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\usepackage{amssymb}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem*{main}{Main~Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}

\theoremstyle{definition}
\newtheorem{definition}{Definition}

\theoremstyle{remark}
\newtheorem*{notation}{Notation}

\numberwithin{equation}{section}
\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm {\LARGE\bf A multidimensional version of a result of \\
\vskip .5cm Davenport-Erd\H{o}s}
\vskip 1cm
\large
O-Yeat Chan, Geumlan Choi, and Alexandru Zaharescu\\
Department of Mathematics\\
University of Illinois \\
1409 West Green Street\\
Urbana, IL 61801\\
USA \\
\href{mailto:ochan@math.uiuc.edu}{ochan@math.uiuc.edu}\\
\href{mailto:g-choi1@math.uiuc.edu}{g-choi1@math.uiuc.edu}\\
\href{mailto:zaharesc@math.uiuc.edu}{zaharesc@math.uiuc.edu}
\end{center}

\vskip .5in

\begin{center}
{\bf Abstract}
\end{center}

Davenport and Erd\H{o}s showed that the distribution of values
of sums of the form
\begin{equation*}
S_h(x)=\sum_{m=x+1}^{x+h} \left(\frac mp \right),
\end{equation*}
where $p$ is a prime and $\left(\frac mp \right)$ is
the Legendre symbol, is normal as $h, p\to\infty$ such
that $\frac{\log h}{\log p}\to 0$. We prove a similar
result for sums of the form
\begin{equation*}
S_h(x_1, \ldots, x_n)=\sum_{z_1=x_1+1}^{x_1+h} \cdots
\sum_{z_n=x_n+1}^{x_n+h} \left( \frac {z_1+ \cdots+z_n}{p}
\right).
\end{equation*}

\vskip .5in

\section{Introduction}\label{sec1}

Given a prime number $p$, an integer $x$ and a positive integer $h$,
we consider the sum
\[
S_h(x)=\sum_{m=x+1}^{x+h} \left(\frac mp \right),
\]
where here and in what follows $\left(\frac mp \right)$ 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\' olya-Vinogradov (see ~\cite{P}, ~\cite{V}) shows that
$S_h(x)=O(\sqrt p\log p)$, and assuming the Generalized
Riemann Hypothesis, Montgomery and Vaughan ~\cite{MV} proved
that $S_h(x)=O(\sqrt p\log\log p)$.
The results of Burgess ~\cite{B} 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^{\epsilon}$, for fixed $\epsilon>0$ and $p$ large.
This would imply the well-known hypothesis of Vinogradov
that the smallest positive quadratic nonresidue mod $p$
is $<p^{\epsilon}$, for any fixed $\epsilon>0$ and $p$ large
enough in terms of $\epsilon$. We mention that Ankeny ~\cite{A}
showed that assuming the Generalized Riemann Hypothesis,
the smallest positive quadratic nonresidue mod $p$ is
$O(\log^2p)$. It is much easier to obtain cancellation,
even square root cancellation, if one averages $S_h(x)$
over $x$. In fact, Davenport and Erd\H{o}s~\cite{DE}
entirely solved the problem of the distribution of values
of $S_h(x)$, $0\leq x<p$, as $h,p\to\infty$ such that
$\frac{\log h}{\log p}\to 0$. Under these growth conditions
they showed that the distribution becomes normal. Precisely,
they proved that
\[
\frac 1p M_p(\lambda) \to \frac {1}{\sqrt {2 \pi}}
\int_{-\infty}^{\lambda} e^{-\frac 12t^2}dt, \quad \text{as $p \to
\infty$},
\]
where $M_p(\lambda)$ is the number of integers $x$, $0 \le x <p$,
satisfying $S_h(x) \le \lambda h^{\frac 12}$.
\par
For a fixed $n\geq 2$, we consider multidimensional sums of the form
\begin{equation} \label{eq:1-1}
S_h(x_1, \ldots, x_n)=\sum_{z_1=x_1+1}^{x_1+h} \cdots
\sum_{z_n=x_n+1}^{x_n+h} \left( \frac {z_1+ \cdots+z_n}{p}
\right),
\end{equation}
where $p$ is a prime number,
$x_1, \ldots, x_n$ are integer numbers, and $h$ is a positive
integer. Upper bounds for individual sums of this type
have been provided by Chung~\cite{C}. In
this paper we investigate the distribution of values of
these sums, and obtain a result similar to that of
Davenport and Erd\H{o}s.
Let
\begin{equation}\label{eq:1-2}
c_n: =\int_0^n f(t)^2 dt,
\end{equation}
where $f(t)$ is the volume of the region in
$\mathbb R^{n-1}$ defined by
\[ \{(a_1,\dots,a_{n-1})\in\mathbb R^{n-1} : 0 < a_i \le 1,
\; i=1, \ldots ,n-1; \; t-1 \le a_1 + \cdots + 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}(\lambda)$ be the
number of lattice points $(x_1, \ldots, x_n)$ with $0 \le x_1,
\ldots, x_n< p$, such that
\[
S_h(x_1, \ldots, x_n) \le \lambda c_n^{\frac 12}h^{n-\frac 12}.
\]
Then we show that as $h, p\to \infty$ such that
$\frac {\log h}{\log p} \to 0$, one has
\[
\frac {1}{p^n} M_{n, p}( \lambda) \to \frac {1}{\sqrt {2 \pi}}
\int_{-\infty}^{\lambda} e^{-\frac {t^2}{2}} dt.
\]


\section{Estimating the moments}\label{sec2}
We now proceed to estimate higher moments of our sums $S_h(x_1,
\ldots, x_n)$.

\begin{lemma}\label{lem1}
Let $p$ be a prime number and let $h$ and $r$ be positive
integers. Then
\begin{multline}\label{eq:2-1}
\sum_{x_1, \ldots, x_n {\rm (mod}\; p{\rm )}} S_h^{2r}(x_1, \ldots, x_n) =1
\cdot 3 \cdots (2r-3)(2r-1)\\ \cdot \left( c_nh^{2n-1}+O_{n,
r}(h^{2n-2}) \right)^r \left(p^n+O_r(p^{n-1}) \right)
+O_r\left(h^{2nr}p^{n-\frac 12} \right),
\end{multline}
and
\begin{equation}\label{eq:2-2}
\sum_{x_1, \ldots, x_n {\rm (mod}\; p{\rm)}} S_h^{2r-1}(x_1, \ldots, x_n)=O_r
\left( h^{n(2r-1)}p^{n-\frac 12} \right).
\end{equation}

\end{lemma}

\begin{proof}
Consider first the case when the exponent is $2r$. We have
\[
S_h(x_1, \ldots, x_n)=\sum_{a_1=1}^h \cdots \sum_{a_n=1}^h \left(
\frac {x_1+ \cdots +x_n+a_1+ \cdots +a_n}{p} \right).
\]
Therefore
\begin{multline*}
S_h^{2r}(x_1, \ldots, x_n)= \\ \sum_{a_{1, 1}=1}^h \cdots \sum_{a_{n,
1}=1}^h \cdots \sum_{a_{1, 2r}=1}^h \cdots \sum_{a_{n, 2r}=1}^h
\left( \tfrac {(x_1+ \cdots+x_n+a_{1, 1}+ \cdots +a_{n, 1}) \cdots
(x_1+ \cdots+ x_n+a_{1, 2r}+ \cdots +a_{n, 2r})}{p} \right)
\end{multline*}
and so
\begin{multline*}
\sum_{x_1, \ldots, x_n \text{(mod $p$)}} S_h^{2r}(x_1, \ldots, ,x_n)\\
= \sum_{\substack {a_{i,j}=1 \\ 1 \le i \le n \\ 1 \le j \le
2r}}^h \sum_{\ \ \  x_1, \ldots, x_n \text{(mod $p$)}} \left(
\tfrac {(x_1+ \cdots+x_n+a_{1, 1}+ \cdots +a_{n, 1}) \cdots (x_1+
\cdots+ x_n+a_{1, 2r}+ \cdots +a_{n, 2r})}{p} \right).
\end{multline*}

Divide the sets of $n$-tuples $\{(a_{1, i}, \ldots, a_{n, i}) : i=1,
\ldots, 2r \}$ into two types. If there exists an $i$ such that
the number of $j\in\{1,\dots,2r\}$ for which $a_{1, i}+ \cdots
+a_{n, i}=a_{1, j}+ \cdots +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, \ldots, x_n$, the
product $(x_1+\cdots+x_n+a_{1, 1}+ \cdots +a_{n, 1}) \cdots (x_1+
\cdots+ x_n+a_{1, 2r}+ \cdots +a_{n, 2r})$, as a polynomial in
$x_1$, is not congruent mod $p$ to the square of another
polynomial, by Weil's bounds~\cite{W1} we have
\begin{align*}
\sum_{x_2, \ldots, x_n \text{(mod $p$)}} &\sum_{\ \ x_1 \text{(mod
$p$)}} \left( \tfrac {(x_1+ \cdots+x_n+a_{1, 1}+ \cdots +a_{n, 1})
\cdots (x_1+\cdots
+x_n+a_{1, 2r}+ \cdots+a_{n, 2r})}{p} \right)\\
&=\sum_{\ \ \ x_2, \cdots, x_n \text{(mod
$p$)}}O_r(p^{1/2})=O_r(p^{n-\frac 12}).
\end{align*}
So the sum of terms of type $1$ is $O_r \left(h^{2nr}p^{n-\frac
12} \right)$. Now consider the sum of terms of type $2$. Since the
polynomial $(x_1+ \cdots +x_n+a_{1, 1}+ \cdots +a_{n, 1}) \cdots
(x_1+ \cdots +x_n+a_{1, 2r}+ \cdots +a_{n, 2r})$ is a perfect
square in this case, the Legendre symbol is $1$, except for those
values of $x_1,\dots,x_n$ for which this product vanishes mod $p$.
Since the product has at most $r$ distinct factors, for any values
of $x_2,\dots,x_n$ there are at most $r$ values of $x_1$ for which
the product vanishes mod $p$. Thus the sum over $x_1, \ldots, 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)\left(p^n+O_r(p^{n-1}) \right), \] where $F(h, n, r)$ is
the number of sets $\{(a_{1, i}, \ldots, a_{n, i}) : i=1, \ldots, 2r
\}$ yielding multinomials of type $2$, i.e., sets for which each
value of $a_{1, i}+ \cdots +a_{n, i}$ occurs an even number of
times, as $i$ runs over the set $\{1, 2, \ldots, 2r \}$. For any
integer $m$ with $n \le m\le nh$, let $N_m(h, n)$ be the number of
$n$-tuples $(a_{1, i}, \ldots, a_{n, i})$ for which $1 \le a_{1,
i}, \ldots, a_{n, i} \le h$ and $a_{1, i}+\cdots+a_{n,i}=m$. Then
the number of pairs of $n$-tuples $(a_{1,  i}, \ldots, a_{n, i})$,
$(a_{1,  j}, \ldots, a_{n, j})$, with $a_{1, i}+ \cdots+a_{n,
i}=a_{1, j}+ \cdots+a_{n, j}$, is $\sum_{m} \left(N_m(h, n)
\right)^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 $\left( \sum_m N_m^2
\right)^r$, and the number of ways to arrange these pairs in $2r$
places is $(2r-1)(2r-3) \cdots 3 \cdot 1$. Hence,
\[
F(h, n, r) \le 1 \cdot 3 \cdots (2r-3)(2r-1) \left( \sum_m N_m^2
\right)^r.
\]
On the other hand, the number of ways of choosing $r$ pairs of
distinct sums is at least
\begin{align*}
 \left(\sum_m N_m^2 \right)
&\left(\sum_m N_m^2- \max_m \{ N_m^2 \} \right) \cdots \left(
\sum_m N_m^2-(r-1) \max_m \{N_m^2 \} \right) \\
\quad &\ge \left(\sum_m N_m^2-r \max_m \{ N_m^2 \} \right)^r,
\end{align*}
and the number of different ways to arrange them in $2r$ places is
$(2r-1)(2r-3) \cdots 3 \cdot 1$. Thus
\begin{multline*}
1 \cdot 3 \cdots (2r-3)(2r-1) \left( \sum_m N_m^2-r \max_m {N_m^2}
\right)^r \le F(h, n, r) \\
\le 1 \cdot 3 \cdots (2r-3)(2r-1) \left(\sum_m N_m^2 \right)^r.
\end{multline*}
Next, we estimate the number
$N_m(h,  n)=N_m$. It is clear that for any $m$ with
$0<m\leq nh$, $N_m$ is the number of lattice
points in the region $R_m$ in $\mathbb R^{n-1}$ given by
\[
R_m:= \begin{cases} 0 <a_i \le h, \quad \text{for $i=1, \ldots, n-1$;} \\
m-h \le a_1+ \cdots +a_{n-1} < m.
\end{cases}
\]
We send the region $R_m$ to the unit cube in $\mathbb R^{n-1}$ via
the map $\mathbf x \mapsto \frac {\mathbf x}{h}$. Then we have
\[
\overline {R_m}:= \begin{cases} 0 <a_i \le 1, \quad \text{for $i=1,
\ldots, n-1$;} \\ \frac mh-1 \le a_1+ \cdots+ a_{n-1}< \frac mh.
\end{cases}
\]
By the Lipschitz principle ~\cite {D1} 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 mh)$. Then
\begin{align*}
\sum_{0<m \le nh} N_m^2 &= \sum_{0 <m \le nh} h^{2n-2} \left(f
\left(\frac mh \right) \right)^2+ \sum_{0 < m \le nh} O_n(h^{2n-3})\\
&=h^{2n-1} \sum_{0<m \le nh} \left( f \left(\frac mh \right)
\right)^2 \frac 1h
+O_n(h^{2n-2}) \\
&=h^{2n-1} \int_0^n \left(f(t) \right)^2dt+O_n(h^{2n-2}) \\
&=h^{2n-1}c_n+O_n(h^{2n-2}), \quad \text{as $h \to \infty$}.
\end{align*}
Hence
\[
F(h, n, r)=1 \cdot 3 \cdots (2r-3)(2r-1) \left(c_nh^{2n-1}+O_{n,
r}(h^{2n-2}) \right)^r,
\]
and ~\eqref{eq:2-1} follows. It is clear that ~\eqref{eq:2-2}
holds, since there are no sets of type $2$ in this case. This
completes the proof of the lemma.

\end{proof}



\section{Main results}\label{sec3}
By using the estimates for the higher moments of $S_h(x_1,
\ldots, x_n)$ given in Lemma~\ref{lem1}, we show that
under appropriate growth conditions on $h, p,$ the
distribution of our sums
$S_h(x_1, \ldots, x_n)$ is normal.
\begin{theorem}\label{th1}
Let $h$ be any function of $p$ such that
\begin{equation}\label{eq:3-1}
h \to \infty,\quad  \frac {\log h}{\log p} \to 0 \quad \text{as $p
\to \infty$.}
\end{equation}
Let $M_{n, p}(\lambda)$ denote the number of lattice points
$(x_1, \ldots, x_n)$, $0 \le x_1, \ldots, x_n <p$, such that
\[
S_h(x_1, \ldots, x_n) \le \lambda c_n^{\frac 12}h^{n-\frac 12},
\]
with $S_h(x_1, \ldots, x_n)$ defined by ~\eqref{eq:1-1}
and $c_n$ defined by ~\eqref{eq:1-2}.
Then
\[
\frac 1{p^n} M_{n,p}(\lambda) \to \frac {1}{\sqrt {2 \pi}}
\int_{-\infty}^{\lambda} e^{-\frac {t^2}{2}} dt, \quad \text{as $p
\to \infty$.}
\]
\end{theorem}

\begin{proof}
We consider the sum
\begin{equation}\label{eq:3-1.5}
\frac {1}{p^n} \sum_{x_1, \ldots, x_n  \text{(mod $p$)}}
\left(\frac {1}{c_n^{1/2}h^{n-1/2}}S_h(x_1, \ldots, x_n)
\right)^r.
\end{equation}
It follows from the above lemma that for each fixed $r$ and $n$,
if $r$ is even, then the quantity from $~\eqref{eq:3-1.5}$ is
\[
1 \cdot 3 \cdots (r-3)(r-1)\left(1+O_{n,
r}\left(\frac 1h \right) \right)^r \left(1+O_r\left(\frac 1p
\right) \right)+O_{n,r}(h^{\frac r2}p^{-\frac 12}),
\]
while if $r$ is odd, the quantity from $~\eqref{eq:3-1.5}$
is $O_{n,r}(h^{\frac r2}p^{-\frac 12})$.
Using ~\eqref{eq:3-1}, we have that for each positive integer $r$,
\begin{equation}\label{eq:3-2}
\frac {1}{p^n} \sum_{x_1, \ldots, x_n \text{(mod $p$)}}
\left(\frac {1}{c_n^{1/2}h^{n-1/2}}S_h(x_1, \ldots, x_n) \right)^r
\to \mu_r, \quad \text{as $p \to \infty$},
\end{equation}
where $\mu_r=\begin{cases} 1 \cdot 3 \cdots (r-1), & \text{if $r$
is even;} \\ 0, & \text{if $r$ is odd.}
\end{cases}$
\par \noindent
Let $N_{n, p}(s)$ be the number of $n$-tuples $(x_1, \ldots, x_n)$
with $0 \le x_i <p$, $i=1, \ldots, n$ such that $S_h(x_1, \ldots,
x_n) \le 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 \ge h^n$, and $M_{n, p}(\lambda)=N_{n,
p}(\lambda c_n^{\frac 12}h^{n-\frac 12})$.
We write ~\eqref{eq:3-2} in the form
\begin{equation}\label{eq:3-3}
\frac {1}{p^n} \sum_{s=-h^n}^{h^n} \left( \frac {s}{c_n^{\frac
12}h^{n-\frac 12}} \right)^r \left(N_{n, p}(s)-N_{n, p}(s-1)
\right) \to \mu_r, \quad \text{as $p \to \infty$}.
\end{equation}
This is similar to relation (26) of Davenport-Erd\H{o}s~\cite {DE}.
Following their argument, if we set
\[
\Phi_{n, p}(t)=\frac 1{p^n}N_{n, p}(tc_n^{\frac12}h^{n-\frac 12})
=\frac 1{p^n}M_{n, p}(t),
\]
and
\[
\Phi(t)=\frac{1}{\sqrt {2 \pi}} \int_{-\infty}^t e^{-\frac 12 u^2}du,
\]
we obtain
\begin{equation}\label{eq:3-2-0}
\int_{-\infty}^{\infty} t^r d \Phi_{n, p}(t) \to
\int_{-\infty}^{\infty} t^r d \Phi(t), \quad \text{as $p \to
\infty$},
\end{equation}
for any fixed positive integer $r$, which is the analogue of
relation (28) from ~\cite {DE}. It now remains to show that, for
each real number $\lambda$,
\begin{equation}\label{eq:3-2-1}
\Phi_{n, p}(\lambda) \to \Phi (\lambda), \quad \text{as $p \to
\infty$}.
\end{equation}
The assertion of ~\eqref{eq:3-2-1} follows from the well-known
fact (see ~\cite{F}) 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} \to m_r$
for all $r$ as $k \to \infty$, then $F_k \to F$ as $k \to \infty$.
We give the outline of the proof following the argument of
Davenport-Erd\H{o}s~\cite {DE}. Suppose that ~\eqref{eq:3-2-1}
fails for some $\lambda$. Then we can find a subsequence
$\{\Phi_{n, p^{\prime}} \}$ and a $\delta>0$ such that
\begin{equation}\label{eq:3-2-2}
\left|\Phi_{n, p^{\prime}}(\lambda)-\Phi(\lambda) \right| \ge
\delta, \quad \text{for all $p^{\prime}$}.
\end{equation}
By the two theorems of Helly (see the introduction to ~\cite{S})
there exists a subsequence $\{\Phi_{n, p^{\prime \prime}} \}$ of
$\{\Phi_{n, p^{\prime}} \}$ which converges to a distribution
$\Psi$ at every point of continuity, and
\[
\int_{-\infty}^{\infty}t^r d \Psi(t)=\lim_{p^{\prime \prime} \to
\infty }\int_{-\infty}^ {\infty} t^r d \Phi_{n, p^{\prime \prime}}
=\int_{-\infty}^{\infty} t^r d \Phi (t).
\]
Since $\Phi$ is the only distribution with these special moments
$\mu_1, \mu_2, \ldots$, we have $\Psi (t)= \Phi(t)$ for all $t$.
This contradicts ~\eqref{eq:3-2-2}. Hence one concludes that,
as $p \to \infty$,
\[
\frac 1{p^n} M_{n, p}(\lambda)=
\Phi_{n, p}( \lambda) \to
\Phi(\lambda)=\frac {1}{\sqrt {2 \pi}}
\int_{-\infty}^{\lambda}e^{-\frac 12 t^2} dt,
\]
which completes the proof of the theorem.
\end{proof}

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
\begin{equation*}
g_n(X,Y)=\sum_{l=0}^{n-1}\left(\sum_{k=0}^l (-1)^k {\binom
{n}{k}}{\binom {X+(l-k)Y+n-1}{n-1}}\right)^2.
\end{equation*}
Note that the total degree of $g_n(X,Y)$ is at most $2n-2$.
\begin{proposition}\label{pp1}
For any $n$,
\begin{equation*}
c_n = \sum_{k=0}^{2n-2} \frac{a_{n,k}}{k+1}\,,
\end{equation*}
where $a_{n,k}$ is the coefficient of $X^{k}Y^{2n-2-k}$
in $g_n(X,Y)$.
\end{proposition}

\begin{proof}
We know that for fixed $n$ and $h\to\infty$,
\begin{equation*}
\sum_{m} N_m^2 = h^{2n-1}c_n+O_n(h^{2n-2}),
\end{equation*}
where $N_m=N_m(h,n)$ is the number of
$n$-tuples $(a_1,\dots,a_n)$ such that $a_1+\cdots +a_n=m$, with
$1\leq a_i \leq h$.
Replacing $m$ by $m^\prime=m-n$ and each $a_i$ by
$b_i=a_i-1$, we get $\sum_m N_m^2 =
\sum_{m^\prime} (N^\prime_{m^\prime})^2$, where
$N^\prime_{m^\prime}$ is the number of $n$-tuples
$(b_1,\dots,b_n)$ such that $b_1+\cdots+b_n=m^\prime$,
with $0\leq b_i \leq h-1$.

Now, the number of ways to obtain a sum of $m^\prime$ from $n$
non-negative integers, with no restrictions, is $\binom
{m^\prime+n-1}{n-1}$.  If we restrict any fixed $b_i$ to satisfy
the inequality $b_i\geq h$, then the number of ways drops to
$\binom {m^\prime-h+n-1}{n-1}$. If we restrict any two $b_i, b_j$
to satisfy $b_i, b_j \geq h$ then we have $\binom
{m^\prime-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^\prime_{m^\prime}=\sum_{0\leq k\leq m^\prime/h} (-1)^k {\binom
{n}{k}}{\binom {m^\prime-kh+n-1}{n-1}}.
\]
So we have, for $lh \leq m^\prime < (l+1)h$, $0\leq l \leq n-1$,
\[
N^\prime_{m^\prime} = \sum_{k=0}^l (-1)^k {\binom {n}{k}}{\binom
{m^\prime-kh+n-1}{n-1}}.
\]
Replacing $m^\prime$ by $s+lh$, with $0\leq s\leq h-1$,
we get
\[
N^\prime_{s+lh} = \sum_{k=0}^l (-1)^k {\binom {n}{k}}{\binom
{s+(l-k)h+n-1}{n-1}}.
\]
Therefore
\[
\sum_{m^\prime} (N^\prime_{m^\prime})^2 = \sum_{s=0}^{h-1}
\sum_{l=0}^{n-1}\bigg(\sum_{k=0}^l (-1)^k {\binom {n}{k}}{\binom
{s+(l-k)h+n-1}{n-1}}\bigg)^2
\]
\[=\sum_{s=0}^{h-1} g_n(s,h).\]
It follows that
\begin{equation}\label{AB1}
\sum_{s=0}^{h-1} g_n(s,h)=h^{2n-1}c_n+O_n(h^{2n-2}).
\end{equation}
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\leq k\leq 2n-2$,
\[
\sum_{s=0}^{h-1} s^k =
\frac{1}{k+1}h^{k+1}+O_n(h^k),
\]
we obtain
\begin{align*}
\sum_{s=0}^{h-1} g_n(s,h) &=
\sum_{s=0}^{h-1} \left(\sum_{k=0}^{2n-2} a_{n,k}s^kh^{2n-2-k} +
\text{lower order terms} \right)\\
&=\sum_{k=0}^{2n-2} \sum_{s=0}^{h-1}a_{n,k}s^kh^{2n-2-k} +
O_n(h^{2n-2})\\
&=\sum_{k=0}^{2n-2}\frac{a_{n,k}}{k+1}h^{2n-1} + O_n(h^{2n-2}).
\end{align*}
By combining this with (\ref{AB1}),
we obtain the  desired result.
\end{proof}

For $n=2, 3, 4, 5, 6$, one finds that $c_2=\frac 23$,
$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
\begin{equation*}
c_{10}=\frac{37307713155613}{121645100408832}\,,
\end{equation*}
and
\begin{equation*}
c_{25}=\frac{675361967823236555923456864701225753248337661154331976453}
{34659935272607838226339154
60520201577706853740052480000000}\,.
\end{equation*}
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)=\sum_{u=x+1}^{x+h} \sum_{v=y+1}^{y+k} \left( \frac
{u+v}{p} \right),
\]
where $x$,  $y$ are any integers and $h$, $k$ are positive integers,
with $h \ge k$, say. Then, by using the same arguments as in the
proof of Theorem~\ref{th1}, one can prove the following result.

\begin{theorem}\label{th2}
Let $h$, $k$ be functions of $p$ such that
\[
h \ge k, \quad \frac hk \to \alpha, \quad k \to \infty,
\quad \frac {\log
k}{\log p} \to 0, \quad \text{as $p \to \infty$}.
\]
Denote $\beta=\sqrt {\alpha-\frac 13}$ and $\beta^{\prime}=\sqrt
{1-\frac 1{3 \alpha}}$. Let $M_p(\lambda)$ be the number of pairs
$(x, y)$ with $0 \le x, y <p$, $x$, $y$ integers, such that $S_{h,
k}(x ,y) \le \lambda \beta k^{\frac 32}$. Let
${M_p}^{\prime}(\lambda)$ be the number of pairs
$(x, y)$ with $0 \le x, y <p$, $x$, $y$ integers, such that
$S_{h
,k}(x, y) \le \lambda {\beta}^{\prime}h^{\frac 12}k$. Then, as $p
\to \infty$,
\[
\frac 1{p^2} M_p(\lambda) \to \frac {1}{\sqrt {2 \pi}}
\int_{-\infty}^{\lambda} e^{-\frac 12 x^2} dx,
\]
and
\[
\frac 1{p^2} {M_p}^{\prime} (\lambda) \to \frac 1{\sqrt {2 \pi}}
\int_{-\infty}^{\lambda} e^{-\frac 12 x^2} dx. \]

\end{theorem}

We remark that when $h$ is much larger than $k$,
$S_{h,k}(x, y)$ is close to $k$ times the
$1$-dimensional sum $S_h(x+y)$. Also, in this case
$\alpha$ is large,
$\beta^{\prime}$ is close to $1$, and the above statement for
${M_p}{\prime}(\lambda)$ approaches the $1$-dimensional result
of Davenport and Erd\H{o}s. Note also that in case
$\alpha=1$, we have $\beta=\sqrt{2/3}=\sqrt{c_2}$ , and the statement
of Theorem ~\ref{th2} for ${M_p}(\lambda)$ coincides
with that of Theorem~\ref{th1} for $n=2$.


\begin{thebibliography}{99}

\bibitem{A}
N. C. Ankeny, {The least quadratic nonresidue}, \emph{Ann. of
Math.} (2) {\bf 55} (1952), 65--72.

\bibitem{B}
D. A. Burgess, {On character sums and L-series. II}, \emph{Proc.
London Math. Soc.} (3) {\bf 13} (1963), 524--536.

\bibitem{C}
F. R. K. Chung, {Several generalizations of Weil sums}, \emph{J.
Number Theory} {\bf 49} (1994), 95--106.

\bibitem{D1}
H. Davenport, {On a principle of Lipschitz}, \emph{J. London Math.
Soc.} {\bf 26} (1951), 179--183.

\bibitem{DE}
H. Davenport and P. Erd\H{o}s, {The distribution of quadratic and
higher residues}, \emph{Publ.\ Math.\ Debrecen} {\bf 2} (1952),
252--265.

\bibitem{F}
W.\ Feller, \emph{An Introduction to Probalility Theory and Its
Applications}, Vol. 2, 2nd edition, Wiley, New York,  1971.


\bibitem{MV}
H. L. Montgomery and R. C. Vaughan, {Exponential sums with
multiplicative coefficients}, \emph{Invent. Math. } {\bf 43}
(1977), 69--82.

\bibitem{P}
G. P\' olya, {Uber die verteilung der quadratischen Reste und
Nichtreste}, \emph{ Nachrichten K. Ges. Wiss. G\" ottingen}
(1918), 21--29.

\bibitem{S}
J.\ A.\ Shohat and J.\ D.\ Tamarkin, \emph{The Problem of Moments},
Math.\ Surveys No. 1, Amer.\ Math.\ Soc., New York, 1943.

\bibitem{V}
I. M. Vinogradov, {Sur la distribution des r\' esidus et des
non-r\' esidus des puissances}, \emph{J. Phys.-Math. Soc. Perm.}
{\bf 1} (1919), 94--98.

\bibitem{W1}
A.\ Weil, {On some exponential sums}, \emph{Proc.\ Natl.\ Acad.\
Sci.\ USA} {\bf 34} (1948), 204--207.




\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11T99; Secondary 11A15.

\noindent \emph{Keywords:  Legendre symbol, normal distribution.}


\bigskip
\hrule
\bigskip


\vspace*{+.1in}
\noindent
Received February 24, 2003;
revised version received  June 16, 2003.
Published in {\it Journal of Integer Sequences},
July 9, 2003.
\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.
\vskip .1in



\end{document}