Möbius-féle megfordítási formula

Möbius-féle megfordítási formula a matematikában, ezen belül a számelméletben a Möbius-függvény egyik legfontosabb tulajdonságát kimondó képlet. A klasszikus formulát a 19. században alkotta meg August Ferdinand Möbius.

Hasonló képletek kaphatók lokálisan véges részben rendezett halmazok felhasználásával. Lásd: illeszkedési algebra.

Az állítás

Legyen $f(n)$ számelméleti függvény. Definiáljuk a $g(n)$ számelméleti függvényt a

$g(n)=\sum _{d|n}f(d)$

képlettel. Ekkor minden n-re

$f(n)=\sum _{d|n}\mu (d)g\left({\frac {n}{d}}\right)$

teljesül, ahol μ a Möbius-függvény, és az összegzés befutja n pozitív osztóit. A két függvényt egymás Möbius-transzformáltjának nevezik.

Általánosabban, a képlet akkor is működik, ha az f és g függvények a pozitív egészek helyett egy másik Abel-csoportba képeznek.

A Dirichlet-konvolúció jelölésével az első képlet:

$g=f*1$

a második képlet:

$f=\mu *g.$

ahol 1 a konstans 1 függvény, és * a Dirichlet-konvolúció.

Bizonyítása

Felhasználjuk a

