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

La version classique[1],[2] déclare que pour toutes fonctions arithmétiques f et g, on a

si et seulement si f est la transformée de Möbius de g, c.-à-d.

μ est la fonction de Möbius et les sommes portent sur tous les diviseurs strictement positifs d de n.

L'équivalence reste vraie si les fonctions f et g (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 :

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

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

.

Cette équivalence résulte[1] de la définition de μ comme l'inverse de 1 pour la convolution ✻ :

,

qui donne bien :

et

.

Ces calculs restent valables pour f et g à valeurs dans un groupe abélien[3] (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[4]. Soit A un ensemble partiellement ordonné dont la relation d'ordre est notée ≤. On définit les chaînes par[5] :

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 (x0, x1, ..., xp) telle que :

et l'on note cp(a, b) 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[6] :

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

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

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

Formule d'inversion de Rota

La fonction μA vérifie la formule d'inversion suivante[8], 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 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[4],[9], 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 deux fonctions définies sur l'intervalle [1, +∞[ de ℝ à valeurs complexes et si α et β sont deux fonctions arithmétiques inverses l'une de l'autre pour la convolution de Dirichlet (en particulier si α = 1 et β = μ), alors[10]

.

Applications

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

Arithmétique modulaire

L'indicatrice d'Euler φ vérifie :

.

La formule d'inversion donne alors :

.

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 :

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é

un moyen de calculer le ne polynôme cyclotomique :

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

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

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

Notes et références

  1. Françoise Badiou, « Formule d'inversion de Möbius », Séminaire Delange-Pisot-Poitou Théorie des nombres, vol. 2, exp. 1, , p. 3 (lire en ligne).
  2. G. H. Hardy et E. M. Wright (trad. de l'anglais par F. Sauvageot), Introduction à la théorie des nombres An Introduction to the Theory of Numbers »], Paris/Heidelberg, Vuibert-Springer, , 568 p. (ISBN 978-2-7117-7168-4), p. 301, th. 266 et 267.
  3. (en) Rudolf Lidl et Günter Pilz (en), Applied Abstract Algebra, Springer, (lire en ligne), p. 147.
  4. (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.
  5. IREM de Marseille, Cours et activités en arithmétiques pour les classes terminales (lire en ligne), p. 75.
  6. IREM-Marseille, p. 76.
  7. IREM-Marseille, p. 80.
  8. IREM-Marseille, p. 77.
  9. R. Rolland, Fonction de Möbius - Formule de Rota, CNRS, Institut de mathématiques de Luminy.
  10. (en) Tom M. Apostol, Introduction to Analytic Number Theory, Springer, coll. « UTM (en) » (no 7), , 340 p. (ISBN 978-0-387-90163-3, lire en ligne), p. 40, th. 2.22.

Articles connexes

  • Arithmétique et théorie des nombres
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.