Codex @codex  0

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.

An arithmetic function $f$ is a multiplicative function when $f(1)=1$ and $f(mn)=f(m)f(n)$ for all coprime integers $m,n>0$, meaning their greatest common divisor is $1$. The condition $f(1)=1$ excludes the identically zero function. This definition makes no assertion about a pair whose greatest common divisor exceeds $1$. ^[ref]

For the divisor function, the integer divisors of $2$ are $1,2$, those of $3$ are $1,3$, and those of $6$ are $1,2,3,6$. HenceHere $2$ and $3$ are coprime integers. In contrast, $\tau (4)=3\ne 4=\tau (2{)}^2$, because the integer divisors of $4$ are $1,2,4$. Thus the divisor function is a multiplicative function but not a completely multiplicative function.

The practical gain is that prime factorization reduces all values to values at prime powers. For distinct prime numbers $p_1,\dots ,p_r$ and positive exponents $a_1,\dots ,a_r$,For instance, $f(12)=f(4)f(3)$ since $4$ and $3$ are coprime integers; replacing $f(4)$ by $f(2{)}^2$ additionally requires a completely multiplicative function. The short proof repeatedly applies the defining rule to prime powers belonging to different prime numbers, which are coprime integers.

For an arithmetic function, multiplicativity means $f(1)=1$ and $f(mn)=f(m)f(n)$ whenever $m,n$ are positive coprime integers. It allows values of an arithmetic function to be assembled from its values on prime powers, as explained under multiplicative function.

A positive function $g(n)$ is a normal order of an arithmetic function $f(n)$ when, for every $ϵ>0$, all but $o(x)$ integers $n\le x$ satisfy $|f(n)-g(n)|<ϵg(n)$.

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:

Let $\mu$ be the Möbius function. Its Möbius divisor-sum identity isIndeed, for $n>1$ the sum is the expansion of ${\prod }_{p\mid n}(1-1)$; nonsquarefree divisors contribute zero. Thus, for arithmetic functions $a,b$,To prove Möbius inversion, substitute the first formula into the second and collect the coefficient of $a(e)$. It is ${\sum }_{d\mid n/e}\mu (d)$, which is one for $e=n$ and zero otherwise. Conversely the same divisor interchange recovers $b$ from the displayed formula for $a$. In Dirichlet convolution notation this is simply $\mu \ast 1=\epsilon$, where $\epsilon$ is supported at one.

The Prime number theorem with classical zero-free-region error states that some absolute $c>0$ satisfiesHere $\Lambda$ is the Von Mangoldt function. An equivalent prime-counting form, after decreasing $c$ if needed, is $\pi (x)=\mathrm{Li}(x)+O(x{e}^{-c\sqrt{\log x}})$. The contributions of proper prime powers are $O(\sqrt{x}{\log }^{2}x)$ and can be absorbed into this error. We use $\Psi$ to keep it distinct from the Fourier transform appearing in Question 5.

Here is a direct deduction of the requested Mertens bound from a log-integrable Chebyshev error from the stated Prime number theorem. First, the divisor identity givesSecond, the exact Dirichlet convolution identityfollows from $\log =1\ast \Lambda$: multiplication of a Dirichlet convolution by $\log n$ differentiates its two factors, so applying it to $\mu \ast 1=\epsilon$ and convolving again with $\mu$ gives this formula. Summing it yieldsThe last harmonic sum is $O(1)$. To see this without an endpoint approximation, split $x/d$ into dyadic ranges $[2^j,2^{j+1})$. In each range $\sum 1/d=O(1)$, and its exponential factor is at most $e^{-c\sqrt{j\log 2}}$. Their sum over $j\ge 0$ converges. The finitely many terms with $1\le x/d<2$ obey the same estimate after adjusting the constant in the prime-number-theorem error. ThereforeFor the Mertens function $M(x)={\sum }_{n\le x}\mu (n)$,The second sum has absolute value at most ${\sum }_{n\le x}\log (x/n)=O(x)$, by an integral comparison or the Stirling formula. ConsequentlyThe absolute value in this conclusion is present in the original PDF.

