.de HX
.if \\$1=3 .ds }0
..
.fp 4 M2 UnivMath2
.fp 5 M6 UnivMath6
.fp 6 M3 UnivMath3
.nr Pt 1
.EQ
delim $$
gsize 11
define int0 % size +6 {bold {font M3 "\N'36'"}} %
define RR % font M6 R %
define ZZ % font M6 Z %
define CC % font M6 C %
define lpar % "\b'\(lt\(lb'" %
define rpar % "\b'\(rt\(rb'" %
define dd % "..." %
define ge % ^>=^ %
define le % ^<=^ %
define spr % sup prime %
define sst % sup star %
define as % a sub %
define bs % b sub %
define mem % member %
define smf % sum from %
define zs % z sub %
define GA % GAMMA %
define cs % c sub %
define ss % s sub %
define pt % partial %
define Ns % N sub %
define ws % w sub %
define us % u sub %
define Vs % V sub %
define th % theta %
define ths % theta sub %
define bx % bold x %
define bz % bold z %
define xs % x sub %
define af % alpha %
define afs % alpha sub %
.EN
.S 11
.am DE
.ls 2
.sp
..
.ds HP 11 11 11 11 11 11 11
.ds HF 3 3 3 3 3 3 3
.TL
Lattice Points in High-Dimensional Spheres
.AU "J. E. Mazo" JEM MH 11217
.AU "A. M. Odlyzko" AMO MH 11218 7286 2C-355
.AS 1
.ls 2
.P
Let $N( bx ,^n,^af )$ denote the number of integer lattice points inside the $n$-dimensional sphere of radius $( af n ) sup 1/2$ with center at $bx$.
This number $N( bx ,^n,^af )$ is studied for $af$ fixed, $n^->^inf$, and $bold x$ varying.
The average value (as $bx$ varies) of $N( bx ,^n,^af )$ is just the volume of the sphere,
which is roughly of the form $( 2 pi e af ) sup n/2$.
It is shown that the maximal and minimal values of $N( bx ,^n,^af )$ differ from the average by
factors exponential in $n$,
which is in contrast to the usual lattice point problems in bounded dimensions.
This lattice point problem arose separately in universal quantization and in low density
subset sum problems.
.ls 1
.AE
.MT 4
.ls 2
.H 1 "Introduction"
A general principle, dating back to Gauss, that is widely used in estimating the number of integer lattice points in nice sets
$S$ in $RR sup n$ is that this number equals the volume of $S$ with a small error term [4,5,13].
This approach is very useful, and can be proved to be rigorous, for example, if one
considers the number of lattice points in sets $rT$, where the dimension $n$ is fixed, $T$ is a given nice set, and $r^->^inf$.
However, we will show below that this principle fails completely if one considers the dimension $n^->^inf$, and the sets $S$ to be spheres of radii proportional to $n sup 1/2$.
That this general principle cannot be justified rigorously in this case
is not surprising, since (i)\ the surface area of the
sphere of radius $( af n ) sup 1/2$ is larger than the volume by a factor of $(n/ af ) sup 1/2$, and (ii)\ the diameter of the unit cube is comparable to the diameter of the sphere.
However, it is rather interesting that it is not
just the proof, but the principle itself, that fails.
.P
At the end of this section we will mention some applications of our results.
At this point we remark that the problem of estimating the number of lattice points in an $n$-dimensional sphere is in some ways most delicate when the
radius $r= ( af n ) sup 1/2$ for a constant $alpha$.
If $r^<=^n sup {1/2- epsilon}$ for some fixed $epsilon ^>^0$, then for most
locations of the center of the sphere, there will be no lattice points inside it.
If $r ^>=^n sup {1/2 + epsilon}$, then it can be shown by methods similar to those of this paper
that the classical principle does apply, and the number of lattice points inside the sphere is asymptotic to the volume, no matter where the center is located.
.P
For $bx = ( xs 1 ,^dd ,^xs n )^mem^RR sup n$, and $af ^>^0$,
let $S( bx ,^n,^af )$ denote the $n$-dimensional sphere of radius $( af n ) sup 1/2$ centered at $bx$,
.DS 2
.EQ (1.1)
S( bx ,^n,^af ) ~=~ left {
bold z ^mem^RR sup n ^:~ sum from i=1 to n ^( zs i - xs i ) sup 2 ^<=^ af n right } ^.
.EN
.DE
Further, let $N( bx ,^n,^af )$ denote the number of lattice points in $S( bx ,^n,^af )$,
.DS 2
.EQ (1.2)
N ( bx ,^n,^af ) ~=~ left {
bold z^member^ZZ sup n ^:~ sum from i=1 to n ^( zs i - xs i ) sup 2 le af n right } ^.
.EN
.DE
We will study the dependence of $N( bx ,^n,^af )$ on
$bx$ for $af$ fixed and $n^->^inf$.
The average value of $N( bx ,^n,^af )$ as $bx$ runs over the unit cube
$0 le xs 1 ,^dd ,^xs n le 1$ is just the volume of the sphere
$S( bx ,^n,^af )$, which equals
.DS 2
.EQ (1.3)
{pi sup n/2 ( af n ) sup n/2} over {GA (n/2 +1 )} ~wig~
( pi n ) sup -1/2 ^(2 pi e af ) sup n/2
~~~roman {"as"}~~~
n^->^inf^.
.EN
.DE
.P
This paper shows that the maximal and minimal values of $N( bold x ,^n,^af )$,
as $bold x$ varies, differ from the mean value by multiplicative
factors of the form $exp ( cn )$, where $c$ is a constant depending
on $af$.
Table\ 1 shows the growth rates of $N( bold x ,^n,^af )$.
The entry labeled $lim^n sup -1 ^log ^( 1+ min ^N )$ denotes
.DS 2
.EQ
lim from {n^->^inf} ~ n sup -1 ^log ^lpar 1+ min from {bold x} ^N( bold x ,^n ,^af ) rpar ^,
.EN
.DE
for example.
Natural logarithms are used in the table, as in the rest of the paper.
The values in the table are all obtained by truncation, not rounding, so that $pi$, for example, might be represented as 3.141592.
Table\ 1 was computed using the estimates of Section\ 2, and the transcendental
equations that arise were solved numerically.
Table\ 1 shows that as $af ^->^inf$, the difference between the minimal and maximal values of $N ( bold x ,^n,^af )$ decreases, which was to be expected.
.P
The precise results are stated and proved in Section\ 2.
They give the (asymptotically) minimal and maximal values of $N( bold x ,^n,^af )$ to within multiplicative factors of $exp ( c sup prime n sup 1/2 )$, where $c sup prime$ is another constant depending on $af$.
(Section\ 3 mentions possible ways to improve on these estimates.)
The main terms in the asymptotic estimates come from solutions of certain transcendental equations.
.P
The results of Section\ 2 show that (at least to within multiplicative factors of $exp ( c spr n sup 1/2 )$) $N( bold x ,^n,^af )$ is maximized at $bold x = (0,^0,^dd ,^0 )$
and minimized at $bold x = ( 1/2 ,^1/2 ,^dd ,^1/2)$.
(Note that $N( ( 1/2 ,^dd ,^1/2 ) ,^n,^af ) = 0$ for any $af ^<^ 1/4$.)
While the best possible result is probably much better (perhaps with the maximum of $N( bold x ,^n,^af )$ only a constant
times $N((0,^dd ,^0) ,^n,^af )$, for example),
there are infinitely many values of $af$ for each $n$ for which
.DS 2
.EQ
max from {bold x} ~ N( bold x ,^n,^af ) ~>~ N ((0,^0,^dd ,^0) ,^n,^af ) ^.
.EN
.DE
To see this, fix $n$ and consider a sphere of radius $af$
centered at $(0,^0,^dd ,^0)$.
Increase $af$ until there are lattice points just outside the sphere.
If we now move the sphere, we will capture about half of those lattice points.
By using the very precise saddle-point estimate sketched in Section\ 3, it is possible to show
a stronger result, namely
that for any $0^<^c sub 1 ^<^c sub 2 ^<^inf$, there is a $delta ^>^0$ such that
.DS 2
.EQ
max from {bold x} ~ N ( bold x ,^n,^alpha sub n ) ^>^
(1+ delta ) N ( (0,^0,^dd ,^0) ,^n,^alpha sub n )
.EN
.DE
for a sequence of values $alpha sub n$, $n ^>=^n sub 0$, with
$c sub 1 ^<^ alpha sub n ^<^c sub n$.
.P
Most of the published works on lattice points have concentrated on the difference between the number of lattice points inside a sphere and the volume of the sphere as the radius of the sphere
increases and the dimension is held constant (see [5,7,13]
and the references given there).
Most of these results have also concentrated on spheres with centers at the origin.
The few papers we are aware of that deal with variable centers also consider
fixed dimensions and radii going to infinity [1,3,12,15].
.P
The main results of this paper were obtained in 1982, prompted by a question posed by J.\ Ziv in connection with his work on universal quantization [16].
(Our results could be used to obtain another proof of his main technical results.)
Afterwards, similar problems turned up in connection with an algorithm for solving
low-density subset-sum problems [9], where a crucial
role in evaluating the performance of the algorithm is played by an estimate for $N(( 0,^dd ,^0),^n,^af )$.
This same estimate is also used in [6], which presents a simplified analysis of the algorithm of [9].
.H 1 "Main results and proofs"
We define
.DS 2
.EQ (2.1)
f(s,^y) ~=~ sum from {k=- inf} to inf ~
e sup {- s(k-y) sup 2} , ~~~
y^member^RR , ~~~s^member^CC , ~~~roman Re ^(s) ^>^0 ^.
.EN
.DE
Our results will be phrased in terms of $f(s,^y)$.
In the standard terminology of theta functions [2,14] we have
.DS 3
.EQ (2.2)
f(s,^y) mark ~=~ e sup {- sy sup 2} ^theta sub 3 ( iys ,^is / pi ) ^,
.EN
.sp .5
.nr Eq 1
.EQ where
~~
.EN
.sp .5
.nr Eq 0
.EQ (2.3)
theta sub 3 (z,^t) lineup ~=~ sum from {k= - inf} to inf ~ e sup {pi it k sup 2} ^cos ^(2k z ) ^,
.EN
.DE
a result that will be used extensively, since it will allow us to utilize a
variety of results about theta functions.
(See [10] for other recent applications of classical theta function results.)
.P
We next define $F(s) = F( xs 1 ,^dd ,^xs n ,^s )$ by
.DS 2
.EQ (2.4)
F(s) ~=~ prod from j=1 to n ~ f(s,^xs j ) ^.
.EN
.DE
By (2.1), we have
.DS 2
.EQ (2.5)
F(s) ~=~ sum from r ~ Ns r ^e sup -sr ^,
.EN
.DE
where $Ns r = Ns r ( bx ,^n )$ is the number of lattice points at distance $r sup 1/2$ from $bold x$, and
$r$ runs over all the (countably many) nonnegative values that can occur this way.
We first obtain a very easy upper bound.
.H 3 "Lemma 1."
.I
For any $s^member^RR sup +$,
.DS 2
.EQ (2.6)
N( bx ,^n,^af ) ~<=~ e sup {s af n} ~ prod from j=1 to n ~ f(s,^xs j ) ^.
.EN
.DE
.R
.H 3 "Proof."
By (2.4) and (2.5), we have
.DS 3
.EQ
e sup {s af n} ~ prod from j=1 to n ~ f(s ,^xs j ) mark ~=~ sum from r~
Ns r ^e sup {s( af n -r)}
.EN
.sp
.EQ
lineup ~>=~ sum from {r le af n} ~Ns r ~=~ N( bx ,^n,^af ) ^,
.EN
.DE
which is the desired result.
.br
.ta 6iR
.sp -2
	$blot$
