Hubbry Logo
search
logo
Möbius function avatar
Möbius function
Möbius function
current hub
M

Möbius function

logo
Community Hub0 Subscribers

Wikipedia

Möbius function
View on Wikipedia
from Wikipedia

The Möbius function 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 Gian-Carlo Rota in the 1960s, generalizations of the Möbius function were introduced into combinatorics, and are similarly denoted .

Key Information

Definition

[edit]

The Möbius function is defined by[3]

The Möbius function can alternatively be represented as

where is the Kronecker delta, is the Liouville function, is the number of distinct prime divisors of , and is the number of prime factors of , counted with multiplicity.

Another characterization by Carl Friedrich Gauss is the sum of all primitive roots.[4]

Values

[edit]

The values of for the first 50 positive numbers are

1 2 3 4 5 6 7 8 9 10
1 −1 −1 0 −1 1 −1 0 0 1
11 12 13 14 15 16 17 18 19 20
−1 0 −1 1 1 0 −1 0 −1 0
21 22 23 24 25 26 27 28 29 30
1 1 −1 0 0 1 0 0 −1 −1
31 32 33 34 35 36 37 38 39 40
−1 0 1 1 1 0 −1 1 1 0
41 42 43 44 45 46 47 48 49 50
−1 −1 −1 0 0 1 −1 0 0 0

The first 50 values of the function are plotted below:

The 50 first values of '"`UNIQ--postMath-00000019-QINU`"'
The 50 first values of

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 is a complex number with real part larger than 1 we have

This may be seen from its Euler product

Also:

  • where is Euler's constant.

The Lambert series for the Möbius function is

which converges for . For prime , we also have

Algebraic number theory

[edit]

Gauss[1] proved that for a prime number the sum of its primitive roots is congruent to .

If denotes the finite field of order (where is necessarily a prime power), then the number of monic irreducible polynomials of degree over is given by[5]

The Möbius function is used in the Möbius inversion formula.

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 . Under second quantization, multiparticle excitations are considered; these are given by for any natural number . 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 that distinguishes fermions and bosons is then none other than the Möbius function .

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.[6]

Properties

[edit]

The Möbius function is multiplicative (i.e., whenever and 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 (including itself and 1) is zero except when :

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 in combinatorics are connected with the use of the Pólya enumeration theorem in combinatorial groups and combinatorial enumerations.

There is a formula[7] for calculating the Möbius function without directly knowing the factorization of its argument:

i.e. is the sum of the primitive -th 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.[8][9] Similar identities hold for the Mertens function.

Proof of the formula for the sum of over divisors

[edit]

The formula

can be written using Dirichlet convolution as: where is the identity under the convolution.

One way of proving this formula is by noting that the Dirichlet convolution of two multiplicative functions is again multiplicative. Thus it suffices to prove the formula for powers of primes. Indeed, for any prime and for any

,

while for

.

Other proofs

[edit]

Another way of proving this formula is by using the identity

The formula above is then a consequence of the fact that the th roots of unity sum to 0, since each th root of unity is a primitive th root of unity for exactly one divisor of .

However it is also possible to prove this identity from first principles. First note that it is trivially true when . Suppose then that . Then there is a bijection between the factors of for which and the subsets of the set of all prime factors of . 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 of a non-empty finite set . First, if , there is exactly one odd-cardinality subset of , namely itself, and exactly one even-cardinality subset, namely . Next, if , then divide the subsets of into two subclasses depending on whether they contain or not some fixed element in . There is an obvious bijection between these two subclasses, pairing those subsets that have the same complement relative to the subset . Also, one of these two subclasses consists of all the subsets of the set , 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 -containing subsets of . 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.[10]

sections

[edit]

if and only if 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 is prime, then , but the converse is not true. The first non prime for which is . 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 and the Riemann hypothesis.

From the formula

it follows that the Mertens function is given by

where is the Farey sequence of order .

This formula is used in the proof of the Franel–Landau theorem.[11]

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[12] defined a generalised Möbius function to be the -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 . The definition may be extended to complex by reading the binomial as a polynomial in .[13]

Implementations

[edit]

See also

[edit]

Notes

[edit]

Sources

[edit]
[edit]

Grokipedia

Möbius function

View on Grokipedia
from Grokipedia
The Möbius function, denoted μ(n)\mu(n), is a fundamental multiplicative function in number theory defined on the positive integers nn, where μ(n)=0\mu(n) = 0 if nn has a repeated prime factor, μ(n)=1\mu(n) = 1 if n=1n = 1 or nn is a square-free positive integer with an even number of distinct prime factors, and μ(n)=−1\mu(n) = -1 if nn is a square-free positive integer with an odd number of distinct prime factors.[1][2] Introduced by the German mathematician August Ferdinand Möbius in his 1832 paper on properties of power sums, it encodes information about the square-free nature of integers and plays a central role in analytic and combinatorial number theory.[3][1] One of the defining properties of the Möbius function is its multiplicativity: for coprime positive integers mm and nn, μ(mn)=μ(m)μ(n)\mu(mn) = \mu(m) \mu(n).[2] Another key property is the summatory relation ∑d∣nμ(d)=1\sum_{d \mid n} \mu(d) = 1 if n=1n = 1 and 00 otherwise, which expresses the function's orthogonality to the constant function 1 over the divisors of nn.[1][2] This leads to its Dirichlet series representation ∑n=1∞μ(n)ns=1ζ(s)\sum_{n=1}^\infty \frac{\mu(n)}{n^s} = \frac{1}{\zeta(s)} for Re⁡(s)>1\operatorname{Re}(s) > 1, where ζ(s)\zeta(s) is the Riemann zeta function, highlighting its reciprocal relationship with the zeta function and its importance in the study of prime distributions.[1] The Möbius function is most notably applied through the Möbius inversion formula, a cornerstone of number theory that provides a way to recover an arithmetic function f(n)f(n) from its summatory form F(n)=∑d∣nf(d)F(n) = \sum_{d \mid n} f(d) via f(n)=∑d∣nμ(d)F(n/d)f(n) = \sum_{d \mid n} \mu(d) F(n/d).[2][4] This inversion generalizes the principle of inclusion-exclusion and finds applications in counting square-free integers, evaluating sums over divisors, and proving results like the Euler totient function's properties.[2] In analytic number theory, the partial sums of μ(n)\mu(n), known as the Mertens function M(x)=∑n≤xμ(n)M(x) = \sum_{n \leq x} \mu(n), are connected to the Riemann Hypothesis, as their growth rate influences estimates for the zeta function's zeros.[1]

Definition

Mathematical Definition

The Möbius function, denoted μ(n)\mu(n), is an arithmetic function defined on the positive integers nn. A positive integer nn is said to be square-free if it is not divisible by any perfect square greater than 1, meaning in its prime factorization, no prime appears with exponent greater than 1. The function μ(n)\mu(n) takes the value 1 if nn is square-free and has an even number of distinct prime factors, -1 if nn is square-free and has an odd number of distinct prime factors, and 0 otherwise.[1] The number of distinct prime factors of nn is denoted by the prime omega function ω(n)\omega(n). More explicitly, if the prime factorization of nn is n=p1k1p2k2⋯prkrn = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r} where the pip_i are distinct primes and each ki≥1k_i \geq 1, then μ(n)=0\mu(n) = 0 if any ki≥2k_i \geq 2, and otherwise μ(n)=(−1)r\mu(n) = (-1)^r, where r=ω(n)r = \omega(n).[1] This definition implies that μ(n)\mu(n) is completely determined by the prime factorization of nn, and μ(1)=1\mu(1) = 1 since 1 has no prime factors.[5] The Möbius function was introduced by August Ferdinand Möbius in his 1832 paper "Über eine besondere Art von Umkehrung der Reihen" (On a special type of series inversion), published in the Journal für die reine und angewandte Mathematik, volume 9, pages 105–123, where it arose as coefficients in the inversion of certain power series expansions.[6][7] Its application in number theory, particularly through connections to divisor sums and Dirichlet convolution, was developed and popularized by mathematicians such as Peter Gustav Lejeune Dirichlet and Richard Dedekind in the mid-19th century.[6]

