Dirichlet hyperbola method

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$: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. 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 identityThe subtraction is for the whole overlap square, rather than only the diagonal. The same Dirichlet hyperbola method identity holds for real $x\ge 1$, with $D(x)={\sum }_{n\le x}\tau (n)$ and $r=\lfloor \sqrt{x}\rfloor$. ^[ref]

The divisor summatory function adds the divisor function up to a cutoff $x\ge 1$. It counts all ordered pairs of positive integers whose product is at most $x$. For $N=12$, the twelve individual divisor function values areCounting columns of lattice points instead gives $12+6+4+3+2+2+1+1+1+1+1+1=35$. The Dirichlet hyperbola method needs only the first three column counts:The arithmetic work of the Dirichlet hyperbola method is much smaller even though the answer is identical.

This is useful for elementary averages: individual divisor function values fluctuate, but their summation has the regular behavior given by the divisor summatory asymptotic. Dividing that estimate by a positive integer $N$ giveswhere $\log$ is the natural logarithm, $\gamma$ is the Euler--Mascheroni constant, and $O$ uses big O notation. This describes an average, rather than an estimate for every individual divisor function value. ^[ref]

A balanced Dirichlet hyperbola method split takes real thresholds $A=B=\sqrt{N}$. An asymmetric split takes $1\le A\le N$ and $B=N/A$. Every lattice point with $ab\le N$ then has $a\le A$ or $b\le B$, and every point in their overlap rectangle is allowed because $AB=N$. For arithmetic functions $f,g$, define their partial sums by $F(t)={\sum }_{a\le t}f(a)$ and $G(t)={\sum }_{b\le t}g(b)$, always over positive integers. The same inclusion-exclusion principle, now with weight $f(a)g(b)$, yieldsNo multiplicativity assumption is needed: this is a finite rearrangement of Dirichlet convolution. The constant-one arithmetic function in both positions recovers the divisor summatory function. For $N=12$, $A=2$, $B=6$ givesIt uses two columns and six rows, with a twelve-point overlap.

For general positive real thresholds, $AB\ge N$ is sufficient for coverage, since $a>A$ and $b>B$ would imply $ab>AB\ge N$. If $AB>N$, however, the overlap can include points above the hyperbola. The correct subtraction is then ${\sum }_{a\le A,b\le B,ab\le N}f(a)g(b)$; the product $F(A)G(B)$ is justified only when the whole integer rectangle lies below it. For example, $N=12$, $A=B=4$ covers every allowed pair, but its rectangle contains the forbidden pair $(4,4)$, so subtracting all sixteen points would give $34$ instead of $35$.

Conversely, the balanced integer thresholds $r,r$ have $r^2\le N$ and still cover every allowed pair because $(r+1{)}^2>N$. More generally, positive integer thresholds $U,V$ give coverage exactly when $(U+1)(V+1)>N$, and their overlap is a full rectangle exactly when $UV\le N$. These discrete conditions explain why the square-root identity works even when $r^2<N$.

The direct divisor summatory function formula evaluates $N$ floor divisions. Its balanced Dirichlet hyperbola method formula evaluates $r=\lfloor \sqrt{N}\rfloor$ floor divisions and reuses their sum for the other strip, followed by doubling and square-overlap subtraction. Thus it uses $O(\sqrt{N})$ arithmetic operations, with big O notation, in a model that counts each division, addition and multiplication as one operation. At $N=10^6$, the division counts for these two formulas are $10^6$ and $10^3$.

For a general Dirichlet convolution, the asymmetric formula has $\lfloor A\rfloor +\lfloor B\rfloor$ outer terms; evaluating $F$ and $G$ has an additional cost. Under $AB=N$, equal thresholds minimize $A+B$, but an asymmetric split can be useful if the two partial sums have different evaluation costs. The balanced divisor summatory function gains the further reuse because its two arithmetic functions are identical.

These are arithmetic operation counts, rather than counts of elementary operations on binary digits: the integers grow with $N$, and division of longer integers costs more in that model of computational complexity theory. Computing $r$ also requires an exact integer square root, or checking and correcting a numerical square root until $r^2\le N<(r+1{)}^2$ holds.

The Dirichlet hyperbola method gives $D(x)=2{\sum }_{a\le r}\lfloor x/a\rfloor -r^2$, where $r=\lfloor \sqrt{x}\rfloor$. The harmonic number estimate $H_r=\log r+\gamma +O(1/r)$, with $\gamma$ the Euler's constant, yields $D(x)=2x(\log r+\gamma )-r^2+O(x/r+r)$. Substitution of $r=\sqrt{x}+O(1)$ gives the displayed asymptotic expansion. Comparison of ${\sum }_{n\le x}\log n$ with its integral consequently gives ${\sum }_{n\le N}(\tau (n)-\log n-2\gamma )=O(\sqrt{N})$ for integer $N$.

Write $B(t)={\sum }_{n\le t}\tau (n)/n$ and $r=\lfloor \sqrt{t}\rfloor$. The weighted Dirichlet hyperbola method givesIndeed, use $H_{\lfloor u\rfloor }=\log u+\gamma +O(1/u)$ and ${\sum }_{a\le r}(\log a)/a=\frac{1}{2}{\log }^{2}r+c\prime +O(\log (2r)/r)$. The latter follows by comparing each summand with the integral on its unit interval: the derivative of $(\log t)/t$ has an integrable tail. Since $r=\sqrt{t}+O(1)$, substitution yields the expansion. Here $H_n$ is the harmonic number and $\gamma$ the Euler--Mascheroni constant.