.P
The bound of Lemma\ 1 is optimized by choosing $s$ appropriately.
We next show that there is basically a unique best choice for $s$.
We let $||y ||$ denote the distance from $y$ to the nearest integer,
.DS 2
.EQ
|| y || ~=~ min from k ~ |y - k | ~,
.EN
.DE
and note that
.DS 2
.EQ (2.7)
N(( xs 1 ,^dd ,^xs n ) , ^n,^af )~=~
N(( || xs 1 || ^,~dd ,^|| xs n || ) , ^n,^af ) ^.
.EN
.DE
.H 3 "Lemma 2."
.I
For $y^member^RR$, let $g(s) = f(s,^y)$.
Then for all $s^member^RR sup +$,
.DS 3
.EQ (2.8)
g(s) mark ~>~ 0 ^,
.EN
.sp
.EQ (2.9)
{g spr} over g (s) lineup ~<~ 0 ^,
.EN
.sp
.EQ (2.10)
lpar {g spr} over g rpar sup {"" sup "" sup "" sup {size +8 prime}} (s) lineup ~>~ 0 ^,
.EN
.DE
and
.DS 3
.EQ (2.11)
{g spr} over g (s) mark ~->~ -^inf ~~~a s ~~~ s ^->^0 sup +^,
.EN
.sp
.EQ (2.12)
{g spr} over g (s) lineup ~->~ - ^|| y || sup {2} ~~~ a s ~~~
s ^->^inf ^.
.EN
.DE
Furthermore, for any constants $0^<^cs 1 ^<^cs 2 ^<^inf$, there is a constant $cs 3 ^>^0$ depending on $cs 1$ and $cs 2$ only, but not on $y$, such that for $cs 1 le s le cs 2$,
.DS 2
.EQ (2.13)
lpar {g spr} over g rpar sup {"" sup "" sup "" sup {size +8 prime}} (s)~>=~ cs 3 ^.
.EN
.DE
Also, $g(s)$, $( g spr / g ) (s)$, $( g sup prime / g ) sup prime (s)$, and $( g sup prime / g ) sup {prime prime} (s)$ are all bounded for $cs 1 le s le cs 2$
by constants independent of $y$.
.R
.H 3 "Proof."
Inequalities (2.8) and (2.9) are obvious from
the definition (2.1) of $g(s) = f(s,^y)$.
To prove (2.10), note that we need to prove
.DS 2
.EQ
g sup {prime prime} (s) g(s) ~>~ (g spr (s)) sup 2 ^,
.EN
.DE
which is equivalent to
.DS 3
.EQ
left ( sum from k ^(k-y) sup 4 ^mark e sup {-s(k-y) sup 2} right )
left ( sum from m ^e sup {-s(m-y) sup 2} right )
.EN
.sp .3
.EQ (2.14)
~~
.EN
.sp .3
.EQ
lineup >~ left ( sum from k ^(k-y) sup 2 e sup {-s(k-y) sup 2} right ) sup 2 ^.
.EN
.DE
However, (2.14) follows by the Cauchy-Schwarz inequality,
with strict inequality holding because the terms in the sums cannot be proportional.
In fact, if we use the identity
.DS 2
.EQ (2.15)
2 ^sum from i ^as i sup 2 ^sum from j ^bs j sup 2 ^-^ 2 left ( sum from i ^as i bs i right ) sup 2 ~=~
sum from i,j ^( as i bs j - as j bs i ) sup 2 ^,
.EN
.DE
we see that for $0 ^<^cs 1 le s le cs 2 ^<^inf$,
.DS 2
.EQ (2.16)
g sup {prime prime} (s) g(s) ~>~ (g spr (s)) sup 2 ^+^eta
.EN
.DE
for some $eta = eta ( cs 1 ,^cs 2 ) ^>^0$ that does not depend on $y$, and this (together
with the trivial boundedness claims in the last section of the lemma)
establishes (2.13)
for some effectively computable constant $c sub 3$.
(To simply prove the existence of $c sub 3$, we can use a compactness argument.)
.P
This limit (2.11) follows from comparing the series for $g spr (s)$ and $g(s)$, while (2.12)
follows by noting that only the leading
terms in the series for $g spr (s)$ and $g(s)$ are involved in determining the asymptotic behavior as $s^->^inf$.
.br
.ta 6iR
.sp -2
	$blot$
