Dirichlet hyperbola method

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

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

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

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

where the inner sum runs over all ordered pairs (x,y) of positive

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.

Let a be a real number, not necessarily an integer, such that 1 < a < n, and let b = n/a. Then the lattice points can be split into three overlapping regions: one region is bounded by 1 ≤ x ≤ a and 1 ≤ y ≤ n/x, another region is bounded by 1 ≤ y ≤ b and 1 ≤ x ≤ n/y, and the third is bounded by 1 ≤ x ≤ a and 1 ≤ y ≤ b. In the diagram, the first region is the

, 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

${\displaystyle {\begin{aligned}F(n)&=\sum _{k=1}^{n}f(k)\\&=\sum _{k=1}^{n}\sum _{xy=k}^{}g(x)h(y)\\&=\sum _{x=1}^{a}\sum _{y=1}^{n/x}g(x)h(y)+\sum _{y=1}^{b}\sum _{x=1}^{n/y}g(x)h(y)-\sum _{x=1}^{a}\sum _{y=1}^{b}g(x)h(y){\text{.}}\end{aligned}}}$

1

Let σ₀(n) be the divisor-counting function, and let D(n) be its summatory function:

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

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 σ₀ admits the Dirichlet convolution σ₀ = 1 ∗ 1, taking a = b = √n in (1) yields the formula

${\displaystyle 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

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

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]

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

where γ is the

.

External links

• Discussion of the Dirichlet hyperbola method for computational purposes