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

A Wikipédiából, a szabad enciklopédiából

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[szerkesztés | forrásszöveg szerkesztése]

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 befutjha 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[szerkesztés | forrásszöveg szerkesztése]

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 a bbó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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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

G(x) = \sum_{1 \le n \le x}F(x/n)\quad\mbox{ ha }x\ge 1,

akkor

F(x) = \sum_{1 \le n \le x}\mu(n)G(x/n)\quad\mbox{ 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)\quad\mbox{ ha }x\ge 1

és

F(x) = \sum_{1 \le n \le x}\alpha^{-1}(n)G(x/n)\quad\mbox{ 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(\left\lfloor \frac{n}{m}\right\rfloor\right)\quad\mbox{ 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(\left\lfloor \frac{n}{m}\right\rfloor\right)\quad\mbox{ 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 bn. 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 bn, é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 bn, akkor a tört tovább nem egyszerűsíthető alakja (a/d)/(b/d), ahol b/dn/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\ge 1\quad\Longleftrightarrow\quad
f(x) = \sum_{m=1}^\infty \mu(m)\frac{g(mx)}{m^s}\quad\mbox{ 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}^\infty \alpha(m)\frac{f(mx)}{m^s}\quad\mbox{ ha } x\ge 1\quad\Longleftrightarrow\quad
f(x) = \sum_{m=1}^\infty \alpha^{-1}(m)\frac{g(mx)}{m^s}\quad\mbox{ ha } x\ge 1.

Az általánosítások bizonyítása[szerkesztés | forrásszöveg szerkesztése]

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{align}
\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] \qquad\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) \qquad\text{mivel }i(r)=0\text{ kivéve, ha }r=1
\end{align}

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

Források[szerkesztés | forrásszöveg szerkesztése]

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.