Función \(\mu\) y fórmula de inversión de Möbius

Introducción

En este capítulo vamos a introducir una suma particular. Normalmente hacemos las sumas desde algún valor \(k=1\), hasta cierto valor \(n\). Por ejemplo, si sumamos los números desde \(1\) hasta \(20\) tendremos lo siguiente:

\[\sum_{k = 1}^{20}k = 1 + 2 + 3 + \ldots + 19 + 20 = 210.\]

Pero vamos a descubrir qué pasa si sumamos los números menores a cierto entero \(n\) que son divisores de \(n\). Por ejemplo, si sumamos los números menores o iguales que \(20\) que dividen a \(20\), entonces tendríamos:

\[\sum_{d|20}d = 1 + 2 + 4 +5 + 10 + 20 = 42.\]

Además, veremos una introducción a las funciones aritméticas que tienen la propiedad de que son multiplicativas, esto es, que si tenemos una función \(f\) y dos números \(m\) y \(n\) que son primos relativos se cumple que \(f(mn) = f(m)f(n)\).
También vamos a introducir una función especial, la función \(\mu(n)\) de Möbius. Mostraremos algunas propiedades que nos serán de ayuda para demostrar la fórmula de inversión de Möbius.

Sumas de funciones sobre divisores

En capítulos anteriores, definimos a la función \(\sigma(n)\) para calcular la suma de los divisores de un número , para calcular el número de divisores de un número fue \(\tau(n)\) y la función \(\varphi(n)\) de Euler que calcula cuántos números menores a un entero \(n\) son primos relativos con \(n\). Éstas funciones están definidas para todos los enteros positivos.
Dado que ya construimos lo anterior, en esta sección vamos a presentar la siguiente definición.

Definición 22 (Suma sobre divisores)

Dada una función \(f:\mathbb{Z}^+ \to \mathbb{R}\), podemos construir la suma de sus imágenes bajo los divisores de \(n\), como sigue:

\[F(n)=\sum_{d|n} f(d),\]

donde \(F:\mathbb{Z}^+ \to \mathbb{R}\).

En lo que resta de las notas, nos referiremos a \(F\) como la función suma sobre divisores de \(f\).

Ejemplo 60

Supongamos que tenemos una función \(f\), entonces la suma de sus imágenes bajo los divisores de \(18\) es:

\[F(18) = \sum_{d|18} f(d) = f(1) + f(2) + f(3) + f(6) + f(9) + f(18).\]

Por ejemplo, si \(f(d) = d^2\). Entonces la función \(F\) suma sobre divisores de \(f\) evaluada en \(18\) sería:

\[\begin{align*} F(18) = \sum_{d|18} f(d) &= f(1) + f(2) + f(3) + f(6) + f(9) + f(18) \\ &= 1^2 + 2^2 + 3^2 + 6^2 + 9^2 + 18^2 \\ & \\ &= 1 + 4 + 9 + 36 + 81 + 324 = 455. \end{align*}\]

Quizás parece una operación complicada, sin embargo, hay algunas funciones \(f\) para las que su \(F\) es algo especial, que ya habíamos estudiado.

Ejemplo 61

Si \(f:\mathbb{Z}^+ \to \mathbb{R}\) es la función constante \(f(n)=1\), entonces en \(F(n)\) estamos sumando el número \(1\) tantas veces como cantidad de divisores tiene \(n\). Es decir, la función suma sobre divisores de \(f\) es precisamente \(\tau(n)\).
Cuando \(n=18\), obtenemos lo siguiente:

\[\begin{align*} F(18) = \sum_{d|18} f(d) &= f(1) + f(2) + f(3) + f(6) + f(9) + f(18) \\ &= 1 + 1 + 1 + 1 + 1 + 1 = 6 \\ & \\ &= \tau(18). \end{align*}\]

Ejemplo 62

Si \(f:\mathbb{Z}^+ \to \mathbb{R}\) es la función constante \(f(n)=n\), entonces en \(F(n)\) estamos sumando precisamente todos los divisores de \(n\). Es decir, la función suma sobre divisores de \(f\) es precisamente \(\sigma(n)\).
Cuando \(n=18\), tenemos lo siguiente:

\[\begin{align*} F(18) = \sum_{d|18} f(d) &= f(1) + f(2) + f(3) + f(6) + f(9) + f(18) \\ &= 1 + 2 + 3 + 6 + 9 + 18 = 39 \\ & \\ &= \sigma(18). \end{align*}\]

A partir de la función \(f\) es evidente cómo es que tenemos que calcular la función \(F\). Pero imaginemos que tenemos lo contrario. Pensemos que hay un problema en el que conocemos \(F\) y queremos encontrar \(f\). Por ejemplo, ¿será posible dar una función \(f:\mathbb{Z}^+\to \mathbb{R}\) tal que \(\sum_{d|n} f(d)=\varphi(n)\)?
Este tipo de “preguntas inversas” aparecen en muchos lugares de las matemáticas. En los siguientes ejemplos mostraremos algunos casos.

Ejemplo 63

Supongamos que conocemos \(F\), y sabemos que está definida como:

\[F(n) = f(1) + f(2) + \ldots + f(n).\]

En esta situación no conocemos quién es \(f\), pero podemos hacer lo siguiente para recuperarla:
Si tenemos las ecuaciones:

\[\begin{align*} F(n) &= f(1) + f(2) + \ldots + f(n), \\ & \\ F(n-1) &= f(1) + f(2) + \ldots + f(n-1), \end{align*}\]

y restamos \(F(n)\) menos \(F(n-1)\) obtenemos:

\[f(n) = F(n) - F(n-1).\]

Si suponemos que \(F(n) = \frac{n(n+1)}{2}\), ¿Quién sería \(f\)?
Para obtener \(f\) haríamos lo siguiente:

\[\begin{align*} F(1) &= f(1), & F(1) &=\frac{1(1+1)}{2} = 1, \\ & \\ F(2) &= f(1) + f(2), & F(2) &=\frac{2(2+1)}{2} = 3, \\ & \\ F(3) &= f(1) + f(2) + f(3), & F(3) &=\frac{3(3+1)}{2} = 6, \\ &\vdots & &\vdots \end{align*}\]

Podemos ver que de las igualdades anteriores podemos recuperar \(f\)

\[\begin{align*} f(1) &= 1, \\ & \\ f(2) &= 3 - f(1) = 3 - 1 = 2, \\ & \\ f(3) & = 6 - f(1) - f(2) = 6 - 1 - 2 = 3, \\ &\vdots \end{align*}\]

En general tendríamos que:

\[\begin{align*} f(n) &= F(n) - F(n-1) \\ & \\ &= \frac{n(n+1)}{2} - \frac{(n-1)(n-1+1)}{2} \\ & \\ &= \frac{n^2 + n}{2} - \frac{n^2 - n}{2} \\ & \\ &= \frac{2n}{2} = n. \end{align*}\]

Ejemplo 64

Supongamos que tenemos \(f:\mathbb{R} \to \mathbb{R}\). Otra forma de “sumarla” es integrarla, y podríamos definir \(F\) como:

\[F(x)=\int_{0}^x f(t)dt.\]

Entonces, para recuperar \(f\) tendríamos que derivar \(F\). Aplicando el teorema fundamental del cálculo tendríamos lo siguiente:

\[F'(x) = f(x).\]

Si suponemos que \(F(x) = x^2\), entonces podríamos recuperar \(f\) de la siguiente manera:

\[\begin{align*} F(x) &= \int_{0}^x f(t)dt, \\ & \\ x^2 &= \int_{0}^x f(t)dt. \\ \end{align*}\]

Derivando ambos lados de la ecuación:

\[f(x) = 2x.\]

Como veremos más adelante en esta sección, también para la operación suma sobre divisores existe una manera de “invertirla”. A esto se le conoce como el teorema de inversion de Möbius. Sin embargo, para enunciarlo necesitamos algunas definiciones y propiedades previas.

En la Proposición 12 mostramos que para dos enteros \(m\) y \(n\) tales que \((m,n) = 1\), entonces \(\sigma(mn) = \sigma(m) \cdot \sigma(n)\), en general tenemos la siguiente definición.

Definición 23 (Funciones multiplicativas)

Una función es llamada multiplicativa si cumple que \(f(mn) = f(m)\cdot f(n)\) siempre que \(m\) y \(n\) sean primos relativos positivos.

Se dice que es completamente multiplicativa si \(f(mn) = f(m)\cdot f(n)\) se cumple para cualesquiera \(m\) y \(n\) enteros positivos.

Dada la definición de funciones multiplicativas, podemos pasar a demostrar el siguiente teorema.

Teorema 22

Si \(f\) es una función multiplicativa, entonces la función suma sobre divisores de \(f\), \(F(n)= \sum_{d|n}f(d)\) es también multiplicativa.

Demostración. Para mostrar que \(F\) es una función multiplicativa, tenemos que mostrar que si \(m\) y \(n\) son enteros positivos primos relativos entonces se cumple que \(F(mn) = F(m)\cdot F(n)\).

Asumamos por hipótesis que \((m,n) = 1\), entonces tendríamos que:

\[F(mn) = \sum_{d|mn} f(d).\]

Ahora, como \((m,n) = 1\) cualquier divisor \(d\) de \(mn\) es el producto de un único par de divisores positivos \(d_1\) de \(m\) y \(d_2\) de \(n\), en donde se cumple que \((d_1,d_2) = 1\). Además como \(f\) es multiplicativa tendríamos que \(f(d_1d_2) = f(d_1) \cdot f(d_2)\). Por lo tanto, tendremos lo siguiente:

\[\begin{align*} F(mn) &= \sum_{d|mn} f(d) \\ & \\ &= \sum_{d_1|m,d_2|n}f(d_1d_2) \\ & \\ &= \sum_{d_1|m,d_2|n}f(d_1)\cdot f(d_2) \\ & \\ &= \sum_{d_2|n} \left( \sum_{d_1|m} f(d_1) \right)f(d_2) \\ & \\ &= \sum_{d_2|n}F(m)f(d_2) \\ & \\ &= F(m) \sum_{d_2|n}f(d_2) \\ & \\ &= F(m) \cdot F(n). \end{align*}\]

Por lo tanto, \(F(mn) = F(m)\cdot F(n)\). Así, \(F\) es una función multiplicativa\(.\square\)

Ejemplo 65

Sea \(f\) una función multiplicativa. sea \(F\) su función suma sobre divisores. Verifica que se cumple que

\[F(mn) = F(m)\cdot F(n),\]

cuando \(m=25\) y \(n=8\).

Solución.

Como los divisores de \(25\) son \(1,5,25\), entonces tenemos

\[F(25) = \sum_{d|25}f(d) = f(1) + f(5) + f(25).\]

Por otro lado los divisores de \(8\) son \(1,2,4,8\), entonces

\[F(8) = \sum_{d|8}f(d) = f(1) + f(2) + f(4) + f(8).\]

Como \((25,8) = 1\), sucede que \(25\) y \(8\) no comparten factores en común. Por ello, los divisores de \(25\cdot 8 = 200\) los podemos obtener de la siguiente manera

\[\begin{align*} &5^0\cdot 2^0=1, & &5^1\cdot 2^0=5, & &5^2\cdot 2^0=25, \\ & \\ &5^0\cdot 2^1=2, & &5^1\cdot 2^1=10, & &5^2\cdot 2^1=50, \\ & \\ &5^0\cdot 2^2=4, & &5^1\cdot 2^2=20, & &5^2\cdot 2^2=100, \\ & \\ &5^0\cdot 2^3=8, & &5^1\cdot 2^3=40, & &5^2\cdot 2^3=200. \end{align*}\]

Por lo tanto, tenemos lo siguiente

\[\begin{align*} F(200) &= F(25\cdot 8) = \sum_{d|200}f(d) \\ & \\ &= f(1) + f(2) + f(4) + f(5) + f(8) + f(10) + f(20) + f(25) + f(40)\\ & +f(50) + f(100) + f(200) \\ & \\ &= f(1\cdot 1) + f(2\cdot 1) + f(4\cdot 1) + f(5\cdot 1) + f(8\cdot 1) + f(2\cdot 5) + f(4\cdot 5)\\ & + f(25\cdot 1) + f(8\cdot 5) +f(2\cdot 25) + f(25\cdot 4) + f(25\cdot 8) \\ & \\ &= f(1)\cdot f(1) + f(2)\cdot f(1) + f(4)\cdot f(1) + f(5)\cdot f(1)\\ & + f(8)\cdot f(1)+ f(2)\cdot f(5) + f(4)\cdot f(5) + f(25)\cdot f(1) \\ & + f(8)\cdot f(5) +f(2)\cdot f(25) + f(25)\cdot f(4) + f(25)\cdot f(8) \\ & \\ &= f(1) \left[ f(1) + f(2)+ f(4)+ f(8) \right] + f(5) \left[ f(1)+ f(2)+ f(4)+ f(8) \right]\\ & + f(25) \left[ f(1)+f(2)+f(4)+f(8) \right] \\ & \\ &= \left[ f(1) + f(2)+ f(4)+ f(8) \right] \left[ f(1)+ f(5)+ f(25) \right] \\ & \\ &= F(8) \cdot F(25). \end{align*}\]

Con el Teorema 22 obtenemos otro camino para demostrar la Proposición 12.

Proposición 19

La función \(\sigma(n)\) es multiplicativa.

Demostración. Tenemos que demostrar que para dos enteros positivos \(m\) y \(n\) tales que \((m,n) = 1\), se cumple que:

\[\sigma(mn) = \sigma(m) \cdot \sigma(n).\]

Ya vimos en el Ejemplo 62, que si tomamos \(f(d) = d\) entonces:

\[\sum_{d|n}f(d) = \sigma(n).\]

Entonces por el Teorema 22 basta con probar que la función \(f(d) = d\) es multiplicativa.

Para probar lo anterior tomemos \(m\) y \(n\) enteros positivos tales que \((m,n) = 1\) entonces:

\[f(mn) = mn = f(m) \cdot f(n).\]

Por lo tanto \(f(d)\) es multiplicativa, y podemos concluir que \(\sigma(n)\) también es multiplicativa\(.\square\)

Código para dada una función \(f\), encontrar \(F\)

Primero veamos que podemos definir funciones \(f\) como en el Ejemplo 61 y Ejemplo 62 de la siguiente manera.

La función identidad \(f(n) = n\), que para cualquier valor de \(n\) nos regresa el mismo valor.

def identidad(n):
    return n

Con un ciclo for podemos observar el valor de la función para varios valores de \(n\).

for i in range(1,20,3):
    print(f"f({i}) = {identidad(i)}")

f(1) = 1
f(4) = 4
f(7) = 7
f(10) = 10
f(13) = 13
f(16) = 16
f(19) = 19

La función unitaria \(f(n) = 1\), que para cualquier valor de \(n\) nos regresa como resultado \(1\).

def unos(n):
    return 1

Usemos un ciclo for para observar varios cálculos.

for i in range(1,20,3):
    print(f"f({i}) = {unos(i)}")

f(1) = 1
f(4) = 1
f(7) = 1
f(10) = 1
f(13) = 1
f(16) = 1
f(19) = 1

Ahora lo que queremos es calcular la suma sobre divisores de \(f\), es decir:

\[F(n) = \sum_{d|n}f(n).\]

Para ello creamos el siguiente código.

def F_grande(f):
    def F(n):
        resultado = 0
        for d in range(1,n+1):
            if n % d == 0:
                resultado = resultado + f(d)
        return resultado
    return F

Vamos a calcular la suma sobre divisores de la función identidad. Vamos a utilizar un ciclo for para calcular varios valores. Puedes comprobar el valor de \(F(18)\) es el mismo que en el Ejemplo 62.

sigma = F_grande(identidad)

for i in range(10,21):
    print(f"La suma sobre divisores de la función identidad es: F({i}) = {sigma(i)}")

La suma sobre divisores de la función identidad es: F(10) = 18
La suma sobre divisores de la función identidad es: F(11) = 12
La suma sobre divisores de la función identidad es: F(12) = 28
La suma sobre divisores de la función identidad es: F(13) = 14
La suma sobre divisores de la función identidad es: F(14) = 24
La suma sobre divisores de la función identidad es: F(15) = 24
La suma sobre divisores de la función identidad es: F(16) = 31
La suma sobre divisores de la función identidad es: F(17) = 18
La suma sobre divisores de la función identidad es: F(18) = 39
La suma sobre divisores de la función identidad es: F(19) = 20
La suma sobre divisores de la función identidad es: F(20) = 42

Ahora, vamos a calcular la suma sobre divisores de la función unitaria. Igual que en ejemplo anterior, utilizaremos un ciclo for para observar varios resultados. Puedes comprobar el valor de \(F(18)\) es el mismo que en el Ejemplo 61.

tau=F_grande(unos)

for i in range(10,21):
    print(f"La suma sobre divisores de la función unitaria es: F({i}) = {tau(i)}")

La suma sobre divisores de la función unitaria es: F(10) = 4
La suma sobre divisores de la función unitaria es: F(11) = 2
La suma sobre divisores de la función unitaria es: F(12) = 6
La suma sobre divisores de la función unitaria es: F(13) = 2
La suma sobre divisores de la función unitaria es: F(14) = 4
La suma sobre divisores de la función unitaria es: F(15) = 4
La suma sobre divisores de la función unitaria es: F(16) = 5
La suma sobre divisores de la función unitaria es: F(17) = 2
La suma sobre divisores de la función unitaria es: F(18) = 6
La suma sobre divisores de la función unitaria es: F(19) = 2
La suma sobre divisores de la función unitaria es: F(20) = 6

Definición de la función \(\mu\)

Ahora procederemos a presentar una función que nos será de mucha utilidad para invertir la expresión \(F(n)= \sum_{d|n}f(d)\).

Definición 24 (La función de Möbius)

Sea \(n\) un entero positivo. La función \(\mu(n)\) de Möbius es definida como:

\[\begin{split}\mu(n) = \begin{cases} 1 &\text{ cuando } n=1. \\ (-1)^k &\text{ cuando } n=p_1\cdot p_2 \cdot \ldots \cdot p_k, \text{ en donde } p_i \text{ son primos distintos. } \\ 0 &\text{ cuando } p^2 \mid n \text{ para algún primo } p. \end{cases}\end{split}\]

Ejemplo 66

Calculemos los primeros 10 valores de la función \(\mu(n)\) de Möbius.

\[\begin{align*} &\mu(1) = 1, & &\mu(6) = (-1)^2 = 1 \text{ , ya que } 6 = 2\cdot 3 \\ & \\ &\mu(2) = (-1)^1 = -1, & &\mu(7) = (-1)^1 = -1, \\ & \\ &\mu(3) = (-1)^1 = -1, & &\mu(8) = 0 \text{ , ya que } 2^2 = 4\mid 8, \\ & \\ &\mu(4) = 0 \text{ , ya que } 2^2 = 4\mid 4, & &\mu(9) = 0 \text{ , ya que } 3^2 = 9\mid 9, \\ & \\ &\mu(5) = (-1)^1 = -1, & &\mu(10) = (-1)^2 = 1 \text{ , ya que } 10 = 2\cdot 5. \end{align*}\]

Observación 11

Un entero es llamado libre de cuadrados si no es divisible por el cuadrado de un primo. Así, \(\mu(n) \neq 0\) si y sólo si \(n\) es libre de cuadrados.

Veamos que la función \(\mu(n)\) es multiplicativa.

Teorema 23

Sean \(m\) y \(n\) primos relativos, entonces \(\mu(mn) = \mu(m) \cdot \mu(n)\).

Demostración. Sean \(m\) y \(n\) enteros positivos.

• Caso 1) Si \(m=1\) o \(n=1\).

Si \(m=1\). Por definición tenemos que \(\mu(m) = 1\) y además \(mn = n\), por lo cual

\[\mu(mn) = \mu(n) = 1\cdot \mu(n) = \mu(m) \cdot \mu(n).\]

Si tomáramos \(n = 1\) procederíamos análogamente y obtendríamos el mismo resultado.

• Caso 2) Supongamos que \(m\) o \(n\) es divisible por \(p^2\) para algún primo \(p\).

Sin pérdida de generalidad tomemos que \(p^2|m\). Luego, por definición tenemos que \(\mu(m) = 0\).
Como \(p^2|m\), entonces \(p^2|mn\) y de nuevo por definición \(\mu(mn) = 0\).
Por lo tanto, tenemos que:

\[\mu(mn) = 0 = 0\cdot \mu(n) = \mu(m) \cdot \mu(n).\]

Si tomáramos que \(p^2|n\) procederíamos análogamente y obtendríamos el mismo resultado.

• Caso 3) Supongamos que \(m\) y \(n\) son libres de cuadrados.

Como \(m\) y \(n\) son libres de cuadrados entonces tenemos que \(m = p_1p_2\cdot \ldots \cdot p_r\) y \(n = q_1q_2\cdot \ldots \cdot q_s\) en donde cada uno de los \(p_r\) y \(p_s\) son primos distintos, esto se cumple ya que \((m,n) = 1\).
Por un lado, tendríamos por definición que \(\mu(m) = (-1)^r\) y \(\mu(n) = (-1)^s\).
Por otro lado tenemos \(mn = p_1p_2\cdot \ldots \cdot p_rq_1q_2\cdot \ldots \cdot q_s\) por lo cual \(\mu(mn) = (-1)^{r+s}\), entonces:

\[\mu(mn) = (-1)^{r+s} = (-1)^r (-1)^s = \mu(m) \cdot \mu(n).\]

Entonces \(\mu(mn) = \mu(m) \cdot \mu(n)\) se cumple en cada uno de los casos y por lo tanto concluimos que la función \(\mu\) es multiplicativa. \(\square\)

Ejemplo 67

Determina si \(\mu(mr) = \mu(m) \cdot \mu(r)\), en donde \(m=15\) y \(r = 28\).

Solución.

Como \(m = 15 = 3\cdot 5\), entonces \(\mu(m) = (-1)^2 = 1\), por ser producto de primos distintos.

Luego, tenemos que \(r = 28 = 2^2 \cdot 7\), entonces \(\mu(r) = 0\) ya que \(2^2 \mid 28\).

Por otro lado, tenemos que \(mr = 15 \cdot 28 = 3\cdot 5 \cdot 2^2 \cdot 7\), entonces \(\mu(mr) = 0\) ya que \(2^2 \mid 15\cdot 28\).

Por lo tanto, \(\mu(mr) = 0 = 1\cdot 0 = \mu(m) \cdot \mu(r). \square\)

Lema 8

Sea \(F(n) = \sum_{d|n}\mu(d)\). Entonces \(F(n) = 0\) cuando \(n = p^a\) con \(a \ge 1\).

Demostración. Desarrollemos la siguiente suma:

\[\begin{align*} F(n) &= F(p^a) \\ & \\ &= \sum_{d|p^a} \mu(d) \\ & \\ &= \sum_{i=0}^{a} \mu(p^i) \\ & \\ &= \mu(1) + \mu(p) + \mu(p^2) + \ldots + \mu(p^a) \\ & \\ &= 1 + (-1) + 0 + \ldots + 0 = 0. \square \end{align*}\]

Fórmula de inversión de Möbius

En esta sección vamos a demostrar la fórmula de inversión de Möbius. Para ello necesitamos algunos resultados previos que iremos desarrollando.

Definición 25 (Producto de convolución de Dirichlet)

Sean \(f\) y \(g\) dos funciones aritméticas. Definimos su producto de convolución de Dirichlet \(f\star g\) como sigue:

\[(f\star g)(n)=\sum_{d|n} f(d)g\left( \frac{n}{d} \right).\]

Observación 12

Veamos cómo se comporta esta suma cuando tomamos \(n=18\).

\[\begin{align*} (f\star g)(18) &=\sum_{d|18} f(d)g\left( \frac{18}{d} \right) \\ & \\ &= f(1)g(18) + f(2)g(9) + f(3)g(6) + f(6)g(3) + f(9)g(2) + f(18)g(1) \\ & \\ &= \sum_{a,b|ab=18} f(a)g(b). \end{align*}\]

Lo anterior indica que las siguientes dos descripciones generan los mismos conjuntos.

\[\left\{ \left( d,\frac{n}{d} \right) \text{ tal que } d|n \right\} = \left\{(1,18) , (2,9) , (3,6) , (6,3) , (9,2) , (18,1) \right\}.\]

\[ \left\{ (a,b) \text{ tal que } ab = n \right\} = \{(1,18) , (2,9) , (3,6) , (6,3) , (9,2) , (18,1) \}.\]

Vamos a ver que la Observación 12 se puede generalizar.

Proposición 20

Para cualesquiera dos funciones aritméticas \(f\) y \(g\) se cumple

\[(f\star g)(n)= \sum_{d|n}f(d)g\left( \frac{n}{d} \right) = \sum_{a,b: ab=n}f(a)g(b).\]

Demostración. Para probar lo anterior vamos a demostrar que,

\[\left\{ \left( d,\frac{n}{d} \right) \text{ tal que } d|n \right\} = \left\{ (a,b) \text{ tal que } ab = n \right\}.\]

• \(\left\{ \left( d,\frac{n}{d} \right) \text{ tal que } d|n \right\} \subseteq \left\{ (a,b) \text{ tal que } ab = n \right\}\).

Tomemos un elemento \(x \in \left\{ \left( d,\frac{n}{d} \right) \text{ tal que } d|n \right\}\), entonces \(x = (d,\frac{n}{d})\). Como tenemos que \(d|n\) por definición tenemos que \(n = da\) para algún entero positivo \(a\), de lo anterior obtenemos lo siguiente \(\frac{n}{d} = a\). Entonces tenemos que \(x = (d,\frac{n}{d}) = (d,a)\) en dónde \(da = n\). Por lo tanto \(x \in \left\{ (a,b) \text{ tal que } ab = n \right\}\).

• \(\left\{ \left( d,\frac{n}{d} \right) \text{ tal que } d|n \right\} \supseteq \left\{ (a,b) \text{ tal que } ab = n \right\}\).

Sea \(x \in \left\{ (a,b) \text{ tal que } ab = n \right\}\), entonces \(x = (a,b)\). Como tenemos que \(ab = n\) esto quiere decir que \(a|n\), además \(b = \frac{n}{a}\). Entonces tenemos que \(x = (a,b) = (a, \frac{n}{a})\) y además \(a|n\). Por lo tanto \(x \in \left\{ \left( d,\frac{n}{d} \right) \text{ tal que } d|n \right\}. \square\)

Proposición 21 (Asociatividad)

Sean \(f\), \(g\) y \(h\) funciones aritméticas, entonces

\[(f\star g)\star h= \sum_{abc=n} f(a) g(b) h(c)= f\star (g\star h).\]

Demostración. Sean \(f\), \(g\) y \(h\) funciones aritméticas. Para probar la ley de la asociatividad debemos probar que \(f\star (g\star h) = (f\star g)\star h\).
Comencemos por el lado izquierdo de la igualdad y hagamos \(u = g \star h\), entonces tenemos lo siguiente:

\[\begin{align*} \left( f\star (g\star h) \right)(n) = (f\star u)(n) &= \sum_{a|n}f(a)u\left( \frac{n}{a} \right) = \sum_{ad=n}f(a)u(d) \\ & \\ &= \sum_{ad=n}f(a) (g \star h)(d) = \sum_{ad=n}f(a) \left( \sum_{b|d}g(b)h\left( \frac{d}{b} \right) \right) \\ & \\ &= \sum_{ad=n}f(a) \left( \sum_{bc=d}g(b)h(c) \right) \\ & \\ &= \sum_{abc=n}f(a)g(b)h(c). \end{align*}\]

Similarmente, si hacemos que \(v = f \star g\), entonces tenemos lo siguiente:

\[\begin{align*} \left( (f \star g) \star h \right) (n) = (v\star h)(n) &= \sum_{d|n}u(d)h\left( \frac{n}{d} \right) = \sum_{dc=n}v(d)h(c) \\ & \\ &= \sum_{dc=n}(f \star g)(d)h(c) = \sum_{dc=n} \left( \sum_{a|d}f(a)g \left( \frac{d}{a} \right) \right) h(c) \\ & \\ &= \sum_{dc=n} \left( \sum_{ab=d}f(a)g(b) \right) h(c) \\ & \\ &= \sum_{abc=n}f(a)g(b)h(c). \end{align*}\]

Por lo tanto, se cumple que \( (f\star g)\star h = f\star (g\star h). \square\)

Dejaremos como ejercicio demostrar que el producto de convolución de Dirichlet es conmutativo.

Para la siguiente parte de esta sección, vamos a definir las siguientes funciones.

Definición 26 (\(u\) y \(e\))

Definimos:

• \(u(n)=1\) para todo \(n\).

• \(e(n)=\begin{cases} 1 &\text{ si } n=1, \\ 0 &\text{ si } n>1. \end{cases}\)

Ahora, vamos a demostrar dos proposiciones que nos ayudarán para demostrar la fórmula de inversión de Möbius.

Proposición 22

Dada la Definición 26 tenemos lo siguiente. Para cualquier función aritmética \(f\) se cumplen que:

1. \(f\star e = f\).

2. \(F(n)= \sum_{d|n}f(d) = (f\star u)(n)\).

Demostración. \(1\).

Veamos cómo se desarrolla la convolución de \(f\star e\). Además, sabemos que sin importar cuantos divisores tenga \(n\), la única forma en que \(\frac{n}{d} = 1\) es que \(d=n\).
Supongamos que \(n\) tiene \(d_1,d_2,\ldots,d_m\) divisores en donde \(d_m = n\), entonces tenemos lo siguiente

\[\begin{align*} \left( f\star e \right)(n) &= \sum_{d|n}f(d)e\left( \frac{n}{d} \right) \\ & \\ &= f(d_1)e\left( \frac{n}{d_1} \right) + f(d_2)e\left( \frac{n}{d_2} \right) + f(d_3)e\left( \frac{n}{d_3} \right) + \ldots + f(d_m)e\left( \frac{n}{d_m} \right) \\ & \\ &= f(d_1) \cdot 0 + f(d_2)\cdot 0 + f(d_3)\cdot 0 + \ldots + f(n)e\left( \frac{n}{n} \right) \\ & \\ &= f(n)e(1) = f(n). \square \end{align*}\]

Demostración. \(2\).

Empecemos viendo qué pasa con el lado derecho de la igualdad y supongamos que \(n\) tiene \(d_1,d_2,\ldots,d_m\) divisores. Además, por definición tenemos que \(u(n) = 1\) para todo valor de \(n\), entonces tenemos lo siguiente

\[\begin{align*} (f\star u)(n) &= \sum_{d|n}f(d)u \left( \frac{n}{d} \right) \\ & \\ &= f(d_1)u\left(\frac{n}{d_1} \right) + f(d_2)u\left(\frac{n}{d_2} \right) + f(d_3)u\left(\frac{n}{d_3} \right) + \ldots + f(d_m)u\left(\frac{n}{d_m} \right) \\ & \\ &=f(d_1) + f(d_2) + f(d_3) + \dots + f(d_m) \\ & \\ &=\sum_{d|n}f(d) = F(n). \square \end{align*}\]

Podemos decir entonces que la función \(e\) es el neutro para la convolución de Dirichlet.

Proposición 23

La inversa de \(u\) es \(\mu\). En otras palabras, \(u\star \mu =e\).

Demostración. Veamos los siguientes dos casos, el primero cuando \(n=1\) y el segundo cuando \(n>1\) y tenemos su descomposición canónica, es decir, \(n = p_1^{\alpha_1}p_2^{\alpha_2} \ldots p_k^{\alpha_k}\).

• Caso 1) Cuando \(n = 1\).

Entonces tenemos lo siguiente:

\[\begin{align*} \left( u\star \mu \right)(n) &= \sum_{d|1} u(d) \mu \left( \frac{1}{d} \right) \\ & \\ &= u(1) \mu (1) \\ & \\ &= 1 \cdot 1 = 1. \end{align*}\]

• Caso 2) Cuando \(n >1\).

Supongamos que \(n = p_1^{\alpha_1}p_2^{\alpha_2} \ldots p_k^{\alpha_k}\).
Recordemos que ya probamos en la Proposición 22 que para cualquier función aritmética se cumple que \(F(n)=(f\star u)(n)\), también vimos que la función aritmética \(\mu\) es multiplicativa, entonces podemos aplicar el Teorema 22 y el Lema 8 y tendríamos lo siguiente:

\[\begin{align*} \left( u\star \mu \right)(n) &= \left( \mu \star u \right)(n) = F(n) \\ &\\ &= F(p_1^{\alpha_1}p_2^{\alpha_2} \ldots p_k^{\alpha_k}) \\ & \\ &= F(p_1^{\alpha_1}) \cdot F(p_2^{\alpha_2}) \cdot \ldots \cdot F(p_k^{\alpha_k}) \\ & \\ &= \sum_{d_1|p_1^{\alpha_1}}\mu(d_1) \cdot \sum_{d_2|p_2^{\alpha_2}}\mu(d_2) \cdot \ldots \cdot \sum_{d_k|p_k^{\alpha_k}}\mu(d_k) \\ & \\ &= \prod_{i=1}^{k}\left( \sum_{j = 0}^{\alpha_i}\mu(p_i^j) \right) = \prod_{i=0}^{k}(0) = 0. \square \end{align*}\]

Teorema 24 (Fórmula de inversión de Möbius)

Sea \(f:\mathbb{Z}^+\to \mathbb{R}\) una función multiplicativa y \(F:\mathbb{Z}^+ \to \mathbb{R}\) su función suma sobre divisores. Entonces, se puede obtener \(f\) a partir de \(F\) mediante la siguiente suma,

\[f(n)=\sum_{d|n} \mu(d)F\left( \frac{n}{d} \right).\]

Demostración. Como vimos en la Proposición 22 tenemos que,

\[F=f\star u.\]

Si aplicamos la convolución con \(\mu\) en ambos de la igualdad, tenemos que:

\[\begin{align*} (F \star \mu)(n) &= ((f \star u) \star \mu)(n), \\ & \\ (\mu \star F)(n) &= (f \star (u \star \mu))(n), \\ & \\ (\mu \star F)(n) &= (f \star e)(n), \\ & \\ \sum_{d|n}\mu(d)F\left( \frac{n}{d} \right) &= f(n). \\ \end{align*}\]

Por lo tanto, se cumple que \(f(n)=\sum_{d|n} \mu(d)F( \frac{n}{d}). \square\)

Un par de ejemplos de inversión de Möbius

Corolario 6

Sea \(f\) una función aritmética con su suma sobre divisores \(F = \sum_{d|n}f(d)\). Entonces si \(F\) es multiplicativa, \(f\) es también multiplicativa.

Demostración. Supongamos que \(m\) y \(n\) son números enteros positivos primos relativos. Queremos mostrar que \(f(mn) = f(m)f(n)\).
Tengamos en cuenta la siguiente observación: Si \(d\) es un divisor de \(mn\), entonces \(d=d_1d_2\) en donde \(d_1|m\) y \(d_2|n\), además \((d_1,d_2) = 1\). Usaremos el Teorema 24 y el hecho de que la función \(\mu\) y \(F\) son multiplicativas, entonces tenemos lo siguiente

\[\begin{align*} f(mn) &= \sum_{d|mn}\mu(d)F\left( \frac{mn}{d} \right) \\ & \\ &=\sum_{d_1|m , d_2|n} \mu(d_1d_2)F\left( \frac{mn}{d_1d_2} \right) \\ & \\ &= \sum_{d_1|m , d_2|n} \mu(d_1) \mu(d_2)F\left( \frac{m}{d_1} \right)F\left( \frac{n}{d_2} \right) \\ & \\ &= \sum_{d_1|m} \mu(d_1)F\left( \frac{m}{d_1} \right) \cdot \sum_{d_2|n} \mu(d_2)F\left( \frac{n}{d_2} \right) \\ & \\ &= f(m) f(n). \square \end{align*}\]

