Nombre de Dedekind

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

On connait des estimations asymptotiques précises de   qui montrent que la suite  est à croissance rapide, à peu près à la vitesse .

Bien que l'on connaisse une expression exacte de  sous forme de somme, aucune expression fermée pour  n'est connue.

Le problème de Dedekind consistant à calculer numériquement  reste difficile : les valeurs exactes de  n'ont été trouvées que pour  , la dernière en 2023 ().

Définitions

Fonctions booléennes croissantes 
Une fonction booléenne (de première forme) est une fonction qui associe un booléen à un -uplet de booléens (c'est-à-dire des bits égaux à 0 ou 1). Autrement dit, c'est l'une des applications de  dans .

Elle est croissante si, lorsque l'un des booléens de départ passe de 0 à 1, l'image ne peux passer de 1 à 0. Le nombre de Dedekind  est le nombre de fonctions booléennes croissantes à  variables.

Étant donné un ensemble  à  éléments, l'ensemble  des parties de  étant en bijection avec , une fonction booléenne (de deuxième forme) est une application de  dans .

Upsets 
Sous sa deuxième forme, une fonction booléenne  est croissante si .

La fonction  ne prenant que deux valeurs 0 et 1, ceci équivaut à ce que .

Une fonction booléenne étant entièrement déterminée par l'ensemble des parties de  ayant pour image 1, le nombre de Dedekind  est le nombre d'éléments  de  vérifiant , appelés en anglais des "upsets" de .

Par exemple, la fonction booléenne croissante sur  qui vaut 1 pour  a pour "upset" associé .

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

Par exemple, l'"upset"  correspond à l'antichaîne .

Complexes simpliciaux 
En leur retirant une unité, les nombres de Dedekind dénombrent également les complexes simpliciaux abstraits sur , ensembles  de parties de  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  est associée au complexe .

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  et , on peut fabriquer deux autres fonctions booléennes croissantes  et , respectivement leur conjonction logique et leur disjonction logique. L' ensemble des fonctions booléennes croissantes à  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  ordonné par l'inclusion. Cette construction produit un treillis distributif libre à  générateurs, les  fonctions définies par . Ainsi, les nombres de Dedekind dénombrent les treillis distributifs libres à  générateurs.

Exemples 
Pour  = 2, il existe 6 fonctions booléennes croissantes à deux variables, correspondant à 6 antichaînes de   :

 La fonction constante égale 0 correspondant à  l'antichaîne vide Ø
 La conjonction logique  , valant 1 uniquement pour , correspondant à l'antichaîne .
 La fonction  , qui ignore son deuxième argument et renvoie le premier, correspondant à l'antichaîne 
 La fonction  , qui ignore son premier argument et renvoie le deuxième, correspondant à l'antichaîne 
 La disjonction logique   , valant 0 uniquement pour , correspondant à l'antichaîne 
 La fonction constante égale à 1 correspondant à l'antichaîne .
Pour  = 3, il existe 20 antichaînes de  : les 17 antichaînes formées de parties ayant toutes le même nombre d'éléments, plus les 3 antichaînes du type .

Calcul des nombres de Dedekind 
Les valeurs exactes des nombres de Dedekind sont connues pour  :

 2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, 286386577668298411128469151667598498812366, .

Les six premiers nombres ont été donnés par Church en 1940,  a été calculé par Ward en 1946,  par Church en 1965, et Berman & Köhler en 1976,  par Wiedemann en 1991 ;  a été découvert en 2023 simultanément par Christian Jäkel, Lennart Van Hirtum et alii.

Si  est pair,  est pair. Le calcul du cinquième nombre de Dedekind  a réfuté une conjecture de Garrett Birkhoff selon laquelle  serait toujours divisible par .

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

 

où  est le -ème chiffre binaire du nombre , qui peut être obtenu en utilisant la partie entière sous la forme

 

Cependant, cette formule n'est pas utile pour calculer les valeurs de  pour  grand en raison du grand nombre de termes dans la sommation.

Évaluation asymptotique 
Tout ensemble formé de parties de  ayant le même nombre d'éléments est une antichaîne de . On en déduit la minoration 
  ;  voir la ,
dont on déduit la minoration simple .

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

 

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 :

 

pour n pair, et

 

pour n impair, où

 
 

et

 

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

Notes

Références 

Système d'ensembles
Logique mathématique
Suite d'entiers