This site is supported by donations to The OEIS Foundation.

Möbius transform

(Redirected from Moebius (or Mobius) transform)

Not to be confused with the Möbius transformation (linear fractional transformation).

The Möbius transform (or Möbius inversion) is a bijection from the set of positive integer sequences to the set of positive integer sequences. It is thus a permutation of positive integer sequences (not a permutation of the positive integers, but of "positive integer sequences" as mathematical objects, the set of which has the cardinality of the continuum, i.e. the cardinality of the powerset of the positive integers ${\displaystyle 2^{\aleph _{0}}}$). Furthermore, the Möbius transform of a sequence gives a sequence with the same number of terms, so for each ${\displaystyle k\in \mathbb {N} }$ we have a permutation of "positive integer sequences with ${\displaystyle k}$ terms."

The Möbius transform of a positive integer sequence ${\displaystyle \{a_{n}\}_{n\geq 1}}$ is the unique positive integer sequence ${\displaystyle \{b_{n}\}_{n\geq 1}}$ defined (via the so-called Möbius inversion formula) as

${\displaystyle b_{n}:=\sum _{d|n}\mu {\big (}{\tfrac {n}{d}}{\big )}\,a_{d},}$

where ${\displaystyle d|n}$ means ${\displaystyle d}$ divides ${\displaystyle n}$ and ${\displaystyle \scriptstyle \mu (n)\,}$ is the Möbius function.

Inverse Möbius transform

The inverse Möbius transform, sometimes referred to as the sum-of-divisors transform, giving ${\displaystyle \{a_{n}\}_{n\geq 1}}$ from ${\displaystyle \{b_{n}\}_{n\geq 1}}$, is

${\displaystyle a_{n}=\sum _{d|n}b_{d},}$

where ${\displaystyle d|n}$ means ${\displaystyle d}$ divides ${\displaystyle n}$.

Examples

For example, the Möbius transform of the Fibonacci numbers

${\displaystyle \{a_{n}\}_{n\geq 1}}$ = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...}

is

${\displaystyle \{b_{n}\}_{n\geq 1}}$ = {1, 0, 1, 2, 4, 6, 12, 18, 32, 50, 88, 134, ...} (A007436)

since we have, for

${\displaystyle n}$ = 1: ${\displaystyle b_{1}}$ = ${\displaystyle \mu }$(1 / 1) * ${\displaystyle a_{1}}$ = 1 * 1 = 1;
${\displaystyle n}$ = 2: ${\displaystyle b_{2}}$ = ${\displaystyle \mu }$(2 / 1) * ${\displaystyle a_{1}}$ + ${\displaystyle \mu }$(2 / 2) * ${\displaystyle a_{2}}$ = (−1) * 1 + 1 * 1 = 0;
${\displaystyle n}$ = 3: ${\displaystyle b_{3}}$ = ${\displaystyle \mu }$(3 / 1) * ${\displaystyle a_{1}}$ + ${\displaystyle \mu }$(3 / 3) * ${\displaystyle a_{3}}$ = (−1) * 1 + 1 * 2 = 1;
${\displaystyle n}$ = 4: ${\displaystyle b_{4}}$ = ${\displaystyle \mu }$(4 / 1) * ${\displaystyle a_{1}}$ + ${\displaystyle \mu }$(4 / 2) * ${\displaystyle a_{2}}$ + ${\displaystyle \mu }$(4 / 4) * ${\displaystyle a_{4}}$ = 0 * 1 + (−1) * 1 + 1 * 3 = 2;
${\displaystyle n}$ = 5: ${\displaystyle b_{5}}$ = ${\displaystyle \mu }$(5 / 1) * ${\displaystyle a_{1}}$ + ${\displaystyle \mu }$(5 / 5) * ${\displaystyle a_{5}}$ = (−1) * 1 + 1 * 5 = 4;
${\displaystyle n}$ = 6: ${\displaystyle b_{6}}$ = ${\displaystyle \mu }$(6 / 1) * ${\displaystyle a_{1}}$ + ${\displaystyle \mu }$(6 / 2) * ${\displaystyle a_{2}}$ + ${\displaystyle \mu }$(6 / 3) * ${\displaystyle a_{3}}$ + ${\displaystyle \mu }$(6 / 6) * ${\displaystyle a_{6}}$ = 1 * 1 + (−1) * 1 + (−1) * 2 + 1 * 8 = 6;
${\displaystyle n}$ = 7: ${\displaystyle b_{7}}$ = ${\displaystyle \mu }$(7 / 1) * ${\displaystyle a_{1}}$ + ${\displaystyle \mu }$(7 / 7) * ${\displaystyle a_{7}}$ = (−1) * 1 + 1 * 13 = 12;

