Fórmula de inversión de Möbius

En matemáticas , la fórmula clásica de inversión de Möbius es una relación entre pares de funciones aritméticas , cada una definida a partir de la otra mediante sumas de divisores . Fue introducida en la teoría de números en 1832 por August Ferdinand Möbius . ^{[ 1 ]}

Una gran generalización de esta fórmula se aplica a la suma sobre un conjunto parcialmente ordenado localmente finito arbitrario , con la fórmula clásica de Möbius aplicada al conjunto de los números naturales ordenados por divisibilidad: véase álgebra de incidencia .

La versión clásica establece que si g y f son funciones aritméticas que satisfacen

${\displaystyle g(n)=\sum _{d\mid n}f(d)\quad {\text{para todo entero }}n\geq 1}$

entonces

${\displaystyle f(n)=\sum _{d\mid n}\mu (d)\,g\!\left({\frac {n}{d}}\right)\quad {\text{para todo entero }}n\geq 1}$

donde μ es la función de Möbius y las sumas se extienden sobre todos los divisores positivos d de n (indicados por${\displaystyle d\mid n}$(en las fórmulas anteriores). En efecto, la función original f ( n ) puede determinarse a partir de g ( n ) mediante la fórmula de inversión. Se dice que ambas secuencias son transformadas de Möbius una de la otra.

La fórmula también es correcta si f y g son funciones de los enteros positivos en algún grupo abeliano (visto como un módulo Z ) .

En el lenguaje de las convoluciones de Dirichlet , la primera fórmula se puede escribir como

${\displaystyle g={\mathit {1}}*f}$

donde ∗ denota la convolución de Dirichlet y 1 es la función constante 1 ( n ) = 1 . La segunda fórmula se escribe entonces como

${\displaystyle f=\mu *g.}$

En el artículo sobre funciones multiplicativas se ofrecen muchos ejemplos específicos .

El teorema se deduce porque ∗ es (conmutativa y) asociativa, y 1 ∗ μ = ε , donde ε es la función identidad para la convolución de Dirichlet, que toma valores ε (1) = 1 , ε ( n ) = 0 para todo n > 1 . Por lo tanto

${\displaystyle \mu *g=\mu *({\mathit {1}}*f)=(\mu *{\mathit {1}})*f=\varepsilon *f=f}$.

Reemplazar${\displaystyle f,g}$por${\displaystyle \ln f,\ln g}$, obtenemos la versión del producto de la fórmula de inversión de Möbius:

${\displaystyle g(n)=\prod _{d|n}f(d)\iff f(n)=\prod _{d|n}g\left({\frac {n}{d}}\right)^{\mu (d)},\forall n\geq 1.}$

Dejar

${\displaystyle a_{n}=\sum _{d\mid n}b_{d}}$

de modo que

${\displaystyle b_{n}=\sum _{d\mid n}\mu \left({\frac {n}{d}}\right)a_{d}}$

es su transformada. Las transformadas están relacionadas mediante series: la serie de Lambert

${\displaystyle \sum _{n=1}^{\infty }a_{n}x^{n}=\sum _{n=1}^{\infty }b_{n}{\frac {x^{n}}{1-x^{n}}}}$

y la serie de Dirichlet :

${\displaystyle \sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}=\zeta (s)\sum _{n=1}^{\infty }{\frac {b_{n}}{n^{s}}}}$

donde ζ ( s ) es la función zeta de Riemann .

Dada una función aritmética, se puede generar una secuencia biinfinita de otras funciones aritméticas aplicando repetidamente la primera sumatoria.

Por ejemplo, si se parte de la función totiente de Euler φ y se aplica repetidamente el proceso de transformación, se obtiene:

1. φ la función totiente
2. φ ∗ 1 = I , donde I ( n ) = n es la función identidad
3. I ∗ 1 = σ ₁ = σ , la función divisora

Si la función inicial es la propia función de Möbius, la lista de funciones es:

1. μ , la función de Möbius
2. μ ∗ 1 = ε donde$${\displaystyle \varepsilon (n)={\begin{cases}1,&{\text{si }}n=1\\0,&{\text{si }}n>1\end{cases}}}$$es la función de la unidad
3. ε ∗ 1 = 1 , la función constante
4. 1 ∗ 1 = σ ₀ = d = τ , donde d = τ es el número de divisores de n , (ver función divisor ).

