Funciones multiplicativas: \tau, \sigma, \phi revisitadas

Funciones aritméticas y multiplicatividad

Una función aritmética es cualquier función $f : \mathbb{Z}^+ \to \mathbb{C}$. El estudio sistemático de tales funciones es uno de los pilares de la teoría de números analítica y olímpica. Las más importantes son aquellas que respetan la estructura multiplicativa de los enteros.

Una función aritmética $f$ se llama multiplicativa si $f(1) = 1$ y $f(mn) = f(m)f(n)$ siempre que $\gcd(m,n) = 1$. Se llama completamente multiplicativa si la condición $f(mn) = f(m)f(n)$ vale para todos $m, n$ sin restricción.

La importancia de la multiplicatividad radica en que basta conocer los valores de $f$ en las potencias de primos $p^k$ para determinar $f$ en todo entero positivo: si $n = p_1^{a_1} \cdots p_r^{a_r}$, entonces $f(n) = f(p_1^{a_1}) \cdots f(p_r^{a_r})$.

La función $\tau$: número de divisores

La función $\tau(n)$ (también escrita $d(n)$) cuenta el número de divisores positivos de $n$. Para $n = p_1^{a_1} \cdots p_r^{a_r}$, cada divisor $d$ de $n$ tiene la forma $d = p_1^{b_1} \cdots p_r^{b_r}$ con $0 \le b_i \le a_i$. Hay $(a_1+1)$ opciones para $b_1$, $(a_2+1)$ para $b_2$, etc.

La fórmula resultante $\tau(p_1^{a_1} \cdots p_r^{a_r}) = (a_1+1)(a_2+1) \cdots (a_r+1)$ es la base de incontables problemas olímpicos. Ejemplos: $\tau(12) = \tau(2^2 \cdot 3) = 3 \cdot 2 = 6$; los divisores son $1, 2, 3, 4, 6, 12$. $\tau(p^k) = k+1$ para primo $p$.

La función $\tau$ es multiplicativa: si $\gcd(m,n)=1$, cada divisor de $mn$ se escribe de manera única como $d_1 d_2$ con $d_1 \mid m$ y $d_2 \mid n$, así $\tau(mn) = \tau(m)\tau(n)$.

**Promedio de $\tau$.** Una estimación clásica: $\frac{1}{N}\sum_{n=1}^N \tau(n) \approx \ln N$. Esto refleja que un entero típico de tamaño $N$ tiene del orden de $\ln N$ divisores.

La función $\sigma$: suma de divisores

La función $\sigma(n)$ es la suma de todos los divisores positivos de $n$. Para una potencia de primo $p^k$: $\sigma(p^k) = 1 + p + p^2 + \cdots + p^k = \frac{p^{k+1}-1}{p-1}$.

Por multiplicatividad, $\sigma(p_1^{a_1} \cdots p_r^{a_r}) = \frac{p_1^{a_1+1}-1}{p_1-1} \cdot \frac{p_2^{a_2+1}-1}{p_2-1} \cdots \frac{p_r^{a_r+1}-1}{p_r-1}$.

Ejemplo: $\sigma(12) = \sigma(2^2)\sigma(3) = (1+2+4)(1+3) = 7 \cdot 4 = 28$. Verificación: $1+2+3+4+6+12 = 28$.

Números perfectos. Un número $n$ es perfecto si $\sigma(n) = 2n$, es decir, la suma de sus divisores propios es $n$ mismo. Euclides demostró que $2^{p-1}(2^p-1)$ es perfecto cuando $2^p-1$ es primo (primo de Mersenne). Euler demostró la recíproca para números pares: todo número par perfecto tiene esta forma.

La función de Euler $\phi$ revisitada

La función de Euler $\phi(n)$ cuenta los enteros en $\{1, \ldots, n\}$ que son coprimos con $n$. Ya la vimos en relación con el Teorema de Euler ($a^{\phi(n)} \equiv 1 \pmod n$ para $\gcd(a,n)=1$). Ahora la estudiamos como función multiplicativa.

Para primo $p$: $\phi(p) = p-1$. Para $p^k$: entre $1, \ldots, p^k$ los no coprimos con $p^k$ son exactamente los múltiplos de $p$: hay $p^{k-1}$ de ellos, así $\phi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$.

Por multiplicatividad: $\phi(n) = n \prod_{p \mid n}\left(1 - \frac{1}{p}\right)$. Esta es la fórmula del producto de Euler para $\phi$.

Identidad fundamental. $\sum_{d \mid n} \phi(d) = n$. Demostración: las $n$ fracciones $1/n, 2/n, \ldots, n/n$ en su forma reducida $a/d$ con $d \mid n$ y $\gcd(a,d)=1$; hay $\phi(d)$ fracciones con denominador $d$, y la suma sobre todos los $d \mid n$ da $n$.

Caracterización de funciones multiplicativas

Teorema. Si $f$ y $g$ son funciones multiplicativas, entonces la función $h(n) = \sum_{d \mid n} f(d) g(n/d)$ (llamada convolución de Dirichlet de $f$ y $g$, que veremos en la próxima lección) también es multiplicativa.

Esto explica por qué $\sigma$ y $\tau$ son multiplicativas: $\tau = \mathbf{1} * \mathbf{1}$ y $\sigma = \text{id} * \mathbf{1}$ donde $\mathbf{1}(n) = 1$ y $\text{id}(n) = n$ son ambas multiplicativas.

Criterio de multiplicatividad. Una función aritmética $f$ con $f(1)=1$ es multiplicativa si y solo si es "completamente determinada por sus valores en potencias de primos" en el sentido de que $f(p^a q^b) = f(p^a)f(q^b)$ para todo par de primos distintos $p, q$ y todo $a, b \ge 1$.

Aplicación olímpica: números con $\tau(n) = k$

Un problema clásico es: ¿para qué valores de $k$ existe $n$ con exactamente $k$ divisores? La respuesta es todos los $k \ge 1$: basta tomar $n = 2^{k-1}$.

Más interesante: ¿cuántos enteros $n \le 1000$ tienen exactamente 12 divisores? Como $12 = (a_1+1)(a_2+1)\cdots$, las formas posibles de $n$ son: $p^{11}$, $p^5 q$, $p^3 q^2$, $p^3 qr$, $p^2 q^2 r$, $p^2 qrs$, $pqrst$ (con $p < q < r < s < t$ primos). Contando con $n \le 1000$: $2^{11} = 2048 > 1000$ (ninguno del tipo $p^{11}$); $p^5 q$: $2^5 \cdot 3 = 96$, $2^5 \cdot 5 = 160$, etc. El conteo sistemático es parte del ejercicio.

Problema olímpico típico. Si $\tau(n) = \tau(n+1) = 4$ para algún entero $n$, ¿cuáles son las formas posibles de $n$ y $n+1$? Los enteros con 4 divisores son de la forma $p^3$ o $pq$ (primos distintos). La paridad fuerza que uno de ellos sea par, restringiendo fuertemente los casos.