Fórmula de inversión de Möbius

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 introducido en la teoría de números en 1832 por August Ferdinand Möbius.

Una gran generalización de esta fórmula se aplica a la suma de un conjunto arbitrario localmente finito parcialmente ordenado, con Möbius' fórmula clásica aplicable al conjunto de los números naturales ordenados por divisibilidad: ver á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

g()n)=.. d▪ ▪ nf()d)para cada enteron≥ ≥ 1{displaystyle g(n)=sum _{dmid n}f(d)quad {text{for every integer }ngeq 1}

entonces

f()n)=.. d▪ ▪ nμ μ ()d)g()nd)para cada enteron≥ ≥ 1{displaystyle f(n)=sum _{dmid n}mu (d)gleft({frac {n}{d}right)quad ################################################################################################################################################################################################################################################################ }ngeq 1}

Donde μ es la función Möbius y las sumas se extienden sobre todos los divisores positivos d de n (indicado por d▪ ▪ n{displaystyle dmid n} en las fórmulas anteriores). En efecto, el original f()n) puede determinarse dado g()n) usando la fórmula de inversión. Se dice que las dos secuencias son Möbius transforma uno del otro.

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 circunvoluciones de Dirichlet, la primera fórmula puede escribirse como

g=1Alternativa Alternativa f{displaystyle g={mátit {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

f=μ μ Alternativa Alternativa g.{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 de identidad para la convolución de Dirichlet, tomando valores ε(1) = 1, ε(n ) = 0 para todos los n > 1. Por lo tanto

μ μ Alternativa Alternativa g=μ μ Alternativa Alternativa ()1Alternativa Alternativa f)=()μ μ Alternativa Alternativa 1)Alternativa Alternativa f=ε ε Alternativa Alternativa f=f{displaystyle mu *g=mu *({mathit {1}*f)=(mu *{mathit {1}})*f=varepsilon *f=f}.

Existe una versión de producto de la fórmula de inversión de Möbius basada en la suma mencionada anteriormente:

g()n)=∏ ∏ dSilencionf()d)⟺ ⟺ f()n)=∏ ∏ dSilenciong()nd)μ μ ()d),О О n≥ ≥ 1.{displaystyle g(n)=prod _{d habitn}f(d)iff f(n)=prod _{d habitn}gleft({frac {n}right)}{mu (d)},forall ngeq 1.}

Relaciones en serie

Dejar

an=.. d▪ ▪ nbd{displaystyle A_{n}=sum _{dmid No.

para que

bn=.. d▪ ▪ nμ μ ()nd)ad{displaystyle b_{n}=sum _{dmid n}mu left({frac {n}right)a_{d}

es su transformación. Las transformadas se relacionan mediante series: la serie de Lambert

.. n=1JUEGO JUEGO anxn=.. n=1JUEGO JUEGO bnxn1− − xn{displaystyle sum _{n=1}{infty. ¿Qué? }b_{n}{frac {x}{n}{1-x^{n}}}

y la serie de Dirichlet:

.. n=1JUEGO JUEGO anns=Especificaciones Especificaciones ()s).. n=1JUEGO JUEGO bnns{displaystyle sum _{n=1}{infty }{frac {fn} {fn}}=zeta (s)sum _{n=1}{infty }{frac {fn} {fn}}} {fn}}} {fn}}} {fn}}}}}}}} {fn}}}}}}}}}}}} {cH}}}}}}}}}}}}}} {cH}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}

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 totient de Euler φ, y aplica repetidamente el proceso de transformación, uno obtiene:

1. φ la función totiente
2. φ Alternativa 1 = I, donde I()n) n es la función de identidad
3. I Alternativa 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 Möbius
2. μ Alternativa 1 = ε Donde
   1end{cases}}}" display="block" xmlns="http://www.w3.org/1998/Math/MathML">ε ε ()n)={}1,sin=10,sin■1{displaystyle varepsilon (n)={begin{cases}1, limit{if} - No.

   1end{cases}}}" aria-hidden="true" class="mwe-math-fallback-image-display" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/98ad09dc0f65cc3578fc29154bae9abc1ad72f43" style="vertical-align: -2.505ex; width:21.607ex; height:6.176ex;"/>
   es la función de unidad