Ambas listas de funciones se extienden infinitamente en ambas direcciones. La fórmula de inversión de Möbius permite recorrer estas listas en sentido inverso.

Como ejemplo, la secuencia que comienza con φ es:

${\displaystyle f_{n}={\begin{cases}\underbrace {\mu *\ldots *\mu } _{-n{\text{ factores}}}*\varphi &{\text{si }}n<0\\[8px]\varphi &{\text{si }}n=0\\[8px]\varphi *\underbrace {{\mathit {1}}*\ldots *{\mathit {1}}} _{n{\text{ factores}}}&{\text{si }}n>0\end{cases}}}$

Las secuencias generadas se pueden entender quizás más fácilmente considerando la serie de Dirichlet correspondiente : cada aplicación repetida de la transformación corresponde a una multiplicación por la función zeta de Riemann .

Una fórmula de inversión relacionada, más útil en combinatoria, es la siguiente: supongamos que F ( x ) y G ( x ) son funciones de valores complejos definidas en el intervalo [ 1, ∞) tales que

${\displaystyle G(x)=\sum _{1\leq n\leq x}F\left({\frac {x}{n}}\right)\quad {\mbox{ para todo }}x\geq 1}$

entonces

${\displaystyle F(x)=\sum _{1\leq n\leq x}\mu (n)G\left({\frac {x}{n}}\right)\quad {\mbox{ para todo }}x\geq 1.}$

Aquí las sumas se extienden sobre todos los enteros positivos n que son menores o iguales a x .

Esto a su vez es un caso especial de una forma más general. Si α ( n ) es una función aritmética que posee una inversa de Dirichlet α ⁻¹ ( n ) , entonces si se define

${\displaystyle G(x)=\sum _{1\leq n\leq x}\alpha (n)F\left({\frac {x}{n}}\right)\quad {\mbox{ para todo }}x\geq 1}$

entonces

${\displaystyle F(x)=\sum _{1\leq n\leq x}\alpha ^{-1}(n)G\left({\frac {x}{n}}\right)\quad {\mbox{ for all }}x\geq 1.}$

La fórmula anterior surge en el caso especial de la función constante α ( n ) = 1 , cuya inversa de Dirichlet es α ⁻¹ ( n ) = μ ( n ) .

Una aplicación particular de la primera de estas extensiones surge si tenemos funciones (de valores complejos) f ( n ) y g ( n ) definidas en los enteros positivos, con

${\displaystyle g(n)=\sum _{1\leq m\leq n}f\left(\left\lfloor {\frac {n}{m}}\right\rfloor \right)\quad {\mbox{ for all }}n\geq 1.}$

Al definir F ( x ) = f (⌊ x ⌋) y G ( x ) = g (⌊ x ⌋) , deducimos que

${\displaystyle f(n)=\sum _{1\leq m\leq n}\mu (m)g\left(\left\lfloor {\frac {n}{m}}\right\rfloor \right)\quad {\mbox{ for all }}n\geq 1.}$

Un ejemplo sencillo del uso de esta fórmula es contar el número de fracciones reducidas 0 < a / b < 1 , donde a y b son coprimos y b ≤ n . Si llamamos f ( n ) a este número, entonces g ( n ) es el número total de fracciones 0 < a / b < 1 con b ≤ n , donde a y b no son necesariamente coprimos. (Esto se debe a que toda fracción ⁠ a / b ⁠ con mcd( a , b ) = d y b ≤ n se puede reducir a la fracción ⁠ a / d / b / d ⁠ con ⁠ b / d ⁠ ≤ ⁠ n / d ⁠ , y viceversa). Aquí es sencillo determinar g ( n ) = ⁠ n ( n − 1) / 2 ⁠ , pero f ( n ) es más difícil de calcular.

Otra fórmula de inversión es (donde suponemos que las series involucradas son absolutamente convergentes ):

${\displaystyle g(x)=\sum _{m=1}^{\infty }{\frac {f(mx)}{m^{s}}}\quad {\mbox{ for all }}x\geq 1\quad \Longleftrightarrow \quad f(x)=\sum _{m=1}^{\infty }\mu (m){\frac {g(mx)}{m^{s}}}\quad {\mbox{ for all }}x\geq 1.}$

