Möbius-Inversionsformel - Möbius inversion formula

In der Mathematik ist die klassische Möbius-Inversionsformel eine Beziehung zwischen Paaren arithmetischer Funktionen , die jeweils durch Summen über Teiler voneinander definiert sind . Es wurde 1832 von August Ferdinand Möbius in die Zahlentheorie eingeführt .

Eine große Verallgemeinerung dieser Formel gilt für die Summation über eine beliebige lokal endliche partiell geordnete Menge , wobei die klassische Formel von Möbius für die Menge der nach Teilbarkeit geordneten natürlichen Zahlen gilt: siehe Inzidenzalgebra .

Angabe der Formel

Die klassische Version besagt , dass wenn g und f sind arithmetische Funktionen erfüllen

${\displaystyle g(n)=\sum _{d\mid n}f(d)\quad {\text{für jede ganze Zahl }}n\geq 1}$

dann

${\displaystyle f(n)=\sum _{d\mid n}\mu(d)g\left({\frac {n}{d}}\right)\quad {\text{für jede ganze Zahl }} n\geq 1}$

wobei μ die Möbius-Funktion ist und sich die Summen über alle positiven Teiler d von n erstrecken ( in den obigen Formeln durch gekennzeichnet). Tatsächlich kann das ursprüngliche f ( n ) bei gegebenem g ( n ) unter Verwendung der Inversionsformel bestimmt werden. Die beiden Folgen werden als Möbius-Transformationen voneinander bezeichnet. ${\displaystyle d\mid n}$

Die Formel ist auch richtig , wenn f und g Funktionen sind , von den positiven ganzen Zahlen in eine abelschen Gruppe (als ein angesehen ℤ - Modul ).

In der Sprache der Dirichlet-Faltung kann die erste Formel geschrieben werden als

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

wobei ∗ die Dirichlet-Faltung bezeichnet und 1 die konstante Funktion 1 ( n ) = 1 ist . Die zweite Formel wird dann geschrieben als

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

Viele konkrete Beispiele werden im Artikel über multiplikative Funktionen gegeben .

Der Satz folgt, weil ∗ (kommutativ und) assoziativ ist und 1 ∗ μ = ε , wobei ε die Identitätsfunktion für die Dirichlet-Faltung ist, mit Werten ε (1) = 1 , ε ( n ) = 0 für alle n > 1 . Daher

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

Es gibt eine Produktversion der oben genannten summierungsbasierten Möbius-Inversionsformel:

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

Reihenbeziehungen

Lassen

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

so dass

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

ist seine Verwandlung. Die Transformationen sind durch Reihen verbunden: die Lambert-Reihe

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

und die Dirichlet-Reihe :

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

wobei ζ ( s ) die Riemannsche Zetafunktion ist .

Wiederholte Transformationen

Bei einer gegebenen arithmetischen Funktion kann man durch wiederholtes Anwenden der ersten Summation eine bi-infinite Folge anderer arithmetischer Funktionen erzeugen.

Beginnt man beispielsweise mit der Eulerschen Totient-Funktion φ und wendet den Transformationsprozess wiederholt an, erhält man:

1. φ die Totient-Funktion
2. φ ∗ 1 = I , wobei I ( n ) = n die Identitätsfunktion ist
3. I ∗ 1 = σ ₁ = σ , die Teilerfunktion

Wenn die Startfunktion die Möbius-Funktion selbst ist, lautet die Liste der Funktionen:

1. μ , die Möbius-Funktion
2. μ ∗ 1 = ε wobei

   ${\displaystyle \varepsilon (n)={\begin{cases}1,&{\mbox{if }}n=1\\0,&{\mbox{if }}n>1\end{cases}}}$

   ist die Einheitsfunktion

3. ε ∗ 1 = 1 , die konstante Funktion
4. 1 ∗ 1 = σ ₀ = d = τ , wobei d = τ die Anzahl der Teiler von n ist (siehe Teilerfunktion ).

Beide Listen von Funktionen erstrecken sich unendlich in beide Richtungen. Die Möbius-Inversionsformel ermöglicht es, diese Listen rückwärts zu durchlaufen.

