От квантовой гравитации до комбинаторики: 5 математических проблем

Гипотеза Римана

Гипотеза немецкого математика Бернхарда Римана, сформулированная в 1859 году и вошедшая в список семи задач тысячелетия, описывает распределение простых чисел (это числа, которые делятся только на один и себя) среди натуральных. Воспользовавшись давней идеей Леонарда Эйлера, Риман определил дзета-функцию. Что это такое? Представьте, что вам нужно сложить бесконечный ряд чисел, так называемых обратных квадратов:

Кажется, что в сумме получится бесконечность. Эта задача, прозванная базельской проблемой, долгое время считалась нерешенной. Однако Леонард Эйлер сумел показать, что сумма конечна и равна. Эйлер подставлял в показатель степени в знаменателях дробей четные натуральные числа до 26 и последовательно рассчитывал результат для каждого ряда — ряда обратных четвертых, шестых, восьмых степеней и так далее, — и всегда получалось конечное число. Эта сумма и есть дзета-функция ζ (s), где s — показатель степени в знаменателях. При вводе четного натурального числа функция выводит значение соответствующего ряда: ζ (2) =. Эйлер нашел способ выразить дзета-функцию не в виде суммы, а в виде произведения, где p — простое число:

Эта формула работает не только для целых чисел, но и для действительных (всех, которые можно изобразить на числовой прямой) при условии, что s>1.

Риман расширил диапазон: он показал, что дзета-функцию можно находить и для комплексных чисел, которые изобразить на числовой прямой невозможно, зато возможно показать на координатной плоскости. Одним из результатов этой работы стала формула для расчета количества простых чисел до заданного предела. Риман предположил, что количество простых чисел до x выражается через распределение так называемых «нетривиальных нулей» дзета-функции. Это значения, которые нужно подставить в функцию, чтобы результат был равен нулю. Какие-то значения очевидны для математиков (это отрицательные четные целые числа –2, –4, –6), но поиск других требует определенных усилий. Риман вычислил несколько нетривиальных корней и заметил, что у них всех есть что-то общее: все они выглядят как ½ + it, где i — квадратный корень из отрицательного числа, а t является действительным числом. Это можно изобразить на координатной плоскости: область значений нетривиальных нулей функции будет выглядеть как вертикальная линия.

Существуют косвенные свидетельства, что гипотеза Римана верна, но найти исчерпывающее доказательство чрезвычайно сложно, и множество математиков по всему миру пытаются это сделать. Если им это удастся, то в теории чисел откроются новые горизонты. Кроме того, дзета-функция используется в практических задачах, связанных с простыми числами, например в криптографии.

Отрывок из книги Иэна Стюарта «Величайшие математические задачи» о гипотезе Римана и ее доказательстве

Гипотеза Виттена

Эдвард Виттен — один из немногих физиков, у которого имеются математические заслуги. В 1990 году он получил Филдсовскую премию, одну из престижнейших математических наград. Его гипотеза, касающаяся квантовой гравитации, которая объединяет гравитационную теорию Эйнштейна и квантовую теорию, стала прорывом в математике. Четырехмерное пространство-время очень сложно для представления, поэтому физики пытаются представить, как объединенная теория выглядит в двумерном пространстве, и выстраивают различные математические модели.

Двумерная квантовая гравитация описывает движение частицы — или, согласно теории струн, эволюционирующего во времени одномерного объекта, струны. Согласно квантовой теории, для описания жизнедеятельности частицы нужно ввести интегрирование по пространству всех возможных двумерных поверхностей. В модели двумерной квантовой гравитации А все возможные двумерные поверхности заменяются их триангуляцией, или разбиениями на многоугольники. В результате анализа этой модели обнаружилась связь между уравнением Кортевега — де Фриза, описывающим движением волн в мелкой воде, и некоторыми характеристиками разбиения плоскостей на многоугольники. Числа, отвечающие за асимптоты по количеству разбиений на многоугольники, складываются в функцию, которая является решением этого уравнения.

В разработке модели B сыграл решающую роль Виттен. Эта модель описывается в терминах алгебраической геометрии — алгебраических кривых, заданных полиномиальными уравнениями, и их пространства. Виттен показал, что функция, которая строится, анализирует геометрию пространств алгебраических кривых, в точности совпадает с функциями, возникающими при анализе разбиения поверхностей на многоугольники, и, как следствие, является решением уравнения Кортевега — де Фриза. Иными словами, Виттен предположил, что модели A и B эквивалентны. Математическое сообщество несколько десятилетий изучало геометрию пространств таких кривых, но результатов, которые были бы справедливы для всех пространств, не было. Гипотеза Виттена оказалась прорывом, и математическое сообщество ринулось на поиски ее доказательств, которые вскоре были найдены.

Математик Сергей Ландо о математических основаниях гипотезы Виттена

Проблема перебора

