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

Sablon:Egyért2 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)=\{\begin{array}{cc}1& \text{ ha }n=1\\ 0& \text{ ha }n>1\end{array}$

tulajdonságot.

Eszerint

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

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

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

Emiatt $\mu *g=\mu *(1*f)=(\mu *1)*f=ϵ*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}^{\mathrm{\infty }}{a}_n{x}^n=\sum _{n=1}^{\mathrm{\infty }}{b}_n\frac{x^n}{1-x^n}$

és a Dirichlet-sor:

$\sum _{n=1}^{\mathrm{\infty }}\frac{a_n}{n^s}=\zeta (s)\sum _{n=1}^{\mathrm{\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 $\phi$ függvénnyel kezdve:

1. $\phi$ az Euler-függvény
2. $\phi *1=\mathrm{Id}$ ahol $\mathrm{Id}(n)=n$ az identitásfüggvény
3. $\mathrm{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=\epsilon$ ahol $\epsilon (n)=\{\begin{array}{cc}1,& \text{ha }n=1\\ 0,& \text{ha }n>1\end{array}$ az egységfüggvény
3. $\epsilon *1=1$, a konstans függvény
4. $1*1={\sigma }_0=\mathrm{d}=\tau$, ahol $\mathrm{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 $\phi$-vel indulva:

$f_n=\{\begin{array}{cc}\underset{-n\text{ factors}}{\underbrace{\mu *\dots *\mu }}*\phi & \text{ha }n<0\\ \phi & \text{ha }n=0\\ \phi *\underset{n\text{ factors}}{\underbrace{1*\dots *1}}& \text{ha }n>0\end{array}$

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\le n\le x}F(x/n)\text{ ha }x\ge 1$,

akkor

$F(x)=\sum _{1\le n\le x}\mu (n)G(x/n)\text{ ha }x\ge 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\le n\le x}\alpha (n)F(x/n)\text{ ha }x\ge 1$

és

$F(x)=\sum _{1\le n\le x}{\alpha }^{-1}(n)G(x/n)\text{ ha }x\ge 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\le m\le n}f\left(\lfloor \frac{n}{m}\rfloor \right)\text{ hogyha }n\ge 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\le m\le n}\mu (m)g\left(\lfloor \frac{n}{m}\rfloor \right)\text{ ha }n\ge 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}^{\mathrm{\infty }}\frac{f(mx)}{m^s}\text{ ha }x\ge 1⟺f(x)=\sum _{m=1}^{\mathrm{\infty }}\mu (m)\frac{g(mx)}{m^s}\text{ ha }x\ge 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}^{\mathrm{\infty }}\alpha (m)\frac{f(mx)}{m^s}\text{ ha }x\ge 1⟺f(x)=\sum _{m=1}^{\mathrm{\infty }}{\alpha }^{-1}(m)\frac{g(mx)}{m^s}\text{ ha }x\ge 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{array}{cc}\sum _{1\le n\le x}\mu (n)g\left(\frac{x}{n}\right)& =\sum _{1\le n\le x}\mu (n)\sum _{1\le m\le x/n}f\left(\frac{x}{mn}\right)\\ & =\sum _{1\le n\le x}\mu (n)\sum _{1\le m\le x/n}\sum _{1\le r\le x}[r=mn]f\left(\frac{x}{r}\right)\\ & =\sum _{1\le r\le x}f\left(\frac{x}{r}\right)\sum _{1\le n\le x}\mu (n)\sum _{1\le m\le x/n}[m=r/n]\text{az összegzés sorrendjének megváltoztatásával}\\ & =\sum _{1\le r\le x}f\left(\frac{x}{r}\right)\sum _{n|r}\mu (n)\\ & =\sum _{1\le r\le x}f\left(\frac{x}{r}\right)i(r)\\ & =f(x)\text{mivel }i(r)=0\text{ kivéve, ha }r=1\end{array}$

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, Sablon:ISBN
• Sablon:SpringerEOM
• K. Ireland, M. Rosen. A Classical Introduction to Modern Number Theory, (1990) Springer-Verlag

Fordítás

• Sablon:Fordítás