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

Почему эта теорема — отдельный комбинаторный факт — заслужила самую престижную математическую премию? Теорема Семереди — это пример утверждения, которое повлияло сразу на несколько математических областей. Более того, из теоремы Семереди возникло и новое направление — комбинаторная эргодическая теория. Эта математическая область, смесь комбинаторики и эргодической теории, была создана Фюрстенбергом в 70-е годы вскоре после публикации теоремы Семереди. Результат Семереди также связан и с теорией графов. Один частный инструмент доказательства Семереди, так называемая лемма регулярности Семереди, является сейчас основным инструментом исследования в теории плотных графов. С теоремой Семереди связана и теория чисел, например, потрясающий результат Грина — Тао, который утверждает, что простые числа содержат прогрессии любой длины. Теорема Семереди также связана и с гармоническим анализом, и с другими науками. Аналитическое доказательство теоремы Семереди было получено в 1998 году Гауэрсом, за что ему присудили Филдсовскую премию.
Прежде чем сформулировать теорему Семереди, мы начнем с некоторого более простого вопроса, а именно с теоремы, доказанной ван дер Варденом в 1927 году. Предположим, что у нас имеется ряд натуральных чисел, который раскрашен в два цвета: черный и белый. Таким образом, каждому числу приписан либо белый, либо черный цвет. В натуральных числах есть арифметические прогрессии — последовательности чисел, которые находятся на одинаковом расстоянии (например, 5-10-15, 1-2-3-4-5). Ясно, что мы можем найти бесконечно много таких прогрессий. Усложним вопрос: верно ли, что если натуральные числа раскрашены в два цвета, то всегда можно утверждать, что можно обнаружить прогрессию, состоящую сплошь из чисел одного цвета, то есть либо белую, либо черную? Еще раз: верно ли, что, как бы мы ни раскрашивали натуральные числа в два цвета, всегда можно найти некоторые числа, находящиеся на одинаковом расстоянии, причем имеющие один и тот же цвет? Положительный ответ на этот вопрос и составляет предмет теоремы ван дер Вардена. Более того, оказывается, что как бы мы ни раскрашивали натуральные числа — в 2, или в 10, или 100 цветов, — все равно можно найти прогрессию произвольной длины, состоящую из элементов одного цвета.
Читать дальше: http://postnauka.ru/faq/38273