Эндре Семереди: в любом хаосе есть порядок

Проучившись шесть месяцев в медицинском институте, Эндре Семереди (Endre Szemerédi) решил, что не может доверить себе скальпель — как он позже сказал, он усомнился в своей способности «выполнять работу, несущую такую ответственность» — и ушел. Некоторое время он искал себя, затем поступил на математический факультет и по канцелярской ошибке был распределен к научному руководителю, которого никогда не просил. Эта ошибка в документах отправила его в Москву к Израилю Гельфанду (Israel Gelfand), одному из величайших математиков XX века, а не к Александру Гельфонду (Alexander Gelfond), к которому Семереди на самом деле хотел попасть. Это одна из самых удачных случайностей в данной области.

Из Будапешта в Москву по ошибке

Семереди родился 21 августа 1940 года в Будапеште. После короткой и неудачной попытки заняться медициной он получил степень бакалавра в Университете имени Лоранда Этвеша (Eötvös Loránd University) в Будапеште, а затем отправился в Московский государственный университет для работы над магистерской и докторской диссертациями. Там, под руководством Гельфанда — результат той самой канцелярской ошибки, — он начал карьеру в дискретной математике, которая в конечном итоге принесла ему редкое для комбинаторики признание, сопоставимое с медалью Филдса: Абелевскую премию (Abel Prize).

Теорема, носящая его имя

Главное достижение Семереди, объявленное в 1975 году, разрешило гипотезу, которую Пол Эрдёш (Paul Erdős) и Пал Туран (Pál Turán) выдвинули десятилетиями ранее и которая до этого момента оставалась недоказанной: любой набор натуральных чисел с положительной верхней плотностью — грубо говоря, любой набор, который не сходит на нет относительно всей числовой прямой — должен содержать арифметические прогрессии любой длины. Это утверждение о скрытом порядке: как бы нерегулярно или разреженно ни выглядел достаточно существенный набор целых чисел, внутри него неизбежно скрыты закономерные последовательности. Комитет Абелевской премии позже резюмировал дух его работы одной фразой: «в любом хаосе есть порядок».

Лемма о регулярности

Доказательство этой теоремы породило нечто еще более важное, чем сама теорема. В процессе работы Семереди представил то, что сейчас называется леммой Семереди о регулярности (Szemerédi regularity lemma), — структурный результат, показывающий, что каждый достаточно большой граф можно разбить на ограниченное число частей, которые в точном статистическом смысле ведут себя почти случайно по отношению друг к другу. Это звучит как техническая лемма, но она стала одним из центральных инструментов современной комбинаторики, лежащим в основе проверки свойств, теории пределов графов и значительной части экстремальной теории графов, развитой за последующие десятилетия. Лауреаты Филдсовской премии, включая Тимоти Гауэрса (Timothy Gowers) и Ласло Ловаса (László Lovász), посвящали целые лекции прослеживанию ее следствий — редкий случай, когда побочный продукт доказательства превосходит по влиянию свою исходную теорему.

Корпус именных результатов

Карьера Семереди привела к появлению необычайно большого количества результатов, которые теперь носят его имя наряду с именами соавторов: теорема Семереди — Троттера (Szemerédi–Trotter theorem) в геометрической теории инцидентности, ограничивающая количество пересечений точек и прямых на плоскости; теорема Хайнала — Семереди (Hajnal–Szemerédi theorem) о раскраске графов; теорема Эрдёша — Семереди (Erdős–Szemerédi theorem) о суммах и произведениях в конечных множествах, фундаментальный результат в области, которая стала называться арифметической комбинаторикой; и, совместно с Миклошем Аитай (Miklós Ajtai), теорема об углах (corners theorem). Вместе с Аитай и Яношем Комлошем (János Komlós) он установил влиятельные границы для чисел Рамсея (Ramsey numbers) и построил сортировочные сети оптимальной глубины — редкий выход из чистой математики в теоретическую информатику, что помогло обосновать его окончательное академическое пристанище на кафедре информатики. Вместе с Аитай, Вацлавом Хваталом (Václav Chvátal) и Монро Ньюборном (Monroe Newborn) он также доказал неравенство числа пересечений (crossing number inequality), фундаментальную границу в теории рисования графов. В более чем двухстах опубликованных статьях прослеживается последовательная линия: поиск жесткой, неизбежной структуры внутри объектов — множеств целых чисел, графов, конфигураций точек, — которые на поверхности кажутся беспорядочными.