Relation to Divisors

The Möbius function arises in number theory as a tool for inverting sums over divisors of an integer nn. Specifically, if two arithmetic functions ff and gg satisfy g(n)=∑d∣nf(d)g(n) = \sum_{d \mid n} f(d) for all positive integers nn, then the Möbius inversion formula states that f(n)=∑d∣nμ(d) g(n/d)f(n) = \sum_{d \mid n} \mu(d) \, g(n/d).[4] This formula, introduced by August Ferdinand Möbius in 1832, provides a systematic way to recover ff from gg.[4] In the context of Dirichlet convolution, the relation can be interpreted as follows: the constant function 1(n)=1\mathbf{1}(n) = 1 for all nn convolves with any arithmetic function ff to yield the sum-of-divisors function σ0(f)(n)=∑d∣nf(d)\sigma_0(f)(n) = \sum_{d \mid n} f(d). The Möbius function μ\mu serves as the Dirichlet convolution inverse of 1\mathbf{1}, meaning that μ∗1=ϵ\mu * \mathbf{1} = \epsilon, where ϵ\epsilon is the unit function with ϵ(1)=1\epsilon(1) = 1 and ϵ(n)=0\epsilon(n) = 0 for n>1n > 1. Thus, μ(n)\mu(n) acts as the coefficients that "undo" the summation over divisors.[8] A prominent application of this inversion appears in the recovery of Euler's totient function ϕ(n)\phi(n), which counts the number of positive integers up to nn that are coprime to nn. It is a known identity that ∑d∣nϕ(d)=n\sum_{d \mid n} \phi(d) = n for all n≥1n \geq 1. To derive the inverted form, apply the Möbius inversion formula with g(k)=kg(k) = k and f(k)=ϕ(k)f(k) = \phi(k), yielding ϕ(n)=∑d∣nμ(d) (n/d)\phi(n) = \sum_{d \mid n} \mu(d) \, (n/d). The steps are: start from n=∑d∣nϕ(d)n = \sum_{d \mid n} \phi(d); substitute n/dn/d for the role of gg in the general formula, where the divisors align such that the sum over d∣nd \mid n of μ(d)⋅(n/d)\mu(d) \cdot (n/d) directly inverts the original sum; this holds because the convolution inverse ensures the equality.[9] The Möbius function also connects to the Riemann zeta function through Dirichlet series. For Re⁡(s)>1\operatorname{Re}(s) > 1, the Dirichlet series ∑n=1∞μ(n)/ns\sum_{n=1}^\infty \mu(n) / n^s equals 1/ζ(s)1/\zeta(s), where ζ(s)=∑n=1∞1/ns=∏p(1−p−s)−1\zeta(s) = \sum_{n=1}^\infty 1 / n^s = \prod_p (1 - p^{-s})^{-1} is the zeta function. This follows from expanding the Euler product ∏p(1−p−s)=1/ζ(s)\prod_p (1 - p^{-s}) = 1/\zeta(s) and matching coefficients with the definition of μ(n)\mu(n), which is zero for non-squarefree nn and alternates in sign based on the number of distinct prime factors.[8]

Values and Examples

Tabular Values for Small n

The Möbius function μ(n) takes values in {-1, 0, 1}, determined by the prime factorization of n: it is 1 if n has an even number of distinct prime factors (square-free), -1 if an odd number (square-free), and 0 if n has a repeated prime factor.[10] To illustrate these values concretely, the following table lists μ(n) for n from 1 to 30, along with a brief note on the prime factorization used for computation.[10]
nPrime factorizationμ(n)
1(empty product)1
22-1
33-1
42²0
55-1
62 × 31
77-1
82³0
93²0
102 × 51
1111-1
122² × 30
1313-1
142 × 71
153 × 51
162⁴0
1717-1
182 × 3²0
1919-1
202² × 50
213 × 71
222 × 111
2323-1
242³ × 30
255²0
262 × 131
273³0
282² × 70
2929-1
302 × 3 × 5-1
These values reveal the sign pattern of μ(n), which oscillates between positive and negative for square-free n while inserting zeros for non-square-free cases: for the initial terms, it follows 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, 1, 0, 0, -1, -1.[10] Simple examples include μ(p) = -1 for any prime p (odd number of prime factors), and μ(pq) = 1 for distinct primes p and q (even number).[10]

Patterns in Prime Powers

The Möbius function displays a clear pattern when restricted to prime powers. For any prime $ p $ and positive integer exponent $ k $, $ \mu(p^k) = -1 $ if $ k = 1 $, and $ \mu(p^k) = 0 $ if $ k \geq 2 $.[1] This behavior arises because higher powers introduce repeated prime factors, causing the function to vanish. The following table lists these values for the first five primes:
Prime $ p $$ \mu(p) $$ \mu(p^2) $$ \mu(p^3) $
2-100
3-100
5-100
7-100
11-100
These entries highlight that $ \mu(n) $ is never zero for primes but is zero for all prime powers greater than the first.[10] For products of prime powers, the pattern extends multiplicatively when the factors are coprime. Specifically, if $ n $ and $ m $ are coprime, then $ \mu(nm) = \mu(n) \mu(m) $.[1] For example, $ 30 = 2 \times 3 \times 5 $ is a product of three distinct primes, so $ \mu(30) = \mu(2) \mu(3) \mu(5) = (-1)^3 = -1 $.[10] In general, for square-free $ n $ with $ \omega(n) $ distinct prime factors, $ \mu(n) = (-1)^{\omega(n)} $, while $ \mu(n) = 0 $ for any non-square-free $ n $.[1] A key visual pattern emerges in the distribution: $ \mu(n) \neq 0 $ if and only if $ n $ is square-free, and the natural density of square-free positive integers is $ 6/\pi^2 \approx 0.607927 $.[11] This proportion indicates that non-zero values of $ \mu(n) $ appear for roughly 60.8% of all positive integers, alternating in sign based on the parity of the number of prime factors in their square-free decompositions.[10]

Core Properties

Multiplicativity

