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

Portail des mathématiques

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

Catégorie : Arithmétique

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Formule d'inversion de möbius de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

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 »; voir l’algèbre… … Wikipédia en Français
Formule d'inversion de Mobius — 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… … Wikipédia en Français
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… … Wikipédia en Français
Formule Du Crible De Poincaré — Principe d inclusion exclusion Exemple d inclusion exclusion à partir de trois ensembles. En combinatoire, le principe d’inclusion exclusion permet d’exprimer le nombre d’éléments (ou cardinal) d une réunion finie d ensembles finis en fonction du … Wikipédia en Français
Formule du crible — Principe d inclusion exclusion Exemple d inclusion exclusion à partir de trois ensembles. En combinatoire, le principe d’inclusion exclusion permet d’exprimer le nombre d’éléments (ou cardinal) d une réunion finie d ensembles finis en fonction du … Wikipédia en Français
Formule du crible de Poincare — Principe d inclusion exclusion Exemple d inclusion exclusion à partir de trois ensembles. En combinatoire, le principe d’inclusion exclusion permet d’exprimer le nombre d’éléments (ou cardinal) d une réunion finie d ensembles finis en fonction du … Wikipédia en Français
Formule du crible de Poincaré — Principe d inclusion exclusion Exemple d inclusion exclusion à partir de trois ensembles. En combinatoire, le principe d’inclusion exclusion permet d’exprimer le nombre d’éléments (ou cardinal) d une réunion finie d ensembles finis en fonction du … Wikipédia en Français
Formule du crible de poincaré — Principe d inclusion exclusion Exemple d inclusion exclusion à partir de trois ensembles. En combinatoire, le principe d’inclusion exclusion permet d’exprimer le nombre d’éléments (ou cardinal) d une réunion finie d ensembles finis en fonction du … Wikipédia en Français
Fonction De Möbius — Pour les articles homonymes, voir Moebius. August Ferdinand Möbius est le premier à étudier systématiquement la fonction qui por … Wikipédia en Français
Fonction de Mobius — Fonction de Möbius Pour les articles homonymes, voir Moebius. August Ferdinand Möbius est le premier à étudier systématiquement la fonction qui por … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Formule d'inversion de möbius