Conversely, the inverse Möbius transform of the Möbius transform of the Fibonacci numbers gives back the Fibonacci numbers, e.g.

${\displaystyle n}$ = 1: ${\displaystyle a_{1}}$ = ${\displaystyle b_{1}}$ = 1;
${\displaystyle n}$ = 2: ${\displaystyle a_{2}}$ = ${\displaystyle b_{1}}$ + ${\displaystyle b_{2}}$ = 1 + 0 = 1;
${\displaystyle n}$ = 3: ${\displaystyle a_{3}}$ = ${\displaystyle b_{1}}$ + ${\displaystyle b_{3}}$ = 1 + 1 = 2;
${\displaystyle n}$ = 4: ${\displaystyle a_{4}}$ = ${\displaystyle b_{1}}$ + ${\displaystyle b_{2}}$ + ${\displaystyle b_{4}}$ = 1 + 0 + 2 = 3;
${\displaystyle n}$ = 5: ${\displaystyle a_{5}}$ = ${\displaystyle b_{1}}$ + ${\displaystyle b_{5}}$ = 1 + 4 = 5;
${\displaystyle n}$ = 6: ${\displaystyle a_{6}}$ = ${\displaystyle b_{1}}$ + ${\displaystyle b_{2}}$ + ${\displaystyle b_{3}}$ + ${\displaystyle b_{6}}$ = 1 + 0 + 1 + 6 = 8;
${\displaystyle n}$ = 7: ${\displaystyle a_{7}}$ = ${\displaystyle b_{1}}$ + ${\displaystyle b_{7}}$ = 1 + 12 = 13;

Matrix representation of the Möbius transform

The Möbius transform of a finite sequence of positive integers ${\displaystyle \{a_{n}\}_{1\leq n\leq N}}$ into a finite sequence of positive integers ${\displaystyle \{b_{n}\}_{1\leq n\leq N}}$ may be represented by a ${\displaystyle N\times N}$ matrix ${\displaystyle M}$ (here shown as a right-side operator, so that we can conveniently represent the sequences as row vectors; if the sequences are represented as column vectors, we use the transpose ${\displaystyle M^{T}}$ as a left-side operator instead)

${\displaystyle (b_{1},\ldots ,b_{N})=(a_{1},\ldots ,a_{N})\,M=(a_{1},\ldots ,a_{N})\left({\begin{matrix}{\begin{array}{cccccc}M_{11}&M_{12}&\cdots &M_{1N}\\M_{21}&M_{22}&\cdots &M_{2N}\\\vdots &\vdots &\ddots &\vdots \\M_{N1}&M_{N2}&\cdots &M_{NN}\end{array}}\end{matrix}}\right),}$

where ${\displaystyle M_{ij}=[i|j]\,\mu {\big (}{\tfrac {j}{i}}{\big )}}$. (This matrix has trace ${\displaystyle N}$ and determinant 1.)

For the inverse Möbius transform, we thus have

${\displaystyle (a_{1},\ldots ,a_{N})=(b_{1},\ldots ,b_{N})\,M^{-1},}$

where ${\displaystyle M^{-1}}$ is the inverse matrix of ${\displaystyle M}$, with ${\displaystyle M_{ij}^{-1}=[i|j]}$. (This matrix also has trace ${\displaystyle N}$ and determinant 1.)

Starting with ${\displaystyle M^{-1}}$ (for which we have to know about the divisors, for each integer from 1 to ${\displaystyle N}$), one may then generate ${\displaystyle M}$ as ${\displaystyle (M^{-1})^{-1}}$ (where the top row now tells us which numbers from 1 to ${\displaystyle N}$ are squarefree, and whether they have an odd or even number of distinct prime factors!).

For the Möbius transform of finite sequences of a positive integers, e.g. of the first 8 terms of the Fibonacci sequence, we have the 8 ${\displaystyle \times }$ 8 matrix

${\displaystyle (1,0,1,2,4,6,12,18)=(1,1,2,3,5,8,13,21)\left({\begin{matrix}{\begin{array}{cccccccc}1&-1&-1&0&-1&1&-1&0\\0&1&0&-1&0&-1&0&0\\0&0&1&0&0&-1&0&0\\0&0&0&1&0&0&0&-1\\0&0&0&0&1&0&0&0\\0&0&0&0&0&1&0&0\\0&0&0&0&0&0&1&0\\0&0&0&0&0&0&0&1\\\end{array}}\end{matrix}}\right),}$

and for the inverse Möbius transform, we have

${\displaystyle (1,1,2,3,5,8,13,21)=(1,0,1,2,4,6,12,18)\left({\begin{matrix}{\begin{array}{cccccccc}1&1&1&1&1&1&1&1\\0&1&0&1&0&1&0&1\\0&0&1&0&0&1&0&0\\0&0&0&1&0&0&0&1\\0&0&0&0&1&0&0&0\\0&0&0&0&0&1&0&0\\0&0&0&0&0&0&1&0\\0&0&0&0&0&0&0&1\\\end{array}}\end{matrix}}\right).}$

