Dirichlet convolution ($\ast$)

The Dirichlet convolution of arithmetic functions $f,g$ is the arithmetic functionIn the first sum, $d$ runs over the positive integer divisors of $n$; the second uses ordered pairs of positive integers whose product is $n$. Both sums are finite. Each pair contributes one weight from $f$ and one from $g$, so Dirichlet convolution combines information attached to complementary factors. It turns a divisor sum into an operation on arithmetic functions. ^[ref]

For $n=12$ the six ordered pairs are $(1,12),(2,6),(3,4),(4,3),(6,2),(12,1)$. The constant-one arithmetic function gives one per pair, while the identity arithmetic function weights the first factor by its size:Here $\tau$ is the divisor function and ${\sigma }_1$ is the sum-of-divisors function. By comparison, the pointwise product of arithmetic functions gives $(1\cdot 1)(12)=1$ and $(\mathrm{id}\cdot 1)(12)=12$.

Commutativity follows by swapping the two entries of every ordered pair. Associativity follows by reindexing either grouping over the same ordered tuples of three positive integers:For example, $((1\ast 1)\ast 1)(12)$ counts ordered tuples of three positive integers with product $12$. Distribute the two occurrences of the prime factor $2$ among three entries in $\left(\genfrac{}{}{0ex}{}{2+2}{2}\right)=6$ ways, and the one occurrence of the prime factor $3$ in $\left(\genfrac{}{}{0ex}{}{1+2}{2}\right)=3$ ways. These binomial coefficients are the stars and bars counts of exponent choices in the nonnegative integers; prime factorization therefore gives $6\cdot 3=18$ such tuples. Directly, the same Dirichlet convolution is ${\sum }_{d\mid 12}\tau (d)=1+2+2+3+4+6=18$.

The Identity for Dirichlet convolution is $\epsilon$, and the Möbius function reverses a divisor sum because $\mu \ast 1=\epsilon$. This makes Dirichlet convolution useful both for counting factorizations and for recovering an arithmetic function from its divisor sum.

The Dirichlet convolution of two multiplicative functions is a multiplicative function. For positive coprime integers $m,n$, every positive integer divisor of $mn$ has a unique form $de$ with $d\mid m$ and $e\mid n$, by prime factorization. The pairs $d,e$ and $m/d,n/e$ are each coprime integers, so the defining rules for the two multiplicative functions separate the sum:Also $(f\ast g)(1)=f(1)g(1)=1$. This short argument proves multiplicativity of both the divisor function $1\ast 1$ and the sum-of-divisors function $\mathrm{id}\ast 1$. The result need not be a completely multiplicative function, even when both inputs are: $1\ast 1=\tau$ fails at $2\cdot 2$. ^[ref]

The constant-one arithmetic function has $1(n)=1$ for every positive integer $n$, including $1(1)=1(12)=1$. It is a completely multiplicative function. Its Dirichlet convolution with an arithmetic function $f$ is the divisor sum $(1\ast f)(n)={\sum }_{d\mid n}f(d)$. Thus $1\ast 1=\tau$, the divisor function. Its pointwise product of arithmetic functions with $f$ is $f$ itself; its Dirichlet convolution with $f$ generally is not. The Identity for Dirichlet convolution is instead $\epsilon$.

The identity arithmetic function is $\mathrm{id}(n)=n$ on the positive integers, for example $\mathrm{id}(1)=1$ and $\mathrm{id}(12)=12$. It is a completely multiplicative function and gives the sum-of-divisors function through $\mathrm{id}\ast 1={\sigma }_1$ under Dirichlet convolution. It is distinct from the Identity for Dirichlet convolution $\epsilon$. The identity $\mathrm{id}=1\ast \phi$, where $\phi$ is Euler's totient function, is equivalent to ${\sum }_{d\mid n}\phi (d)=n$.

The Identity for Dirichlet convolution is the arithmetic functionFor every arithmetic function $f$, it satisfies $f\ast \epsilon =\epsilon \ast f=f$. Indeed, in $(f\ast \epsilon )(n)={\sum }_{d\mid n}f(d)\epsilon (n/d)$, only $d=n$ survives. For example,At $n=1$ the sole term is $f(1)\epsilon (1)=f(1)$. This gives a useful way to check Dirichlet convolution calculations: inserting $\epsilon$ leaves every value unchanged. The three arithmetic functions $1$, $\mathrm{id}$, and $\epsilon$ all take value $1$ at $1$, but at $12$ the constant-one arithmetic function, the identity arithmetic function, and the Identity for Dirichlet convolution take values $1$, $12$, and $0$, respectively. ^[ref]

The Möbius function is the inverse of the constant-one arithmetic function under Dirichlet convolution, meaning $\mu \ast 1=1\ast \mu =\epsilon$. The Möbius divisor-sum identity gives a short proof: for $n>1$ the nonzero terms expand ${\prod }_{p\mid n}(1-1)=0$, while at $1$ the sum is $\mu (1)=1$. At $12$, the computation isThe zeros occur because $4$ and $12$ are divisible by the square of the prime number $2$. Consequently, if $F=f\ast 1$ is a divisor sum, then associativity gives $F\ast \mu =f\ast (1\ast \mu )=f\ast \epsilon =f$: this is Möbius inversion.

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.