Dirichlet hyperbola method

An example of the Dirichlet hyperbola method with $n=10,$ $a\approx 2.7,$ and $b\approx 3.7.$

In number theory, the Dirichlet hyperbola method is a technique to evaluate the sum

$F(n)=\sum _{k=1}^{n}f(k),$

where Template:Mvar is a multiplicative function. The first step is to find a pair of multiplicative functions Template:Mvar and Template:Mvar such that, using Dirichlet convolution, we have Template:Math; the sum then becomes

$F(n)=\sum _{k=1}^n\sum _{xy=k}^{}g(x)h(y),$

where the inner sum runs over all ordered pairs Template:Math of positive integers such that Template:Math. 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 Template:Math, where Template:Mvar runs over the integers Template:Math: for each such point Template:Math, the sum contains a term Template:Math, and vice versa.

Let Template:Mvar be a real number, not necessarily an integer, such that Template:Math, and let Template:Math. Then the lattice points can be split into three overlapping regions: one region is bounded by Template:Math and Template:Math, another region is bounded by Template:Math and Template:Math, and the third is bounded by Template:Math and Template:Math. In the diagram, the first region is the union of the blue and red regions, the second region is the union of the red and green, and the third region is the red. Note that this third region is the intersection of the first two regions. By the principle of inclusion and exclusion, the full sum is therefore the sum over the first region, plus the sum over the second region, minus the sum over the third region. This yields the formula

Examples

Let Template:Math be the divisor-counting function, and let Template:Math be its summatory function:

$D(n)=\sum _{k=1}^n{\sigma }_0(k).$

Computing Template:Math naïvely requires factoring every integer in the interval Template:Math; an improvement can be made by using a modified Sieve of Eratosthenes, but this still requires Template:Math time. Since Template:Math admits the Dirichlet convolution Template:Math, taking Template:Math in (Template:EquationNote) yields the formula

$D(n)=\sum _{x=1}^{\sqrt{n}}\sum _{y=1}^{n/x}1\cdot 1+\sum _{y=1}^{\sqrt{n}}\sum _{x=1}^{n/y}1\cdot 1-\sum _{x=1}^{\sqrt{n}}\sum _{y=1}^{\sqrt{n}}1\cdot 1,$

which simplifies to

$D(n)=2\cdot \sum _{x=1}^{\sqrt{n}}\lfloor \frac{n}{x}\rfloor -{\lfloor \sqrt{n}\rfloor }^2,$

which can be evaluated in Template:Math operations.

The method also has theoretical applications: for example, Peter Gustav Lejeune Dirichlet introduced the technique in 1849 to obtain the estimate

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

where Template:Mvar is the Euler–Mascheroni constant.

External links

• Discussion of the Dirichlet hyperbola method for computational purposes