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 Modèle:S mini- siècleModèle:Vérification siècle 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>Modèle:Article.</ref><ref>Modèle:Ouvrage, th. 266 et 267.</ref> déclare que pour toutes fonctions arithmétiques Modèle:Mvar et Modèle:Mvar, on a

<math>\forall n\in\N^*\quad g(n)=\sum_{d\mid n}f(d)</math>

si et seulement si Modèle:Mvar est la transformée de Möbius de Modèle:Mvar, Modèle:C.-à-d.

<math>\forall n\in\N^*\quad f(n)=\sum_{d\mid n}\mu(d)g(n/d)</math>

où Modèle:Mvar est la fonction de Möbius et les sommes portent sur tous les diviseurs strictement positifs Modèle:Mvar de Modèle:Mvar.

L'équivalence reste vraie si les fonctions Modèle:Mvar et Modèle:Mvar (définies sur l'ensemble ℕ* des entiers strictement positifs) sont à valeurs dans un groupe abélien (vu comme ℤ-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 ✻ g définie par :

<math>\forall n \in \N^* \quad (f*g) (n) = \sum_{d|n} f(d)g(n/d).</math>

Cette loi sur F est associative, commutative et distributive par rapport à l'addition, et il existe un élément neutre : la fonction notée ici δ₁ et définie par δ₁(1) = 1 et pour tout entier n > 1, δ₁(n) = 0.

Le groupe des inversibles (F^×, ✻) de cet anneau est le groupe abélien constitué des fonctions f telles que f(1) ≠ 0 (les 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 :

<math>g=f*{\rm 1}\Leftrightarrow f=g*\mu</math>.

Cette équivalence résulte<ref name=Badiou3/> de la définition de μ comme l'inverse de 1 pour la convolution ✻ :

<math>{\rm 1}*\mu=\mu*{\rm 1}=\delta_1</math>,

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>Modèle:Ouvrage.</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 à 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>{{#invoke:Langue|indicationDeLangue}} G.-C. Rota, « 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 ensemble partiellement ordonné dont la relation d'ordre est notée ≤. On définit les chaînes par<ref name=IREM75>Modèle:Ouvrage.</ref> :

En supposant que l'ordre sur A est Modèle:Lien, 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 une nouvelle fonction de Möbius, qu'il note μ_A, caractérisée par<ref name=IREM76>Modèle:Harvsp.</ref> :

Elle généralise la fonction de Möbius classique μ<ref>Modèle:Harvsp.</ref> :

Formule d'inversion de Rota

La fonction μ_A vérifie la formule d'inversion suivante<ref>Modèle:Harvsp.</ref>, qui généralise celle pour μ :

En effet, le produit de convolution de Dirichlet se généralise, permettant d'associer à tout ordre localement fini A son Modèle:Lien, et μ_A s'interprète alors comme un inverse dans cet anneau unitaire. Ceci fournit in fine une preuve très courte — analogue à 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 :

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 Modèle:Mvar et Modèle:Mvar sont deux fonctions définies sur l'intervalle Modèle:Math de ℝ à valeurs complexes et si Modèle:Mvar et Modèle:Mvar sont deux fonctions arithmétiques inverses l'une de l'autre pour la convolution de Dirichlet (en particulier si Modèle:Math et Modèle:Mvar), alors<ref>Modèle:Ouvrage, Modèle:Nobr.</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

Modèle:Voir L'indicatrice d'Euler φ vérifie :

<math>\forall n\in \N^*\quad n=\sum_{d|n}\varphi(d)</math>.

La formule d'inversion donne alors :

<math>\forall n\in\N^*\quad\varphi(n)=\sum_{d|n}\mu(d)\frac nd</math>.

Polynôme cyclotomique

Modèle:Voir 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 :

<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>

En prenant, comme groupe multiplicatif, celui des fractions rationnelles non nulles à coefficients rationnels et, comme fonction f, celle qui associe à tout entier n > 0 le n^e polynôme cyclotomique Φ_n, on obtient, en vertu de l'égalité

<math>X^n-1=\prod_{d|n}\Phi_d(X)</math>

un moyen de calculer le n^e polynôme cyclotomique :

<math>\Phi_n(X)=\prod_{d|n}(X^{n/d}- 1)^{\mu(d)}.</math>

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

Modèle:Voir Certains codes correcteurs, comme les codes cycliques sont construits à l'aide de l'anneau des polynômes à coefficients dans le corps fini F_q à q éléments et d'un polynôme irréductible et unitaire de degré nModèle:Refnec. C'est l'une des raisons pour lesquelles on s'intéresse au nombre m_n(q) de polynômes irréductibles unitaires de degré n à coefficients dans F_q. Cette question est un exemple de problème de dénombrement faisant intervenir la fonction de Möbius.

On démontre algébriquement que

<math>q^n=\sum_{d|n}d~m_d(q).</math>

Par inversion de Möbius, on en déduit<ref name=Rolland>R. Rolland, Fonction de Möbius - Formule de Rota, CNRS, Institut de mathématiques de Luminy.</ref> :

<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>

Articles connexes

• Transformée de Möbius
• Série de Lambert
• Série de Dirichlet