Dedekind čísla

Stabilní verze byla zkontrolována 29. března 2022 . Existují neověřené změny v šablonách nebo .

Dedekindova čísla jsou rychle rostoucí posloupnost celých čísel pojmenovaná po Richardu Dedekindovi , který je definoval v roce 1897. Dedekindovo číslo M ( n ) počítá počet monotónních booleovských funkcí n proměnných . Ekvivalentně tato čísla počítají počet antiřetězců podmnožin n -prvkové množiny, počet prvků ve volné distributivní mřížce s n generátory nebo počet abstraktních simpliciálních komplexů s n prvky.

Známé jsou přesné asymptotické odhady M ( n ) [1] [2] [3] a přesné vyjádření jako součet [4] . Dedekindův problém výpočtu hodnot M ( n ) však zůstává obtížný – není znám žádný uzavřený výraz pro M ( n ) a přesné hodnoty M ( n ) byly nalezeny pouze pro [5] .

Definice

Booleovská funkce je funkce, která přijímá jako vstup n booleovských proměnných (to znamená hodnoty, které mohou být buď nepravda (false) nebo pravda (pravda), nebo ekvivalentně binární hodnoty , které mohou být 0 nebo 1) , a jako výstup dává další booleovskou proměnnou. Funkce je monotónní , pokud pro jakoukoli kombinaci vstupů může změna jedné vstupní proměnné z false na true pouze změnit výstup z false na true, ale ne z true na false. Dedekindovo číslo M ( n ) je počet různých monotónních booleovských funkcí n proměnných.

Antiřetěz množin (také známý jako rodina Spencer ) je rodina množin, z nichž žádná není obsažena v žádné jiné množině. Je-li V množina n booleovských proměnných, antiřetězec A podmnožin V definuje monotónní booleovskou funkci f , když hodnota f je pravdivá pro danou množinu vstupů, pokud některá podmnožina vstupů funkce f je pravdivá, pokud patří do A a jinak nepravda. Naopak jakákoli monotónní booleovská funkce tak definuje antiřetězec, minimální podmnožiny booleovských proměnných, které nutí funkci vyhodnotit jako true. Dedekindovo číslo M ( n ) je tedy rovno počtu různých antiřetězců podmnožin množiny n -prvků [3] .

Třetí ekvivalentní způsob popisu stejné třídy používá teorii mřížky . Ze dvou monotónních booleovských funkcí f a g můžeme najít další dvě monotónní booleovské funkce a , jejich logickou konjunkci a logickou disjunkci . Rodina všech monotónních booleovských funkcí n vstupů spolu s těmito dvěma operacemi tvoří distributivní mříž definovanou Birkhoffovou větou o reprezentaci z částečně uspořádané množiny podmnožin n proměnných s řádem částečného začlenění množin. . Tato konstrukce poskytuje volnou distributivní mřížku s n generátory [6] . Dedekindova čísla tedy počítají počet prvků ve volných distributivních svazech [7] [8] [9] .

Dedekindova čísla také počítají (ještě jedno) počet abstraktních simpliciálních komplexů na n prvcích, rodině množin s vlastností, že do rodiny patří také jakákoli podmnožina množiny v rodině. Jakýkoli antiřetězec definuje simpliciální komplex , rodinu podmnožin členů antiřetězců, a naopak maximální simplice v komplexech tvoří antiřetězec [4] .

Příklad

Pro n =2 existuje šest monotónních booleovských funkcí a šest antiřetězců podmnožin dvouprvkové množiny { x , y }:

Hodnoty

Přesné hodnoty Dedekindových čísel jsou známé pro :

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 sekvence A000372 v OEIS .

Prvních šest z těchto čísel uvedl Church [7] . M (6) vypočítal Ward [10] , M (7) vypočítal Church [8] Berman a Köhler [11] a M (8) vypočítal Wiederman [5] .

Je-li n sudé, pak M ( n ) musí být také sudé [12] . Počítání pátého Dedekindova čísla vyvrací domněnku Garretta Birkhoffa , že M ( n ) je vždy dělitelné [7] .

Sumační vzorec

Kiselevich [4] přepsal logickou definici antiřetězců do následujícího aritmetického vzorce pro Dedekindova čísla:

kde je -tý bit z , který lze zapsat zaokrouhlením dolů

Tento vzorec je však nepoužitelný pro výpočet hodnot M ( n ) pro velké n kvůli velkému počtu součtových členů.

Asymptotika

Logaritmus Dedekindových čísel lze přesně odhadnout pomocí mezí

Nerovnice nalevo zde počítá počet antiřetězců, ve kterých má každá množina přesně prvky, a pravou nerovnost dokázali Kleitman a Markovsky [1] .

Korshunov [2] poskytl ještě přesnější odhady [9]

pro sudé n , a

pro liché n , kde

a

Hlavní myšlenkou těchto odhadů je, že ve většině antichainů mají všechny sady velikosti velmi blízké n /2 [9] . Pro n = 2, 4, 6, 8 dává Korshunovův vzorec odhad, který má chybu 9,8 %, 10,2 %, 4,1 % a -3,3 % [13] .

Poznámky

  1. ↑ 1 2 Kleitman, Markowsky, 1975 .
  2. ↑ 1 2 Korshunov, 1981 .
  3. ↑ 12 Kahn , 2002 .
  4. ↑ 1 2 3 Kisielewicz, 1988 .
  5. ↑ 12 Wiedemann , 1991 .
  6. ↑ Zde použitá definice volné distributivní mřížky umožňuje jakékoli konečné konvergence a divergence, včetně prázdných, jako operace na mřížce. U volné distributivní mřížky, ve které jsou povoleny pouze párové konvergence a divergence, bychom měli vyloučit horní a spodní prvky mřížky a odečíst dva od Dedekindových čísel.
  7. ↑ Kostel 123 , 1940 .
  8. ↑ Kostel 12 , 1965 .
  9. ↑ 1 2 3 Zaguia, 1993 .
  10. ↑ Ward, 1946 .
  11. ↑ Berman, Köhler, 1976 .
  12. ↑ Jamamoto, 1953 .
  13. ↑ Hnědá, KS, < https://www.mathpages.com/home/kmath094/kmath094.htm > 

Literatura