Dirichlet hyperbola method

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

$\sum _{n\leq x}f(n),$

where $f,g,h$ are multiplicative functions with $f=g*h$, where $*$ is the Dirichlet convolution. It uses the fact that

$\sum _{n\leq x}f(n)=\sum _{n\leq x}\sum _{ab=n}g(a)h(b)=\sum _{a\leq {\sqrt {x}}}\sum _{b\leq {\frac {x}{a}}}g(a)h(b)+\sum _{b\leq {\sqrt {x}}}\sum _{a\leq {\frac {x}{b}}}g(a)h(b)-\sum _{a\leq {\sqrt {x}}}\sum _{b\leq {\sqrt {x}}}g(a)h(b).$

Uses

Let $\sigma _{0}(n)$ be the divisor-counting function, and let $D(n)$ be its summatory function:

$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 ${\widetilde {O}}(n)$ time. Since $\sigma _{0}$ admits the Dirichlet convolution $\sigma _{0}=1*1$, the Dirichlet hyperbola method yields the formula

$D(n)=\sum _{a\leq {\sqrt {n}}}\sum _{b\leq {\frac {n}{a}}}1\cdot 1+\sum _{a\leq {\sqrt {n}}}\sum _{b\leq {\frac {n}{a}}}1\cdot 1-\sum _{a\leq {\sqrt {n}}}\sum _{b\leq {\sqrt {n}}}1\cdot 1,$

which simplifies to

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

which can be evaluated in $O\left({\sqrt {n}}\right)$ operations.

The method also has theoretical applications: for example, further manipulation of this formula yields the estimate

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

where $\gamma$ is the Euler–Mascheroni constant.

External links

• Discussion of the Dirichlet hyperbola method for computational purposes