Nombre de Dedekind

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

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.

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

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

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

Définitions

Fonctions booléennes croissantes

Une fonction booléenne (de première forme) est une fonction qui associe un booléen à un $n$-uplet de booléens (c'est-à-dire des bits égaux à 0 ou 1). Autrement dit, c'est l'une des $2^{2^{n}}$applications de $\{0,1\}^{n}$ dans $\{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 $D_{n}$ est le nombre de fonctions booléennes croissantes à $n$ variables.

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

Upsets

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

La fonction $f$ ne prenant que deux valeurs 0 et 1, ceci équivaut à ce que $\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 $E_{n}$ ayant pour image 1, le nombre de Dedekind $M(n)$ est le nombre d'éléments ${\mathcal {U}}$ de ${\mathcal {P}}({\mathcal {P}}(E_{n}))$ vérifiant $\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 $E_{n}$.

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

Antichaînes

Si dans un "upset" on ne conserve que les parties de $E_{n}$ qui sont les points de départ d'une chaine pour l'inclusion, on obtient une antichaîne de ${\mathcal {P}}(E_{n})$ (également connue sous le nom d'ensemble de Sperner), ensemble de parties de $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 $M(n)$ est égal au nombre d’antichaînes que l'on peut former dans l'ensemble des parties d'un ensemble à $n$ éléments.

Par exemple, l'"upset" ${\mathcal {U}}=\{\{1,2\},\{1,3\},\{1,2,3\}\}$ correspond à l'antichaîne ${\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 $E_{n}$, ensembles ${\mathcal {C}}$ de parties de $E_{n}$ ayant la propriété que toute partie non vide d'un élément de ${\mathcal {C}}$ appartient également à ${\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 ${\mathcal {A}}=\{\{1,2\},\{1,3\}\}$ est associée au complexe ${\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 $f$ et $g$, on peut fabriquer deux autres fonctions booléennes croissantes $f\land g$ et $f\lor g$, respectivement leur conjonction logique et leur disjonction logique. L' ensemble des fonctions booléennes croissantes à $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 ${\mathcal {P}}(E_{n})$ ordonné par l'inclusion. Cette construction produit un treillis distributif libre à $n$ générateurs, les $n$ fonctions définies par $f_{i}(x_{1},\cdots ,x_{n})=x_{i}$. Ainsi, les nombres de Dedekind dénombrent les treillis distributifs libres à $n$ générateurs.

Exemples

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

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

Pour $n$ = 3, il existe 20 antichaînes de ${\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 $\{\{1\},\{2,3\}\}$.

Calcul des nombres de Dedekind

Les valeurs exactes des nombres de Dedekind sont connues pour $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, $D_{6}$ a été calculé par Ward en 1946, $D_{7}$ par Church en 1965, et Berman & Köhler en 1976, $D_{8}$ par Wiedemann en 1991 ; $D_{9}$ a été découvert en 2023 simultanément par Christian Jäkel, Lennart Van Hirtum et alii.

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

Formule de sommation

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

$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ù $b_{i}^{k}$ est le $i$-ème chiffre binaire du nombre $k$, qui peut être obtenu en utilisant la partie entière sous la forme

$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 $D_{n}$ pour $n$ grand en raison du grand nombre de termes dans la sommation.

Évaluation asymptotique

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

$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 $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 :

${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 :

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

pour n pair, et

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

pour n impair, où

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

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

et

$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 $n/2$. Pour $n$ = 2, 4, 6, 8, la formule de Korshunov fournit une estimation à 9,8 %, 10,2 %, 4,1 % et − 3,3 % près respectivement.

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).