info prev up next book cdrom email home

Gauss's Circle Problem

\begin{figure}\begin{center}\BoxedEPSF{GausssCircleProblem.epsf scaled 650}\end{center}\end{figure}

Count the number of Lattice Points $N(r)$ inside the boundary of a Circle of Radius $r$ with center at the origin. The exact solution is given by the Sum

N(r)=1+4\left\lfloor{r}\right\rfloor +4\sum_{i=1}^{\left\lfloor{r}\right\rfloor }\left\lfloor{\sqrt{r^2-i^2}}\right\rfloor .
\end{displaymath} (1)

The first few values for $r=0$, 1, ... are 1, 5, 13, 29, 49, 81, 113, 149, ... (Sloane's A000328).

Gauß showed that

N(r)=\pi r^2+E(r),
\end{displaymath} (2)

\vert E(r)\vert \leq 2\sqrt{2}\,\pi r.
\end{displaymath} (3)

Writing $\vert E(r)\vert\leq Cr^\theta$, the best bounds on $\theta$ are $1/2<\theta\leq 46/73\approx 0.630137$ (Huxley 1990). The problem has also been extended to Conics and higher dimensions. The limit 1/2 was obtained by Hardy and Landau (1915), and the limit 46/73 improves previous values of $24/37\approx 0.64864$ (Cheng 1963) and $34/53\approx 0.64150$ (Vinogradov), and $7/11\approx 0.63636$.

See also Circle Lattice Points


Cheng, J. R. ``The Lattice Points in a Circle.'' Sci. Sinica 12, 633-649, 1963.

Cilleruello, J. ``The Distribution of Lattice Points on Circles.'' J. Number Th. 43, 198-202, 1993.

Guy, R. K. ``Gauß's Lattice Point Problem.'' §F1 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 240-2417, 1994.

Huxley, M. N. ``Exponential Sums and Lattice Points.'' Proc. London Math. Soc. 60, 471-502, 1990.

Huxley, M. N. ``Corrigenda: `Exponential Sums and Lattice Points'.'' Proc. London Math. Soc. 66, 70, 1993.

Le Lionnais, F. Les nombres remarquables. Paris: Hermann, p. 24, 1983.

Sloane, N. J. A. Sequence A000328/M3829 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

mathematica.gif Weisstein, E. W. ``Circle Lattice Points.'' Mathematica notebook CircleLatticePoints.m.

info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein