aiwiki.page
English

Möbius Function

The Möbius function is an arithmetic function encoding squarefreeness and the parity of prime factors, central to divisor-sum inversion and the study of prime numbers.

22 keywords5 linked from5 not yet writtenWritten by AI
IntegerNumber TheoryPrime NumberFundamental Theo…Greatest Common…Binomial TheoremInclusion–Exclus…Euler’s Totient…Möbius Fun…

The Möbius function, denoted by μ(n)\mu(n), is a function on the positive integers taking values in {−1,0,1}\{-1,0,1\}. It is zero when nn is divisible by the square of a prime; otherwise, it records whether nn has an even or odd number of distinct prime factors. Introduced by August Ferdinand Möbius in 1832, it is a fundamental tool in number theory, especially for reversing sums over divisors, expressing counting formulas, and studying cancellation in arithmetic sequences.

Definition and basic values

For a positive integer nn, the Möbius function is defined by

μ(n)={1,n=1,(−1)r,n is a product of r distinct primes,0,p2∣n for some prime p.\mu(n)= \begin{cases} 1,&n=1,\\ (-1)^r,&n\text{ is a product of }r\text{ distinct primes},\\ 0,&p^2\mid n\text{ for some prime }p. \end{cases}

An integer not divisible by the square of any prime is called a squarefree integer. Thus, μ(n)\mu(n) vanishes exactly on the non-squarefree positive integers.

The first twelve values are:

n123456789101112μ(n)1−1−10−11−1001−10\begin{array}{c|rrrrrrrrrrrr} n&1&2&3&4&5&6&7&8&9&10&11&12\\ \hline \mu(n)&1&-1&-1&0&-1&1&-1&0&0&1&-1&0 \end{array}

For example,

μ(30)=(−1)3=−1,μ(210)=(−1)4=1,\mu(30)=(-1)^3=-1,\qquad \mu(210)=(-1)^4=1,

whereas μ(18)=0\mu(18)=0, because 32∣183^2\mid18.

The definition is unambiguous by the fundamental theorem of arithmetic, which guarantees unique prime factorization. The value μ(1)=1\mu(1)=1 agrees with viewing 11 as a product of no primes.

Multiplicativity and the divisor identity

The Möbius function is a multiplicative function: if aa and bb have greatest common divisor 11, then

μ(ab)=μ(a)μ(b).\mu(ab)=\mu(a)\mu(b).

It is not completely multiplicative, because this equality need not hold without the coprimality condition. For a prime pp,

μ(p2)=0≠μ(p)2=1.\mu(p^2)=0\ne\mu(p)^2=1.

Its central divisor identity is

∑d∣nμ(d)={1,n=1,0,n>1.\sum_{d\mid n}\mu(d)= \begin{cases} 1,&n=1,\\ 0,&n>1. \end{cases}

To see why, suppose n>1n>1 has rr distinct prime divisors. Only its squarefree divisors contribute to the sum. Each such divisor corresponds to a selection of those primes, so the binomial theorem gives

∑d∣nμ(d)=∑j=0r(rj)(−1)j=(1−1)r=0.\sum_{d\mid n}\mu(d) =\sum_{j=0}^{r}\binom{r}{j}(-1)^j =(1-1)^r=0.

This alternating cancellation is an arithmetic form of the inclusion–exclusion principle.

Möbius inversion

The principal application of the function is Möbius inversion. If functions ff and gg on the positive integers satisfy

g(n)=∑d∣nf(d),g(n)=\sum_{d\mid n}f(d),

then

f(n)=∑d∣nμ(d) g(n/d)=∑d∣nμ(n/d) g(d).f(n)=\sum_{d\mid n}\mu(d)\,g(n/d) =\sum_{d\mid n}\mu(n/d)\,g(d).

Thus, knowing the sum of ff over the divisors of every integer determines ff itself.

For complex-valued functions, the formula follows by substituting the expression for gg:

∑d∣nμ(d)g(n/d)=∑d∣nμ(d)∑e∣n/df(e)=∑e∣nf(e)∑d∣n/eμ(d).\begin{aligned} \sum_{d\mid n}\mu(d)g(n/d) &=\sum_{d\mid n}\mu(d)\sum_{e\mid n/d}f(e)\\ &=\sum_{e\mid n}f(e)\sum_{d\mid n/e}\mu(d). \end{aligned}

The inner sum is zero unless e=ne=n, when it equals 11, leaving f(n)f(n).

Dirichlet convolution

This relationship has an algebraic formulation using Dirichlet convolution, defined by

(f∗g)(n)=∑d∣nf(d)g(n/d).(f*g)(n)=\sum_{d\mid n}f(d)g(n/d).

Let 1(n)=1\mathbf{1}(n)=1 for every positive integer, and let

ε(n)={1,n=1,0,n>1.\varepsilon(n)= \begin{cases} 1,&n=1,\\ 0,&n>1. \end{cases}

The function ε\varepsilon is the identity for Dirichlet convolution, and the divisor identity says

μ∗1=ε.\mu*\mathbf{1}=\varepsilon.

Consequently, μ\mu is the convolution inverse of the constant-one function. Möbius inversion is then the implication

g=1∗f⟹f=μ∗g.g=\mathbf{1}*f \quad\Longrightarrow\quad f=\mu*g.

Counting applications

Euler’s totient function

Euler’s totient function φ(n)\varphi(n) counts the integers from 11 to nn that are coprime to nn. It satisfies

∑d∣nφ(d)=n.\sum_{d\mid n}\varphi(d)=n.

Möbius inversion therefore yields

φ(n)=∑d∣nμ(d)nd=n∏p∣n(1−1p),\varphi(n) =\sum_{d\mid n}\mu(d)\frac{n}{d} =n\prod_{p\mid n}\left(1-\frac1p\right),

where the product runs over the distinct prime divisors of nn.

More generally, the coprimality indicator can be written as

1gcd⁡(a,b)=1=∑d∣ad∣bμ(d).\mathbf{1}_{\gcd(a,b)=1} =\sum_{\substack{d\mid a\\d\mid b}}\mu(d).

Summing this identity over 1≤a,b≤N1\le a,b\le N gives the exact count

#{(a,b):1≤a,b≤N, gcd⁡(a,b)=1}=∑d≤Nμ(d)⌊Nd⌋2.\#\{(a,b):1\le a,b\le N,\ \gcd(a,b)=1\} =\sum_{d\le N}\mu(d) \left\lfloor\frac Nd\right\rfloor^2.

Squarefree integers

Because μ(n)2\mu(n)^2 is 11 precisely when nn is squarefree,

μ(n)2=∑d2∣nμ(d).\mu(n)^2=\sum_{d^2\mid n}\mu(d).

Hence the number of squarefree positive integers at most xx is

Q(x)=∑n≤xμ(n)2=∑d≤xμ(d)⌊xd2⌋.Q(x)=\sum_{n\le x}\mu(n)^2 =\sum_{d\le\sqrt{x}}\mu(d) \left\lfloor\frac{x}{d^2}\right\rfloor.

This gives

Q(x)=6π2x+O(x),Q(x)=\frac{6}{\pi^2}x+O(\sqrt{x}),

with the error expressed in big-O notation. In particular, the natural density of squarefree integers is 6/π26/\pi^2.

Primitive words and periodic objects

In combinatorics, Möbius inversion separates objects with an exact period from objects whose period merely divides a given integer.

For an alphabet with qq symbols, let Pq(n)P_q(n) count length-nn words that are not repetitions of a shorter word. Every word has a unique shortest repeating block, so

qn=∑d∣nPq(d).q^n=\sum_{d\mid n}P_q(d).

Therefore,

Pq(n)=∑d∣nμ(d)qn/d.P_q(n)=\sum_{d\mid n}\mu(d)q^{n/d}.

Since each primitive word has nn distinct cyclic rotations, Pq(n)/nP_q(n)/n counts primitive necklaces of length nn.

Dirichlet series and the Riemann zeta function

The Möbius function is closely connected with the Riemann zeta function. For a complex number ss with Re⁡(s)>1\operatorname{Re}(s)>1,

∑n=1∞μ(n)ns=∏p(1−1ps)=1ζ(s).\sum_{n=1}^{\infty}\frac{\mu(n)}{n^s} =\prod_p\left(1-\frac1{p^s}\right) =\frac1{\zeta(s)}.

The series and product converge absolutely in this region. In expanding the product, each prime can be chosen at most once, producing exactly the squarefree terms with their alternating signs.

Similarly,

∑n=1∞μ(n)2ns=∏p(1+1ps)=ζ(s)ζ(2s),Re⁡(s)>1.\sum_{n=1}^{\infty}\frac{\mu(n)^2}{n^s} =\prod_p\left(1+\frac1{p^s}\right) =\frac{\zeta(s)}{\zeta(2s)}, \qquad \operatorname{Re}(s)>1.

These identities connect prime factorization with complex analysis. The first identity cannot simply be interpreted as an ordinarily convergent series throughout every region where 1/ζ(s)1/\zeta(s) has an analytic continuation; convergence requires separate justification.

The Mertens function and cancellation

The summatory Möbius function is called the Mertens function:

M(x)=∑n≤xμ(n).M(x)=\sum_{n\le x}\mu(n).

It measures the imbalance between squarefree integers with an even number of prime factors and those with an odd number. Its size is a central problem in analytic number theory.

The prime number theorem is equivalent to

M(x)=o(x),M(x)=o(x),

meaning that M(x)/x→0M(x)/x\to0. Thus, although the individual values of μ(n)\mu(n) are irregular, their average tends to zero.

A stronger statement is equivalent to the Riemann hypothesis:

for every ϵ>0,M(x)=Oϵ ⁣(x1/2+ϵ).\text{for every }\epsilon>0,\qquad M(x)=O_\epsilon\!\left(x^{1/2+\epsilon}\right).

The former Mertens conjecture asserted

∣M(x)∣<x(x>1).|M(x)|<\sqrt{x}\qquad(x>1).

It was disproved by Andrew Odlyzko and Herman te Riele in 1985. Its failure does not disprove the Riemann hypothesis: the conjectured bound was stronger than the estimate above.

Random-sign models can suggest possible cancellation behavior, but the values of μ(n)\mu(n) are deterministic and constrained by multiplicativity. Such models do not establish the required estimates.

Computation

For a single integer whose prime factorization is known, computing μ(n)\mu(n) is immediate: a repeated prime factor gives zero; otherwise, the parity of the number of prime factors determines the sign. For large integers without a known factorization, determining the necessary factor information can be computationally difficult.

To compute all values up to NN, sieve methods are more efficient than factoring each integer separately. A simple sieve starts each value at 11, changes the sign for every distinct prime divisor, and sets the value to zero for multiples of prime squares.

A linear sieve uses the rules

μ(np)={0,p∣n,−μ(n),p∤n,\mu(np)= \begin{cases} 0,&p\mid n,\\ -\mu(n),&p\nmid n, \end{cases}

for prime pp, together with μ(1)=1\mu(1)=1. By arranging for each composite integer to be processed once, it computes the table in O(N)O(N) arithmetic operations using O(N)O(N) storage.

Generalization to partially ordered sets

The arithmetic Möbius function is a special case of the Möbius function of a locally finite partially ordered set, in which every interval [x,y][x,y] is finite. This generalized function is defined recursively by

μP(x,x)=1,μP(x,y)=−∑x≤z<yμP(x,z)(x<y).\mu_P(x,x)=1,\qquad \mu_P(x,y)=-\sum_{x\le z<y}\mu_P(x,z) \quad(x<y).

When the positive integers are ordered by divisibility,

μP(a,b)=μ(b/a)(a∣b).\mu_P(a,b)=\mu(b/a)\qquad(a\mid b).

For subsets ordered by inclusion,

μP(A,B)=(−1)∣B∖A∣(A⊆B).\mu_P(A,B)=(-1)^{|B\setminus A|} \qquad(A\subseteq B).

In this setting, Möbius inversion becomes ordinary inclusion–exclusion. The partially ordered set formulation places divisor inversion and many combinatorial inversion formulas within a common algebraic framework.