Möbioův inverzní vzorec - Möbius inversion formula

v matematika, klasika Möbioův inverzní vzorec je vzorec pro získání podmínek nekonečného součtu. Bylo zavedeno do teorie čísel v roce 1832 August Ferdinand Möbius.^[1]

Velké zobecnění tohoto vzorce platí pro součet nad libovolným lokálně konečná částečně objednaná množina, přičemž Möbiovi klasický vzorec platí pro množinu přirozených čísel seřazených podle dělitelnosti: viz výskytová algebra.

Prohlášení o vzorci

Klasická verze uvádí, že pokud G a F jsou aritmetické funkce uspokojující

${displaystyle g (n) = součet _ {dmid n} f (d) quad {ext {pro každé celé číslo}} ngeq 1}$

pak

${displaystyle f (n) = součet _ {dmid n} mu (d) gleft ({frac {n} {d}} ight) quad {ext {pro každé celé číslo}} ngeq 1}$

kde μ je Möbiova funkce a částky přesahují všechny kladné hodnoty dělitele d z n (značeno pomocí ${displaystyle dmid n}$ ve výše uvedených vzorcích). Ve skutečnosti originál F(n) lze určit daný G(n) pomocí inverzního vzorce. O dvou sekvencích se říká, že jsou Möbius se transformuje navzájem.

Vzorec je také správný, pokud F a G jsou funkce od kladných celých čísel do některých abelianská skupina (zobrazeno jako ℤ-modul ).

V jazyce Dirichletovy závity, první vzorec může být napsán jako

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

kde ∗ označuje Dirichletovu konvoluci a 1 je konstantní funkce 1(n) = 1. Druhý vzorec je poté zapsán jako

${displaystyle f = mu * g.}$

Mnoho konkrétních příkladů je uvedeno v článku o multiplikativní funkce.

Věta následuje, protože ∗ je (komutativní a) asociativní a 1 ∗ μ = ε, kde ε je funkce identity pro Dirichletovu konvoluci, která bere hodnoty ε(1) = 1, ε(n) = 0 pro všechny n > 1. Tím pádem

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

K dispozici je verze produktu Möbiova inverzního vzorce založeného na součtu výše:

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

Sériové vztahy

Nechat

${displaystyle a_ {n} = součet _ {dmid n} b_ {d}}$

aby

${displaystyle b_ {n} = součet _ {dmid n} mu zbývá ({frac {n} {d}} večer) a_ {d}}$

je jeho transformace. Transformace souvisejí pomocí řady: Lambertova řada

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

a Dirichletova řada:

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

kde ζ(s) je Funkce Riemann zeta.

Opakované transformace

Vzhledem k aritmetické funkci lze generovat bi-nekonečnou sekvenci dalších aritmetických funkcí opakovaným použitím prvního součtu.

Například pokud jeden začíná na Eulerova totientová funkce φ, a opakovaně aplikuje proces transformace, získá:

1. φ funkce totient
2. φ ∗ 1 = Já, kde Já(n) = n je funkce identity
3. Já ∗ 1 = σ₁ = σ, funkce dělitele

Pokud je počáteční funkcí samotná Möbiova funkce, je seznam funkcí:

1. μ, Möbiova funkce
2. μ ∗ 1 = ε kde

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

   je funkce jednotky

3. ε ∗ 1 = 1, konstantní funkce
4. 1 ∗ 1 = σ₀ = d = τ, kde d = τ je počet dělitelů n, (viz funkce dělitele ).

Oba tyto seznamy funkcí se nekonečně rozšiřují v obou směrech. Möbioův inverzní vzorec umožňuje tyto seznamy procházet zpět.

Jako příklad posloupnost začínající na φ je:

${displaystyle f_ {n} = {egin {cases} underbrace {mu * ldots * mu} _ {- n {ext {faktory}}} * varphi & {ext {if}} n <0 [8px] varphi & { ext {if}} n = 0 [8px] varphi * underbrace {{mathit {1}} * ldots * {mathit {1}}} _ {n {ext {faktory}}} a {ext {if}} n > 0end {cases}}}$

Vygenerované sekvence lze snad snáze pochopit zvážením odpovídajících Dirichletova řada: každé opakované použití transformace odpovídá násobení pomocí Funkce Riemann zeta.

Zobecnění

Související inverzní vzorec užitečnější v kombinatorika je následující: předpokládejme F(X) a G(X) jsou komplex -hodnota funkce definované na interval [1,∞) takhle

${displaystyle G (x) = suma _ {1leq nleq x} Fleft ({frac {x} {n}} ight) quad {mbox {pro všechny}} xgeq 1}$

