Möbius Function

Why the Möbius function matters

• Inclusion-exclusion at scale. Möbius inversion is inclusion-exclusion for divisor lattices. Counting square-free numbers ≤ n, primes by sieve, integers coprime to a given n, irreducible polynomials over F_q — every such count uses Möbius inversion to convert "≤ d divides" into "exactly d divides".
• Distribution of primes. Selberg's symmetric formula and the Erdős-Selberg elementary proof of the prime number theorem use μ in critical places. The von Mangoldt function Λ(n) — equal to log p when n = p^k, else 0 — satisfies Λ = -μ * log * 1, expressing prime power counts via Möbius inversion.
• Riemann hypothesis equivalences. RH ↔ M(n) = O(n^(1/2+ε)). The partial-sum behaviour of μ is exquisitely sensitive to ζ's zeros, making μ one of the most direct experimental windows on RH.
• Combinatorics on posets. Möbius functions of partially ordered sets generalise μ — in lattice theory, the Möbius function of a finite lattice gives the inversion formula for arbitrary order-preserving counts. Rota's 1964 paper "On the Foundations of Combinatorial Theory" elevated Möbius inversion to a central tool of modern combinatorics.
• Computer science enumeration. Counting necklaces with k beads of c colours uses Möbius inversion: the number of distinct necklaces is (1/k) Σ_(d|k) μ(d) c^(k/d). Counting Lyndon words, primitive sequences, irreducible polynomials over finite fields all follow this pattern.
• Cyclotomic polynomials. The n-th cyclotomic polynomial Φₙ(x) factors as ∏_{d|n} (x^d − 1)^μ(n/d), giving an explicit closed form via Möbius inversion of x^n − 1 = ∏_{d|n} Φ_d(x).
• Cryptography and number-theoretic sums. Sums of multiplicative functions weighted by μ — Mobius randomness sums — appear in proofs of equidistribution, in Vinogradov's theorem on three primes, and in modern sieve theory.

Common misconceptions

• "μ is just a parity function." It is the parity of ω(n) (number of distinct primes) ONLY for square-free n. For non-square-free n, μ is 0 — not ±1. The Liouville function λ(n) = (-1)^Ω(n), counting with multiplicity, is the parity-everywhere companion: λ(p^2) = 1, μ(p^2) = 0. They behave similarly on average but differ pointwise.
• "Mertens conjecture is true." Mertens conjectured |M(n)| ≤ sqrt(n) for n ≥ 1; this would have implied RH. Odlyzko and te Riele disproved it in 1985. The conjecture's failure does not disprove RH — only the strong bound is too tight; a slightly weaker O(n^(1/2+ε)) bound is still equivalent to RH.
• "Irregular = random." μ has structure: it is multiplicative, deterministic, and computable from prime factorisation. The "Möbius randomness heuristic" says correlations of μ with reasonable arithmetic functions are small — but this is a deep conjectural property, not a literal claim that μ is random.
• "Möbius inversion needs a number-theoretic context." Inversion is an identity in any incidence algebra of a locally finite poset. Number theory is one example (divisor lattice); subset lattice gives standard inclusion-exclusion; subgroup lattice gives Burnside-style counts. Rota showed all these are instances of one phenomenon.
• "μ is multiplicative for all a, b." Multiplicativity requires coprime a, b. μ(2 · 4) = μ(8) = 0 ≠ μ(2) · μ(4) = (-1)(0) = 0 (this happens to agree, but try μ(2)·μ(2) = 1 vs μ(4) = 0). Coprimality matters.
• "Computing μ(n) is hard." Given the prime factorisation of n, μ(n) follows immediately: 0 if any exponent ≥ 2, else (-1)^(number of factors). The hard part is factorisation itself — for cryptographic-size n, computing μ(n) is as hard as factoring.

A worked Möbius inversion

Recover Euler's totient from its summatory: it is known that Σ_{d|n} φ(d) = n. Apply Möbius inversion with g(n) = n and f = φ: φ(n) = Σ_{d|n} μ(d) · (n/d). For n = 12: divisors 1, 2, 3, 4, 6, 12 with μ values 1, -1, -1, 0, 1, 0. Hence φ(12) = 12 - 6 - 4 + 0 + 2 + 0 = 4. Check directly: integers in [1,12] coprime to 12 are {1, 5, 7, 11} — count 4. The closed form φ(n) = n · ∏_(p|n) (1 - 1/p) drops out by expanding the product. One identity, two routes; Möbius inversion is the bridge.

Density of square-free integers

Among integers up to x, what fraction are square-free? The Möbius function provides the answer: the count is Σ_{d ≤ sqrt(x)} μ(d) · floor(x/d²) ≈ x · Σ_d μ(d)/d² = x/ζ(2) = 6x/π² ≈ 0.6079 x. So roughly 60.79% of integers are square-free. The proof: each integer is either square-free or has a unique squareful prefactor d², and inclusion-exclusion via μ peels off the squareful contributions. The constant 6/π² recurs in many density problems and is one of the most direct meeting-points of μ, ζ, and elementary counting.