Dedekind tal

Den stabile version blev tjekket den 29. marts 2022 . Der er ubekræftede ændringer i skabeloner eller .

Dedekind-tal er en hurtigt voksende sekvens af heltal opkaldt efter Richard Dedekind , som definerede dem i 1897. Dedekind-tallet M ( n ) tæller antallet af monotone boolske funktioner af n variable. Tilsvarende tæller disse tal antallet af antikæder af delmængder af et n -elementsæt, antallet af elementer i et frit fordelingsgitter med n generatorer eller antallet af abstrakte simple komplekser med n elementer.

De nøjagtige asymptotiske estimater af M ( n ) [1] [2] [3] og det nøjagtige udtryk som en sum [4] er kendt. Dedekinds problem med at beregne værdierne af M ( n ) er dog stadig vanskeligt - intet lukket udtryk for M ( n ) er kendt, og de nøjagtige værdier af M ( n ) er kun fundet for [5] .

Definitioner

En boolsk funktion er en funktion, der tager n boolske variable som input (det vil sige værdier, der kan være enten falsk (falsk) eller sand (sand), eller tilsvarende binære værdier , som kan være enten 0 eller 1), og giver en anden boolesk variabel som output. En funktion er monotonisk , hvis ændring af en inputvariabel fra falsk til sand for enhver kombination af input kun kan ændre outputtet fra falsk til sand, men ikke fra sand til falsk. Dedekind-tallet M ( n ) er antallet af forskellige monotone booleske funktioner af n variable.

En antikæde af sæt (også kendt som en Spencer-familie ) er en familie af sæt, hvoraf ingen er indeholdt i noget andet sæt. Hvis V er et sæt af n boolske variable, definerer antikæden A af delmængder af V en monoton boolsk funktion f , når værdien af ​​f er sand for det givne sæt af input, hvis en delmængde af input af funktion f er sand, hvis den tilhører A og falsk ellers. Omvendt definerer enhver monoton boolsk funktion således en antikæde, de minimale delmængder af boolske variabler, der tvinger funktionen til at evaluere til sand. Derfor er Dedekind-tallet M ( n ) lig med antallet af forskellige antikæder af delmængder af n -elementsættet [3] .

En tredje ækvivalent måde at beskrive den samme klasse på bruger gitterteori . Fra to monotone boolske funktioner f og g , kan vi finde to andre monotone boolske funktioner og deres logiske konjunktion og logiske disjunktion hhv. Familien af ​​alle monotone boolske funktioner af n input danner sammen med disse to operationer et distributivt gitter defineret af Birkhoffs repræsentationssætning fra et delvist ordnet sæt af delmængder af n variable med en partiel inklusionsrækkefølge af mængder . Denne konstruktion giver et frit fordelingsgitter med n generatorer [6] . Således tæller Dedekind-tal antallet af elementer i frie fordelingsgitter [7] [8] [9] .

Dedekind-tal tæller også (én mere) antallet af abstrakte simpliciale komplekser på n elementer, en familie af mængder med den egenskab, at enhver delmængde af en mængde i familien også tilhører familien. Enhver antikæde definerer et simpelt kompleks , en familie af undergrupper af medlemmer af antikæder, og omvendt danner de maksimale simplices i komplekser en antikæde [4] .

Eksempel

For n =2 er der seks monotone boolske funktioner og seks antikæder af delmængder af to-elementsættet { x , y }:

Værdier

De nøjagtige værdier af Dedekind-tallene er kendt for :

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 sekvens A000372 i OEIS .

De første seks af disse numre blev givet af Kirken [7] . M (6) blev beregnet af Ward [10] , M (7) blev beregnet af Church [8] Berman og Köhler [11] , og M (8) blev beregnet af Wiederman [5] .

Hvis n er lige, så skal M ( n ) også være lige [12] . Beregning af det femte Dedekind-tal modbeviser Garrett Birkhoffs formodning om, at M ( n ) altid er delelig med [7] .

Summationsformel

Kiselevich [4] omskrev den logiske definition af antikæder til følgende aritmetiske formel for Dedekind-tal:

hvor er den -te bit af , som kan skrives ved at runde ned

Denne formel er dog ubrugelig til at beregne værdierne af M ( n ) for stor n på grund af det store antal summeringsled.

Asymptotik

Logaritmen af ​​Dedekind-tal kan estimeres nøjagtigt ved hjælp af grænser

Her tæller uligheden til venstre antallet af antikæder, hvor hvert sæt har præcis elementer, og den rigtige ulighed blev bevist af Kleitman og Markovsky [1] .

Korshunov [2] gav endnu mere præcise skøn [9]

for selv n , og

for ulige n , hvor

og

Hovedideen med disse estimater er, at i de fleste antikæder har alle sæt størrelser meget tæt på n /2 [9] . For n = 2, 4, 6, 8 giver Korshunovs formel et estimat, der har en fejl på henholdsvis 9,8 %, 10,2 %, 4,1 % og -3,3 % [13] .

Noter

  1. ↑ 1 2 Kleitman, Markowsky, 1975 .
  2. ↑ 1 2 Korsjunov, 1981 .
  3. ↑ 12 Kahn , 2002 .
  4. ↑ 1 2 3 Kisielewicz, 1988 .
  5. ↑ 12 Wiedemann , 1991 .
  6. ↑ Definitionen af ​​et frit distributivt gitter, der bruges her, tillader enhver endelig konvergens og divergens, inklusive tomme, som operationer på gitteret. For et frit distributivt gitter, hvor kun parvise konvergenser og divergenser er tilladt, bør man udelukke de øverste og nederste elementer af gitteret og trække to fra Dedekind-tallene.
  7. ↑ 123 Kirke , 1940 .
  8. ↑ 12 Kirke , 1965 .
  9. ↑ 1 2 3 Zaguia, 1993 .
  10. ↑ Ward, 1946 .
  11. ↑ Berman, Köhler, 1976 .
  12. ↑ Yamamoto, 1953 .
  13. ↑ Brown, KS, < https://www.mathpages.com/home/kmath094/kmath094.htm > 

Litteratur