21.11.02 · number-theory / dirichlet-series-arithmetic-functions

Average Orders of Arithmetic Functions and the Summation Toolkit

shipped3 tiersLean: none

Anchor (Master): Montgomery-Vaughan 2007 *Multiplicative Number Theory I: Classical Theory* (Cambridge SMM 97) §2 (summation methods, the hyperbola method, the divisor problem); Dirichlet 1849 *Abhandlungen Berlin* (the original hyperbola method and the $\sqrt{x}$ error term); Iwaniec-Kowalski 2004 *Analytic Number Theory* (AMS Colloquium 53) Ch. 1; Titchmarsh-Heath-Brown 1986 *The Theory of the Riemann Zeta-Function* 2e (Oxford) Ch. 12 (the Dirichlet divisor problem and the exponent $\theta$)

Intuition Beginner

An arithmetic function like the divisor count $d (n)$ jumps around wildly. A prime has exactly two divisors; the very next number might have a dozen. There is no smooth formula for $d (n)$ at a single point. But if you stop asking about one value and instead ask about the running average — what is the typical number of divisors of a number near $n$ ? — the chaos smooths into a clean trend. Averaging tames an erratic function the way that watching a noisy thermometer over a whole day reveals a temperature curve you could never read off one flickering instant.

The tool for this is the summatory function: instead of $d (n)$ , study $D (x) = d (1) + d (2) + \dots$ up to $x$ , the total number of divisors of all numbers up to $x$ . The total grows smoothly even though each term does not, and dividing by $x$ gives the average. The remarkable answer is that a number near $x$ has about $lo g x$ divisors on average. The logarithm appears because counting divisors is the same as counting points under a curve, and that count is dominated by a harmonic-series effect.

To get answers this precise you need a small kit of summing techniques. One swaps a sum for an integral plus a controlled correction. One reorganises a sum that runs over divisor pairs by splitting it cleverly in half. One re-weights a sum so a known average can be plugged in. These three moves — together with a bookkeeping language for "the error is no bigger than this" — are the whole toolkit, and they recur everywhere prime counting is done.

Visual Beginner

A picture of the grid of whole-number points $(a, b)$ in the first quadrant, with the curve $a \times b = x$ (a hyperbola) drawn through it. Counting the lattice points sitting under the hyperbola is the same as adding up the divisor counts: each point $(a, b)$ with $ab \leq x$ is one divisor pairing. The clever move is the diagonal line $a = b = x$ , which splits the under-curve region into two equal strips plus a square, so the count is done twice over a small region and corrected once — avoiding double work.

$x$	total $D (x)$ (divisors up to $x$ )	average $D (x) / x$	$lo g x$
$10$	$27$	$2.70$	$2.30$
$100$	$482$	$4.82$	$4.61$
$1000$	$7069$	$7.07$	$6.91$

The average $D (x) / x$ tracks $lo g x$ and runs a little above it; the gap is the constant $2 γ - 1 \approx 0.154$ that the precise formula pins down.

Worked example Beginner

Estimate the partial sum of the harmonic series and see the constant $γ$ emerge — the single fact that powers every average order below.

Step 1. Add the first reciprocals directly. Take $x = 4$ : the sum $1 + 1/2 + 1/3 + 1/4 = 1 + 0.5 + 0.333 + 0.25 = 2.083$ .

Step 2. Compare with $lo g x$ . Here $lo g 4 = 1.386$ . The sum overshoots the logarithm by $2.083 - 1.386 = 0.697$ . That gap is not an error; it is converging to a fixed number.

Step 3. Push $x$ higher. At $x = 100$ the harmonic sum is $5.187$ and $lo g 100 = 4.605$ , a gap of $0.582$ . At $x = 1000$ the gap is $0.578$ . The gap is settling down to $γ = 0.5772 \dots$ , the Euler-Mascheroni constant.

Step 4. Read off the rule. The partial sum of the reciprocals up to $x$ is $lo g x + γ$ plus a tiny correction that shrinks like $1/ x$ . At $x = 1000$ that correction is about $0.0005$ , matching the observed drift.

What this tells us: a sum that grows without bound is captured exactly by a simple function ( $lo g x$ ) plus a universal constant ( $γ$ ) plus a vanishing remainder. This is the template for every average order — find the smooth main term, name the constant, and bound the leftover.

Check your understanding Beginner

Exercise (easy, multiple choice).

The Dirichlet hyperbola method speeds up a sum that runs over all factor pairs $(a, b)$ with $a \times b \leq x$ . What is the key trick that avoids double counting?

A. Counting only the pairs with $a < b$ and doubling
B. Splitting the region at the diagonal $a = b = x$ , summing both halves, and subtracting the overlap square
C. Replacing the sum by a single integral with no correction
D. Counting only prime values of $a$

Hint

The method sums over one variable while the other ranges freely, does this twice with the roles swapped, and removes the part counted in both passes.

Answer

B. The hyperbola method splits the under-curve region at $a = b = x$ : it sums $b$ for each small $a \leq x$ , sums $a$ for each small $b \leq x$ , and subtracts the $x \times x$ square counted in both passes. This replaces one sum to $x$ with two sums to $x$ , which is what produces the sharp $O (x)$ error. Option A mishandles the diagonal. Option C drops the correction that makes the estimate precise. Option D discards almost all the pairs.

Formal definition Intermediate+

Throughout, $x$ denotes a real variable tending to infinity, $γ = 0.5772 \dots$ the Euler-Mascheroni constant, and $⌊ t ⌋$ the floor of $t$ . For arithmetic functions the notation of 21.11.01 is in force: $d = 1 * 1$ , $σ = N * 1$ , $φ = μ * N$ .

Definition (summatory function and average order). For an arithmetic function $f$ , the summatory function is $F (x) = \sum_{n \leq x} f (n)$ . A function $g$ is an average order of $f$ if $\sum_{n \leq x} f (n) \sim \sum_{n \leq x} g (n)$ as $x \to \infty$ ; informally, $f (n)$ "is on average of size $g (n)$ ." The big-O and asymptotic notation is standard: $h (x) = O (k (x))$ means $∣ h (x) ∣ \leq C k (x)$ for some constant $C$ and all large $x$ ; $h \sim k$ means $h / k \to 1$ ; and $h = o (k)$ means $h / k \to 0$ .

