Създавайки сензация в математическата общност, само с 42 цифри група учени разкриват математическата загадка на така нареченото девето число на Дедекинд.
Математиците търсят тази стойност от 1991 г. Учените от Университета Падерборн и Католическия университет в град Льовен (KU Leuven), Белгия, стигат до точната последователност от числа с помощта на суперкомпютъра Noctua, разположен там. Резултатите ще бъдат представени през септември на Международния семинар за булеви функции и техните приложения (BFA) в Норвегия.
Това, което започва като проект за дипломната работа за магистърска степен на Ленарт Ван Хиртум (Lennart Van Hirtum) тогава студент по компютърни науки в KU Leuven и сега научен сътрудник в Университета в Падерборн, се превръща в огромен успех.
По-ранните числа в поредицата са открити от самия математик Ричард Дедекинд, когато той дефинира проблема през 1897 г., а по-късно - от девама велики ранни специалисти по компютърни науки като Рандолф Чърч (Randolph Church) и Морган Уорд (Morgan Ward).
„В продължение на 32 години изчисляването на D(9) бе открито предизвикателство и бе под въпрос дали изобщо ще бъде възможно да се изчисли това число“, разказва Ван Хиртум.
Предишното число в последователността на Дедекинд, 8-то число на Дедекинд, е намерено през 1991 г. с помощта на Cray 2, най-мощният суперкомпютър по това време.
„Струваше ни се възможно, че вече може да се изчисли 9-то число на голям суперкомпютър“, разказва Ван Хиртум, описвайки мотивацията за амбициозния проект, който той първоначално изпълнява съвместно с ръководителите на магистърската си дипломна работа в KU Льовен.
Що е то число на Дедекинд
Числото на Дедекинд е броят на монотонните булеви функции. Булевите функции се разглеждат от булевата алгебра, раздел от математическата логика. Тези функции приемат като вход n променливи, които могат да имат само две стойности: 0 или 1 (което съответства на "лъжа" или "истина"). Резултатът също може да бъде 0 или 1.
Монотонните булеви функции са функции, които ограничават логиката до два оператора - логическо "и" (AND, "&", конюнкция, "∧") и логическо "или" (OR, "|", дизюнкция, "∨"), без оператора "NOT". Така монотонните функции поредставляват подмножество от всички възможни булеви функции.
 |
"1" тогава и само тогава, ако всички входове са "1" "0" ако и само ако поне един вход е "0" |
 |
"1" ако и само ако поне един вход е "1" "0" тогава и само тогава, ако всички входове са "0" |
Кредит: elementy.ru
Колкото повече са променливите, толкова по-голямо е числото. Например, ако има 0 променливи, могат да съществуват само две функции: f = 0 и f = 1. За една променлива има три функции: f(x) = 0, f(x) = 1 и f(x) = x. За две променливи се добавят още три: втората променлива f(x,y) = y, както и логическото AND (x ∧ y) и логическото OR (x ∨ y). За три аргумента броят на функциите вече се увеличава до D(4) = 20, а за пет аргумента - до D(5) = 168.
В препринтите на arXiv.org математиците обясняват, че по същество може да си представите монотонна булева функция в две, три и безкрайно много измерения като игра с n-измерен куб. Според правилата на тази игра, балансирате куба на един ъгъл, след което оцветявате всеки от останалите ъгли в бяло или червено. При това никога не трябва да поставяте белия ъгъл върху червения. Така се получава нещо като вертикално пресичане на бялото и червеното. Целта на играта е да преброите колко различни конюнкции има.
Кредит: uni-paderborn.de
Това са първите 8 числа на Дедекинд.
Тази задача е решена преди 32 години и математиците стигат до деветата задънена улица
Първите няколко числа на Дедекинд били доста очевидни, след което започнали трудностите. Невъзможно е да се намери дедекиндово число за голям брой аргументи толкова просто, затова се използват или асимптотични решения, които определят интервала, в който попада желаната стойност, или точна формула, за чието използване са необходими значителни изчислителни ресурси. Формулата представлява сума, която се изразява от второто определение на числата на Дедекинд чрез антивериги, т.е. подмножества на подредено множество, в които (за разлика от веригата) всякакви двойки елементи са несравними. Числото на Дедекинд в този случай определя броя на елементите в решетката от антивериги в частично подреденото множество.
Резултатите от сумирането по тези формули се търсят с помощта на суперкомпютри. Последното вече намерено число на Дедекинд е осмото - D(8). Това 23-цифрено число е изчислено още през 1991 г. и са били необходими 200 часа, и то с един от най-мощните суперкомпютри по онова време - Cray-2. Оказва се, че това е 23-цифрено число.
През 2014 г. белгийските математици Патрик Де Каусмакер (Patrick De Causmaecker) и Стефан Де Ванемакер (Stefan De Wannemacker) от Католическия университет в Льовен предлагат друга версия на формулата, чрез която сумирането може да се използва за намиране на дедекиндови числа.
Сумиране за изчисляване на дедекиндните числа. Кредит: Lennart Van Hirtum et al / arXiv, 2023
Тази формула позволява да се разложи решетката на антиверигите на подрешетки в пространства с по-малка размерност. Шестизмерните подрешетки са били достатъчни, за да се изчисли на суперкомпютър D(8) и да се потвърди вече известната стойност, но за изчисляване на следващото число компютърната мощ не бе достатъчна.
Сега учените са взели тази формула и са я адаптирали към възможностите на съвременните компютри. След три месеца изчисления със суперкомпютърния клъстер Noctua 2 те успяват да получат деветото число на Дедекинд.
И ето как изглежда то: 286386577668298411128469151667598498812366.
Справка: A computation of D(9) using FPGA Supercomputing
Lennart Van Hirtum, Patrick De Causmaecker, Jens Goemaere, Tobias Kenter, Heinrich Riebler, Michael Lass and Christian Plessl https://arxiv.org/pdf/2304.03039.pdf
Източници:
Ninth Dedekind number discovered: Scientists solve long-known problem in mathematics, Universität Paderborn
Dedekind's Problem, Generating the Monotone Boolean Functions, mathpages
Коментари
Моля, регистрирайте се от TУК!
Ако вече имате регистрация, натиснете ТУК!
Няма коментари към тази новина !
Последни коментари