The Möbius function μ(n)\mu(n) is a multiplicative arithmetic function, meaning that if gcd⁡(m,n)=1\gcd(m, n) = 1, then μ(mn)=μ(m)μ(n)\mu(mn) = \mu(m) \mu(n).[2] To prove this property, consider the prime factorizations of mm and nn. Since gcd⁡(m,n)=1\gcd(m, n) = 1, they share no common prime factors. Recall that μ(k)=0\mu(k) = 0 if kk has a squared prime factor, μ(k)=1\mu(k) = 1 if k=1k = 1, μ(k)=(−1)r\mu(k) = (-1)^r if kk is square-free with rr distinct prime factors, and μ(k)=−1\mu(k) = -1 if r=1r = 1. If either mm or nn has a squared prime factor, then μ(m)=0\mu(m) = 0 or μ(n)=0\mu(n) = 0, so μ(m)μ(n)=0\mu(m) \mu(n) = 0; moreover, mnmn also has that squared factor, so μ(mn)=0\mu(mn) = 0. If both mm and nn are square-free with rr and ss distinct primes respectively, then mnmn is square-free with r+sr + s distinct primes, yielding μ(mn)=(−1)r+s=(−1)r(−1)s=μ(m)μ(n)\mu(mn) = (-1)^{r+s} = (-1)^r (-1)^s = \mu(m) \mu(n). Thus, multiplicativity holds in all cases.[2] This multiplicativity implies that μ(n)\mu(n) is not completely multiplicative, as the property fails when gcd⁡(m,n)>1\gcd(m, n) > 1. For example, take m=n=pm = n = p for a prime pp: μ(p2)=0\mu(p^2) = 0, but μ(p)μ(p)=(−1)⋅(−1)=1\mu(p) \mu(p) = (-1) \cdot (-1) = 1.[2] A key consequence of multiplicativity is the Euler product representation of the associated Dirichlet series. For Re⁡(s)>1\operatorname{Re}(s) > 1,
∑n=1∞μ(n)ns=∏p(1−1ps)=1ζ(s), \sum_{n=1}^\infty \frac{\mu(n)}{n^s} = \prod_p \left(1 - \frac{1}{p^s}\right) = \frac{1}{\zeta(s)},
where the product is over all primes pp and ζ(s)\zeta(s) is the Riemann zeta function. As s→1+s \to 1^+, the right side approaches 0, reflecting the divergence of ζ(s)\zeta(s) to infinity due to the harmonic series of primes.[8]

Inversion Formula

The Möbius inversion formula provides a method to recover an arithmetic function ff from its divisor sum gg, where g(n)=∑d∣nf(d)g(n) = \sum_{d \mid n} f(d) for all positive integers nn. In this case, f(n)=∑d∣nμ(d) g(n/d)f(n) = \sum_{d \mid n} \mu(d) \, g(n/d). This relation holds for any arithmetic functions ff and gg, and it is a cornerstone of analytic number theory for inverting sums over divisors.[12] The proof relies on the multiplicativity of the Möbius function μ\mu, which allows the relation to be established first for prime powers and then extended generally. Consider the case where n=pkn = p^k for a prime pp and integer k≥0k \geq 0. Here, g(pk)=∑j=0kf(pj)g(p^k) = \sum_{j=0}^k f(p^j), and the inversion gives f(pk)=∑j=0kμ(pj) g(pk−j)f(p^k) = \sum_{j=0}^k \mu(p^j) \, g(p^{k-j}). Since μ(1)=1\mu(1) = 1, μ(p)=−1\mu(p) = -1, and μ(pj)=0\mu(p^j) = 0 for j≥2j \geq 2, this simplifies to f(pk)=g(pk)−g(pk−1)f(p^k) = g(p^k) - g(p^{k-1}) (with g(p−1)=0g(p^{-1}) = 0 for the base case k=0k=0). Substituting the expression for gg yields g(pk)−g(pk−1)=f(pk)g(p^k) - g(p^{k-1}) = f(p^k), confirming the formula holds for prime powers.[13] For the general case, substitute the definition of gg into the proposed inversion:
∑d∣nμ(d) g(n/d)=∑d∣nμ(d)∑e∣(n/d)f(e)=∑m∣nf(m)∑d∣(n/m)μ(d), \sum_{d \mid n} \mu(d) \, g(n/d) = \sum_{d \mid n} \mu(d) \sum_{e \mid (n/d)} f(e) = \sum_{m \mid n} f(m) \sum_{d \mid (n/m)} \mu(d),
where the inner sum is over divisors dd of n/mn/m. The multiplicativity of μ\mu implies ∑d∣ℓμ(d)=0\sum_{d \mid \ell} \mu(d) = 0 if ℓ>1\ell > 1 and equals 1 if ℓ=1\ell = 1. Thus, the double sum equals f(n)f(n) when n/m=1n/m = 1 (i.e., m=nm = n) and vanishes otherwise, proving the formula.[12] A key application derives the property ∑d∣nμ(d)=0\sum_{d \mid n} \mu(d) = 0 for n>1n > 1. Setting ff to be the Dirichlet identity function ϵ(n)\epsilon(n) (where ϵ(1)=1\epsilon(1) = 1 and ϵ(n)=0\epsilon(n) = 0 for n>1n > 1), the divisor sum gives g(n)=1g(n) = 1 for all nn. Inversion then yields ϵ(n)=∑d∣nμ(d)⋅1\epsilon(n) = \sum_{d \mid n} \mu(d) \cdot 1, so the sum is 1 if n=1n=1 and 0 otherwise.[14] Another important application is the formula for Euler's totient function ϕ(n)\phi(n), which counts the integers up to nn coprime to nn. It satisfies ∑d∣nϕ(d)=n\sum_{d \mid n} \phi(d) = n, so by inversion, ϕ(n)=∑d∣nμ(d) (n/d)\phi(n) = \sum_{d \mid n} \mu(d) \, (n/d), or equivalently ϕ(n)=n∏p∣n(1−1/p)\phi(n) = n \prod_{p \mid n} (1 - 1/p).[12] The Möbius inversion formula generalizes the Leibniz rule for finite differences.[14]

Sum Over Divisors

