Möbius ters çevirme formülü - Möbius inversion formula

İçinde matematik, klasik Möbius ters çevirme formülü sonsuz bir toplamın koşullarını elde etmek için bir formüldür. Tanıtıldı sayı teorisi 1832'de Ağustos Ferdinand Möbius.^[1]

Bu formülün büyük bir genellemesi, keyfi bir formülün toplamı için geçerlidir. yerel olarak sonlu kısmen sıralı küme Bölünebilirlikle sıralanan doğal sayılar kümesine uygulanan Möbius'un klasik formülü ile: bkz. insidans cebiri.

Formülün ifadesi

Klasik versiyon, eğer g ve f vardır aritmetik fonksiyonlar doyurucu

${displaystyle g (n) = toplam _ {dmid n} f (d) quad {ext {her tam sayı için}} ngeq 1}$

sonra

${displaystyle f (n) = toplam _ {dmid n} mu (d) gleft ({frac {n} {d}} ight) quad {ext {her tam sayı için}} ngeq 1}$

nerede μ ... Möbius işlevi ve toplamlar tüm pozitiflere yayılır bölenler d nın-nin n (ile gösterilir ${displaystyle dmid n}$ yukarıdaki formüllerde). Aslında, orijinal f(n) verilen belirlenebilir g(n) ters çevirme formülünü kullanarak. İki dizinin olduğu söyleniyor Möbius dönüşümleri birbirinden.

Formül de doğrudur, eğer f ve g pozitif tamsayılardan bazılarına fonksiyonlardır değişmeli grup (bir ℤ-modül ).

Dilinde Dirichlet evrişimleri ilk formül şu şekilde yazılabilir:

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

nerede ∗ Dirichlet evrişimini belirtir ve 1 ... sabit fonksiyon 1(n) = 1. İkinci formül daha sonra şöyle yazılır

${displaystyle f = mu * g.}$

Makalede birçok özel örnek verilmiştir. çarpımsal fonksiyonlar.

Teorem şu nedenden dolayı ∗ (değişmeli ve) ilişkiseldir ve 1 ∗ μ = ε, nerede ε Dirichlet evrişimi için değer alan özdeşlik fonksiyonudur ε(1) = 1, ε(n) = 0 hepsi için n > 1. Böylece

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

Yukarıda belirtilen toplama tabanlı Möbius ters çevirme formülünün bir ürün sürümü vardır:

${displaystyle g (n) = prod _ {d | n} f (d) iff f (n) = prod _ {d | n} gleft ({frac {n} {d}} ight) ^ {mu (d) }, forall ngeq 1.}$

Seri ilişkileri

İzin Vermek

${displaystyle a_ {n} = toplam _ {dmid n} b_ {d}}$

Böylece

${displaystyle b_ {n} = toplam _ {dmid n} mu sol ({frac {n} {d}} ight) a_ {d}}$

dönüşümüdür. Dönüşümler, seriler aracılığıyla ilişkilidir: Lambert serisi

${displaystyle toplamı _ {n = 1} ^ {infty} a_ {n} x ^ {n} = toplam _ {n = 1} ^ {infty} b_ {n} {frac {x ^ {n}} {1- x ^ {n}}}}$

ve Dirichlet serisi:

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

nerede ζ(s) ... Riemann zeta işlevi.

Tekrarlanan dönüşümler

Bir aritmetik fonksiyon verildiğinde, ilk toplamı tekrar tekrar uygulayarak diğer aritmetik fonksiyonların iki sonsuz dizisini üretebilir.

Örneğin, biri şununla başlarsa Euler'in totient işlevi φve dönüşüm sürecini tekrar tekrar uygularsa elde edilen:

1. φ totient işlevi
2. φ ∗ 1 = ben, nerede ben(n) = n ... kimlik işlevi
3. ben ∗ 1 = σ₁ = σ, bölen işlevi

Başlangıç ​​işlevi Möbius işlevinin kendisiyse, işlevlerin listesi şöyledir:

