Möbius function
Encyclopedia
- For the rational functions defined on the complex numbers, see Möbius transformation.
The classical Möbius function μ(n) is an important multiplicative function
Multiplicative function
In number theory, a multiplicative function is an arithmetic function f of the positive integer n with the property that f = 1 and whenevera and b are coprime, then...
in number theory
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
and combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
. The German mathematician August Ferdinand Möbius
August Ferdinand Möbius
August Ferdinand Möbius was a German mathematician and theoretical astronomer.He is best known for his discovery of the Möbius strip, a non-orientable two-dimensional surface with only one side when embedded in three-dimensional Euclidean space. It was independently discovered by Johann Benedict...
introduced it in 1832. This classical Möbius function is a special case of a more general object in combinatorics (see below).
Definition
μ(n) is defined for all positive integerInteger
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s n and has its values in
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
of n into prime factor
Prime factor
In number theory, the prime factors of a positive integer are the prime numbers that divide that integer exactly, without leaving a remainder. The process of finding these numbers is called integer factorization, or prime factorization. A prime factor can be visualized by understanding Euclid's...
s. It is defined as follows:
- μ(n) = 1 if n is a square-freeSquare-free integerIn mathematics, a square-free, or quadratfrei, integer is one divisible by no perfect square, except 1. For example, 10 is square-free but 18 is not, as it is divisible by 9 = 32...
positive integer with an evenEven and odd numbersIn mathematics, the parity of an object states whether it is even or odd.This concept begins with integers. An even number is an integer that is "evenly divisible" by 2, i.e., divisible by 2 without remainder; an odd number is an integer that is not evenly divisible by 2...
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
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 :
- 1, −1, −1, 0, −1, 1, −1, 0, 0, 1, −1, 0, −1, 1, 1, 0, −1, 0, −1, 0, 1, 1, −1, 0, 0, ...
The first 50 values of the function are plotted below:
Properties and applications
The Möbius function is multiplicativeMultiplicative function
In number theory, a multiplicative function is an arithmetic function f of the positive integer n with the property that f = 1 and whenevera and b are coprime, then...
(i.e. μ(ab) = μ(a) μ(b) whenever a and b are coprime
Coprime
In number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...
). 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 odd numbers of elements as subsets with even numbers of elements - in the same way as binomial coefficients exhibit alternating entries of odd and even power which sum symmetrically.) This leads to the important Möbius inversion formula
Möbius inversion formula
In mathematics, the classic Möbius inversion formula was introduced into number theory during the 19th century by August Ferdinand Möbius. Other Möbius inversion formulas are obtained when different local finite partially ordered sets replace the classic case of the natural numbers ordered by...
and is the main reason why μ is of relevance in the theory of multiplicative and arithmetic functions.
Other applications of μ(n) in combinatorics are connected with the use of the Pólya enumeration theorem
Pólya enumeration theorem
The Pólya enumeration theorem , also known as the Redfield–Pólya Theorem, is a theorem in combinatorics that both follows and ultimately generalizes Burnside's lemma on the number of orbits of a group action on a set. The theorem was first published by John Howard Redfield in 1927...
in combinatorial groups and combinatorial enumerations.
In number theory another arithmetic function
Arithmetic function
In number theory, an arithmetic function is a real or complex valued function ƒ defined on the set of natural numbers In number theory, an arithmetic (or arithmetical) function is a real or complex valued function ƒ(n) defined on the set of natural numbers In number theory, an arithmetic (or...
closely related to the Möbius function is the Mertens function, defined by
for every natural number n. This function is closely linked with the positions of zeroes of the Riemann zeta function. See the article on the Mertens conjecture
Mertens conjecture
In mathematics, the Mertens conjecture is the incorrect statement that the Mertens function M is bounded by √n, which implies the Riemann hypothesis...
for more information about the connection between M(n) and the Riemann hypothesis
Riemann hypothesis
In mathematics, the Riemann hypothesis, proposed by , is a conjecture about the location of the zeros of the Riemann zeta function which states that all non-trivial zeros have real part 1/2...
.
The ordinary generating function for the Möbius function follows from the binomial series
applied to triangular matrices:
The Lambert series for the Möbius function is:
The Dirichlet series that generates
Generating function
In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general...
the Möbius function is the (multiplicative) inverse of the Riemann zeta function
This is easy to see from its Euler product
Euler product
In number theory, an Euler product is an expansion of a Dirichlet series into an infinite product indexed by prime numbers. The name arose from the case of the Riemann zeta-function, where such a product representation was proved by Leonhard Euler.-Definition:...
There is a formula for calculating the Möbius function without knowing the factorization of its argument:
i.e. μ(n) is the sum of the primitive nth roots of unity.
From this it follows that the Mertens function is given by:
where 
is the Farey sequenceFarey sequence
In mathematics, the Farey sequence of order n is the sequence of completely reduced fractions between 0 and 1 which, when in lowest terms, have denominators less than or equal to n, arranged in order of increasing size....
of order n.
This formula is used in the proof of the Franel-Landau theorem.
Gauss proved that for a prime number p the sum of its primitive roots is congruent to μ(p − 1) (mod p).
If Fq denotes the finite field
Finite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
of order q (where q is necessarily a prime power), then the number N of monic irreducible polynomials of degree n over Fq is given by:
The infinite symmetric matrix starting:
defined by the recurrence:
can be used to calculate the Möbius function:
Average order
The average orderAverage order of an arithmetic function
In number theory, the average order of an arithmetic function is some simpler or better-understood function which takes the same values "on average".Let f be an arithmetic function...
of the Möbius function is zero. This statement is, in fact, equivalent to the prime number theorem
Prime number theorem
In number theory, the prime number theorem describes the asymptotic distribution of the prime numbers. The prime number theorem gives a general description of how the primes are distributed amongst the positive integers....
.
μ(n) sections
μ(n) = 0 if and only ifIf and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
n is divisible by a square. The first numbers with this property are :
- 4, 8, 9, 12, 16, 18, 20, 24, 25, 27, 28, 32, 36, 40, 44, 45, 48, 49, 50, 52, 54, 56, 60, 63,....
If n is prime, then μ(n) = −1, but the converse is not true. The first non prime n for which μ(n) = −1 is 30 = 2·3·5. The first such numbers with three distinct prime factors (sphenic number
Sphenic number
In number theory, a sphenic number is a positive integer which is the product of three distinct prime numbers.Note that this definition is more stringent than simply requiring the integer to have exactly three prime factors; e.g. 60 = 22 × 3 × 5 has exactly 3 prime factors, but is not sphenic.All...
s) are:
- 30, 42, 66, 70, 78, 102, 105, 110, 114, 130, 138, 154, 165, 170, 174, 182, 186, 190, 195, 222, … .
and the first such numbers with 5 distinct prime factors are:
- 2310, 2730, 3570, 3990, 4290, 4830, 5610, 6006, 6090, 6270, 6510, 6630, 7410, 7590, 7770, 7854, 8610, 8778, 8970, 9030, 9282, 9570, 9690, … .
Generalization
In combinatoricsCombinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
, every locally finite partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
(poset) is assigned an incidence algebra
Incidence algebra
In order theory, a field of mathematics, an incidence algebra is an associative algebra, defined for any locally finite partially ordered setand commutative ring with unity.-Definition:...
. One distinguished member of this algebra is that poset's "Möbius function". The classical Möbius function treated in this article is essentially equal to the Möbius function of the set of all positive integers partially ordered by divisibility
Divisor
In mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...
. See the article on incidence algebra
Incidence algebra
In order theory, a field of mathematics, an incidence algebra is an associative algebra, defined for any locally finite partially ordered setand commutative ring with unity.-Definition:...
s for the precise definition and several examples of these general Möbius functions.
Physics
The Möbius function also arises in the primon gasPrimon gas
In mathematical physics, the primon gas or free Riemann gas is a toy model illustrating in a simple way some correspondences between number theory and ideas in quantum field theory and dynamical systems. It is a quantum field theory of a set of non-interacting particles, the primons; it is called a...
or free Riemann gas model of supersymmetry
Supersymmetry
In particle physics, supersymmetry is a symmetry that relates elementary particles of one spin to other particles that differ by half a unit of spin and are known as superpartners...
. In this theory, the fundamental particles or "primons" have energies log p. Under second-quantization, multiparticle excitations are considered; these are given by log n for any natural number n. This follows from the fact that the factorization of the natural numbers into primes is unique.
In the free Riemann gas, any natural number can occur, if the primon
Primon gas
In mathematical physics, the primon gas or free Riemann gas is a toy model illustrating in a simple way some correspondences between number theory and ideas in quantum field theory and dynamical systems. It is a quantum field theory of a set of non-interacting particles, the primons; it is called a...
s are taken as boson
Boson
In particle physics, bosons are subatomic particles that obey Bose–Einstein statistics. Several bosons can occupy the same quantum state. The word boson derives from the name of Satyendra Nath Bose....
s. If they are taken as fermion
Fermion
In particle physics, a fermion is any particle which obeys the Fermi–Dirac statistics . Fermions contrast with bosons which obey Bose–Einstein statistics....
s, then the Pauli exclusion principle
Pauli exclusion principle
The Pauli exclusion principle is the quantum mechanical principle that no two identical fermions may occupy the same quantum state simultaneously. A more rigorous statement is that the total wave function for two identical fermions is anti-symmetric with respect to exchange of the particles...
excludes squares. The operator (−1)F
(-1)^F
In a quantum field theory with fermions, F is a unitary, Hermitian, involutive operator which multiplies bosonic states by 1 and fermionic states by −1. This is always a global internal symmetry of any quantum field theory with fermions and corresponds to a rotation by 2π. This splits the Hilbert...
which distinguishes fermions and bosons is then none other than the Möbius function μ(n).
The free Riemann gas has a number of other interesting connections to number theory, including the fact that the partition function
Partition function (statistical mechanics)
Partition functions describe the statistical properties of a system in thermodynamic equilibrium. It is a function of temperature and other parameters, such as the volume enclosing a gas...
is the Riemann zeta function. This idea underlies Alain Connes
Alain Connes
Alain Connes is a French mathematician, currently Professor at the Collège de France, IHÉS, The Ohio State University and Vanderbilt University.-Work:...
' attempted proof of the Riemann hypothesis
Riemann hypothesis
In mathematics, the Riemann hypothesis, proposed by , is a conjecture about the location of the zeros of the Riemann zeta function which states that all non-trivial zeros have real part 1/2...
.