Möbius function
Named after  August Ferdinand Möbius 

Publication year  1832 
Author of publication  August Ferdinand Möbius 
No. of known terms  infinite 
First terms  1, −1, −1, 0, −1, 1, −1, 0, 0, 1 
OEIS index 

The Möbius function μ(n) is a multiplicative function in number theory introduced by the German mathematician August Ferdinand Möbius (also transliterated Moebius) in 1832.^{[i]}^{[ii]}^{[2]} It is ubiquitous in elementary and analytic number theory and most often appears as part of its namesake the Möbius inversion formula. Following work of GianCarlo Rota in the 1960s, generalizations of the Möbius function were introduced into combinatorics, and are similarly denoted μ(x).
Definition[edit]
For any positive integer n, define μ(n) as the sum of the primitive nth 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 squarefree positive integer with an even number of prime factors.
 μ(n) = −1 if n is a squarefree positive integer with an odd number of prime factors.
 μ(n) = if 0n has a squared prime factor.
The Möbius function can alternatively be represented as
where δ is the Kronecker delta, λ(n) is the Liouville function, ω(n) is the number of distinct prime divisors of n, and Ω(n) is the number of prime factors of n, counted with multiplicity.
It can also be defined as the Dirichlet convolution inverse of the constant1 function.
Values[edit]
The values of μ(n) for the first 50 positive numbers 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 
n  31  32  33  34  35  36  37  38  39  40 

μ(n)  −1  0  1  1  1  0  −1  1  1  0 
n  41  42  43  44  45  46  47  48  49  50 

μ(n)  −1  −1  −1  0  0  1  −1  0  0  0 
The first 50 values of the function are plotted below:
Larger values can be checked in:
Applications[edit]
Mathematical series[edit]
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
Also:
 where  Euler's constant.
The Lambert series for the Möbius function is:
which converges for q < 1. For prime α ≥ 2, we also have
Algebraic number theory[edit]
Gauss^{[1]} proved that for a prime number p the sum of its primitive roots is congruent to μ(p − 1) (mod p).
If F_{q} denotes the finite field of order q (where q is necessarily a prime power), then the number N of monic irreducible polynomials of degree n over F_{q} is given by:^{[3]}
Physics[edit]
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's attempted proof of the Riemann hypothesis.^{[4]}
Properties[edit]
The Möbius function is multiplicative (i.e., μ(ab) = μ(a) μ(b)) whenever a and b are coprime.
Proof: Given two coprime numbers , we induct on . If , then . Otherwise, , so
The sum of the Möbius function over all positive divisors of n (including n itself and 1) is zero except when n = 1:
The equality above 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.
Other applications of μ(n) in combinatorics are connected with the use of the Pólya enumeration theorem in combinatorial groups and combinatorial enumerations.
There is a formula^{[5]} for calculating the Möbius function without directly knowing the factorization of its argument:
i.e. μ(n) is the sum of the primitive nth roots of unity. (However, the computational complexity of this definition is at least the same as that of the Euler product definition.)
Other identities satisfied by the Möbius function include
and
 .
The first of these is a classical result while the second was published in 2020.^{[6]}^{[7]} Similar identities hold for the Mertens function.
Proof of the formula for Σ_{dn} μ(d)[edit]
Using
the formula
can be seen as a consequence of the fact that the nth roots of unity sum to 0, since each nth root of unity is a primitive dth root of unity for exactly one divisor d of n.
However it is also possible to prove this identity from first principles. First note that it is trivially true when n = 1. Suppose then that n > 1. Then there is a bijection between the factors d of n for which μ(d) ≠ 0 and the subsets of the set of all prime factors of n. The asserted result follows from the fact that every nonempty finite set has an equal number of odd and evencardinality subsets.
This last fact can be shown easily by induction on the cardinality S of a nonempty finite set S. First, if S = 1, there is exactly one oddcardinality subset of S, namely S itself, and exactly one evencardinality subset, namely ∅. Next, if S > 1, then divide the subsets of S into two subclasses depending on whether they contain or not some fixed element x in S. 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 evencardinality subsets. These subsets in turn correspond bijectively to the even and oddcardinality {x}containing subsets of S. 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.
Average order[edit]
The mean value (in the sense of average orders) of the Möbius function is zero. This statement is, in fact, equivalent to the prime number theorem.^{[8]}
μ(n) sections[edit]
μ(n) = 0 if and only if n is divisible by the square of a prime. 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, ... (sequence A013929 in the OEIS).
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 the 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 the OEIS).
Mertens function[edit]
In number theory another arithmetic function 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 for more information about the connection between M(n) and the Riemann hypothesis.
From the formula
it follows that the Mertens function is given by:
where F_{n} is the Farey sequence of order n.
This formula is used in the proof of the Franel–Landau theorem.^{[9]}
Generalizations[edit]
Incidence algebras[edit]
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[edit]
Constantin Popovici^{[10]} defined a generalised Möbius function μ_{k} = μ ∗ ... ∗ μ to be the kfold 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.^{[11]}
Implementations[edit]
 Mathematica
 Maxima
 geeksforgeeks C++, Python3, Java, C#, PHP, Javascript
 Rosetta Code
 Sage
