title: Formule d'inversion de Möbius
text: # 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^,$ déclare que pour toutes fonctions arithmétiques f et g, on a
  
  $\forall n\in \mathbb {N} ^{*}\quad g(n)=\sum _{d\mid n}f(d)$
  
  si et seulement si f est la transformée de Möbius de g, c.-à-d.
  
  $\forall n\in \mathbb {N} ^{*}\quad f(n)=\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.
  
  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 :
  
  $\forall n\in \mathbb {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
  
  En notant 1 la fonction constante 1(n) = 1, la formule d'inversion se réécrit :
  
  $g=f*{\rm {1}}\Leftrightarrow f=g*\mu$
  
  Cette équivalence résulte de la définition de μ comme l'inverse de 1 pour la convolution ✻ :
  
  ${\rm {1}}*\mu =\mu *{\rm {1}}=\delta _{1}$
  
  qui donne bien :
  
      $g=f*{\rm {1}}\Rightarrow g*\mu =f*{\rm {1}}*\mu =f*\delta _{1}=f$
  
  et
  
      $f=g*\mu \Rightarrow f*{\rm {1}}=g*\mu *{\rm {1}}=g*\delta _{1}=g$.
  
  Ces calculs restent valables pour f et g à valeurs dans un groupe abélien (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. Soit A un ensemble partiellement ordonné dont la relation d'ordre est notée ≤. On définit les chaînes par :
  
     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 $(x_0,$ $x_1,$ ..., $x_p)$ telle que :
     $a=x_{0}<x_{1}<\cdots x_{p-1}<x_{p}=b,$
     et l'on note $c_p(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 :
  
     Soient a et b deux éléments de A tel que a < b :
     $\mu _{A}(a,a)=1\quad {\text{et}}\quad \sum _{a\leq c\leq b}\mu _{A}(a,c)=\sum _{a\leq c\leq b}\mu _{A}(c,b)=0,$
  
  Elle généralise la fonction de Möbius classique μ :
  
     Pour A = ℕ*, ordonné par « a ≤ b lorsque a est un diviseur de b », on a
     $\forall a,b\in \mathbb {N} ^{*},\quad a\mid b\Rightarrow \mu _{A}(a,b)=\mu (b/a).$
  
  ### Formule d'inversion de Rota
  
  La fonction $μ_A$ vérifie la formule d'inversion suivante, qui généralise celle pour μ :
  
     $\forall b\in A\quad g(b)=\sum _{a\leq b}f(a)\quad \Longleftrightarrow \quad \forall b\in A\quad f(b)=\sum _{a\leq 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^,,$ alors qu'un calcul direct est possible :
  
  $\sum _{a\leq b}g(a)\mu _{A}(a,b)=\sum _{a\leq b}\left(\sum _{c\leq a}f(c)\right)\mu _{A}(a,b)=\sum _{c\leq b}f(c)\sum _{c\leq a\leq b}\mu _{A}(a,b).$
  
  D'après la caractérisation de $μ_A,$ les termes de droite sont tous nuls, sauf si c est égal à b ; a est alors aussi égal à b et $μ_A(a,$ a) est égal à 1, ce qui montre le résultat.
  
  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
  
      $\forall x\geq 1\quad G(x)=\sum _{1\leq n\leq x}\alpha (n)F(x/n)\quad \Longleftrightarrow \quad \forall x\geq 1\quad F(x)=\sum _{1\leq n\leq x}\beta (n)G(x/n)$.
  
  ## Applications
  
  Des exemples sont donnés dans l'article Fonction multiplicative.
  
  ### Arithmétique modulaire
  
  L'indicatrice d'Euler φ vérifie :
  
  $\forall n\in \mathbb {N} ^{*}\quad n=\sum _{d|n}\varphi (d)$
  
  La formule d'inversion donne alors :
  
  $\forall n\in \mathbb {N} ^{*}\quad \varphi (n)=\sum _{d|n}\mu (d){\frac {n}{d}}$
  
  ### 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 \mathbb {N} ^{*}\quad g(n)=\prod _{d|n}f(d)\quad {\text{alors}}\quad \forall n\in \mathbb {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
  
  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é n, où n est premier avec q. 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
  
  $q^{n}=\sum _{d|n}d~m_{d}(q).$
  
  Par inversion de Möbius, on en déduit :
  
  $n~m_{n}(q)=\sum _{d|n}\mu (d)q^{n/d},\quad {\text{i.e.}}\quad m_{n}(q)={\frac {1}{n}}\sum _{d|n}\mu (d)q^{n/d}.$
  
  