$\sum _{d|n}\mu (d)=\delta (n)=\left\{{\begin{matrix}1&{\mbox{ ha }}n=1\\0&{\mbox{ ha }}n>1\end{matrix}}\right.$

tulajdonságot.

Eszerint

$\sum _{d|n}\mu (d)g\left({\frac {n}{d}}\right)=$ $\sum _{d|n}\mu (d)\sum _{d'|{\frac {n}{d}}}f(d')=\sum _{d'|n}f(d')\sum _{d|{\frac {n}{d'}}}\mu (d)=$ $\sum _{d'|n}f(d')\delta \left({\frac {n}{d'}}\right)=f(n).$

Másként, a képlet következik abból, hogy $*$ asszociatív és kommutatív, és $1*\mu =\epsilon$, ahol $\epsilon$ a Dirichlet-konvolúció identitásfüggvénye, és így definiálható:

$\epsilon (1)=1,$ és $\epsilon (n)=0$ minden $n>1$-re.

Emiatt $\mu *g=\mu *(1*f)=(\mu *1)*f=\epsilon *f=f$.

Relációk

Legyen

$a_{n}=\sum _{d\mid n}b_{d}$

úgy, hogy

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

a transzformációja. A transzformáció a sorok segítségével elvégezhető: a Lambert-sor

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

és a Dirichlet-sor:

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

ahol $\zeta (s)$ a Riemann-féle zéta-függvény.

Ismételt transzformációk

Egy adott számtani függvényből függvények egy mindkét irányban végtelen sorozata kapható az összegzési és a megfordítási képletek többszöri alkalmazásával.

Például a $\varphi$ függvénnyel kezdve:

1. $\varphi$ az Euler-függvény
2. $\varphi *1=\operatorname {Id}$ ahol $\operatorname {Id} (n)=n$ az identitásfüggvény
3. $\operatorname {Id} *1=\sigma _{1}=\sigma$, az osztóösszeg-függvény

A Möbius-függvénnyel kezdve:

1. $\mu$, a Möbius-függvény
2. $\mu *1=\varepsilon$ ahol $\varepsilon (n)={\begin{cases}1,&{\mbox{ha }}n=1\\0,&{\mbox{ha }}n>1\end{cases}}$ az egységfüggvény
3. $\varepsilon *1=1$, a konstans függvény
4. $1*1=\sigma _{0}=\operatorname {d} =\tau$, ahol $\operatorname {d} =\tau$ az n osztóinak számát adja meg.

Mindegyik lista folytatható mindkét irányba a Möbius-féle megfordítási formula felhasználásával:

Például $\varphi$-vel indulva:

$f_{n}={\begin{cases}\underbrace {\mu *\ldots *\mu } _{-n{\text{ factors}}}*\varphi &{\text{ha }}n<0\\\varphi &{\text{ha }}n=0\\\varphi *\underbrace {1*\ldots *1} _{n{\text{ factors}}}&{\text{ha }}n>0\end{cases}}$

A Dirichlet-sorok segíthetnek megérteni ezeket a függvényeket. A transzformáció minden egyes alkalmazása megfelel a Riemann-féle zéta-függvénnyel való szorzásnak.

Általánosítások

Egy leginkább a kombinatorikában használt hasonló megfordítási képlet a következő: Legyen F(x) és G(x) az [1,∞) intervallumon értelmezett komplex értékű függvény. Ekkor, hogyha

$G(x)=\sum _{1\leq n\leq x}F(x/n)\quad {\mbox{ ha }}x\geq 1$,

akkor

$F(x)=\sum _{1\leq n\leq x}\mu (n)G(x/n)\quad {\mbox{ ha }}x\geq 1.$

Itt az összegzés minden pozitív egészre megy, ami kisebb vagy egyenlő, mint x.

Ez egy még általánosabb képlet speciális esete. Ha az $\alpha (n)$ számelméleti függvény Dirichlet-inverze $\alpha ^{-1}(n)$, akkor

$G(x)=\sum _{1\leq n\leq x}\alpha (n)F(x/n)\quad {\mbox{ ha }}x\geq 1$

és

$F(x)=\sum _{1\leq n\leq x}\alpha ^{-1}(n)G(x/n)\quad {\mbox{ ha }}x\geq 1.$

Ez az $\alpha (n)=1$ konstans függvény példáján látható a legjobban, aminek Dirichlet-inverze

$\alpha ^{-1}(n)=\mu (n)$.

Az első kiterjesztés részleges alkalmazása az f(n) és g(n) pozitív egészeken értelmezett komplex értékű függvényekre, ahol

$g(n)=\sum _{1\leq m\leq n}f\left(\left\lfloor {\frac {n}{m}}\right\rfloor \right)\quad {\mbox{ hogyha }}n\geq 1.$

Az $F(x)=f(\lfloor x\rfloor )$ és $G(x)=g(\lfloor x\rfloor )$ függvények bevezetésével:

$f(n)=\sum _{1\leq m\leq n}\mu (m)g\left(\left\lfloor {\frac {n}{m}}\right\rfloor \right)\quad {\mbox{ ha }}n\geq 1.$

A képlet egy egyszerű felhasználási példája a tovább nem egyszerűsíthető törtek megszámlálását, ha 0 < a/b < 1 és b≤n. EZ azt is jelenti, hogy a számláló és a nevező relatív prímek. Jelöljük ezt a számot f(n)-nel. Ekkor a fenti számításokkal kapott g(n) azoknak a törteknek a száma, amelyekre b≤n, és a számláló és a nevező nem feltétlenül relatív prím. Ez így látható be: Ha az a/b törtben a és b legnagyobb közös osztója d, és b≤n, akkor a tört tovább nem egyszerűsíthető alakja (a/d)/(b/d), ahol b/d ≤ n/d. Innen már egyszerű, hogy g(n) = n(n-1)/2, de f(n) nehezebben számítható.

Egy másik megfordítási képlet, ha a benne szereplő sorok abszolút folytonosak:

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

Ez szintén azt az esetet általánosítja, hogy $\alpha (n)$ számelméleti függvény, és Dirichlet-inverze $\alpha ^{-1}(n)$:

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

Az általánosítások bizonyítása

A következőkben Iverson konvencióját használjuk, ami szerint az igaz számértéke 1, a hamis számértéke 0. Az első általánosítás bizonyításához felhasználjuk, hogy $\sum _{d|n}\mu (d)=i(n)$, vagyis 1*μ=i.

Ezután így folytatjuk a számolást: ${\begin{aligned}\sum _{1\leq n\leq x}\mu (n)g\left({\frac {x}{n}}\right)&=\sum _{1\leq n\leq x}\mu (n)\sum _{1\leq m\leq x/n}f\left({\frac {x}{mn}}\right)\\&=\sum _{1\leq n\leq x}\mu (n)\sum _{1\leq m\leq x/n}\sum _{1\leq r\leq x}[r=mn]f\left({\frac {x}{r}}\right)\\&=\sum _{1\leq r\leq x}f\left({\frac {x}{r}}\right)\sum _{1\leq n\leq x}\mu (n)\sum _{1\leq m\leq x/n}[m=r/n]\qquad {\text{az összegzés sorrendjének megváltoztatásával}}\\&=\sum _{1\leq r\leq x}f\left({\frac {x}{r}}\right)\sum _{n|r}\mu (n)\\&=\sum _{1\leq r\leq x}f\left({\frac {x}{r}}\right)i(r)\\&=f(x)\qquad {\text{mivel }}i(r)=0{\text{ kivéve, ha }}r=1\end{aligned}}$

A második általánosítás hasonlóan bizonyítható, kivéve hogy a konstans 1 helyett α(n) szerepel.

Források

• Apostol, Tom M. (1976), Introduction to analytic number theory, Undergraduate Texts in Mathematics, New York-Heidelberg: Springer-Verlag, ISBN 978-0-387-90163-3
• Sablon:SpringerEOM
• K. Ireland, M. Rosen. A Classical Introduction to Modern Number Theory, (1990) Springer-Verlag

Fordítás

• Ez a szócikk részben vagy egészben a Möbius inversion formula című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.