Möbioův inverzní vzorec

Möbius inverzní formule classic byl zaveden do teorie čísel v průběhu XIX -tého století August Ferdinand Möbius . Později byl zobecněn na jiné „Möbiovy inverzní vzorce“.

Státy

Klasické verze prohlašuje, že pro všechny aritmetické funkce $f$ a $g$ , máme

\ forall n \ in \ mathbb {N} ^ {*} \ quad g (n) = \ sum _ {{d \ mid n}} f (d)

tehdy a jen tehdy, pokud $f$ je Möbius transformace z $g$ , tj.

{\ displaystyle \ forall n \ in \ mathbb {N} ^ {*} \ quad f (n) = \ součet _ {d \ mid n} \ mu (d) g (n / d)}

kde $μ$ je Möbiova funkce a součty se vztahují ke všem přísně kladným dělitelům $d$ z $n$ .

Ekvivalence stále platí v případě, že funkce $f$ a $g$ (definované na množině ℕ * z přísně kladných celých čísel ) mají hodnoty v abelian skupiny (viděn jako ℤ - modul ).

Konvoluční důkaz

Dirichletova konvoluce

Umístíme se do komutativního kruhu F aritmetických funkcí, definovaného následovně. Sada F aritmetických funkcí je přirozeně opatřena přídavkem, který z ní činí abelianskou skupinu . Je opatřena druhým vnitřním zákona , na Dirichlet konvoluce , spojením s dvěma prvky f a g z F , jejichž funkce f ✻ g definovaný:

\ forall n \ in \ mathbb {N} ^ {*} \ quad (f * g) (n) = \ sum _ {{d | n}} f (d) g (n / d).

Tento zákon o F je asociativní , komutativní a distribuční s ohledem na sčítání a existuje neutrální prvek : funkce zde uvedená δ 1 a definovaná δ 1 (1) = 1 a pro jakékoli celé číslo n > 1, δ 1 ( n ) = 0.

Skupina invertibles ( F x , ✻) tohoto prstence je skupina abelian tvořena funkcí f tak, že f (1) ≠ 0 ( multiplikativní funkce tvoří podskupinu ).

Demonstrace

Poznámkou 1 konstantní funkce 1 ( n ) = 1, inverze vzorec je přepsána:

{\ displaystyle g = f * {\ rm {1}} \ šipka doleva f = g * \ mu}

Tato ekvivalence vyplývá z definice μ jako inverzní k 1 pro konvoluci ✻ :

{\ displaystyle {\ rm {1}} * \ mu = \ mu * {\ rm {1}} = \ delta _ {1}}

což dává dobře:

{\ displaystyle g = f * {\ rm {1}} \ Rightarrow g * \ mu = f * {\ rm {1}} * \ mu = f * \ delta _ {1} = f}

{\ displaystyle f = g * \ mu \ Rightarrow f * {\ rm {1}} = g * \ mu * {\ rm {1}} = g * \ delta _ {1} = g}

Tyto výpočty zůstávají v platnosti pro f a g s hodnotami v abelian skupiny ( G , +), protože dílčí prstenec z F skládá z mapování celočíselných obsahuje? A 1 , a mapování ℕ * v G tvoří právo modul na tomto kruhu, přičemž vnějším zákonem je konvoluce definovaná stejnými vzorci.

Zobecnění a kombinatorický důkaz

Kontext

Kombinatorický přístup umožňuje zobecnit výše uvedenou studii. Nechť A je částečně uspořádaná množina, jejíž pořadí je uvedeno ≤. Řetězce definujeme :

Nechť a a b jsou dva prvky A takové, že a ≤ b . Pro libovolné přirozené číslo p nazýváme „řetězec délky p spojující a až b “, jakoukoli konečnou posloupnost ( x 0 , x 1 , ..., x p ), která:

a = x_ {0} <x_ {1} <\ cdots x _ {{p-1}} <x_ {p} = b,

a označíme c p ( a , b ) počet těchto řetězců.