pak

${displaystyle F (x) = součet _ {1leq nleq x} mu (n) Gleft ({frac {x} {n}} ight) quad {mbox {pro všechny}} xgeq 1.}$

Zde součty přesahují všechna kladná celá čísla n které jsou menší nebo rovny X.

Toto je zase zvláštní případ obecnější formy. Li α(n) je aritmetická funkce vlastnit a Dirichlet inverzní α⁻¹(n), pak pokud jeden definuje

${displaystyle G (x) = součet _ {1leq nleq x} alpha (n) Fleft ({frac {x} {n}} ight) quad {mbox {pro všechny}} xgeq 1}$

pak

${displaystyle F (x) = součet _ {1leq nleq x} alpha ^ {- 1} (n) Gleft ({frac {x} {n}} ight) quad {mbox {pro všechny}} xgeq 1.}$

Předchozí vzorec vzniká ve zvláštním případě konstantní funkce α(n) = 1, jehož Dirichlet inverzní je α⁻¹(n) = μ(n).

Pokud máme funkce (s komplexními hodnotami), vyvstává konkrétní aplikace první z těchto rozšíření F(n) a G(n) definováno na kladných celých číslech, s

${displaystyle g (n) = součet _ {1leq mleq n} fleft (leftlfloor {frac {n} {m}} ightfloor ight) quad {mbox {pro všechny}} ngeq 1.}$

Definováním F(X) = F(⌊X⌋) a G(X) = G(⌊X⌋), odvodíme to

${displaystyle f (n) = součet _ {1leq mleq n} mu (m) gleft (leftlfloor {frac {n} {m}} ightfloor ight) quad {mbox {pro všechny}} ngeq 1.}$

Jednoduchým příkladem použití tohoto vzorce je počítání počtu redukované frakce 0 < A/b < 1, kde A a b jsou coprime a b ≤ n. Pokud to necháme F(n) tedy toto číslo G(n) je celkový počet zlomků 0 < A/b < 1 s b ≤ n, kde A a b nejsou nutně coprime. (Je to proto, že každý zlomek A/b s gcd (A,b) = d a b ≤ n lze zredukovat na zlomek A/d/b/d s b/d ≤ n/da naopak.) Zde je jednoduché určit G(n) = n(n − 1)/2, ale F(n) je těžší vypočítat.

Další inverzní vzorec je (kde předpokládáme, že zapojené řady jsou absolutně konvergentní):

${displaystyle g (x) = sum _ {m = 1} ^ {infty} {frac {f (mx)} {m ^ {s}}} quad {mbox {for all}} xgeq 1quad Longleftrightarrow quad f (x) = součet _ {m = 1} ^ {infty} mu (m) {frac {g (mx)} {m ^ {s}}} quad {mbox {pro všechny}} xgeq 1.}$

Jak je uvedeno výše, zobecňuje se to na případ, kdy α(n) je aritmetická funkce mající Dirichletovu inverzi α⁻¹(n):

${displaystyle g (x) = součet _ {m = 1} ^ {infty} alfa (m) {frac {f (mx)} {m ^ {s}}} quad {mbox {pro všechny}} xgeq 1quad Longleftrightarrow quad f (x) = součet _ {m = 1} ^ {infty} alpha ^ {- 1} (m) {frac {g (mx)} {m ^ {s}}} quad {mbox {pro všechny}} xgeq 1.}$

Například existuje dobře známý důkaz týkající se Funkce Riemann zeta do primární funkce zeta , který používá sériovou formu Möbiovy inverze v předchozí rovnici, když ${displaystyle s = 1}$. Jmenovitě Produkt Euler zastoupení ${displaystyle zeta (s)}$ pro ${displaystyle Re (s)> 1}$

${displaystyle log zeta (s) = - součet _ {pmathrm {prime}} protokol vlevo (1- {frac {1} {p ^ {s}}} ight) = součet _ {kgeq 1} {frac {P (ks )} {k}} iff P (s) = součet _ {kgeq 1} {frac {mu (k)} {k}} log zeta (ks), Re (s)> 1.}$

Tyto identity pro alternativní formy Möbiově inverze se nacházejí v ^[2]. Obecnější teorii Möbiových inverzních vzorců částečně citovaných v další části o incidenčních algebrách konstruuje Rota v ^[3].

Multiplikativní notace

Protože Möbiova inverze platí pro jakoukoli abelianskou skupinu, nezáleží na tom, zda je operace skupiny zapsána jako sčítání nebo jako násobení. To vede k následující notační variantě inverzního vzorce:

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

