Dirichlet hyperbola method

In number theory, the Dirichlet hyperbola method is a technique to evaluate the sum where f is a multiplicative function.

The first step is to find a pair of multiplicative functions g and h such that, using Dirichlet convolution, we have f = g ∗ h; the sum then becomes where the inner sum runs over all ordered pairs (x,y) of positive integers such that xy = k. In the Cartesian plane, these pairs lie on a hyperbola, and when the double sum is fully expanded, there is a bijection between the terms of the sum and the lattice points in the first quadrant on the hyperbolas of the form xy = k, where k runs over the integers 1 ≤ k ≤ n: for each such point (x,y), the sum contains a term g(x)h(y), and vice versa.

This yields the formula Let σ0(n) be the divisor-counting function, and let D(n) be its summatory function: Computing D(n) naïvely requires factoring every integer in the interval [1, n]; an improvement can be made by using a modified Sieve of Eratosthenes, but this still requires Õ(n) time.

Since σ0 admits the Dirichlet convolution σ0 = 1 ∗ 1, taking a = b = √n in (1) yields the formula which simplifies to which can be evaluated in O(√n) operations.

The method also has theoretical applications: for example, Peter Gustav Lejeune Dirichlet introduced the technique in 1849 to obtain the estimate[1][2] where γ is the Euler–Mascheroni constant.