✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · SCI-MAT-002-095

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.

NameExpressionDescription

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

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.

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

NameDescription

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

NameDescription

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

NameDescription

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

TitleProblemSolutionAnswer

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