INVERSIONS DE MÖBIUS (^{1})

Dominique Foata

La formule d’inversion de Möbius, comme le soulignait fort justement le professeur Temperley lors de la Rencontre d’Aberdeen (6-12 juillet 1975), n’est en fait qu’une sublimation du principe d’inclusion-exclusion. Chacun sait bien que le plus difficile dans les applications est de calculer la fonction de Möbius sous-jacente et à l’exception de quelques cas simples, ce calcul ne dérive pas des principes, mais reste une affaire d’ingéniosité et d’expérience.

La formule d’inversion, de façon habituelle (cf., par exemple, Rota (1964)), est présentée dans le cadre des ensembles ordonnés localement finis (“locally finite partially ordered sets”). Dans Cartier-Foata (1969, chap. 2), on trouve une définition de fonction de Möbius des monoïdes à factorisation finie. Le but de cette note est de montrer la connexion entre ces deux présentations.

En aucun cas, je ne veux faire ici œuvre originale : mon but est simplement de montrer qu’il n’y a qu’une “théorie” de l’inversion de Möbius. Le cadre choisi pour présenter la formule d’inversion est au fond accessoire et ne peut être qu’une structure algébrique rudimentaire. En fait, la proposition 1 cidessous doit être attribuée à Rota (1972) et la proposition 2 à Schützenberger (1974) dans des communications privées avec l’auteur.

1. Ensembles ordonnés

La construction de la fonction de Möbius pour les ensembles ordonnés est très clairement exposée dans Rota (1964). Soit P un ensemble ordonné localement fini, c’est-à-dire que si x ≤ y, il n’y a qu’un nombre fini de z ∈ P tels que x ≤ z ≤ y. On forme l’ensemble R(P × P) des fonctions réelles de deux variables x et y, où x et y sont dans P, ayant les propriétés suivantes :

(i) f(x, y) = 0 si x ≰ y; (ii) f(x, x) est, pour tout x ∈ P, une constante qui ne dépend que de f.(^{2})

L’ensemble R(P × P) est muni d’une structure d’algèbre associative sur le corps des réels – on l’appellera désormais l’algèbre d’incidence de P – en prenant pour somme f + g et produit fg de deux éléments f, g de R(P × P), les fonctions définies par

(f + g)(x, y) = f(x, y) + g(x, y);
(fg)(x, y) = ∑_{x≤z≤y} f(x, z)g(z, y);

(^{1}) The present text was written on the occasion of the Science Research Council Rencontre, Aberdeen, July 6–12 1975 and had been never published since.

(^{2}) La restriction (ii) n’est en général pas imposée. Elle est ici mentionnée par commodité.

On se persuadera que les fonction ξ_{P} et μ_{P} définies ci-après appartiennent bien à R(P ×P).

pour tout x, y dans P. L’algèbre R(P × P) a un élément unité δ (la fonction de Kronecker). On distingue enfin une application ξ_{P} définie par

