Inversión de Möbius

Teoría

La inversión de Möbius es una herramienta súper poderosa en la teoría de números que te permite "deshacer" una suma sobre divisores. Imagina que tienes una función aritmética $f(n)$ que no conoces directamente, pero sí conoces su función sumatoria $g(n)$, que es simplemente la suma de los valores de $f$ para todos los divisores de $n$. Esta técnica te da la receta exacta para recuperar los valores originales de $f(n)$ usando una función especial llamada la función de Möbius, $\mu(n)$.

Esta técnica es fundamental en problemas de olimpiada, especialmente cuando te piden contar cosas relacionadas con el máximo común divisor (mcd) o cuando trabajas con la función $\phi$ de Euler. La idea clave es que la función de Möbius actúa como un "filtro" que cancela todos los términos de la suma excepto el que te interesa. Es muy parecido al principio de inclusión-exclusión, pero aplicado de forma elegante a la estructura de divisibilidad de los números enteros. Si logras ver un problema como una suma sobre divisores, la inversión de Möbius suele ser la llave que abre la solución.

Para entenderla bien, piensa en la convolución de Dirichlet. La inversión de Möbius te dice básicamente que la función constante $1$ (que siempre vale 1) y la función de Möbius son inversas una de la otra bajo esta operación. Esto significa que si una función se construye acumulando valores, puedes aplicar la función de Möbius para "limpiar" esa acumulación y regresar al estado inicial.

Fórmulas Clave

Primero, recuerda la definición de la función de Möbius $\mu(n)$:

• $\mu(1) = 1$
• $\mu(n) = (-1)^k$ si $n$ es el producto de $k$ primos distintos (libre de cuadrados).
• $\mu(n) = 0$ si $n$ tiene algún factor cuadrático ($p^2 | n$).

La propiedad fundamental que hace que todo funcione es: $$\sum_{d|n} \mu(d) = \begin{cases} 1 & \text{si } n = 1 \ 0 & \text{si } n > 1 \end{cases}$$

El Teorema de Inversión de Möbius dice que si tienes dos funciones aritméticas $f$ y $g$ que cumplen: $$g(n) = \sum_{d|n} f(d)$$ Entonces puedes encontrar $f(n)$ haciendo: $$f(n) = \sum_{d|n} g(d) \mu\left(\frac{n}{d}\right)$$

También existe una forma simétrica usando la convolución de Dirichlet $(f * g)(n) = \sum_{d|n} f(d)g(n/d)$. Si defines $\mathbf{1}(n) = 1$ para todo $n$, el teorema se reduce a: $$g = f * \mathbf{1} \iff f = g * \mu$$

Una variación muy útil en problemas de conteo es la forma "hacia arriba" (para funciones con soporte infinito o en ciertos contextos combinatorios): $$G(n) = \sum_{k=1}^{\infty} F(kn) \implies F(n) = \sum_{k=1}^{\infty} \mu(k) G(kn)$$

Demostración

Para demostrar que $f(n) = \sum_{d|n} g(d) \mu(n/d)$ si empiezas con $g(n) = \sum_{k|n} f(k)$, sigue estos pasos:

1. Toma la expresión de la derecha y sustituye la definición de $g(d)$: $$\sum_{d|n} \mu\left(\frac{n}{d}\right) g(d) = \sum_{d|n} \mu\left(\frac{n}{d}\right) \left( \sum_{k|d} f(k) \right)$$

2. Ahora, cambia el orden de la doble suma. Nota que la condición de los índices es $k | d$ y $d | n$. Esto es equivalente a decir que $k$ debe ser un divisor de $n$, y que $d$ debe ser un múltiplo de $k$ que a su vez divida a $n$. Entonces, puedes escribir la suma como: $$\sum_{k|n} f(k) \sum_{d: k|d|n} \mu\left(\frac{n}{d}\right)$$

3. Haz un cambio de variable en la suma interna. Si defines $m = n/d$, nota que cuando $d$ recorre los valores entre $k$ y $n$ que son múltiplos de $k$ y divisores de $n$, entonces $m$ recorre exactamente todos los divisores de $n/k$. La suma se transforma en: $$\sum_{k|n} f(k) \left( \sum_{m|(n/k)} \mu(m) \right)$$

4. Usa la propiedad fundamental de la función de Möbius que aparece en las fórmulas clave. La suma interna $\sum_{m|(n/k)} \mu(m)$ será igual a $0$ siempre, a menos que el número sobre el que sumas los divisores sea $1$. Es decir, la suma es distinta de cero solo cuando $n/k = 1$, lo que implica que $k = n$.

5. Por lo tanto, el único término que sobrevive en la suma exterior es aquel donde $k = n$: $$f(n) \cdot (1) = f(n)$$

Esto confirma que la fórmula recupera exactamente el valor de $f(n)$.

$\square$