Voir la source de Formule d'inversion de Möbius

La '''formule d'inversion de Möbius''' classique a été introduite dans la [[théorie des nombres]] au cours du {{s-|XIX}} par [[August Ferdinand Möbius]]. Elle a été généralisée plus tard à d'autres « formules d'inversion de Möbius ».

== Énoncé ==
La version classique<ref name=Badiou3>{{article|auteur=Françoise Badiou|url=http://archive.numdam.org/ARCHIVE/SDPP/SDPP_1960-1961__2_/SDPP_1960-1961__2__A1_0/SDPP_1960-1961__2__A1_0.pdf|titre=Formule d'inversion de Möbius|périodique=Séminaire Delange-Pisot-Poitou Théorie des nombres|volume=2, exp. 1|année=1960|passage=3}}.</ref>{{,}}<ref>{{Ouvrage |langue=fr |langue originale=en |auteur1=[[Godfrey Harold Hardy|G. H. Hardy]] |auteur2=[[Edward Maitland Wright|E. M. Wright]] |traducteur=F. Sauvageot |titre=Introduction à la théorie des nombres |titre original=An Introduction to the Theory of Numbers |éditeur=[[Vuibert]]-[[Springer Verlag|Springer]] |lieu=Paris/Heidelberg |année=2007 |pages totales=568 |passage=301 |isbn=978-2-7117-7168-4}}, th. 266 et 267.</ref> déclare que pour toutes [[fonction arithmétique|fonctions arithmétiques]] {{mvar|f}} et {{mvar|g}}, on a
<center><math>\forall n\in\N^*\quad g(n)=\sum_{d\mid n}f(d)</math>
si et seulement si {{mvar|f}} est la '''transformée de Möbius''' de {{mvar|g}}, {{c.-à-d.}}
<math>\forall n\in\N^*\quad f(n)=\sum_{d\mid n}\mu(d)g(n/d)</math></center>

où {{mvar|μ}} est la [[fonction de Möbius]] et les sommes portent sur tous les [[diviseur]]s [[Nombre positif|strictement positifs]] {{mvar|d}} de {{mvar|n}}.

L'équivalence reste vraie si les fonctions {{mvar|f}} et {{mvar|g}} (définies sur l'ensemble ℕ* des [[Entier naturel|entiers strictement positifs]]) sont à valeurs dans un [[groupe abélien]] (vu comme [[Entier relatif|ℤ]]-[[Module sur un anneau|module]]).

== Preuve par convolution ==
=== Convolution de Dirichlet ===
On se place dans l'[[anneau commutatif]] ''F ''des fonctions arithmétiques, défini comme suit. L'ensemble ''F ''des fonctions arithmétiques est naturellement muni d'une addition qui en fait un [[groupe abélien]]. On le munit d'une deuxième [[loi interne]], la [[convolution de Dirichlet]], en associant à deux éléments ''f'' et ''g'' de ''F ''la fonction ''f''&nbsp;✻&nbsp;''g'' définie par :
<center><math>\forall n \in \N^* \quad (f*g) (n) = \sum_{d|n} f(d)g(n/d).</math></center>
Cette loi sur ''F ''est [[associativité|associative]], [[Commutativité|commutative]] et [[Distributivité|distributive]] par rapport à l'addition, et il existe un [[élément neutre]] : la fonction notée ici [[Symbole de Kronecker|δ{{ind|1}}]] et définie par δ{{ind|1}}(1) = 1 et pour tout entier ''n ''> 1, δ{{ind|1}}(''n'') = 0.

Le [[Groupe des unités|groupe des inversibles]] (''F''{{exp|×}}, ✻) de cet anneau est le groupe abélien constitué des fonctions ''f ''telles que ''f''(1) ≠ 0 (les  [[Fonction multiplicative|fonctions multiplicatives]] en forment un [[sous-groupe]]).

=== Démonstration ===
En notant '''1''' la [[fonction constante]] '''1'''(''n'') = 1, la formule d'inversion se réécrit :
<center><math>g=f*{\rm 1}\Leftrightarrow f=g*\mu</math>.</center>
Cette équivalence résulte<ref name=Badiou3/> de la [[Fonction de Möbius#Définition équivalente|définition de μ comme l'inverse de '''1''' pour la convolution ✻]] :
<center><math>{\rm 1}*\mu=\mu*{\rm 1}=\delta_1</math>,</center>
qui donne bien :
:<math>g=f*{\rm 1}\Rightarrow g*\mu=f*{\rm 1}*\mu=f*\delta_1=f</math>
et
:<math>f=g*\mu\Rightarrow f*{\rm 1}=g*\mu*{\rm 1}=g*\delta_1=g</math>.
Ces calculs restent valables pour ''f'' et ''g'' à valeurs dans un groupe abélien<ref>{{Ouvrage |langue=en |auteur1=Rudolf Lidl |auteur2={{Lien|Günter Pilz}} |titre=Applied Abstract Algebra |éditeur=[[Springer Verlag|Springer]] |année=1998 |passage=147 |isbn= |lire en ligne=https://books.google.fr/books?id=_49AmSWo4_AC&pg=PA147}}.</ref> (''G'', +) car le [[sous-anneau]] de ''F'' constitué des applications à valeurs entières contient μ et '''1''', et les applications de ℕ* dans ''G'' forment un [[Module sur un anneau#Module à gauche, module à droite|module à droite]] sur cet anneau, la [[loi externe]] étant la convolution définie par les mêmes formules.

== Généralisation et preuve combinatoire ==
=== Contexte ===
Une approche combinatoire permet de généraliser l'étude ci-dessus<ref name=Rota>{{en}} G.-C. Rota, « [http://www.maths.ed.ac.uk/~aar/papers/rota1.pdf On the foundations of combinatorial theory, I: Theory of Möbius functions] », ''Z. Wahrscheinlichkeitstheorie u. verw. Gebiete'', vol. 2, 1963, p. 340-368.</ref>. Soit ''A ''un [[Poset|ensemble partiellement ordonné]] dont la [[relation d'ordre]] est notée ≤. On définit les [[Chaîne (ordres)|chaînes]] par<ref name=IREM75>{{Ouvrage |nom1=[[IREM]] de Marseille |titre=Cours et activités en arithmétiques pour les classes terminales |éditeur= |année= |passage=75 |isbn= |lire en ligne=http://www.irem.univ-mrs.fr/IMG/pdf/arithmetique.pdf |id=IREM-Marseille}}.</ref> :

{{énoncé||Soient ''a'' et ''b ''deux éléments de ''A'' tels que ''a''&nbsp;≤&nbsp;''b''. Pour tout entier naturel ''p'', on appelle « chaîne de longueur ''p'' joignant ''a'' à ''b'' », toute suite finie (''x''<sub>0</sub>,&nbsp;''x''<sub>1</sub>,&nbsp;...,&nbsp;''x<sub>p</sub>'') telle que :
<center><math>a=x_0< x_1 < \cdots x_{p-1}< x_p=b,</math></center>
et l'on note ''c<sub>p</sub>''(''a'',&nbsp;''b'') le nombre de ces chaînes.}}

En supposant que l'ordre sur ''A ''est {{Lien|trad=Locally finite poset|Ordre partiel locallement fini|texte=localement fini}}, c'est-à-dire qu'il n'existe qu'un nombre fini d'éléments situés entre ''a'' et ''b'', [[Gian-Carlo Rota]] construit alors [[Fonction de Möbius#Définitions et propriétés élémentaires|une nouvelle ''fonction de Möbius'', qu'il note μ{{ind|''A''}}, caractérisée par]]<ref name=IREM76>{{harvsp|IREM-Marseille|p=76}}.</ref> :

{{énoncé||Soient ''a'' et ''b'' deux éléments de ''A'' tel que ''a ''< ''b'' :
<center><math>\mu_A(a,a)=1 \quad\text{et}\quad \sum_{a\le c\le b} \mu_A(a,c) = \sum_{a\le c\le b} \mu_A(c,b)=0,</math></center>}}

[[Fonction de Möbius#Relation entre la définition de Möbius et celle de Rota|Elle généralise la fonction de Möbius classique μ]]<ref>{{harvsp|IREM-Marseille|p=80}}.</ref> :

{{énoncé||2=Pour ''A ''= ℕ*, ordonné par « ''a''&nbsp;≤&nbsp;''b'' lorsque ''a'' est un diviseur de ''b'' », on a
<center><math>\forall a,b\in\N^*,\quad a\mid b\Rightarrow\mu_A(a,b)=\mu(b/a).</math></center>}}

=== Formule d'inversion de Rota ===
La fonction μ{{ind|''A''}} vérifie la formule d'inversion suivante<ref>{{harvsp|IREM-Marseille|p=77}}.</ref>, qui généralise celle pour μ :

{{énoncé||<center><math>\forall b\in A\quad g(b)=\sum_{a\le b}f(a) \quad\Longleftrightarrow\quad \forall b\in A\quad f(b)=\sum_{a\le b}g(a)\mu_A(a,b).</math></center>}}

En effet, le [[produit de convolution]] de Dirichlet se généralise, permettant d'associer à tout ordre localement fini ''A ''son {{Lien|trad=Incidence algebra|algèbre d'incidence}}, et μ{{ind|''A''}} s'interprète alors comme un inverse dans cet [[anneau unitaire]]. Ceci fournit ''in fine ''une preuve très courte — analogue à [[#Démonstration|celle donnée plus haut pour μ]] — de la formule d'inversion ci-dessus, mais nécessite de développer au préalable cette théorie<ref name=Rota/>{{,}}<ref name=Rolland/>, alors qu'un calcul direct est possible :

{{Démonstration|titre=Démonstration directe|contenu=
<center><math>\sum_{a \le b} g(a)\mu_A(a,b) = \sum_{a \le b} \left(\sum_{c \le a} f(c)\right) \mu_A(a,b)= \sum_{c \le b} f(c) \sum_{c\le a \le b} \mu_A(a,b).</math></center>

D'après la caractérisation de μ{{ind|''A''}}, les termes de droite sont tous nuls, sauf si ''c'' est égal à ''b'' ; ''a'' est alors aussi égal à ''b'' et μ<sub>''A''</sub>(''a'',&nbsp;''a'') est égal à 1, ce qui montre le résultat.
}}

En appliquant cette formule à d'autres ensembles partiellement ordonnés localement finis que celui des entiers strictement positifs ordonné par divisibilité, on obtient d'autres formules d'inversion de Möbius, comprenant entre autres le [[principe d'inclusion-exclusion de Moivre]].

Lorsque l'ordre utilisé est l'ordre usuel sur les entiers naturels non nuls, on obtient la formule suivante, utile en [[combinatoire]] :

si {{mvar|F}} et {{mvar|G}} sont deux fonctions définies sur l'intervalle {{math|[1, +∞[}} de ℝ à valeurs [[nombre complexe|complexes]] et si {{mvar|α}} et {{mvar|β}} sont deux fonctions arithmétiques inverses l'une de l'autre pour la convolution de Dirichlet (en particulier si {{math|1=''α'' = '''1'''}} et {{mvar|1=β = μ}}), alors<ref>{{Ouvrage |langue=en |auteur1=[[Tom M. Apostol]] |titre=Introduction to Analytic Number Theory |éditeur=[[Springer Verlag|Springer]] |collection={{Lien|Undergraduate Texts in Mathematics|texte=UTM}} |numéro dans collection=7 |année=1976 |pages totales=340 |passage=40 |isbn=978-0-387-90163-3 |lire en ligne={{Google Livres|Il64dZELHEIC|page=40}}}}, {{nobr|th. 2.22}}.</ref>
: <math>\forall x\ge 1 \quad G(x) = \sum_{1 \le n \le x}\alpha(n)F(x/n)\quad\Longleftrightarrow\quad\forall x\ge 1 \quad F(x) = \sum_{1 \le n \le x}\beta(n)G(x/n)</math>.

== Applications ==

Des exemples sont donnés dans l'article [[Fonction multiplicative]].
=== Arithmétique modulaire ===
{{Voir|Indicatrice d'Euler}}
[[Indicatrice d'Euler#Arithmétique modulaire|L'indicatrice d'Euler φ vérifie]] :
<center><math>\forall n\in \N^*\quad n=\sum_{d|n}\varphi(d)</math>.</center>
La formule d'inversion donne alors :
<center><math>\forall n\in\N^*\quad\varphi(n)=\sum_{d|n}\mu(d)\frac nd</math>.</center>

=== Polynôme cyclotomique ===
{{Voir|Polynôme cyclotomique}}
La formule d'inversion de Möbius est valable pour toute fonction ''f'' de '''N'''* dans un groupe abélien. Si ce groupe est noté multiplicativement, la formule devient :
<center><math>\text{si}\quad\forall n\in\N^*\quad g(n)=\prod_{d|n} f(d)\quad\text{alors}\quad\forall n\in\N^*\quad f(n)=\prod_{d|n}g(n/d)^{\mu(d)}.</math></center>
En prenant, comme groupe multiplicatif, celui des [[fraction rationnelle|fractions rationnelles]] non nulles à coefficients rationnels et, comme fonction ''f'', celle qui associe à tout entier ''n ''> 0 le ''n''{{e}} [[polynôme cyclotomique]] Φ{{ind|''n''}}, on obtient, en vertu de l'égalité
<center><math>X^n-1=\prod_{d|n}\Phi_d(X)</math></center>
un moyen de calculer le ''n''{{e}} polynôme cyclotomique :
<center><math>\Phi_n(X)=\prod_{d|n}(X^{n/d}- 1)^{\mu(d)}.</math></center>
Ces deux équations précisent celles du paragraphe précédent, qui correspondent au degré des polynômes en jeu.

=== Polynôme irréductible et corps fini ===
{{Voir|contenu=Paragraphe détaillé : « [[Corps fini#Un critère d'irréductibilité|Un critère d'irréductibilité]] », dans l'article sur les corps finis.}}
Certains [[code correcteur|codes correcteurs]], comme les [[code cyclique|codes cycliques]]<!--lien mort<ref>C. Bachoc ''[http://www.ufr-mi.u-bordeaux.fr/CSI/Cours/code.pdf Cours de code]'' Université Bordeaux I (2004) p 18</ref>--> sont construits à l'aide de l'anneau des [[polynôme]]s à coefficients dans le [[corps fini]] '''F'''<sub>''q''</sub> à ''q ''éléments et d'un [[polynôme irréductible]] et [[polynôme unitaire|unitaire]] de degré ''n''{{Refnec|date=août 2013|, où ''n'' est premier avec ''q''}}. C'est l'une des raisons pour lesquelles on s'intéresse au nombre ''m{{ind|n}}''(''q'') de polynômes irréductibles unitaires de degré ''n'' à coefficients dans '''F'''<sub>''q''</sub>. Cette question est un exemple de problème de dénombrement faisant intervenir la fonction de Möbius.

On démontre algébriquement que
<center><math>q^n=\sum_{d|n}d~m_d(q).</math></center>

Par inversion de Möbius, on en déduit<ref name=Rolland>R. Rolland, ''[http://www.acrypta.com/telechargements/DossierBoole/mobius2006.pdf Fonction de Möbius - Formule de Rota]'', [[CNRS]], Institut de mathématiques de [[Luminy]].</ref> :

<center><math>n~m_n(q)=\sum_{d|n}\mu(d)q^{n/d},\quad\text{i.e.}\quad m_n(q)=\frac 1n\sum_{d|n}\mu(d)q^{n/d}.</math></center>

== Notes et références ==
{{Traduction/Référence|en|Möbius inversion formula|6887713}}
{{Crédit d'auteurs|interne|Fonction de Möbius|95886168}}
{{Références|colonnes=2}}

== Articles connexes ==
*[[Transformée de Möbius]]<!--à fusionner ?-->
*[[Série de Lambert]]
*[[Série de Dirichlet]]

{{Portail|théorie des nombres}}

[[Catégorie:Arithmétique]]

[[ru:Функция Мёбиуса#Обращение Мёбиуса]]