Engineering/Mathematics/Foundations of number theory
Arithmetic Functions and Möbius Inversion
Divisor sums appear everywhere a quantity is counted by degree, order or period. Dirichlet convolution turns them into an algebra, and Möbius inversion turns any such sum inside out — which is how the number of irreducible polynomials of a given degree is counted exactly.
- Core theory
- Number theory
- Counting tool
- ≈14 min read
- Used in finite field theory
01
Executive summary
An arithmetic function is any map from positive integers to a ring, usually ℂ. The useful ones are multiplicative: f(mn) = f(m)f(n) whenever gcd(m,n) = 1. Such a function is completely determined by its values on prime powers, which reduces every question about it to a local one.
The organising operation is Dirichlet convolution. Under it the arithmetic functions with f(1) ≠ 0 form an abelian group, the multiplicative functions form a subgroup, and the Möbius function is the inverse of the constant function 1. Möbius inversion is nothing more than multiplying by that inverse.
Divisor-indexed convolution; the natural product on arithmetic functions.
The unit of the convolution algebra.
∑ over divisors of μ gives ε — the defining property of the Möbius function.
F = f ∗ 1 ⟺ f = F ∗ μ. Any divisor-sum relation can be run backwards.
02
Definitions
Multiplicative and completely multiplicative
f is multiplicative if f(1) = 1 and f(mn) = f(m)f(n) for coprime m,n; it is completely multiplicative if the condition holds for all m,n. Multiplicative functions are determined by their prime-power values via f(n) = ∏pe ∥ n f(pe).
| Function | Definition | Value at pe | Type |
|---|---|---|---|
| ε | 1 if n = 1, else 0 | 0 | completely multiplicative |
| 1 | constant 1 | 1 | completely multiplicative |
| Id | n | pe | completely multiplicative |
| τ = σ0 | number of divisors | e + 1 | multiplicative |
| σ = σ1 | sum of divisors | (pe+1−1)/(p−1) | multiplicative |
| φ | count of units mod n | pe − pe−1 | multiplicative |
| μ | Möbius function | −1 if e = 1, else 0 | multiplicative |
| Λ | von Mangoldt | log p | neither |
Λ is not multiplicative but is the natural weight for prime counting: ∑_{d∣n} Λ(d) = log n.
Dirichlet convolution
The operation is commutative and associative, has identity ε, and f has a convolution inverse exactly when f(1) ≠ 0. Crucially, the convolution of two multiplicative functions is multiplicative — which is how multiplicativity of φ, σ and τ is proved uniformly.
03
The Möbius function and inversion
The defining identity
Proof: for n > 1 with k distinct prime factors, only squarefree divisors contribute, giving ∑j C(k,j)(−1)j = (1−1)k = 0 by the binomial theorem.
Möbius inversion
A multiplicative version of the same statement, useful when the underlying relation is a product rather than a sum:
Immediate example
From ∑d ∣ n φ(d) = n — proved by partitioning {1,…,n} according to gcd with n — inversion gives φ(n) = ∑d ∣ n μ(d)·n/d = n ∏p ∣ n(1 − 1/p), recovering the closed form without any counting argument.
04
Applications
Counting irreducible polynomials over a finite field
Every monic irreducible of degree d over Fq divides Xqk − X exactly when d ∣ k, and that polynomial is squarefree. Comparing degrees gives qk = ∑d ∣ k d·Iq(d), and inversion yields the exact count:
Other standard uses
Necklace and Lyndon word counts
The number of aperiodic cyclic strings of length n over a k-letter alphabet is (1/n)∑d∣n μ(d)kn/d — the same formula, because both count objects of exact period.
Cyclotomic polynomials
Φn(X) = ∏d∣n(Xd−1)μ(n/d), obtained by multiplicative inversion of Xn−1 = ∏d∣nΦd(X).
Squarefree counting
∑n ≤ x |μ(n)| = 6x/π2 + O(√x): about 61% of integers are squarefree.
Inclusion–exclusion sieving
μ is the sign bookkeeping of inclusion–exclusion over prime divisors; every elementary sieve is a truncated Möbius sum.
Coprimality density
The probability that two random integers are coprime is 1/ζ(2) = 6/π2, from ∑ μ(n)/n2.
Order statistics in groups
In a cyclic group of order m, the count of elements of exact order d is φ(d) — an inversion of the divisor-sum count of elements of order dividing d.
05
Dirichlet series: the analytic shadow
Attaching the formal series Df(s) = ∑n ≥ 1 f(n)n−s converts convolution into multiplication: Df∗g = Df·Dg. Multiplicativity becomes an Euler product.
| Function | Dirichlet series | Reading |
|---|---|---|
| 1 | ζ(s) | The Riemann zeta function; Euler product ∏p(1−p−s)−1 |
| μ | 1/ζ(s) | Möbius inversion in analytic form |
| φ | ζ(s−1)/ζ(s) | From φ = Id ∗ μ |
| τ | ζ(s)2 | From τ = 1 ∗ 1 |
| σ | ζ(s)ζ(s−1) | From σ = 1 ∗ Id |
| Λ | −ζ′(s)/ζ(s) | The link between zeros of ζ and prime counting |
The last line is the entry point to analytic prime number theory: error terms in the prime number theorem correspond directly to the zero-free region of ζ.
Why an engineer should care
The identity ∑ μ(n)n−s = 1/ζ(s) is the reason sieve estimates and smooth-number densities are computable at all. Those densities set the parameters — the size of the factor base and the sieving interval — for subexponential factoring and discrete-log algorithms.
06
Computing arithmetic functions
| Task | Method | Cost |
|---|---|---|
| μ, φ, τ, σ for all n ≤ N | linear sieve over smallest prime factor | O(N) time, O(N) space |
| μ(n) or φ(n) at a single large n | requires factoring n | as hard as factoring |
| ∑n ≤ x μ(n) (Mertens function) | Deléglise–Rivat and successors | sublinear, but far from trivial |
| Iq(k) | direct Möbius sum over divisors of k | O(τ(k)) arithmetic operations |
| Convolution f ∗ g up to N | divisor-pair enumeration | O(N log N) |
Single-point evaluation is not cheap
There is an asymmetry worth internalising: computing φ or μ for every integer below a bound is linear time, but computing either at one cryptographically sized argument requires the factorization of that argument. Confusing the two leads to badly wrong performance assumptions.
07
Quick reference and FAQ
| Identity | Meaning |
|---|---|
| 1 ∗ μ = ε | Definition of the Möbius function |
| φ ∗ 1 = Id | ∑d∣n φ(d) = n |
| φ = Id ∗ μ | Closed form for the totient |
| 1 ∗ 1 = τ | Divisor count |
| Id ∗ 1 = σ | Divisor sum |
| Λ ∗ 1 = log | von Mangoldt weighting |
| μ ∗ log = −Λ | Inverted form, used in analytic estimates |
Why is μ(n) = 0 for non-squarefree n?
Is Möbius inversion the same as inclusion–exclusion?
Where does this appear in the rest of the library?
Does the theory work over an arbitrary ring?
09
References and further reading
- V. Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, 2005 — §2.6 and §20.3.
- T. M. Apostol, Introduction to Analytic Number Theory, Springer, 1976 — Chapters 2 and 11, the standard reference for Dirichlet convolution.
- R. Lidl and H. Niederreiter, Finite Fields, 2nd ed., Cambridge, 1997 — §3.2 for the irreducible-polynomial count.
- R. P. Stanley, Enumerative Combinatorics, Vol. 1, 2nd ed., Cambridge, 2011 — §3.7 on Möbius functions of posets.
KEVOS® Knowledge LibraryEngineering → MathematicsTaxonomy ID: ENG-MATHPage ID: arithmetic-functions-and-mobius-inversionReview cycle: annual