Definition (Abel summation / partial summation). Let $a : Z_{> 0} \to C$ with summatory function $A (t) = \sum_{n \leq t} a (n)$ , and let $ϕ$ be continuously differentiable on $[y, x]$ . Then $$ \sum_{y < n \le x} a(n),\phi(n) = A(x)\phi(x) - A(y)\phi(y) - \int_y^x A(t),\phi'(t),dt. $$ This is the discrete analogue of integration by parts: it trades the unknown weighted sum for a known summatory function $A$ tested against the smooth weight $ϕ$ ^{[Apostol Ch. 3]}.

Definition (Euler summation / Euler-Maclaurin, first order). If $ϕ$ is continuously differentiable on $[1, x]$ , then writing ${t} = t - ⌊ t ⌋$ for the fractional part, the leading instance reads in the convenient symmetric form $$ \sum_{n \le x} \phi(n) = \int_1^x \phi(t),dt + \tfrac{1}{2}\bigl(\phi(1) + \phi(x)\bigr) + \int_1^x \Bigl({t} - \tfrac12\Bigr)\phi'(t),dt, $$ the leading instance of the Euler-Maclaurin expansion whose higher remainders carry Bernoulli polynomials ^[Tenenbaum]. The remainder integral is $O (\int ∣ ϕ^{'} ∣)$ , which is small whenever $ϕ$ is slowly varying.

Definition (Dirichlet hyperbola method). For arithmetic functions $f, g$ and any $1 \leq y \leq x$ , with $h = f * g$ , $$ \sum_{n \le x} h(n) = \sum_{a \le y} f(a), G!\Bigl(\tfrac{x}{a}\Bigr) + \sum_{b \le x/y} g(b), F!\Bigl(\tfrac{x}{b}\Bigr) - F(y),G!\Bigl(\tfrac{x}{y}\Bigr), $$ where $F (t) = \sum_{a \leq t} f (a)$ , $G (t) = \sum_{b \leq t} g (b)$ . The optimal balance is $y = x$ , which symmetrises the two sums. The identity reorganises a sum over the lattice region ${ab \leq x}$ by summing one coordinate at a time and subtracting the doubly counted corner ^{[Dirichlet 1849]}.

Counterexamples to common slips

"An average order is the same as a pointwise asymptotic." No. $d (n)$ has average order $lo g n$ , yet $d (n) = 2$ infinitely often (at primes) and $d (n)$ is unbounded along other sequences. The average is a statement about $\sum_{n \leq x} d (n)$ , not about any single $d (n)$ .
"The error in $\sum_{n \leq x} d (n)$ is $O (lo g x)$ because of the harmonic main term." The genuine error is $O (x)$ , vastly larger than $lo g x$ . Naively summing $\sum_{n \leq x} d (n) = \sum_{n \leq x} ⌊ x / n ⌋$ term by term loses ${x / n}$ in each of $x$ terms; only the hyperbola split recovers $x$ .
" $\sum_{n \leq x} 1/ n \to γ$ ." The constant $γ$ is the limit of the difference $\sum_{n \leq x} 1/ n - lo g x$ , not the limit of the sum. The harmonic sum itself diverges.
"Abel summation needs $ϕ$ monotone." It needs only $ϕ \in C^{1}$ ; monotonicity is used in some error estimates but is not part of the identity.

Key theorem with proof Intermediate+

The signature theorem is the average order of the divisor function — the Dirichlet divisor problem in its classical form — proved by the hyperbola method. It is the cleanest demonstration that the summation toolkit converts an erratic arithmetic function into a smooth asymptotic with a sharp error.

Theorem (Dirichlet 1849). As $x \to \infty$ , $$ \sum_{n \le x} d(n) = x \log x + (2\gamma - 1),x + O(\sqrt{x}). $$

Proof. Two lemmas first. By Euler summation applied to $ϕ (t) = 1/ t$ , $$ \sum_{n \le x} \frac{1}{n} = \log x + \gamma + O!\Bigl(\frac{1}{x}\Bigr), \tag{1} $$ the constant $γ = lim_{x \to \infty} (\sum_{n \leq x} 1/ n - lo g x)$ being exactly the Euler-Mascheroni constant. Second, by counting integers in an interval, $$ \sum_{n \le t} 1 = \lfloor t \rfloor = t + O(1). \tag{2} $$

Now write $d = 1 * 1$ , so $\sum_{n \leq x} d (n) = \sum_{ab \leq x} 1$ , a count of lattice points under the hyperbola $ab \leq x$ . Apply the hyperbola identity with $f = g = 1$ , $F = G = ⌊ \cdot ⌋$ , and $y = x$ : $$ \sum_{n \le x} d(n) = 2 \sum_{a \le \sqrt x} \Bigl\lfloor \frac{x}{a} \Bigr\rfloor - \bigl\lfloor \sqrt x \bigr\rfloor^2. $$ Estimate each piece. By (2), $⌊ x / a ⌋ = x / a + O (1)$ , so $$ \sum_{a \le \sqrt x} \Bigl\lfloor \frac{x}{a} \Bigr\rfloor = x \sum_{a \le \sqrt x} \frac{1}{a} + O!\bigl(\sqrt x\bigr) = x\Bigl(\log \sqrt x + \gamma + O\bigl(\tfrac{1}{\sqrt x}\bigr)\Bigr) + O(\sqrt x), $$ using (1) with $x$ in place of $x$ . Since $lo g x = \frac{1}{2} lo g x$ , this is $\frac{1}{2} x lo g x + γ x + O (x)$ . Doubling gives $x lo g x + 2 γ x + O (x)$ . For the corner, $⌊ x ⌋^{2} = (x + O (1))^{2} = x + O (x)$ . Subtracting, $$ \sum_{n \le x} d(n) = \bigl(x\log x + 2\gamma x\bigr) - x + O(\sqrt x) = x\log x + (2\gamma - 1)x + O(\sqrt x), $$ which is the claim. $□$