The sum of the Möbius function over the divisors of a positive integer nn is given by the identity
∑d∣nμ(d)=[n=1], \sum_{d \mid n} \mu(d) = [n=1],
where [n=1][n=1] is the Iverson bracket, which evaluates to 1 if n=1n=1 and 0 otherwise.[1] This is equivalently expressed as ∑d∣nμ(d)=ϵ(n)\sum_{d \mid n} \mu(d) = \epsilon(n), with ϵ\epsilon denoting the Dirichlet unit function, which is 1 at n=1n=1 and 0 elsewhere.[15] A primary proof of this identity applies the Möbius inversion formula to the Dirichlet unit function ϵ\epsilon. The summatory function associated with ϵ\epsilon under Dirichlet convolution is g(n)=∑d∣nϵ(d)=1g(n) = \sum_{d \mid n} \epsilon(d) = 1 for every n≥1n \geq 1, since only the divisor d=1d=1 contributes a nonzero value. The inversion formula then yields ϵ(n)=∑d∣nμ(d) g(n/d)\epsilon(n) = \sum_{d \mid n} \mu(d) \, g(n/d). Substituting g(n/d)=1g(n/d) = 1 simplifies this to ∑d∣nμ(d)=ϵ(n)\sum_{d \mid n} \mu(d) = \epsilon(n).[13] An alternative proof exploits the connection to inclusion-exclusion over the square-free divisors of nn. The terms μ(d)\mu(d) vanish unless dd is square-free, so the sum restricts to the square-free divisors, which are precisely the products of distinct subsets of the prime factors of nn. If ω(n)=k>0\omega(n) = k > 0 is the number of distinct prime factors of nn, the sum becomes ∑r=0k(kr)(−1)r=(1−1)k=0\sum_{r=0}^{k} \binom{k}{r} (-1)^r = (1-1)^k = 0. For n=1n=1, where k=0k=0, the sum is simply μ(1)=1\mu(1) = 1. This cancellation reflects the inclusion-exclusion principle applied to counting with signed contributions from prime factors.[15] Another proof uses the generating function for the Möbius function, whose Dirichlet series is ∑n=1∞μ(n)n−s=1/[ζ(s)](/page/Riemannzetafunction)\sum_{n=1}^\infty \mu(n) n^{-s} = 1/[\zeta(s)](/page/Riemann_zeta_function) for ℜ(s)>1\Re(s) > 1, where ζ(s)\zeta(s) is the Riemann zeta function. The convolution property of Dirichlet series implies that the series for ϵ\epsilon is the constant 1, and since ζ(s)⋅(1/ζ(s))=1\zeta(s) \cdot (1/\zeta(s)) = 1, this corresponds to the convolution u∗μ=ϵu * \mu = \epsilon with u(n)=1u(n) = 1. Locally, for a prime power pap^a with a≥1a \geq 1, the sum ∑j=0aμ(pj)=1−1+0+⋯+0=0\sum_{j=0}^a \mu(p^j) = 1 - 1 + 0 + \cdots + 0 = 0; multiplicativity extends this to 0 for any n>1n > 1.[1] An inductive proof on ω(n)\omega(n) provides further verification. The base case ω(n)=0\omega(n) = 0 (so n=1n=1) gives ∑d∣1μ(d)=μ(1)=1\sum_{d \mid 1} \mu(d) = \mu(1) = 1. Now assume the identity holds for all positive integers with fewer than kk distinct prime factors, where k≥1k \geq 1. For nn with ω(n)=k\omega(n) = k, select a prime pp dividing nn and let v=vp(n)≥1v = v_p(n) \geq 1, m=n/pvm = n / p^v, so ω(m)=k−1\omega(m) = k-1. The divisors of nn are d=d′pjd = d' p^j with d′∣md' \mid m and 0≤j≤v0 \leq j \leq v, yielding
∑d∣nμ(d)=(∑d′∣mμ(d′))(∑j=0vμ(pj)). \sum_{d \mid n} \mu(d) = \left( \sum_{d' \mid m} \mu(d') \right) \left( \sum_{j=0}^v \mu(p^j) \right).
The inner sum is 1+(−1)+0+⋯+0=01 + (-1) + 0 + \cdots + 0 = 0, so the product is 0; the induction hypothesis confirms the first factor is [m=1][m=1], but the zero factor suffices.[16] This identity establishes that μ\mu serves as the Dirichlet convolution inverse to the constant function u(n)=1u(n) = 1 within the ring of arithmetic functions, as u∗μ=ϵu * \mu = \epsilon, the multiplicative identity of the ring.[13]

Analytic Properties

Average Order

The average order of the Möbius function μ(n)\mu(n) is characterized by the asymptotic behavior of its partial sums, known as the Mertens function M(x)=∑n≤xμ(n)M(x) = \sum_{n \leq x} \mu(n). Specifically, the normalized sum 1x∑n≤xμ(n)=M(x)x\frac{1}{x} \sum_{n \leq x} \mu(n) = \frac{M(x)}{x} tends to 0 as x→∞x \to \infty. This result is equivalent to the prime number theorem, which asserts that the number of primes up to xx is asymptotically xlog⁡x\frac{x}{\log x}.[17] A proof of this asymptotic follows from the Dirichlet series representation ∑n=1∞μ(n)ns=1ζ(s)\sum_{n=1}^\infty \frac{\mu(n)}{n^s} = \frac{1}{\zeta(s)} for Re⁡(s)>1\operatorname{Re}(s) > 1, where ζ(s)\zeta(s) is the Riemann zeta function. Since ζ(s)\zeta(s) has no zeros in this half-plane and a simple pole at s=1s=1, standard analytic methods such as the Wiener-Ikehara theorem or Perron's formula imply that M(x)=o(x)M(x) = o(x). An explicit unconditional bound is given by Mertens' theorem, which states that M(x)=O(xexp⁡(−clog⁡x))M(x) = O\left(x \exp\left(-c \sqrt{\log x}\right)\right) for some constant c>0c > 0. This was originally established in the late 19th century and refined over time. The equivalence to the prime number theorem and the initial rigorous proof of M(x)=o(x)M(x) = o(x) were established by Hans von Mangoldt in 1895, building on Riemann's ideas about the zeta function. Under the Riemann hypothesis, the error term improves significantly to M(x)=O(xlog⁡x)M(x) = O(\sqrt{x} \log x). As of 2024, the best explicit unconditional bounds include ∣M(x)∣<0.4188xexp⁡(−0.1148log⁡x)|M(x)| < 0.4188 x \exp(-0.1148 \sqrt{\log x}) for x≥exp⁡(363.11)x \geq \exp(363.11), obtained via comparisons with sums over zeta zeros. More refined subexponential bounds, such as ∣M(x)∣<5.61432xexp⁡(−0.00319(log⁡x)3/5(log⁡log⁡x)−1/5)|M(x)| < 5.61432 x \exp(-0.00319 (\log x)^{3/5} (\log \log x)^{-1/5}) for large xx, have also been derived.[18]

Distribution of μ(n)

The Möbius function μ(n)\mu(n) takes the value 0 precisely when nn is not square-free, and the asymptotic density of square-free positive integers up to xx is 6π2\frac{6}{\pi^2}, so the proportion of n≤xn \leq x with μ(n)=0\mu(n) = 0 is 1−6π21 - \frac{6}{\pi^2}.[19] Among the square-free integers, the values μ(n)=1\mu(n) = 1 and μ(n)=−1\mu(n) = -1 occur with equal frequency, each with asymptotic density 3π2\frac{3}{\pi^2}.[19] Since μ(n)2=1\mu(n)^2 = 1 if nn is square-free and 0 otherwise, the second moment satisfies ∑n≤xμ(n)2∼6π2x\sum_{n \leq x} \mu(n)^2 \sim \frac{6}{\pi^2} x.[19] This reflects the density of square-free numbers and provides a quantitative measure of the support of μ(n)\mu(n). Under the Riemann Hypothesis, sums of the Möbius function in short intervals of length h→∞h \to \infty with h=o(N)h = o(N) follow a normal distribution with mean 0 and variance ∼6hπ2\sim \frac{6h}{\pi^2}, indicating pseudorandom behavior.[20] The Chowla conjecture further asserts that correlations of the Möbius function vanish, meaning that for any fixed distinct shifts h1,…,hkh_1, \dots, h_k, the average 1x∑n≤x∏j=1kμ(n+hj)=o(1)\frac{1}{x} \sum_{n \leq x} \prod_{j=1}^k \mu(n + h_j) = o(1) as x→∞x \to \infty.[21] As of 2023, Matomäki and Radziwiłł, in joint work with others, established that the logarithmic average of μ(n)2\mu(n)^2 in short intervals aligns asymptotically with its global density 6π2\frac{6}{\pi^2}, extending uniformity results for bounded multiplicative functions.[22]

