TOPICS
Search

Gauss's Circle Problem

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
GausssCircleProblem

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|_r_|+4sum_(i=1)^(|_r_|)|_sqrt(r^2-i^2)_|
(1)
=1+4sum_(i=1)^(r^2)(-1)^(i-1)|_(r^2)/(2i-1)_|
(2)
=1+4sum_(i=0)^(infty)(|_(r^2)/(4i+1)_|-|_(r^2)/(4i+3)_|)
(3)

(Hilbert and Cohn-Vossen 1999, p. 39). The first few values for r=0, 1, ... are 1, 5, 13, 29, 49, 81, 113, 149, ... (OEIS A000328).

The series for N(r) is intimately connected with the sum of squares function r(n) (i.e., the number of representations of n by two squares), since

N(r)=sum_(n=0)^(r^2)r(n)
(4)

(Hardy 1999, p. 67). N(r) is also closely connected with the Leibniz series since

1/4[(N(r))/(r^2)-1/(r^2)]=1-1/3+1/5-1/7+...+/-1/r+/-(E(r))/r =1/4[pi+2Phi(-1,1,1/2+r)]+/-(E(r))/r =1/4[pi+psi_0(1/4(3+2r))-psi_0(1/4(1+2r))]+/-(E(r))/r,
(5)

where Phi(z,s,a) is a Lerch transcendent and psi_0(x) is a digamma function, so taking the limit r->infty gives

1/4pi=1-1/3+1/5-1/7+1/9+...
(6)

(Hilbert and Cohn-Vossen 1999, p. 39).

Gauss showed that

N(r)=pir^2+E(r),
(7)

where

|E(r)|<=2sqrt(2)pir
(8)

(Hardy 1999, p. 67).

GausssCirclePi

The first few values of N(r)/r^2 are 5, 13/4, 29/9, 49/16, 81/25, 113/36, 149/49, 197/64, 253/81, 317/100, 377/121, 49/16, ... (OEIS A000328 and A093837). As can be seen in the plot above, the values of r such that N(r)/r^2>pi are r=2, 3, 4, 6, 11, 16, 21, 36, 52, 53, 86, 101, ... (OEIS A093832).

Writing |E(r)|<=Cr^theta, the best bounds on theta are

1/2<theta<=131/208 approx 0.62981
(9)

(Huxley 2003). The lower limit 1/2 was obtained independently by Hardy and Landau in 1915. The following table summarizes incremental improvements in the upper limit (updated from Hardy 1999, p. 81).

thetaapprox.citation
11.00000Dirichlet
2/30.66667Voronoi (1903), Sierpiński (1906), van der Corput (1923)
37/560.66071Littlewood and Walfisz (1925)
33/500.66000van der Corput (1922)
27/410.65854van der Corput (1928)
15/230.65217
24/370.64865Chen (1963), Kolesnik (1969)
35/540.64815Kolesnik (1982)
278/4290.64802Kolesnik
34/530.64151Vinogradov (1935)
7/110.63636Iwaniec and Mozzochi (1988)
46/730.63014Huxley (1993)
131/2080.62981Huxley (2003)

The problem has also been extended to conics, ellipsoids (Hardy 1915), and higher dimensions.

See also

Circle Lattice Points, Dirichlet Divisor Problem, Leibniz Series, Schinzel Circle, Sum of Squares Function

Explore with Wolfram|Alpha

References

