Hienot numerot

Vakaa versio tarkistettiin 29.3.2022 . Malleissa tai malleissa on vahvistamattomia muutoksia .

Dedekind-luvut ovat nopeasti kasvava kokonaislukusarja , joka on nimetty Richard Dedekindin mukaan, joka määritteli ne vuonna 1897. Dedekind-luku M ( n ) laskee n muuttujan monotonisten Boolen funktioiden lukumäärän . Vastaavasti nämä luvut laskevat n -alkiojoukon osajoukkojen antiketjujen lukumäärän, vapaan distributiivisen hilan alkioiden määrän , jossa on n generaattoria , tai abstraktien yksinkertaisten kompleksien , joissa on n elementtiä.

M ( n ) [1] [2] [3] tarkat asymptoottiset estimaatit ja tarkka lauseke summana [4] tunnetaan. Dedekindin ongelma M ( n ):n arvojen laskemisessa on kuitenkin edelleen vaikea – suljetun muotoista lauseketta arvolle M ( n ) ei tunneta, ja M ( n ):n tarkat arvot on löydetty vain [5] .

Määritelmät

Boolen funktio on funktio, joka ottaa syötteenä n loogista muuttujaa (eli arvoja, jotka voivat olla joko epätosi (false) tai tosi (tosi), tai vastaavasti binääriarvoja , jotka voivat olla joko 0 tai 1) ja antaa toisen loogisen muuttujan tulosteena. Funktio on monotoninen , jos yhden syötemuuttujan vaihtaminen epätosi arvosta tosi voi muuttaa tulosteen vain epätosi arvosta tosi, mutta ei tosi arvosta epätosi. Dedekind-luku M ( n ) on n muuttujan eri monotonisten Boolen funktioiden lukumäärä.

Joukkojen vastaketju (tunnetaan myös nimellä Spencer-perhe ) on joukko joukkoja, joista mikään ei sisälly mihinkään muuhun joukkoon. Jos V on joukko n Boolen muuttujaa, V :n osajoukkojen antiketju A määrittää monotonisen Boolen funktion f , kun f:n arvo on tosi annetulle syötejoukolle, jos jokin funktion f syötteiden osajoukko on tosi, jos se kuuluu A ja false muuten. Sitä vastoin mikä tahansa monotoninen Boolen funktio määrittää siten antiketjun, Boolen muuttujien vähimmäisosajoukot, jotka pakottavat funktion evaluoitumaan todeksi. Siksi Dedekind-luku M ( n ) on yhtä suuri kuin n - elementtijoukon [3] osajoukkojen eri antiketjujen lukumäärä .

Kolmas vastaava tapa kuvata samaa luokkaa käyttää hilateoriaa . Kahdesta monotonisesta Boolen funktiosta f ja g löydämme kaksi muuta monotonista Boolen funktiota ja , niiden looginen konjunktio ja looginen disjunktio . Kaikkien n syötteen monotonisten Boolen funktioiden perhe muodostaa yhdessä näiden kahden operaation kanssa Birkhoffin esityslauseella en] määritellyn distributiivisen hilan n: n muuttujan osajoukkojen joukosta osittaisen joukon sisällyttämisjärjestyksen kanssa. . Tämä konstruktio antaa vapaan distributiivisen hilan , jossa on n generaattoria [6] . Siten Dedekind-luvut laskevat elementtien lukumäärän vapaassa distributiivisessa hilassa [7] [8] [9] .

Dedekind-luvut laskevat myös (yhden lisää) abstraktien yksinkertaisten kompleksien lukumäärän n alkiolla , joukkojen perhettä, jolla on ominaisuus, että mikä tahansa joukon osajoukko perheessä kuuluu myös perheeseen. Mikä tahansa antiketju määrittelee yksinkertaisen kompleksin , antiketjujen jäsenten osajoukkojen perheen, ja päinvastoin, kompleksien suurimmat yksinkertaisuudet muodostavat antiketjun [4] .

Esimerkki

Arvolle n =2 on kuusi monotonista Boolen funktiota ja kuusi kaksielementtijoukon { x , y } osajoukkojen antiketjua:

Arvot

Dedekind-lukujen tarkat arvot tunnetaan seuraavista :

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 sekvenssi A000372 OEIS : ssä .

Ensimmäiset kuusi näistä luvuista antoi kirkko [7] . M (6) laski Ward [10] , M (7) laski Church [8] Berman ja Köhler [11] ja M (8) laski Wiederman [5] .

Jos n on parillinen, niin M ( n ) on myös parillinen [12] . Viidennen Dedekind-luvun laskeminen kumoaa Garrett Birkhoffin oletuksen, jonka mukaan M ( n ) on aina jaollinen [7] :llä .

Summakaava

Kiselevich [4] kirjoitti uudelleen antiketjujen loogisen määritelmän seuraavaksi aritmeettiseksi kaavaksi Dedekind-luvuille:

missä on -th bitti , joka voidaan kirjoittaa pyöristämällä alaspäin

Tämä kaava on kuitenkin hyödytön M ( n ) -arvojen laskemiseen suurelle n :lle, koska summatermejä on paljon.

Asymptotiikka

Dedekind-lukujen logaritmi voidaan arvioida tarkasti rajojen avulla

Tässä vasemmanpuoleinen epäyhtälö laskee niiden antiketjujen määrän, joissa jokaisessa joukossa on täsmälleen elementtejä, ja oikean epäyhtälön osoittivat Kleitman ja Markovsky [1] .

Koršunov [2] antoi vielä tarkempia arvioita [9]

jopa n , ja

parittomille n , missä

ja

Näiden arvioiden pääidea on, että useimmissa antiketjuissa kaikkien joukkojen koot ovat hyvin lähellä n /2 :ta [9] . Kun n = 2, 4, 6, 8, Koršunovin kaava antaa arvion, jonka virhe on 9,8 %, 10,2 %, 4,1 % ja -3,3 % [13] .

Muistiinpanot

  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. ↑ Tässä käytetty vapaan distributiivisen hilan määritelmä sallii kaikki äärelliset konvergenssit ja divergenssit, mukaan lukien tyhjät, operaatioina hilassa. Vapaassa distributiivisessa hilassa, jossa sallitaan vain parittaiset konvergenssit ja divergenssit, tulee jättää hilan ylä- ja alaelementit pois ja vähentää kaksi Dedekind-luvuista.
  7. ↑ 123 kirkko , 1940 .
  8. ↑ 12 kirkko , 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 > 

Kirjallisuus