Fórmula de inversión de Möbius

Relación entre pares de funciones aritméticas

En matemáticas , la clásica fórmula de inversión de Möbius es una relación entre pares de funciones aritméticas , cada una definida a partir de la otra por sumas sobre 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 arbitrario localmente finito , y la fórmula clásica de Möbius se aplica al conjunto de los números naturales ordenados por divisibilidad: véase álgebra de incidencia .

Enunciado de la fórmula

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{for every integer }}n\geq 1}$

entonces

${\displaystyle f(n)=\sum _{d\mid n}\mu (d)g\left({\frac {n}{d}}\right)\quad {\text{for every integer }}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 en las fórmulas anteriores). En efecto, la f ( n ) original se puede determinar dada g ( n ) utilizando la fórmula de inversión. Se dice que las dos secuencias son transformadas de Möbius entre sí. ${\displaystyle d\mid n}$

La fórmula también es correcta si f y g son funciones de los números 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 puede escribirse 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 dan muchos ejemplos específicos .

El teorema se deduce porque ∗ es (conmutativo y) asociativo, 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}$.

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

${\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.}$

Relaciones de series

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 por medio de 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 .

Transformaciones repetidas

Dada una función aritmética, se puede generar una secuencia bi-infinita de otras funciones aritméticas aplicando repetidamente la primera suma.

Por ejemplo, si uno comienza con la función totiente de Euler φ y 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 divisor

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 = ε dondees la función unitaria $${\displaystyle \varepsilon (n)={\begin{cases}1,&{\text{if }}n=1\\0,&{\text{if }}n>1\end{cases}}}$$
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 recorrerlas hacia atrás.

A modo de ejemplo, la secuencia que comienza con φ es:

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

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

Generalizaciones

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 valor complejo definidas en el intervalo [1, ∞) tales que

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

entonces

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

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

Este 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 uno define

${\displaystyle G(x)=\sum _{1\leq n\leq x}\alpha (n)F\left({\frac {x}{n}}\right)\quad {\mbox{ for all }}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 dejamos que f ( n ) sea 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 cada fracción ⁠a/b⁠ con mcd( a , b ) = d y b ≤ n se puede reducir a la fracción ⁠un / a/b / d⁠ con ⁠b/d⁠ ≤ ⁠norte/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 asumimos 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 prueba 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 . Es decir, por la representación del producto de Euler de para ${\displaystyle s=1}$ ${\displaystyle \zeta (s)}$ ${\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] . Rota construye una teoría más general de las fórmulas de inversión de Möbius, citada parcialmente en la siguiente sección sobre álgebras de incidencia. ^[3]

Notación multiplicativa

Como la inversión de Möbius se aplica a cualquier grupo abeliano, no hay diferencia 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)}.}$

Pruebas de generalizaciones

La primera generalización se puede demostrar de la siguiente manera. Utilizamos 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. Utilizamos el resultado de que

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

es decir, , donde es la función unitaria . ${\displaystyle 1*\mu =\varepsilon }$ ${\displaystyle \varepsilon }$

Contamos con 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 prueba en el caso más general donde α ( n ) reemplaza a 1 es esencialmente idéntica, al igual que la segunda generalización.

Sobre posets

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

${\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 , donde K es un anillo conmutativo, tenemos ${\displaystyle f,g:P\to K}$

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

Si y sólo 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 aritmética clásica de Möbius es el caso especial del conjunto parcial P de números enteros positivos ordenados por divisibilidad : es decir, para los números enteros positivos s, t, definimos el orden parcial para significar que s es un divisor de t . ${\displaystyle s\preccurlyeq t}$

Contribuciones de Weisner, Hall y Rota

La formulación general de la fórmula de inversión de Möbius [para conjuntos parcialmente ordenados] fue propuesta por primera vez de forma independiente por Weisner (1935) y Philip Hall (1936); ambos autores estaban motivados por problemas de teoría de grupos. Ninguno de los dos autores parece haber sido consciente de las implicaciones combinatorias de su trabajo y ninguno desarrolló la teoría de las funciones de Möbius. En un artículo fundamental sobre las funciones de Möbius, Rota mostró la importancia de esta teoría en las 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 de la teoría clásica 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 han convertido en un área activa de la combinatoria. ^[4]

Véase también

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

Notas

1. Möbius 1832, págs. 105-123
2. Manual NIST de funciones matemáticas, Sección 27.5.
3. [Sobre los fundamentos de la teoría combinatoria, I. Teoría de las funciones de Möbius|https://link.springer.com/content/pdf/10.1007/BF00531932.pdf]
4. Bender y Goldman 1975, págs. 789-803

Referencias

• 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), Una introducción clásica a la teoría de números moderna , Textos de posgrado en matemáticas (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

Enlaces externos

• Fórmula de inversión de Möbius en ProofWiki
• Weisstein, Eric W. "Transformación de Möbius". MundoMatemático .