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

Ez a szócikk a számelméleti fogalomról szól. Hasonló címmel lásd még: Möbius (egyértelműsítő lap).

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.

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

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

képlettel. Ekkor minden n-re

${\displaystyle 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:

${\displaystyle g=f*1}$

a második képlet:

${\displaystyle f=\mu *g.}$

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

Felhasználjuk a

${\displaystyle \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

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

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

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

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

Legyen

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

úgy, hogy

${\displaystyle 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

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

és a Dirichlet-sor:

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

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

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 ${\displaystyle \varphi }$ függvénnyel kezdve:

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

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

1. ${\displaystyle \mu }$, a Möbius-függvény
2. ${\displaystyle \mu *1=\varepsilon }$ ahol ${\displaystyle \varepsilon (n)={\begin{cases}1,&{\mbox{ha }}n=1\\0,&{\mbox{ha }}n>1\end{cases}}}$ az egységfüggvény
3. ${\displaystyle \varepsilon *1=1}$, a konstans függvény
4. ${\displaystyle 1*1=\sigma _{0}=\operatorname {d} =\tau }$, ahol ${\displaystyle \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 ${\displaystyle \varphi }$-vel indulva:

${\displaystyle 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.

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

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

akkor

${\displaystyle 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 ${\displaystyle \alpha (n)}$ számelméleti függvény Dirichlet-inverze ${\displaystyle \alpha ^{-1}(n)}$, akkor

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

és

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

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

${\displaystyle \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

${\displaystyle 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 ${\displaystyle F(x)=f(\lfloor x\rfloor )}$ és ${\displaystyle G(x)=g(\lfloor x\rfloor )}$ függvények bevezetésével:

${\displaystyle 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:

${\displaystyle 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 ${\displaystyle \alpha (n)}$ számelméleti függvény, és Dirichlet-inverze ${\displaystyle \alpha ^{-1}(n)}$:

${\displaystyle 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.}$

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 ${\displaystyle \sum _{d|n}\mu (d)=i(n)}$, vagyis 1*μ=i.

Ezután így folytatjuk a számolást: ${\displaystyle {\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.

• 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

• 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.