3. ε Alternativa 1 = 1, la función constante
4. 1 Alternativa 1 = σ₀ = d = τ, donde d τ es el número de divisores de n, (ver función divisor).

Estas dos 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:

<math alttext="{displaystyle f_{n}={begin{cases}underbrace {mu *ldots *mu } _{-n{text{ factors}}}*varphi &{text{if }}n0end{cases}}}" xmlns="http://www.w3.org/1998/Math/MathML">fn={}μ μ Alternativa Alternativa ...... Alternativa Alternativa μ μ ⏟ ⏟ − − nfactoresAlternativa Alternativa φ φ sin.0φ φ sin=0φ φ Alternativa Alternativa 1Alternativa Alternativa ...... Alternativa Alternativa 1⏟ ⏟ nfactoressin■0{displaystyle f_{n}={begin{cases}underbrace {mu *ldots *mu } {fnfnfnfnfnfnfnfnfnfnK}n=0[8px]varphi > {fnfncH00}cHFF}cH00} {fnfn}fnfnfnfnh} {fnfnfnfnfn}}fnfnfnfnfnfnfn}fnfnfnfnfnfnfnfn}fnfnfnfnfnfnfnfn}fnfn}fnfn}fnfn}fnfnfnfn\fnfn}fnfnfnfn\\\\\fnfn}fn - ¿Qué?<img alt="{displaystyle f_{n}={begin{cases}underbrace {mu *ldots *mu } _{-n{text{ factors}}}*varphi &{text{if }}n0end{cases}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/18220333c3e2775d67fff05a360acda8f57659f2" style="vertical-align: -8.838ex; width:31.822ex; height:18.843ex;"/>

Las secuencias generadas quizás 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: suponga F(x) y G(x) son funciones de valor complejo definidas en el intervalo [1, ∞) tal que

G()x)=.. 1≤ ≤ n≤ ≤ xF()xn)para todosx≥ ≥ 1{displaystyle G(x)=sum _{1leq nleq x}Fleft({frac {x}{n}right)quad {mbox{ for all }xgeq 1}

entonces

F()x)=.. 1≤ ≤ n≤ ≤ xμ μ ()n)G()xn)para todosx≥ ≥ 1.{displaystyle F(x)=sum _{1leq nleq x}mu (n)Gleft({frac {x}{n}right)quad {mbox{ for all }xgeq 1.}

Aquí las sumas se extienden sobre todos los enteros positivos n que son menores o iguales que 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 uno define

G()x)=.. 1≤ ≤ n≤ ≤ xα α ()n)F()xn)para todosx≥ ≥ 1{displaystyle G(x)=sum _{1leq nleq x}alpha (n)Fleft({frac {x}{n}right)quad {mbox{ for all }xgeq 1}

entonces

F()x)=.. 1≤ ≤ n≤ ≤ xα α − − 1()n)G()xn)para todosx≥ ≥ 1.{displaystyle F(x)=sum _{1leq nleq x}alpha ^{-1}(n)Gleft({frac {x}{n}right)quad {mbox{ for all }xgeq 1.}

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

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

g()n)=.. 1≤ ≤ m≤ ≤ nf()⌊nm⌋)para todosn≥ ≥ 1.{displaystyle g(n)=sum _{1leq mleq n}fleft(leftlfloor {frac {n} {m}rightrfloor right)quad {mbox{ for all }ngeq 1.}

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

f()n)=.. 1≤ ≤ m≤ ≤ nμ μ ()m)g()⌊nm⌋)para todosn≥ ≥ 1.{displaystyle f(n)=sum _{1leq mleq n}mu (m)gleft(leftlfloor {frac {n} {m}rightrfloor right)quad {mbox{ for all }ngeq 1.}

Un ejemplo simple 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 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 asumimos que las series involucradas son absolutamente convergentes):

g()x)=.. m=1JUEGO JUEGO f()mx)mspara todosx≥ ≥ 1⟺ ⟺ f()x)=.. m=1JUEGO JUEGO μ μ ()m)g()mx)mspara todosx≥ ≥ 1.{fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {f}}}quad {mbox{ for all }xgq 1quad Longleftright arrowquad f(x)=sum _{m=1}{m=1}{inftymm}mmm}mm} {} {} {m} {m}{} {m} {m} {f}f} {f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}fn {mbox{ for all }xgeq 1.}

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

