Möbius transform

This article page is a stub, please help by expanding it.

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 integer sequences to the set of integer sequences.

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

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

where $d|n$ means $d$ divides $n$ and $\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 $\{a_{n}\}_{n\geq 1}$ from $\{b_{n}\}_{n\geq 1}$, is

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

where $d|n$ means $d$ divides $n$.

Examples

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

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

is

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

since we have, for

$n$ = 1: $b_{1}$ = $\mu$(1 / 1) * $a_{1}$ = 1 * 1 = 1;

$n$ = 2: $b_{2}$ = $\mu$(2 / 1) * $a_{1}$ + $\mu$(2 / 2) * $a_{2}$ = (−1) * 1 + 1 * 1 = 0;

$n$ = 3: $b_{3}$ = $\mu$(3 / 1) * $a_{1}$ + $\mu$(3 / 3) * $a_{3}$ = (−1) * 1 + 1 * 2 = 1;

$n$ = 4: $b_{4}$ = $\mu$(4 / 1) * $a_{1}$ + $\mu$(4 / 2) * $a_{2}$ + $\mu$(4 / 4) * $a_{4}$ = 0 * 1 + (−1) * 1 + 1 * 3 = 2;

$n$ = 5: $b_{5}$ = $\mu$(5 / 1) * $a_{1}$ + $\mu$(5 / 5) * $a_{5}$ = (−1) * 1 + 1 * 5 = 4;

$n$ = 6: $b_{6}$ = $\mu$(6 / 1) * $a_{1}$ + $\mu$(6 / 2) * $a_{2}$ + $\mu$(6 / 3) * $a_{3}$ + $\mu$(6 / 6) * $a_{6}$ = 1 * 1 + (−1) * 1 + (−1) * 2 + 1 * 8 = 6;

$n$ = 7: $b_{7}$ = $\mu$(7 / 1) * $a_{1}$ + $\mu$(7 / 7) * $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.

$n$ = 1: $a_{1}$ = $b_{1}$ = 1;

$n$ = 2: $a_{2}$ = $b_{1}$ + $b_{2}$ = 1 + 0 = 1;

$n$ = 3: $a_{3}$ = $b_{1}$ + $b_{3}$ = 1 + 1 = 2;

$n$ = 4: $a_{4}$ = $b_{1}$ + $b_{2}$ + $b_{4}$ = 1 + 0 + 2 = 3;

$n$ = 5: $a_{5}$ = $b_{1}$ + $b_{5}$ = 1 + 4 = 5;

$n$ = 6: $a_{6}$ = $b_{1}$ + $b_{2}$ + $b_{3}$ + $b_{6}$ = 1 + 0 + 1 + 6 = 8;

$n$ = 7: $a_{7}$ = $b_{1}$ + $b_{7}$ = 1 + 12 = 13;

Matrix representation of the Möbius transform

The Möbius transform of a finite sequence of integers $\{a_{n}\}_{1\leq n\leq N}$ into a finite sequence of integers $\{b_{n}\}_{1\leq n\leq N}$ may be represented by a $N\times N$ matrix $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 $M^{T}$ as a left-side operator instead)

$(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 $M_{ij}=[i|j]\,\mu {\big (}{\tfrac {j}{i}}{\big )}$. (This matrix has trace $N$ and determinant 1.)

For the inverse Möbius transform, we thus have

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

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

Starting with $M^{-1}$ (for which we have to know about the divisors, for each integer from 1 to $N$), one may then generate $M$ as $(M^{-1})^{-1}$ (where the top row now tells us which numbers from 1 to $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 integers, e.g. of the first 8 terms of the Fibonacci sequence, we have the 8 $\times$ 8 matrix

$(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

$(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 integers, e.g. of the Fibonacci sequence, we have the infinite square matrix

$(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 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.) 

A007435 Inverse Moebius transform of Fibonacci numbers.

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

External links

• Bernstein, M.; Sloane, N. J. A. (1995), “Some Canonical Sequences of Integers”, Linear Algebra and Its Applications 226-228: 57-72, doi:10.1016/0024-3795(94)00245-9, http://neilsloane.com/doc/eigen.pdf . (Seidel Festschrift.)