Möbius inversion
ProvedFamousTheorems.mobius_inversionMöbius inversion. Let be a ring and . Then
where is the Möbius function.
Möbius inversion is a basic tool of multiplicative number theory. It turns identities such as into , it underlies the counting of irreducible polynomials over finite fields, and it generalizes to incidence algebras of posets.
Formalization note. Mathlib's ArithmeticFunction.sum_eq_iff_sum_mul_moebius_eq. The second sum is over n.divisorsAntidiagonal, the pairs with , and ArithmeticFunction.moebius is the integer-valued Möbius function, cast to R.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem mobius_inversion {R : Type*} [NonAssocRing R] {f g : ℕ → R} :
(∀ n > 0, ∑ i ∈ n.divisors, f i = g n) ↔
∀ n > 0, ∑ x ∈ n.divisorsAntidiagonal, (ArithmeticFunction.moebius x.1 : R) * g x.2 = f n := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `ArithmeticFunction.sum_eq_iff_sum_mul_moebius_eq`. Proof here reduces to that Mathlib result.