.P
We now proceed to prove our main results.
Note that as $s^->^inf$,
.DS 2
.EQ (2.17)
f(s,^y) ~wig~
left {
matrix {
ccol {1 above e sup {- s || y || sup {2}} above 2 e sup -s/4}
lcol {~~roman if above ~~roman if above ~~roman if}
lcol {~~|| y ||^=^0 , above~~ 0^<^|| y || ^<^ 1/2 , above ~~|| y ||^=^ 1/2 .}
}
.EN
.DE
Therefore if
.DS 2
.EQ (2.18)
sum from j=1 to n ~ || xs j || sup {2} ~>~ af n ^,
.EN
.DE
then Lemma\ 1 implies that $N( bx ,^n,^af ) = 0$.
This result is obvious anyway,
but it is interesting to see that it can be obtained by our analytic method.
.H 3 "Theorem 1."
.I
Suppose that $af$ and $delta$
are positive constants.
For any $bx = ( xs 1 ,^dd ,^xs n ) ^member^RR sup n$ that satisfies
.DS 2
.EQ (2.19)
af n ~>~ delta n ~+~ sum from j=1 to n ~ || xs j || sup {2}
.EN
.DE
there is a unique $s= s ( af ) = s ( af ;^bx )$ that satisfies
the equation
.DS 2
.EQ (2.20)
sum from j=1 to n ~ pt over {pt s} ~ log ~ f(s,^xs j ) ~+~ af n ~=~ 0 ^.
.EN
.DE
For this $s= s( af )$, we have
.DS 2
.EQ (2.21)
N( bx ,^n,^af ) ~<=~ e sup {s( af ) af n} ~ prod from j=1 to n ~
f(s( af ) ,^xs j )
.EN
.DE
and also
.DS 2
.EQ (2.22)
N( bx ,^n,^af )~>=~
e sup {s( af ) af n - cn sup 1/2} ~prod from j=1 to n ~ f(s( af ) ,^x sub j )
.EN
.DE
for a constant $c^>^0$ that depends only on $af$ and $delta$.
.R
.H 3 "Proof."
The existence and uniqueness of $s( af )$ follow from Lemma\ 2.
The upper bound (2.21) holds with any $s$,
not just $s( af )$, as we already noted in Lemma\ 1.
Thus it only remains to prove the lower bound (2.22).
.P
We choose
.DS 2
.EQ
0 ^<^ s sub 1 ^<^s sub 2 ^<^s sub 3 ~=~ s( af )
.EN
.DE
and define $afs k$, $1 le k le 3$, by
.DS 2
.EQ (2.23)
afs k ~=~ - ^ 1 over n ~ sum from j=1 to n ~ pt over {pt s} ~ log~ f(s sub k ,^xs j ) ^.
.EN
.DE
By Lemma\ 2, we have $afs 1 ^>^afs 2 ^>^afs 3 ^>^0$.
.P
We next let
$F(s)$ be defined by (2.4),
and consider
.DS 2
.EQ (2.24)
H ^=^ e sup {afs 2 s sub 2 n} F( s sub 2 ) ^-^e sup {afs 1 s sub 1 n} F( s sub 1 ) e sup {( afs 2 - afs 1 )s sub 2 n} ^-^ e sup {afs 3 s sub 3 n}
F( s sub 3 ) e sup {( afs 2 - afs 3 ) s sub 2 n} ^.
.EN
.DE
If we write
.DS 2
.EQ (2.25)
H ~=~ sum from r ~ N sub r ^ws r ^,
.EN
.DE
then we see that $ws r le 0$ for $r ge afs 1 n$, since
in that range
.DS 2
.EQ
afs 2 s sub 2 n ^-^ s sub 2 r ~<=~ afs 1 s sub 1 n ^-^ s sub 1 r ^+^ ( afs 2 - afs 1 ) s sub 2 n ^,
.EN
.DE
so just subtracting the second term on the right side in (2.25) from the first gives $ws r le 0$.
Similarly, we find $ws r le 0$ for $r le afs 3 n$.
Now for $afs 3 n ^<^r ^<^afs 1 n$,
.DS 2
.EQ (2.27)
ws r ~<=~ exp ( afs 2 s sub 2 n - s sub 2 r ) ~<=~ exp (( afs 2 - afs 3 ) s sub 2 n ) ^,
.EN
.DE
so
.DS 2
.EQ (2.28)
N( bx ,^n,^af ) ~>=~ H ^exp ( - ( afs 2 - afs 3 ) s sub 2 n ) ^.
.EN
.DE
Thus we basically have to prove that $H$ is positive and large.
.P
Let us consider
.DS 2
.EQ (2.29)
V sub 1 ~=~ afs 2 s sub 2 n ^+^log ^F( s sub 2 ) ^-^ afs 1 s sub 1 n ^-^log ^F( s sub 1 ) ^-^ ( afs 2 - afs 1 ) s sub 2 n ^.
.EN
.DE
By Lemma\ 2,
.DS 3
.EQ
log^F( s sub 1 ) ^=^log ^F(s sub 2 ) ^+^ ( s sub 1 - s sub 2 ) {F spr} over F (s sub 2 ) ^+^1 over 2 ( s sub 1 - s sub 2 ) sup 2
lpar {F spr} over F rpar sup {"" sup "" sup "" sup {size +8 prime}} ( s sub 2 ) ^+^ O ( n | s sub 1 - s sub 2 | sup {^3} ) ^,
.EN
.DE
where the constant implied by the $O$-notation depends only on $af$ and $delta$.
Also,
.DS 3
.EQ
afs 1 n mark ~=~ -^ {F spr} over F ( s sub 1 ) ^=^ - ^ {F spr} over F ( s sub 2 ) ^+^ ( s sub 2 - s sub 1 ) lpar {F spr} over F rpar sup {"" sup "" sup "" sup {size +8 prime}} (s sub 2 ) ^+^ O ( n | s sub 1 - s sub 2 | sup {^3} )
.EN
.sp
.EQ
lineup ~=~ afs 2 n ^+^ ( s sub 2 - s sub 1 ) lpar {F spr} over F rpar sup {"" sup "" sup "" sup {size +8 prime}} ( s sub 2 ) ^+^ O( n | s sub 1 - s sub 2 | sup {^3} ) ^.
.EN
.DE
Therefore
.DS 2
.EQ (2.30)
V sub 1 ~=~ 1 over 2 ( s sub 1 - s sub 2 ) sup 2^ lpar {F spr} over F rpar sup {"" sup "" sup "" sup {size +8 prime}} ( s sub 2 ) ^+^ O ( n | s sub 1 - s sub 2 | sup {^3} ) ^.
.EN
.DE
Similarly, if we let
.DS 2
.EQ (2.31)
V sub 3 ~=~ af sub 2 s sub 2 n ^+^ log ^F( s sub 2 ) ^-^ af sub 3 s sub 3 n ^-^ log^F ( s sub 3 ) ^-^ ( af sub 2 - af sub 3 ) s sub 2 n ^,
.EN
.DE
then we find that
.DS 2
.EQ (2.32)
V sub 3 ~=~ 1 over 2 ^(s sub 3 - s sub 2 ) sup 2 ^
lpar {F spr} over F rpar sup {"" sup "" sup "" sup {size +8 prime}} ( s sub 2 ) ^+^ O ( n |
s sub 3 - s sub 2 | sup {^3} ) ^.
.EN
.DE
Therefore, if we choose
.DS 3
.EQ
s sub 2 mark ~=~ s sub 3 ^-^ C ^n sup -1/2^,
.EN
.sp .25
.EQ (2.33)
~~
.EN
.sp .25
.EQ
s sub 1 lineup ~=~ s sub 3 ^-^ 2C ^n sup -1/2 ^,
.EN
.DE
for any $C^>^0$, then by Lemma\ 2 we will have
.DS 2
.EQ (2.34)
V sub 1 ,^V sub 3 ~>=~ C sup 2 sigma ^-^ O ( n sup -1/2 ) ~~~roman "as" ~~~
n ^->^inf
.EN
.DE
for some $sigma ^>^0$, and so if $C$ is chosen large enough, then for large $n$ we will have
.DS 2
.EQ (2.35)
V sub 1 ,^V sub 3 ~>=~ 2 ^,
.EN
.DE
and so
.DS 2
.EQ (2.36)
H ~>=~ 1 over 2 ~ e sup {af sub 2 s sub 2 n} F( s sub 2 ) ^,
.EN
.DE
which together with (2.28) proves (2.22),
since by the same arguments as were used to estimate $V sub 1$ and $V sub 3$,
.DS 2
.EQ (2.37)
af sub 2 s sub 2 n ^+^ log ^F ( s sub 2 ) ~>=~ af sub 3 s sub 3 n ^+^log ^F( s sub 3 ) ^-^ c spr n sup 1/2 ^.
.EN
.DE
This completes the proof of Theorem\ 1.
.br
.ta 6iR
.sp -2
	$blot$
.P
Theorem\ 1 determines $N( bold x ,^n,^alpha )$ to within a multiplicative factor of $exp ( cn sup 1/2 )$ for all $bold x$ if $alpha ^>^ 1/4$, and also for many
values of $bold x$
(in particular for $bold x ^=^ (0,^0,^dd ,^0)$) if $0^<^alpha le 1/4$.
However, the determination is in terms of solutions to complicated transcendental equations.
We next use the results of Theorem\ 1 to show that up to factors
of $exp ( cn sup 1/2 )$, $N( bold x ,^n,^ alpha )$ is maximized at
$bold x = (0,^0,^dd ,^0)$ and minimized at $bold x = (1/2 ,^1/2, ^dd ,^1/2 )$.
.H 3 "Theorem 2."
.I
For any $af ^>^0$, there is a constant $c spr ( af ) ^>^0$ such that for
all $bold x ^member^RR sup n$,
.DS 2
.EQ (2.38)
N( bold x ,^n,^af ) ~<=~ exp ( c spr ( af ) n sup 1/2 ) ^N ( bold x sub 0 ,^n ,^af ) ^,
.EN
.DE
where $bold x sub 0 = ( 0,^0,^dd ,^0 )$.
For any $af ^>^ 1/4$, there is a constant $c sup {prime prime} ( af ) ^>^0$ such that for all $bold x ^member^RR sup n$,
.DS 2
.EQ (2.39)
N ( bold x ,^n,^af ) ~>=~ exp ( - c sup {prime prime} ( af ) n sup 1/2 ) ^N( bold x sub 1 ,^n,^af ) ^,
.EN
.DE
where $bold x sub 1 = ( 1/2 ,^1/2 ,^dd ,^1/2 )$.
$($For $0^<^af ^<^1/4$, $N( bold x sub 1 ,^n,^af ) = 0$, so $(2.39)$ is trivially valid there also.$)$
.R
.H 3 "Proof."
By Eq.\ (2.2) and the fundamental transformation formula for theta functions
[2,14]
.DS 2
.EQ (2.40)
theta sub 3 (z,^t) ~=~ (- it ) sup -1/2 ^exp ( z sup 2 / ( pi it )) theta sub 3 ( z/t , ^- i/t ) ^,
.EN
.DE
we have, for any $s^member^RR sup +$,
.DS 3
.EQ
f(s,^y) mark ~=~ ( pi /s ) sup 1/2 ^theta sub 3 ( pi y ,^i pi /s )
.EN
.sp
.EQ
lineup ~=~ ( pi /s ) sup 1/2 ~sum from {k=- inf} to inf ~ exp ( - pi sup 2 k sup 2 / s ) ~roman cos^(2 ky pi )
.EN
.sp .2
.EQ (2.41)
~~
.EN
.sp .2
.EQ
lineup ~<=~ ( pi / s ) sup 1/2 ~ sum from {k= - inf} to inf ~ exp ( - pi sup 2 k sup 2 /s )
.EN
.sp
.EQ
lineup ~=~ f(s,^0) ^.
.EN
.DE
Therefore for any $s^>^0$, $af ^>^0$,
.DS 2
.EQ (2.42)
e sup {s af n} ^F ( x sub 1 ,^dd ,^x sub n ,^s ) le
e sup {s af n} ^F( 0,^dd ,^0,^s) ^,
.EN
.DE
and so by Lemma\ 1 and Theorem\ 1 we obtain the inequality (2.38).
.P
To prove (2.39), we use a similar argument, but this time we utilize the infinite product for theta functions
[2; Eq.\ (32.1)].
We find, for $q= exp ( - pi sup 2 /s )$, that
.DS 3
.EQ
f(s,^y) mark ~=~ ( pi /s ) sup 1/2 ^theta sub 3 ( pi y ,^i pi /s )
.EN
.sp
.EQ
lineup ~=~ ( pi / s ) sup 1/2 ^theta sub 4 ( pi y + pi /2 ,^i pi /s )
.EN
.sp
.EQ (2.43)
lineup ~=~ ( pi /s ) sup 1/2 ~prod from k=1 to inf ~ "{"
(1+ 2 q sup 2k-1 ^cos ( 2 pi y ) + q sup 4k-2 ) ( 1-q sup 2k ) "}"
.EN
.sp
.EQ
lineup ~>=~ ( pi /s ) sup 1/2 ~prod from k=1 to inf ~ "{"
(1-2q sup 2k-1 + q sup 4k-2 ) ( 1-q sup 2k ) "}"
.EN
.sp
.EQ
lineup ~=~ f( s,^1/2 ) ^,
.EN
.DE
which shows that for all $s^>^0$, $af ^>^0$,
.DS 2
.EQ (2.44)
e sup {s af n} ^F( x sub 1 ,^dd ,^x sub n ,^s ) ~>=~ e sup {s af n} ^F( 1/2 ,^dd ,^1/2 ,^s ) ^,
.EN
.DE
and this gives the inequality (2.39).
.br
.ta 6iR
.sp -2
	$blot$
.P
To conclude our series of technical results, we show that the extremal values of $N( bold x ,^n ,^af )$ differ from the mean value by exponential factors.
.H 3 "Theorem 3."
.I
For any $af ^>^0$, there is a constant $omega^>^0$ such that for $n^>=^n sub 0 ( af )$,
.DS 2
.EQ (2.45)
N(( 1/2 ,^dd ,^1/2) ,^n,^af ) e sup {omega n} ~<=~
(2 pi e af ) sup n/2 ~<=~ N (( 0,^dd ,^0) ,^n,^af ) e sup {- omega n} ^.
.EN
.DE
.R
.H 3 "Proof."
In view of previous results, it suffices to show that if (in the notation of Theorem\ 1)
.DS 2
.EQ (2.46)
s sub 1 ~=~ s( af ; ~ ( 0,^dd ,^0 )) ^,
.EN
.DE
then
.DS 2
.EQ (2.47)
s sub 1 af ^+^ log^f(s sub 1 ,^0) ~>~ 1 over 2 ~ log ^( 2 pi e af ) ^,
.EN
.DE
and that if $af ^>^ 1/4$ and
.DS 2
.EQ (2.48)
s sub 2 ~=~ s ( af ; ~ ( 1/2 ,^dd ,^1/2 )) ^,
.EN
.DE
then
.DS 2
.EQ (2.49)
s sub 2 af ^+^ log ^f ( s sub 2 ,^1/2 ) ~<~ 1 over 2 ~ log ^ (2 pi e af ) ^.
.EN
.DE
(Note that for $0^<^ af le 1/4$, the inequality on the left side of (2.45) is trivial, as
$N(( 1/2 ,^dd ,^1/2 ) ,^n,^af ) =0$ for $0 ^<^af ^<^1/4$,
and $= 2 sup n$ for $af = 1/4$.)
It is easy to see (using the transformation formula (2.40), as in the first part of (2.41)) that
.DS 2
.EQ (2.50)
s sub 1 af ^+^ log ^f ( s sub 1 ,^0) ^-^ 1 over 2 ^log ^( 2 pi e af ) ^->^0 ~~~roman {"as"} ~~~ af ^->^inf ^,
.EN
.DE
and so to prove (2.47) it suffices to show that
for $0^<^af ^<^inf$,
.DS 2
.EQ (2.51)
partial over {partial af}~ lpar s sub 1 af + log^f ( s sub 1 ,^0) - 1 over 2 ^log ^( 2 pi e af ) rpar
^<^ 0 ^.
.EN
.DE
Since
.DS 2
.EQ (2.52)
af ^=^ - ^ partial over {partial s sub 1} ~ log ^f( s sub 1 ,^0) ^,
.EN
.DE
inequality (2.51) will follow if we show that
.DS 2
.EQ (2.53)
- ^ partial over {partial s} ~log ^f (s ,^0) ~<~ 1 over 2s , ~~~~ 0 ^<^ s^<^ inf ^.
.EN
.DE
As in inequality (2.41), we have
.DS 2
.EQ
f(s ,^0) ~=~ ( pi / s ) sup 1/2 ^theta sub 3 ( 0,^ i pi /s ) ^,
.EN
.DE
and so we only have to show that
.DS 2
.EQ (2.54)
partial over {partial s} ~ theta sub 3 ( 0,^i pi /s ) ^>^0 ~~~for ~~~ 0 ^<^ s ^<^ inf ^,
.EN
.DE
which is obvious from the infinite sum (2.3) defining $theta sub 3$.
This proves (2.47).
.P
To prove (2.48), we use a similar argument.
Again,
.DS 2
.EQ (2.55)
s sub 2 af ^+^ log ^f( s sub 2 ,^1/2 ) ^-^ 1 over 2 ^log^ ( 2 pi e af ) ^->^0 ~~~roman {"as"} ~~~ af ^->^inf ^,
.EN
.DE
so it suffices to show that for $0 ^<^ af ^<^inf$,
.DS 2
.EQ (2.56)
partial over {partial af} ^lpar s sub 2 af + log ^f ( s sub 2 ,^1/2 ) ^-^ 1 over 2^log^( 2 pi e af ) rpar ^>^0 ^.
.EN
.DE
Since
.DS 2
.EQ (2.57)
af ^=^ - ^ partial over {partial s sub 2} ~ log ^f( s sub 2 ,^1/2 ) ^,
.EN
.DE
we need to show that
.DS 2
.EQ (2.58)
- ^partial over {partial s} ~log^f(s ,^1/2 ) ~>~ 1 over 2s ^, ~~~~
0^<^s^<^inf ^,
.EN
.DE
which reduces to showing that
.DS 2
.EQ (2.59)
partial over {partial s} ~
theta sub 4 ( 0,^i pi /s ) ^<^ 0 ~~~~for ~~~~0 ^<^s ^<^ inf ^.
.EN
.DE
This, however, follows form the infinite product for $theta sub 4 ( 0,^i pi /s )$.
As in (2.43), we find that for $q = exp ( - pi sup 2 /s )$,
.DS 2
.EQ (2.60)
theta sub 4 (0,^ i pi / s ) ~=~ prod from k=1 to inf ~ "{"
( 1-q sup 2k-1 ) sup 2 (1-q sup 2k ) "}" ^,
.EN
.DE
and so (2.59) follows.
This completes the proof of the theorem.
.br
.ta 6iR
.sp -2
	$blot$
.P
A different proof of Theorem\ 3 could be given based more directly on the proofs of Theorems\ 1 and 2.
It would rely on the fact that
.DS 2
.EQ
exp ( n alpha s ( alpha ;^bold x ))~F ( x sub 1 ,^dd ,^x sub n ,^s )
.EN
.DE
is not constant as $bold x$ varies, and so minimal and maximal
values have to differ from the mean.
.H 1 "Concluding remarks"
Theorem\ 2 leaves open the question whether the inequality (2.39) of Theorem\ 2 holds for $af = 1/4$.
It seems very likely that it does, and this might be provable by extensions of our methods.
(By Theorem\ 1, inequality (2.39) definitely holds if $SIGMA ^|| x sub j || sup 2$ stays away from $n/4$.)
.P
The lower bound of Theorem\ 2 can be obtained fairly easily basically because
it estimates partial sums of coefficients of generating functions.
When one deals with a single fixed generating function, it is often possible to get very precise information about the asymptotic behavior of sums of coefficients with indices $<=^x$ as $x^->^inf$ by using Tauberian theorems.
Since Tauberian theorems require very little information about the generating function, such a method is very convenient to use.
Unfortunately, it is not applicable to our problem, since we do not deal with a single fixed generating function, but a sequence of functions.
.P
The method used to obtain the lower bound of Theorem\ 2 is very simple, and can be extended to many other problems
in number theory, analysis, and combinatorial enumeration.
For example, it can be used to show that the Rush-Sloane packing results [11] hold for general $sigma$, not just for integers.
.P
The essence of the lower bound method of Theorem\ 2 is the use of a weighted
sum of the quantities whose
cumulative sums are being sought.
In our case it gives estimates accurate to within multiplicative factors of $exp ( cn sup 1/2 )$.
One can improve on this method and obtain more accurate estimates by using more complicated weights (which might also require
using an integral of $exp ( s af n ) F(s)$ times a weight function instead of the simple
three-term sum of (2.24)).
.P
In some cases it is possible to obtain very precise estimates by using the saddle-point method.
For example, to estimate
$N( bold x sub 0 ,^n,^af )$, where $bold x sub 0 = ( 0,^dd ,^0)$, let
.DS 2
.EQ
z ^=^ e sup -s ^,
.EN
.DE
so that $f(s,^0) = h(z)$, with
.DS 2
.EQ (3.1)
h(z) ^=^ 1 ^+^ 2 ~sum from k=1 to inf ~ z sup k sup 2 ^.
.EN
.DE
Then $N sub r =0$ for $r ^!=^m sup 1/2$, $m mem ZZ$, $m ge 0$,
and if $r = m sup 1/2$, then $N sub r$ is the coefficient of $z sup m$ in
the Taylor series expansion of $h(z) sup n$.
Therefore for $r= m sup 1/2$ (so $af = m/n$)
.DS 2
.EQ (3.2)
N((0,^dd ,^0) ,^n,^af ) ~=~ 1 over {2 pi i} ~ int0~
{h(z) sup n} over {z sup m} ~ dz over z(1-z) ^,
.EN
.DE
where the integral is taken over any circle
$|z| = w$, $0 ^<^w ^<^1$.
If we let $m,^n^->^inf$ so that $af = m/n mem ( c sub 1 ,^c sub 2 )$ for some fixed $0 ^<^ c sub 1 ^<^ c sub 2 ^<^ inf$, then it is easy to show that the integrand in (3.2) has an approximate saddle point
at $z = z sub 0$, where $z sub 0$ is the unique real solution in (0,\|1) to
.DS 2
.EQ (3.3)
z ~ {h spr} over h ^(z) ~=~ af
.EN
.DE
(this corresponds to the point determined by Theorem\ 1), and that
.DS 2
.EQ (3.4)
N((0,^dd ,^0 ),^n,^af ) ~wig~ 1 over {(1-z sub 0 ) sqrt {2b pi n}} ~
{h(z sub 0 ) sup n} over {z sub 0 sup m} ^,
.EN
.DE
where
.DS 2
.EQ (3.5)
b ~=~ d over dz ~ left "" lpar {h sup prime} over n ^(z) ^-^ m over nz rpar ^right | sub {z = z sub 0} ^.
.EN
.DE
This estimate shows that the bound of Lemma\ 1 is off only by a factor of $n sup 1/2$ for $bold x = (0,^dd ,^0)$, and suggests that the same is true for other $bold x$.
.P
The estimate (3.4) applies only for $af = m/n$, $m,^n mem Z sup +$.
If we wish to apply it for a fixed $af$, with $n ^->^inf$, we do not obtain
a simple solution, since for each $n$ we need to take $m= left floor n af right floor$ (the integer
part of $n af$) and compute the bound for this $m$.
This gives rise to slight oscillations,
reflecting the fact that the number of lattice points in a sphere of radius $(m+1) sup 1/2$ is larger than the number in a sphere of radius $m sup 1/2$ by a constant $>^1$.
.P
The saddle-point method can be extended to a few points other than $bold x = (0,^dd ,^0)$.
However, to obtain precise bounds by analytic method, it seems that one needs to go
back to using the functions $f(s,^y)$, but this time allowing $s$ to be complex.
Perron-type integral formulas can then be used to evaluate the $N( bold x ,^n ,^af )$, but to estimate them effectively one needs to use kernels that lead to problems similar to those
one encounters when using weighted sums of the form mentioned
at the beginning of this section.
.PH ""
.bp
.ce
.B REFERENCES
.sp
.nr P 1
.PH "''R-\\\\nP''"
.AL
.LI
J. Beck,
On a lattice point problem of L. Moser. I,
\f2Combinatorica\f1 \f38\f1 (1989), 21-47.
.LI
R. Bellman,
\f2A Brief Introduction to Theta Functions\f1,
Holt, Rinehart,
and Winston, 1961.
.LI
K. Chandrasekharan and R. Narasimhan,
On lattice-points in a random sphere,
\f2Bull. Amer. Math. Soc.\f1 \f373\f1 (1967), 68-71.
.LI
P. Erdo\*:s,
P.\ M. Gruber, and J. Hammer,
\f2Lattice Points\f1, Longman, 1989.
.LI
F. Fricker,
.I
Einfu\*:hrung in die Gitterpunktlehre,
.R
Birkha\*:user, 1982.
.LI
A.\ M. Frieze,
On the Lagarias-Odlyzko algorithm for the subset sum problem,
\f2SIAM J. Comp.\f1 \f315\f1 (1986), 536-539.
.LI
E. Grosswald,
\f2Representations of Integers as Sums of Squares\f1,
Springer, 1985.
.LI
J. Hammer,
\f2Unsolved Problems Concerning Lattice Points\f1,
Pitman 1977.
.LI
J.\ C. Lagarias and A.\ M. Odlyzko,
Solving low-density subset sum problems,
\f2J. Assoc. Comp. Mach.\f1 \f332\f1 (1985), 229-246.
(Preliminary version in
\f2Proc. 24th IEEE Found. Computer Sci. Symp.\f1,
1983, pp.\ 1-10.)
.LI
H.\ L. Montgomery,
Minimal theta functions,
\f2Glasgow Math. J.\f1 \f330\f1 (1988), 75-85.
.LI
J. Rush and N.\ J.\ A. Sloane,
An improvement to the Minkowski-Hlawka bound for packing superballs,
\f2Mathematika\f1 \f334\f1 (1987), 8-18.
.LI
A.\ I. Vinogradov and M.\ M. Skriganov,
The number of lattice points inside the sphere with variable center,
analytic number theory and the theory of functions, 2,\p
.sp -.2
$Zap.~ Nan c to {down 155 {"\N'207'"}} n. ~Sem.$
\f2Leningrad Otdal. Mat. Inst. Steklov\f1
(\f2LOMI\f1) \f391\f1 (1979), 25-30, 180.
.LI
A. Walfisz,
\f2Gitterpunkte in mehrdimensionalen Kugeln\f1,
Polish Scientific Publishers,
Warsaw, 1957.
.LI
E.\ T. Whittaker and G.\ N. Watson,
\f2A Course of Modern Analysis\f1,
4th ed., Cambridge Univ. Press, 1927.
.LI
A.\ A. Yudin, On the number of integer points in the displaced circles,
\f2Acta Arith.\f1 \f314\f1 (1967/68), 141-152.
.LI
J. Ziv,
On universal quantization,
\f2IEEE Trans. Information Theory\f1
\f3IT-31\f1 (1985), 344-347.
.LE
.PH ""
.bp
.DS
.VL 8
.LI "Table\ 1."
Number of lattice points, $N$, in an $n$-dimensional sphere of radius $( alpha n ) sup 1/2$ as the center of the sphere varies.
.LE
.sp 2
.TS
center;
c | c | c | c
n | n | n | n.
$af$	$lim ^n sup -1^log^(1+ min^N )$	$lim ^n sup -1^log^( roman mean ^N )$	$lim ^n sup -1^log^( max ^N )$
.sp .2
_
.sp .25
0.1	0.0	0.267645986	0.394414813
.sp .5
0.2	0.0	0.614219576	0.639415756
.sp .5
0.3	0.810070417	0.816952131	0.821516167
.sp .5
0.4	0.960010601	0.960793167	0.961505491
.sp .5
0.5	1.072260430	1.072364942	1.072467359
.sp .5
0.6	1.163511322	1.163525721	1.163540062
.sp .5
0.7	1.240599064	1.240601061	1.240603056
.sp .5
0.8	1.307366480	1.307366757	1.307367034
.sp .5
0.9	1.366258236	1.366258275	1.366258313
.sp .5
1.0	1.418938527	1.418938533	1.418938538
.TE
.DE
.ls 1
.CS