For the Möbius transform of infinite sequences of a positive integers, e.g. of the Fibonacci sequence, we have the infinite square matrix

${\displaystyle (1,0,1,2,4,6,12,18,32,50,88,134,...)=(1,1,2,3,5,8,13,21,34,55,89,144,...)\left({\begin{matrix}{\begin{array}{cccccc}M_{11}&M_{12}&M_{13}&\cdots \\M_{21}&M_{22}&M_{23}&\cdots \\M_{31}&M_{32}&M_{33}&\cdots \\\vdots &\vdots &\vdots &\ddots \end{array}}\end{matrix}}\right).}$

For the inverse Möbius transform of infinite sequences of a positive integers, we obviously shall not attempt to invert the above infinite matrix!

Eigensequences of the Möbius transform

The eigensequences of the Möbius transform are... ?

Sequences

Sequences (Moebius transform)

A?????? Moebius transform applied once to sequence 1,0,0,0,....
A007427 Moebius transform applied twice to sequence 1,0,0,0,....
A007428 Moebius transform applied thrice to sequence 1,0,0,0,....

A?????? (Moebius transform applied once to natural numbers.)
A007431 Sum_{d|n} phi(d)*mu(n/d). (Moebius transform of Euler's totient function (A000010).) (Moebius transform applied twice to natural numbers.)
A007432 Moebius transform applied thrice to natural numbers.

A007438 Moebius transform of triangular numbers.
A007434 Jordan function J_2(n) (a generalization of phi(n)). (Moebius transform of squares.)

A007444 Moebius transform of primes.

A007436 Moebius transform of Fibonacci numbers.

Sequences (inverse Moebius transform)

A?????? d_2(n), or tau_2(n), the number of ordered 2-factorizations of n as n = r s. (Inverse Moebius transform applied once to all 1's sequence.)
A007425 d_3(n), or tau_3(n), the number of ordered 3-factorizations of n as n = r s t. (Inverse Moebius transform applied twice to all 1's sequence.)
A007426 d_4(n), or tau_4(n), the number of ordered 4-factorizations of n as n = r s t u. (Inverse Moebius transform applied thrice to all 1's sequence; or, Dirichlet convolution of d(n) [ A000005 ].)
A061200 d_5(n), or tau_5(n), the number of ordered 5-factorizations of n as n = r s t u v. (Inverse Moebius transform applied 4 times to all 1's sequence.)

A000005 d(n) (also called tau(n) or sigma_0(n)), the number of divisors of n. (Inverse Moebius transform of ...)

A000203 sigma(n) = sum of divisors of n. Also called sigma_1(n). (Inverse Moebius transform of the natural numbers.)
A007429 Inverse Moebius transform applied twice to natural numbers.
A007430 Inverse Moebius transform applied thrice to natural numbers.

A007437 Inverse Moebius transform of triangular numbers.
A007433 Inverse Moebius transform applied twice to squares.

A046951 Number of squares dividing n. (Inverse Moebius transform of characteristic function of squares (A010052).)
A061704 Number of cubes dividing n. (Inverse Moebius transform of characteristic function of cubes (A010057).)
A069088 Sum(d|n, core(d) ) where d are the divisors of n and where core(d) is the squarefree part of d: the smallest number such that d*core(d) is a square. (Inverse Moebius transform of squarefree part of n (A007913).)

A007445 Inverse Moebius transform of primes.

A001221 Number of distinct primes dividing n (also called omega(n)). (Inverse Moebius transform of characteristic function of primes (A010051).)
A?????? Number of distinct "2-almost primes" (A??????) which are factors of n. (Inverse Moebius transform of characteristic function of "2-almost primes" (A??????).)
A101606 Number of distinct "3-almost primes" (A014612) which are factors of n. (Inverse Moebius transform of characteristic function of "3-almost primes" (A101605).)
A101638 Number of distinct "4-almost primes" (A014613) which are factors of n. (Inverse Moebius transform of characteristic function of "4-almost primes" (A101637).)
A?????? Number of distinct "5-almost primes" (A??????) which are factors of n. (Inverse Moebius transform of characteristic function of "5-almost primes" (A??????).)

A?????? Number of distinct Sophie Germain primes dividing n. (Inverse Moebius transform of characteristic function of Sophie Germain primes (A156660).)(Verify.)[1]

A007435 Inverse Moebius transform of Fibonacci numbers.

A057660 Sum_{k=1..n} n/GCD(n,k). (Inverse Moebius transform of phi(n^2).)

Notes

1. Needs verification.