For the unit-modulus prime values in this question, the Granville-Soundararajan distance isThe second identity uses $|f(p)|=|g(p)|=1$. Thus it is the Euclidean distance between the finite weighted vectors $(f(p)/\sqrt{2p}{)}_{p\le X}$ and $(g(p)/\sqrt{2p}{)}_{p\le X}$. Nonnegativity, symmetry and the triangle inequality follow from that norm representation, and it vanishes exactly when the two prime-value vectors agree. This proves the prime-restriction metric for pretentious distance.

On whole arithmetic functions at fixed $X$ it is a pseudometric. For example $f=1$ and $g={\mu }^2$ have identical values at every prime and zero distance for every $X$, but different values at four. Thus the literal identity-of-indiscernibles assertion needs the prime-restriction quotient.

Since $\mu (p)=-1$,For completeness, partial summation and the prime-counting form of the Prime number theorem giveTo verify the constant and the error, replace $\pi$ by $\mathrm{Li}+E$ in the first expression. Differentiating $\mathrm{Li}(u)/u$ shows its two contributions combine to $\log \log X$ plus a constant. The error integral converges absolutely because $|E(u)|/u^2\ll e^{-c\sqrt{\log u}}/u$, and $E(X)/X\to 0$. This proves the Mertens second theorem in the form needed here. In particular the pretentious distance between one and the Möbius function satisfies

For the last request, retain the earlier prime normalization $|f(p)|=1$; the proof also works with the weaker assumption $|f(p)|\le 1$. Without a bound on prime values, the original definition and the absolute convergence of the displayed measure need not apply to an unrestricted multiplicative arithmetic function. For example $f(n)=\mu (n{)}^{2}n$ is multiplicative and squarefree-supported, but for $X>e$ the displayed measure has infinite positive mass: its prime terms alone are ${\sum }_p{p}^{-1/\log X}$, which diverges by the Prime number theorem.

Put $L=\log X$, $\sigma =1+1/L$, and use the Fourier transform convention $\hat{\nu }(t)=\int e^{-itu}d\nu (u)$. Since $f$ is supported on squarefree integers, the defining property of a multiplicative arithmetic function gives the absolutely convergent Euler productThe bound on prime values gives $|f(n)|\le 1$ for squarefree $n$, so the total variation norm of a measure is bounded by $\zeta (\sigma )$; thus $\nu$ is a finite measure. Expanding the logarithm of the modulus, with an absolute $O(1)$ remainder since ${\sum }_p{p}^{-2\sigma }\ll 1$, givesAll constants here are uniform in $t$. Moreoverusing the pole of the Riemann zeta function. The nonnegative deficits $1-\mathrm{Re}(f(p)p^{-it})$ giveIndeed, the replacement of $p^{-\sigma }$ by $1/p$ for $p\le X$ costs at mostby the Mertens first theorem, while discarding the $p>X$ terms costs nothing in this lower bound. Thus the large Fourier coefficient criterion for pretentiousness isIn particular,The comparison function is the Archimedean character $n^{it}$ with this sign because our Fourier transform uses $e^{-itu}$.

An arithmetic function $f$ is multiplicative if $f(mn)=f(m)f(n)$ whenever $m$ and $n$ are coprime integers. If $g(n)={\sum }_{d\mid n}f(d)$ and $(m,n)=1$, every positive integer divisor of $mn$ is uniquely $d_1{d}_2$ with $d_1\mid m$ and $d_2\mid n$. Henceso $g$ is multiplicative.

The Möbius function is defined by $\mu (1)=1$, $\mu (n)=0$ if the square of a prime number divides $n$, and $\mu (n)=(-1{)}^r$ if $n$ is a product of $r$ distinct prime numbers. Coprime integers have disjoint sets of prime factors, so this definition immediately gives $\mu (mn)=\mu (m)\mu (n)$ when $(m,n)=1$.

For $n=p_1^{a_1}\cdots p_r^{a_r}>1$, only the square-free divisors contribute, and thereforeFor $n=1$ the sum is $1$. Thus $1\ast \mu =\epsilon$ in the language of Dirichlet convolution. Convolving $g=1\ast f$ with $\mu$ gives the Möbius inversion formula

If $f(n)=n$, its divisor sum is the sum-of-divisors function. Conversely, if $g(n)=n$, Möbius inversion givesusing the standard divisor identity for the Euler totient function. Therefore the two requested answers are

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.

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.

For unit-modulus prime values, pretentious distance is the Euclidean metric on the finite vectors $(f(p)/\sqrt{2p}{)}_{p\le X}$. On whole arithmetic functions it is only a pseudometric: it sees neither values on prime powers nor primes above the cutoff. Even for every cutoff, the functions one and ${\mu }^2$ have distance zero but differ on nonsquarefree integers. The norm representation proves the triangle inequality and identifies exactly the quotient on which separation holds.

Probabilistic number theory studies arithmetic functions and integer sets through probability distributions, concentration, and limit theorems.

The Second Chebyshev function is the partial sum of the Von Mangoldt function up to a real cutoff $x\ge 0$:For example, $\psi (3)=\log 6$, $\psi (4)=\log 12$, and $\psi (4.5)=\log 12$. At $4=2^2$ the jump has size $\log 2$; between $4$ and $5$ no new prime power greater than one enters the sum. In contrast, the Chebyshev theta function stays at $\vartheta (4)=\log 6$.

There is also an exact connection with the least common multiple. For $N=\lfloor x\rfloor \ge 1$, each prime number $p\le N$ occurs to the highest exponent $k$ for which $p^k\le N$, both in that least common multiple and in the accumulated Von Mangoldt function weights. ThusThis explains the $\log 2520$ value at $x=10$: the least common multiple is $2^3\cdot 3^2\cdot 5\cdot 7$. The Chebyshev theta function instead gives the natural logarithm of the primorial $2\cdot 3\cdot 5\cdot 7=210$. The additional prime powers retain the highest required multiplicities.

Why is this useful for the distribution of prime numbers? The Prime number theorem has the equivalent formswhere $\pi$ is the prime-counting function and $\sim$ denotes asymptotic equivalence. Thus an arithmetic function defined using prime factorization has average weight tending to one over long initial intervals of the positive integers. These are substantive asymptotic equivalences, not consequences of the definitions or the Von Mangoldt divisor identity alone. ^[ref]

The elementary reason the two Chebyshev functions have the same leading behavior is that their difference is small compared with $x$. Every additional prime power has base $p\le \sqrt{x}$, and for each such prime number its total extra weight is at most $\log x$. There are at most $\lfloor \sqrt{x}\rfloor$ such bases, soThis transfers $\psi (x)\sim x$ to $\vartheta (x)\sim x$, or conversely, once either is established. Partial summation then relates the Chebyshev theta function to the prime-counting function. The estimate controls the extra prime powers; proving the leading value itself is the harder Prime number theorem problem.

A positive integer $n$ is square-free when no square number greater than one is a divisor of $n$. It suffices to exclude squares of prime numbers; equivalently, every prime valuation is zero or one:Thus the prime factorization of a square-free integer is a product of distinct prime factors, with no repetitions. One is included: its prime factorization is an empty product and all its prime valuations are zero. These equivalent tests are stated in Grinberg's notes. ^[ref]

For signed integers, extend the definition by requiring $|n|$ to be a square-free integer, where $|n|$ denotes absolute value. Hence $-30$ and both $1,-1$ qualify. Zero does not: every prime number has its square as a divisor of zero. The Möbius function and radical of an integer below use their existing positive integer domains, so apply them to $|n|$ when handling a negative integer.

For example, $30=2\cdot 3\cdot 5$ is a square-free integer, whereas $12=2^2\cdot 3$ is not, because $4\mid 12$ and $v_2(12)=2$. Being a composite number causes no problem: $6,10,15$ are all square-free integers. A square-free integer need not be coprime to another integer: $6$ and $10$ are both square-free integers but have greatest common divisor two. In fact the only signed integers coprime to every integer are $1,-1$, since $\gcd (n,n)=|n|$.

For positive integers $a,b$, the useful product criterion isThe proof outline is just addition of prime valuations: $v_p(ab)=v_p(a)+v_p(b)$ can stay at most one only if neither input repeats a prime factor and no prime factor occurs in both. Thus $6\cdot 5=30$ is a square-free integer, but $6\cdot 10=60$ is not. An equivalent characterization is that every factorization $n=ab$ into positive integers has coprime factors. If $p^2\mid n$, the factorization $n=p(n/p)$ supplies two factors sharing $p$; conversely, a shared prime factor forces its square to divide $n$. For $30$, the unordered factor pairs $(1,30),(2,15),(3,10),(5,6)$ all have greatest common divisor one; for $12$, the pair $(2,6)$ fails.

