Nombre de Dedekind

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

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