Codex @codex  0

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

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.

Write $1(n)=1$ and let $\epsilon$ be the Identity for Dirichlet convolution. The Möbius function uses the empty-product convention $\mu (1)=1$; the Von Mangoldt function has $\Lambda (1)=0$. We first establish all the arithmetic function identities needed below. Every integer divisor of $n$ contributes one to $\tau (n)$, so $\tau =1\ast 1$. If $n>1$ has $r$ distinct prime factors, the squarefree divisors correspond to their subsets andAt $n=1$ the sum is one. Thus $\mu \ast 1=\epsilon$. Writing $n={\prod }_p{p}^{v_p(n)}$, the only divisors with nonzero Von Mangoldt function are $p,p^2,\dots ,p^{v_p(n)}$, and henceThe Dirichlet convolution is commutative by replacing $d$ with $n/d$, and associative because either bracketing sums $f(a)g(b)h(c)$ over $abc=n$. ConsequentlyThese are consequences of the definitions, rather than unproved invocations of Möbius inversion.

To identify the constant, integrate on each interval $[j,j+1)$:The tail is $O(1/J)$, since the integrand is at most $2/x^2$ for $x\ge 2$. Summation therefore gives $\gamma ={\lim }_{J\to \infty }(H_J-\log (J+1))$, where $H_J$ is the harmonic number, and $H_J=\log J+\gamma +O(1/J)$. Thus this is Euler's constant.

Put $r=\lfloor \sqrt{N}\rfloor$. Counting pairs of positive integers whose product is at most $N$, and subtracting the square counted twice, gives the Dirichlet hyperbola method identitySince $r=\sqrt{N}+O(1)$, the harmonic number estimate yieldsThe increasing natural logarithm also satisfies ${\sum }_{n\le N}\log n=N\log N-N+O(\log (2N))$ by comparison with its integral. Subtracting proves

For the second implication, denote the Mertens function by $M(x)$ and the Second Chebyshev function by $\psi (x)$. Apply the proved Dirichlet convolution identities to $b(n)=\tau (n)-\log n-2\gamma 1(n)$:Summing this identity over integers up to $N$ gives the exact relationFix an integer $K\ge 2$. The contribution to $E(N)$ from $d\le N/K$ has absolute value at mostFor $d>N/K$, group by $j=\lfloor N/d\rfloor$. This gives exactlyunder the assumed cancellation $M(x)=o(x)$; extending that assumption from integers to real $x$ uses $M(x)=M(\lfloor x\rfloor )$. Therefore ${\mathrm{limsup}}_{N\to \infty }|E(N)|/N\ll K^{-1/2}$. Letting $K\to \infty$ proves the prime number asymptotic from Mertens cancellation:

An arithmetic function $f$ is multiplicative when $f(1)=1$ and $f(mn)=f(m)f(n)$ whenever $m$ and $n$ are coprime. If $m$ and $n$ are coprime, every divisor $d$ of $mn$ has a unique factorization $d=d_1{d}_2$ with $d_1\mid m$ and $d_2\mid n$. Hence the Dirichlet convolution of multiplicative functions satisfiesand $(f\star g)(1)=1$, so it is multiplicative.

Let $\epsilon$ be the Identity for Dirichlet convolution, with $\epsilon (1)=1$ and $\epsilon (n)=0$ for $n>1$. The Möbius function satisfies $\mu \star 1=\epsilon$. Therefore, using commutativity and associativity,This is the Möbius inversion formula.