Nombre de Dedekind

Treillis distributifs libres des fonctions booléennes croissantes ayant 0, 1, 2 , 3 arguments, et possédant respectivement 2, 3, 6 et 20 éléments.

En mathématiques, les nombres de Dedekind ${\displaystyle D_{n}}$, définis en 1897 par Richard Dedekind^[1], dénombrent les fonctions booléennes croissantes à ${\displaystyle n}$ variables. De manière équivalente, ${\displaystyle D_{n}}$ est le nombre d'antichaînes formées avec les parties d'un ensemble à ${\displaystyle n}$ éléments, ainsi que le nombre d'éléments d'un treillis distributif libre à ${\displaystyle n}$ générateurs, ou encore, diminué de 1, le nombre de complexes simpliciaux abstraits sur un ensemble à ${\displaystyle n}$ éléments.

On connaît des estimations asymptotiques précises de ${\displaystyle D_{n}}$ qui montrent que la suite ${\displaystyle (D_{n})}$ est à croissance rapide, à peu près à la vitesse ${\displaystyle 2^{2^{n}}}$^[2].

Bien que l'on connaisse une expression exacte de ${\displaystyle D_{n}}$ sous forme de somme, on n'en connait aucune expression fermée.

Le problème de Dedekind consistant à calculer numériquement ${\displaystyle D_{n}}$ reste difficile : les valeurs exactes de ${\displaystyle D_{n}}$ n'ont été trouvées que pour ${\displaystyle n\leqslant 9}$ , la dernière en 2023 (suite A000372 de l'OEIS)^[2],[3],[4].

Définitions

Fonctions booléennes croissantes

