Dedekind numere

Versiunea stabilă a fost verificată pe 29 martie 2022 . Există modificări neverificate în șabloane sau .

Numerele Dedekind sunt o succesiune de numere întregi în creștere rapidă numită după Richard Dedekind , care le-a definit în 1897. Numărul Dedekind M ( n ) numără numărul de funcții booleene monotone ale n variabile. În mod echivalent, aceste numere numără numărul de antilanțuri de submulțimi ale unei mulțimi de n elemente, numărul de elemente dintr-o rețea distributivă liberă cu n generatoare , sau numărul de complexe simpliale abstracte cu n elemente.

Estimările asimptotice exacte ale lui M ( n ) [1] [2] [3] și expresia exactă ca sumă [4] sunt cunoscute. Cu toate acestea , problema lui Dedekind de a calcula valorile lui M ( n ) rămâne dificilă - nu se cunoaște nicio expresie în formă închisă pentru M ( n ), iar valorile exacte ale lui M ( n ) au fost găsite numai pentru [5] .

Definiții

O funcție booleană este o funcție care ia ca intrare n variabile booleene (adică valori care pot fi fie false (false) fie adevărate (adevărate), fie, în mod echivalent, valori binare , care pot fi fie 0, fie 1), și oferă o altă variabilă booleană ca ieșire. O funcție este monotonă dacă, pentru orice combinație de intrări, schimbarea unei variabile de intrare de la fals la adevărat poate schimba numai rezultatul de la fals la adevărat, dar nu de la adevărat la fals. Numărul Dedekind M ( n ) este numărul de funcții booleene monotone diferite ale n variabile.

Un antilanț de mulțimi (cunoscut și sub numele de familie Spencer ) este o familie de mulțimi care nu sunt conținute în niciun alt set. Dacă V este o mulțime de n variabile booleene, anti-lanțul A de submulțimi ale lui V definește o funcție booleană monotonă f când valoarea lui f este adevărată pentru setul dat de intrări dacă un subset de intrări ale funcției f este adevărată dacă aparține A și fals în caz contrar. Dimpotrivă, orice funcție booleană monotonă definește astfel un antilanț, subseturile minime de variabile booleene care forțează funcția să fie evaluată la adevărat. Prin urmare, numărul Dedekind M ( n ) este egal cu numărul de antilanțuri diferite de submulțimi ale mulțimii de n - elemente [3] .

Un al treilea mod echivalent de a descrie aceeași clasă folosește teoria rețelei . Din două funcții booleene monotone f și g , putem găsi alte două funcții booleene monotone și , respectiv, conjuncția lor logică și respectiv disjuncția logică . Familia tuturor funcțiilor booleene monotone ale n intrări, împreună cu aceste două operații, formează o rețea distributivă definită de teorema de reprezentare Birkhoff dintr-o mulțime parțial ordonată de submulțimi de n variabile cu un ordin de includere parțială a mulțimilor. . Această construcție oferă o rețea distributivă liberă cu n generatoare [6] . Astfel, numerele Dedekind numără numărul de elemente din rețelele de distribuție liberă [7] [8] [9] .

Numerele dedekind mai numără (încă unul) numărul de complexe simpliale abstracte pe n elemente, o familie de mulțimi cu proprietatea că orice submulțime a unei mulțimi din familie aparține și ea familiei. Orice antilanț definește un complex simplicial , o familie de submulțimi de membri ai antilanțului și invers, simplexurile maxime din complexe formează un antilanț [4] .

Exemplu

Pentru n =2, există șase funcții booleene monotone și șase antilanțuri de submulțimi ale mulțimii de două elemente { x , y }:

Valori

Valorile exacte ale numerelor Dedekind sunt cunoscute pentru :

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 secvența A000372 în OEIS .

Primele șase dintre aceste numere au fost date de Church [7] . M (6) a fost calculat de Ward [10] , M (7) a fost calculat de Church [8] Berman și Köhler [11] , iar M (8) a fost calculat de Wiederman [5] .

Dacă n este par, atunci M ( n ) trebuie să fie și par [12] . Calcularea celui de-al cincilea număr Dedekind infirmă conjectura lui Garrett Birkhoff că M ( n ) este întotdeauna divizibil cu [7] .

Formula de însumare

Kiselevich [4] a rescris definiția logică a antilanțurilor în următoarea formulă aritmetică pentru numerele Dedekind:

unde este --lea bit din , care poate fi scris prin rotunjire în jos

Cu toate acestea, această formulă este inutilă pentru calcularea valorilor lui M ( n ) pentru n mare din cauza numărului mare de termeni de însumare.

Asimptotice

Logaritmul numerelor Dedekind poate fi estimat exact folosind limite

Aici, inegalitatea din stânga numără numărul de antilanțuri în care fiecare mulțime are exact elemente, iar inegalitatea dreaptă a fost demonstrată de Kleitman și Markovsky [1] .

Korshunov [2] a dat estimări și mai precise [9]

pentru chiar n , și

pentru n impar , unde

și

Ideea principală a acestor estimări este că în majoritatea antilanțurilor toate mulțimile au dimensiuni foarte apropiate de n /2 [9] . Pentru n = 2, 4, 6, 8, formula lui Korshunov oferă o estimare care are o eroare de 9,8%, 10,2%, 4,1% și respectiv -3,3% [13] .

Note

  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. ↑ Definiția unei rețele distributive libere utilizată aici permite orice convergențe și divergențe finite, inclusiv cele goale, ca operații pe rețea. Pentru o rețea distributivă liberă, în care sunt permise doar convergențele și divergențele pe perechi, ar trebui să excludeți elementele de sus și de jos ale rețelei și să scădeți două din numerele Dedekind.
  7. ↑ 123 Biserica , 1940 .
  8. ↑ 12 Biserica , 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 > 

Literatură