Gauss circle problem

In mathematics, the Gauss circle problem is the problem of determining how many lattice points there are in a circle centred at the origin and with radius "r". The first progress on a solution was made by Carl Friedrich Gauss, hence its name.

The problem

Consider a circle in R² with centre at the origin and radius "r" ≥ 0. Gauss' circle problem asks how many points there are inside this circle of the form ("m","n") where "m" and "n" are both integers. Since the equation of this circle is given in Cartesian coordinates by "x"² + "y"² = "r"², the question is equivalently asking how many pairs of integers "m" and "n" there are such that:$m^2+n^2leq\; r^2.$

If the answer for a given "r" is denoted by "N"("r") then the following list shows the first few values of "N"("r") for "r" between 0 and 10::1, 5, 13, 29, 49, 81, 113, 149, 197, 253, 317 OEIS|id=A000328.

Bounds on a solution and conjecture

The area inside a circle of radius "r" is given by π"r"², and since a square of area 1 in R² contains one integer point, the expected answer to the problem could be about π"r"². In fact it should be slightly higher than this, since circles are more efficient at enclosing space than squares. So in fact it should be expected that:$N(r)=pi\; r^2\; +E(r),$for some error term "E"("r"). Finding a correct upper bound for "E"("r") is thus the form the problem has taken.

Gauss managed to proveG.H. Hardy, "Ramanujan: Twelve Lectures on Subjects Suggested by His Life and Work, 3rd ed." New York: Chelsea, (1999), p.67.] that:$E(r)leq\; 2sqrt\{2\}pi\; r.$
Hardy [G.H. Hardy, "On the Expression of a Number as the Sum of Two Squares", Quart. J. Math. 46, (1915), pp.263–283.] and, independently, Landau found a lower bound by showing that:$E(r)\; eq\; oleft(r^\{1/2\}(log\; r)^\{1/4\}\; ight),$using the little o-notation. It is conjecturedR.K. Guy, "Unsolved problems in number theory, Third edition", Springer, (2004), pp.365–366.] that the correct bound is:$E(r)=Oleft(r^\{1/2+varepsilon\}\; ight).$

Writing |"E"("r")| ≤ "Cr"^"t", the current bounds on "t" are:with the lower bound from Hardy and Landau in 1915, and the upper bound proved by Huxley in 2000. [M.N. Huxley, "Integer points, exponential sums and the Riemann zeta function", Number theory for the millenium, II (Urbana, IL, 2000) pp.275–290, A K Peters, Natick, MA, 2002, MathSciNet | id = 1956254.]

Exact forms

The value of "N"("r") can be given by several series. In terms of a sum involving the floor function it can be expressed as: [D. Hilbert and S. Cohn-Vossen, "Geometry and the Imagination", New York: Chelsea, (1999), pp.33–35.] :$N(r)=1+4sum\_\{i=0\}^infty\; left(leftlfloorfrac\{r^2\}\{4i+1\}\; ight\; floor-leftlfloorfrac\{r^2\}\{4i+3\}\; ight\; floor\; ight).$

A much simpler sum appears if the sum of squares function "r"₂("n") is defined as the number of ways of writing the number "n" as the sum of two squares. Then:$N(r)=sum\_\{n=0\}^\{r^2\}\; r\_2(n).$

Generalisations

Although the original problem asks for integer lattice points in a circle, there is no reason not to consider other shapes or conics, indeed Dirichlet's divisor problem is the equivalent problem where the circle is replaced by the rectangular hyperbola. Similarly one could extend the question from two dimensions to higher dimensions, and ask for integer points within a sphere or other objects. 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.

Notes

External links

*MathWorld|urlname=GausssCircleProblem|title=Gauss's circle problem