Fórmula de inversión de Möbius

Relación entre pares de funciones aritméticas

En matemáticas , la fórmula de inversión clásica de Möbius es una relación entre pares de funciones aritméticas , cada una definida a partir de la otra mediante sumas sobre divisores . Fue introducido 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 de un conjunto arbitrario localmente finito parcialmente ordenado , aplicándose la fórmula clásica de Möbius al conjunto de los números naturales ordenados por divisibilidad: ver álgebra de incidencia .

Declaración 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 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 sigue porque ∗ es (conmutativo y) asociativo, y 1 ∗ μ = ε , donde ε es la función identidad para la convolución de Dirichlet, tomando valores ε (1) = 1 , ε ( n ) = 0 para todo n > 1 . De este modo

${\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 en serie

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 transformación. Las transformadas se relacionan 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 .

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 se comienza con 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{if }}n=1\\0,&{\text{if }}n>1\end{cases}}}$$
   es la función unitaria
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 hacia atrás.

Como 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 tal vez puedan entenderse más fácilmente considerando la serie de Dirichlet correspondiente : cada aplicación repetida de la transformada corresponde a la 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 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{ 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 sean menores o iguales que x .

Éste, 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{ 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 , cuyo inverso 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 números 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óna/bcon mcd( a , b ) = d y b ≤ n se puede reducir a la fraccióna / d/b / dconb/d≤norte/d, y viceversa.) Aquí es sencillo determinar g ( n ) =norte ( norte - 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 arriba, esto se generaliza al caso donde α ( 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 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 parcialmente citada 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 del grupo se escribe como suma o como multiplicación. Esto da lugar a la siguiente variante notacional 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. 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 que

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

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

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

En posets

Para un poset P , un conjunto dotado de una relación de orden parcial , defina la función de Möbius de P recursivamente por ${\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 sumatorias 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 solo si

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

(Ver Stanley's Enumerative Combinatorics , Vol 1, Sección 3.7.) La función aritmética de Mobius clásica es el caso especial del poset P de enteros positivos ordenados por divisibilidad : es decir, para enteros positivos s, t, definimos el orden parcial como significado que s es divisor de t . ${\displaystyle s\preccurlyeq t}$

Contribuciones de Weisner, Hall y Rota

El enunciado de la fórmula general de inversión de Möbius [para conjuntos parcialmente ordenados] fue dado 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 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. Observó la relación entre temas como la inclusión-exclusión, la inversión clásica de Möbius en la 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. ^[4]

Ver también

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

Notas

1. Moebius 1832, págs. 105-123
2. Manual de funciones matemáticas del NIST, 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, SEÑOR  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. Matemáticas. Mensual , 82 (8): 789–803, doi :10.2307/2319793, JSTOR  2319793
• Irlanda, 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, Prensa de la Universidad de Cambridge, ISBN 0-521-55309-1
• Stanley, Richard P. (1999), Combinatoria enumerativa, vol. 2, Prensa de la Universidad de Cambridge, 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 .