# Dirichlet hyperbola method

Let $f$, $g$, and $h$ be multiplicative functions such that $f=g*h$, where $*$ denotes the convolution (http://planetmath.org/DirichletConvolution) of $g$ and $h$. The Dirichlet hyperbola method (typically shortened to hyperbola method) is a way to $\displaystyle\sum_{n\leq x}f(n)$ by using the fact that $f=g*h$:

 $\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)$

Note that, since $ab=n\leq x$, not both of $a$ and $b$ can be larger than $\sqrt{x}$. The Dirichlet hyperbola method follows from this fact as well as the inclusion-exclusion principle.

This method for calculating $\displaystyle\sum_{n\leq x}f(n)$ is advantageous when the sums in of $g$ and $h$ are easier to handle and when $|g(n)-h(n)|$ is relatively small for most $n\in\mathbb{N}$.

As an example, the sum $\displaystyle\sum_{n\leq x}\tau(n)$ will be calculated using the Dirichlet hyperbola method.

Note that $\tau=1*1$. Thus:

$\begin{array}[]{ll}\displaystyle\sum_{n\leq x}\tau(n)&\displaystyle=\sum_{a% \leq\sqrt{x}}\sum_{b\leq\frac{x}{a}}1+\sum_{b\leq\sqrt{x}}\sum_{a\leq\frac{x}{% b}}1-\sum_{a\leq\sqrt{x}}\sum_{b\leq\sqrt{x}}1\\ &\\ &\displaystyle=\sum_{a\leq\sqrt{x}}\left(\frac{x}{a}+O(1)\right)+\sum_{b\leq% \sqrt{x}}\left(\frac{x}{b}+O(1)\right)-\left(\sum_{a\leq\sqrt{x}}1\right)\left% (\sum_{b\leq\sqrt{x}}1\right)\\ &\\ &\displaystyle=2\sum_{c\leq\sqrt{x}}\left(\frac{x}{c}+O(1)\right)-\left(\sum_{% c\leq\sqrt{x}}1\right)^{2}\\ &\\ &\displaystyle=2x\sum_{c\leq\sqrt{x}}\frac{1}{c}+O\left(\sum_{c\leq\sqrt{x}}1% \right)-(\sqrt{x}+O(1))^{2}\\ &\\ &\displaystyle=2x\left(\log\sqrt{x}+\gamma+O\left(\frac{1}{\sqrt{x}}\right)% \right)+O(\sqrt{x})-\left(x+O(\sqrt{x})+O(1)\right)\\ &\\ &\displaystyle=2x\left(\frac{1}{2}\log x+\gamma+O\left(\frac{1}{\sqrt{x}}% \right)\right)-x+O(\sqrt{x})\\ &\\ &\displaystyle=x\log x+2\gamma x+O\left(\frac{x}{\sqrt{x}}\right)-x+O(\sqrt{x}% )\\ &\\ &\displaystyle=x\log x+(2\gamma-1)x+O(\sqrt{x})\end{array}$

Title Dirichlet hyperbola method DirichletHyperbolaMethod 2013-03-22 15:58:27 2013-03-22 15:58:27 Wkbj79 (1863) Wkbj79 (1863) 14 Wkbj79 (1863) Definition msc 11N37 hyperbola method ConvolutionMethod TauFunction EulersConstant