Теорема Семереди

Какие математические гипотезы лежат в основе теоремы Семереди? Как она была доказана? И как теорема Семереди повлияла на дальнейшее развитие математической науки? Об этом рассказывает доктор физико-математических наук Илья Шкредов.

Почему теорема Семереди — красивый, глубокий, но все-таки отдельный комбинаторный факт — заслужил самую престижную математическую премию? Дело в том, что теорема Семереди — это замечательный пример утверждения, которое повлияло сразу на несколько математических областей. Более того, из теоремы Семереди возникла новая область — комбинаторная эргодическая теория. Это сделал вскоре после Семереди Фюрстенберг в 70-е годы. Теорема Семереди связана с теорией графов. Один частный инструмент доказательства Семереди, так называемая лемма регулярности Семереди, сейчас является основным инструментом в теории графов.

Предположим, что у нас есть множество бесконечное — популярный цвет, и я определю плотность этого множества. То есть возьму отрезок натурального ряда от 1 до N, посчитаю, сколько точек в множество попало, поделю на N и возьму верхний предел. Тогда гипотеза Эрдеша — Турана формулируется так: верно ли, что если плотность множества положительная, например этот цвет составляет 1% от всех натуральных чисел, то можно найти одноцветную прогрессию, состоящую только из точек этого множества? Это очень сложная задача, хотя частный пример прогрессии длины три был доказан в 1953 году Клаусом Ротом, замечательным английским математиком, филдсовским лауреатом. Филдсовскую премию он получил не за это, но случай прогрессии длины три особый, поскольку в этой ситуации можно применить известный классический подход Виноградова, а вот с прогрессией длины четыре начинаются проблемы. В 1969 году Эндре Семереди, используя сложные комбинаторные рассуждения, опубликовал доказательство, которое занимало примерно 50 страниц, и даже график того, из какого утверждения вытекает какое, представлял где-то полстраницы непонятного, закрученного текста.

Главное достижение Семереди, с моей точки зрения, состоит в том, что он предложил эту новую идеологию. До Семереди наука занималась либо случайными объектами, как, скажем, теория вероятности, либо структурированными объектами, не знаю, как геометрия, например, еще что-то. А вот Семереди сказал, что не нужно бояться: если у нас нет случайности, то это неплохо, это значит, что есть структура, но небольшая. Если у нас нет структуры, то это тоже неплохо, потому что тогда у нас есть случайность.