Za předpokladu, že pořadí na A je místně konečný (v) , to znamená, že existuje pouze omezený počet prvků, umístěných mezi a b , Gian-Carlo Rota poté vytvoří novou funkci Möbiovi , které zaznamená, u Stabilizátory A , vyznačující se tím, :

Nechť a a b jsou dva prvky A takové, že a < b :

\ mu _ {A} (a, a) = 1 \ quad {\ text {and}} \ quad \ sum _ {{a \ leq c \ leq b}} \ mu _ {A} (a, c) = \ sum _ {{a \ leq c \ leq b}} \ mu _ {A} (c, b) = 0,

Zobecňuje klasickou Möbiovu funkci μ :

Pro A = ℕ *, seřazené podle „ a ≤ b, když a je dělitel b “, máme

\ forall a, b \ in \ mathbb {N} ^ {*}, \ quad a \ mid b \ Rightarrow \ mu _ {A} (a, b) = \ mu (b / a).

Vzorec inverze Rota

Funkce μ A splňuje následující inverzní vzorec, který zobecňuje funkci pro μ:

{\ displaystyle \ forall b \ v A \ quad g (b) = \ součet _ {a \ leq b} f (a) \ quad \ Longleftrightarrow \ quad \ forall b \ v A \ quad f (b) = \ součet _ {a \ leq b} g (a) \ mu _ {A} (a, b).}

Ve skutečnosti Dirichletův konvoluční produkt zobecňuje, což umožňuje asociovat s jakýmkoli lokálně konečným řádem A jeho incidenční algebru (in) a μ A je pak v tomto jednotkovém kruhu interpretováno jako inverzní . To nakonec poskytuje velmi krátký důkaz - podobný tomu, který je uveden výše pro μ - výše uvedeného inverzního vzorce, ale vyžaduje to, aby byla nejprve vyvinuta tato teorie, zatímco je možný přímý výpočet:

Přímá ukázka

\ sum _ {{a \ leq b}} g (a) \ mu _ {A} (a, b) = \ sum _ {{a \ leq b}} \ left (\ sum _ {{c \ leq a }} f (c) \ right) \ mu _ {A} (a, b) = \ sum _ {{c \ leq b}} f (c) \ sum _ {{c \ leq a \ leq b}} \ mu _ {A} (a, b).

Podle charakterizace μ A jsou členy vpravo všechny nulové, kromě případů, kdy je c rovno b ; a se pak také rovná b a μ A ( a , a ) se rovná 1, což ukazuje výsledek.

Aplikováním tohoto vzorce na jiné částečně uspořádané lokálně konečné množiny než na striktně kladná celá čísla seřazená podle dělitelnosti získáme další Möbiovy inverzní vzorce, mimo jiné i Moivreův princip vyloučení a začlenění .

Když je použitým řádem obvyklé pořadí na nenulových přirozených celých číslech, získáme následující vzorec užitečný v kombinatorice :