Bohr, H. and Cramér, H. "Ellipsoidprobleme." In "Die neuere Entwicklung der analytischen Zahlentheorie." Ch. IIC88 in Enzykl. d. Math. Wiss., Vol. 2, Part 3, Issue 2 II C 8, 823-824, 1922.Chen, 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.Graham, S. W. and Kolesnik, G. Van Der Corput's Method of Exponential Sums. Cambridge, England: Cambridge University Press, 1991.Guy, R. K. "Gauß's Lattice Point Problem." §F1 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 240-241, 1994.Hardy, G. H. "On the Expression of a Number as the Sum of Two Squares." Quart. J. Math. 46, 263-283, 1915.Hardy, G. H. Ramanujan: Twelve Lectures on Subjects Suggested by His Life and Work, 3rd ed. New York: Chelsea, 1999.Hardy, G. H. and Wright, E. M. An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, pp. 268-269, 1979.Hilbert, D. and Cohn-Vossen, S. Geometry and the Imagination. New York: Chelsea, pp. 33-35, 1999.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.Huxley, M. N. "Exponential Sums and Lattice Points. II." Proc. London Math. Soc. 66, 279-301, 1993.Huxley, M. N. "Exponential Sums and Lattice Points III." Proc. London Math. Soc. 87, 5910-609, 2003.Iwaniec, H. and Mozzochi, C. J. "On the Divisor and Circle Problem." J. Numb. Th. 29, 60-93, 1988.Keller, H. B. and Swenson, J. R. "Experiments on the Lattice Problem of Gauss." Math. Comput. 17, 223-230, 1963.Kolesnik, G. A. "An Improvement of the Remainder Term in the Divisor Problem." Mat. Zametki 6, 545-554, 1969. English translation in Math. Notes 6, 784-791, 1969.Kolesnik, G. "On the Order of zeta(1/2+it) and Delta(R)." Pacific J. Math. 98, 107-122, 1982.Landau, E. "Neue Untersuchungen über die Pfeiffer'sche Methode zur Abschätzung von Gitterpunktanzahlen." Sitzungsber. d. math-naturw. Classe der Kaiserl. Akad. d. Wissenschaften, 2. Abteilung, Wien, No. 124, 469-505, 1915.Landau, E. "Über die Gitterpunkte in einem mehrdimensionalen Ellipsoid." In Zur analytischen Zahlentheorie der definiten quadratischen Formen. Sitzungsber. d. Berliner math. Gesellschaft, 458-476, 1915.Landau, E. "Über die Anzahl der Gitterpunkte in gewissen Bereichen. I." Nachr. v. d. Gesellschaft d. Wiss. zu Göttingen, math.-phys. Klasse, 687-770, 1912.Landau, E. "Über die Anzahl der Gitterpunkte in gewissen Bereichen. II." Nachr. v. d. Gesellschaft d. Wiss. zu Göttingen, math.-phys. Klasse, 209-243, 1915.Landau, E. "Über die Anzahl der Gitterpunkte in gewissen Bereichen. III." Nachr. v. d. Gesellschaft d. Wiss. zu Göttingen, math.-phys. Klasse, 96-101, 1917.Landau, E. "Über die Anzahl der Gitterpunkte in gewissen Bereichen. IV." Nachr. v. d. Gesellschaft d. Wiss. zu Göttingen, math.-phys. Klasse, 137-150, 1924.Landau, E. "Über die Gitterpunkte in einem Kreise. I." Nachr. v. d. Gesellschaft d. Wiss. zu Göttingen, math.-phys. Klasse, 148-160, 1915.Landau, E. "Über die Gitterpunkte in einem Kreise. II." Nachr. v. d. Gesellschaft d. Wiss. zu Göttingen, math.-phys. Klasse, 161-171, 1915.Landau, E. "Über die Gitterpunkte in einem Kreise. III." Nachr. v. d. Gesellschaft d. Wiss. zu Göttingen, math.-phys. Klasse, 109-134,1920.Landau, E. "Über die Gitterpunkte in einem Kreise. IV." Nachr. v. d. Gesellschaft d. Wiss. zu Göttingen, math.-phys. Klasse, 58-65, 1924.Landau, E. "Über die Gitterpunkte in einem Kreise. V." Nachr. v. d. Gesellschaft d. Wiss. zu Göttingen, math.-phys. Klasse 135-136, 1924.Landau, E. "Über Gitterpunkte in mehrdimensionalen Ellipsoiden. I." Math. Z. 21, 126-132, 1924.Landau, E. "Über Gitterpunkte in mehrdimensionalen Ellipsoiden. II." Math. Z. 24, 299-310, 1925.Landau, E. Vorlesungen über Zahlentheorie, Vol. 2. New York: Chelsea, pp. 183-308, 1970.Landau, E. and van der Corput, J. G. "Über Gitterpunkte in ebenen Bereichen." Nachr. v. d. Gesellschaft d. Wissenschaften zu Göttingen, math.-phys. Klasse, 135-171, 1920.Le Lionnais, F. Les nombres remarquables. Paris: Hermann, p. 24, 1983.Littlewood, J. E. and Walfisz, A. "The Lattice Points of a Circle. (With a Note by Prof. E. Landau.)." Proc. Roy. Soc. London (A) 106, 478-488, 1925.Sloane, N. J. A. Sequences A000328/M3829, A093832, and A093837 in "The On-Line Encyclopedia of Integer Sequences."Titchmarsh, E. C. "On van der Corput's Method and the Zeta-Function of Riemann. I." Quart. J. Math. (Oxford) 2, 161-173, 1931.Titchmarsh, E. C. "On van der Corput's Method and the Zeta-Function of Riemann. II." Quart. J. Math. (Oxford) 2, 313-320, 1931.Titchmarsh, E. C. "The Lattice Points in a Circle." Proc. London Math. Soc. 28, 96-115, 1934.Titchmarsh, E. C. "Corrigendum. The Lattice-Points in a Circle." Proc. London Math. Soc. 38, 555, 1935.van der Corput, J. G. "Zum Teilerproblem." Math. Ann. 98, 697-716, 1928.Vinogradov, I. M. "Anzahl der Gitterpunkte in der Kugel." Traveaux Inst. Phys.-Math. Stekloff (Leningrade) 9, 17-38, 1935. [Russian].

Referenced on Wolfram|Alpha

Gauss's Circle Problem

Cite this as:

Weisstein, Eric W. "Gauss's Circle Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GausssCircleProblem.html

Subject classifications