---
tag: 26XTJJT267
kind: problem
name: Gauss circle problem
msc: [11P21]
uses: [0C4JS9RF5M, 0TGV80E6A4, WN9V7WSJKF]
about: [26XTJJT267]
sources:
  - url: https://en.wikipedia.org/wiki/Gauss_circle_problem
same_as:
  wikidata: Q2096220
  wikipedia: Gauss circle problem
history:
  posed_by: "Carl Friedrich Gauss"
---

## Problem

For a real number $r > 0$, let $N(r)$ be the number of points $(x, y) \in \Z^2$ with $x^2 + y^2 \le r^2$, and let $E(r) = N(r) - \pi r^2$.
The problem is to determine the infimum $\theta$ of the real numbers $\alpha$ such that $E(r) = O(r^{\alpha})$ as $r \to \infty$, in [[big O notation|0TGV80E6A4]].

## Remarks

Gauss observed that $\abs{E(r)} \le 2\sqrt{2}\,\pi r$ for $r \ge 1$: the unit squares centred at the counted points lie between the discs of radius $r - \sqrt2/2$ and $r + \sqrt2/2$.
So $\theta \le 1$.
Sierpiński proved in 1906 that $E(r) = O(r^{2/3})$.
Hardy and Landau showed independently that $E(r)$ is not $O(r^{1/2})$, so $\theta \ge 1/2$.
It is conjectured that $\theta = 1/2$, that is, $E(r) = O(r^{1/2 + \varepsilon})$ for every $\varepsilon > 0$.
Martin Huxley proved $E(r) = O(r^{131/208 + \varepsilon})$ in 2003, and the problem remains open.
For example, $N(1) = 5$ and $N(2) = 13$, while $\pi \approx 3.14$ and $4\pi \approx 12.57$.

## Explanations

### L1 human

Draw a circle of radius $r$ around the origin on squared paper and count the grid points inside it.
The count is close to the area $\pi r^2$, since each grid point owns one unit square.
The question is how big the error can be.
The easy bound is about the length of the circle, but the true error appears to be much smaller, about the square root of that.