Como se indicó anteriormente, esto se generaliza al caso en que α ( n ) es una función aritmética que posee una inversa de Dirichlet α ⁻¹ ( n ) :

${\displaystyle g(x)=\sum _{m=1}^{\infty }\alpha (m){\frac {f(mx)}{m^{s}}}\quad {\mbox{ for all }}x\geq 1\quad \Longleftrightarrow \quad f(x)=\sum _{m=1}^{\infty }\alpha ^{-1}(m){\frac {g(mx)}{m^{s}}}\quad {\mbox{ for all }}x\geq 1.}$

Por ejemplo, existe una demostración bien conocida que relaciona la función zeta de Riemann con la función zeta prima que utiliza la forma basada en series de la inversión de Möbius en la ecuación anterior cuando${\displaystyle s=1}$. Es decir, mediante la representación del producto de Euler de${\displaystyle \zeta (s)}$para ${\displaystyle \Re (s)>1}$

${\displaystyle \log \zeta (s)=-\sum _{p\mathrm {\ prime} }\log \left(1-{\frac {1}{p^{s}}}\right)=\sum _{k\geq 1}{\frac {P(ks)}{k}}\iff P(s)=\sum _{k\geq 1}{\frac {\mu (k)}{k}}\log \zeta (ks),\Re (s)>1.}$

Estas identidades para formas alternativas de inversión de Möbius se encuentran en ^{[ 2 ]} . Una teoría más general de fórmulas de inversión de Möbius, citada parcialmente en la siguiente sección sobre álgebras de incidencia, es construida por Rota en ^{[ 3 ] .}

Como la inversión de Möbius se aplica a cualquier grupo abeliano, no importa si la operación de grupo se escribe como suma o como multiplicación. Esto da lugar a la siguiente variante de notación de la fórmula de inversión:

${\displaystyle {\mbox{if }}F(n)=\prod _{d|n}f(d),{\mbox{ then }}f(n)=\prod _{d|n}F\left({\frac {n}{d}}\right)^{\mu (d)}.}$

La primera generalización se puede demostrar de la siguiente manera. Usamos la convención de Iverson de que [condición] es la función indicadora de la condición, siendo 1 si la condición es verdadera y 0 si es falsa. Usamos el resultado de que

${\displaystyle \sum _{d|n}\mu (d)=\varepsilon (n),}$

eso es,${\displaystyle 1*\mu =\varepsilon }$, dónde${\displaystyle \varepsilon }$es la función unitaria .

Tenemos lo siguiente:

${\displaystyle {\begin{aligned}\sum _{1\leq n\leq x}\mu (n)g\left({\frac {x}{n}}\right)&=\sum _{1\leq n\leq x}\mu (n)\sum _{1\leq m\leq {\frac {x}{n}}}f\left({\frac {x}{mn}}\right)\\&=\sum _{1\leq n\leq x}\mu (n)\sum _{1\leq m\leq {\frac {x}{n}}}\sum _{1\leq r\leq x}[r=mn]f\left({\frac {x}{r}}\right)\\&=\sum _{1\leq r\leq x}f\left({\frac {x}{r}}\right)\sum _{1\leq n\leq x}\mu (n)\sum _{1\leq m\leq {\frac {x}{n}}}\left[m={\frac {r}{n}}\right]\qquad {\text{rearranging the summation order}}\\&=\sum _{1\leq r\leq x}f\left({\frac {x}{r}}\right)\sum _{n|r}\mu (n)\\&=\sum _{1\leq r\leq x}f\left({\frac {x}{r}}\right)\varepsilon (r)\\&=f(x)\qquad {\text{since }}\varepsilon (r)=0{\text{ except when }}r=1\end{aligned}}}$

La demostración en el caso más general donde α ( n ) reemplaza a 1 es esencialmente idéntica, al igual que la segunda generalización.

Para un poset P , un conjunto dotado de una relación de orden parcial${\displaystyle \leq }$, define la función de Möbius${\displaystyle \mu }$de P recursivamente por