Ejemplo 68

Demuestra que

\[\sum_{d|n} \varphi(d)=n.\]

Solución.

Veamos que el conjunto de los enteros positivos de \(1\) hasta \(n\) se puede separar en conjuntos disjuntos con la siguiente idea.
Si tomamos un entero \(0 < m \le n\), lo pondremos en el conjunto \(C_d\) si se cumple que \((m,n) = d\). Luego, por la Proposición 8 tenemos que \((\frac{m}{d},\frac{n}{d}) = 1\). Por lo cual, el número de enteros que hay en cada conjunto \(C_d\) es el número de enteros positivos que no son mayores a \(\frac{n}{d}\) y que son primos relativos con el entero \(\frac{n}{d}\). Como cada entero desde \(1\) hasta \(n\) está exactamente en un conjunto, entonces \(n\) es la suma de todos los elementos en esos conjuntos disjuntos, y podemos escribir que

\[n = \sum_{d|n} \varphi\left( \frac{n}{d} \right).\]

Como \(d\) recorre por todos lo enteros positivos que dividen a \(n\) y la expresión \(\frac{n}{d}\) también recorre todos esos divisores, tenemos que:

\[n = \sum_{d|n} \varphi\left( \frac{n}{d} \right) = \sum_{d|n} \varphi(d). \square\]

Veamos otra demostración de que la función \(\varphi\) de Euler es multiplicativa.

Ejemplo 69

Demuestra que la función \(\varphi(n)\) es multiplicativa.

Solución.

Sabemos que por el Ejemplo 68, \(\sum_{d|n} \varphi(d)=n\). Entonces tenemos que la suma sobre divisores de la función \(\varphi(n)\) es igual a \(n\), es decir que \(F(n) = n\).

Luego tenemos que si \(m\) y \(n\) son enteros positivos tales que \((m,n) = 1\), se cumple que:

\[F(mn) = mn = F(m) \cdot F(n).\]

Esto quiere decir que \(F\) es multiplicativa. Entonces usando el Corolario 6 podemos concluir que \(\varphi(n)\) es también multiplicativa\(.\square\)

Código para calcular la función \(\mu\) y para hacer inversión de Möbius

Vamos a crear un código que nos regrese el valor de la función \(\mu(n)\).

def mu(n):
    if n==1:
        return 1
    mu = 1
    for i in range(2,n+1):
        if n % i == 0:
            contador = 0
            while n % i == 0:
                n //= i 
                contador += 1
            if contador > 1:
                return 0 
            mu = -mu
    return mu 

Vamos a utilizar un ciclo for para observar varios resultados de la función \(\mu(n)\).

for i in range(1,11):
    print(f"mu({i})= {mu(i)}")

mu(1)= 1
mu(2)= -1
mu(3)= -1
mu(4)= 0
mu(5)= -1
mu(6)= 1
mu(7)= -1
mu(8)= 0
mu(9)= 0
mu(10)= 1

Ahora, veamos un código para calcular la fórmula de inversión de Möbius.

