Two Classic Problems in Point-Counting

In this post, I’d like to discuss two classic problems in analytic number theory, the Gauss circle problem (GCP) and the Dirichlet divisor problem (DDP). These two problems ask similar questions: how well can we approximate the number of lattice points inside certain planar regions? (Namely, within the circle of radius $\sqrt{X}$ and below the hyperbola $xy=X$ .)

By introducing the arithmetic functions

$r_2(n) := \#\{(a,b) \in \mathbb{Z}^2 : a^2 + b^2 =n\}, \qquad d(n) := \#\{k \geq 1: k \mid n\},$

we can recast the GCP and the DDP in terms of error bounds for average order estimates. In this new language, our questions are as follows:

Question: Find the minimal $\alpha$ (resp. $\beta$ ) for which

(GCP) $\displaystyle\sum_{n \leq X} r_2(n) = \pi X+ O (X^{\alpha+\epsilon})$
(DDP) $\displaystyle\sum_{n \leq X} d(n) = X \log X+(2\gamma-1)X +O(X^{\beta+\epsilon})$

holds for any $\epsilon>0$ . (Here, $\gamma \approx .577$ is the Euler-Mascheroni constant.)

In each case, the leading terms are due to pioneering work by the eponymous mathematicians, who also showed (resp.) that $\alpha,\beta \leq \frac{1}{2}$ . The first improvement past the $\frac{1}{2}$ -barrier in the GCP and DDP was due to Sierpiński (in 1903), who showed that $\alpha,\beta \leq \frac{1}{3}$ . (These bounds are sometimes credited to Voronoi, Sierpiński’s advisor, with the year 1906.)

Bounds have steadily improved ever since, with progress towards the GCP occurring in lockstep with progress towards the DDP. The current bounds (both due to Huxley, 2003) give $\alpha, \beta \leq 131/416 \approx .3149$ , and well-supported conjectures anticipate that $\alpha = \beta = \frac{1}{4}$ should be the correct exponents.

There are some superficial reasons why progress towards the GCP and the DDP should be related (eg. circles and hyperbolas are both plane conics), but it appears that a deeper connection was not realized until the work of Sierpiński and Voronoi in the early twentieth century. (Very briefly, their techniques apply Poisson summation to transform the partial sums above into a form that makes the analogy clearer.)

A second connection would have to wait until the development of automorphic forms over the next two decades. In this context, the circle and divisor problems can be posed as estimates for partial sums of coefficients of theta functions and powers of the Riemann zeta function, respectively.

Perhaps the connection between the GCP and the DDP would have been realized sooner if the initial bounds (due to Gauss and Dirichlet, respectively) in each problem had been derived using similar techniques. Indeed, Gauss’ estimate amounts to estimating the area of a narrow annulus, while Dirichlet’s estimate relies upon what has become known as the Dirichlet hyperbola method. [This has been discussed in an earlier post on this site.]

In essence, the hyperbola method takes advantage of the $xy$ -symmetry of the hyperbola $xy=X$ to convert a sum of length $O(X)$ into one of length $O(\sqrt{X})$ . (Not-so-coincidentally, the work of Sierpiński and Voronoi converts these sums into dual sums of length $O(X^{1/3})$ .)

Since circles $x^2+y^2 = X$ have $xy$ -symmetry as well, it seems reasonable to suppose that a Dirichlet-style hyperbola trick could derive the Gauss bound of $O(\sqrt{X})$ in the GCP. As it happens, this can be done, but there is little reason to do so, since the sums involved in estimating the GCP by counting lattice points in rows are already of length $O(\sqrt{X})$ .

To see the comparison explicitly, consider the hyperbola-style decomposition

$\displaystyle\sum_{n \leq X} r_2(n) = 1 + 8\!\sum_{y \leq \sqrt{X/2}}\bigg(\sum_{x =1}^{\sqrt{X-y^2}} \!\!1 -\sum_{x\leq y} 1 \bigg)+4\!\sum_{d\leq \sqrt{X/2}}\! 1+4\sum_{d\leq \sqrt{X}} 1,$

as well as the Riemann-sum-style decomposition

$\displaystyle\sum_{n \leq X} r_2(n) = 1+4\!\sum_{x \leq \sqrt{X}} \sum_{y =1}^{\sqrt{X-x^2}} \!\!1 +4\! \sum_{x \leq \sqrt{X}}\! 1 = 4\sum_{x \leq \sqrt{X}} \!\sqrt{X-x^2} + O(\sqrt{X}).$

Both formulas can be used to prove the Gauss bound, but the second is obviously simpler. Either way, we have accomplished what we set out to do: replace a sum of length $X$ with one of length $\sqrt{X}$ .

To estimate the sum that remains, we replace $\sqrt{1-x^2/X}$ with its Taylor series and interchange the order of summation. It follows that

$\displaystyle\sum_{n \leq X} r_2(n) =4\sqrt{X}\sum_{k=0}^\infty \binom{1/2}{k} \frac{(-1)^k}{X^k}\sum_{x\leq \sqrt{X}} x^{2k} + O(\sqrt{X}).$ (1)

To estimate the inner sum above, we apply the Riemann sum estimates

$\displaystyle\frac{\lfloor \sqrt{X} \rfloor^{2k+1}}{2k+1} = \int_0^{\lfloor \sqrt{X} \rfloor} t^{2k} dt \leq \sum_{x \leq \sqrt{X}} x^{2k} \leq \int_0^{\lfloor \sqrt{X} \rfloor +1} t^{2k} dt =\frac{(\lfloor \sqrt{X} \rfloor +1)^{2k+1}}{2k+1}$

to show that that the sum over $x \leq \sqrt{X}$ in (1) is $X^{k+1/2}/(2k+1) + O (X^{k})$ . Taking into account the sum over our error terms, we conclude that

$\displaystyle\sum_{n \leq X} r_2(n) = 4 X \sum_{k=0}^\infty \binom{1/2}{k} \frac{(-1)^k}{2k+1} + O(\sqrt{X}).$

The series that remains is a special value (at $z=1$ ) in the Taylor series for an anti-derivative of $\sqrt{1-z^2}$ , namely

$f(z) := \displaystyle\int_0^z \sqrt{1-t^2} \,dt = \frac{z\sqrt{1-z^2}+\arcsin(z)}{2},$

which gives at last the Gauss estimate:

$\displaystyle\sum_{n \leq X} r_2(n) = 4f(1) X+ O(\sqrt{X}) = \pi X + O(\sqrt{X}).$

— EXERCISES —

Exercise 1: Using the hyperbola method, show that

$\displaystyle\sum_{n \leq X} r_2(n) = -2X + 4\sqrt{2}X \sum_{k=0}^\infty \binom{1/2}{k} \frac{(-1)^k}{2^k(2k+1)} + O(\sqrt{X})$

and use this to recover the Gauss bound. Which method gives a better effective constant in the error term?

Exercise 2: Pick’s Theorem (1899) gives a formula for calculating the area of a (simple) polygon with vertices on a lattice. This formula reads

$A= i+b/2-1,$

in which $A$ is the area, $i$ is the number of interior lattice points, and $b$ is the number of lattice points on the boundary of the polygon.

Apply Pick’s Theorem to the convex hull of the collection of lattice points in a circle of radius $\sqrt{X}$ to prove the Gauss bound. Similarly (and slightly harder), show that Pick’s Theorem implies Dirichlet’s $O(\sqrt{X})$ bound.

a. w. walker

mathematics and miscellany

Two Classic Problems in Point-Counting

Leave a Reply Cancel reply

Share this:

Like this:

Leave a Reply Cancel reply