Введение

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

История

Теорема Ван дер Вэрдена, предшественница теоремы Сземереди, была доказана в 1927 году. Случаи k = 1 и k = 2 теоремы Сземереди тривиальны. Случай k = 3, известный как теорема Ротта, был установлен в 1953 году Клаусом Роттом путем адаптации метода кругов Харди — Литтлвуда. Эндре Сземереди доказал случай k = 4 с помощью комбинаторики. Используя подход, аналогичный примененному им для случая k = 3, Рот в 1972 году представил второе доказательство этого результата. Общий случай был решен в 1975 году также Сземереди, который разработал остроумное и сложное расширение своего предыдущего комбинаторного аргумента для k = 4 (Эрдёш назвал его «шедевром комбинаторного мышления»). В настоящее время известно несколько других доказательств, наиболее значимыми из которых являются доказательства, полученные Хиллелем Фурстенбергом в 1977 году с использованием эргодической теории, и Тимоти Говерсом в 2001 году, применившим как анализ Фурье, так и комбинаторику. Теренс Тао назвал различные доказательства теоремы Сземереди «камнем Розетты», позволяющим установить связь между различными областями математики.

Расширения и обобщения

Многомерное обобщение теоремы Шемереди было впервые доказано Хиллелем Фурстенбергом и Ицхаком Катзнелсоном с использованием эргодической теории. Тимоти Говерс, Войтех Рёдль и Йозеф Скокан совместно с Бренданом Нагле, Рёдлем и Матиасом Шахтом, а также Теренс Тао предоставили комбинаторные доказательства. Александр Лейбман и Виталий Бергельсон обобщили теорему Шемереди на полиномиальные прогрессии: если – множество с положительной верхней плотностью, а – полиномы, принимающие целые значения, такие что , то существует бесконечно много таких, что для всех . Результат Лейбмана и Бергельсона также справедлив в многомерном случае. Конечночная версия теоремы Шемереди может быть обобщена на конечные аддитивные группы, включая векторные пространства над конечными полями. Аналог для конечного поля может служить моделью для понимания теоремы в натуральных числах. Задача получения оценок в случае k=3 теоремы Шемереди в векторном пространстве известна как задача о множестве шапок. Теорема Грина — Тао утверждает, что простые числа содержат арифметические прогрессии произвольной длины. Она не вытекает из теоремы Шемереди, поскольку плотность простых чисел в натуральных числах равна 0. В качестве части своего доказательства Бен Грин и Тао ввели "относительную" теорему Шемереди, которая применяется к подмножествам целых чисел (включая подмножества с плотностью 0), удовлетворяющим определенным условиям псевдослучайности. Более общая относительная теорема Шемереди была впоследствии сформулирована Дэвидом Конлоном, Джейкобом Фоксом и Юфэй Чжао. Гипотеза Эрдеша об арифметических прогрессиях подразумевает как теорему Шемереди, так и теорему Грина — Тао.