${\displaystyle \mu (s,s)=1{\text{ for }}s\in P,\qquad \mu (s,u)=-\sum _{s\leq t<u}\mu (s,t),\quad {\text{ for }}s<u{\text{ in }}P.}$

(Aquí se supone que las sumas son finitas.) Entonces, para${\displaystyle f,g:P\to K}$donde K es un anillo conmutativo , tenemos

${\displaystyle g(t)=\sum _{s\leq t}f(s)\qquad {\text{ for all }}t\in P}$

si y solo si

${\displaystyle f(t)=\sum _{s\leq t}g(s)\mu (s,t)\qquad {\text{ for all }}t\in P.}$

(Véase Combinatoria enumerativa de Stanley , vol. 1, sección 3.7).

La función de Möbius aritmética clásica es un caso especial del conjunto parcialmente ordenado P de enteros positivos ordenados por divisibilidad : es decir, para enteros positivos s, t, definimos el orden parcial.${\displaystyle s\preccurlyeq t}$para significar que s es un divisor de t . En el conjunto potencia${\displaystyle {\mathcal {P}}(S)}$de un conjunto${\displaystyle S}$, ordenado por${\displaystyle \subseteq }$(inclusión de conjuntos), el teorema de inversión de Möbius reproduce el principio de inclusión-exclusión y en el conjunto${\displaystyle \mathbb {N} }$de números naturales con su ordenación estándar (total) por${\displaystyle \leq }$El teorema coincide con una versión discreta del teorema fundamental del cálculo (véase Combinatoria enumerativa de Stanley , vol. 1, sección 3.8). En diversas ciencias, muchas medidas de interacción pueden formularse como inversiones de Möbius en diferentes conjuntos parcialmente ordenados. Algunos ejemplos son los valores de Shapley en la teoría de juegos , las interacciones de máxima entropía en la mecánica estadística , la epistasis en genética y la información de interacción , la correlación total y la descomposición de información parcial de la teoría de la información . ^{[ 4 ]}

La formulación general de la fórmula de inversión de Möbius [para conjuntos parcialmente ordenados] fue presentada por primera vez de forma independiente por Weisner (1935) y Philip Hall (1936); ambos autores se inspiraron en problemas de teoría de grupos. Ninguno de los dos parece haber sido consciente de las implicaciones combinatorias de su trabajo ni desarrolló la teoría de las funciones de Möbius. En un artículo fundamental sobre funciones de Möbius, Rota demostró la importancia de esta teoría en matemáticas combinatorias y la trató en profundidad. Señaló la relación entre temas como la inclusión-exclusión, la inversión de Möbius clásica en teoría de números, los problemas de coloración y los flujos en redes. Desde entonces, bajo la fuerte influencia de Rota, la teoría de la inversión de Möbius y temas relacionados se ha convertido en un área activa de la combinatoria. ^{[ 5 ]}

• secuencia de Farey
• Principio de inclusión-exclusión

• Apostol, Tom M. (1976), Introducción a la teoría analítica de números , Textos de pregrado en matemáticas, Nueva York-Heidelberg: Springer-Verlag, ISBN 978-0-387-90163-3, MR 0434929 , Zbl 0335.10001  
• Bender, Edward A.; Goldman, J.  R. (1975), "Sobre las aplicaciones de la inversión de Möbius en el análisis combinatorio" , Amer. Math. Monthly , 82 (8): 789– 803, doi : 10.2307/2319793 , JSTOR 2319793 
• Ireland, K.; Rosen, M. (2010), A Classical Introduction to Modern Number Theory , Graduate Texts in Mathematics (Libro 84) (2.ª  ed.), Springer-Verlag, ISBN 978-1-4419-3094-1
• Kung, Joseph PS (2001) [1994], "Inversión de Möbius" , Enciclopedia de Matemáticas , EMS Press
• Möbius, AF (1832), "Über eine besondere Art von Umkehrung der Reihen". , Journal für die reine und angewandte Mathematik , 9 : 105-123
• Stanley, Richard P. (1997), Combinatoria enumerativa , vol.  1, Cambridge University Press, ISBN 0-521-55309-1
• Stanley, Richard P. (1999), Combinatoria enumerativa , vol.  2, Cambridge University Press, ISBN 0-521-56069-1

• Weisstein, Eric W. "Transformación de Möbius" . MundoMatemático .