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

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

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⩽9$ , la dernière en 2023 (Modèle:OEIS)Modèle:,Modèle:,.

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 $𝒫(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 $𝒫(E_n)$ dans $\{0,1\}$.

Upsets

Sous sa deuxième forme, une fonction booléenne $f$ est croissante si $\mathrm{\forall }A,B\in 𝒫(E_n)(A\subset B\Rightarrow f(A)⩽f(B))$.

La fonction $f$ ne prenant que deux valeurs 0 et 1, ceci équivaut à ce que $\mathrm{\forall }A,B\in 𝒫(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 $𝒰$ de $𝒫(𝒫(E_n))$ vérifiant $\mathrm{\forall }A,B\in 𝒫(E_n)((A\in 𝒰\text{ et }A\subset B)\Rightarrow B\in 𝒰)$, 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é $𝒰=\{\{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 $𝒫(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" $𝒰=\{\{1,2\},\{1,3\},\{1,2,3\}\}$ correspond à l'antichaîne $𝒜=\{\{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 $𝒞$ de parties de $E_n$ ayant la propriété que toute partie non vide d'un élément de $𝒞$ appartient également à $𝒞$.

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 $𝒜=\{\{1,2\},\{1,3\}\}$ est associée au complexe $𝒞=\{\{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\wedge g$ et $f\vee 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 $𝒫(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 $𝒫(\{1,2\})$ :

• La fonction constante égale 0 correspondant à l'antichaîne vide Ø
• La conjonction logique $f(x,y)=x\wedge 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\vee 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 $𝒫(\{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⩽n⩽9$ :

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, 286386577668298411128469151667598498812366, Modèle: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}(1-b_i^k{b}_j^k\prod _{m=0}^{{\log }_{2}i}(1-b_m^i+b_m^i{b}_m^j)),$

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=\lfloor \frac{k}{2^i}\rfloor -2\lfloor \frac{k}{2^{i+1}}\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 $𝒫(E_n)$. On en déduit la minoration

$D_n⩾\sum _{k=0}^n{2}^{(\genfrac{}{}{0ex}{}{n}{k})}-n$ ; voir la Modèle:OEIS,

dont on déduit la minoration simple $D_n⩾2^{(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })}$.

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

$(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })⩽{\log }_2{D}_n⩽(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })(1+O\left(\frac{\log n}{n}\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^{(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })}\exp a(n)$

pour n pair, et

$D_n=(1+o(1))2^{(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })+1}\exp (b(n)+c(n))$

pour n impair, où

$a(n)=(\genfrac{}{}{0ex}{}{n}{n/2-1})(2^{-n/2}+n^2{2}^{-n-5}-n{2}^{-n-4}),$

$b(n)=(\genfrac{}{}{0ex}{}{n}{(n-3)/2})(2^{-(n+3)/2}+n^2{2}^{-n-6}-n{2}^{-n-3}),$

et

$c(n)=(\genfrac{}{}{0ex}{}{n}{(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.