jestliže $F$ a $G$ jsou dvě funkce definované na intervalu $[1, + \infty [$ of ℝ se složitými hodnotami a pokud $α$ a $β$ jsou dvě aritmetické funkce vzájemně inverzní pro Dirichletovu konvoluci (zejména pokud $α = 1$ a $β = μ$ ), pak

{\ displaystyle \ forall x \ geq 1 \ quad G (x) = \ součet _ {1 \ leq n \ leq x} \ alpha (n) F (x / n) \ quad \ Longleftrightarrow \ quad \ forall x \ geq 1 \ quad F (x) = \ sum _ {1 \ leq n \ leq x} \ beta (n) G (x / n)}

Aplikace

Příklady jsou uvedeny v článku Multiplikativní funkce .

Modulární aritmetika

Eulerův index φ kontroluje :

{\ displaystyle \ forall n \ in \ mathbb {N} ^ {*} \ quad n = \ sum _ {d | n} \ varphi (d)}

Vzorec inverze pak dává:

{\ displaystyle \ forall n \ in \ mathbb {N} ^ {*} \ quad \ varphi (n) = \ sum _ {d | n} \ mu (d) {\ frac {n} {d}}}

Cyklomtomický polynom

Inverzní vzorec Möbius je platné pro všechny funkce f o N * v abelian skupině. Pokud je tato skupina označena násobením, stane se vzorec:

{\ text {si}} \ quad \ forall n \ in \ mathbb {N} ^ {*} \ quad g (n) = \ prod _ {{d | n}} f (d) \ quad {\ text { then}} \ quad \ forall n \ in \ mathbb {N} ^ {*} \ quad f (n) = \ prod _ {{d | n}} g (n / d) ^ {{\ mu (d) }}.

Když vezmeme jako multiplikativní skupinu skupinu nenulových racionálních zlomků s racionálními koeficienty a jako funkci f funkci , která spojuje s jakýmkoli celým číslem n > 0, n- tý cyklotomický polynom Φ n , získáme na základě rovnosti

X ^ {n} -1 = \ prod _ {{d | n}} \ Phi _ {d} (X)

způsob výpočtu n- tého cyklotomického polynomu:

\ Phi _ {n} (X) = \ prod _ {{d | n}} (X ^ {{n / d}} - 1) ^ {{\ mu (d)}}.

Tyto dvě rovnice specifikují rovnice z předchozího odstavce, které odpovídají stupni polynomů ve hře.

Neredukovatelný polynom a konečné pole

Některé opravné kódy , jako jsou cyklické kódy, jsou konstruovány pomocí kruhu polynomů s koeficienty v konečném poli F q s prvky q a neredukovatelným a jednotným polynomem stupně n , kde n je prvočíslo s q . To je jeden z důvodů, proč nás zajímá počet m n ( q ) neredukovatelných jednotných polynomů stupně n s koeficienty ve F q . Tato otázka je příkladem problému počítání zahrnujícího Möbiovu funkci.

Algebraicky to dokazujeme

q ^ {n} = \ sum _ {{d | n}} d ~ m_ {d} (q).

Möbiově inverzí odvodíme:

n ~ m_ {n} (q) = \ sum _ {{d | n}} \ mu (d) q ^ {{n / d}}, \ quad {\ text {ie}} \ quad m_ {n} (q) = {\ frac 1n} \ sum _ {{d | n}} \ mu (d) q ^ {{n / d}}.

Poznámky a odkazy

(fr) Tento článek je částečně nebo zcela převzat z článku anglické Wikipedie s názvem „ Möbiova inverzní formule “ ( viz seznam autorů ) .

Tento článek je částečně nebo zcela převzat z článku s názvem „ Möbiova funkce “ (viz seznam autorů ) .

Françoise Badiou, „ Möbiova inverzní formule “, Delange-Pisot-Poitou Seminář Teorie čísel , sv. 2, zk. 1,1960, str. 3 ( číst online ).
GH Hardy a EM Wright ( přeloženo z angličtiny F. Sauvageotem), Úvod do teorie čísel [„ Úvod do teorie čísel “], Paříž / Heidelberg, Vuibert - Springer ,2007, 568 s. ( ISBN 978-2-7117-7168-4 ) , str. 301, th. 266 a 267.
(en) Rudolf Lidl a Günter Pilz (en) , Applied Abstract Algebra , Springer ,1998( číst online ) , s. 147.
(v) G.-C. Rota, „ Na základech kombinatorické teorie, I: Teorie Möbiových funkcí “, Z. Wahrscheinlichkeitstheorie u. verw. Gebiete , sv. 2, 1963, str. 340-368.
IREM z Marseille , Kurzy a aktivity v aritmetice pro závěrečné kurzy ( číst online ) , s. 75.
IREM-Marseille , str. 76.
IREM-Marseille , str. 80.
IREM-Marseille , str. 77.
R. Rolland, Möbiova funkce - Rotaův vzorec , CNRS , Luminy Mathematics Institute .
(in) Tom M. Apostol , Introduction to Analytic Number Theory , Springer , al. " UTM (en) " ( n o 7),1976, 340 s. ( ISBN 978-0-387-90163-3 , číst online ) , s. 40, th. 2.22 .

Související články