Möbius function

related topics
{math, number, function}
{math, energy, light}

The classical Möbius function μ(n) is an important multiplicative function in number theory and combinatorics. The German mathematician August Ferdinand Möbius introduced it in 1832.[1][2] This classical Möbius function is a special case of a more general object in combinatorics (see below).

Contents

Definition

μ(n) is defined for all positive integers n and has its values in {−1, 0, 1} depending on the factorization of n into prime factors. It is defined as follows:

  • μ(n) = 1 if n is a square-free positive integer with an even number of prime factors.
  • μ(n) = −1 if n is a square-free positive integer with an odd number of prime factors.
  • μ(n) = 0 if n is not square-free.

An equivalent way to state this is to define the two functions

ω(n), the number of distinct primes dividing the number n and
Ω(n), the number of prime factors of n, counted with multiplicities. Clearly, ω(n) ≤ Ω(n).

Then

\mu(n)=\begin{cases} (-1)^{\omega(n)}=(-1)^{\Omega(n)} &\mbox{if }\; \omega(n) = \Omega(n)\\
0&\mbox{if }\;\omega(n) < \Omega(n).\end{cases}


This implies that μ(1) = 1. (1 has an even number of prime factors, namely zero). The value of μ(0) is undefined.

Values of μ(n) for the first 25 positive numbers (sequence A008683 in OEIS):

The 50 first values of the function are plotted below:

Properties and applications

The Möbius function is multiplicative (i.e. μ(ab) = μ(aμ(b) whenever a and b are coprime). The sum over all positive divisors of n of the Möbius function is zero except when n = 1:

(A consequence of the fact that every non-empty finite set has just as many subsets with an even number of elements as it has subsets with an odd number of elements.) This leads to the important Möbius inversion formula and is the main reason why μ is of relevance in the theory of multiplicative and arithmetic functions.

Full article ▸

related documents
Cyclone (programming language)
Commutator
Banach algebra
Elementary function
Square-free integer
Pre-Abelian category
Bounded set
String searching algorithm
Principal ideal domain
Fermat's little theorem
Tuple
Multiplication table
Enriched category
HMAC
Infimum
Homomorphism
Caesar cipher
Division ring
Linear classifier
Binary space partitioning
Floor and ceiling functions
Semi-continuity
Elliptic function
Loss of significance
Counting sort
Pseudocode
Iterative method
Cofinality
Ternary numeral system
Twin prime