Проблема перебора уже несколько десятилетий остается одной из центральных проблем в математической логике и Computer Science. Можно ли свести сложные задачи, которые решаются только путем перебора множества вариантов, к более простым? Совпадают ли классы задач P и NP?

Задачи P класса можно решить быстро, то есть за полиноминальное время. Если задать вычислительной машине исходный объем данных n битов, то ее число шагов по ее решению будет ограничено некоторой степенью числа n (полиномом). Задачи NP класса — медленные. Главный вопрос в отношении таких задач: если положительный ответ на какой-то вопрос можно проверить за полиномиальное время, то правда ли, что ответ на этот вопрос можно столь же быстро найти?

Впервые вопрос о равенстве классов поставили независимо друг от друга Стивен Кук и Леонид Левин в 1970-х годах. Они заметили, что самые разные переборные задачи универсальны: если кто-то придумает быстрый алгоритм решения одной из них, то с его помощью можно будет быстро решать любую другую переборную задачу. С тех пор появилось много интересных исследований, но равенство или неравенство классов P и NP так и не было доказано. Эта проблема вошла в список задач тысячелетия.

Если окажется, что классы P и NP совпадают и есть быстрый способ решения сложных задач, то разрушится вся система криптографии с открытым ключом, которая, предположительно, обеспечивает безопасность личных данных. В то же время можно будет быстро решать важные практические задачи. В противном случае надежность современной криптографии подтвердится. Квантовые компьютеры могут ускорить решение задач NP-класса методом обыкновенного перебора, однако не исключено, что они смогут быстро решать только определенный тип задач.

Математик Александр Шень о проблеме перебора и машине Тьюринга

16-я проблема Гильберта

Это одна из 23 задач, которые Давид Гильберт предложил 8 августа 1900 года на II Международном конгрессе математиков. Она связана с топологией алгебраических кривых и поверхностей и до сих пор считается решенной лишь частично. Чтобы понять, что это за проблема, необходимо обратиться к понятию предельного цикла. Представьте себе маятник в часах, который непрерывно движется, то есть его амплитуда и частота остаются постоянными. С точки зрения математика, такой маятник движется по предельному циклу: вне зависимости от начального положения со временем поведение маятника приближается к конкретному периодическому движению, то есть он проходит одни и те же этапы. Даже очень простые системы, которые можно описать простыми формулами, могут обладать несколькими предельными циклами, но определение того, сколько их, оказывается очень сложной задачей.

16-я проблема Гильберта разделена на две части. Вторая часть затрагивает максимальное количество и расположение предельных циклов в дифференциальном уравнении на плоскости, и она оказалась довольно коварной. В середине XX века математики Петровский и Ландис представили свое решение, которое основано на использовании комплексных чисел, но оно оказалось ошибочным. Тем не менее этот путь привел к открытию многих интересных явлений, связанных именно с дифференциальными уравнениями в комплексной области.

Математик Илья Щуров о предельных циклах и поисках решения проблемы Гильберта

О 21-й проблеме Гильберта

Теорема Семереди (гипотеза Эрдеша — Турана)

Гипотеза Эрдеша — Турана, затрагивающая проблемы комбинаторики, была доказана в 1960-х годах венгерским математиком Эндре Семереди. За это в 2012 году он получил самую престижную математическую награду — премию Абеля. Эта гипотеза, сформированная в 1936 году, обобщала теорему Ван дер Вардена. Теорема утверждала, что в ряду натуральных чисел, каждому из которых приписан черный или белый цвет, всегда можно найти прогрессию произвольной длины, состоящую из элементов одного цвета, находящихся на одинаковом расстоянии друг от друга (5-10-15…). Более того, такая прогрессия обнаруживается, сколько бы цветов мы ни использовали.

Эрдеш и Туран предположили, что верен гораздо более сильный результат: такую прогрессию всегда можно обнаружить в цвете, в который раскрашено наибольшее количество натуральных чисел множества, при этом совершенно неважно, как раскрашены остальные числа. Оказалось, что всегда можно найти прогрессию из одного, двух или трех чисел, но начиная с четырех начинались проблемы. В 1969 году Эндре Семереди показал, что утверждение верно и для прогрессии из четырех элементов, а в 1975 году он получил доказательство для любого количества чисел. В своем доказательстве Семереди пользовался сложным и запутанным языком комбинаторики. Позже ученые смогли передоказать теорему в рамках различных направлений математики.

Теорема Семереди повлияла сразу на несколько математических областей: теорию графов, теорию чисел и гармонический анализ. Более того, из нее возникло и новое направление — комбинаторная эргодическая теория. Семереди сумел доказать, что любое произвольное множество, или граф, или динамическая система обязательно обладают какой-то внутренней структурой и внутренними взаимосвязями.

Математик Илья Шкредов о доказательствах теоремы Семереди и ее влиянии на математику