The Möbius function, denoted by , is a function on the positive integers taking values in . It is zero when is divisible by the square of a prime; otherwise, it records whether 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 , the Möbius function is defined by
An integer not divisible by the square of any prime is called a squarefree integer. Thus, vanishes exactly on the non-squarefree positive integers.
The first twelve values are:
For example,
whereas , because .
The definition is unambiguous by the fundamental theorem of arithmetic, which guarantees unique prime factorization. The value agrees with viewing as a product of no primes.
Multiplicativity and the divisor identity
The Möbius function is a multiplicative function: if and have greatest common divisor , then
It is not completely multiplicative, because this equality need not hold without the coprimality condition. For a prime ,
Its central divisor identity is
To see why, suppose has 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
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 and on the positive integers satisfy
then
Thus, knowing the sum of over the divisors of every integer determines itself.
For complex-valued functions, the formula follows by substituting the expression for :
The inner sum is zero unless , when it equals , leaving .
Dirichlet convolution
This relationship has an algebraic formulation using Dirichlet convolution, defined by
Let for every positive integer, and let
The function is the identity for Dirichlet convolution, and the divisor identity says
Consequently, is the convolution inverse of the constant-one function. Möbius inversion is then the implication
Counting applications
Euler’s totient function
Euler’s totient function counts the integers from to that are coprime to . It satisfies
Möbius inversion therefore yields
where the product runs over the distinct prime divisors of .
More generally, the coprimality indicator can be written as
Summing this identity over gives the exact count
Squarefree integers
Because is precisely when is squarefree,
Hence the number of squarefree positive integers at most is
This gives
with the error expressed in big-O notation. In particular, the natural density of squarefree integers is .
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 symbols, let count length- words that are not repetitions of a shorter word. Every word has a unique shortest repeating block, so
Therefore,
Since each primitive word has distinct cyclic rotations, counts primitive necklaces of length .
Dirichlet series and the Riemann zeta function
The Möbius function is closely connected with the Riemann zeta function. For a complex number with ,
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,
These identities connect prime factorization with complex analysis. The first identity cannot simply be interpreted as an ordinarily convergent series throughout every region where has an analytic continuation; convergence requires separate justification.
The Mertens function and cancellation
The summatory Möbius function is called the Mertens function:
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
meaning that . Thus, although the individual values of are irregular, their average tends to zero.
A stronger statement is equivalent to the Riemann hypothesis:
The former Mertens conjecture asserted
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 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 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 , sieve methods are more efficient than factoring each integer separately. A simple sieve starts each value at , 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
for prime , together with . By arranging for each composite integer to be processed once, it computes the table in arithmetic operations using 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 is finite. This generalized function is defined recursively by
When the positive integers are ordered by divisibility,
For subsets ordered by inclusion,
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.