Convolución de Dirichlet

Teoría

La convolución de Dirichlet es una operación súper poderosa que toma dos funciones aritméticas (funciones que van de los enteros positivos a los números complejos) y te entrega una nueva función. Imagina que tienes dos funciones $f$ y $g$; su convolución, que escribes como $f * g$, suma los productos de los valores de $f$ y $g$ evaluados en los divisores de un número. Es como una multiplicación especial que vive en el mundo de la teoría de números. Si alguna vez has sentido que funciones como la de Euler ($\phi$) o la de Möbius ($\mu$) están conectadas de forma misteriosa, la convolución es el pegamento que explica esas relaciones.

¿Por qué te importa esto? Porque simplifica muchísimo el manejo de sumas sobre divisores. En lugar de pelearte con sumatorias horribles, puedes ver todo como una estructura algebraica elegante. Además, tiene una conexión directa con las series de Dirichlet: si multiplicas dos series de Dirichlet, los coeficientes de la serie resultante son precisamente la convolución de los coeficientes originales. Esto es clave en problemas de nivel IMO o USAMO donde necesitas manipular identidades de funciones multiplicativas o aplicar la inversión de Möbius de forma rápida y sin errores.

La intuición clave es que la convolución de Dirichlet trata a los divisores de un número como los "componentes" de una multiplicación. Mientras que la suma normal de funciones suma valores punto a punto, la convolución mezcla los valores de $f$ y $g$ basándose en cómo se descompone el número $n$ en factores. Si $f$ y $g$ son multiplicativas, su convolución también lo será, lo que te permite estudiar funciones complejas analizando solo lo que pasa con las potencias de primos.

Fórmulas Clave

La definición principal de la convolución de Dirichlet para dos funciones $f$ y $g$ evaluadas en $n$ es: $$(f * g)(n) = \sum_{d|n} f(d)g\left(\frac{n}{d}\right)$$ También puedes escribirla de forma simétrica como: $$(f * g)(n) = \sum_{ab=n} f(a)g(b)$$

Aquí tienes las propiedades y funciones especiales más importantes:

• Elemento Identidad: La función $\epsilon(n)$ (también llamada $I$ o $\delta$) cumple que $f * \epsilon = f$. La defines como: $$\epsilon(n) = \begin{cases} 1 & \text{si } n = 1 \ 0 & \text{si } n > 1 \end{cases}$$
• Conmutatividad y Asociatividad: $$f * g = g * f$$ $$(f * g) * h = f * (g * h)$$
• Inversión de Möbius: Si defines la función constante $1(n) = 1$ para todo $n$, entonces la función de Möbius $\mu$ es su inversa bajo la convolución ($1 * \mu = \epsilon$). Esto te da la famosa fórmula: $$g(n) = \sum_{d|n} f(d) \iff f(n) = \sum_{d|n} g(d)\mu\left(\frac{n}{d}\right)$$
• Identidades famosas:
  • Función de Euler: $\phi * 1 = Id$, donde $Id(n) = n$.
  • Cantidad de divisores: $d(n) = (1 * 1)(n)$.
  • Suma de divisores: $\sigma(n) = (Id * 1)(n)$.

Demostración

Lo que hay que mostrar es que la convolución de Dirichlet es asociativa, es decir, que $(f * g) * h = f * (g * h)$. Esta es la propiedad más importante porque te permite agrupar funciones como quieras en problemas de olimpiada.

1. Primero, escribe la definición de la parte izquierda evaluada en $n$. Toma $F = f * g$, entonces: $$((f * g) * h)(n) = (F * h)(n) = \sum_{d|n} F(d)h\left(\frac{n}{d}\right)$$

2. Ahora, sustituye la definición de $F(d)$ dentro de la suma. Nota que $F(d) = \sum_{ab=d} f(a)g(b)$: $$((f * g) * h)(n) = \sum_{d|n} \left( \sum_{ab=d} f(a)g(b) \right) h\left(\frac{n}{d}\right)$$

3. Observa que esta es una suma doble sobre pares $(d, n/d)$ y luego sobre pares $(a, b)$ tales que $ab=d$. Si juntas todo, te das cuenta de que estás sumando sobre todas las ternas de números $(a, b, c)$ cuyo producto es exactamente $n$: $$((f * g) * h)(n) = \sum_{abc=n} f(a)g(b)h(c)$$

4. Ahora haz lo mismo para el lado derecho. Si tomas $G = g * h$, entonces: $$(f * (g * h))(n) = (f * G)(n) = \sum_{a|n} f(a)G\left(\frac{n}{a}\right)$$

5. Sustituye $G(n/a) = \sum_{bc=n/a} g(b)h(c)$: $$(f * (g * h))(n) = \sum_{a|n} f(a) \left( \sum_{bc=n/a} g(b)h(c) \right)$$

6. Al igual que antes, esto se reduce a una suma sobre todas las combinaciones de $a, b, c$ tales que su producto es $n$: $$(f * (g * h))(n) = \sum_{abc=n} f(a)g(b)h(c)$$

Como ambos lados de la ecuación original resultan en la misma suma sobre las ternas $(a, b, c)$ que cumplen $abc=n$, queda demostrado que la operación es asociativa. $\square$