See also[edit]
Notes[edit]
 ^ 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". (Hardy & Wright 1980, Notes on ch. XVI)
 ^ 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.^{[1]} 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.
Citations[edit]
 ^ ^{a} ^{b} Gauss 1986, Art. 81.
 ^ Möbius 1832, pp. 105–123.
 ^ Jacobson 2009, §4.13.
 ^ Bost & Connes 1995, pp. 411–457.
 ^ Hardy & Wright 1980, (16.6.4), p. 239.
 ^ Apostol 1976.
 ^ Kline 2020.
 ^ Apostol 1976, §3.9.
 ^ Edwards 1974, Ch. 12.2.
 ^ Popovici 1963, pp. 493–499.
 ^ Sándor & Crstici 2004, p. 107.
Sources[edit]
 Apostol, Tom M. (1976), Introduction to analytic number theory, Undergraduate Texts in Mathematics, New York; Heidelberg: SpringerVerlag, ISBN 9780387901633, MR 0434929, Zbl 0335.10001
 Bost, J.B.; Connes, Alain (1995), "Hecke Algebras, Type III factors and phase transitions with spontaneous symmetry breaking in number theory", Selecta Mathematica, New Series, 1 (3): 411–457, doi:10.1007/BF01589495, S2CID 116418599
 Deléglise, Marc; Rivat, Joël (1996), "Computing the summation of the Möbius function", Experimental Mathematics, 5 (4): 291–295, doi:10.1080/10586458.1996.10504594, S2CID 574146
 Edwards, Harold (1974), Riemann's Zeta Function, Mineola, New York: Dover Publications, ISBN 0486417409
 Gauss, Carl Friedrich (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory), H. Maser (German translator) (2nd ed.), New York: Chelsea, ISBN 0828401918
 Gauss, Carl Friedrich (1986), Disquisitiones Arithemeticae, Arthur A. Clarke (English translator) (corrected 2nd ed.), New York: Springer, ISBN 0387962549
 Hardy, G. H.; Wright, E. M. (1980) [First edition published 1938], An Introduction to the Theory of Numbers (5th ed.), Oxford: Oxford University Press, ISBN 9780198531715 – via Internet Archive
 Kline, Jeffery (2020), "Unital Sums of the Möbius and Mertens Functions" (PDF), Journal of Integer Sequences, 23 (8): 1–17
 Jacobson, Nathan (2009) [First published 1985], Basic algebra I (2nd ed.), Dover Publications, ISBN 9780486471891
 Klimov, N. I. (2001) [1994], "Möbius function", Encyclopedia of Mathematics, EMS Press
 Möbius, A. F. (1832), "Über eine besondere Art von Umkehrung der Reihen", Journal für die reine und angewandte Mathematik, 9: 105–123
 Pegg, Ed, Jr (2003), "The Möbius function (and squarefree numbers)", Ed Pegg's Math Games
{{cite web}}
: CS1 maint: multiple names: authors list (link)  Popovici, Constantin P. (1963), "A generalization of the Möbius function", Studii şi Cercetări Matematice, 14: 493–499, MR 0181602
 Sándor, Jozsef; Crstici, Borislav (2004), Handbook of number theory II, Dordrecht: Kluwer Academic, ISBN 1402025467, Zbl 1079.11001
 Sándor, József; Mitrinović, Dragoslav S.; Crstici, Borislav, eds. (2006), Handbook of number theory I, Dordrecht: SpringerVerlag, pp. 187–226, ISBN 1402042159, Zbl 1151.11300