Formule d'inversion de Möbius

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

La formule d'inversion de Möbius classique a été introduite dans la théorie des nombres au cours du XIXe 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é[modifier | modifier le code]

La version classique[1] déclare que si f et g sont des fonctions arithmétiques vérifiant

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

alors

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

où μ est la fonction de Möbius et les sommes portent sur tous les diviseurs strictement positifs d de n. La formule reste valable si f et g sont des fonctions définies sur l'ensemble ℕ* des entiers strictement positifs à valeurs dans un groupe abélien (vu comme -module).

Preuve par convolution[modifier | modifier le code]

Convolution de Dirichlet[modifier | modifier le code]

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 :

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

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 δ1 et définie par δ1(1) = 1 et pour tout entier n > 1, δ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[modifier | modifier le code]

En notant 1 la fonction constante 1(n) = 1, la formule d'inversion se réécrit :

g=f*{\rm 1}\Rightarrow f=g*\mu.

Cette formule pour f quelconque peut se déduire du cas particulier où f est la fonction δ1. En effet, μ est l'inverse de 1 pour la convolution ✻ :

{\rm 1}*\mu=\delta_1.

On a donc bien :

g=f*{\rm 1}\Rightarrow g*\mu=f*{\rm 1}*\mu=f*\delta_1=f.

Généralisation et preuve combinatoire[modifier | modifier le code]

Contexte[modifier | modifier le code]

Une approche combinatoire permet de généraliser l'étude ci-dessus[2]. Soit A un ensemble partiellement ordonné dont la relation d'ordre est notée ≤. On définit les chaînes par[3] :

Soient a et b deux éléments de A tels que a ≤ b. Pour tout entier naturel p, on appelle « chaîne de longueur p joignant a à b », toute suite finie (x0x1, ..., xp) telle que :

a=x_0< x_1 < \cdots x_{p-1}< x_p=b,
et l'on note cp(ab) le nombre de ces chaînes.

En supposant que l'ordre sur A est localement fini (en), 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[4] :

Soient a et b deux éléments de A tel que a < b :

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

Elle généralise la fonction de Möbius classique μ[5] :

Pour A = ℕ*, ordonné par « a ≤ b lorsque a est un diviseur de b », on a

\forall a,b\in\N^*,\quad a\mid b\Rightarrow\mu_A(a,b)=\mu(b/a).

Formule d'inversion de Rota[modifier | modifier le code]

La fonction μA vérifie la formule d'inversion suivante[6], qui généralise celle pour μ :

Si

\forall b\in A\quad g(b)=\sum_{a\le b}f(a),

alors

\forall b\in A\quad f(b)=\sum_{a\le b}g(a)\mu_A(a,b).

En effet, le produit de convolution de Dirichlet se généralise, permettant d'associer à tout ordre localement fini A son algèbre d'incidence (en), 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[2],[7], 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 F et G sont des fonctions définies sur l'intervalle [1, +∞[ de ℝ à valeurs complexes vérifiant

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

alors

\forall x\ge 1 \quad F(x) = \sum_{1 \le n \le x}\mu(n)G(x/n).

Applications[modifier | modifier le code]

Des exemples sont donnés dans l'article Fonction multiplicative.

Arithmétique modulaire[modifier | modifier le code]

Article détaillé : Indicatrice d'Euler.

L'indicatrice d'Euler est la fonction φ qui à tout entier n > 0 associe le nombre de générateurs du groupe cyclique d'ordre n. Dans un tel groupe, deux éléments de même ordre engendrent le même sous-groupe et cet ordre d est un diviseur de n. Si les éléments du groupe sont partitionnés selon leurs ordres, on obtient donc :

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

La formule d'inversion donne alors[8] :

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

Polynôme cyclotomique[modifier | modifier le code]

Article détaillé : 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 :

\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)}.

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 ne polynôme cyclotomique Φn, on obtient, en vertu de l'égalité

X^n-1=\prod_{d|n}\Phi_d(X)

un moyen de calculer le ne polynôme cyclotomique :

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

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[modifier | modifier le code]

Paragraphe détaillé : « Un critère d'irréductibilité », dans l'article sur les corps finis.

Certains codes correcteurs, comme les codes cycliques sont construits à l'aide de l'anneau des polynômes à coefficients dans le corps fini Fq à q éléments et d'un polynôme irréductible et unitaire de degré n, où n est premier avec q[réf. nécessaire]. C'est l'une des raisons pour lesquelles on s'intéresse au nombre mn(q) de polynômes irréductibles unitaires de degré n à coefficients dans Fq. Cette question est un exemple de problème de dénombrement faisant intervenir la fonction de Möbius.

On démontre algébriquement que

q^n=\sum_{d|n}d~m_d(q).

Par inversion de Möbius, on en déduit[7] :

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

Notes et références[modifier | modifier le code]

  1. F. Badiou, « Formule d'inversion de Möbius », Séminaire Delange-Pisot-Poitou Théorie des nombres, vol. 2, exp. 1,‎ 1960, p. 3 (lire en ligne).
  2. a et b (en) 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.
  3. IREM de Marseille, Cours et activités en arithmétiques pour les classes terminales (lire en ligne), p. 75.
  4. IREM-Marseille, p. 76.
  5. IREM-Marseille, p. 80.
  6. IREM-Marseille, p. 77.
  7. a et b R. Rolland, Fonction de Möbius - Formule de Rota, CNRS, Institut de mathématiques de Luminy.
  8. Ce paragraphe s'inspire de IREM-Marseille, p. 72.

Articles connexes[modifier | modifier le code]