Dirichlet's Divisor Problem

How large is $\tau(1) + \tau(2) + \cdots + \tau(n)$?

Individual divisor counts $\tau(k)$ jump erratically — $\tau(p) = 2$ for primes, $\tau(12) = 6$, $\tau(1024) = 11$. There is no clean formula for $\tau(k)$.

But the sum is smooth. Averaging washes out the fluctuations. Dirichlet found the precise asymptotic in 1849, and it is one of the most beautiful results in elementary analytic number theory.

---

The main theorem

Theorem (Dirichlet, 1849). Let $D(n) = \displaystyle\sum_{k=1}^{n} \tau(k)$. Then:

$D(n) = n\ln n + (2\gamma - 1)n + O(\sqrt{n})$

where $\gamma \approx 0.5772\ldots$ is the Euler-Mascheroni constant.

Equivalently: the average number of divisors of integers up to $n$ is $\ln n + (2\gamma - 1) + O(1/\sqrt{n})$.

---

The proof — two steps

Step 1: Lattice point reformulation

From Counting Lattice Points:

$D(n) = \sum_{k=1}^{n}\tau(k) = \#\{(a,b) \in \mathbb{Z}^2 : a,b \geq 1,\ ab \leq n\}$

Each pair $(a,b)$ with $ab \leq n$ corresponds to a divisor $a$ of some $k = ab \leq n$.

Step 2: Count using symmetry

Let $m = \lfloor\sqrt{n}\rfloor$. Split the region $ab \leq n$ by the diagonal $a = b$:

$D(n) = 2\sum_{a=1}^{m}\left\lfloor\frac{n}{a}\right\rfloor - m^2$

Now approximate $\lfloor n/a \rfloor \approx n/a$:

$\sum_{a=1}^{m}\left\lfloor\frac{n}{a}\right\rfloor = n\sum_{a=1}^{m}\frac{1}{a} - \sum_{a=1}^{m}\left\{\frac{n}{a}\right\}$

where $\{x\}$ is the fractional part. The second sum is $O(m) = O(\sqrt{n})$ since each term is in $[0,1)$.

Using $H_m = \ln m + \gamma + O(1/m)$ and $m = \sqrt{n} + O(1)$:

$\sum_{a=1}^{m}\frac{1}{a} = \ln\sqrt{n} + \gamma + O(1/\sqrt{n}) = \frac{1}{2}\ln n + \gamma + O(1/\sqrt{n})$

Therefore:

$2\sum_{a=1}^{m}\left\lfloor\frac{n}{a}\right\rfloor = 2n\!\left(\frac{1}{2}\ln n + \gamma\right) + O(\sqrt{n}) = n\ln n + 2\gamma n + O(\sqrt{n})$

Subtracting $m^2 = n + O(\sqrt{n})$:

$D(n) = n\ln n + 2\gamma n - n + O(\sqrt{n}) = n\ln n + (2\gamma-1)n + O(\sqrt{n})$

$\blacksquare$

---

The error term — the open problem

Dirichlet showed the error is $O(\sqrt{n})$. In 1903, Voronoï improved this to $O(n^{1/3}\log n)$.

The conjecture — called the Dirichlet Divisor Conjecture — is that the error is $O(n^{1/4+\varepsilon})$ for any $\varepsilon > 0$.

The lower bound $\Omega(n^{1/4})$ is known — the error is at least this large infinitely often.

The best upper bound (Huxley, 2003): $O(n^{131/416})$ where $131/416 \approx 0.3149$.

The gap between $0.25$ (conjecture) and $0.3149$ (best known) has not closed in over 20 years.

---

Why $2\gamma - 1$?

The constant $2\gamma - 1 \approx 0.1544$ arises from two sources:

• $2\gamma$: from the harmonic sum approximation, with the Euler-Mascheroni constant appearing twice (once from each side of the symmetry argument)
• $-1$: from subtracting $m^2 \approx n$

The fact that $\gamma$ appears here — the same constant that measures the gap between $H_n$ and $\ln n$ — is not a coincidence. Both come from approximating a discrete sum by a continuous integral over $1/x$.

---

Consequences and connections

Average divisor count. $\tau(1) + \cdots + \tau(n))/n \sim \ln n$. A typical integer near $n$ has about $\ln n$ divisors.

Highly composite numbers. Numbers with unusually many divisors (like 12, 24, 60, 120...) are the outliers — they pull the average up. Most numbers near them have far fewer divisors.

Connection to Riemann zeta function. The Dirichlet series:

$\sum_{n=1}^{\infty} \frac{\tau(n)}{n^s} = \zeta(s)^2$

where $\zeta(s) = \sum n^{-s}$ is the Riemann zeta function. The divisor problem is equivalent to understanding the behavior of $\zeta(s)^2$ near $s=1$.

The Riemann Hypothesis (on the zeros of $\zeta$) would imply the Dirichlet Divisor Conjecture — but neither is proved.

---

Worked problems

Problem 1. Verify Dirichlet's formula for $n = 10$.

$D(10) = 27$ (computed earlier).

Formula: $10\ln 10 + (2\times 0.5772 - 1)\times 10 = 23.026 + 1.544 = 24.57$.

Error: $27 - 24.57 = 2.43$. And $\sqrt{10} \approx 3.16$. Error is well within $O(\sqrt{n})$. ✓

Problem 2. Estimate the number of $(a,b,c)$ triples with $abc \leq n$.

Generalizing: $\#\{abc \leq n\} = \sum_{k=1}^{n} \tau_3(k)$ where $\tau_3(k)$ counts ordered triples $(a,b,c)$ with $abc = k$.

By a similar lattice point argument: $\sum_{k=1}^{n}\tau_3(k) \sim \frac{n}{2}(\ln n)^2$.

Problem 3. Show that $\tau(n) = O(n^\varepsilon)$ for any $\varepsilon > 0$.

For any fixed $\varepsilon > 0$, $\tau(n) < n^\varepsilon$ for all sufficiently large $n$. (The divisor function grows slower than any power of $n$.)

Proof sketch. For $n = p_1^{a_1}\cdots p_k^{a_k}$: $\tau(n) = \prod(a_i+1)$. Each factor $(a_i+1) \leq 2a_i$ for $a_i \geq 1$, and $a_i \leq \log_2 n$. The number of prime factors $k \leq \log_2 n$. So $\tau(n) \leq 2^k \leq 2^{\log_2 n} = n$. With more careful bounds, $\tau(n) = O(n^\varepsilon)$. $\blacksquare$

Problem 4. If $\tau(n) = n/10$, what can you say about $n$?

From $\tau(n) = O(n^\varepsilon)$, $\tau(n)$ grows much slower than $n$. So $\tau(n) = n/10$ is impossible for large $n$. Checking small values: the equation $\tau(n) = n/10$ would require $n = 10$ with $\tau(10)=4 \neq 1$, $n=20$ with $\tau(20)=6\neq 2$... no solutions exist beyond trivial cases.

---

The thread so far

$\text{floor function} \to \text{lattice points} \to \text{hyperbola area} \to \text{median paradox} \to \text{Dirichlet's theorem}$

Each page in this thread answered one question and raised the next. The floor function counted multiples. Lattice points connected counting to geometry. The hyperbola's area gave the logarithm. The median showed the skewness concretely. Dirichlet's theorem gave the precise asymptotic.

The open question — how sharp is the error $O(\sqrt{n})$ — remains. The answer, if it comes, will require tools from complex analysis far beyond this thread.