Mertens Function

The Mertens function, denoted M(x)M(x), is the summatory function of the Möbius function μ(n)\mu(n), defined for real x≥1x \geq 1 by
M(x)=∑n≤xμ(n). M(x) = \sum_{n \leq x} \mu(n).
[23] This partial sum captures the cumulative effect of the Möbius function's values, which alternate in sign based on the prime factorization of nn. Unconditionally, it is known that M(x)=o(x)M(x) = o(x) as x→∞x \to \infty, a result following from the prime number theorem via partial summation, since ∑n=1∞μ(n)/n=0\sum_{n=1}^\infty \mu(n)/n = 0. Under the Riemann hypothesis (RH), stronger asymptotic bounds hold for M(x)M(x). Specifically, RH implies ∣M(x)∣<x (log⁡x)O(1)|M(x)| < \sqrt{x} \, (\log x)^{O(1)} for large xx, reflecting the function's controlled growth relative to x\sqrt{x}.[24] More precisely, RH is equivalent to M(x)=O(x1/2+ϵ)M(x) = O(x^{1/2 + \epsilon}) for every ϵ>0\epsilon > 0. Odlyzko and Teichmüller developed methods in 1987 using high-precision computations of zeta function zeros to derive explicit bounds on M(x)M(x) consistent with RH, enabling numerical verification of these estimates up to large scales. The Mertens conjecture, proposed in 1897, asserted that ∣M(x)∣<x|M(x)| < \sqrt{x} for all x>1x > 1. This was disproved in 1985 by Odlyzko and te Riele, who demonstrated through analytic arguments involving the zeta function that lim sup⁡x→∞∣M(x)∣/x>1.009\limsup_{x \to \infty} |M(x)| / \sqrt{x} > 1.009 and lim inf⁡x→∞M(x)/x<−1.004\liminf_{x \to \infty} M(x) / \sqrt{x} < -1.004, implying infinitely many counterexamples, though the smallest remains unknown, exceeding 101610^{16} from direct computations, with upper bounds around exp⁡(1029)\exp(10^{29}) as of 2025.[25][26] Weaker variants, such as ∣M(x)∣<cx|M(x)| < c \sqrt{x} for some constant c>1c > 1, remain open. Computations have reached up to x=1016x = 10^{16} (as of 2018), revealing pronounced oscillations that align with expectations under RH but exceed the original Mertens bound in magnitude.[23] These computations leverage the explicit formula linking M(x)M(x) to sums over the nontrivial zeros of the zeta function, providing empirical insights into the hypothesis's implications for the function's behavior.

Applications

In Number-Theoretic Sums