Důkazy zevšeobecnění

První zevšeobecnění lze prokázat následovně. Používáme Iversonova konvence že [podmínka] je indikátorová funkce podmínky, je 1, pokud je podmínka pravdivá, a 0, pokud je nepravdivá. Výsledek použijeme

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

to je 1 ∗ μ = i.

Máme následující:

${displaystyle {egin {aligned} součet _ {1leq nleq x} mu (n) gleft ({frac {x} {n}} ight) & = součet _ {1leq nleq x} mu (n) součet _ {1leq mleq { frac {x} {n}}} fleft ({frac {x} {mn}} ight) & = součet _ {1leq nleq x} mu (n) součet _ {1leq mleq {frac {x} {n}} } součet _ {1leq rleq x} [r = mn] fleft ({frac {x} {r}} ight) & = součet _ {1leq rleq x} fleft ({frac {x} {r}} ight) součet _ {1leq nleq x} mu (n) součet _ {1leq mleq {frac {x} {n}}} vlevo [m = {frac {r} {n}} ight] qquad {ext {přeskupit pořadí součtů}} & = součet _ {1leq rleq x} fleft ({frac {x} {r}} ight) součet _ {n | r} mu (n) & = součet _ {1leq rleq x} fleft ({frac {x } {r}} ight) i (r) & = f (x) qquad {ext {protože}} i (r) = 0 {ext {kromě případů}} r = 1end {zarovnáno}}}$

Důkaz v obecnějším případě, kde α(n) nahradí 1 je v podstatě identické, stejně jako druhá generalizace.

Na posety

Pro poset P, množina obdařená vztahem částečného řádu ${displaystyle leq}$, definujte Möbiovu funkci ${displaystyle mu}$ z P rekurzivně od

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

(Zde se předpokládá, že součty jsou konečné.) Pak pro ${displaystyle f, g: P o K}$, kde K. je pole, máme

${displaystyle g (t) = součet _ {sleq t} f (s) qquad {ext {pro všechny}} plechovka P}$

kdyby a jen kdyby

${displaystyle f (t) = součet _ {sleq t} g (s) mu (s, t) qquad {ext {pro všechny}} plech P.}$

(Viz Stanley's Enumerativní kombinatorika, Svazek 1, oddíl 3.7.)

Příspěvky Weisnera, Halla a Roty

Výrok obecného Möbiova inverzního vzorce [pro částečně uspořádané množiny] byl poprvé uveden nezávisle na Weisner (1935) a Philip Hall (1936); oba autoři byli motivováni problémy teorie skupin. Zdá se, že ani jeden autor nevěděl o kombinatorických důsledcích své práce a nerozvinul teorii Möbiových funkcí. V základním dokumentu o Möbiových funkcích Rota ukázal význam této teorie v kombinatorické matematice a podrobně ji popsal. Poznamenal vztah mezi tématy, jako je inkluze-exkluze, teoretická číselná Möbiova inverze, barevné problémy a toky v sítích. Od té doby se pod silným vlivem Roty stala teorie Möbiově inverze a souvisejících témat aktivní oblastí kombinatoriky.^[4]

Viz také

Poznámky

Reference

• Apostol, Tom M. (1976), Úvod do analytické teorie čísel„Pregraduální texty z matematiky, New York-Heidelberg: Springer-Verlag, ISBN  978-0-387-90163-3, PAN  0434929, Zbl  0335.10001
• Bender, Edward A .; Goldman, J. R. (1975), „K aplikacím Möbiově inverze v kombinatorické analýze“, Amer. Matematika. Měsíční, 82: 789–803, doi:10.2307/2319793
• Irsko, K .; Rosen, M. (2010), Klasický úvod do moderní teorie čísel„Postgraduální texty z matematiky (kniha 84) (2. vydání), Springer-Verlag, ISBN  978-1-4419-3094-1
• Kung, Joseph P.S. (2001) [1994], „Möbiova inverze“, Encyclopedia of Mathematics, Stiskněte EMS
• Möbius, A. F. (1832), „Über eine besondere Art von Umkehrung der Reihen.“, Journal für die reine und angewandte Mathematik, 9: 105–123
• Stanley, Richard P. (1997), Enumerativní kombinatorika, 1, Cambridge University Press, ISBN  0-521-55309-1
• Stanley, Richard P. (1999), Enumerativní kombinatorika, 2, Cambridge University Press, ISBN  0-521-56069-1

externí odkazy

• Möbioův inverzní vzorec na ProofWiki
• Weisstein, Eric W. „Möbiova transformace“. MathWorld.