Möbius inversion is a mathematical technique used to reverse relationships involving sums over divisors. It is based on the Möbius function and its divisor-sum identity. The central idea is that if one arithmetic function is defined as a sum of another function over the divisors of an integer, the original function can be recovered by applying a corresponding sum involving the Möbius function.
Suppose f and g are arithmetic functions related by g(n) = Σ_{d|n} f(d). This means that g(n) is obtained by adding the values of f over all positive divisors of n. Möbius inversion states that the original function can be recovered through f(n) = Σ_{d|n} μ(d)g(n/d). An equivalent form is f(n) = Σ_{d|n} μ(n/d)g(d).
The reason the formula works is the identity Σ_{d|n} μ(d) = 0 for n > 1 and 1 for n = 1. When the divisor sums are expanded, the Möbius values cancel contributions from all unwanted divisors, leaving only the required original value.
Möbius inversion is widely used in number theory, combinatorics, and the study of arithmetic functions. It is particularly useful when a function is easier to calculate as a sum over divisors than directly. It also has important analogues in partially ordered sets, where it becomes a general mathematical inversion principle.
Möbius Inversion Formula
The Möbius Inversion Formula is a fundamental result in number theory that allows an arithmetic function to be recovered from its divisor sums by using the Möbius function.
| Name | Expression | Description |
|---|---|---|
Divisor-Sum Relationship | g(n) = Σ_{d|n} f(d) | Defines g as the sum of f over all positive divisors of n. |
Möbius Inversion Formula | f(n) = Σ_{d|n} μ(d)g(n/d) | Recovers f from g by weighting the divisor terms with the Möbius function. |
Equivalent Inversion Form | f(n) = Σ_{d|n} μ(n/d)g(d) | An equivalent expression obtained by changing the divisor variable. |
Möbius Identity | Σ_{d|n} μ(d) = ε(n) | Here ε(1) = 1 and ε(n) = 0 for n > 1. |
Explanation
Variables
F(n)
The original arithmetic function to be recovered.
G(n)
The transformed function defined as the sum of f over the divisors of n.
D
A positive divisor of n.
N
A positive integer.
Μ(d)
The Möbius function evaluated at divisor d.
Ε(n)
The identity arithmetic function that equals 1 at n = 1 and 0 otherwise.
Example or application
A worked example has not yet been added.
Definition
If g(n) = Σ_{d|n} f(d), then the Möbius Inversion Formula states that f(n) = Σ_{d|n} μ(d)g(n/d), where μ is the Möbius function.
Purpose
The purpose of Möbius inversion is to recover an arithmetic function from its divisor-sum transformation. It provides a systematic method for reversing sums over divisors and isolating individual arithmetic contributions.
Importance
It reverses divisor-sum relationships between arithmetic functions.
It is a direct application of the Möbius function.
It helps derive important identities involving divisor functions.
It is used in counting problems involving divisibility and exact properties.
It provides a foundation for more general inversion principles in combinatorics.
It plays an important role in analytic and algebraic number theory.
Key Concepts
| Name | Description |
|---|---|
Divisor Sum | A sum taken over all positive divisors of an integer. |
Möbius Function | The multiplicative function μ(n) used to cancel unwanted divisor contributions. |
Inversion | The process of recovering an original function from a transformed function. |
Arithmetic Function | A function defined on positive integers. |
Divisor-Sum Transformation | The relationship g(n) = Σ_{d|n} f(d), which combines the values of f over the divisors of n. |
Characteristics
Möbius inversion applies to arithmetic functions defined on positive integers.
It uses the Möbius function to reverse divisor sums.
It is based on the identity Σ_{d|n} μ(d) = 0 for n > 1.
It has equivalent forms depending on how the divisors are indexed.
It can simplify problems involving sums over divisors.
It is closely related to Dirichlet convolution.
It has generalizations to partially ordered sets and combinatorial structures.
Types
| Name | Description |
|---|---|
Classical Arithmetic Möbius Inversion | The standard inversion formula for arithmetic functions and sums over positive divisors. |
Dirichlet Convolution Form | An equivalent formulation using the convolution inverse of the constant-one arithmetic function. |
Poset Möbius Inversion | A broader generalization of Möbius inversion to functions defined on partially ordered sets. |
Components
| Name | Description |
|---|---|
Original Function | The arithmetic function f(n) that is to be recovered. |
Transformed Function | The function g(n), defined as a sum of f over the divisors of n. |
Divisor Set | The positive divisors over which the sums are calculated. |
Möbius Function | The function μ(n) that provides the required cancellation. |
Inversion Sum | The final divisor sum that reconstructs f(n). |
Properties
Möbius inversion reverses a divisor-sum transformation.
The inversion formula is based on the Möbius divisor-sum identity.
The formula has two equivalent forms obtained by changing the divisor variable.
It can be expressed compactly using Dirichlet convolution.
It applies to arithmetic functions without requiring them to be multiplicative.
The inversion process relies on the structure of positive integer divisibility.
The general principle extends to finite partially ordered sets and other mathematical structures.
Examples
| Title | Problem | Solution | Answer |
|---|---|---|---|
Recovering a Function from a Divisor Sum | Suppose g(n) = Σ_{d|n} f(d). Express f(6) using Möbius inversion. | The positive divisors of 6 are 1, 2, 3, and 6. Using f(6) = Σ_{d|6} μ(d)g(6/d), we obtain f(6) = μ(1)g(6) + μ(2)g(3) + μ(3)g(2) + μ(6)g(1). The Möbius values are 1, −1, −1, and 1. | f(6) = g(6) − g(3) − g(2) + g(1). |
Recovering Euler's Totient Function | Use Möbius inversion to understand the relationship between the identity function and Euler's totient function. | A standard divisor-sum identity is Σ_{d|n} φ(d) = n. Thus, set g(n) = n and f(n) = φ(n). Möbius inversion gives φ(n) = Σ_{d|n} μ(d)(n/d). | φ(n) = Σ_{d|n} μ(d)(n/d). |
Applications
Recovering arithmetic functions from divisor sums.
Deriving formulas for Euler's totient function.
Counting objects according to exact divisibility properties.
Solving combinatorial counting problems.
Developing identities in analytic number theory.
Studying inversion principles on partially ordered sets.
Working with Dirichlet convolution.
Prerequisites
Divisors and divisibility
Arithmetic functions
Möbius function
Finite summation notation
Basic Dirichlet convolution
Learning Objectives
Explain the purpose of Möbius inversion.
State the classical Möbius Inversion Formula.
Identify the original and transformed arithmetic functions.
Apply the formula to a divisor-sum relationship.
Explain how the Möbius function produces cancellation.
Derive the Möbius formula for Euler's totient function.
Describe the connection between Möbius inversion and Dirichlet convolution.
Common Mistakes
Using μ(n) instead of the Möbius value for the appropriate divisor.
Confusing g(n) = Σ f(d) with the inversion formula.
Changing the divisor variable incorrectly.
Forgetting to include every positive divisor.
Assuming that f must be multiplicative for Möbius inversion to apply.
Ignoring the identity value μ(1) = 1.
Confusing arithmetic Möbius inversion with its more general partially ordered set version.
Practice Questions
State the Möbius Inversion Formula.
If g(n) = Σ_{d|n} f(d), write the expression for f(n).
Use Möbius inversion to express f(10) in terms of g.
Derive φ(n) = Σ_{d|n} μ(d)(n/d).
Explain why the Möbius divisor-sum identity is necessary for inversion.
What is the relationship between Möbius inversion and Dirichlet convolution?
Does Möbius inversion require the original arithmetic function to be multiplicative?
Key Takeaway
Möbius inversion reverses divisor-sum relationships by using the Möbius function to cancel unwanted terms. It is one of the central techniques for transforming and recovering arithmetic functions in number theory.
Related Topics
Möbius Function
Dirichlet Convolution
Multiplicative Arithmetic Functions
Euler's Totient Function
Divisor Functions
Partially Ordered Sets
Analytic Number Theory
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Source verification pending; check an authoritative textbook, university, standards body, or peer-reviewed source.
Suggest a correction or source · More in Arithmetic & Number Theory