The Möbius function plays a central role in the Dirichlet convolution of arithmetic functions, defined as (f∗g)(n)=∑d∣nf(d)g(n/d)(f * g)(n) = \sum_{d \mid n} f(d) g(n/d). Specifically, the convolution of the Möbius function μ\mu with the constant function 1(n)=11(n) = 1 for all nn yields the Dirichlet unit function ε\varepsilon, where ε(1)=1\varepsilon(1) = 1 and ε(n)=0\varepsilon(n) = 0 for n>1n > 1, satisfying (μ∗1)(n)=∑d∣nμ(d)=ε(n)(\mu * 1)(n) = \sum_{d \mid n} \mu(d) = \varepsilon(n).[27] This property establishes μ\mu as the Dirichlet inverse of the constant function 11, forming the basis for inverting convolutions in number-theoretic sums.[28] This inversion capability enables the recovery of arithmetic functions from their convolutions with 11. For instance, if g(n)=∑d∣nf(d)g(n) = \sum_{d \mid n} f(d), then Möbius inversion gives f(n)=∑d∣nμ(d)g(n/d)f(n) = \sum_{d \mid n} \mu(d) g(n/d). A classic application arises with the Euler totient function φ(n)\varphi(n), which counts the integers up to nn coprime to nn. The identity ∑d∣nφ(d)=n\sum_{d \mid n} \varphi(d) = n follows directly from φ=μ∗id\varphi = \mu * \mathrm{id}, where id(n)=n\mathrm{id}(n) = n is the identity function, allowing the sum to be inverted to express φ(n)\varphi(n) explicitly.[29] In evaluating sums over arithmetic progressions or divisor structures, partial sums involving μ(n)\mu(n) often appear. For example, the partial sum ∑n≤xμ(n)log⁡nn\sum_{n \leq x} \frac{\mu(n) \log n}{n} converges asymptotically to −1-1 as x→∞x \to \infty, reflecting the behavior of the Dirichlet series ∑n=1∞μ(n)log⁡nns=ζ′(s)ζ(s)2\sum_{n=1}^\infty \frac{\mu(n) \log n}{n^s} = \frac{\zeta'(s)}{\zeta(s)^2} near s=1s=1, where the limit yields −1-1.[30] A representative application is counting square-free integers, which are positive integers not divisible by any perfect square other than 11. The indicator function for square-freeness is ∣μ(n)∣|\mu(n)|, since μ(n)≠0\mu(n) \neq 0 if and only if nn is square-free. The number of square-free integers up to xx is thus ∑n≤x∣μ(n)∣∼6π2x\sum_{n \leq x} |\mu(n)| \sim \frac{6}{\pi^2} x, where 6π2=1ζ(2)\frac{6}{\pi^2} = \frac{1}{\zeta(2)} is the natural density of square-free integers derived from the Euler product over primes.[31] In sieve theory, the Möbius function provides weights for inclusion-exclusion principles to estimate the distribution of primes or prime-like sequences. Brun's sieve, introduced by Viggo Brun in 1915, modifies the full inclusion-exclusion via μ\mu by truncating the sum to a finite level, balancing exactness with computational feasibility. This truncation replaces the unrestricted ∑d∣Pμ(d)\sum_{d \mid P} \mu(d) (where PP is a product of small primes) with a weighted sum over restricted divisors, yielding upper and lower bounds for sifted sets, such as twin primes, with error terms controlled by sieve dimensions.[32]

In Algebraic Number Theory

In algebraic number theory, the Möbius function extends naturally to the multiplicative semigroup of nonzero ideals in the ring of integers OK\mathcal{O}_K of a number field KK, where OK\mathcal{O}_K is a Dedekind domain. The ideal Möbius function μ\mu is defined by μ(a)=0\mu(\mathfrak{a}) = 0 if a\mathfrak{a} has a repeated prime ideal factor, μ(a)=(−1)r\mu(\mathfrak{a}) = (-1)^r if a\mathfrak{a} is a product of rr distinct prime ideals, and μ((1))=1\mu((1)) = 1. This definition preserves multiplicativity, and the fundamental property holds: for any nonzero ideal a\mathfrak{a}, ∑d∣aμ(d)=[a=(1)]\sum_{\mathfrak{d} \mid \mathfrak{a}} \mu(\mathfrak{d}) = [ \mathfrak{a} = (1) ], where [⋅][ \cdot ] is the Iverson bracket (1 if true, 0 otherwise). This relation enables Möbius inversion in the poset of ideals ordered by divisibility, analogous to the integer case.[33] The Dedekind zeta function ζK(s)=∑a≠(0)N(a)−s=∏p(1−N(p)−s)−1\zeta_K(s) = \sum_{\mathfrak{a} \neq (0)} N(\mathfrak{a})^{-s} = \prod_{\mathfrak{p}} (1 - N(\mathfrak{p})^{-s})^{-1} (for Re⁡(s)>1\operatorname{Re}(s) > 1, where the sum is over nonzero ideals and the product over prime ideals) has reciprocal 1/ζK(s)=∑aμ(a)N(a)−s1/\zeta_K(s) = \sum_{\mathfrak{a}} \mu(\mathfrak{a}) N(\mathfrak{a})^{-s}, mirroring the Riemann zeta function's Euler product inversion. This generalization plays a crucial role in analytic properties of number fields. Dirichlet LL-functions over Q\mathbb{Q}, defined as L(s,χ)=∑nχ(n)n−s=∏p(1−χ(p)p−s)−1L(s, \chi) = \sum_n \chi(n) n^{-s} = \prod_p (1 - \chi(p) p^{-s})^{-1} for a Dirichlet character χ\chi, satisfy 1/L(s,χ)=∑nμ(n)χ(n)n−s1/L(s, \chi) = \sum_n \mu(n) \chi(n) n^{-s} when χ\chi is principal (reducing to the zeta case) or more generally via the twisted Möbius function μχ\mu \chi. The Artin conjecture asserts that Artin LL-functions associated to irreducible representations of the Galois group Gal(L/K)\mathrm{Gal}(L/K) of a Galois extension L/KL/K coincide with finite products of such Dirichlet LL-functions (or Hecke LL-functions in the number field setting), thereby linking the Möbius inversion to the analytic continuation and functional equations of these LL-functions.[34] A key application arises in the class number formula for quadratic fields K=Q(D)K = \mathbb{Q}(\sqrt{D}). For imaginary quadratic fields (D<0D < 0), the class number h(K)h(K) is given by h(K)=w∣Δ∣2πL(1,χΔ)h(K) = \frac{w \sqrt{|\Delta|}}{2\pi} L(1, \chi_\Delta), where Δ\Delta is the discriminant, ww is the number of roots of unity in KK, and χΔ\chi_\Delta is the Kronecker symbol character; the real quadratic case adjusts the constant accordingly. Here, ζK(s)=ζ(s)L(s,χΔ)\zeta_K(s) = \zeta(s) L(s, \chi_\Delta), so the Euler product for ζK(s)\zeta_K(s) incorporates the prime factorization structure, with μ\mu entering via the reciprocal's Dirichlet series expansion, which aids in residue computations and analytic class number bounds. In ray class groups, the Möbius function appears in Stickelberger's theorem and its generalizations: for the ray class group modulo m\mathfrak{m} in cyclotomic extensions, the Stickelberger annihilator ideal, generated by elements involving Gauss sums τ(χ)=∑a mod mχ(a)ζa\tau(\chi) = \sum_{a \bmod \mathfrak{m}} \chi(a) \zeta^{a}, acts on the group, and degree formulas like [Clm(K):Cl(K)][\mathrm{Cl}_\mathfrak{m}(K) : \mathrm{Cl}(K)] involve Möbius inversion over divisors of the conductor via the ideal Euler totient ϕ(m)=∑d∣mμ(d)N(m/d)\phi(\mathfrak{m}) = \sum_{d \mid \mathfrak{m}} \mu(d) N(\mathfrak{m}/d), adjusted by unit group indices such as [OK×:(1+m)∩OK×][\mathcal{O}_K^\times : (1 + \mathfrak{m}) \cap \mathcal{O}_K^\times].[34][35][36]

In Physics

In quantum field theory, the Möbius function μ(n) finds an interpretation as the fermion number operator (-1)^F, which distinguishes bosonic and fermionic states in supersymmetric theories. This equivalence allows the derivation of the classical Möbius inversion formula from physical principles, such as the Witten index—a topological invariant that counts the difference between bosonic and fermionic ground states—and leads to number-theoretic results like an analogue of the prime number theorem through sums involving μ(n).[37] The function also appears in the algebraic structure underlying multiple zeta values (MZVs), which evaluate Feynman integrals in perturbative quantum field theory. Specifically, μ(n) enters the Möbius transformation used to count irreducible MZVs of given weight and depth, facilitating reductions and relations among these periods that arise in scattering amplitudes and renormalization. For instance, in enumerating basis elements for MZVs up to weight 18, the transformation T(a,b) = ∑_{c|a,b} μ(c) (a/c + b/c)! / ((a/c)! (b/c)!) determines the dimension of irreducible sums, supporting conjectures on their structure in QFT computations.[38] In statistical mechanics, μ(n) arises in probabilistic models for square-free numbers inspired by random surface configurations, where limit theorems for random variables tied to prime factorizations mimic ensemble averages. Additionally, through inclusion-exclusion principles generalized via Möbius inversion, μ(n) counts signed lattice configurations in models like dimers or Ising systems on periodic graphs, correcting for overcounting in partition functions. The primon gas, or Riemann gas, provides a toy model where the bosonic partition function is the Riemann zeta function ζ(s), while the fermionic counterpart involves 1/ζ(s) = ∑ μ(n)/n^s, illustrating supersymmetric balances in energy levels log p for primes p. In string theory, the number-theoretic Möbius function contributes to partition functions via the Riemann gas framework, where μ(n) encodes fermionic contributions inverting the bosonic zeta-function spectrum, linking worldsheet modular invariance to arithmetic structures. As of 2024, analogies from random matrix theory model the statistics of L-function zeros—governed by explicit formulas involving μ(n)—to study quantum chaos in arithmetic systems, such as spectral correlations in chaotic billiards mirroring Möbius randomness.[39][40]

Generalizations

In Incidence Algebras

The Möbius function admits a profound generalization to the setting of partially ordered sets (posets) through the framework of incidence algebras, as formalized by Gian-Carlo Rota in his seminal 1964 paper.[41] For a locally finite poset PP, the incidence algebra I(P)I(P) consists of all functions f:P×P→Rf: P \times P \to \mathbb{R} such that f(x,y)=0f(x,y) = 0 whenever x≰yx \not\leq y, equipped with pointwise addition and a convolution product defined by
(h=f∗g)(x,y)=∑x≤z≤yf(x,z) g(z,y). (h = f * g)(x,y) = \sum_{x \leq z \leq y} f(x,z) \, g(z,y).
This algebra is associative and unital, with the identity element ε\varepsilon given by ε(x,y)=1\varepsilon(x,y) = 1 if x=yx = y and 00 otherwise.[41] Central to this structure is the zeta function ζ∈I(P)\zeta \in I(P), defined by ζ(x,y)=1\zeta(x,y) = 1 if x≤yx \leq y and 00 otherwise, which encodes the order relations of the poset. The Möbius function μ∈I(P)\mu \in I(P) is the unique two-sided inverse of ζ\zeta under convolution, satisfying ζ∗μ=μ∗ζ=ε\zeta * \mu = \mu * \zeta = \varepsilon. It can be computed recursively: μ(x,x)=1\mu(x,x) = 1 for all x∈Px \in P, and for x<yx < y,
μ(x,y)=−∑x≤z<yμ(x,z). \mu(x,y) = -\sum_{x \leq z < y} \mu(x,z).
Equivalently, μ(x,y)\mu(x,y) admits an explicit expression as an alternating sum over chains in the poset: if x≰yx \not\leq y, then μ(x,y)=0\mu(x,y) = 0; otherwise,
μ(x,y)=∑(−1)k, \mu(x,y) = \sum (-1)^k,
where the sum runs over all chains x=z0<z1<⋯<zk=yx = z_0 < z_1 < \cdots < z_k = y in PP, counting each chain of length kk (i.e., with kk strict inequalities) with sign (−1)k(-1)^k. This signed enumeration captures the inclusion-exclusion principle inherent in Möbius inversion for posets.[41] In the specific case of the poset of positive divisors of a fixed integer nn under divisibility (the divisor lattice), the generalized Möbius function recovers the classical number-theoretic version: μ(1,d)=μ(d)\mu(1,d) = \mu(d) for each divisor dd of nn, where μ\mu denotes the arithmetic Möbius function.[42] More broadly, Rota's framework enables Möbius inversion in arbitrary posets: if functions f,g:P→Rf, g: P \to \mathbb{R} satisfy g(x)=∑y≤xf(y)g(x) = \sum_{y \leq x} f(y) for all x∈Px \in P, then f(x)=∑y≤xμ(y,x) g(y)f(x) = \sum_{y \leq x} \mu(y,x) \, g(y). This inversion tool has found extensive applications in combinatorics, particularly for counting chains and deriving inclusion-exclusion identities in structures like lattices and simplicial complexes, underpinning much of modern enumerative combinatorics.[41]

Related Functions

The Liouville function λ(n)\lambda(n) is defined as λ(n)=(−1)Ω(n)\lambda(n) = (-1)^{\Omega(n)}, where Ω(n)\Omega(n) counts the total number of prime factors of nn with multiplicity.[43] It relates to the Möbius function via the identity λ(n)=∑d2∣nμ(n/d2)\lambda(n) = \sum_{d^2 \mid n} \mu(n/d^2).[44] This connection arises from the Dirichlet series representation ∑n=1∞λ(n)n−s=ζ(2s)/ζ(s)\sum_{n=1}^\infty \lambda(n) n^{-s} = \zeta(2s)/\zeta(s), reflecting how λ\lambda modifies the sign based on total prime multiplicity while incorporating square factors through the Möbius term.[44] In 1963, Constantin P. Popovici introduced a generalization μk(n)\mu_k(n) as the kk-fold Dirichlet convolution of the Möbius function with itself, so that μ1(n)=μ(n)\mu_1(n) = \mu(n) and higher kk correspond to repeated convolutions.[45] This construction preserves multiplicativity and generalizes inversion formulas for sums over multiple convolutions, with applications to higher-order zeta function identities like ∑nμk(n)n−s=1ζ(s)k\sum_n \mu_k(n) n^{-s} = \frac{1}{\zeta(s)^k}.[45] The Jordan totient function Jk(n)J_k(n) generalizes Euler's totient and is given by Jk(n)=∑d∣nμ(d)(n/d)kJ_k(n) = \sum_{d \mid n} \mu(d) (n/d)^k, counting the number of kk-tuples modulo nn with no common divisor greater than 1. For k=1k=1, it reduces to ϕ(n)\phi(n), and the formula follows from Möbius inversion applied to the identity nk=∑d∣nJk(d)n^k = \sum_{d \mid n} J_k(d). This sum modifies the Möbius contribution by weighting with powers, emphasizing higher-dimensional coprimality. Additionally, μ(n)2\mu(n)^2 serves as the characteristic function of square-free positive integers, taking value 1 if nn is square-free and 0 otherwise, since μ(n)≠0\mu(n) \neq 0 precisely when nn has no squared prime factors.[46] Unlike the classical μ(n)\mu(n), which includes sign based on the number of distinct primes, μ(n)2\mu(n)^2 focuses solely on the support (square-freeness) without sign alternation. These variants alter the Möbius function's sign or domain to suit specific arithmetic properties, such as multiplicity counting or higher convolutions.

Computation

Algorithms

To compute the Möbius function μ(n) for a single integer n, the standard approach begins with the prime factorization of n. Once the prime factors are obtained, μ(n) is determined by the definition: μ(n) = 0 if n has a repeated prime factor (i.e., is not square-free), μ(n) = 1 if n is a square-free positive integer with an even number of distinct prime factors, and μ(n) = -1 if it has an odd number.[2] For small to moderate n, trial division suffices for factorization: divide n successively by all integers from 2 up to √n, tracking the primes and their multiplicities. This method has time complexity O(√n) in the worst case but is practical for n up to around 10^12 on standard hardware.[2] For larger n, more advanced factorization algorithms like Pollard's rho method are employed, which finds a non-trivial factor in expected time O(√p) where p is the smallest prime factor of n, making it efficient for numbers with factors up to 10^20 or so.[47] For batch computation of μ(n) for all n ≤ x, sieve methods based on variants of the Sieve of Eratosthenes are used, achieving near-optimal efficiency. A basic implementation runs in O(x log log x) time by initializing an array of size x, marking multiples of each prime to identify square factors and count distinct primes per number. The linear sieve improves this to O(x) time by ensuring each composite number is visited only once, using the smallest prime factor (SPF) array. The algorithm proceeds as follows: generate primes up to x via a linear pass, computing the SPF for each integer; then, for each n, factorize using the SPF chain to check square-freeness and count distinct primes, setting μ(n) accordingly (e.g., μ(p) = -1 for primes p, μ(1) = 1, and 0 for non-square-free n). This also enables simultaneous computation of related functions like Euler's totient via Möbius inversion.[48] For very large x (e.g., up to 10^16), segmented sieves process the range in blocks of size fitting available memory, precomputing small primes up to √x and sieving each segment independently. This adapts the linear sieve to handle massive scales, with overall time complexity still O(x log log x) but practical space usage around 50 GB for x = 10^16, as demonstrated in computations of the Mertens function (the partial sum of μ(n)). Such methods represent the state-of-the-art for batch evaluation, with the linear sieve variant providing the optimal asymptotic complexity for dense computation up to x.[48]

Software Implementations

The Möbius function μ(n)\mu(n) is implemented in several mathematical software systems, leveraging efficient factorization or sieving methods to compute its value based on the prime factors of nn. These implementations facilitate computations in number theory applications, such as inclusion-exclusion principles or Dirichlet series evaluations.[49] In SageMath, the function mobius(n) computes μ(n)\mu(n) for a positive integer nn by first obtaining the prime factorization of nn using Sage's built-in integer factorization routines, then applying the definition: μ(n)=0\mu(n) = 0 if nn has a squared prime factor, μ(1)=1\mu(1) = 1, and μ(n)=(−1)k\mu(n) = (-1)^k otherwise, where kk is the number of distinct prime factors. This approach integrates seamlessly with Sage's broader arithmetic capabilities, allowing for vectorized computations via mobius_range(start, stop, step). For example: 
sage: mobius(30)
-1
sage: mobius_range(1, 10)
[1, -1, -1, 0, -1, 1, -1, 0, 0, 1]
The implementation is documented in the SageMath reference manual.[49] PARI/GP provides the moebius(x) function to evaluate μ(∣x∣)\mu(|x|) for nonzero integer xx, relying on its highly optimized factoring engine, which employs multiple algorithms including the elliptic curve method (ECM) for efficient handling of large composites. This makes it particularly suitable for computing μ(n)\mu(n) for large nn, where factorization speed is critical. ECM in PARI/GP is activated for numbers beyond small trial division limits, contributing to subexponential performance in practice. An example usage in GP: 
gp> moebius(30)
-1
gp> moebius(1000000007)  \\ a large prime
-1
The function is part of PARI/GP's arithmetic functions module, with ECM details outlined in the system's factorization documentation.[50] In Python's SymPy library, the Möbius function is accessible via sympy.functions.combinatorial.numbers.mobius(n) for single values, computed through prime factorization similar to other systems; since version 1.13, the older sympy.ntheory.mobius(n) is deprecated in favor of this combinatorial interface. For computing μ(n)\mu(n) over vectors or ranges, SymPy uses the sieve.mobiusrange(a, b) method, which employs a sieve-based approach akin to the Eratosthenes sieve to generate values efficiently up to a limit. Example: 
from sympy import mobius, [sieve](/page/Sieve)
print(mobius(30))  # -1
print(list([sieve](/page/Sieve).mobiusrange(1, 10)))  # [1, -1, -1, 0, -1, 1, -1, 0, 0, 1]
This sieving capability is ideal for batch computations in analytic number theory tasks. The implementation is detailed in SymPy's number theory and combinatorial modules documentation.[51][52][53] Mathematica implements the Möbius function as MoebiusMu[n], which returns μ(n)\mu(n) for positive integer nn and supports symbolic manipulation alongside numerical evaluation. It uses internal factorization optimized for both small and large inputs, integrating with Mathematica's broader number theory toolkit. For instance: 
MoebiusMu[30]
(* -1 *)
Table[MoebiusMu[n], {n, 1, 10}]
(* {1, -1, -1, 0, -1, 1, -1, 0, 0, 1} *)
This function is part of Mathematica's core integer functions and is suitable for both standalone computations and within larger symbolic expressions.[54] Performance comparisons across these systems highlight differences in efficiency, particularly for large nn. Benchmarks indicate that PARI/GP generally outperforms Mathematica and SymPy for factoring large integers, a key step in single μ(n)\mu(n) computations, due to its specialized optimizations like ECM for semiprimes. SymPy's sieving excels for range-based tasks up to moderate limits like 10710^7. Basic trial division or Pollard rho algorithms underpin smaller cases across all tools.[55]

References

  1. Möbius Function -- from Wolfram MathWorld
  2. https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_(Raji
  3. The Early (and Peculiar) History of the Möbius Function - jstor
  4. Möbius Inversion Formula -- from Wolfram MathWorld
  5. Möbius function - PlanetMath
  6. https://digitalcommons.ursinus.edu/triumphs_number/12
  7. [PDF] DIRICHLET SERIES The Riemann zeta-function ζ(s ... - Keith Conrad
  8. DLMF: §27.5 Inversion Formulas ‣ Multiplicative Number Theory ...
  9. A008683 - OEIS
  10. Squarefree numbers - OeisWiki
  11. [PDF] Mobius Inversion Formula, Zeta Functions, Lecture 14 Notes
  12. [PDF] Möbius Inversion Formula. Multiplicative Functions - UC Berkeley math
  13. [PDF] Möbius Inversion Formula and Applications to Cyclotomic Polynomials
  14. [PDF] Introduction to analytic number theory
  15. [PDF] an introduction - theory of numbers
  16. [2302.12218] An Elementary Proof of the Prime Number Theorem ...
  17. New explicit bounds for Mertens function and the reciprocal ... - arXiv
  18. A simple proof that the square-free numbers have density 6/(pi^2)
  19. [PDF] the m¨obius function in short intervals
  20. The autocorrelation of the Möbius function and Chowla's conjecture ...
  21. Higher uniformity of bounded multiplicative functions in short ...
  22. Computations of the Mertens Function and Improved Bounds ... - arXiv
  23. growth of the Mertens function and the Riemann Hypothesis - arXiv
  24. [PDF] Disproof of the Mertens conjecture.
  25. Dirichlet convolution and the Möbius inversion formula
  26. Dirichlet convolution - OeisWiki
  27. Totient Function -- from Wolfram MathWorld
  28. Prove that $\sum_{n=1}^\infty \mu(n) \frac{\log n}{n} =1
  29. Squarefree -- from Wolfram MathWorld
  30. Chapter 13 Brun's combinatorial sieve
  31. Möbius formulas for densities of sets of prime ideals - arXiv
  32. [PDF] Contents 10 Analytic Number Theory - Evan Dummit
  33. Gauss Sums, Stickelberger's Theorem, and the Gras Conjecture for ...
  34. Supersymmetry and the Möbius inversion function
  35. [PDF] The multiple zeta value data mine - Open Research Online
  36. B.L. Julia - Statistical Theory of Numbers
  37. Quantum Chaos, Random Matrix Theory, and the Riemann ζ-function
  38. [PDF] On the foundations of combinatorial theory I. Theory of M&#x00F6
  39. [PDF] Lecture 10 1 Review of incidence algebras - Cornell Mathematics
  40. [PDF] The distribution of the summatory function of the Möbius ... - arXiv
  41. VALUE PATTERNS OF MULTIPLICATIVE FUNCTIONS AND ...
  42. [PDF] arXiv:1509.08243v2 [math.NT] 20 Oct 2015
  43. [PDF] Pollard's Rho Method - UMD MATH
  44. Linear Sieve - Algorithms for Competitive Programming
  45. Miscellaneous arithmetic functions - Standard Commutative Rings
  46. Arithmetic functions and the factoring engine - PARI/GP
  47. Number Theory - SymPy 1.14.0 documentation
  48. Combinatorial - SymPy 1.14.0 documentation
  49. Python sympy | sieve.mobiusrange() method - GeeksforGeeks
  50. MoebiusMu - Wolfram Language Documentation
  51. Integer factorization software: PARI/GP, Mathematica, SymPy
User Avatar
No comments yet.