Möbius inversionsformel

Inom matematiken är den klassiska Möbius-inversionsformeln en relation mellan par av aritmetiska funktioner , var och en definierad från den andra av summor över divisorer . Det introducerades i talteorin 1832 av August Ferdinand Möbius .

En stor generalisering av denna formel gäller summering över en godtycklig lokalt ändlig partiellt ordnad mängd , där Möbius klassiska formel gäller för mängden naturliga tal ordnade efter delbarhet: se incidensalgebra .

Uttalande av formeln

Den klassiska versionen säger att om $g$ och $f$ är aritmetiska funktioner som uppfyller

g(n)=\summa _{d\mid n}f(d)\quad {\text{för varje heltal } }n\geq 1

sedan

f(n)=\summa _{d\mid n}\mu (d)g\left( {\frac {n}{d}}\right)\quad {\text{för varje heltal }}n\geq 1

där $μ$ är Möbius-funktionen och summorna sträcker sig över alla positiva divisorer $d$ av $n$ (anges med $d\mid n$ i formlerna ovan). I själva verket kan den ursprungliga $f (n)$ bestämmas givet $g (n)$ genom att använda inversionsformeln. De två sekvenserna sägs vara Möbius-transformer av varandra.

Formeln är också korrekt om $f$ och $g$ är funktioner från de positiva heltal till någon abelsk grupp (sett som en $Z$ - modul ).

På språket Dirichlet convolutions kan den första formeln skrivas som

g={\mathit {1}}*f

där $*$ anger Dirichlet-faltningen, och $1$ är konstantfunktionen $1 (n) = 1$ . Den andra formeln skrivs då som

f=\mu *g.

Många specifika exempel ges i artikeln om multiplikativa funktioner .

Satsen följer eftersom $*$ är (kommutativ och) associativ, och $1 * μ = ε$ , där $ε$ är identitetsfunktionen för Dirichlet-faltningen, med värdena $ε (1) = 1$ , $ε (n) = 0$ för alla $n > 1$ . Således

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

.

Det finns en produktversion av den summeringsbaserade Möbius-inversionsformeln som anges ovan:

g(n)=\prod _{d|n}f(d)\iff f(n)=\prod _{d|n }g\left({\frac {n}{d}}\right)^{\mu (d)},\forall n\geq 1.

Serierelationer

Låta

a_{n}=\summa _{d\mid n}b_{d}

så att

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

är dess förvandling. Transformerna är relaterade med hjälp av serier: Lambert-serien

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

och Dirichlet-serien :

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

där $ζ (s)$ är Riemanns zeta-funktion .

Upprepade transformationer

Givet en aritmetisk funktion kan man generera en bi-oändlig sekvens av andra aritmetiska funktioner genom att upprepade gånger tillämpa den första summeringen.

Till exempel, om man börjar med Eulers totientfunktion $φ$ , och upprepade gånger tillämpar transformationsprocessen, får man:

$φ$ totientfunktionen
$φ * 1 = I$ , där $I (n) = n$ är identitetsfunktionen
$I * 1 = σ 1 = σ$ , divisorfunktionen

Om startfunktionen är själva Möbius-funktionen är listan över funktioner:

$μ$ , Möbius-funktionen
$μ * 1 = ε$ där $\varepsilon (n)={\begin{cases}1,&{\text{if }}n=1\\0,& {\text{if }}n>1\end{cases}}$ är enhetens funktion
$ε * 1 = 1$ , konstantfunktionen
$01 * 1 = σ = d = τ$ , där $d = τ$ är antalet divisorer för $n$ , (se divisorfunktion ) .

Båda dessa listor med funktioner sträcker sig oändligt åt båda hållen. Möbius-inversionsformeln gör det möjligt att förflytta dessa listor bakåt.

är sekvensen som börjar med $φ :$

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

De genererade sekvenserna kan kanske lättare förstås genom att överväga motsvarande Dirichlet-serie : varje upprepad tillämpning av transformationen motsvarar multiplikation med Riemanns zeta-funktion .

Generaliseringar

En relaterad inversionsformel som är mer användbar i kombinatorik är följande: anta att $F (x)$ och $G (x)$ är komplexa funktioner definierade på intervallet $[1, \infty)$ så att

G(x)=\summa _{1\leq n\leq x}F\left({\frac {x }{n}}\right)\quad {\mbox{ för alla }}x\geq 1

sedan

F(x)=\summa _{1\leq n\leq x}\mu (n )G\left({\frac {x}{n}}\right)\quad {\mbox{ för alla }}x\geq 1.

