Formuła inwersji Möbiusa - Möbius inversion formula

W matematyce klasyczna formuła inwersji Möbiusa jest relacją między parami funkcji arytmetycznych , z których każda jest zdefiniowana przez sumy nad dzielnikami . Został wprowadzony do teorii liczb w 1832 roku przez Augusta Ferdynanda Möbiusa .

Duże uogólnienie tego wzoru odnosi się do sumowania nad dowolnym lokalnie skończonym zbiorem częściowo uporządkowanym , przy czym klasyczna formuła Möbiusa stosuje się do zbioru liczb naturalnych uporządkowanych według podzielności: patrz algebra padania .

Stwierdzenie wzoru

Wersja klasyczna stwierdza, że ​​jeśli g i ffunkcjami arytmetycznymi spełniającymi

następnie

gdzie μ jest funkcją Möbiusa i sumy rozciągają się na wszystkie pozytywne dzielnikami d o n (oznaczone w powyższych wzorach). W efekcie oryginalne f ( n ) można wyznaczyć na podstawie g ( n ) za pomocą wzoru inwersji. Mówi się, że te dwie sekwencje są wzajemnymi transformacjami Möbiusa .

Wzór jest również poprawny, jeśli f i g są funkcjami od liczb całkowitych dodatnich do jakiejś grupy abelowej ( rozumianej jako - moduł ).

W języku splotów Dirichleta pierwszą formułę można zapisać jako

gdzie oznacza splot Dirichleta, a 1 jest funkcją stałą 1 ( n ) = 1 . Druga formuła jest następnie zapisywana jako

W artykule o funkcjach multiplikatywnych podano wiele konkretnych przykładów .

Twierdzenie wynika, ponieważ jest (przemienne i) asocjacyjne, a 1μ = ε , gdzie ε jest funkcją tożsamości dla splotu Dirichleta, przyjmującą wartości ε (1) = 1 , ε ( n ) = 0 dla wszystkich n > 1 . Zatem

.

Istnieje wersja produktu opartej na sumowaniu formuły inwersji Möbiusa podanej powyżej:

Relacje seryjne

Pozwolić

aby

jest jego transformacją. Przekształcenia są powiązane szeregami: szereg Lamberta

oraz seria Dirichleta :

gdzie ζ ( s ) jest funkcją zeta Riemanna .

Powtarzające się transformacje

Mając daną funkcję arytmetyczną, można wygenerować bi-nieskończony ciąg innych funkcji arytmetycznych, wielokrotnie stosując pierwszą sumę.

Na przykład, jeśli zaczniemy od funkcji totient Eulera φ i wielokrotnie zastosujemy proces transformacji, otrzymamy:

  1. φ funkcja totient
  2. φ1 = I , gdzie I ( n ) = n jest funkcją tożsamościową
  3. I1 = σ 1 = σ , funkcja dzielnika

Jeśli funkcją początkową jest sama funkcja Möbiusa, lista funkcji to:

  1. μ , funkcja Möbiusa
  2. μ1 = ε gdzie
    jest funkcją jednostki?
  3. ε1 = 1 , stała funkcja
  4. 11 = σ 0 = d = τ , gdzie d = τ jest liczbą dzielników n , (patrz funkcja dzielnika ).

Obie te listy funkcji rozciągają się w nieskończoność w obu kierunkach. Formuła inwersji Möbiusa umożliwia przechodzenie tych list wstecz.

Jako przykład sekwencja zaczynająca się od φ to:

Wygenerowane sekwencje mogą być być może łatwiej zrozumiane przez rozważenie odpowiedniego szeregu Dirichleta : każde powtórzone zastosowanie transformacji odpowiada mnożeniu przez funkcję zeta Riemanna .

Uogólnienia

Pokrewny wzór inwersji, bardziej przydatny w kombinatoryce, jest następujący: załóżmy, że F ( x ) i G ( x )funkcjami o wartościach zespolonych zdefiniowanymi na przedziale [1,∞) takimi, że

następnie

Tutaj sumy rozciągają się na wszystkie dodatnie liczby całkowite n, które są mniejsze lub równe x .

To z kolei jest szczególnym przypadkiem o bardziej ogólnej formie. Jeśli α ( n ) jest funkcją arytmetyczną posiadającą odwrotność Dirichleta α -1 ( n ) , to jeśli zdefiniujemy

następnie

Poprzedni wzór pojawia się w szczególnym przypadku funkcji stałej α ( n ) = 1 , której odwrotność Dirichleta wynosi α- 1 ( n ) = μ ( n ) .

Szczególne zastosowanie pierwszego z tych rozszerzeń ma miejsce, gdy mamy (o wartościach zespolonych) funkcje f ( n ) i g ( n ) zdefiniowane na liczbach całkowitych dodatnich, przy czym

