In mathematics, the Gauss circle problem is the problem of determining how many integer lattice points there are in a circle centered at the origin and with radius . This number is approximated by the area of the circle, so the real problem is to accurately bound the error term describing how the number of points differs from the area. The first progress on a solution was made by Carl Friedrich Gauss, hence its name.

A circle of radius 5 centered at the origin has area 25π, approximately 78.54, but it contains 81 integer points, so the error in estimating its area by counting grid points is approximately 2.46. For a circle with slightly smaller radius, the area is nearly the same, but the circle contains only 69 points, producing a larger error of approximately 9.54. The Gauss circle problem concerns bounding this error more generally, as a function of the radius of the circle.

The problem

edit

Consider a circle in   with center at the origin and radius  . Gauss's circle problem asks how many points there are inside this circle of the form   where   and   are both integers. Since the equation of this circle is given in Cartesian coordinates by  , the question is equivalently asking how many pairs of integers m and n there are such that

 

If the answer for a given   is denoted by   then the following list shows the first few values of   for   an integer between 0 and 12 followed by the list of values   rounded to the nearest integer:

1, 5, 13, 29, 49, 81, 113, 149, 197, 253, 317, 377, 441 (sequence A000328 in the OEIS)
0, 3, 13, 28, 50, 79, 113, 154, 201, 254, 314, 380, 452 (sequence A075726 in the OEIS)

Bounds on a solution and conjecture

edit

  is roughly  , the area inside a circle of radius  . This is because on average, each unit square contains one lattice point. Thus, the actual number of lattice points in the circle is approximately equal to its area,  . So it should be expected that

 

for some error term   of relatively small absolute value. Finding a correct upper bound for   is thus the form the problem has taken. Note that   does not have to be an integer. After   one has  At these places   increases by   after which it decreases (at a rate of  ) until the next time it increases.

Gauss managed to prove[1] that

 

Hardy[2] and, independently, Landau found a lower bound by showing that

 

using the little o-notation. It is conjectured[3] that the correct bound is

 

Writing  , the current bounds on   are

 

with the lower bound from Hardy and Landau in 1915, and the upper bound proved by Martin Huxley in 2000.[4]

Exact forms

edit

The value of   can be given by several series. In terms of a sum involving the floor function it can be expressed as:[5]

 

This is a consequence of Jacobi's two-square theorem, which follows almost immediately from the Jacobi triple product.[6]

A much simpler sum appears if the sum of squares function   is defined as the number of ways of writing the number   as the sum of two squares. Then[1]

 

Most recent progress rests on the following Identity, which has been first discovered by Hardy:[7]

 

where   denotes the Bessel function of the first kind with order 1.

Generalizations

edit

Although the original problem asks for integer lattice points in a circle, there is no reason not to consider other shapes, for example conics; indeed Dirichlet's divisor problem is the equivalent problem where the circle is replaced by the rectangular hyperbola.[3] Similarly one could extend the question from two dimensions to higher dimensions, and ask for integer points within a sphere or other objects. There is an extensive literature on these problems. If one ignores the geometry and merely considers the problem an algebraic one of Diophantine inequalities, then there one could increase the exponents appearing in the problem from squares to cubes, or higher.

The dot planimeter is physical device for estimating the area of shapes based on the same principle. It consists of a square grid of dots, printed on a transparent sheet; the area of a shape can be estimated as the product of the number of dots in the shape with the area of a grid square.[8]

The primitive circle problem

edit

Another generalization is to calculate the number of coprime integer solutions   to the inequality

 

This problem is known as the primitive circle problem, as it involves searching for primitive solutions to the original circle problem.[9] It can be intuitively understood as the question of how many trees within a distance of r are visible in the Euclid's orchard, standing in the origin. If the number of such solutions is denoted   then the values of   for   taking small integer values are

0, 4, 8, 16, 32, 48, 72, 88, 120, 152, 192 … (sequence A175341 in the OEIS).

Using the same ideas as the usual Gauss circle problem and the fact that the probability that two integers are coprime is  , it is relatively straightforward to show that

 

As with the usual circle problem, the problematic part of the primitive circle problem is reducing the exponent in the error term. At present, the best known exponent is   if one assumes the Riemann hypothesis.[9] Without assuming the Riemann hypothesis, the best upper bound currently known is

 

for a positive constant  .[9] In particular, no bound on the error term of the form   for any   is currently known that does not assume the Riemann Hypothesis.

Notes

edit
  1. ^ a b Hardy, G. H. (1959). Ramanujan: Twelve Lectures on Subjects Suggested by His Life and Work (3rd ed.). New York: Chelsea Publishing Company. p. 67. MR 0106147.
  2. ^ Hardy, G. H. (1915). "On the expression of a number as the sum of two squares". Quarterly Journal of Mathematics. 46: 263–283.
  3. ^ a b Guy, Richard K. (2004). "F1: Gauß's lattice point problem". Unsolved Problems in Number Theory. Problem Books in Mathematics. Vol. 1 (3rd ed.). New York: Springer-Verlag. pp. 365–367. doi:10.1007/978-0-387-26677-0. ISBN 0-387-20860-7. MR 2076335.
  4. ^ Huxley, M. N. (2002). "Integer points, exponential sums and the Riemann zeta function". In Bennett, M. A.; Berndt, B. C.; Boston, N.; Diamond, H. G.; Hildebrand, A. J.; Philipp, W. (eds.). Number theory for the millennium, II: Papers from the conference held at the University of Illinois at Urbana–Champaign, Urbana, IL, May 21–26, 2000. Natick, Massachusetts: A K Peters. pp. 275–290. MR 1956254.
  5. ^ Hilbert, D.; Cohn-Vossen, S. (1952). Geometry and the Imagination. New York, N. Y.: Chelsea Publishing Company. pp. 37–38. MR 0046650.
  6. ^ Hirschhorn, Michael D. (2000). "Partial fractions and four classical theorems of number theory". The American Mathematical Monthly. 107 (3): 260–264. CiteSeerX 10.1.1.28.1615. doi:10.2307/2589321. JSTOR 2589321.
  7. ^ Landau, Edmund (1927). Vorlesungen über Zahlentheorie. Vol. 2. Verlag S. Hirzel. p. 189.
  8. ^ Steinhaus, Hugo. "O mierzeniu pól płaskich" (PDF). Przegląd Matematyczno-Fizyczny (in Polish). 2 (1–2): 24–29.
  9. ^ a b c Wu, Jie (2002). "On the primitive circle problem". Monatshefte für Mathematik. 135 (1): 69–81. doi:10.1007/s006050200006. MR 1894296. S2CID 119451320.
edit