1. μMöbius işlevi
2. μ ∗ 1 = ε nerede

   ${displaystyle varepsilon (n) = {egin {case} 1, & {mbox {if}} n = 1 0, & {mbox {if}} n> 1end {case}}}$

   ... birim işlevi

3. ε ∗ 1 = 1, sabit fonksiyon
4. 1 ∗ 1 = σ₀ = d = τ, nerede d = τ bölenlerin sayısı n, (görmek bölen işlevi ).

Bu işlev listelerinin her ikisi de her iki yönde sonsuza kadar uzanır. Möbius ters çevirme formülü, bu listelerin geriye doğru hareket etmesini sağlar.

Örnek olarak, ile başlayan dizi φ dır-dir:

${displaystyle f_ {n} = {egin {case} underbrace {mu * ldots * mu} _ {- n {ext {faktör}}} * varphi ve {ext {if}} n <0 [8px] varphi & { ext {if}} n = 0 [8px] varphi * underbrace {{mathit {1}} * ldots * {mathit {1}}} _ {n {ext {faktörler}}} & {ext {if}} n > 0 {vakaları}}} sonlandır$

Üretilen diziler, karşılık gelenler dikkate alınarak belki daha kolay anlaşılabilir. Dirichlet serisi: dönüşümün her tekrarlanan uygulaması, ile çarpmaya karşılık gelir Riemann zeta işlevi.

Genellemeler

İlgili bir ters çevirme formülü daha kullanışlı kombinatorik aşağıdaki gibidir: varsayalım F(x) ve G(x) vardır karmaşık değerli fonksiyonlar üzerinde tanımlanmış Aralık [1,∞) öyle ki

${displaystyle G (x) = toplam _ {1leq nleq x} Fleft ({frac {x} {n}} ight) dörtlü {mbox {tümü için}} xgeq 1}$

sonra

${displaystyle F (x) = toplam _ {1leq nleq x} mu (n) Gleft ({frac {x} {n}} ight) dörtlü {mbox {tümü için}} xgeq 1.}$

Burada toplamlar tüm pozitif tam sayıları kapsar n küçük veya eşit olan x.

Bu da daha genel bir şekle sahip özel bir durumdur. Eğer α(n) bir aritmetik fonksiyon sahip olmak Dirichlet ters α⁻¹(n), o zaman biri tanımlarsa

${displaystyle G (x) = toplam _ {1leq nleq x} alfa (n) Fleft ({frac {x} {n}} ight) dörtlü {mbox {tümü için}} xgeq 1}$

sonra

${displaystyle F (x) = toplam _ {1leq nleq x} alfa ^ {- 1} (n) Gleft ({frac {x} {n}} ight) dörtlü {mbox {hepsi için}} xgeq 1.}$

Önceki formül, sabit fonksiyonun özel durumunda ortaya çıkar α(n) = 1, kimin Dirichlet ters dır-dir α⁻¹(n) = μ(n).

Bu uzantılardan ilkinin belirli bir uygulaması, (karmaşık değerli) işlevlere sahipsek ortaya çıkar. f(n) ve g(n) pozitif tamsayılar üzerinde tanımlanmıştır

${displaystyle g (n) = toplam _ {1leq mleq n} fleft (sol kat {frac {n} {m}} ightfloor ight) dörtlü {mbox {tümü için}} ngeq 1.}$

Tanımlayarak F(x) = f(⌊x⌋) ve G(x) = g(⌊x⌋), bunu anlıyoruz

${displaystyle f (n) = toplam _ {1leq mleq n} mu (m) gleft (sol kat {frac {n} {m}} ightfloor ight) dörtlü {mbox {hepsi için}} ngeq 1.}$

Bu formülün kullanımına basit bir örnek, sayıları saymaktır. indirgenmiş kesirler 0 < a/b < 1, nerede a ve b coprime ve b ≤ n. İzin verirsek f(n) bu numara ol o zaman g(n) toplam kesir sayısı 0 < a/b < 1 ile b ≤ n, nerede a ve b coprime olması gerekmez. (Bunun nedeni, her fraksiyonun a/b ile gcd (a,b) = d ve b ≤ n kesire indirgenebilir a/d/b/d ile b/d ≤ n/dve tam tersi.) Burada karar vermek kolaydır. g(n) = n(n − 1)/2, fakat f(n) hesaplamak daha zordur.

