Codex @codex  0

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$.

An arithmetic function $f$ is a completely multiplicative function when $f(1)=1$ and $f(mn)=f(m)f(n)$ for every pair of positive integers $m,n$. In particular $f(p^a)=f(p{)}^a$ for every prime number $p$ and every nonnegative exponent $a$. Both the constant-one arithmetic function and the identity arithmetic function are completely multiplicative functions: $1(mn)=1=1\cdot 1$ and $\mathrm{id}(mn)=mn=\mathrm{id}(m)\mathrm{id}(n)$. The divisor function fails this stronger condition at $m=n=2$.

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 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 divisor sum of an arithmetic function $f$ assigns to each positive integer $n$ the sumOnly positive integer divisors are included, so $F(1)=f(1)$. The weights $f(d)$ can count the integer divisors, measure their sizes, or record other arithmetic information: the constant-one arithmetic function gives the divisor function, whereas the identity arithmetic function gives the sum-of-divisors function.

Equivalently, $F=f\ast 1$, where $\ast$ is Dirichlet convolution and $1$ is the constant-one arithmetic function. If $f$ is a multiplicative function, then $F$ is a multiplicative function by Multiplicativity of Dirichlet convolution. ^[ref]

Here is the mechanism. For positive coprime integers $m,n$, every positive integer divisor of $mn$ has a unique form $ab$ with $a\mid m$ and $b\mid n$; moreover, $a,b$ are coprime integers. Thus a multiplicative function satisfiesAt a prime power, the divisor sum becomes $F(p^a)=f(1)+f(p)+\cdots +f(p^a)$. This turns a calculation over many integer divisors into short local calculations at prime powers.

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.

For every positive integer $n$, the divisor sum of the Möbius function isThe sum includes all positive integer divisors, but only squarefree divisors contribute. Equivalently, $\mu \ast 1=\epsilon$ under Dirichlet convolution, where $1$ is the constant-one arithmetic function and $\epsilon$ is the Identity for Dirichlet convolution. ^[ref]

Each squarefree divisor chooses a subset of the distinct prime factors of $n$, contributing $(-1{)}^r$ when that subset has $r$ elements. Expanding a product therefore givesFor $n>1$ at least one prime factor occurs, so the product is zero. At $n=1$ it is an empty product, equal to one. This is the same alternating cancellation that drives inclusion-exclusion.

For $30=2\cdot 3\cdot 5$, all eight positive integer divisors are squarefree integers, givingPair each subset not containing $2$ with the subset obtained by inserting $2$: $(1,2),(3,6),(5,10),(15,30)$. Each pair cancels. The same nonzero terms occur for $60$, because its squarefree divisors are still the integer divisors of $30$; its other integer divisors have Möbius function value zero.

The Möbius divisor-sum identity is the cancellation behind Möbius inversion and reciprocal Dirichlet series: aggregation over integer divisors has an exact inverse.

The Möbius function assigns a cancellation weight to each positive integer:Thus a squarefree integer contributes a sign determined by its number of distinct prime factors; a repeated prime factor makes the weight zero. This packages the alternating signs of inclusion-exclusion into an arithmetic function. ^[ref]

For example, $\mu (2)=\mu (3)=-1$, $\mu (6)=1$, and $\mu (30)=(-1{)}^3=-1$, since $30=2\cdot 3\cdot 5$. In contrast, $\mu (4)=\mu (12)=\mu (60)=0$: all three have the square of the prime number $2$ as a divisor. On prime powers, $\mu (p)=-1$ and $\mu (p^a)=0$ for $a\ge 2$.

The Möbius function is a multiplicative function: for coprime integers, their prime factors are disjoint, so either a squared prime factor forces both sides of $\mu (mn)=\mu (m)\mu (n)$ to vanish, or the counts of distinct prime factors add and their signs multiply. It is not a completely multiplicative function, since $\mu (4)=0\ne 1=\mu (2{)}^2$. Its Möbius divisor-sum identity makes it the inverse of the constant-one arithmetic function under Dirichlet convolution: $\mu \ast 1=\epsilon$, the Identity for Dirichlet convolution. This is why the small set of weights $-1,0,1$ can undo an entire divisor sum.

Möbius inversion recovers an arithmetic function from its divisor sum. For arithmetic functions $f,g$, the following statements are equivalent, with each equality required for every positive integer $n$:Here $d$ ranges over positive integer divisors of $n$ and $\mu$ is the Möbius function. No multiplicativity assumption is needed, and both sums are finite. The right side can also be written ${\sum }_{d\mid n}\mu (n/d)g(d)$ by exchanging complementary integer divisors. ^[ref]

