Gauss circle problem

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

${\displaystyle m^{2}+n^{2}\leq r^{2}.}$

If the answer for a given ${\displaystyle r}$ is denoted by ${\displaystyle N(r)}$ then the following list shows the first few values of ${\displaystyle N(r)}$ for ${\displaystyle r}$ an integer between 0 and 12 followed by the list of values ${\displaystyle \pi r^{2}}$ 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)

${\displaystyle N(r)}$ is roughly ${\displaystyle \pi r^{2}}$, the area inside a circle of radius ${\displaystyle r}$. 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, ${\displaystyle \pi r^{2}}$. So it should be expected that

${\displaystyle N(r)=\pi r^{2}+E(r)\,}$

for some error term ${\displaystyle E(r)}$ of relatively small absolute value. Finding a correct upper bound for ${\displaystyle \mid E(r)\mid }$ is thus the form the problem has taken. Note that ${\displaystyle r}$ does not have to be an integer. After ${\displaystyle N(4)=49}$ one has${\displaystyle N({\sqrt {17}})=57,N({\sqrt {18}})=61,N({\sqrt {20}})=69,N(5)=81.}$ At these places ${\displaystyle E(r)}$ increases by ${\displaystyle 8,4,8,12}$ after which it decreases (at a rate of ${\displaystyle 2\pi r}$) until the next time it increases.

Gauss managed to prove[1] that

${\displaystyle |E(r)|\leq 2{\sqrt {2}}\pi r.}$

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

${\displaystyle |E(r)|\neq o\left(r^{1/2}(\log r)^{1/4}\right),}$

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

${\displaystyle |E(r)|=O\left(r^{1/2+\varepsilon }\right).}$

Writing ${\displaystyle E(r)\leq Cr^{t}}$, the current bounds on ${\displaystyle t}$ are

${\displaystyle {\frac {1}{2}}<t\leq {\frac {131}{208}}=0.6298\ldots ,}$

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

The value of ${\displaystyle N(r)}$ can be given by several series. In terms of a sum involving the floor function it can be expressed as:[5]

${\displaystyle N(r)=1+4\sum _{i=0}^{\infty }\left(\left\lfloor {\frac {r^{2}}{4i+1}}\right\rfloor -\left\lfloor {\frac {r^{2}}{4i+3}}\right\rfloor \right).}$

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 ${\displaystyle r_{2}(n)}$ is defined as the number of ways of writing the number ${\displaystyle n}$ as the sum of two squares. Then[1]

${\displaystyle N(r)=\sum _{n=0}^{r^{2}}r_{2}(n).}$

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

${\displaystyle N(x)-{\frac {r_{2}(x^{2})}{2}}=\pi x^{2}+x\sum _{n=1}^{\infty }{\frac {r_{2}(n)}{\sqrt {n}}}J_{1}(2\pi x{\sqrt {n}}),}$

where ${\displaystyle J_{1}}$ denotes the Bessel function of the first kind with order 1.

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]

• Weisstein, Eric W. "Gauss's circle problem". MathWorld.
• Grant Sanderson, "Pi hiding in prime regularities", 3Blue1Brown