Başka bir ters çevirme formülü şudur (burada yer alan serilerin kesinlikle yakınsak olduğunu varsayıyoruz):

${displaystyle g (x) = toplam _ {m = 1} ^ {infty} {frac {f (mx)} {m ^ {s}}} dörtlü {mbox {tümü için}} xgeq 1quad Longleftrightarrow dörtlü f (x) = toplam _ {m = 1} ^ {infty} mu (m) {frac {g (mx)} {m ^ {s}}} dörtlü {mbox {tümü için}} xgeq 1.}$

Yukarıdaki gibi, bu durum genelleşir α(n) Dirichlet tersine sahip bir aritmetik fonksiyondur α⁻¹(n):

${displaystyle g (x) = sum _ {m = 1} ^ {infty} alpha (m) {frac {f (mx)} {m ^ {s}}} quad {mbox {for all}} xgeq 1quad Longleftrightarrow quad f (x) = toplam _ {m = 1} ^ {infty} alfa ^ {- 1} (m) {frac {g (mx)} {m ^ {s}}} dörtlü {mbox {tümü için}} xgeq 1.}$

Örneğin, ile ilgili iyi bilinen bir kanıt var. Riemann zeta işlevi için asal zeta işlevi önceki denklemde Möbius inversiyonunun seri bazlı formunu kullanan ${displaystyle s = 1}$. Yani, tarafından Euler ürünü temsili ${ekran stili zetaları}$ için ${displaystyle Re (s)> 1}$

${displaystyle log zeta (s) = - toplam _ {pmathrm {asal}} log sola (1- {frac {1} {p ^ {s}}} ight) = toplam _ {kgeq 1} {frac {P (ks )} {k}} ancak P (s) = toplam _ {kgeq 1} {frac {mu (k)} {k}} log zeta (ks), Re (s)> 1.}$

Alternatif Möbius inversiyon formları için bu kimlikler, ^[2]. Bir sonraki bölümde insidans cebirleri üzerine kısmen alıntılanan daha genel bir Möbius inversiyon formülleri teorisi, Rota tarafından ^[3].

Çarpımsal gösterim

Möbius ters çevirme herhangi bir değişmeli grup için geçerli olduğundan, grup işleminin toplama olarak mı yoksa çarpma olarak mı yazıldığı fark etmez. Bu, ters çevirme formülünün aşağıdaki notasyonel varyantına yol açar:

${displaystyle {mbox {if}} F (n) = prod _ {d | n} f (d), {mbox {sonra}} f (n) = prod _ {d | n} Fleft ({frac {n} {d}} ight) ^ {mu (d)}.}$

Genellemelerin kanıtları

İlk genelleme şu şekilde ispatlanabilir. Kullanırız Iverson'ın kongresi Bu [koşul], koşulun gösterge işlevidir; koşul doğruysa 1, yanlışsa 0 olur. Sonucu kullanıyoruz ki

${displaystyle toplamı _ {d | n} mu (d) = i (n),}$

yani, 1 ∗ μ = ben.

Aşağıdakilere sahibiz:

${displaystyle {egin {hizalı} toplam _ {1leq nleq x} mu (n) gleft ({frac {x} {n}} ight) & = toplam _ {1leq nleq x} mu (n) toplam _ {1leq mleq { frac {x} {n}}} fleft ({frac {x} {mn}} ight) & = sum _ {1leq nleq x} mu (n) toplam _ {1leq mleq {frac {x} {n}} } toplam _ {1leq rleq x} [r = mn] fleft ({frac {x} {r}} ight) & = toplam _ {1leq rleq x} fleft ({frac {x} {r}} ight) toplamı _ {1leq nleq x} mu (n) toplam _ {1leq mleq {frac {x} {n}}} sol [m = {frac {r} {n}} ight] qquad {ext {toplama sırasını yeniden düzenleme}} & = toplam _ {1leq rleq x} fleft ({frac {x} {r}} ight) toplam _ {n | r} mu (n) & = toplam _ {1leq rleq x} fleft ({frac {x } {r}} ight) i (r) & = f (x) qquad {ext {beri}} i (r) = 0 {ext {hariç}} r = 1end {hizalı}}}$