Als ein Beispiel mit der Sequenz beginnend φ ist:

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

Die erzeugten Folgen lassen sich vielleicht leichter verstehen, wenn man die entsprechende Dirichlet-Reihe betrachtet : Jede wiederholte Anwendung der Transformation entspricht einer Multiplikation mit der Riemannschen Zeta-Funktion .

Verallgemeinerungen

Ein verwandtes Inversionsformel nützlichere in Kombinatorik ist wie folgt: Angenommen , F ( x ) und G ( x ) sind komplexe -wertige Funktionen auf dem definierten Intervall [1, ∞) derart , dass

${\displaystyle G(x)=\sum _{1\leq n\leq x}F\left({\frac {x}{n}}\right)\quad {\mbox{ für alle }}x\geq 1}$

dann

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

Dabei erstrecken sich die Summen über alle positiven ganzen Zahlen n, die kleiner oder gleich x sind .

Dies wiederum ist ein Sonderfall einer allgemeineren Form. Wenn α ( n ) eine arithmetische Funktion mit einer Dirichlet-Inversen α ⁻¹ ( n ) ist , dann definiert man

${\displaystyle G(x)=\sum _{1\leq n\leq x}\alpha (n)F\left({\frac {x}{n}}\right)\quad {\mbox{ für alle }}x\geq 1}$

dann

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

Die vorhergehende Formel ergibt sich in dem speziellen Fall der konstante Funktion α ( n ) = 1 , dessen Dirichlet Invers ist α ^-1 ( n ) = μ ( n ) .

Eine besondere Anwendung der ersten dieser Erweiterungen ergibt sich, wenn wir (komplexwertige) Funktionen f ( n ) und g ( n ) auf den positiven ganzen Zahlen definiert haben, mit

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

Durch Definition von F ( x ) = f (⌊ x ⌋) und G ( x ) = g (⌊ x ⌋) folgern wir, dass

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

Ein einfaches Beispiel für die Verwendung dieser Formel ist das Zählen der Anzahl der reduzierten Brüche 0 < ein/B<1 , wobei a und b sind coprime und b ≤ n . Lassen wir f ( n ) diese Zahl sein, dann ist g ( n ) die Gesamtzahl der Brüche 0 <ein/B< 1 mit b ≤ n , wobei a und b nicht notwendigerweise teilerfremd sind. (Das liegt daran, dass jeder Bruchein/Bmit gcd( a , b ) = d und b ≤ n kann man auf den Bruchein / d/b / d mit B/D ≤ n/D, und umgekehrt.) Hier lässt sich g ( n ) =n ( n − 1)/2, aber f ( n ) ist schwieriger zu berechnen.

Eine andere Inversionsformel lautet (wo wir annehmen, dass die beteiligten Reihen absolut konvergent sind):

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

Wie oben verallgemeinert sich dies auf den Fall, in dem α ( n ) eine arithmetische Funktion mit einer Dirichlet-Inversen α ⁻¹ ( n ) ist :

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

Zum Beispiel gibt es einen wohlbekannten Beweis, der die Riemannsche Zetafunktion mit der Primzetafunktion in Beziehung setzt, der die reihenbasierte Form der Möbius-Inversion in der vorherigen Gleichung verwendet, wenn . Nämlich durch die Euler-Produktdarstellung von for ${\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)=\ Summe _{k\geq 1}{\frac{P(ks)}{k}}\iff P(s)=\sum_{k\geq 1}{\frac {\mu(k)}{k} }\log\zeta(ks),\Re(s)>1.}$

Diese Identitäten für alternative Formen der Möbius-Inversion finden sich in. Eine allgemeinere Theorie der Möbius-Inversionsformeln, die teilweise im nächsten Abschnitt über Inzidenzalgebren zitiert wird, wird von Rota in konstruiert.

Multiplikative Notation

Da die Möbius-Inversion für jede abelsche Gruppe gilt, macht es keinen Unterschied, ob die Gruppenoperation als Addition oder als Multiplikation geschrieben wird. Daraus ergibt sich folgende Notationsvariante der Inversionsformel:

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

Beweise für Verallgemeinerungen