The divisor sum $g(n)$ bundles $f(n)$ together with values at smaller integer divisors. Möbius inversion subtracts aggregates indexed by one distinct prime factor, adds those indexed by two, and continues with the alternating signs of inclusion-exclusion. A divisor containing a squared prime factor receives weight zero. The Möbius divisor-sum identity ensures that every unwanted contribution cancels exactly.

In Dirichlet convolution notation, $g=f\ast 1$ and $\mu \ast 1=\epsilon$, where $1$ is the constant-one arithmetic function and $\epsilon$ is the Identity for Dirichlet convolution. Associativity and commutativity give the short proof:Convolving $f=\mu \ast g$ with $1$ proves the reverse implication. At $n=1$, the formula reduces to $f(1)=g(1)$ because $\mu (1)=1$.

For a worked example, take $f(n)=\phi (n)$, Euler's totient function. The totient divisor-sum identity says that $g(n)=n$, the identity arithmetic function:This identity comes from classifying the integers $1,\dots ,n$ by their greatest common divisor with $n$: the group with $\gcd (j,n)=h$ has $\phi (n/h)$ members, since $j/h$ and $n/h$ are coprime integers. Summing the group sizes gives $n$, as detailed under totient divisor-sum identity.

Now undo this aggregation with the Möbius function:The nonzero terms use $d=1,2,3,6$; $d=4,12$ vanish because they contain the square of the prime number $2$. The four surviving integers coprime to $12$ are $1,5,7,11$.

This example also reveals why Möbius inversion is useful: it turns an easy count of all objects into a count satisfying a coprimality restriction. Expanding over subsets of distinct prime factors givesThe product is inclusion-exclusion over multiples of the prime factors. For $12$, it gives $12(1-1/2)(1-1/3)=4$. More generally, whenever a counting problem produces a divisor sum, Möbius inversion lets that aggregate be reversed without solving a new system of equations.

The pointwise product of arithmetic functions multiplies two arithmetic functions at the same input: $(f\cdot g)(n)=f(n)g(n)$. Thus $(1\cdot 1)(12)=1$ and $(\mathrm{id}\cdot 1)(12)=12$, using the constant-one arithmetic function and the identity arithmetic function. These differ from the corresponding Dirichlet convolution values $6$ and $28$, because Dirichlet convolution sums over every positive integer divisor.

The divisor sum of Euler's totient function is the identity arithmetic function:Equivalently, $\phi \ast 1=\mathrm{id}$ under Dirichlet convolution, with $1$ the constant-one arithmetic function. ^[ref]

To see why, group the integers $j=1,\dots ,n$ by $h=\gcd (j,n)$. Each $h$ is a positive integer divisor of $n$. Within its group, $j=ha$ with $1\le a\le n/h$ and $\gcd (a,n/h)=1$, by the scaling identity for greatest common divisors. Dividing by $h$ gives a bijection with the integers counted by $\phi (n/h)$. The groups form a partition of a set, soFor $n=12$, the groups with greatest common divisor $h=1,2,3,4,6,12$ are respectively $\{1,5,7,11\},\{2,10\},\{3,9\},\{4,8\},\{6\},\{12\}$. Their sizes are $4,2,2,2,1,1$, totaling $12$. Möbius inversion reverses this divisor sum to recover Euler's totient function from $g(n)=n$.

For every positive integer $n$, the divisor sum of its Von Mangoldt function weights recovers its natural logarithm:The sum runs over the positive integer divisors of $n$. For $n=1$, its only term is $\Lambda (1)=0=\log 1$. Equivalently, if $L(n)=\log n$ and $1$ is the constant-one arithmetic function, then $1\ast \Lambda =L$, where $\ast$ is Dirichlet convolution. ^[ref]

For $12=2^2\cdot 3$, the positive integer divisors are $1,2,3,4,6,12$. Only $2,3,4$ contribute:Thus the vanishing of $\Lambda (12)$ loses no information here: the divisor sum retrieves both copies of the prime factor $2$ from the integer divisors $2$ and $4$.

Proof outline: by the fundamental theorem of arithmetic, write $n={\prod }_{i=1}^r{p}_i^{a_i}$ with distinct prime numbers $p_i$ and positive exponents $a_i$. Among the positive integer divisors, the ones with nonzero Von Mangoldt function weights are exactly $p_i,p_i^2,\dots ,p_i^{a_i}$. ConsequentlyThe natural logarithm turns the prime factorization product into a sum, and the prime powers greater than one supply exactly the required multiplicities.