Här sträcker sig summorna över alla positiva heltal $n$ som är mindre än eller lika med $x$ .

Detta är i sin tur ett specialfall av mer allmän form. Om $α (n)$ är en aritmetisk funktion som har en Dirichlet invers $α -1 (n)$ , då om man definierar

G(x)=\summa _{1\leq n\leq x}\alpha (n) F\left({\frac {x}{n}}\right)\quad {\mbox{ för alla }}x\geq 1

sedan

F(x)=\summa _{1\leq n\leq x}\alpha ^{-1}(n)G\left({\frac {x}{n}}\right)\quad {\mbox{ för alla }}x\geq 1.

Den föregående formeln uppstår i specialfallet med konstantfunktionen $α (n) = 1$ , vars Dirichlet-invers är $α -1 (n) = μ (n)$ .

En speciell tillämpning av den första av dessa förlängningar uppstår om vi har (komplext värderade) funktioner $f (n)$ och $g (n)$ definierade på de positiva heltalen, med

g(n)=\summa _{1\leq m\leq n}f\left(\left(\left) \lfloor {\frac {n}{m}}\right\rfloor \right)\quad {\mbox{ för alla }}n\geq 1.

Genom att definiera $F (x) = f (⌊ x ⌋)$ och $G (x) = g (⌊ x ⌋)$ , härleder vi att

f(n)=\summa _{1\leq m\leq n}\mu (m)g\left(\left\lfloor {\frac {n}{m}}\right\rfloor \right)\quad {\mbox{ för alla }}n\geq 1.

Ett enkelt exempel på användningen av denna formel är att räkna antalet reducerade fraktioner $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px} 0 < a / b < 1$ , där $a$ och $b$ är coprime och $b \leq n$ . Om vi låter $f (n)$ vara detta tal, så är $g (n)$ det totala antalet bråk $0 < a / b < 1$ med $b \leq n$ , där $a$ och $b$ inte nödvändigtvis är coprime. (Detta beror på att varje bråkdel $a / b$ med $gcd(a, b) = d$ och $b \leq n$ kan reduceras till bråkdelen $a / d / b / d$ med $b / d \leq n / d$ , och vice versa.) Här det är enkelt att bestämma $g (n) = n (n - 1) / 2$ , men $f (n)$ är svårare att beräkna.

En annan inversionsformel är (där vi antar att de inblandade serierna är absolut konvergenta):

g(x)=\sum _{m=1}^{\infty }{\frac {f(mx)}{m^{s}}}\quad {\mbox{ för alla }}x\ geq 1\quad \Longleftrightarrow \quad f(x)=\sum _{m=1}^{\infty }\mu (m){\frac {g(mx)}{m^{s}}}\quad {\mbox{ för alla }}x\geq 1.

Som ovan generaliserar detta till fallet där $α (n)$ är en aritmetisk funktion som har en Dirichlet-invers $α -1 (n)$ :

g(x)=\sum _{m=1}^{\infty }\alpha (m){\frac {f(mx)}{m^{s}}}\ quad {\mbox{ för alla }}x\geq 1\quad \Longleftrightarrow \quad f(x)=\sum _{m=1}^{\infty }\alpha ^{-1}(m){\frac {g(mx)}{m^{s}}}\quad {\mbox{ för alla }}x\geq 1.

Till exempel finns det ett välkänt bevis som relaterar Riemann zeta-funktionen till prime zeta-funktionen som använder den seriebaserade formen av Möbius-inversion i föregående ekvation när $s=1$ . Nämligen genom Euler- produktrepresentationen av $\zeta (s)$ för $\Re (s)>1$

\log \zeta (s)=-\summa _{p\mathrm {\ prime} }\log \left(1-{\frac { 1}{p^{s}}}\right)=\summa _{k\geq 1}{\frac {P(ks)}{k}}\iff P(s)=\summa _{k\geq 1}{\frac {\mu (k)}{k}}\log \zeta (ks),\Re (s)>1.

Dessa identiteter för alternativa former av Möbius-inversion finns i. En mer allmän teori om Möbius-inversionsformler som delvis citeras i nästa avsnitt om incidensalgebror konstrueras av Rota i.

Multiplikativ notation

Eftersom Möbius-inversion gäller för vilken abelsk grupp som helst, gör det ingen skillnad om gruppoperationen skrivs som addition eller som multiplikation. Detta ger upphov till följande notationsvariant av inversionsformeln:

{\mbox{if }}F(n)=\prod _{d|n}f(d),{\mbox{ sedan }}f(n)=\prod _{d|n}F\ vänster({\frac {n}{d}}\höger)^{\mu (d)}.