Die erste Verallgemeinerung lässt sich wie folgt beweisen. Wir verwenden Iversons Konvention, dass [Bedingung] die Indikatorfunktion der Bedingung ist, die 1 ist, wenn die Bedingung wahr ist, und 0, wenn sie falsch ist. Wir verwenden das Ergebnis, dass

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

das heißt, wo ist die Einheitsfunktion . ${\displaystyle 1*\mu =\varepsilon}$${\displaystyle\varepsilon}$

Wir haben folgendes:

${\displaystyle {\begin{ausgerichtet}\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{Umstellen der Summationsreihenfolge}}\\&=\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{seit }}\varepsilon (r)=0{\text{ außer wenn }}r=1\end{ausgerichtet }}}$

Der Beweis im allgemeineren Fall, in dem α ( n ) 1 ersetzt, ist im Wesentlichen identisch, ebenso wie die zweite Verallgemeinerung.

Auf Posen

Für ein Poset P , eine Menge mit einer partiellen Ordnungsrelation , definiere die Möbius-Funktion von P rekursiv durch ${\displaystyle \leq}$${\displaystyle\mu}$

${\displaystyle \mu(s,s)=1{\text{ für }}s\in P,\qquad\mu(s,u)=-\sum_{s\leq t<u}\mu (s ,t),\quad {\text{ für }}s<u{\text{ in }}P.}$

(Hier geht man davon aus, dass die Summen endlich sind.) Dann gilt für , wo K ein kommutativer Ring ist, ${\displaystyle f,g:P\to K}$

${\displaystyle g(t)=\sum _{s\leq t}f(s)\qquad {\text{ für alle }}t\in P}$

dann und nur dann, wenn

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

(Siehe Stanleys Enumerative Combinatorics , Bd. 1, Abschnitt 3.7.)

Beiträge von Weisner, Hall und Rota

Die Aussage der allgemeinen Möbius-Inversionsformel [für teilgeordnete Mengen] wurde erstmals unabhängig von Weisner (1935) und Philip Hall (1936) gegeben; beide Autoren wurden durch gruppentheoretische Probleme motiviert. Keiner der Autoren scheint sich der kombinatorischen Implikationen seiner Arbeit bewusst gewesen zu sein und hat auch keine Theorie der Möbius-Funktionen entwickelt. In einer grundlegenden Arbeit über Möbius-Funktionen zeigte Rota die Bedeutung dieser Theorie in der kombinatorischen Mathematik auf und behandelte sie eingehend. Er stellte die Beziehung zwischen Themen wie Inklusion-Exklusion, klassische zahlentheoretische Möbius-Inversion, Farbprobleme und Strömungen in Netzwerken fest. Seitdem hat sich unter dem starken Einfluss von Rota die Theorie der Möbius-Inversion und verwandte Themen zu einem aktiven Gebiet der Kombinatorik entwickelt.

Siehe auch

Anmerkungen

Verweise

• Apostol, Tom M. (1976), Einführung in die analytische Zahlentheorie , Undergraduate Texts in Mathematics, New York-Heidelberg: Springer-Verlag, ISBN 978-0-387-90163-3, HERR  0434929 , Zbl  0335.10001
• Bender, Edward A.; Goldman, J. R. (1975), "Über die Anwendungen der Möbius-Inversion in der kombinatorischen Analyse" , Amer. Mathematik. Monatlich , 82 (8): 789–803, doi : 10.2307/2319793 , JSTOR  2319793
• Irland, K.; Rosen, M. (2010), A Classical Introduction to Modern Number Theory , Graduate Texts in Mathematics (Band 84) (2. Aufl.), Springer-Verlag, ISBN 978-1-4419-3094-1
• Kung, Joseph PS (2001) [1994], "Möbius-Inversion" , Enzyklopädie der Mathematik , 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), Enumerative Combinatorics , 1 , Cambridge University Press, ISBN 0-521-55309-1
• Stanley, Richard P. (1999), Enumerative Combinatorics , 2 , Cambridge University Press, ISBN 0-521-56069-1

Externe Links

• Möbius-Inversionsformel im ProofWiki
• Weisstein, Eric W. "Möbius-Transformation" . MathWorld .