ξ_{P} (x, y) = \{ \begin{matrix}1, & si x ≤ y; \\ 0, & autrement. \end{matrix}

La fonction de Möbius μ_{P} de P n’est autre que l’inverse (on démontre qu’il existe !) de ξ_{P} dans A(P ×P). Autrement dit, μ_{P} est la fonction satisfaisant à

ξ_{P} μ_{P} = μ_{P} ξ_{P} = δ.

2. Monoïdes à factorisation finie

Soit maintenant M un monoïde, c’est-à-dire un ensemble muni d’une opération associative (qu’on notera multiplicativement), admettant un élément unité (qu’on notera 1). Le monoïde M peut ou non contenir un élément zéro, noté 0, tel que 0 · x = x · 0 = 0 pour tout x dans M. On note M^{+} l’ensemble des éléments non nuls de M.

On appelle décomposition d’un élément x de M toute suite finie s = (x_{1}, …, x_{q}) d’éléments de M, différents de 0 et de 1, telle que x = x_{1} ⋯ x_{q}. L’entier q s’appelle le degré de la décomposition s. On admet, par convention, une décomposition vide de 1, de degré 0. On dit que le monoïde M est à factorisation finie, si tout élément de M^{+} n’admet qu’un nombre fini de décompositions.

Soit R(M) l’ensemble des fonctions réelles sur M^{+}. On munit R(M) d’une structure d’algèbre associative en posant

(f + g)(x) = f(x) + g(x);
(fg)(x) = ∑_{x_{1}x_{2}=x} f(x_{1})g(x_{2}).

Dans la seconde règle ci-dessus, la sommation est étendue à tous les couples (x_{1}, x_{2}) tels que x_{1}x_{2} = x, en particulier, aux couples (1, x) et (x, 1). On dira encore que R(M) est l’algèbre d’incidence de M. De même, on distingue deux éléments ξ_{M} et ϵ_{M} dans R(M), définis par ξ_{m}(x) = 1 pour tout x dans M^{+} et ϵ_{M}(x) = 1 ou 0 suivant que x = 1 ou x ≠ 0, 1.

3. Formules d’inversion

La formule d’inversion de Möbius dans le cas des ensembles ordonnés est la suivante : soient f et g deux fonctions réelles d’une variable x courant dans un ensemble ordonné P et p un élément de P. Alors les relations suivantes sont équivalentes :

g(x) = ∑_{p≤y≤x} f(y),  pour tout x dans P ;
f(x) = ∑_{p≤y≤x} g(y)μ_{P} (y, x), pour tout x dans P.

Dans le cas des monoïdes à factorization finie, la formule d’inversion de Möbius est une identité dans l’algèbre d’incidence R(M) du monoïde M (cf. Cartier-Foata (1969), p. 20). Soient f et g deux fonctions réelles sur M^{+}. On a l’équivalence entre les deux formules

g(x) = ∑_{x_{1}x_{2}=x} f(x_{2}),  pour tout x dans M^{+} ;
f(x) = ∑_{x_{1}x_{2}=x} μ_{M}(x_{1})g(x_{2}), pour tout x dans M^{+}.

Un dernier rapprochement entre μ_{P} et μ_{M}. Dans le cas des ensembles ordonnés, on détermine μ_{P} par récurrence au moyen des formules μ_{P} (x, x) = 1 et

μ_{P} (x, y) = − ∑_{x≤z≤y, z≠y} μ_{P} (x, z),

en utilisant le fait qu’il n’y a qu’un ensemble fini de z tels que x ≤ z ≤ y.

Dans le cas des monoïdes, la fonction de Möbius μ_{M} est donnée en chaque point x par l’argument suivant. Pour tout x dans M^{+} on note d_{+}(x) (resp. d_{−}(x)) le nombre de décompositions de x de degré pair (resp. impair). Alors

μ_{M}(x) = d_{+}(x) − d_{−}(x)

pour tout x dans M.

4. Algèbres d’incidence des monoïdes

Voyons maintenant comment le calcul de toute fonction de Möbius d’un ensemble ordonné peut être ramené au calcul d’une fonction de Möbius d’un monoïde à factorisation finie.

Proposition 1. — Soit R(P × P) l’algèbre d’incidence d’un ensemble ordonné localement fini P. Alors il existe un monoïde à factorisation finie M tel que son algèbre d’incidence R(M) soit isomorphie à R(P × P).

Démonstration. — Soit J l’ensemble des couples (x, y) d’éléments de P tels que x ≤ y et x ≠ y. Soient encore deux éléments que nous noterons 0 et 1 n’appartenant pas à P. On munit l’ensemble M = {0, 1} ∪ J d’une structure de monoïde en posant

(∗)

0 · m = m · 0 = 0,  pour tout m dans M;
1 · m = m · 1 = m,  pour tout m dans M^{+} = M \ {0};

et pour (x, y) , (z, t) dans J

(∗∗)  (x, y) · (z, t) = \{ \begin{matrix}(x, t), & si y = z; \\ 0, & sinon. \end{matrix}

La multiplication ainsi définie est évidemment associative. Si (x, y) est dans J, il n’admet qu’un nombre fini de décompositions, puisque le segment [x, y] = {z ∈ P : x ≤ z ≤ y} est fini. Le monoïde M est donc à factorisation finie.

Soit maintenant f ∈ R(P × P). On définit la fonction réelle f_{M} sur M^{+} par les relations

(i)  f_{M}(1) = f(x, x),  pour un élément x quelconque de P ;
(ii)  f_{M}(x, y) = f(x, y),  pour x < y.

Montrons que l’application f ↦ f_{M} est un isomorphisme de R(P × P) sur R(M). Le caractère bijectif de f ↦ f_{M} est évident d’après les relations (i) et (ii) et la relation (f + g)_{M} = f_{M} + g_{M} est triviale. Reste à vérifier : (fg)_{M} = f_{M}g_{M}. Or, pour x < y, on a

(fg)_{M}(x, y) = ∑_{x≤z≤y} f(x, z)g(z, y)

= ∑_{x<z<y} f(x, z)g(z, y) + f(x, x)g(x, y) + f(x, y)g(y, y)

= ∑ f_{M}(x_{1}, y_{1})g_{M}(x_{2}, y_{2}) + f_{M}(1)g_{M}(x, y) + f_{M}(x, y)g_{M}(1),

où la sommation est étendue à l’ensemble des paires de couples (x_{1}, y_{1}), (x_{2}, y_{2}) tels que (x_{1}, y_{1}) · (x_{2}, y_{2}) = (x, y). D’où

(fg)_{M} = (f_{M}g_{M})(x, y).

Enfin, pour tout x dans P,

(fg)_{M}(1) = (fg)(x, x)
= f(x, x)g(x, x) = f_{M}(1)g_{M}(1)
= (f_{M}g_{M})(1).

Corollaire. — Soit M le monoïde associé à l’ensemble ordonné P par les relations (∗) et (∗∗). On a alors

μ_{P} (x, y) = μ_{M}(x, y)

pour tout couple (x, y) tel que x ≤ y.

En effet, μ_{M} est l’image de μ_{P} par l’isomomorphisme f ↦ f_{M}.

5. Algèbres d’incidence des ensembles ordonnés

Réciproquement, on peut ramener le calcul de la fonction de Möbius d’un monoïde à factorisation finie M à celui de la fonction de Möbius d’un ensemble ordonné P. Il y a cependant une restriction à imposer sur le monoïde M. On dit qu’un monoïde M est simplifiable (à droite) si pour x, u, v dans M avec x ≠ 0 on a : [xu = xv] ⇒ [u = v]. Supposons M simplifiable. Si u, x, y sont dans M et si y = xu, l’élément u est défini de façon unique. On peut donc poser

u = y/x et ainsi y = x (y/x).

Compte tenu de cette restriction, on a le résultat suivant.

Proposition 2. — Soit R(M) l’algèbre d’incidence d’un monoïde à factoorisation finie et simplifiable. Alors il existe un ensemble ordonné localement fini P tel que son algèbre d’incidence R(P ×P) soit isomorphe à R(M).

Démonstration. — L’ensemble ordonné P qu’on va associer à M est la paire (M, ≤), où “≤” est l’ordre défini par

x ≤ y si y = xu pour un certain u dans M.

On définit de cette façon un ordre sur M, car si y = xu et y = zv, on a z = xuv; d’où x ≤ y et y ≤ z entraînent x ≤ y. De plus, cet ordre est localement fini, car si l’on a x ≤ y ≤ z, on a aussi z = yv pour un certain v, où encore (y, v) est une décomposition de degré 2 de z. Comme il n’y a qu’un nombre fini de décompositions de z, il n’y a donc qu’un nombre fini d’éléments y satisfaisant à x ≤ y ≤ z. Comme on a supposé M simplifiable, il existe un et un seul élément noté y/x tel que y = x(y/x) lorsque x ≤ y.

Soit f une fonction appartenant à R(M). On pose alors pour x, y dans M

f_{P} (x, y) = \{ \begin{matrix}f(y/x), & si x ≤ y; \\ 0, & sinon. \end{matrix}

Comme précédemment on peut vérifier que f ↦ f_{P} est bijectif et linéaire. Soient f et g deux éléments de R(M). On a pour x ≤ y

(fg)_{P} (x, y) = (fg)(y/x) = ∑_{u_{1}u_{2}=y/x} f(u_{1})g(u_{2})

= ∑_{x≤y≤z} f(z/x)g(y/z)

= ∑_{x≤y≤z} f_{P} (x, z)g_{P} (z, y) = (f_{P} g_{P})(x, y).

La fonction de Möbius μ_{P} de l’ensemble P = (M, ≤) est alors donnée par

μ_{P} (x, y) = μ_{M}(y/x), lorsque x ≤ y.

Bibliographie

Pierre Cartier, Dominique Foata (1969). — Problèmes combinatoires de commutation et réarrangements. — Lecture Notes in Math., no. 85, Springer-Verlag, Berlin. Gian-Carlo Rota (1964). — On the Foundations of Combinatorial Theory I. Theory of Möbius Inversion, Z. Wahrscheinlichkeitstheorie, 2, p. 340–368. Gian-Carlo Rota (1972). — Communication privée. Marcel-Paul Schützenberger (1974). — Communication privée.

Retyped with TEX, December 10, 2005.

Institut Lothaire 1, rue Murner 67000 Strasbourg, France