Daha genel durumda kanıt α(n) 1'in yerini alır, ikinci genellemede olduğu gibi temelde aynıdır.

Posetlerde

Bir poset için Pkısmi bir düzen ilişkisi ile donatılmış bir küme ${displaystyle leq}$, Möbius işlevini tanımlayın ${displaystyle mu}$ nın-nin P yinelemeli olarak

${displaystyle mu (s, s) = 1 {ext {for}} sin P, qquad mu (s, u) = - toplam _ {sleq t$

(Burada toplamların sonlu olduğu varsayılır.) ${displaystyle f, g: P o K}$, nerede K bir alan, bizde

${displaystyle g (t) = sum _ {sleq t} f (s) qquad {ext {for all}} tin P}$

ancak ve ancak

${displaystyle f (t) = sum _ {sleq t} g (s) mu (s, t) qquad {ext {for all}} tin P.}$

(Stanley'in Numaralandırmalı Kombinatorik, Cilt 1, Kısım 3.7.)

Weisner, Hall ve Rota'nın katkıları

Genel Möbius ters çevirme formülünün ifadesi [kısmen sıralı kümeler için] ilk olarak bağımsız olarak verilmiştir. Weisner (1935) ve Philip Hall (1936); her iki yazar da grup teorisi problemleri tarafından motive edildi. Yazarlardan hiçbiri, çalışmalarının kombinatoryal sonuçlarının farkında değil ve Möbius fonksiyonları teorisini geliştirmemiş görünüyor. Möbius fonksiyonları üzerine temel bir makalede, Rota bu teorinin kombinatoryal matematikteki önemini göstermiş ve derinlemesine incelemesini vermiştir. Dahil etme-dışlama, klasik sayı teorik Möbius dönüşümü, renk problemleri ve ağlardaki akışlar gibi konular arasındaki ilişkiye dikkat çekti. O zamandan beri, Rota'nın güçlü etkisi altında, Möbius ters çevirme teorisi ve ilgili konular, kombinatoriklerin aktif bir alanı haline geldi.^[4]

Ayrıca bakınız

Notlar

Referanslar

• Apostol, Tom M. (1976), Analitik sayı teorisine giriş, Matematikte Lisans Metinleri, New York-Heidelberg: Springer-Verlag, ISBN  978-0-387-90163-3, BAY  0434929, Zbl  0335.10001
• Bender, Edward A .; Goldman, J.R. (1975), "Kombinatoryal analizde Möbius inversiyonunun uygulamaları hakkında", Amer. Matematik. Aylık, 82: 789–803, doi:10.2307/2319793
• İrlanda, K .; Rosen, M. (2010), Modern Sayı Teorisine Klasik Bir Giriş, Matematikte Lisansüstü Metinleri (Kitap 84) (2. baskı), Springer-Verlag, ISBN  978-1-4419-3094-1
• Kung, Joseph P.S. (2001) [1994], "Möbius dönüşümü", Matematik Ansiklopedisi, EMS Basın
• Möbius, A. F. (1832), "Über eine çok iyi Art von Umkehrung der Reihen.", Journal für die reine und angewandte Mathematik, 9: 105–123
• Stanley, Richard P. (1997), Numaralandırmalı Kombinatorik, 1, Cambridge University Press, ISBN  0-521-55309-1
• Stanley, Richard P. (1999), Numaralandırmalı Kombinatorik, 2, Cambridge University Press, ISBN  0-521-56069-1

Dış bağlantılar

• Möbius ters çevirme formülü ProofWiki'de
• Weisstein, Eric W. "Möbius Dönüşümü". MathWorld.