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 f są funkcjami 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:
- φ funkcja totient
- φ ∗ 1 = I , gdzie I ( n ) = n jest funkcją tożsamościową
- I ∗ 1 = σ 1 = σ , funkcja dzielnika
Jeśli funkcją początkową jest sama funkcja Möbiusa, lista funkcji to:
- μ , funkcja Möbiusa
-
μ ∗ 1 = ε gdzie
- jest funkcją jednostki?
- ε ∗ 1 = 1 , stała funkcja
- 1 ∗ 1 = σ 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 ) są 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 b ≤ n . Jeśli niech f ( n ) będzie tą liczbą, to g ( n ) jest całkowitą liczbą ułamków 0 <a/b<1 z b ≤ n , gdzie i b nie są koniecznie względnie pierwsze. (To dlatego, że każdy ułameka/bgdzie gcd( a , b ) = d i b ≤ n można zredukować do ułamkaa / d/b / d z b/D ≤ n/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