I was studying for my end-term examinations, and encountered this beautiful relation describing how the function which counts the number of divisors of the input behaves over at a large scale.
1. The Setup: Lattice Points
We want to estimate the average order of $d(n)$ by summing it up to $x$:
$$
\sum_{n \le x} d(n) = \sum_{n \le x} \sum_{d|n} 1
$$
By swapping the order of summation, we can view this as a sum over pairs $(q, d)$ such that $qd \le x$. Geometrically, this corresponds to counting the number of lattice points (points with integer coordinates) in the first quadrant lying under the hyperbola $qd = x$.
$$
\sum_{n \le x} d(n) = \sum_{d \le x} \sum_{q \le x/d} 1
$$
2. The Naive Approach
A straightforward summation yields a “weak” bound. If we simply sum the number of points on vertical lines $d=1, d=2, \dots$:
$$
\sum_{d \le x} \left\lfloor \frac{x}{d} \right\rfloor = x \sum_{d \le x} \frac{1}{d} + O(x)
$$
Using the harmonic series approximation $\sum \frac{1}{d} \approx \log x$, we get:
$$
\sum_{n \le x} d(n) = x \log x + O(x)
$$
While this shows the average order is $\log n$, the error term $O(x)$ is quite large. We can do better by exploiting the symmetry of the hyperbola.
3. Dirichlet’s Hyperbola Method
The region under $qd = x$ is symmetric about the line $q = d$. The line intersects the hyperbola at $(\sqrt{x}, \sqrt{x})$.
Instead of summing all the way to $x$, we can:
- Count points where $d \le \sqrt{x}$ (the region to the left of the intersection).
- Count points where $q \le \sqrt{x}$ (the region below the intersection).
- Subtract the square region $d, q \le \sqrt{x}$ (the overlap) to avoid double counting.
This gives us the identity:
$$
\sum_{n \le x} d(n) = 2 \sum_{d \le \sqrt{x}} \left\lfloor \frac{x}{d} \right\rfloor - \lfloor \sqrt{x} \rfloor^2
$$
4. Deriving the Asymptotic Formula
Now we apply standard estimates. Let $C$ be Euler’s constant. We use the approximation $\lfloor y \rfloor = y + O(1)$ and $\sum_{d \le y} \frac{1}{d} = \log y + C + O(1/y)$.
$$
\sum_{n \le x} d(n) = 2 \sum_{d \le \sqrt{x}} \left( \frac{x}{d} + O(1) \right) - (\sqrt{x} + O(1))^2
$$
$$
= 2x \sum_{d \le \sqrt{x}} \frac{1}{d} + O(\sqrt{x}) - (x + O(\sqrt{x}))
$$
$$
= 2x \left( \log \sqrt{x} + C + O\left(\frac{1}{\sqrt{x}}\right) \right) - x + O(\sqrt{x})
$$
Simplifying the $\log \sqrt{x}$ term to $\frac{1}{2} \log x$:
$$
= 2x \left( \frac{1}{2} \log x + C \right) - x + O(\sqrt{x})
$$
$$
= x \log x + 2Cx - x + O(\sqrt{x})
$$
5. Conclusion
Grouping the linear terms, we arrive at Dirichlet’s Divisor Problem formula:
$$
\sum_{n \le x} d(n) = x \log x + (2C - 1)x + O(\sqrt{x})
$$
This proves that the average number of divisors of $n$ is $\log n$.
Note: The error term $O(\sqrt{x})$ has been improved significantly over the last century (Voronoi, van der Corput, Kolesnik), but determining the optimal exponent $\theta$ such that the error is $O(x^\theta)$ remains an open problem in number theory.
peace. da1729
Reference
- Introduction to Analytic Number Theory by Tom M. Apostol