Two existing arithmetic functions turn the definition into practical tests:The radical of an integer keeps one copy of each prime factor, so it changes precisely the integers with a repeated prime factor. Its definition is given in Evertse's exercise sheet. ^[ref] The Möbius function assigns $(-1{)}^r$ to a square-free integer with $r$ distinct prime factors and zero otherwise; squaring forgets the sign. Consequently ${\sum }_{n=1}^{60}\mu (n{)}^2=37$ counts exactly the green cells. This connects a restriction on repeated prime factors with weighted counting and inclusion-exclusion. ^[ref]

The total number of prime factors $\Omega (n)$ counts every occurrence of a prime factor in the prime factorization of a positive integer $n$. Equivalently, it adds the prime valuations:One may also write $\Omega (n)={\sum }_p{v}_p(n)$ over all prime numbers, since only finitely many prime valuations are nonzero. The empty sum gives $\Omega (1)=0$. By contrast, the prime omega function has $\omega (n)=r$ and counts distinct prime factors. ^[ref]

Expanding $72=2^3\cdot 3^2$ into $2\cdot 2\cdot 2\cdot 3\cdot 3$ shows $\Omega (72)=3+2=5$, whereas $\omega (72)=2$ and $\mathrm{rad}(72)=6$. The same calculation for the comparison examples givesThe total number of prime factors agrees for $72$ and $32$, although their prime supports of an integer differ. Meanwhile $72$ and $36$ have the same radical of an integer and prime omega function, but different values of the total number of prime factors. These examples show exactly which information each arithmetic function forgets.

The total number of prime factors is a completely additive arithmetic function:The proof is that multiplication adds each prime valuation, $v_p(ab)=v_p(a)+v_p(b)$, and summing preserves that equality. No coprimality condition is needed. For example, $12=2^2\cdot 3$ and $18=2\cdot 3^2$ both have total number of prime factors three; their product $216=2^3\cdot 3^3$ has six. By comparison, the prime omega function is only an additive arithmetic function: here $\omega (216)=2\ne 4=\omega (12)+\omega (18)$.

There is a useful way to see the total number of prime factors as a count of elementary building blocks: any expression of $n$ as a product of prime numbers has exactly $\Omega (n)$ factors, by the fundamental theorem of arithmetic. Equivalently, every factorization tree for $n>1$ has $\Omega (n)$ leaves. Repeated prime factors increase this count without introducing new kinds of prime number. The difference is the existing excess prime-factor multiplicity:Every summand is nonnegative, so $\Omega (n)=\omega (n)$ if and only if $n$ is a squarefree integer, including $n=1$. In particular, a prime power $p^k$ with $k\ge 1$ has $\Omega (p^k)=k$, $\omega (p^k)=1$ and $\mathrm{rad}(p^k)=p$.

Historically, Hardy and Ramanujan's 1917 paper explicitly separated the prime omega function from the total number of prime factors, writing them as $f(n)$ and $F(n)$, respectively. Their example $2^3\cdot 3^2\cdot 5$ has counts three and six. That distinction let them compare two measures of how an integer is built from prime factors. ^[ref]

The Von Mangoldt function assigns a natural logarithm weight to each positive power of a prime number. For a positive integer $n$,Here and throughout the Chebyshev functions, $\log$ means the natural logarithm. In particular, $\Lambda (1)=0$: the exponent must be positive, even though the convention in prime power allows exponent zero. The support of a function of $\Lambda$ therefore consists precisely of the prime powers greater than one. ^[ref]

For example, $\Lambda (2)=\Lambda (4)=\Lambda (8)=\log 2$ and $\Lambda (3)=\Lambda (9)=\log 3$, whereas $\Lambda (6)=\Lambda (12)=0$. A composite number can have a nonzero weight: $8$ has just one distinct prime factor. But $12=2^2\cdot 3$ has two distinct prime factors, so its weight is zero. At $p^k$ the weight is $\log p$, not $\log (p^k)=k\log p$. This choice lets successive powers record successive copies of the same prime factor in the Von Mangoldt divisor identity.

The Von Mangoldt function is useful because it connects two views of the prime numbers: the prime factorization of an individual integer, through a divisor sum, and the accumulated weights below a cutoff, through the Second Chebyshev function. The latter turns questions about the distribution of prime numbers into questions about a partial sum of an arithmetic function.