Bevis på generaliseringar

Den första generaliseringen kan bevisas enligt följande. Vi använder Iversons konvention att [villkor] är indikatorfunktionen för villkoret, är 1 om villkoret är sant och 0 om falskt. Vi använder resultatet som

\sum _{d|n}\mu (d)=\varepsilon (n),

det vill säga $1*\mu =\varepsilon$ , där $\varepsilon$ är enhetsfunktionen .

Vi har följande:

{\begin{aligned}\sum _{ 1\leq n\leq x}\mu (n)g\left({\frac {x}{n}}\right)&=\summa _{1\leq n\leq x}\mu (n)\ summa _{1\leq m\leq {\frac {x}{n}}}f\left({\frac {x}{mn}}\right)\\&=\summa _{1\leq n\ leq x}\mu (n)\summa _{1\leq m\leq {\frac {x}{n}}}\summa _{1\leq r\leq x}[r=mn]f\left( {\frac {x}{r}}\right)\\&=\summa _{1\leq r\leq x}f\left({\frac {x}{r}}\right)\summa _{ 1\leq n\leq x}\mu (n)\summa _{1\leq m\leq {\frac {x}{n}}}\left[m={\frac {r}{n}}\ höger]\qquad {\text{omordna summeringsordningen}}\\&=\summa _{1\leq r\leq x}f\left({\frac {x}{r}}\right)\summa _ {n|r}\mu (n)\\&=\summa _{1\leq r\leq x}f\left({\frac {x}{r}}\right)\varepsilon (r)\\ &=f(x)\qquad {\text{sedan }}\varepsilon (r)=0{\text{ utom när }}r=1\end{aligned}}

Beviset i det mer allmänna fallet där $α (n)$ ersätter 1 är i huvudsak identiskt, liksom den andra generaliseringen.

På posetter

För en poset $P$ , en mängd som är utrustad med en partiell ordningsrelation $\leq$ , definiera Möbius-funktionen $\mu$ av $P$ rekursivt med

\mu (s,s)=1{\text{ för }}s\in P,\qquad \mu (s,u)=-\summa _{s\leq t<u}\mu (s ,t),\quad {\text{ för }}s<u{\text{ i }}P.

(Här antar man att summeringarna är ändliga.) Sedan för $f,g:P\to K$ , där $K$ är en kommutativ ring, har vi

g(t)=\summa _{s\leq t}f(s)\qquad {\text{ för alla }}t \i P

om och endast om

f(t)=\summa _{s\leq t}g(s)\mu (s,t)\qquad {\text{ för alla }}t\i P.

(Se Stanley's Enumerative Combinatorics , Vol 1, Avsnitt 3.7.)

Bidrag från Weisner, Hall och Rota

Uttalandet av den allmänna Möbius-inversionsformeln [för delvis ordnade uppsättningar] gavs först oberoende av Weisner (1935) och Philip Hall (1936); båda författarna motiverades av gruppteoretiska problem. Ingen av författaren tycks ha varit medveten om de kombinatoriska implikationerna av sitt arbete och inte heller utvecklat teorin om Möbiusfunktioner. I en grundläggande artikel om Möbius funktioner Rota vikten av denna teori i kombinatorisk matematik och gav en djupgående behandling av den. Han noterade sambandet mellan sådana ämnen som inkludering-uteslutning, klassisk talteoretisk Möbius-inversion, färgproblem och flöden i nätverk. Sedan dess, under starkt inflytande av Rota, har teorin om Möbius inversion och relaterade ämnen blivit ett aktivt område av kombinatorik.

Se även

Anteckningar

Apostol, Tom M. (1976), Introduktion till analytisk talteori , Undergraduate Texts in Mathematics, New York-Heidelberg: Springer-Verlag, ISBN 978-0-387-90163-3 , MR 0434929 , Zbl 03135.1000
Bender, Edward A.; Goldman, J.R. (1975), "On the applications of Möbius inversion in combinatorial analysis", Amer . Matematik. Monthly , 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 (Book 84) (2nd ed.), Springer-Verlag, ISBN 978-1-4419-3094-1
Kung, Joseph PS (2001) [1994], "Möbius inversion" , Encyclopedia of Mathematics , 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 , vol. 1, Cambridge University Press, ISBN 0-521-55309-1
Stanley, Richard P. (1999), Enumerative Combinatorics , vol. 2, Cambridge University Press, ISBN 0-521-56069-1

externa länkar

Möbius inversionsformel på ProofWiki
Weisstein, Eric W. "Möbius Transform" . MathWorld .