Convolución de Dirichlet

Motivación: sumar sobre divisores

En teoría de números aparece repetidamente la operación de "sumar $f$ sobre los divisores": $\sum_{d \mid n} f(d)$. Si en vez de $f$ sumamos un producto $f(d) \cdot g(n/d)$, obtenemos la convolución de Dirichlet, que resulta ser una operación algebraicamente muy rica.

La convolución de Dirichlet generaliza la convolución discreta usual y la de series de potencias. Aparece de forma natural al estudiar series de Dirichlet $\sum_{n=1}^\infty f(n)/n^s$: el producto de dos series $\sum f(n)/n^s$ y $\sum g(n)/n^s$ es la serie con coeficientes $(f * g)(n)$.

Para el olímpico, la convolución es una herramienta de "inversión": si $g(n) = \sum_{d \mid n} f(d)$, la inversión de Möbius (lección siguiente) permite recuperar $f$ de $g$.

Definición de la convolución de Dirichlet

Dadas dos funciones aritméticas $f, g : \mathbb{Z}^+ \to \mathbb{C}$, su convolución de Dirichlet es la función $f * g : \mathbb{Z}^+ \to \mathbb{C}$ definida por

$(f * g)(n) = \sum_{d \mid n} f(d)\, g(n/d) = \sum_{ab = n} f(a)\, g(b)$

donde la suma recorre todos los pares de enteros positivos $(a, b)$ con $ab = n$.

Ejemplos fundamentales: $\tau = \mathbf{1} * \mathbf{1}$ donde $\mathbf{1}(n) = 1$ para todo $n$ (pues $\sum_{d \mid n} 1 = \tau(n)$). $\sigma = \text{id} * \mathbf{1}$ donde $\text{id}(n) = n$ (pues $\sum_{d \mid n} d = \sigma(n)$). $\phi * \mathbf{1} = \text{id}$ (la identidad fundamental de Euler).

Estructura algebraica: el anillo de Dirichlet

El conjunto de funciones aritméticas con la suma puntual $(f+g)(n) = f(n)+g(n)$ y la convolución de Dirichlet $*$ forma un anillo conmutativo.

Conmutatividad: $(f * g)(n) = \sum_{ab=n} f(a)g(b) = \sum_{ab=n} g(a)f(b) = (g * f)(n)$.

Asociatividad: $((f*g)*h)(n) = \sum_{abc=n} f(a)g(b)h(c) = (f*(g*h))(n)$. El argumento es que ambos lados suman $f(a)g(b)h(c)$ sobre todas las ternas $(a,b,c)$ con $abc = n$.

**Elemento neutro $\varepsilon$:** La función $\varepsilon(n) = [n=1]$ (vale 1 si $n=1$ y 0 en otro caso) satisface $(f * \varepsilon)(n) = \sum_{d \mid n} f(d)\varepsilon(n/d) = f(n) \cdot 1 = f(n)$. Luego $f * \varepsilon = f$ para toda $f$.

Inversibles: $f$ tiene inverso con respecto a $*$ si y solo si $f(1) \ne 0$. El inverso se construye recursivamente: $f^{-1}(1) = 1/f(1)$ y para $n > 1$, $f^{-1}(n) = -\frac{1}{f(1)}\sum_{d \mid n, d < n} f^{-1}(d)\,f(n/d)$.

La función de Möbius $\mu$

El inverso de Dirichlet de la función constante $\mathbf{1}$ es la función de Möbius $\mu$, definida por: $\mu(1) = 1$; $\mu(n) = 0$ si $n$ tiene un factor cuadrado primo; $\mu(p_1 \cdots p_k) = (-1)^k$ si $n = p_1 \cdots p_k$ con primos distintos.

Equivalentemente, $\mu$ es la única función multiplicativa con $\mu(p) = -1$ y $\mu(p^k) = 0$ para $k \ge 2$.

La identidad fundamental: $\mu * \mathbf{1} = \varepsilon$, es decir, $\sum_{d \mid n} \mu(d) = [n=1]$. Demostración: como $\mu$ y $\mathbf{1}$ son multiplicativas, su convolución también lo es. Para $n = p^k$: $\sum_{d \mid p^k} \mu(d) = \mu(1) + \mu(p) + \mu(p^2) + \cdots = 1 + (-1) + 0 + \cdots = 0$ si $k \ge 1$. Para $n=1$: la suma es $\mu(1) = 1$.

Convoluciones notables y sus identidades

El lenguaje de la convolución unifica múltiples identidades clásicas. La tabla siguiente expresa algunas de ellas:

$\mathbf{1} * \mathbf{1} = \tau$ (suma de 1s sobre divisores = número de divisores).

$\text{id} * \mathbf{1} = \sigma$ (suma de divisores).

$\phi * \mathbf{1} = \text{id}$ (identidad de Euler sobre $\phi$).

$\mu * \mathbf{1} = \varepsilon$ (identidad de Möbius).

$\mu * \text{id} = \phi$ (se obtiene convolucionando $\phi * \mathbf{1} = \text{id}$ por $\mu$: $\phi = \mu * \text{id}$).

Esta última identidad $\phi = \mu * \text{id}$ da una prueba alternativa de la fórmula del producto para $\phi$: $\phi(n) = \sum_{d \mid n} \mu(d)\,(n/d) = n \sum_{d \mid n} \mu(d)/d = n \prod_{p \mid n}(1 - 1/p)$.

Aplicación: evaluación de sumas sobre divisores

La convolución permite evaluar sumas del tipo $\sum_{d \mid n} f(d)$ cuando $f$ es multiplicativa. Si $f$ es multiplicativa, $\sum_{d \mid n} f(d) = (f * \mathbf{1})(n)$ también es multiplicativa, y se evalúa factorizando $n$.

Ejemplo. Calcula $\sum_{d \mid 360} \phi(d)$. Como $\phi * \mathbf{1} = \text{id}$, la suma es $\text{id}(360) = 360$. En general, $\sum_{d \mid n} \phi(d) = n$ para todo $n$, resultado que vimos en la lección anterior.

Ejemplo. Calcula $\sum_{d \mid n} \mu(d)^2$. Esta función es el indicador de que $n$ es libre de cuadrados: $\sum_{d \mid n} \mu(d)^2 = 2^{\omega(n)}$ donde $\omega(n)$ es el número de factores primos distintos de $n$. Demostración: es multiplicativa, y en $p^k$: la suma es $\mu(1)^2 + \mu(p)^2 = 1 + 1 = 2$ para todo $k \ge 1$. Así $\sum_{d \mid p_1^{a_1}\cdots p_r^{a_r}} \mu(d)^2 = 2^r = 2^{\omega(n)}$.