Möbius function
{{#invoke:Hatnote|hatnote}}
- For the rational functions defined on the complex numbers, see Möbius transformation.
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).
Definition
For any positive integer n, define μ(n) as the sum of the primitive Template:Mvar-th roots of unity. It has values in {−1, 0, 1} depending on the factorization of n into prime factors:
- μ(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 has a squared prime factor.
The values of μ(n) for the first 30 positive numbers (sequence A008683 in OEIS) are
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
μ(n) | 1 | −1 | −1 | 0 | −1 | 1 | −1 | 0 | 0 | 1 |
n | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
μ(n) | −1 | 0 | −1 | 1 | 1 | 0 | −1 | 0 | −1 | 0 |
n | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
μ(n) | 1 | 1 | −1 | 0 | 0 | 1 | 0 | 0 | −1 | −1 |
The first 50 values of the function are plotted below:
Properties and applications
Properties
The Möbius function is multiplicative (i.e. μ(ab) = μ(a) μ(b) whenever Template:Mvar and Template:Mvar are coprime). The sum over all positive divisors of Template:Mvar (including Template:Mvar itself and 1) of the Möbius function is zero except when n = 1:
This is because the Template:Mvar-th roots of unity sum to 0, and each Template:Mvar-th root of unity is a primitive Template:Mvar-th root of unity for exactly one divisor Template:Mvar of Template:Mvar.
The equality above leads to the important Möbius inversion formula and is the main reason why Template:Mvar 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 in combinatorial groups and combinatorial enumerations.
Mertens function
In number theory another arithmetic function closely related to the Möbius function is the Mertens function, defined by
for every natural number Template:Mvar. This function is closely linked with the positions of zeroes of the Riemann zeta function. See the article on the Mertens conjecture for more information about the connection between M(n) and the Riemann hypothesis.
There is a formula^{[3]} for calculating the Möbius function without directly knowing the factorization of its argument:
i.e. μ(n) is the sum of the primitive Template:Mvar-th roots of unity. (However, the computational complexity of this definition is at least the same as of the Euler Product definition.)
From this it follows that the Mertens function is given by:
where is the Farey sequence of order Template:Mvar.
This formula is used in the proof of the Franel–Landau theorem.^{[4]}
Proof of the formula for
The formula given above,
is trivially true when n = 1. Suppose then that n > 1. Then there is a bijection between the factors Template:Mvar of Template:Mvar for which μ(d) ≠ 0 and the subsets of the set of all prime factors of Template:Mvar. The asserted result follows from the fact that every non-empty finite set has an equal number of odd- and even-cardinality subsets.
This last fact can be shown easily by induction on the cardinality |S| of a non-empty finite set Template:Mvar. First, if |S| = 1, there is exactly one odd-cardinality subset of Template:Mvar, namely Template:Mvar itself, and exactly one even-cardinality subset, namely ∅. Next, if |S| > 1, then divide the subsets of Template:Mvar into two subclasses depending on whether they contain or not some fixed element Template:Mvar in Template:Mvar. There is an obvious bijection between these two subclasses, pairing those subsets that have the same complement relative to the subset {x}. Also, one of these two subclasses consists of all the subsets of the set S \{x}, and therefore, by the induction hypothesis, has an equal number of odd- and even-cardinality subsets. These subsets in turn correspond bijectively to the even- and odd-cardinality {x}-containing subsets of Template:Mvar. The inductive step follows directly from these two bijections.
A related result is that the binomial coefficients exhibit alternating entries of odd and even power which sum symmetrically.
Applications
Mathematical series
The Dirichlet series that generates the Möbius function is the (multiplicative) inverse of the Riemann zeta function; if s is a complex number with real part larger than 1 we have
This may be seen from its Euler product
When s is a complex number with real part larger than 1, the Dirichlet series for the Möbius function also satisfies:{{ safesubst:#invoke:Unsubst||date=__DATE__ |$B= {{#invoke:Category handler|main}}{{#invoke:Category handler|main}}^{[citation needed]} }}
The Lambert series for the Möbius function is:
The ordinary generating function for the Möbius function follows from the binomial series{{ safesubst:#invoke:Unsubst||date=__DATE__ |$B= {{#invoke:Category handler|main}}{{#invoke:Category handler|main}}^{[citation needed]} }}
applied to triangular matrices:Template:Clarify
Algebraic number theory
Gauss^{[5]} proved that for a prime number Template:Mvar the sum of its primitive roots is congruent to μ(p − 1) (mod p).
If F_{q} denotes the finite field of order Template:Mvar (where Template:Mvar is necessarily a prime power), then the number Template:Mvar of monic irreducible polynomials of degree Template:Mvar over F_{q} is given by:^{[6]}
Recurrence
The simplest recurrence for the Möbius function without using the modulo function, is a combination of two recurrences in a table :{{ safesubst:#invoke:Unsubst||date=__DATE__ |$B= {{#invoke:Category handler|main}}{{#invoke:Category handler|main}}^{[citation needed]} }}
This is a table starting:
Matrix inverse
The table equal to if divides and equal to otherwise:
has the matrix inverse equal to if divides and otherwise.{{ safesubst:#invoke:Unsubst||date=__DATE__ |$B= {{#invoke:Category handler|main}}{{#invoke:Category handler|main}}^{[citation needed]} }}
Average order
The average order of the Möbius function is zero. This statement is, in fact, equivalent to the prime number theorem.^{[7]}
μ(n) sections
μ(n) = 0 if and only if n is divisible by the square of a prime. The first numbers with this property are (sequence A013929 in OEIS):
- 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 numbers) are:
- 30, 42, 66, 70, 78, 102, 105, 110, 114, 130, 138, 154, 165, 170, 174, 182, 186, 190, 195, 222, … (sequence A007304 in OEIS).
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, … (sequence A046387 in OEIS).
Generalizations
Incidence algebras
In combinatorics, every locally finite partially ordered set (poset) is assigned an incidence algebra. 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. See the article on incidence algebras for the precise definition and several examples of these general Möbius functions.
Popovici's function
Popovici defined a generalised Möbius function to be the k-fold Dirichlet convolution of the Möbius function with itself. It is thus again a multiplicative function with
where the binomial coefficient is taken to be zero if a > k. The definition may be extended to complex k by reading the binomial as a polynomial in k.^{[8]}
Physics
The Möbius function also arises in the primon gas or free Riemann gas model of supersymmetry. 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 primons are taken as bosons. If they are taken as fermions, then the Pauli exclusion principle excludes squares. The operator (−1)^{F} that 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 is the Riemann zeta function. This idea underlies Alain Connes' attempted proof of the Riemann hypothesis.^{[9]}
See also
Notes
- ↑ Hardy & Wright, Notes on ch. XVI: "... μ(n) occurs implicitly in the works of Euler as early as 1748, but Möbius, in 1832, was the first to investigate its properties systematically."
- ↑ In the Disquisitiones Arithmeticae (1801) Carl Friedrich Gauss showed that the sum of the primitive roots (mod p) is μ(p − 1), (see #Properties and applications) but he didn't make further use of the function. In particular, he didn't use Möbius inversion in the Disquisitiones.
- ↑ Template:Harvnb
- ↑ Edwards, Ch. 12.2
- ↑ Gauss, Disquisitiones, Art. 81
- ↑ Template:Harvnb
- ↑ Template:Harvnb
- ↑ Sandor & Crstici (2004) p.107
- ↑ J.-B. Bost and Alain Connes (1995), "Hecke Algebras, Type III factors and phase transitions with spontaneous symmetry breaking in number theory", Selecta Math. (New Series), 1 411-457.
References
Template:Refbegin The Disquisitiones Arithmeticae has been translated from Latin into English and German. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.
- {{#invoke:citation/CS1|citation
|CitationClass=citation }}
- {{#invoke:citation/CS1|citation
|CitationClass=citation }}
- Template:Apostol IANT
- Computing the summation of the Möbius function by Marc Deléglise and Joël Rivat Experimental Mathematics Volume 5, Issue 4291-295
- {{#invoke:citation/CS1|citation
|CitationClass=citation }}
- {{#invoke:citation/CS1|citation
|CitationClass=citation }}
- {{#invoke:citation/CS1|citation
|CitationClass=citation }}
- {{#invoke:citation/CS1|citation
|CitationClass=citation }}
- {{#invoke:citation/CS1|citation
|CitationClass=citation }}
- {{#invoke:citation/CS1|citation
|CitationClass=citation }}
- Ed Pegg, Jr., "The Möbius function (and squarefree numbers)", MAA Online Math Games (2003)