Американская карьера, основанная на венгерском фундаменте

Семереди присоединился к Ратгерскому университету (Rutgers University) в 1986 году в качестве профессора информатики штата Нью-Джерси, эту должность он занимает до сих пор в качестве почетного профессора, при этом сохраняя постоянную связь с Математическим институтом имени Альфреда Реньи (Alfréd Rényi Institute of Mathematics) в Будапеште, который был институциональным центром венгерской математики с середины XX века. В промежутках он занимал приглашенные должности в Стэнфорде, Макгилле, Университете Южной Каролины и Чикагском университете, а также был членом Института перспективных исследований (Institute for Advanced Study) в Принстоне — карьера, охватывающая математическую миграцию времен холодной войны из Венгрии и советской сферы в американские исследовательские университеты.

Признание

Награды накапливались в течение пяти десятилетий: премия Альфреда Реньи в 1973 году и премия Джорджа Пойи (George Pólya Prize) в 1975 году, сразу после появления его теоремы; премия Лероя П. Стила (Leroy P. Steele Prize) и премия Рольфа Шока (Rolf Schock Prize) по математике, обе в 2008 году; избрание в Национальную академию наук США в 2010 году; и, наконец, в 2012 году — сама Абелевская премия, присужденная «за фундаментальный вклад в дискретную математику и теоретическую информатику, а также в знак признания глубокого и длительного влияния этих вкладов на аддитивную теорию чисел и эргодическую теорию» — формулировка, которая прямо связывает его работу с преобразованием областей, выходящих далеко за рамки узкого определения комбинаторики. Венгрия в 2020 году наградила его орденом Святого Иштвана (Order of Saint Stephen).

Почему Эндре называют гением

Аргументы в пользу гениальности Семереди настолько убедительны, насколько это возможно в математике: единственное доказательство единственной давней гипотезы породило инструмент — лемму о регулярности, — чье дальнейшее влияние на целую дисциплину, возможно, превышает влияние теоремы, для доказательства которой она была создана. Такое влияние второго порядка, когда метод переживает и перерастает свою первоначальную цель, является одним из самых четких индикаторов того, что разум работает на глубочайшем структурном уровне, а не просто решает задачу перед собой. Слова комитета Абелевской премии — поиск порядка внутри хаоса — не являются преувеличением; это справедливое описание того, что на самом деле делает лемма о регулярности, и тот факт, что Гауэрс и Ловас, сами будучи одними из самых титулованных фигур в дисциплине, строили важные лекции вокруг объяснения ее следствий другим математикам, является формой признания коллег, которую трудно подделать или раздуть.

Если здесь и есть оговорка, то она касается узкой специализации, а не преувеличения: слава Семереди подавляющим образом зиждется на результатах в дискретной математике и комбинаторике — областях, которые на протяжении большей части XX века частью математического истеблишмента считались менее престижными, чем анализ, геометрия или теория чисел в их классических формах. Присуждение Абелевской премии комбинаторику в то время само по себе читалось как неявный аргумент в пользу того, что эта область заслуживает признания, которое она долгое время не могла получить. Это не умаляет его работы; это означает, что ярлык «гений» здесь указывает на конкретную, техническую форму структурного понимания, а не на тот тип всеобщей известности, который присущ физикам или математикам, чьи результаты знамениты даже за пределами их области.

Наследие

Лемма о регулярности в настоящее время преподается как стандартный материал на курсах комбинаторики для аспирантов во всем мире и остается активным двигателем новых исследований, в том числе в областях — теоретическая информатика, аддитивная комбинаторика, теория пределов графов, — которые едва существовали, когда Семереди впервые записал ее в 1975 году. Оставаясь активным почетным ученым в возрасте за восемьдесят, он остается одним из самых наглядных примеров в современной математике того, как метод одного доказательства становится более значимым, чем теорема, для обоснования которой он был разработан.