Definiując F ( x ) = f (⌊ x ⌋) i G ( x ) = g (⌊ x ⌋) dedukujemy , że

Prostym przykładem zastosowania tego wzoru jest liczenie liczby ułamków zredukowanych 0 < a/b< 1 , gdzie a i b są względnie pierwsze , a bn . Jeśli niech f ( n ) będzie tą liczbą, to g ( n ) jest całkowitą liczbą ułamków 0 <a/b<1 z bn , gdzie i b nie są koniecznie względnie pierwsze. (To dlatego, że każdy ułameka/bgdzie gcd( a , b ) = d i bn można zredukować do ułamkaa / d/b / d z b/Dn/Di vice versa.) Tutaj łatwo jest określić g ( n ) =n ( n − 1)/2, ale f ( n ) jest trudniejsze do obliczenia.

Innym wzorem inwersji jest (gdzie zakładamy, że szeregi są absolutnie zbieżne):

Jak wyżej, uogólnia to przypadek, w którym α ( n ) jest funkcją arytmetyczną posiadającą odwrotność Dirichleta α -1 ( n ) :

Na przykład, istnieje dobrze znany dowód łączący funkcję zeta Riemanna z pierwszą funkcją zeta, która wykorzystuje szeregową postać inwersji Möbiusa w poprzednim równaniu, gdy . Mianowicie, przez reprezentację produktu Eulera for

Te tożsamości dla alternatywnych form inwersji Möbiusa można znaleźć w. Bardziej ogólna teoria formuł inwersji Möbiusa, częściowo cytowana w następnej sekcji na temat algebr padania, została skonstruowana przez Rotę w.

Notacja multiplikatywna

Ponieważ inwersja Möbiusa dotyczy każdej grupy abelowej, nie ma znaczenia, czy operacja na grupie jest zapisana jako dodawanie czy mnożenie. Daje to początek następującemu wariantowi notacyjnemu formuły inwersji:

Dowody uogólnień

Pierwsze uogólnienie można wykazać w następujący sposób. Używamy konwencji Iversona, że [warunek] jest funkcją wskaźnika warunku, która wynosi 1, jeśli warunek jest prawdziwy, a 0, jeśli jest fałszywy. Używamy wyniku, który

czyli , gdzie jest funkcją jednostkową .

Mamy następujące:

Dowód w bardziej ogólnym przypadku, w którym α ( n ) zastępuje 1, jest zasadniczo identyczny, podobnie jak drugie uogólnienie.

Na postach

Dla posetu P , zbioru obdarzonego częściową relacją porządku , zdefiniuj funkcję Möbiusa z P rekursywnie przez

(Tutaj zakłada się, że sumy są skończone.) Wtedy dla , gdzie K jest pierścieniem przemiennym, mamy

wtedy i tylko wtedy gdy

(Patrz Enumerative Combinatorics Stanleya , tom 1, sekcja 3.7.)

Składki Weisnera, Halla i Rota

Stwierdzenie ogólnej formuły inwersji Möbiusa [dla zbiorów częściowo uporządkowanych] zostało po raz pierwszy podane niezależnie przez Weisnera (1935) i Philipa Halla (1936); obaj autorzy byli motywowani problemami teorii grup. Wydaje się, że żaden z autorów nie zdawał sobie sprawy z kombinatorycznych implikacji swojej pracy i nie rozwinął teorii funkcji Möbiusa. W fundamentalnym artykule na temat funkcji Möbiusa Rota wykazał znaczenie tej teorii w matematyce kombinatorycznej i szczegółowo ją potraktował. Zauważył związek między takimi tematami, jak inkluzja-wykluczenie, klasyczna teoria liczb inwersja Möbiusa, problemy z kolorowaniem i przepływy w sieciach. Od tego czasu, pod silnym wpływem Roty, teoria inwersji Möbiusa i związane z nią tematy stały się aktywnym obszarem kombinatoryki.

Zobacz też

Uwagi

Bibliografia

  • Apostol, Tom M. (1976), Wprowadzenie do analitycznej teorii liczb , Teksty licencjackie z matematyki , New York-Heidelberg: Springer-Verlag, ISBN 978-0-387-90163-3, MR  0434929 , Zbl  0335.10001
  • Bender, Edward A.; Goldman, JR (1975), „O zastosowaniach inwersji Möbiusa w analizie kombinatorycznej” , Amer. Matematyka. Miesięczny , 82 (8): 789–803, doi : 10.2307/2319793 , JSTOR  2319793
  • Irlandia, K.; Rosen, M. (2010), Klasyczne wprowadzenie do współczesnej teorii liczb , Teksty podyplomowe z matematyki (Księga 84) (2nd ed.), Springer-Verlag, ISBN 978-1-4419-3094-1
  • Kung, Joseph PS (2001) [1994], "inwersja Möbiusa" , Encyklopedia Matematyki , 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

Zewnętrzne linki