La Enciclopedia Libre Universal en Español dispone de una lista de distribución pública, enciclo@listas.us.es

Función de Möbius

Artículo de la Enciclopedia Libre Universal en Español.

Saltar a navegación, buscar

[escribe] I Definición

En el campo de la aritmética, la función μ (« mu » o « my ») de Möbius se define así:

Para todo número natural n se considera su descomposición en factores primos :

$n = p_1^{r_1} p_2^{r_2}... p_k^{r_k}$

Si n contiene un factor cuadrado, es decir si una de las potencias r_i es superior o igual a dos, entonces se decide que μ(n) = 0.
Si no es el caso, n es «libre de cuadrado», y se define así la función:
- Si n tiene un número par de factores primos, entonces μ(n) = 1
- Si n tiene un número impar de factores primos, entonces μ(n) = -1

En ambos casos, n se escribe

$\ n = p_1 p_2 ... p_k$

(todos los r_i son iguales a 1 ), y μ(n) = (-1)^k.

Ejemplos:

μ(1) = 1 porque 1 es un producto de cero factor primo (un producto vacío), y cero es par.

μ(18) = 0 porque 18 = 2×3² contiene el factor cuadrado 9.

μ(32) = 0 porque 32 = 2⁵ contiene los cuadrados 4 = 2² y también 16 = 2⁴.

μ(30) = -1 pues 30 = 2×3×5 es producto de tres (impar) primos distintos.

μ(77)= 1 pues 77 = 7×11 es un producto de dos (par) primos distintos.

Una propiedad: Si m y n son coprimos, entonces μ(m·n) = μ(m)·μ(n). Es la multiplicatividad condicional.

Prueba: Si m o n contiene un cuadrado, entonces el producto m·n también, y los dos miembros de la igualdad son iguales a cero. Si no, sea k y k' los números de factores de m y n. Entonces m·n tiene k + k' factores primos, todos distintos porque m y n son coprimos, y la igualdad se escribe sencillamente (-1)^{k + k'} = (-1)^k · (-1)^k'.

[escribe] II Interés

La función de Möbius fue inventada para resolver sistemas particulares de ecuaciones. Para entenderlo, hay que introducir el producto de convolución entre dos sucesiones (o funciones sobre los enteros naturales): si f y g son sucesiones, se define su producto f*g así:

$f*g \ (n) = \sum_{d \mid n} f(d)g(\frac n d)$

Este producto es conmutativo, asociativo, y su neutro es la sucesión ε = (1, 0, 0, 0, 0 ...) es decir: ε(0) = 1 y ε(n) = 0 para todo n > 0.

Llamemos 1 la sucesión constante de valor 1. Entonces:

$f*1 \ (n) = \sum_{d \mid n} f(d)$

Supongamos ahora que tengamos que resolver el sistema siguiente, con una infinidad de líneas y de incógnitas las f(n) (las g(n) son conocidas)

$\left \{ \begin{matrix} f(1) & = & g(1) \\ f(1) + f(2) & = &g(2) \\ f(1) + f(3) & = & g(3) \\ f(1) + f(2) + f(4) & = & g(4) \\ f(1) + f(5) & = & g(5) \\ f(1) + f(2) + f(3) + f(6) & = & g(6) \\ f(1) + f(7) & = & g(7) \\ f(1) + f(2) + f(4) + f(8) & = & g(8) \\ f(1) + f(3) + f(9) & = & g(9) \\ f(1) + f(2) + f(5) + f(10) & = & g(10) \\ & ... & \\ \sum_{d \mid n} f(d) & = & g(n) \\ & ... & \end{matrix} \right.$

En términos de convolución, este sistema se escribe f*1 = g.
Para hallar f, hay que multiplicar ambos miembros de la ecuación por el inverso de la sucesión 1, y este es justamente la sucesión μ de Möbius (prueba más adelante).
Luego (f*1)*μ = g*μ que equivale a f*(1*μ) = g*μ (asociatividad), es decir f*ε = g*μ y finalmente f = g*μ.

En síntesis:

$\ f*1 = g \Longleftrightarrow f = g* \mu$

En términos de sistemas: Para todo n entero natural no nulo,

$(\forall n>0, \sum_{d \mid n} f(d) = g(n) ) \quad \Longleftrightarrow \quad (\forall n>0, f(n) = \sum_{d \mid n}\mu (\frac n d) g(d) )$

Esta propiedad se llama «fórmula de inversión de Möbius» .

Falta demostrar que las funciones μ y 1 son inversas la una de la otra, es decir: μ * 1 = ε, concretamente:

Para n = 1 ,

$\sum_{d \mid 1}\mu (d) = \epsilon (1) = 1$

y si n > 1,

$\sum_{d \mid n}\mu (d) = \epsilon (n) = 0$

Lo primero es obvio porque la suma vale μ (1) = 1.

Lo segundo se muestra por etapas:

Si n = p es primo entonces la suma es μ(1) + μ(p) = 1 1 = 0.
Si n = p^r (r>1), la suma es μ(1) + μ(p) + μ(p²) + ... + μ( p^r) = 1 1 + 0 + ... + 0 = 0.
Si n = a·b, con a y b coprimos, los divisores de a·b son de la forma d₁·d₂, con d₁ y ₂ coprimos. Como hipótesis de inducción admitimos el resultado para a y b (ambos superiores a 1). Luego:

$\sum_{d \mid n}\mu (d) = \sum_{d_1 \mid a, d_2 \mid b} \mu (d_1 d_2) = \sum_{d_1 \mid a, d_2 \mid b} \mu (d_1) \mu( d_2) = \sum_{d_1 \mid a}\mu (d_1) \sum_{d_2 \mid a}\mu (d_2) = 0 \times 0 = 0$

La «inversión» del sistema anterior es, aplicando la fórmula:

$\left \{ \begin{matrix} f(1) & = & g(1) \\ f(2) & = & g(2) - g(1) \\ f(3) & = & g(3) - g(1) \\ f(4) & = & g(4) - g(2) \\ f(5) & = & g(5) - g(1) \\ f(6) & = & g(6) - g(3) - g(2) + g(1) \\ f(7) & = & g(7) - g(1) \\ f(8) & = & g(8) - g(4) \\ f(9) & = & g(9) - g(3) \\ f(10) & = & g(10) - g(5) - g(2) + g(1) \\ & ... & \\ f(n) & = & \sum_{d \mid n} g(d) \mu (\frac d n) \\ & ... & \end{matrix} \right.$