Mik azok a Dedekind-számok, és miért tartott 126 évig az első 9 felfedezése?

Richard Dedekind 1897-ben megjelent, akkoriban kevés figyelmet kapott tanulmányában a természetes számok véges rendszereivel és azok legnagyobb közös osztóival foglalkozott. Úgy vélte, hogy ezek az osztók – még ha nem is prímszámok – bizonyos matematikai vizsgálatokban hasznosak lehetnek, ezért érdemes rendszerezni az ebből fakadó törvényszerűségeket. A matematikus mindössze öt számot tudott megadni abból a sorozatból, amelyet ma Dedekind-számokként ismerünk. Ide tartozik a 0, 1, 4, 18 és a 166, bár ebben ő maga sem volt biztos. Dedekind szerint a számok rendkívül gyorsan növekednek, így nem is próbálkozott egy általános képlet létrehozásával.

Az egyik legszemléletesebb megközelítés egy n-dimenziós kockára épül. A kockát az egyik csúcsára állítjuk, majd a többi csúcsot pirosra vagy fehérre színezzük úgy, hogy fehér pont soha ne kerülhessen egy piros fölé. Az így létrejött „metszéseket” kell megszámolni ahhoz, hogy megkapjuk az adott dimenzióhoz tartozó Dedekind-számot. Nulla dimenzióban két lehetőség van, egy dimenzióban három, kettőben hat, háromban húsz. Négy dimenzióban már 168 különböző elrendezés adódik, ami kettővel több annál, mint amit Dedekind eredetileg megadott – a különbség abból fakad, hogy a modern matematika néhány, a matematikus által triviálisnak tartott esetet is beleszámol.

Egy másik értelmezés halmazelméleti alapú. Ha veszünk egy n elemű halmazt, annak összes részhalmaza egy úgynevezett részhalmazrácsot alkot. A Dedekind-szám ebben az esetben azt mutatja meg, hány olyan antilánc található a rácsban, ahol az elemek nem rendezhetők egymás alá vagy fölé. Létezik egy harmadik, Dedekind eredeti definíciójához közelebb álló megközelítés is, amely monoton Boole-függvényekkel dolgozik. Ezek olyan logikai függvények, ahol egy bemenet 0-ról 1-re váltása nem okozhatja a kimenet 1-ről 0-ra váltását. Az ilyen függvények száma n változó esetén éppen az n-edik Dedekind-szám.

Mindegyik megközelítésről elmondható, hogy a sorozat számai rendkívül gyorsan nőnek, a nyolcadik Dedekind-szám például már 23 számjegyű. Hosszú évtizedekig minden új érték kiszámítása komoly akadályokba ütközött. Az ötödik számra több mint 40 évet kellett várni, a hatodikat 1946-ban, a hetediket 1965-ben, a nyolcadikat pedig 1991-ben, egy akkori szuperszámítógépen végzett, 200 órás számítás eredményeként találták meg.

A kilencedik Dedekind-szám megfejtése sokáig lehetetlennek tűnt. Bár a számítástechnika fejlődése elvileg lehetővé tette volna a kiszámítását, a feladat még modern algoritmusokkal is rendkívül összetett. Végül két egymástól független kutatócsoport egyszerre talált megoldást.

A paderborni egyetem kutatói a képletben rejlő szimmetriákat kihasználva drasztikusan csökkentették a szükséges számítások mennyiségét, és egy nagy teljesítményű szuperszámítógépen futtatták a programot. Eközben a drezdai műszaki egyetem matematikusa, Christian Jäkel egy teljesen más, mátrixszorzásra épülő módszerrel, hagyományos számítógépen jutott el ugyanahhoz az eredményhez. Végül 2023 márciusában publikálta a 42 számjegyű számot, amelyet néhány nappal később a másik csapat eredménye is megerősített – írja az IFLScinece.

A kilencedik Dedekind-szám kiszámítása is mérföldkőnek számít, ám a tizediké már egészen más problémákat is felvet. A kutatók szerint a számítás energiaigénye megközelítené a Nap teljes teljesítményét, az eredmény nagyságrendje pedig a látható univerzum atomjainak számával vetekedne. A szakemberek úgy látják, hogy a tizedik Dedekind-szám kiszámítására nem a közeljövőben fog sor kerülni. Hasonlóan bonyolult akadályokba ütköztek a kutatók a Busy Beaver kiszámításakor, amely már a matematika határait feszegeti.