Inversión de Möbius

La fórmula de inversión: enunciado clásico

El resultado central de esta lección invierte la operación de "sumar sobre divisores". Supongamos que conocemos $g(n) = \sum_{d \mid n} f(d)$ para todo $n$, y queremos recuperar $f$ a partir de $g$.

Teorema (Inversión de Möbius). Si $g(n) = \sum_{d \mid n} f(d)$, entonces $f(n) = \sum_{d \mid n} \mu(d)\, g(n/d) = \sum_{d \mid n} \mu(n/d)\, g(d)$.

Demostración en lenguaje de convolución: la hipótesis es $g = f * \mathbf{1}$. Convolucionando ambos lados por $\mu$: $g * \mu = (f * \mathbf{1}) * \mu = f * (\mathbf{1} * \mu) = f * \varepsilon = f$. Luego $f = g * \mu$, que es exactamente la fórmula.

Demostración directa sin convolución

Para aquellos que prefieren la verificación explícita: queremos mostrar que $\sum_{d \mid n} \mu(n/d) g(d) = f(n)$ dado que $g(d) = \sum_{e \mid d} f(e)$.

Sustituyendo: $\sum_{d \mid n} \mu(n/d) \sum_{e \mid d} f(e) = \sum_{e \mid n} f(e) \sum_{e \mid d \mid n} \mu(n/d)$.

El coeficiente de $f(e)$ en la suma doble es $\sum_{e \mid d \mid n} \mu(n/d)$. Con la sustitución $d = ef$ y $n = em$: $\sum_{f \mid m} \mu(m/f) = \sum_{k \mid m} \mu(k)$ (con $k = m/f$) $= [m = 1] = [e = n]$.

Luego la suma doble colapsa a $f(n) \cdot 1 = f(n)$. La inversión de Möbius queda verificada directamente.

Aplicaciones clásicas

**Ejemplo 1: recuperar $\phi$ de $\text{id}$.** Sabemos que $\phi * \mathbf{1} = \text{id}$, es decir, $\sum_{d \mid n} \phi(d) = n$. La inversión de Möbius da $\phi(n) = \sum_{d \mid n} \mu(n/d)\, d$, que es la fórmula $\phi = \mu * \text{id}$ ya mencionada.

Ejemplo 2: conteo de polinomios primitivos. Sea $\Lambda(n)$ el número de cadenas binarias de longitud $n$ que no son repetición de una cadena más corta (cadenas "primitivas" o "aperiódicas"). Si $M(n) = 2^n$ es el total de cadenas y $M(n) = \sum_{d \mid n} \Lambda(d)$ (cada cadena de longitud $n$ tiene un período mínimo $d \mid n$), entonces $\Lambda(n) = \sum_{d \mid n} \mu(n/d)\, 2^d$ por inversión de Möbius.

Ejemplo 3: fórmula del collar de Burnside. En combinatoria, el número de collares binarios de $n$ cuentas es $\frac{1}{n}\sum_{d \mid n} \phi(d)\, 2^{n/d}$. La inversión de Möbius subyace a la relación entre collares y collares primitivos.

Versión multiplicativa de la inversión

Existe una versión multiplicativa: si $G(n) = \prod_{d \mid n} F(d)$, entonces $F(n) = \prod_{d \mid n} G(d)^{\mu(n/d)}$.

Demostración: aplicar logaritmo a ambos lados reduce la versión multiplicativa a la aditiva con $f = \log F$ y $g = \log G$ (cuando los valores son positivos).

Ejemplo. Sea $F(n)$ la función tal que $G(n) = \prod_{d \mid n} F(d) = n$ para todo $n$. Entonces $F(n) = \prod_{d \mid n} d^{\mu(n/d)}$. Se puede demostrar que $F(n) = e^{\Lambda(n)}$ donde $\Lambda$ es la función de von Mangoldt: $\Lambda(n) = \log p$ si $n = p^k$ y $0$ en otro caso.

La función de Möbius y la criba

La inversión de Möbius está relacionada con el principio de inclusión-exclusión en la criba de Eratóstenes. La función $\mu$ actúa como coeficiente de inclusión-exclusión para propiedades multiplicativas.

Formalmente, si $A$ es un conjunto de enteros y queremos contar los elementos de $A$ coprimos con $n = p_1 \cdots p_k$ (libre de cuadrados), usamos: $\#\{a \in A : \gcd(a,n)=1\} = \sum_{d \mid n} \mu(d) \#\{a \in A : d \mid a\}$. Esta es exactamente la inclusión-exclusión sobre los primos $p_1, \ldots, p_k$.

Aplicación. $\phi(n) = \sum_{d \mid n} \mu(d)\cdot \lfloor n/d \rfloor$ cuando $n$ es libre de cuadrados, y $\phi(n) = \sum_{d \mid n} \mu(d) \cdot (n/d)$ en general, concordando con $\phi = \mu * \text{id}$.

Problemas olímpicos con inversión de Möbius

Estrategia de reconocimiento. La inversión de Möbius aplica cuando: (1) hay una función definida como suma sobre divisores; (2) se quiere aislar el "término diagonal" $f(n)$; (3) aparece el conteo de objetos "primitivos" o "irreducibles" frente a objetos generales.

Problema olímpico (estilo IbAm). Sea $f(n)$ el número de soluciones de $xy \equiv 0 \pmod{n}$ con $1 \le x, y \le n$. Expresa $f(n)$ en términos de $\tau$ y $\phi$. Solución: $f(n) = \sum_{d \mid n} \phi(d)^2$ puede obtenerse convolucionando convenientemente, y la inversión permite descomponer la suma.

Fórmulas de Ramanujan. Las sumas de Ramanujan $c_q(n) = \sum_{\substack{a=1\\\gcd(a,q)=1}}^q e^{2\pi i an/q}$ satisfacen $c_q(n) = \sum_{d \mid \gcd(q,n)} \mu(q/d)\, d$. Se calculan directamente con inversión de Möbius, y aparecen en problemas avanzados de sumas exponenciales.