Une fonction booléenne (de première forme) est une fonction qui associe un booléen à un ${\displaystyle n}$-uplet de booléens (c'est-à-dire des bits égaux à 0 ou 1). Autrement dit, c'est l'une des ${\displaystyle 2^{2^{n}}}$applications de ${\displaystyle \{0,1\}^{n}}$ dans ${\displaystyle \{0,1\}}$.

Elle est croissante si, lorsque l'un des booléens de départ passe de 0 à 1, l'image ne peut passer de 1 à 0. Le nombre de Dedekind ${\displaystyle D_{n}}$ est le nombre de fonctions booléennes croissantes à ${\displaystyle n}$ variables.

Étant donné un ensemble ${\displaystyle E_{n}}$ à ${\displaystyle n}$ éléments, l'ensemble ${\displaystyle {\mathcal {P}}(E_{n})}$ des parties de ${\displaystyle E_{n}}$ étant en bijection avec ${\displaystyle \{0,1\}^{n}}$, une fonction booléenne (de deuxième forme) est une application de ${\displaystyle {\mathcal {P}}(E_{n})}$ dans ${\displaystyle \{0,1\}}$.

Upsets

Sous sa deuxième forme, une fonction booléenne ${\displaystyle f}$ est croissante si ${\displaystyle \forall A,B\in {\mathcal {P}}(E_{n})\,(A\subset B\Rightarrow f(A)\leqslant f(B))}$.

La fonction ${\displaystyle f}$ ne prenant que deux valeurs 0 et 1, ceci équivaut à ce que ${\displaystyle \forall A,B\in {\mathcal {P}}(E_{n})\,((A\subset B{\text{ et }}f(A)=1)\Rightarrow f(B)=1)}$.

Une fonction booléenne étant entièrement déterminée par l'ensemble des parties de ${\displaystyle E_{n}}$ ayant pour image 1, le nombre de Dedekind ${\displaystyle M(n)}$ est le nombre d'éléments ${\displaystyle {\mathcal {U}}}$ de ${\displaystyle {\mathcal {P}}({\mathcal {P}}(E_{n}))}$ vérifiant ${\displaystyle \forall A,B\in {\mathcal {P}}(E_{n})\,((A\in {\mathcal {U}}{\text{ et }}A\subset B)\Rightarrow B\in {\mathcal {U}})}$, appelés en anglais des "upsets" de ${\displaystyle E_{n}}$.

Par exemple, la fonction booléenne croissante sur ${\displaystyle E_{3}=\{1,2,3\}}$ qui vaut 1 pour ${\displaystyle \{1,2\},\{1,3\},\{1,2,3\}}$ a pour "upset" associé ${\displaystyle {\mathcal {U}}=\{\{1,2\},\{1,3\},\{1,2,3\}\}}$.

Antichaînes

Si dans un "upset" on ne conserve que les parties de ${\displaystyle E_{n}}$ qui sont les points de départ d'une chaine pour l'inclusion, on obtient une antichaîne de ${\displaystyle {\mathcal {P}}(E_{n})}$ (également connue sous le nom d'ensemble de Sperner), ensemble de parties de ${\displaystyle E_{n}}$ dont aucune n'est incluse dans une autre. Inversement, toute antichaîne peut être complétée en un "upset".

Par conséquent, le nombre de Dedekind ${\displaystyle M(n)}$ est égal au nombre d’antichaînes que l'on peut former dans l'ensemble des parties d'un ensemble à ${\displaystyle n}$ éléments.

Par exemple, l'"upset" ${\displaystyle {\mathcal {U}}=\{\{1,2\},\{1,3\},\{1,2,3\}\}}$ correspond à l'antichaîne ${\displaystyle {\mathcal {A}}=\{\{1,2\},\{1,3\}\}}$.

Complexes simpliciaux

En leur retirant une unité, les nombres de Dedekind dénombrent également les complexes simpliciaux abstraits sur ${\displaystyle E_{n}}$, ensembles ${\displaystyle {\mathcal {C}}}$ de parties de ${\displaystyle E_{n}}$ ayant la propriété que toute partie non vide d'un élément de ${\displaystyle {\mathcal {C}}}$ appartient également à ${\displaystyle {\mathcal {C}}}$.

Toute antichaîne (sauf {Ø}) détermine un complexe simplicial, l'ensemble de toutes les parties non vides des éléments de l'antichaîne, et inversement les simplexes maximaux d'un complexe simplicial déterminent chacun une antichaîne.

Par exemple, l'antichaine ${\displaystyle {\mathcal {A}}=\{\{1,2\},\{1,3\}\}}$ est associée au complexe ${\displaystyle {\mathcal {C}}=\{\{1\},\{2\},\{3\},\{1,2\},\{1,3\}\}}$.

Treillis distributifs

Une troisième manière équivalente de décrire la même classe d’objets utilise la théorie des treilis. À partir de deux fonctions booléennes croissantes ${\displaystyle f}$ et ${\displaystyle g}$, on peut fabriquer deux autres fonctions booléennes croissantes ${\displaystyle f\land g}$ et ${\displaystyle f\lor g}$, respectivement leur conjonction logique et leur disjonction logique. L' ensemble des fonctions booléennes croissantes à ${\displaystyle n}$ variables muni de ces deux opérations forme un treillis distributif, le treillis donné par le théorème de représentation de Birkhoff à partir de l'ensemble ${\displaystyle {\mathcal {P}}(E_{n})}$ ordonné par l'inclusion. Cette construction produit un treillis distributif libre à ${\displaystyle n}$ générateurs, les ${\displaystyle n}$ fonctions définies par ${\displaystyle f_{i}(x_{1},\cdots ,x_{n})=x_{i}}$^[5]. Ainsi, les nombres de Dedekind dénombrent les treillis distributifs libres à ${\displaystyle n}$ générateurs.

Exemples

Pour ${\displaystyle n}$ = 2, il existe six fonctions booléennes croissantes à deux variables, correspondant à six antichaînes de ${\displaystyle {\mathcal {P}}(\{1,2\})}$ :

• La fonction constante égale 0 correspondant à l'antichaîne vide Ø
• La conjonction logique ${\displaystyle f(x,y)=x\land y}$ , valant 1 uniquement pour ${\displaystyle (1,1)}$, correspondant à l'antichaîne ${\displaystyle \{\{1,2\}\}}$.
• La fonction ${\displaystyle f(x,y)=x}$ , qui ignore son deuxième argument et renvoie le premier, correspondant à l'antichaîne ${\displaystyle \{\{1\}\}}$
• La fonction ${\displaystyle f(x,y)=y}$ , qui ignore son premier argument et renvoie le deuxième, correspondant à l'antichaîne ${\displaystyle \{\{2\}\}}$
• La disjonction logique ${\displaystyle f(x,y)=x\lor y}$ , valant 0 uniquement pour ${\displaystyle (0,0)}$, correspondant à l'antichaîne ${\displaystyle \{\{1\},\{2\}\}}$
• La fonction constante égale à 1 correspondant à l'antichaîne ${\displaystyle \{\varnothing \}}$.

Pour ${\displaystyle n}$ = 3, il existe 20 antichaînes de ${\displaystyle {\mathcal {P}}(\{1,2,3\})}$ : les 17 antichaînes formées de parties ayant toutes le même nombre d'éléments, plus les 3 antichaînes du type ${\displaystyle \{\{1\},\{2,3\}\}}$.

Calcul des nombres de Dedekind

Les valeurs exactes des nombres de Dedekind sont connues pour ${\displaystyle 0\leqslant n\leqslant 9}$ :

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, 286386577668298411128469151667598498812366, suite A000372 de l'OEIS.

Les six premiers nombres ont été donnés par Church en 1940, ${\displaystyle D_{6}}$ a été calculé par Ward en 1946, ${\displaystyle D_{7}}$ par Church en 1965, et Berman & Köhler en 1976, ${\displaystyle D_{8}}$ par Wiedemann en 1991 ; ${\displaystyle D_{9}}$ a été découvert en 2023 simultanément par Christian Jäkel, Lennart Van Hirtum et alii^[6].

Si ${\displaystyle n}$ est pair, ${\displaystyle D_{n}}$ est pair. Le calcul du cinquième nombre de Dedekind ${\displaystyle D_{5}=7581}$ a réfuté une conjecture de Garrett Birkhoff selon laquelle ${\displaystyle D_{n}}$ serait toujours divisible par ${\displaystyle (2n-1)(2n-2)}$.

Formule de sommation

Kisielewicz (1988) a transcrit la définition par les antichaînes en la formule arithmétique suivante :

${\displaystyle D_{n}=\sum _{k=1}^{2^{2^{n}}}\prod _{j=1}^{2^{n}-1}\prod _{i=0}^{j-1}\left(1-b_{i}^{k}b_{j}^{k}\prod _{m=0}^{\log _{2}i}(1-b_{m}^{i}+b_{m}^{i}b_{m}^{j})\right),}$

où ${\displaystyle b_{i}^{k}}$ est le ${\displaystyle i}$-ème chiffre binaire du nombre ${\displaystyle k}$, qui peut être obtenu en utilisant la partie entière sous la forme

${\displaystyle b_{i}^{k}=\left\lfloor {\frac {k}{2^{i}}}\right\rfloor -2\left\lfloor {\frac {k}{2^{i+1}}}\right\rfloor .}$

Cependant, cette formule n'est pas utile pour calculer les valeurs de ${\displaystyle D_{n}}$ pour ${\displaystyle n}$ grand en raison du grand nombre de termes dans la sommation^[7].

Évaluation asymptotique

Tout ensemble formé de parties de ${\displaystyle E_{n}}$ ayant le même nombre d'éléments est une antichaîne de ${\displaystyle {\mathcal {P}}(E_{n})}$. On en déduit la minoration

${\displaystyle D_{n}\geqslant \sum _{k=0}^{n}2^{\binom {n}{k}}-n}$ ; voir la suite A169974 de l'OEIS,

dont on déduit la minoration simple ${\displaystyle D_{n}\geqslant 2^{n \choose \lfloor n/2\rfloor }}$.

Le logarithme binaire des nombres de Dedekind peut être estimé avec précision par l'encadrement :

${\displaystyle {n \choose \lfloor n/2\rfloor }\leqslant \log _{2}D_{n}\leqslant {n \choose \lfloor n/2\rfloor }\left(1+O\left({\frac {\log n}{n}}\right)\right).}$

L'inégalité de gauche a été montrée précédemment et l'inégalité de droite a été prouvée par Kleitman & Markowsky en 1975.

Korshunov (1981) a fourni une estimation encore plus précise :

${\displaystyle D_{n}=(1+o(1))2^{n \choose \lfloor n/2\rfloor }\exp a(n)}$

pour n pair, et

${\displaystyle D_{n}=(1+o(1))2^{{n \choose \lfloor n/2\rfloor }+1}\exp(b(n)+c(n))}$

pour n impair, où

${\displaystyle a(n)={n \choose n/2-1}(2^{-n/2}+n^{2}2^{-n-5}-n2^{-n-4}),}$

${\displaystyle b(n)={n \choose (n-3)/2}(2^{-(n+3)/2}+n^{2}2^{-n-6}-n2^{-n-3}),}$

et

${\displaystyle c(n)={n \choose (n-1)/2}(2^{-(n+1)/2}+n^{2}2^{-n-4}).}$

L’idée principale derrière ces estimations est que, dans la plupart des antichaînes, tous les ensembles ont des tailles très proches de ${\displaystyle n/2}$. Pour ${\displaystyle n}$ = 2, 4, 6, 8, la formule de Korshunov fournit une estimation à 9,8 %, 10,2 %, 4,1 % et − 3,3 % près respectivement^[8].

Notes

1. (de) Richard Dedekind, « Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler », Gesammelte Werke, vol. 2,‎ 1897, p. 103–148 (lire en ligne)
2. Charlotte Mauger, « Le neuvième nombre de Dedekind vient d’être calculé », Pour la Science,‎ septembre 2023 (lire en ligne)
3. Gérard Villemin, « Fonctions booléenne et Nombres de Dedekind », sur villemin.gerard.free.fr
4. Fabien Aoustin, « Le neuvième nombre de Dedekind », Tangente, n^o 216,‎ mars-avril 2024, p. 6-8 (lire en ligne )
5. La définition des treillis distributifs libres utilisée ici autorise comme opérations de treillis toute réunion et intersection finie, y compris la réunion vide et l'intersection vide. Pour le treillis distributif libre dans lequel seules les réunions et les intersections par paires sont autorisées, il faut éliminer les éléments supérieur et inférieur du treillis et soustraire 2 aux nombres de Dedekind.
6. (en) Christian Jäkel, « A computation of the ninth Dedekind Number », Journal of Computational Algebra,‎ 6-7 2023 (lire en ligne)
7. Par exemple, pour ${\displaystyle n=10}$, la somme contient ${\displaystyle 2^{2^{10}}=2^{1024}}$ termes, ce qui est bien au-delà de ce qui peut être calculé numériquement.
8. (en) K. S. Brown, « Generating the monotone Boolean functions »

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Nombre de Dedekind » (voir la liste des auteurs).

• Portail des mathématiques