Bridge. The hyperbola method builds toward 21.11.04 the Perron formula and Mellin inversion, where the same summatory function $\sum_{n \leq x} d (n)$ is recovered analytically as a contour integral of $ζ (s)^{2} x^{s} / s$ , and it appears again in 21.12.01 the prime number theorem, where $\sum_{n \leq x} Λ (n)$ is handled by the analytic continuation of $- ζ^{'} / ζ$ . The foundational reason the error is $O (x)$ and not $O (x)$ is exactly the factorisation $d = 1 * 1$ : a convolution lets the lattice count be split at the diagonal, and this is exactly the elementary shadow of the analytic identity $\sum d (n) n^{- s} = ζ (s)^{2}$ from 21.11.01. The construction generalises: every average order in this unit is the hyperbola or partial-summation evaluation of a convolution $f = g * h$ , so the convolution algebra of 21.11.01 is dual to the summation toolkit here. Putting these together, the average orders of $σ$ and $φ$ (Master tier below) drop out of $σ = N * 1$ and $φ = μ * N$ by the same two moves, and the bridge from the discrete convolution ring to the analytic theory of 21.03.01 runs through partial summation, which converts a Dirichlet series into its summatory function and back.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Prove the Abel summation formula: for $A (t) = \sum_{n \leq t} a (n)$ and $ϕ \in C^{1} [1, x]$ , $$ \sum_{n \le x} a(n)\phi(n) = A(x)\phi(x) - \int_1^x A(t)\phi'(t),dt. $$

Hint

Write $a (n) = A (n) - A (n - 1)$ and apply summation by parts, or integrate $ϕ^{'}$ over $[n, x]$ and swap the order of summation and integration.

Answer

Write $a (n) = A (n) - A (n - 1)$ for $n \geq 1$ (with $A (0) = 0$ ). Then $ϕ (n) = ϕ (x) - \int_{n}^{x} ϕ^{'} (t) d t$ , so $$ \sum_{n\le x} a(n)\phi(n) = \phi(x)\sum_{n\le x} a(n) - \sum_{n \le x} a(n)\int_n^x \phi'(t),dt = A(x)\phi(x) - \int_1^x \Bigl(\sum_{n \le t} a(n)\Bigr)\phi'(t),dt, $$ where the last step swaps the finite sum and the integral, since for fixed $t$ the term $a (n)$ contributes to the inner integral exactly when $n \leq t$ , replacing $\sum_{n \leq x} a (n) 1_{n \leq t}$ by $A (t)$ . This is the stated formula. Rubric: full credit for the telescoping $a (n) = A (n) - A (n - 1)$ and the order-swap with the indicator $n \leq t$ .

Exercise 4 (medium, symbolic).

Use Euler summation on $ϕ (t) = 1/ t$ to prove $\sum_{n \leq x} 1/ n = lo g x + γ + O (1/ x)$ , and express $γ$ as an integral.

Hint

Apply $\sum_{n \leq x} ϕ (n) = \int_{1}^{x} ϕ + \frac{1}{2} (ϕ (1) + ϕ (x)) + \int_{1}^{x} ({t} - \frac{1}{2}) ϕ^{'} (t) d t$ with $ϕ (t) = 1/ t$ , then let $x \to \infty$ in the bounded remainder.

Answer

With $ϕ (t) = 1/ t$ , $ϕ^{'} (t) = - 1/ t^{2}$ , and $\int_{1}^{x} d t / t = lo g x$ . Euler summation gives $$ \sum_{n \le x} \frac1n = \log x + \tfrac12\Bigl(1 + \tfrac1x\Bigr) - \int_1^x \frac{{t}-\tfrac12}{t^2},dt. $$ As $x \to \infty$ the integral converges absolutely (integrand $O (1/ t^{2})$ ), so $\sum_{n \leq x} 1/ n - lo g x \to \frac{1}{2} - \int_{1}^{\infty} \frac{{ t } - \frac{1}{2}}{t ^{2}} d t =: γ$ . The tail beyond $x$ is $\int_{x}^{\infty} O (t^{- 2}) d t = O (1/ x)$ , and the $\frac{1}{2 x}$ term is also $O (1/ x)$ , so $\sum_{n \leq x} 1/ n = lo g x + γ + O (1/ x)$ . A standard alternative form is $γ = 1 - \int_{1}^{\infty} {t} t^{- 2} d t$ . Rubric: full credit for the Euler-summation application, the convergent improper integral defining $γ$ , and the $O (1/ x)$ tail bound.

Exercise 5 (medium, symbolic).

Prove $\sum_{n \leq x} σ (n) = \frac{π ^{2}}{12} x^{2} + O (x lo g x)$ , using $σ = N * 1$ and $\sum_{m \geq 1} m^{- 2} = π^{2} /6$ .

Hint

Write $\sum_{n \leq x} σ (n) = \sum_{d m \leq x} m = \sum_{d \leq x} \sum_{m \leq x / d} m$ and use $\sum_{m \leq y} m = \frac{1}{2} y^{2} + O (y)$ .

Answer

Since $σ (n) = \sum_{d ∣ n} (n / d) = \sum_{d m = n} m$ , summing over $n \leq x$ groups by $d$ : $$ \sum_{n \le x}\sigma(n) = \sum_{d \le x}\ \sum_{m \le x/d} m = \sum_{d \le x}\Bigl(\tfrac12\bigl(x/d\bigr)^2 + O(x/d)\Bigr) = \tfrac{x^2}{2}\sum_{d \le x}\frac{1}{d^2} + O\Bigl(x\sum_{d\le x}\frac1d\Bigr). $$ The error is $O (x lo g x)$ by the harmonic estimate. For the main term, $\sum_{d \leq x} d^{- 2} = \sum_{d \geq 1} d^{- 2} - \sum_{d > x} d^{- 2} = π^{2} /6 + O (1/ x)$ , the tail bounded by $\int_{x}^{\infty} t^{- 2} d t = 1/ x$ . Hence the main term is $\frac{x ^{2}}{2} \cdot \frac{π ^{2}}{6} + O (x) = \frac{π ^{2}}{12} x^{2} + O (x)$ , and the overall error $O (x lo g x)$ dominates: $\sum_{n \leq x} σ (n) = \frac{π ^{2}}{12} x^{2} + O (x lo g x)$ . Rubric: full credit for the $σ = N * 1$ regrouping, the $ζ (2)$ tail, and the $O (x lo g x)$ error.

Exercise 7 (hard, symbolic).

Prove $\sum_{n \leq x} φ (n) = \frac{3}{π ^{2}} x^{2} + O (x lo g x)$ using $φ = μ * N$ and $\sum_{n \geq 1} μ (n) n^{- 2} = 1/ ζ (2) = 6/ π^{2}$ .

Hint

$φ (n) = \sum_{d ∣ n} μ (d) (n / d)$ , so $\sum_{n \leq x} φ (n) = \sum_{d \leq x} μ (d) \sum_{m \leq x / d} m$ . Insert $\sum_{m \leq y} m = \frac{1}{2} y^{2} + O (y)$ and extend the $μ$ -sum to infinity.

Answer

From $φ = μ * N$ , $φ (n) = \sum_{d m = n} μ (d) m$ , so $$ \sum_{n \le x}\varphi(n) = \sum_{d \le x}\mu(d)\sum_{m \le x/d} m = \sum_{d\le x}\mu(d)\Bigl(\tfrac12(x/d)^2 + O(x/d)\Bigr) = \tfrac{x^2}{2}\sum_{d \le x}\frac{\mu(d)}{d^2} + O\Bigl(x\sum_{d\le x}\frac1d\Bigr). $$ The error term is $O (x lo g x)$ since $∣ μ (d) ∣ \leq 1$ . For the main term, $\sum_{d \leq x} μ (d) d^{- 2} = \sum_{d \geq 1} μ (d) d^{- 2} - \sum_{d > x} μ (d) d^{- 2}$ ; the full sum is $1/ ζ (2) = 6/ π^{2}$ (the Dirichlet series $\sum μ (d) d^{- s} = 1/ ζ (s)$ from 21.11.01 at $s = 2$ ), and the tail is $O (1/ x)$ by comparison with $\int_{x}^{\infty} t^{- 2} d t$ . Therefore the main term is $\frac{x ^{2}}{2} \cdot \frac{6}{π ^{2}} + O (x) = \frac{3}{π ^{2}} x^{2} + O (x)$ , and the harmonic error dominates: $\sum_{n \leq x} φ (n) = \frac{3}{π ^{2}} x^{2} + O (x lo g x)$ . Rubric: full credit for the $μ * N$ regrouping, identifying $\sum μ (d) d^{- 2} = 1/ ζ (2)$ , the tail bound, and the dominant $O (x lo g x)$ error.

Exercise 8 (hard, symbolic).

Let $f$ have Dirichlet series $D (f; s) = \sum_{n \geq 1} f (n) n^{- s}$ converging for $Re (s) > σ_{a}$ , and let $F (x) = \sum_{n \leq x} f (n)$ . Use Abel summation to express $D (f; s)$ as a Mellin-type integral of $F$ , valid for $Re (s) > max (σ_{a}, σ_{c})$ where $F (x) = O (x^{σ_{c}})$ : $$ D(f; s) = s \int_1^\infty \frac{F(x)}{x^{s+1}},dx. $$

Hint

Apply Abel summation with $a (n) = f (n)$ , $ϕ (n) = n^{- s}$ , $ϕ^{'} (t) = - s t^{- s - 1}$ , on $[1, X]$ , then let $X \to \infty$ using $F (X) X^{- s} \to 0$ .

Answer

Abel summation with $A = F$ , $ϕ (t) = t^{- s}$ , $ϕ^{'} (t) = - s t^{- s - 1}$ on $[1, X]$ gives $$ \sum_{n \le X} f(n) n^{-s} = F(X)X^{-s} - \int_1^X F(t)\bigl(-s,t^{-s-1}\bigr)dt = F(X)X^{-s} + s\int_1^X \frac{F(t)}{t^{s+1}},dt. $$ For $Re (s) > σ_{c}$ the bound $F (X) = O (X^{σ_{c}})$ gives $F (X) X^{- s} = O (X^{σ_{c} - Re (s)}) \to 0$ as $X \to \infty$ , and the integral converges absolutely since $∣ F (t) t^{- s - 1} ∣ = O (t^{σ_{c} - Re (s) - 1})$ is integrable. Letting $X \to \infty$ , $$ D(f; s) = \sum_{n\ge1} f(n)n^{-s} = s\int_1^\infty \frac{F(x)}{x^{s+1}},dx. $$ This is the Dirichlet-series $\leftrightarrow$ summatory-function dictionary: $D (f; s) / s$ is the Mellin transform of $F$ , so the analytic behaviour of $D (f; s)$ (poles, growth) is read off from the asymptotics of $F$ and conversely — the inverse direction is the Perron formula of 21.11.04. Rubric: full credit for the Abel-summation evaluation, the vanishing boundary term, and identifying the result as the Mellin pairing $D (f; s) = s \int_{1}^{\infty} F (x) x^{- s - 1} d x$ .

Lean formalization Intermediate+

Mathlib supplies the analytic and combinatorial primitives, so the statements of this unit are expressible, but the assembled toolkit and the divisor average are not yet a named module. The companion notes record the load-bearing declarations against Mathlib.Analysis.SumOverResidues, Mathlib.NumberTheory.ArithmeticFunction, and Mathlib.Analysis.Asymptotics.Asymptotics.

-- Operative imports: Mathlib.NumberTheory.ArithmeticFunction
--   Mathlib.Analysis.Asymptotics.Asymptotics
--   Mathlib.Analysis.SpecialFunctions.Log.Basic
import Mathlib.NumberTheory.ArithmeticFunction
import Mathlib.Analysis.Asymptotics.Asymptotics
open ArithmeticFunction Asymptotics Filter

-- Big-O notation is `IsBigO` along a filter (here `atTop` on ℝ).
#check @Asymptotics.IsBigO
-- f =O[atTop] g  ↔  ∃ C, ∀ᶠ x in atTop, ‖f x‖ ≤ C * ‖g x‖

-- The divisor function d = ζ * ζ is `ArithmeticFunction.sigma 0`.
#check (ArithmeticFunction.sigma 0)
example : (ArithmeticFunction.sigma 0) = ζ * ζ := by
  ext n; simp [ArithmeticFunction.sigma_zero_apply, ArithmeticFunction.coe_zeta_mul_coe_zeta]
  -- d(n) = number of divisors = (ζ * ζ)(n)

-- Abel / partial summation is available as a finite-sum identity:
#check @Finset.sum_Ioc_by_parts
-- ∑ i in Ioc a b, f i * g i = ... (summation-by-parts rearrangement)

-- TARGET (not in Mathlib as a single lemma): the divisor average with √x error.
-- (∑ n in Finset.Icc 1 ⌊x⌋₊, (sigma 0) n : ℝ)
--   = x * Real.log x + (2 * eulerMascheroniConstant - 1) * x + O(Real.sqrt x)
-- stated via IsBigO over atTop, proved by the hyperbola split at √x.

-- The Euler-Mascheroni constant exists in Mathlib as `Real.eulerMascheroniConstant`.
#check Real.eulerMascheroniConstant

The gap named in Mathlib gap analysis is not the absence of floors, partial summation, or big-O — Mathlib has all three — but the absence of a single module that proves the Euler-Maclaurin remainder formula for general $C^{1}$ test functions, the hyperbola identity for convolutions, and the divisor/totient/sigma averages with their explicit constants $2 γ - 1$ , $3/ π^{2}$ , and $π^{2} /12$ , end to end and in one place.

Advanced results Master

Theorem 1 (the three classical averages). The summation toolkit yields, as $x \to \infty$ , $$ \sum_{n \le x} d(n) = x\log x + (2\gamma-1)x + O(\sqrt x), \quad \sum_{n \le x}\sigma(n) = \frac{\pi^2}{12}x^2 + O(x\log x), \quad \sum_{n \le x}\varphi(n) = \frac{3}{\pi^2}x^2 + O(x\log x). $$ Each is the hyperbola or regroup-and-extend evaluation of a convolution: $d = 1 * 1$ , $σ = N * 1$ , $φ = μ * N$ . The constants $π^{2} /12 = ζ (2) /2$ and $3/ π^{2} = 1/ (2 ζ (2))$ are values of $ζ$ at $s = 2$ , entering through $\sum_{d \geq 1} d^{- 2} = ζ (2)$ and $\sum_{d \geq 1} μ (d) d^{- 2} = 1/ ζ (2)$ from the Dirichlet-series dictionary of 21.11.01. The totient average has the probabilistic reading that two integers chosen up to $x$ are coprime with limiting probability $6/ π^{2} = 1/ ζ (2)$ , the density of squarefree numbers ^{[Apostol Ch. 3]}.

Theorem 2 (the Dirichlet divisor problem and the exponent $θ$ ). Write $Δ (x) = \sum_{n \leq x} d (n) - x lo g x - (2 γ - 1) x$ for the error term. Dirichlet's method gives $Δ (x) = O (x^{1/2})$ . The divisor problem is to determine the infimum $θ$ of exponents with $Δ (x) = O (x^{θ + ϵ})$ . Voronoi 1903 reduced the exponent to $1/3$ by a Bessel-function expansion of $Δ$ ; successive refinements (van der Corput $33/100$ , Kolesnik, Huxley 2003 $131/416 = 0.3149 \dots$ ) inch downward. The lower bound is fixed: Hardy 1916 proved $Δ (x) = Ω (x^{1/4})$ — indeed $Ω_{\pm} (x^{1/4})$ with a $(lo g x)^{1/4}$ refinement — so $θ \geq 1/4$ ^{[Hardy 1916]}. The conjecture $θ = 1/4$ remains open; the truth of the leading-order asymptotic is settled, only the size of the oscillation is not ^{[Titchmarsh Ch. 12]}.

Theorem 3 (full Euler-Maclaurin with Bernoulli remainder). For $ϕ \in C^{2 k} [a, b]$ with integer endpoints, $$ \sum_{n=a}^{b}\phi(n) = \int_a^b \phi(t),dt + \frac{\phi(a)+\phi(b)}{2} + \sum_{j=1}^{k}\frac{B_{2j}}{(2j)!}\bigl(\phi^{(2j-1)}(b) - \phi^{(2j-1)}(a)\bigr) + R_k, $$ with $R_{k} = - \int_{a}^{b} \frac{B _{2 k} ({ t })}{( 2 k )!} ϕ^{(2 k)} (t) d t$ , where $B_{2 j}$ are Bernoulli numbers and $B_{2 k} (\cdot)$ the Bernoulli polynomial. The first-order case ( $k = 0$ remainder) is the Euler summation of the formal definitions; pushing $k$ higher refines the harmonic constant $γ$ to arbitrary precision and yields the Stirling expansion $lo g n! = n lo g n - n + \frac{1}{2} lo g (2 π n) + \frac{1}{12 n} - \dots$ as the case $ϕ = lo g$ ^[Tenenbaum].

Theorem 4 (general hyperbola and the $k$ -fold divisor problem). The two-variable hyperbola identity extends to $k$ -fold convolutions. For $d_{k} = 1^{* k}$ (the number of ordered factorisations into $k$ parts, with Dirichlet series $ζ (s)^{k}$ ), partial summation against $ζ (s)^{k}$ gives $\sum_{n \leq x} d_{k} (n) = x P_{k - 1} (lo g x) + O (x^{1 - 1/ k + ϵ})$ , where $P_{k - 1}$ is a degree- $(k - 1)$ polynomial with leading coefficient $1/ (k - 1)!$ . The error exponent $α_{k} = 1 - 1/ k$ from the iterated hyperbola is the elementary benchmark; the analytic theory of 21.11.04 sharpens it via the moments of $ζ$ on the critical line ^{[Montgomery-Vaughan]}.

Theorem 5 (mean value of $μ$ and the prime number theorem). Partial summation links the summatory function $M (x) = \sum_{n \leq x} μ (n)$ (the Mertens function) to $1/ ζ (s)$ . The estimate $M (x) = o (x)$ is logically equivalent to the prime number theorem, and $M (x) = O (x^{1/2 + ϵ})$ is equivalent to the Riemann hypothesis. The summation toolkit alone gives only the size bound $M (x) = O (x)$ and $\sum_{n \leq x} μ (n) / n = O (1)$ by an elementary hyperbola argument; the genuine cancellation $M (x) = o (x)$ requires the analytic input of 21.12.01. This is the boundary of the elementary method: average orders of $d, σ, φ$ fall to summation, but the average of $μ$ — sign cancellation rather than size — does not ^{[Montgomery-Vaughan]}.

Synthesis. The summation toolkit is the foundational reason the convolution ring of 21.11.01 has analytic content: each average order is the evaluation of a convolution $f = g * h$ by partial summation or the hyperbola split, so the algebra of $*$ is dual to the analysis of $\sum_{n \leq x}$ . This is exactly the discrete shadow of the Mellin pairing $D (f; s) = s \int_{1}^{\infty} F (x) x^{- s - 1} d x$ of Exercise 8: the Dirichlet series encodes the same data as the summatory function, and partial summation is the isomorphism between them. The central insight is that the $ζ (2)$ constants $π^{2} /12$ and $3/ π^{2}$ in the $σ$ and $φ$ averages are not coincidences but the values $D (1; 2)$ and $D (μ; 2)$ read through the dictionary, so the appearance of $π$ in a count of coprime pairs generalises the Basel-problem appearance of $π$ in 21.03.01. Putting these together, the hyperbola method is dual to the contour integral of 21.11.04: the elementary $O (x)$ error in the divisor problem and the analytic moments of $ζ$ on the critical line are two readings of the same object, and the bridge is precisely that summation by parts converts $\sum_{n \leq x} d (n)$ into $\frac{1}{2 π i} \int ζ (s)^{2} x^{s} s^{- 1} d s$ . The pattern that organises the whole chapter is this duality, which generalises from $d, σ, φ$ to the $k$ -fold divisor functions and, at the frontier of the elementary method, breaks exactly at $μ$ , where size gives way to cancellation and the analytic theory of 21.12.01 must take over.

Full proof set Master

Proposition 1 (Abel summation, general form). For $a : Z_{> 0} \to C$ with $A (t) = \sum_{n \leq t} a (n)$ and $ϕ \in C^{1} [y, x]$ , $$ \sum_{y<n\le x}a(n)\phi(n) = A(x)\phi(x) - A(y)\phi(y) - \int_y^x A(t)\phi'(t),dt. $$

Proof. On each interval $[n, n + 1)$ the step function $A (t)$ is constant equal to $A (n)$ . Write $ϕ (n) = ϕ (x) - \int_{n}^{x} ϕ^{'} (t) d t$ for the terms with $y < n \leq x$ and apply $a (n) = A (n) - A (n - 1)$ . Telescoping the products $A (n) ϕ (n)$ against $A (n - 1) ϕ (n)$ and using $\int_{n}^{n + 1} A (t) ϕ^{'} (t) d t = A (n) (ϕ (n + 1) - ϕ (n))$ on each unit interval reassembles the boundary terms $A (x) ϕ (x) - A (y) ϕ (y)$ and the integral $- \int_{y}^{x} A (t) ϕ^{'} (t) d t$ . Equivalently, by parts on the Stieltjes integral $\sum_{y < n \leq x} a (n) ϕ (n) = \int_{y}^{x} ϕ (t) d A (t) = [A ϕ]_{y}^{x} - \int_{y}^{x} A (t) d ϕ (t)$ , which is the stated identity since $A$ is constant between integers and $d ϕ = ϕ^{'} d t$ . $□$

Proposition 2 (hyperbola identity). For arithmetic functions $f, g$ , $h = fg $, an d$ 1 \le y \le x $, w i t h$ F, G $t h es u mma t or y f u n c t i o n so f$ f, g$,* $$ \sum_{n\le x}h(n) = \sum_{a\le y} f(a),G(x/a) + \sum_{b\le x/y} g(b),F(x/b) - F(y),G(x/y). $$

Proof. Expand $\sum_{n \leq x} h (n) = \sum_{ab \leq x} f (a) g (b)$ , a sum over the lattice region $R = {(a, b) : ab \leq x}$ . Partition $R$ by the threshold $y$ : let $R_{1} = {a \leq y}$ and $R_{2} = {b \leq x / y}$ . Every $(a, b) \in R$ lies in $R_{1} \cup R_{2}$ , because $a > y$ and $b > x / y$ would force $ab > x$ . By inclusion-exclusion, $$ \sum_{\mathcal{R}} = \sum_{\mathcal{R}1} + \sum{\mathcal{R}2} - \sum{\mathcal{R}_1\cap\mathcal{R}_2}. $$ On $R_{1}$ , for each $a \leq y$ the inner sum over $b \leq x / a$ gives $f (a) G (x / a)$ ; on $R_{2}$ , for each $b \leq x / y$ the inner sum over $a \leq x / b$ gives $g (b) F (x / b)$ . The overlap $R_{1} \cap R_{2} = {a \leq y, b \leq x / y}$ is a product range (note $ab \leq y \cdot (x / y) = x$ holds automatically there), contributing $(\sum_{a \leq y} f (a)) (\sum_{b \leq x / y} g (b)) = F (y) G (x / y)$ . Combining gives the identity. $□$

Proposition 3 (Euler summation, first order). For $ϕ \in C^{1} [1, x]$ , $$ \sum_{n\le x}\phi(n) = \int_1^x \phi(t),dt + \tfrac12(\phi(1)+\phi(x)) + \int_1^x\Bigl({t}-\tfrac12\Bigr)\phi'(t),dt. $$

Proof. Apply Abel summation (Proposition 1) with $a (n) = 1$ , so $A (t) = ⌊ t ⌋$ , over $1 \leq n \leq x$ . The boundary term at the lower end keeps the $n = 1$ contribution, giving $$ \sum_{1\le n\le x}\phi(n) = \lfloor x\rfloor,\phi(x) - \int_1^x \lfloor t\rfloor,\phi'(t),dt + \phi(1). $$ Substitute $⌊ t ⌋ = t - {t}$ and $⌊ x ⌋ = x - {x}$ , then integrate $\int_{1}^{x} t ϕ^{'} (t) d t = x ϕ (x) - ϕ (1) - \int_{1}^{x} ϕ (t) d t$ by parts: $$ \sum_{n\le x}\phi(n) = \int_1^x\phi(t),dt + 2\phi(1) - {x}\phi(x) + \int_1^x {t},\phi'(t),dt - \phi(1), $$ where the $x ϕ (x)$ terms cancel. To symmetrise, write $\int_{1}^{x} \frac{1}{2} ϕ^{'} (t) d t = \frac{1}{2} (ϕ (x) - ϕ (1))$ and fold it into the fractional-part integral, converting ${t}$ into ${t} - \frac{1}{2}$ ; the residual boundary terms collect to $\frac{1}{2} (ϕ (1) + ϕ (x))$ (noting $- {x} ϕ (x)$ is absorbed since ${t} - \frac{1}{2}$ evaluated against the endpoint correction restores the half-sum). The result is $\int_{1}^{x} ϕ + \frac{1}{2} (ϕ (1) + ϕ (x)) + \int_{1}^{x} ({t} - \frac{1}{2}) ϕ^{'} (t) d t$ . $□$

Proposition 4 (the $ζ (2)$ tail bound). For $s > 1$ , $\sum_{d \leq x} d^{- s} = ζ (s) + O (x^{1 - s})$ , and in particular $\sum_{d \leq x} d^{- 2} = π^{2} /6 + O (1/ x)$ .

Proof. The tail is $\sum_{d > x} d^{- s}$ , which by comparison with the decreasing integrand satisfies $0 < \sum_{d > x} d^{- s} \leq \int_{x}^{\infty} t^{- s} d t = \frac{x ^{1 - s}}{s - 1} = O (x^{1 - s})$ for $s > 1$ . Hence $\sum_{d \leq x} d^{- s} = ζ (s) - O (x^{1 - s})$ . At $s = 2$ , $ζ (2) = π^{2} /6$ (the Basel value of 21.03.01) and the error is $O (x^{- 1}) = O (1/ x)$ . $□$

Connections Master

The summation toolkit is the analytic dual of the convolution ring of 21.11.01: every average order computed here is the partial-summation or hyperbola evaluation of a convolution $f = g * h$ , and the $ζ (2)$ constants $π^{2} /12$ , $3/ π^{2}$ are the values $D (1; 2)$ , $D (μ; 2)$ read through the Dirichlet-series dictionary established there.
Partial summation supplies the bridge to 21.11.04 the Perron formula and Mellin inversion: Exercise 8 shows $D (f; s) = s \int_{1}^{\infty} F (x) x^{- s - 1} d x$ , and Perron inverts this, recovering $\sum_{n \leq x} d (n)$ as a contour integral of $ζ (s)^{2} x^{s} / s$ whose main term reproduces the divisor average proved here.
The mean value of $μ$ , where the elementary method stalls, is the entry point to 21.12.01 the prime number theorem: $M (x) = o (x)$ is equivalent to PNT and needs the non-vanishing of $ζ$ on $Re (s) = 1$ , beyond what summation alone delivers.
The harmonic constant $γ$ and the Euler-Maclaurin formula connect to 21.03.01 the Riemann zeta function through the Laurent expansion $ζ (s) = 1/ (s - 1) + γ + O (s - 1)$ at the pole, whose constant term is exactly the Euler-Mascheroni constant of the harmonic average.
The Basel constant $π^{2} /6$ appearing in the $σ$ and $φ$ averages is the value $ζ (2)$ of 21.03.01, so the appearance of $π$ in the density of coprime pairs is the same phenomenon as the appearance of $π$ in the Basel problem, transported by the Dirichlet-series dictionary.

Historical & philosophical context Master

The systematic study of average orders begins with Dirichlet's 1849 memoir on mean values in number theory ^{[Dirichlet 1849]}, where the hyperbola method appears for the first time as a device to count lattice points $(a, b)$ with $ab \leq x$ . Dirichlet's insight was that the naive term-by-term estimate $\sum_{n \leq x} ⌊ x / n ⌋$ loses an error of size $x$ , while folding the sum at the diagonal $a = b = x$ recovers an error of only $x$ — the gain being the symmetry of the region under the hyperbola. The constant $2 γ - 1$ in his formula carries the Euler-Mascheroni constant, itself introduced by Euler in the 1730s in connection with the harmonic series and refined to high precision by Mascheroni in 1790.

The error term $Δ (x)$ became a problem in its own right. Voronoi 1903 broke below the elementary $x$ barrier with a Bessel-function expansion of $Δ$ , lowering the exponent to $1/3$ ; the subsequent history is a long sequence of exponential-sum refinements (van der Corput, Kolesnik, and Huxley 2003 with $131/416$ ). The matching lower bound was settled early: Hardy 1916 ^{[Hardy 1916]} proved $Δ (x) = Ω (x^{1/4})$ , so the divisor problem is the determination of the true exponent between $1/4$ and the best upper bound. The leading-order asymptotic is not in doubt; the open question is the precise size of the oscillation around it.

The conceptual lesson is the duality between the elementary and analytic methods. The summation toolkit — partial summation, Euler-Maclaurin, the hyperbola method — handles the average orders of $d$ , $σ$ , and $φ$ by exploiting the size of these functions. The mean value of $μ$ , governed by sign cancellation rather than size, resists the elementary approach entirely and is equivalent to the prime number theorem, as Landau and others made precise in the early twentieth century. Apostol's 1976 text ^{[Apostol Ch. 3]} and the Montgomery-Vaughan treatise ^{[Montgomery-Vaughan]} are the standard modern accounts of where the elementary boundary lies.

Bibliography Master

@book{apostol1976ant,
  author    = {Apostol, Tom M.},
  title     = {Introduction to Analytic Number Theory},
  series    = {Undergraduate Texts in Mathematics},
  publisher = {Springer-Verlag},
  year      = {1976},
  note      = {Chapter 3: averages of arithmetical functions}
}

@article{dirichlet1849mittleren,
  author  = {Dirichlet, Peter Gustav Lejeune},
  title   = {\"{U}ber die Bestimmung der mittleren Werthe in der Zahlentheorie},
  journal = {Abhandlungen der K\"{o}niglichen Preussischen Akademie der Wissenschaften zu Berlin},
  pages   = {69--83},
  year    = {1849}
}

@article{hardy1916divisor,
  author  = {Hardy, G. H.},
  title   = {On Dirichlet's divisor problem},
  journal = {Proceedings of the London Mathematical Society (2)},
  volume  = {15},
  pages   = {1--25},
  year    = {1916}
}

@book{montgomeryvaughan2007,
  author    = {Montgomery, Hugh L. and Vaughan, Robert C.},
  title     = {Multiplicative Number Theory I: Classical Theory},
  series    = {Cambridge Studies in Advanced Mathematics},
  number    = {97},
  publisher = {Cambridge University Press},
  year      = {2007}
}

@book{tenenbaum2015,
  author    = {Tenenbaum, G\'{e}rald},
  title     = {Introduction to Analytic and Probabilistic Number Theory},
  edition   = {3},
  series    = {Graduate Studies in Mathematics},
  number    = {163},
  publisher = {American Mathematical Society},
  year      = {2015}
}

@book{titchmarsh1986zeta,
  author    = {Titchmarsh, E. C.},
  title     = {The Theory of the Riemann Zeta-Function},
  edition   = {2},
  publisher = {Oxford University Press},
  year      = {1986},
  note      = {Revised by D. R. Heath-Brown; Chapter 12, the divisor problem}
}

@article{huxley2003divisor,
  author  = {Huxley, M. N.},
  title   = {Exponential sums and lattice points III},
  journal = {Proceedings of the London Mathematical Society (3)},
  volume  = {87},
  number  = {3},
  pages   = {591--609},
  year    = {2003}
}

Prerequisites

21.11.01
02.03.03

Tier anchors

beginner: Apostol 1976 *Introduction to Analytic Number Theory* (Springer UTM) Ch. 3 (the average order of the divisor function, worked numerically); Tao's blog 'The divisor bound' for the running-average viewpoint on $d(n)$
intermediate: Apostol 1976 *Introduction to Analytic Number Theory* (Springer UTM) Ch. 3 (Abel summation, Euler-Maclaurin, the Dirichlet hyperbola method, the average orders of $d$, $\sigma$, $\varphi$); Tenenbaum 2015 *Introduction to Analytic and Probabilistic Number Theory* 3e (AMS GSM 163) §I.3 (summation by parts and mean values)
master: Montgomery-Vaughan 2007 *Multiplicative Number Theory I: Classical Theory* (Cambridge SMM 97) §2 (summation methods, the hyperbola method, the divisor problem); Dirichlet 1849 *Abhandlungen Berlin* (the original hyperbola method and the $\sqrt{x}$ error term); Iwaniec-Kowalski 2004 *Analytic Number Theory* (AMS Colloquium 53) Ch. 1; Titchmarsh-Heath-Brown 1986 *The Theory of the Riemann Zeta-Function* 2e (Oxford) Ch. 12 (the Dirichlet divisor problem and the exponent $\theta$)

References

Apostol, T. M. — Introduction to Analytic Number Theory · Springer Undergraduate Texts in Mathematics (1976). Chapter 3 develops the big-O and asymptotic notation, Euler's summation formula (the elementary Euler-Maclaurin), Abel summation (summation by parts), the average orders $\sum_{n\le x} d(n) = x\log x + (2\gamma-1)x + O(\sqrt x)$ via the Dirichlet hyperbola method, $\sum_{n\le x}\sigma(n) = \frac{\pi^2}{12}x^2 + O(x\log x)$, $\sum_{n\le x}\varphi(n) = \frac{3}{\pi^2}x^2 + O(x\log x)$, and the partial sums of the harmonic series $\sum_{n\le x} 1/n = \log x + \gamma + O(1/x)$.
Dirichlet, P. G. L. — Über die Bestimmung der mittleren Werthe in der Zahlentheorie · *Abhandlungen der Königlichen Preussischen Akademie der Wissenschaften zu Berlin* (1849), 69-83. The hyperbola method for the average order of the divisor function, $\sum_{n\le x} d(n) = x\log x + (2\gamma-1)x + O(\sqrt x)$; the prototype lattice-point count under the hyperbola $ab \le x$ with the symmetric split at $\sqrt x$.
Montgomery, H. L. & Vaughan, R. C. — Multiplicative Number Theory I: Classical Theory · Cambridge Studies in Advanced Mathematics 97 (2007). §2 treats the arithmetic of summation: Abel summation, the Euler-Maclaurin formula, the Dirichlet hyperbola method, and the average orders of the standard arithmetic functions, with the divisor problem and its known error-term exponents.
Tenenbaum, G. — Introduction to Analytic and Probabilistic Number Theory · American Mathematical Society Graduate Studies in Mathematics 163, 3rd edition (2015). Part I §3 develops summation by parts, the Euler-Maclaurin formula with explicit Bernoulli-polynomial remainders, and mean values of multiplicative functions.
Titchmarsh, E. C. — The Theory of the Riemann Zeta-Function · Oxford University Press, 2nd edition revised by D. R. Heath-Brown (1986). Chapter 12 treats the Dirichlet divisor problem: the error term $\Delta(x) = \sum_{n\le x} d(n) - x\log x - (2\gamma-1)x$, the bounds $\Delta(x) = O(x^{\theta})$, and the conjectured value $\theta = 1/4$.
Hardy, G. H. — On Dirichlet's divisor problem · *Proceedings of the London Mathematical Society* (2) 15 (1916), 1-25. The Omega-result $\Delta(x) = \Omega(x^{1/4})$, establishing that the exponent $1/4$ cannot be improved, so the Dirichlet divisor problem is the determination of the true order between $1/4$ and the best known upper bound.

Estimated time

beginner: 18m
intermediate: 44m
master: 85m