def inversion_m(F):
    def f(n):
        resultado = 0
        for d in range(1, n+1):
            if n % d ==0:
                resultado = resultado + F(d)*mu(n//d)
        return resultado
    return f 

El siguiente ejemplo de código nos mostrará que si tenemos que \(F(n) = \sigma(n)\),es decir,

\[\sigma(n) = F(n) = \sum_{d|n} f(d).\]

Entonces usando el código de la fórmula de inversión de Möbius, el calculo que obtendremos es:

\[\sum_{d|n}\sigma(d) \mu \left( \frac{n}{d} \right) = n = f(n).\]

Verifiquemos lo anterior con nuestro código.
Usemos el código que creamos en el capítulo de número y suma de divisores para calcular la suma de los divisores de un número.

def fact_primos_exponentes(n):
    a = n
    lst_descomp = []
    for i in range(2, a+1):
        while a % i == 0:
            lst_descomp.append(i)
            a //= i
        if a == 1:
            break
    lst_primos = set(lst_descomp)
    lst_exp = []
    for i in lst_primos:
        exp = lst_descomp.count(i)
        lst_exp.append(exp)
    return [list(lst_primos), lst_exp]

def suma_divisores(n):
    b = n 
    lst_prim_exp = fact_primos_exponentes(b)
    lst_1 = [i + 1 for i in lst_prim_exp[1]]
    suma = 1
    for i in range(len(lst_prim_exp[0])):
        a = ((lst_prim_exp[0][i])**(lst_1[i])-1)//(lst_prim_exp[0][i] -1)
        suma *= a
    return suma 

Con un ciclo for vamos a observar distintos valores, obteniendo que \(f\) es la función identidad.

identidad = inversion_m(suma_divisores)

for i in range(1,31,3):
    print(f"Usando la fórmula de inversión de Möbius obtenemos: f({i})= {identidad(i)}")

Usando la fórmula de inversión de Möbius obtenemos: f(1)= 1
Usando la fórmula de inversión de Möbius obtenemos: f(4)= 4
Usando la fórmula de inversión de Möbius obtenemos: f(7)= 7
Usando la fórmula de inversión de Möbius obtenemos: f(10)= 10
Usando la fórmula de inversión de Möbius obtenemos: f(13)= 13
Usando la fórmula de inversión de Möbius obtenemos: f(16)= 16
Usando la fórmula de inversión de Möbius obtenemos: f(19)= 19
Usando la fórmula de inversión de Möbius obtenemos: f(22)= 22
Usando la fórmula de inversión de Möbius obtenemos: f(25)= 25
Usando la fórmula de inversión de Möbius obtenemos: f(28)= 28

Explicación del código

En este capítulo construimos varios códigos, aunque algunos sean sencillos explicaremos cada uno de ellos.

Veamos el código de la función identidad.

def identidad(n):
    return n

1. Definimos una función llamada «identidad» la cual recibe como argumento un número entero positivo. Esta función simplemente nos regresa el mismo valor que ingresamos como argumento.

Veamos el código de la función unitaria.

def unos(n):
    return 1

1. Definimos una función llamada «unos» la cual recibe como argumento un valor entero positivo. La función simplemente nos regresa el valor de \(1\) para cualquier valor entero que le demos como argumento.

Veamos el código para calcular la suma sobre divisores \(F(n)\).

def F_grande(f):
    def F(n):
        resultado = 0
        for d in range(1,n+1):
            if n % d == 0:
                resultado = resultado + f(d)
        return resultado
    return F 

1. Definimos una función llamada «F_grande» que recibe como argumento una función. Por ejemplo, las funciones «identidad» y «unos» que creamos anteriormente.

def F_grande(f):

2. Dentro de la función definimos otra función llamada «F» que recibe como argumento un entero positivo \(n\). Dentro de la función se inicia una variable llamada «resultado» con valor inicial de cero. Luego, empezamos un ciclo for que toma un valor \(d\) dentro del rango de \(1\) a \(n+1\). Con un condicional if revisamos si el residuo al dividir \(n\) entre \(d\) es igual a cero, si la condición es verdadera a la variable «resultado» se le suma el valor que ya tenía definido mas el valor de la función \(f(d)\). El ciclo for recorre todos los números que son divisores del entero \(n\), esto simula la suma sobre los divisores de \(f\). Cuando termina de recorrer todos los valores la función nos regresa el valor de la variable «resultado.»

    def F(n):
        resultado = 0
        for d in range(1,n+1):
            if n % d == 0:
                resultado = resultado + f(d)
        return resultado

3. Finalmente, lo que regresa la función «F_grande» es el valor de la función interior «F», el cual es la suma sobre los divisores evaluados en la función «f».

    return F 

Veamos el código que hicimos para calcular los valores de la función \(\mu(n)\).

def mu(n):
    if n==1:
        return 1
    mu = 1
    for i in range(2,n+1):
        if n % i == 0:
            contador = 0
            while n % i == 0:
                n //= i 
                contador += 1
            if contador > 1:
                return 0 
            mu = -mu
    return mu 

1. Definimos una función llamada «mu» que recibe como argumento un entero positivo \(n\).

def mu(n):

2. Iniciamos con un condicional if que verifica si el valor de \(n = 1\), ya que \(\mu(1) = 1\). Si \(n = 1\), el código nos regresa el valor de \(1\) y se termina.

    if n==1:
        return 1

3. Si la condición anterior no es verdadera pasamos a la siguiente parte del código.
   Iniciamos una variable llamada «mu» con valor inicial de \(1\). Luego, empezamos un ciclo for el cual recorre con la variable «i» los valores de \(2\) hasta \(n\). Un condicional if verifica el residuo al dividir \(n\) entre el valor \(i\). Si el residuo es igual a cero entonces se ejecuta el código dentro del condicional. Se crea una variable llamada «contador» con un valor inicial de cero. Iniciamos un ciclo while el cual tiene como condición que mientras el residuo de \(n\) dividido entre \(i\) sea igual a cero va a actualizar el valor de \(n\) dividiéndolo entre \(i\) y va a aumentar en una unidad el valor del contador. Luego, cuando la condición del ciclo while sea falsa el código sigue con un condicional if el cual verifica el valor de la variable «contador,» si la variable «contador» tiene un valor más grande que uno quiere decir que el número \(n\) es dividido por \(i^2\) y entonces la función nos regresa un valor de cero terminando el código.
   Si el valor de la variable «contador» es igual a \(1\) para todos los valores que se evalúan dentro del ciclo for, entonces el código salta el condicional if en cada uno de esos casos. Sin embargo el valor de la variable «mu» se multiplica por \(-1\) en cada iteración. Lo anterior simula el caso cuando \(n\) tiene primos diferentes en su descomposición.
   Finalmente, obtenemos el valor de la función \(\mu(n)\) para cualquier valor de \(n\).

    mu = 1
    for i in range(2,n+1):
        if n % i == 0:
            contador = 0
            while n % i == 0:
                n //= i 
                contador += 1
            if contador > 1:
                return 0 
            mu = -mu
    return mu 

Veamos el código para la fórmula de inversión de Möbius.

def inversion_m(F):
    def f(n):
        resultado = 0
        for d in range(1, n+1):
            if n % d ==0:
                resultado = resultado + F(d)*mu(n//d)
        return resultado
    return f 

1. Definimos una función llamada «inversion_m» la cual recibe como argumento una función.

def inversion_m(F):

2. Dentro de la función anterior definimos otra función llamada «f» que recibe como argumento un entero positivo \(n\). Iniciamos una variable llamada «resultado» con un valor inicial igual a cero. Creamos un ciclo for que va recorrer los valores de \(1\) hasta \(n\). Dentro del ciclo ponemos un condicional if el cual tiene como condición que si el residuo cuando se divide \(n\) entre \(d\) es igual a cero, la variable «resultado» se actualiza tomando el valor de la misma variable mas el valor de \(F(d)\) multiplicado por \(\mu(d)\), siguiendo la fórmula del Teorema 24. Finalmente nos regresa el valor de la variable «resultado».

    def f(n):
        resultado = 0
        for d in range(1, n+1):
            if n % d ==0:
                resultado = resultado + F(d)*mu(n//d)
        return resultado

3. Al final, lo que obtenemos de la función «inversion_m» es el valor de la función «f». Es decir, la suma de la fórmula del Teorema 24.

    return f 

Ejercicios de práctica

1. Demuestra que la función \(\tau(n)\) es multiplicativa usando las ideas de funciones multiplicativas y la función suma sobre divisores.

2. Si tomamos \(f(d) = \frac{1}{d}\), prueba que \(\sum_{d|n}f(d) = \frac{\sigma(n)}{n}\).

3. Demuestra si \(f\) y \(g\) son funciones aritméticas, entonces su producto de convolución de Dirichlet es conmutativo es decir: \(f\star g = g\star f\).

4. Prueba que si \(f\) y \(g\) son funciones multiplicativas, entonces su producto de convolución de Dirichlet \(f\star g\) es también multiplicativo.