= Dirichlet hyperbola method
{c}
{wiki}
The <Dirichlet hyperbola method> turns a long <summation> over a <Dirichlet convolution> into two short ones by covering the <lattice points> below a <hyperbola> with two overlapping strips. Its simplest application is an exact count: for a <positive integer> $N$, every positive <integer divisor> $a$ of $n\le N$ corresponds to the <ordered pair> $(a,n/a)$. Thus the <divisor summatory function> counts precisely the <ordered pairs> of <positive integers> with $ab\le N$:
$$
D(N)=\sum_{n=1}^N\tau(n)
=\#\{(a,b)\in\mathbb Z_{>0}^2:ab\le N\}
=\sum_{a=1}^N\left\lfloor\frac Na\right\rfloor.
$$
Here $\tau$ is the <divisor function>, and the <floor function> gives the number of allowed values of $b$ for each $a$. The axes are excluded, while points on $ab=N$ are included.
Set $r=\lfloor\sqrt N\rfloor$, using the <floor function> and the positive <square root>. \b[Every counted pair has $a\le r$ or $b\le r$.] Otherwise $ab\ge(r+1)^2>N$. The first strip contains $\sum_{a=1}^r\lfloor N/a\rfloor$ points; swapping the two coordinates gives the same count for the second. Their overlap contains all $r^2$ pairs with $1\le a,b\le r$, since $r^2\le N$. The <inclusion-exclusion principle> therefore gives the exact identity
$$
\boxed{D(N)=2\sum_{a=1}^r\left\lfloor\frac Na\right\rfloor-r^2,
\qquad r=\lfloor\sqrt N\rfloor.}
$$
The subtraction is for the whole overlap square, rather than only the diagonal. The same <Dirichlet hyperbola method> identity holds for real $x\ge1$, with $D(x)=\sum_{n\le x}\tau(n)$ and $r=\lfloor\sqrt x\rfloor$. <Multiplicative number theory: The pretentious approach by Andrew Granville and K. Soundararajan>[Andrew Granville and K. Soundararajan, Multiplicative number theory: The pretentious approach, §1.1.4, pp. 7–8: divisor pairing and the hyperbola split]{ref}
\Image[/dirichlet-hyperbola-lattice-split.png]
{title=The <Dirichlet hyperbola method> counts 35 positive <lattice points> with $ab\le12$: two strips of 22 points overlap in a square of nine points}
Back to article page
