21 марта стало известно, что в этом году Абелевская премия, одна из престижнейших наград по математике, досталась венгерскому ученому Эндре Семереди. Он удостоился этой награды за свой фундаментальный вклад в комбинаторику, теоретические основы информатики и дискретную математику в целом. Работы Семереди нашли себе неожиданное применение в совершенно, на первый взгляд, далеких от комбинаторики областях - теории динамических систем и эргодической теории.
Биография Эндре Семереди не слишком отличается от биографий других великих математиков второй половины XX века. С детства он не особенно интересовался математикой. Если быть точным, то прежде чем заняться этой наукой всерьез, он успел поработать на фабрике и поучиться на врача. Как бы то ни было, но судьба привела его в Будапештский университет имени Лоранда Этвеша, который Семереди закончил в 1965 году. После этого он поступил в аспирантуру Московского государственного университета имени Ломоносова к Израилю Гельфанду, где в 1970 году защитил диссертацию.
На тот момент Семереди активно сотрудничал с Полом Эрдешем - одним из величайших математиков XX века, известным, среди прочего, знаменитым числом Эрдеша. Всемирная слава пришла к нему в 1975 году, когда Семереди доказал теорему, позже получившую его имя. Доказательство во многом основывалось на результатах, полученных в кандидатской диссертации (в частности, там был доказан частный случай этой теоремы). Этот замечательный математический результат стоит того, чтобы остановиться на нем поподробнее.
Немного о плотности
Объектом исследования теоремы являются обычные последовательности натуральных чисел. Так как последовательности бесконечны, то говорить о количестве элементов в них бессмысленно. Вместе с тем, например, интуитивно понятно, что квадраты - то есть числа, представимые в виде квадрата натурального числа - расположены в натуральном ряду гораздо реже чем, например, четные числа. Действительно, в промежутке между любыми двумя соседними четными числами стоит всего одно число, а между двумя соседними квадратами - 2n чисел (где n2 - минимальный из двух квадратов).
Таким образом, хорошей мерой последовательности an (на самом деле всякое такое подмножество множества натуральных чисел может быть представлено в виде последовательности) натуральных чисел может служить его асимптотическая плотность. Для ее определения нам потребуется функция A(n), которая по данному n возвращает количество элементов последовательности an, не превосходящих n. Например, для уже упоминавшихся четных чисел эта функция имеет вид [n/2], где квадратные скобки означают целую часть от числа, а для квадратов - целая часть от квадратного корня из n.
Абелевская премия была учреждена в честь норвежского математика Нильса Абеля и вручается ежегодно выдающимся математикам современности. Денежная составляющая премии - около 750 тысяч евро.
Зная такую функцию, мы можем определить число - предел последовательности A(n)/n при n стремящемся к бесконечности, которое и назовем асимптотической плотностью. Сразу видно, что относительно этой величины последовательность всех четных чисел имеет плотность 0,5 (то есть каждое второе), а квадраты имеют плотность ноль - то есть их почти нет.
Предел, однако, можно определить не всегда, поэтому приходится обращаться к верхнему и нижнему пределам - соответственно максимуму и минимуму пределов всевозможных подпоследовательностей нашей последовательности (речь идет про последовательность A(n)/n). Эти пределы называются верхней и нижней плотностью (или еще говорят верхняя и нижняя плотность Банаха).
Теорема Семереди и гипотеза Эрдеша-Турана
Теорема Семереди, о которой идет речь, связана с плотностью Банаха и выросла из гипотезы Эрдеша и Турана, которая, в свою очередь, стало обобщением теоремы Ван дер Вардена. Чтобы сформулировать эти результаты, нам потребуется еще одно математическое понятие - арифметические прогрессии. Арифметической прогрессией называется последовательность чисел, в которых любые два соседних отличаются на одно и то же число. В школе для таких прогрессий получают формулы общего члена и даже формулы суммы, что говорит в пользу заявления о простоте данного объекта.
Теорема Ван дер Вардена говорит, что для любого натурального числа k при произвольном разбиении всех натуральных чисел на конечное число подмножеств, в одном из них найдется арифметическая прогрессия длины k. Факт этот, несмотря на довольно простую формулировку, оказал огромное влияние на комбинаторику и эргодическую теорию (раздел теории динамических систем, описывающий свойства в некотором смысле хороших систем) - в свое время легендарный советский математик Александр Хинчин даже назвал эту теорему "жемчужиной теории чисел".
В 1936 году Пол Эрдеш и Пол Туран сформулировали гипотезу: для любой последовательности натуральных чисел с ненулевой верхней плотностью Банаха в ней найдется подпоследовательность, которая будет представлять собой арифметическую прогрессию произвольной длины. Как видно из формулировки, Эрдеш и Туран сильно усовершенствовали теорему Ван дер Вардена, рассмотрев вместо подмножеств, на которые разбиваются натуральные числа, подмножества с ненулевой верхней плотностью. При этом их теорема, по сути, указывает на то, какое из подмножеств в разбиении в классической теореме брать - то, которое поплотнее.
В 1956 году Клаус Рот доказал гипотезу для случая прогрессий длины три. В 1969 году, во время подготовки к защите диссертации сам Семереди доказал гипотезу для случая последовательностей длины четыре. Спустя шесть лет он, наконец, доказал теорему в общем виде. Надо сказать, что это сразу же принесло Эндре пользу - он заработал 1000 долларов, которые экстравагантный Пол Эрдеш обещал тому, кто докажет его с Тураном гипотезу (Эрдеш, кстати, часто объявлял денежные призы за открытые вопросы, считая это неплохой мотивацией для молодых математиков). Примечательно, что в 1977 году появилось еще одно доказательство теоремы Семереди, которое использовало совсем иной подход - методы эргодической теории. Это, в некотором смысле, подтвердило фундаментальность утверждения теоремы.
Стоит добавить, что при доказательстве этой теоремы Семереди придумал замечательную лемму о регулярности. Она говорит, что граф, в котором количество ребер связано с количеством вершин определенным соотношением, можно разбить на куски, которые между собой будут связаны в некотором смысле почти случайно. Надо сказать, что эта лемма оказалась чуть ли не популярнее самой теоремы и позже применялась в огромном количестве разных теорий.
Вместо заключения
На этом, конечно, карьера Семереди не закончилась. Он доказал множество замечательных результатов, многие из которых формулируются проще его главной теоремы. Сейчас он постоянный научный сотрудник Математического института Альфреда Реньи Венгерской академии наук (в 2010 году в честь 70-летия математика этот институт даже проводил большую научную конференцию, которая, по большому счету, выросла из результатов венгерского ученого). Кроме того, он занимает должность профессора информатики в Ратгерском университете в Нью-Джерси.