Formule D'inversion De Möbius

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 XIX^e siècle par August Ferdinand Möbius. Elle a été généralisée plus tard à d’autres « formules d’inversion de Möbius »; voir l’algèbre d'incidence. La version classique déclare que si f et g sont des fonctions arithmétiques vérifiant

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

alors

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

où μ est la fonction de Möbius et les sommes portent sur tous les diviseurs positifs d de n. La formule reste valable si f et g sont des fonctions définies sur l’ensemble des entiers naturels non nuls à valeurs dans un certain groupe abélien.

En utilisant la convolution (voir fonction multiplicative), la formule d’inversion peut également s’écrire

μ * 1 = ε (en fait μ * 1 * f = f)

où 1 est la fonction constante prenant la valeur 1, et ε est la fonction telle que ε(1)=1 et pour tout n≠1, ε(n)=0.

Une formulation équivalente de la formule d’inversion plus utile en combinatoire s’énonce ainsi :

si F et G sont des fonctions définies sur l’intervalle [1, +∞[ de $\mathbb{R}$ à 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)$

Ici les sommes portent sur des entiers naturels non nuls qui sont inférieurs ou égaux à x.

La formule d’inversion de Möbius donnée ci-dessus est la formule d’inversion originale de Möbius. Lorsque l’ensemble partiellement ordonné des nombres entiers muni de la relation de divisibilité est remplacé par d’autres ensembles partiellement ordonnés localement finis, nous obtenons d’autres formules d’inversion de Möbius comprenant entre autres le principe d'inclusion-exclusion de Moivre ; pour avoir un aperçu, voir l’algèbre d'incidence.

Une application: dénombrement des irréductibles de $\mathbf{F}_{p}[X]$ de degré donné

Soit p un nombre premier et $\mathbf{F}_{p}$ le corps fini à p éléments. Par des arguments d'algèbre élémentaires on peut démontrer que, pour tout entier naturel non nul n, $X^{p^{n}}-X$ est le produit des polynômes irréductibles unitaires de $\mathbf{F}_{p}[X]$ dont le degré divise n; en notant $\nu(d)\,$ le nombre d'irréductibles unitaires de degré d on a donc, en prenant les degrés: $\sum_{d|n}{d\nu(d)}=p^{n}\,$. La formule d'inversion de Möbius permet alors d'obtenir, avec $f(n)=n\nu(n)\,$ et $g(n)=p^{n}\,$ : $\nu(n)=\frac{1}{n}\sum_{d|n}{\mu(n/d)p^{d}}\,$. On voit en particulier que $\nu(n)\,$ n'est jamais nul.

Voir aussi

Ce document provient de « Formule d%27inversion de M%C3%B6bius ».