Иллюстрация: N + 1; Watchduck / Wikimedia Commons; Lennart Van Hirtum et al. / arXiv. Множество математических закономерностей определяет устройство нашей реальности. Так, золотое сечение является основой различных природных процессов и систем, поражая своей гармонией в структуре наиболее сложных естественных явлений. Среди известных математических объектов выделяются уникальные числа, открытые Рихардом Дедекиндом в конце XIX века. Поиск данных величин связан со сложными задачами по изучению «монотонных булевых функций», которые долгое время оставались неразгаданными. На текущий момент было идентифицировано восемь таких чисел; однако проблема поиска «девятого числа Дедекинда» остается нерешенной уже более тридцати лет, представляя собой одну из значимых проблем для современного математического сообщества.
Числа Дедекинда – это особые математические единицы, целые числа, которые играют центральную роль в изучении монотонных булевых функций. Булевы функции – это форма математической логики, которая оперирует двоичными значениями, то есть значениями, которые могут принимать два различных состояния.
Эти состояния могут быть представлены различными способами: истина и ложь или 0 и 1. В контексте чисел Дедекинда эти булевы функции используются для определения выхода из набора двоичных входов. Монотонные булевы функции являются их подкатегорией. У них есть особенность: они устроены таким образом, что замена 0 на 1 на входе приводит только к изменению выхода с 0 на 1, но не наоборот. Другими словами, эти функции “монотонны” в том смысле, что они не “возвращаются назад”: после того, как значение было изменено с 0 на 1, оно не может быть изменено в обратном направлении.
Группа математиков из Бельгии и Германии и немец Кристиан Якель независимо друг от друга рассчитали значение девятого числа Дедекинда — то есть количества монотонных булевых функций девяти переменных. Предыдущее, восьмое число нашли еще в 1991 году. Чтобы найти девятое число, состоящее из 42 знаков, математикам пришлось адаптировать уже известные формулы для параллельных вычислений. Первая группа специально для расчетов сделала программируемую вентильную матрицу, а немецкий математик — использовал вычисления на графических процессорах, пишут ученые в препринтах на arXiv.org (1, 2).
Дедекиндово число — число монотонных булевых функций, которые можно задать для определенного числа переменных. И переменные, и функции могут принимать только два значения: 0 и 1 (или true и false).
Чем больше переменных, тем больше число. Например, если переменных 0, то функций может быть только две: f = 0 и f = 1. Для одной переменной — три функции: f(x) = 0, f(x) = 1 и f(x) = x. Для двух переменных к ним прибавляются еще три: вторая переменная f(x,y) = y, а также логическое И (x ∧ y), и логическое ИЛИ (x ∨ y). Для трех аргументов число функций возрастает уже до D(4) = 20, для пяти — до D(5) = 168.
Монотонные булевы функции для 0, 1, 2 и 3 переменных. Watchduck / Wikimedia Commons
Результаты суммирования по этим формулам ищут с помощью суперкомпьютеров. Последнее из уже найденных дедекиндовых чисел — восьмое, D(8). Это 23-значное число вычислили еще в 1991 году. В 2014 году бельгийские математики Патрик де Каусмекер (Patrick De Causmaecker) и Стефан де Ваннемакер (Stefan De Wannemacker) из Лёвенского католического университета предложили еще один вариант формулы, с помощью которой суммированием можно найти дедекиндовы числа.
Сумма для вычисления дедекиндовых чисел. Lennart Van Hirtum et al. / arXiv
Теперь группа де Каусмекера, в частности его студент Леннарт ван Хиртум (Lennart Van Hirtum), совместно с группой Кристиана Плессля из Падерборнского университета нашли способ адаптировать эту формулу к существующим компьютерным возможностям. Только программными средствами эту задачу решить не удалось, поэтому ученые собрали программируемую пользователем вентильную матрицу. Чтобы получить значения необходимых 5,574 × 1018 коэффициентов в формуле суммирования, ученым потребовалось около трех месяцев на суперкомпьютерном кластере Noctua 2.
В результате им удалось получить девятое число Дедекинда, которое оказалось равным 286386577668298411128469151667598498812366. В этом числе 42 знака. Кроме самого числа, ученые предоставили данные для полученных коэффициентов, описали способ проверки вычисленного значения, а также обсудили возможные источники ошибок.
Параллельно с бельгийскими математиками девятое число Дедекинда вычислял Кристиан Якель (Christian Jäkel) из Технического университета Дрездена, который опубликовал препринт на три дня раньше коллег из Лёвенского католического университета. Ключевые аспекты решения Якеля — умножение матриц и анализ симметрий антицепей, которые удалось найти с помощью анализа формальных понятий. В отличие от ван Хиртума, Якель для своих расчетов использовал параллельные вычисления не на центральных процессорах, а на графических. В результате вычислений немецкий математик получил то же 42-значное число.
Числа Дедекинда используют, в частности, в теории алгоритмов и теории графов, но на данный момент их поиск носит скорее фундаментальное значение.
Недавно математики, которые занимаются комбинаторикой, сдвинули с мертвой точки оценку для другого числа, имеющего отношение к графам. Математики показали, что верхнюю границу для диагонального числа Рамсея R(n,n) можно сдвигать вниз относительно известного экспоненциального предела 4n. Правда, в этом случае речь идет об асимптотических оценках, а не вычислении точного значения.
Для любознательных: 42 знака логики: как девятое число Дедекинда двигает вперед суперкомпьютеры и микросхемы
Девятое число Дедекинда (D(9)) равно 286 386 577 668 298 411 128 469 151 667 598 498 812 366. Этот 42-значный монстр, вычисленный международной группой ученых, закрыл математический пробел, остававшийся нерешенным более 30 лет. На первый взгляд, поиск столь гигантского числа кажется абстрактной забавой для профессоров, однако за ним скрывается колоссальный прикладной прорыв для ИТ-индустрии, архитектуры процессоров и систем обработки данных.
Что считают числа Дедекинда?
Если говорить простым языком, числа Дедекинда показывают количество возможных конфигураций для особых логических схем — монотонных булевых функций. Представьте себе цифровой автомат, на вход которого подаются нули и единицы. Функция называется монотонной, если при замене любого входного нуля на единицу выходное значение никогда не изменится с единицы на ноль (то есть результат может только «вырасти» или остаться прежним).
Сложность в том, что с ростом числа входных переменных (количества измерений) число возможных комбинаций растет не просто экспоненциально, а суперэкспоненциально:
- Для 2 переменных существует всего 6 комбинаций.
- Для 4 — 168.
- Для 8 переменных (число нашли в 1991 году) — уже 23-значное число.
- Для 9 переменных задача казалась нерешаемой. Количество вариантов сопоставимо с числом песчинок на Земле.
Практическая значимость: зачем ИТ-индустрии число D(9)?
Вычисление девятого числа Дедекинда — это не просто галочка в учебнике математики. Для современных технологий этот успех имеет три важнейших прикладных аспекта.
1. Стресс-тест и эволюция суперкомпьютеров
Чтобы найти D(9), ученые из Падерборнского университета (Германия) и Лёвенского католического университета (Бельгия) использовали суперкомпьютер Noctua 2. Прямой перебор занял бы сотни тысяч лет, поэтому математики применили сложнейшую формулу P-коэффициентов, сократив число операций до «всего лишь» 5.5 х 1018.
Такие сверхзадачи служат идеальным полигоном для тестирования вычислительных систем на пиковых нагрузках, помогая находить скрытые ошибки в параллельных вычислениях и логике обработки данных.
2. Прорыв в проектировании микросхем (FPGA)
Главная технологическая ценность эксперимента — метод, которым была решена задача. Исследователи разработали специализированный аппаратный ускоритель на базе FPGA (программируемых логических матриц). Они создали уникальную архитектуру Count Connected Cores, оптимизировав передачу данных и балансировку памяти.
Разработанный дизайн для FPGA Stratix 10 оказался в 95 раз эффективнее оптимизированного 64-ядерного процессора общего назначения (CPU)! Алгоритмы и методы микроархитектуры, созданные для поиска D(9), теперь могут применяться для оптимизации коммерческих чипов, используемых в беспилотных автомобилях, робототехнике и базовых станциях 5G/6G.
3. Теория графов, базы данных и ИИ
Монотонные булевы функции лежат в основе дискретной математики. Понимание точных границ их пространств (что и отражают числа Дедекинда) критически важно для:
- Оптимизации баз данных: ускорение работы сложных многомерных запросов.
- Теории надежности: расчет устойчивости сложных разветвленных сетей (электрических, логистических или нейросетей) к отказам отдельных узлов.
- Искусственного интеллекта: оптимизация логических деревьев решений в алгоритмах машинного обучения.
Итог
Девятое число Дедекинда показало человечеству предел текущих вычислительных методов. Ученые открыто признают: найти 10-е число этой последовательности с помощью существующих технологий физически невозможно — для этого потребуется фундаментальный переворот в алгоритмах или внедрение полноценных квантовых компьютеров. Таким образом, D(9) стало важной вехой, очертившей границы возможностей современных кремниевых систем.
Автор: Александр Дубов
Источники: https://nplus1.ru/, https://new-science.ru/
