{"id":2771,"date":"2026-07-01T07:16:05","date_gmt":"2026-07-01T11:16:05","guid":{"rendered":"https:\/\/mathvoices.ams.org\/featurecolumn\/?p=2771"},"modified":"2026-07-21T09:48:05","modified_gmt":"2026-07-21T13:48:05","slug":"another-look-at-circles-and-squares","status":"publish","type":"post","link":"https:\/\/mathvoices.ams.org\/featurecolumn\/2026\/07\/01\/another-look-at-circles-and-squares\/","title":{"rendered":"Another Look at Circles and Squares"},"content":{"rendered":"

This is not obviously a difficult problem. But in over two hundred years since Carl Friedrich Gauss first posed it, there has been remarkably little progress…<\/em><\/span><\/p>\n

Another Look at Circles and Squares<\/h1>\n

Bill Casselman
\nUniversity of British Columbia<\/b><\/p>\n

Another look at circles and squares<\/h1>\n

One of the most intriguing unsolved problems in
\nmathematics is very simple to explain.<\/p>\n

A lattice point in the plane is a point $(a,b)$
\nin which both $a$ and $b$ are integers. An earlier Feature Column<\/a>
\nwas concerned with the function<\/p>\n

$$ r_{2}(n) = \\hbox{ the number of lattice points $(a,b)$ such that
\n$a^{2} + b^{2} = n$.} $$<\/p>\n

Or, in other words, the number of lattice points
\nlying on the circle of radius $\\sqrt{n}$ centred at the origin.
\nIn this column, let<\/p>\n

$$ R_{2}(n) = {\\sum}_{m \\le n} r_{2}(m) \\, . $$<\/p>\n

This is the number of lattice points
\ninside the closed disk of radius $\\sqrt{n}$.
\nFor example, $R_{2}(10) = 37$, as this diagram shows:<\/p>\n

\n\"Lattice
\n<\/figure>\n

For large $n$, the number $R_{2}(n)$ is approximately
\nequal to the area $\\pi n$ of the disk of radius $\\sqrt{n}$.
\nThe problem I have in mind is this:<\/p>\n\n\n
\n$\\bullet$ What is a good estimate of the
\nerror $|\\Delta(n)| = |R_{2}(n) – \\pi n|$ in approximating
\n$R_{2}(n)$ by the area?<\/em>\n<\/td>\n<\/tr>\n<\/table>\n

This is not obviously a difficult problem.
\nBut in over two hundred years since
\nCarl Friedrich Gauss
\nfirst posed it, there has been remarkably
\nlittle progress. Gauss proved that
\n$\\Delta(n)$ is bounded by a small
\nmultiple of the length $2 \\pi \\sqrt{n}$ of
\nthe circumference, by an elementary argument.
\nNothing elementary is to be found in any
\nsubsequent work.
\nMathematicians in the early twentieth century
\nshowed in various ways that $\\Delta(n)$ was of order at most $n^{1\/3}$.
\nSince then, improvements have been technical and modest.
\nI think it is fair to say that we have
\nessentially no idea of what’s going on.<\/p>\n

That earlier column derived a formula for $r_{2}(n)$
\ndue to the nineteenth century mathematician Carl Gustav Jacob Jacobi:<\/p>\n

$$ r_{2}(n) = 4(d_{1}(n) – d_{3}(n)) \\qquad \\hbox{( $n \\ge 1$ ) } $$<\/p>\n

where $d_{i}(n)$ is the number of positive divisors of $n$
\ncongruent to $i$ modulo $4$. For example, if $n$ is
\na prime congruent to $1$ modulo $4$ then $r_{2}(n) = 8$,
\nand if it is a prime congruent to $3$ then $r_{2}(n) = 0$.<\/p>\n

\n\"A
Graph of $r_{2}(n)$<\/figcaption><\/figure>\n

\nAs its graph illustrates, the
\nfunction $r_{2}(n)$ behaves erratically as $n$ grows,
\nbut for us the most important thing about it is that
\nit is known
\nthat $r_{2}(n)$ remains rather small
\nas $n$ grows. A well known result is
\nthat it grows more slowly than any
\nfunction $n^{s}$ with $s > 0$. (This is
\nfound, for example, at the beginning
\nof Chapter XIII of the
\nclassic text by Hardy and Wright<\/a>.)<\/p>\n

Some details<\/h2>\n

Gauss’ result is that the difference between $R_{2}(n)$ and the area
\nof the disk is bounded by a small multiple of its circumference:<\/p>\n

\nTheorem<\/b>. If $n \\ge 2$ then
\n$| \\pi n – R_{2}(n) | \\le \\sqrt{2} \\cdot 2 \\pi \\sqrt{n}$.<\/em><\/p>\n

\nProof.<\/em> Each lattice point $\\lambda$ is the center of
\na square $S_{\\lambda}$ of side $1$. These squares tile the plane. Let
\n$R_{in}(n)$ be the number of those squares fully contained in the disk
\nof radius $\\sqrt{n}$, $R_{out}(n)$ the number of those
\nhaving a point in common with it. As the following figures
\nshow, the squares inside the disk cover
\nthe disk of radius $\\sqrt{n} – \\sqrt{2}$, while those in the second group
\nare contained in the disk of radius $\\sqrt{n} + \\sqrt{2}$. <\/p>\n

\n\"Highlights
\n\"Highlights
\n<\/figure>\n

\n

\nTherefore<\/p>\n

$$ \\pi(\\sqrt{n} – \\sqrt{2})^{2} \\le R_{in}(n)
\n\t\\le R_{2}(n) \\le R_{out}(n) \\le \\pi(\\sqrt{n} + \\sqrt{2})^{2} $$<\/p>\n

\nor<\/p>\n

$$ | R_{in}(n) – \\pi n | \\le 2 \\pi (\\sqrt{2} \\sqrt{n} + 1) \\, . $$<\/p>\n

\nThis was apparently first observed by the
\n nineteenth mathematician Carl Friedrich Gauss, who constructed the
\ntable below.<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n
$R^{2}$<\/td>\n$N(R) $<\/td>\n$R^{2}$<\/td>\n$N(R)$<\/td>\n$R^{2}$<\/td>\n$N(R)$<\/td>\n<\/tr>\n
100 <\/td>\n 317 <\/td>\n 1000 <\/td>\n 3149 <\/td>\n 10000 <\/td>\n 31417 <\/td>\n<\/tr>\n
200 <\/td>\n 633 <\/td>\n 2000 <\/td>\n 6293 <\/td>\n 20000 <\/td>\n 62845 <\/td>\n<\/tr>\n
300 <\/td>\n 949 <\/td>\n 3000 <\/td>\n 9425 <\/td>\n 30000 <\/td>\n 94237 <\/td>\n<\/tr>\n
400 <\/td>\n 1257 <\/td>\n 4000 <\/td>\n 12581 <\/td>\n 40000 <\/td>\n 125629 <\/td>\n<\/tr>\n
500 <\/td>\n 1581 <\/td>\n 5000 <\/td>\n 15705 <\/td>\n 50000 <\/td>\n 157093 <\/td>\n<\/tr>\n
600 <\/td>\n 1885 <\/td>\n 6000 <\/td>\n 18853 <\/td>\n 60000 <\/td>\n 188453 <\/td>\n<\/tr>\n
700 <\/td>\n 2209 <\/td>\n 7000 <\/td>\n 21993 <\/td>\n 70000 <\/td>\n 219901 <\/td>\n<\/tr>\n
800 <\/td>\n 2521 <\/td>\n 8000 <\/td>\n 25137 <\/td>\n 80000 <\/td>\n 251305 <\/td>\n<\/tr>\n
900 <\/td>\n 2821 <\/td>\n 9000 <\/td>\n 28269 <\/td>\n 90000 <\/td>\n 282697 <\/td>\n<\/tr>\n
1000 <\/td>\n 3149 <\/td>\n 10000 <\/td>\n 31417 <\/td>\n 100000 <\/td>\n 314197 <\/td>\n<\/tr>\n<\/table>\n

\nIncidentally, Gauss told us what formula he used for these calculations.
\nRecall that $\\lfloor x \\rfloor$ is the largest integer
\nbelow or equal to $x$.
\nBecause of symmetry properties of the circle,
\nthe number of lattice points in the disk is
\n$1$ plus $4$ times the number in the region
\n$b \\ge 1$, $0 \\le a^{2} \\le n-b^{2}$. So<\/p>\n

$$ R_{2}(n) = 1 + 4 \\, {\\sum}_{b^{2} \\le n}
\n\t\\Big( 1 + \\big \\lfloor \\sqrt{n – b^{2}} \\big \\rfloor \\Big) \\, . $$<\/p>\n

The amount of work is proportional to $\\sqrt{n}$, and Gauss’ table
\nrepresents an impressive amount of effort.<\/p>\n

\nGauss’ result is that the discrepancy is of order at most $\\sqrt{n}$.
\nHow good is this estimate?<\/p>\n

\nThe number $R_{2}(n)$ is the same as the number of those unit
\nsquares centred at lattice
\npoints inside the disk of radius $\\sqrt{n}$. But the relation between
\nthe location of a lattice point and how its unit square
\nintersects the disk is a bit complicated. In the following figure
\nthe blue areas represent those pieces of squares centred at
\nlattice points inside the disk that are not themselves in the disk.<\/p>\n

\n\"Portions
\n<\/figure>\n

\nThe blue regions represent how lattice points
\noverestimate the area of the disk.
\nBut they are complemented by the pink areas,
\nwhich are in squares centred outside the disk
\nbut still touch it. They contribute to
\nan underestimate of the area. At least visually, the two colored regions
\nroughly cancel out. This means that Gauss’ bound on $\\Delta$ is pessimistic.
\nHow far off is it? With computers we can look at larger numbers than Gauss.
\nHere are some more values:<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
$n$<\/th>\n$R_{2}(n)$<\/th>\n$\\Delta(n)$<\/th>\n<\/tr>\n
$10^{1}$<\/td>\n37<\/td>\n-6<\/td>\n<\/tr>\n
$10^{2}$<\/td>\n317<\/td>\n-3<\/td>\n<\/tr>\n
$10^{3}$<\/td>\n3149<\/td>\n-7<\/td>\n<\/tr>\n
$10^{4}$<\/td>\n31417<\/td>\n-1<\/td>\n<\/tr>\n
$10^{5}$<\/td>\n314197<\/td>\n-38<\/td>\n<\/tr>\n
$10^{6}$<\/td>\n3141549<\/td>\n44<\/td>\n<\/tr>\n
$10^{7}$<\/td>\n31416025<\/td>\n-98<\/td>\n<\/tr>\n
$10^{8}$<\/td>\n314159053<\/td>\n212<\/td>\n<\/tr>\n
$10^{9}$<\/td>\n3141592409<\/td>\n245<\/td>\n<\/tr>\n
$10^{10}$<\/td>\n31415925457<\/td>\n1079<\/td>\n<\/tr>\n
$10^{11}$<\/td>\n314159264029<\/td>\n1330<\/td>\n<\/tr>\n
$10^{12}$<\/td>\n3141592649641<\/td>\n3949<\/td>\n<\/tr>\n
$10^{13}$<\/td>\n31415926532017<\/td>\n3881<\/td>\n<\/tr>\n
$10^{14}$<\/td>\n314159265350589<\/td>\n8390<\/td>\n<\/tr>\n
$10^{15}$<\/td>\n3141592653588541<\/td>\n1252<\/td>\n<\/tr>\n
$10^{16}$<\/td>\n31415926535867977<\/td>\n29955<\/td>\n<\/tr>\n
$10^{17}$<\/td>\n314159265358987341<\/td>\n-8017<\/td>\n<\/tr>\n
$10^{19}$<\/td>\n31415926535897744689<\/td>\n187696<\/td>\n<\/tr>\n
$10^{20}$<\/td>\n314159265358978759705<\/td>\n564141<\/td>\n<\/tr>\n<\/table>\n

\nBased on what this list shows,
\none would guess that $\\Delta(n)$ is of order
\n$n^{1\/4}$. It is this guess that mathematicians, in
\ntwo hundred years of work, have neither confirmed nor contradicted.<\/p>\n

A short history<\/h1>\n

At the beginning of the twentieth century
\nthe Polish mathematician
\n Wac\u0142aw Sierpinski, just beginning an extremely productive career,
\n proved that the discrepancy is of order at most
\n$n^{1\/3}$. His methods followed very closely
\nearlier work by the Ukrainian mathematician
\nGeorgy Voronoi on a related problem
\nabout hyperbolas rather than circles.
\n(Voronoi had been his advisor in Warsaw.)
\n The English mathematician
\nG. H. Hardy proved that
\n$n^{1\/4}$ is a lower bound for the order of the discrepancy,
\nand conjectured that this is in fact the true upper bound as well.<\/p>\n

\nMuch work has been spent on this conjecture in the past century,
\nbut in spite of much talented effort there has been
\nlittle reward. The sophistication of the mathematics involved is impressive.
\nI am not sure what the best current
\nproven estimate is, but a typical value is
\norder $n^{r}$ for $r = 131\/416 \\sim 0.3149$,
\npublished in 2003 by Martin Huxley.<\/p>\n

An exact formula<\/h2>\n

There is actually an exact formula for $R_{2}(n)$.
\nIt was conjectured by
\nVoronoi in 1905 and, after a few false starts,
\n proved by Hardy and Edmund Landau around 1923.
\nIt has some peculiar features,
\nand in some ways is more of a tease than a
\nmagic key.
\nBut it has played a role in many of the known estimates of $\\Delta(n)$.
\nThis formula is not at all elementary,
\nand involves some higher mathematics.
\nI’ll first state it, then look at a simple model
\nthat illustrates nicely some of its difficulties.<\/p>\n

\nThe Bessel function<\/b> $J_{n}(x)$ is defined by its Taylor series at $x = 0$:<\/p>\n

$$ J_{n}(x) = {\\sum}_{i} { (-1)^{i} \\over i! (n + i)! }
\n\t\\left ( { x \\over 2 } \\right)^{2i + n} \\, ,
\n$$<\/p>\n

\nThis series converges for all $x$, although there are practical problems in
\nusing it for computation, because of cancellation effects.
\nHowever, it will give you absolutely no idea
\nof their important properties, or why they are interesting.
\nThe Taylor series tells us how to calculate Bessel functions for $|x|$ small;
\n we also have a good idea of what they look like in the opposite case—when $|x|$ is large $J_{n}(x)$ differs very little from<\/p>\n

$$ \\sqrt{ \\left ( {2 \\over \\pi x} \\right )}
\n\t\\cos \\left ( x – { (2n+1) \\pi \\over 4 } \\right ) \\, . $$<\/p>\n

\nIt is oscillating and slowly decreasing
\nwhen $|x|$ is large.<\/p>\n

\nLet $\\Lambda$ be the set of lattice points $(a, b)$ in ${\\Bbb R}^{2}$.
\nLet $\\overline{R}_{2}(n)$ be a slight modification of $R_{2}(n)$:<\/p>\n

$$ \\overline{R}_{2}(n) = {\\sum}_{\\lambda} \\chi_{n}(\\lambda) $$<\/p>\n

\nwhere<\/p>\n

$$ \\chi_{n}(x,y) = \\cases {
\n\t\\kern3pt 1 & if $x^{2} + y^{2} < n$ \\cr
\n\t1\/2 & if $x^{2} + y^{2} = n$ \\cr
\n\t\\kern3pt 0 & otherwise. \\cr
\n} $$<\/p>\n

\nThat is to say, lattice points on the
\ncircle $|v|^{2} = n$ are counted as $1\/2$.
\nThe quantity $\\overline{R}_{2}$
\n differs little
\nfrom $R_{2}$, but has some useful properties.
\nThe formula of Hardy and Wright is that<\/p>\n

$$ \\eqalign {
\n\\overline{R}_{2}(n) &= \\pi n
\n+ \\sqrt{n} \\, {\\sum}_{\\lambda \\ne 0}
\n\t{ J_{1}(2 \\pi |\\lambda| \\sqrt{n}) \\over |\\lambda| } \\cr
\n\t&= \\pi n
\n+ \\sqrt{n} \\, {\\sum}_{m \\ne 0} r_{2}(m)
\n\t{ J_{1}(2 \\pi \\sqrt{mn}) \\over \\sqrt{m} } \\, . \\cr
\n} $$ <\/p>\n

\nWell … this looks promising. Especially if one
\nkeeps in mind the asymptotic behaviour of $J_{1}$. This tells us that each individual term is of order $n^{1\/4}$.
\nBut that is an illusion. The series does not converge
\nuniformly, but only conditionally, and
\none can derive from it no really good
\nestimate of $\\overline{R}_{2}(n)$.
\nIt has turned out not to be useless,
\nbut it is not easy to apply.<\/p>\n

\nI’ll not say more about this formula, but try to
\ngive you some idea of the problems that arise
\nby looking at a simple model that we can
\nunderstand thoroughly.<\/p>\n

\nIt involves a one-dimensional analogue of $R_{2}(n)$.
\nFor the moment, suppose $f$ to
\nbe a function on ${\\Bbb R}$ of bounded support and twice differentiable.
\nThe function<\/p>\n

$$ F(x) = {\\sum}_{m} f(x + m) $$<\/p>\n

\nwill be invariant under translations by integers,
\nand can be expressed in terms of its Fourier series:<\/p>\n

\n$$ F(x) = {\\sum}_{m} \\widehat{F}(m) e^{2 \\pi i mx } $$<\/p>\n

\nwhere<\/p>\n

$$ \\widehat{F}(m)
\n\t= \\int_{0}^{1} F(x) e^{-2 \\pi i mx} \\, dx
\n\t= \\int_{{\\Bbb R}} f(x) e^{-2 \\pi i m x} \\, dx \\, .
\n$$<\/p>\n

\nIn particular,<\/p>\n

$$ {\\sum}_{i} f(i)
\n\t= {\\sum}_{j} \\widehat{F}(j) \\, . $$<\/p>\n

This is the summation<\/b> formula.<\/p>\n

\nUnfortunately, we want to use a formula
\nlike this when $f$ is of bounded support, but not necessarily continuous.
\nLet<\/p>\n

$$ \\chi_{\\nu}(x) = \\cases {
\n\t\\kern 3 pt 1 & if $|x| < \\nu$ \\cr
\n\t1\/2 & if $|x| = \\nu$ \\cr
\n\t\\kern 4 pt 0 & otherwise. \\cr
\n} $$<\/p>\n

\nIt is discontinous at $\\pm \\nu$.
\nIs the summation formula valid for $\\chi_{\\nu}$?
\nIf $k$ is an integer then\n<\/p>\n

$$ \\overline{\\chi}_{\\nu}(k) = \\cases {
\n\t2k & if $|k| = \\nu$ \\cr
\n\t2k+1 & if $k < x < k+1$ \\cr
\n}
\n$$<\/p>\n

$$ \\widehat{\\chi}_{\\nu}(m) =
\n\\int_{-\\nu}^{\\nu} \\, e^{-2 \\pi m x} \\, dx
\n$$<\/p>\n

If $m=0$ this is $2\\nu$, and
\notherwise:<\/p>\n

$$
\n\\eqalign {
\n\\left[ { e^{-2\\pi i m x} \\over -2 \\pi i m } \\right ]^{\\nu}_{-\\nu}
\n\t& = { e^{-2\\pi i m\\nu} \\over -2 \\pi i m }
\n\t– { e^{2\\pi i m \\nu} \\over -2 \\pi i m \\nu} \\cr
\n\t&= { \\alpha^{m} – \\alpha^{-m} \\over -2 \\pi i m} \\cr
\n} $$<\/p>\n

if $\\alpha = e^{-2\\pi i \\nu}$.
\nThe terms are the same for $\\pm m$, so the sum is<\/p>\n

$$ \\eqalign {
\n{- 1 \\over \\pi i } {\\sum}_{m > 0}
\n\t{ \\alpha^{m} \\over m }
\n\t– {-1 \\over \\pi i } {\\sum}_{m > 0} { \\alpha^{-m} \\over m }
\n\t& = {-1 \\over \\pi i } \\left ( \\log(1 + \\alpha) – \\log(1 + \\alpha^{-1}) \\right) \\cr
\n\t& = {-1 \\over \\pi i } \\log\\left ( { 1 + \\alpha\\phantom{^{-1}} \\over 1 + \\alpha^{-1} } \\right ) \\, . \\cr
\n} $$<\/p>\n

\nas long as $\\alpha \\ne 1$.
\nBut<\/p>\n

$$ { 1 + \\alpha \\over 1 + \\alpha^{-1} } = \\alpha $$<\/p>\n

so that this becomes<\/p>\n

$$ {1 \\over \\pi i } \\log \\alpha $$<\/p>\n

but $\\alpha = e^{2 \\pi i \\nu}$, $\\log \\alpha$ is $2 \\pi i \\nu$.<\/p>\n

Well, almost.
\nThe peculiar feature is that the series for $\\log (1 – z)$
\nconverges only for $|z| < 1$, whereas for us $|z|=1$.
\nAs $n$ varies, we keep crossing the line $[, \\infty)$,
\nand we have to change the branch of $\\log$.<\/p>\n

\nIncidentally the series we are dealing with does converge,
\nbut it is not so easy to verify this directly.
\nThe point is that as $\\nu$ approaches an integer,
\nthe convergence slows up. Of course it has to,
\nsince $\\chi_{\\nu}$ is not continuous. I do not have a
\nclear picture of how the series in the Hardy-Landau formula works.
\nAs far as I know,
\nthere is no really simple proof of their result.
\nModern mathematicians work with modifications of it.<\/p>\n

Loose ends<\/h2>\n

Curvature?<\/h3>\n

I find the picture<\/p>\n

\n\"Portions
\n<\/figure>\n

fascinating. It suggests that
\nthe basic problem is one of probability—how the location of a
\nlattice point and the orientation of its
\nattached square interact with the circle
\n$x^{2} + y^{2} = n$.
\nThe fact that the circle is curved also plays a role.
\nThis is a well known observation—see
\nan article by Alex Iosevich<\/a>.<\/p>\n

Computation<\/h3>\n

Gauss’ formula for $R_{2}(n)$ is easy to implement,
\nbecause there is a well known simple
\nalgorithm to compute integral square roots
\nwithout calling on real numbers.
\nBut it becomes very slow
\nfor large numbers. A faster one has been
\nproposed on the anonymous web site
\nI write, therefore I am<\/a>.
\nUnfortunately, the code found there uses
\nstandard floating point numbers of low precision and does not work
\nfor even reasonably large $n$. There are references to
\nfaster and more efficient code in comments, but none explicit.
\nThey are claimed to have run time
\nproportional to $n^{1\/3$. The main difference from Gauss’ method is that
\neach pass counts points in triangles instead of line segments.
\nIt would be nice to see a rigorous analysis.<\/p>\n

\nI have myself written a program that
\nfollows the suggestion of the anonymous site;
\nit computes $R_{2}(n)$
\nfor $n$ up to $10^{20}$, and I have posted it<\/a>.
\nIt does not take $n^{1\/3}$ run time,
\nbut is much faster than Gauss’ algorithm.<\/p>\n

Dirichlet’s problem<\/h3>\n

There has been much wotk on the analogue of Gauss’
\nproblem for hyperbolas $xy=n$, which the number of divisors of
\na positive integer replaces $r_{2}$. It was for this
\nproblem that Voronoi proved the $n^{1\/3}$ bound in his
\n1903 paper. Sierpinski followed his argument closely.
\nThe anonymous algorithm discussed above
\nfor the circle problem was first written by Richard Sladkey to
\ndeal with the hyperbolic case, and the basic idea
\nis derived from one of Voronoi’s ideas.<\/p>\n

Reading further<\/h2>\n