g()x)=.. m=1JUEGO JUEGO α α ()m)f()mx)mspara todosx≥ ≥ 1⟺ ⟺ f()x)=.. m=1JUEGO JUEGO α α − − 1()m)g()mx)mspara todosx≥ ≥ 1.{displaystyle g(x)=sum {fnMicrosoft Sans Serif}}quad {mbox{ for all }xgeq 1quad Longleftrightarrow quad f(x)=sum _{m=1}^{infty }alpha ^{-1}(m){(mx)}{m^{s}}}}quad {mbox{ for all }xgeq 1.}

Por ejemplo, hay una prueba bien conocida que relaciona la función Riemann zeta con la función zieta principal que utiliza la forma basada en series de Inversión de Möbius en la ecuación anterior cuando s=1{displaystyle s=1}. Es decir, por la representación del producto Euler Especificaciones Especificaciones ()s){displaystyle zeta (s)} para 1}" xmlns="http://www.w3.org/1998/Math/MathML">R R ()s)■1{displaystyle Re (s)}1" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9ea5968732ea35f67b36093364400e0fd8ca23bf" style="vertical-align: -0.838ex; width:9.085ex; height:2.843ex;"/>

1.}" xmlns="http://www.w3.org/1998/Math/MathML">log⁡ ⁡ Especificaciones Especificaciones ()s)=− − .. pprimelog⁡ ⁡ ()1− − 1ps)=.. k≥ ≥ 1P()ks)k⟺ ⟺ P()s)=.. k≥ ≥ 1μ μ ()k)klog⁡ ⁡ Especificaciones Especificaciones ()ks),R R ()s)■1.{displaystyle log zeta (s)=-sum _{pmathrm { prime} }log left(1-{frac {1}{p^{s}}right)=sum _{kgeq 1}{frac {P(ks)}{k}iff P(s)=sum _{kgeq 1}{frac {mu (k)}}}{k}}log zeta (ks),Re (s)} {} {} {} {}}}}} {log} {log}} {log}}}} {log} {log}}}}} {log} {log}} {log}}}}}loglog}}log}log}} {log}loglog} {log} {log} {log}} {} {log}}}}loglog} {log}}}}}loglog}}}}} {log}log}log}log}log}log}}log}log}}}loglog}1.}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/193b5a8a8dcc89a51e5cfec797adca13384af0a9" style="vertical-align: -3.338ex; width:88.854ex; height:7.176ex;"/>

Estas identidades para formas alternativas de inversión de Möbius se encuentran en. Rota in.

Notación multiplicativa

Como la inversión de Möbius se aplica a cualquier grupo abeliano, no importa 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:

siF()n)=∏ ∏ dSilencionf()d),entoncesf()n)=∏ ∏ dSilencionF()nd)μ μ ()d).{displaystyle {mbox{if }}F(n)=prod _{d habitn}f(d),{mbox{ then }}f(n)=prod _{d perpetuan}Fleft({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 de que

.. dSilencionμ μ ()d)=ε ε ()n),{displaystyle sum _{d habitn}mu (d)=varepsilon (n),}

es decir, 1Alternativa Alternativa μ μ =ε ε {displaystyle 1*mu =varepsilon }, donde ε ε {displaystyle varepsilon } es la función de unidad.

Tenemos lo siguiente:

.. 1≤ ≤ n≤ ≤ xμ μ ()n)g()xn)=.. 1≤ ≤ n≤ ≤ xμ μ ()n).. 1≤ ≤ m≤ ≤ xnf()xmn)=.. 1≤ ≤ n≤ ≤ xμ μ ()n).. 1≤ ≤ m≤ ≤ xn.. 1≤ ≤ r≤ ≤ x[r=mn]f()xr)=.. 1≤ ≤ r≤ ≤ xf()xr).. 1≤ ≤ n≤ ≤ xμ μ ()n).. 1≤ ≤ m≤ ≤ xn[m=rn]reorganización de la orden de summation=.. 1≤ ≤ r≤ ≤ xf()xr).. nSilenciorμ μ ()n)=.. 1≤ ≤ r≤ ≤ xf()xr)ε ε ()r)=f()x)desde entoncesε ε ()r)=0excepto cuandor=1{cHFF} {ccH00}cH00}cH00}cH00} {cH00}cH00}cH0}ccH00}cH0}cH0}cH00}cH00}cH00}ccH00}cH0cH00cH0}cH0cH00cH00}cH00}cH00cH00}ccH00}cH00}cH00}cH00cH00cH0cH0cH00cH00}cH00}cH00}cH00}cH0cH00}cH00}ccH00cH00cH00cH00cH00}cH00}cH0cH00cH00}cH0cH00cH00}cccH {fn} {fn} {fn}fn} {f}fn}m}m}f}m}cccn}ccH00}cH00}cH00}cH00cccH00}ccH00}cH00} {cH00}cH00}cH00}cH00}cH00}ccH00}ccccccH00}cH00}cccH00}cH00}cH00}cH00}cH00}ccccH00}ccH00}cH00}ccH00}ccH00}cccccH00}cH00}cccH00}ccH00}cH00}cccc {r} {n}right]qquad {texto{rearranging {fnMicrosoft Sans Serif} {f} {f} {f} {f} {f}} {f}} {f}}}} {f}}f} {f}} {f}} {cH0} {ccH0} {ccH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00} {cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}

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

En poses

Para una pose P, un conjunto dotado con una relación de orden parcial ≤ ≤ {displaystyle leq }, definir la función Möbius μ μ {displaystyle mu } de P recursivamente por

<math alttext="{displaystyle mu (s,s)=1{text{ for }}sin P,qquad mu (s,u)=-sum _{sleq t<u}mu (s,t),quad {text{ for }}sμ μ ()s,s)=1paras▪ ▪ P,μ μ ()s,u)=− − .. s≤ ≤ t.uμ μ ()s,t),paras.udentroP.{displaystyle mu (s,s)=1{text{ for }sin P,qquad mu (s,u)=-sum _{sleq t madeu}mu (s,t),quad {text{ for }s meantu{text{ in }}P}<img alt="{displaystyle mu (s,s)=1{text{ for }}sin P,qquad mu (s,u)=-sum _{sleq t<u}mu (s,t),quad {text{ for }}s

(Aquí uno asume que las sumas son finitas.) Entonces... f,g:P→ → K{displaystyle f,g:Pto K}, donde K es un anillo conmutativo, tenemos

g()t)=.. s≤ ≤ tf()s)para todost▪ ▪ P{displaystyle g(t)=sum _{sleq t}f(s)qquad {text{ for all }tin P}

si y solo si

f()t)=.. s≤ ≤ tg()s)μ μ ()s,t)para todost▪ ▪ P.{displaystyle f(t)=sum _{sleq t}g(s)mu (s,t)qquad {text{ for all }tin P.}

(Ver Combinatoria enumerativa de Stanley, Vol. 1, Sección 3.7.)

Contribuciones de Weisner, Hall y Rota

The statement of the general Möbius inversion formula [for partially ordered sets] was first given independently by Weisner (1935) and Philip Hall (1936); both author were motivated by group theory problems. Ninguno de los autores parece haber sido consciente de las implicaciones combinatorias de su trabajo y tampoco desarrolló la teoría de las funciones de Möbius. En un documento fundamental sobre las funciones de Möbius, Rota mostró la importancia de esta teoría en las matemáticas combinatorias y dio un tratamiento profundo de ella. Observó la relación entre temas como inclusión-exclusión, inversión de Möbius teórica del número clásico, problemas de color y 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 combinatoria.