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]

Legyen számelméleti függvény. Definiáljuk a számelméleti függvényt a

képlettel. Ekkor minden n-re

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:

a második képlet:

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

Bizonyítása[szerkesztés]

Felhasználjuk a

tulajdonságot.

Eszerint

Másként, a képlet következik a bból, hogy asszociatív és kommutatív, és , ahol a Dirichlet-konvolúció identitásfüggvénye, és így definiálható:

és minden -re.

Emiatt .

Relációk[szerkesztés]

Legyen

úgy, hogy

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

és a Dirichlet-sor:

ahol a Riemann-féle zéta-függvény.

Ismételt transzformációk[szerkesztés]

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 függvénnyel kezdve:

  1. az Euler-függvény
  2. ahol az identitásfüggvény
  3. , az osztóösszeg-függvény

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

  1. , a Möbius-függvény
  2. ahol az egységfüggvény
  3. , a konstans függvény
  4. , ahol 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 -vel indulva:

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]

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

,

akkor

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 számelméleti függvény Dirichlet-inverze , akkor

és

Ez az konstans függvény példáján látható a legjobban, aminek Dirichlet-inverze

.

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

Az és függvények bevezetésével:

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:

Ez szintén azt az esetet általánosítja, hogy számelméleti függvény, és Dirichlet-inverze :

Az általánosítások bizonyítása[szerkesztés]

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 , vagyis 1*μ=i.

Ezután így folytatjuk a számolást:

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

Források[szerkeszté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.