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

Теорема Семереди (ранее известная как гипотеза Эрдёша — Турана) — утверждение в теории чисел, согласно которому для любой плотности δ(0,1) и для любого kN имеется число N(k,δ) такое, что любое подмножество A{1,,N} мощности δN содержит арифметическую прогрессию длины k для любого N>N(k,δ).
 Играет важную роль в арифметической комбинаторике. Обобщение теоремы использовано при доказательстве теоремы Грина — Тао.

История


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

Оценки


 Лучшие оценки N(k,δ):

Clog(1/δ)k1N(k,δ)22δ22k+9 с C>1.
  Нижняя оценка получена Берендом (Felix A. Behrend) (для k=3) и Рэнкином (Robert Alexander Rankin), а верхняя — Гауэрсом. Для случая k=3 известна оценка лучше — Бургейн доказал, что:

N(3,δ)Cδ2log(1/δ).
  В 2010 году Сандерс доказал, что подмножество множества {1,2,,N}, не имеющее арифметической прогрессии длины 3, имеет размер O(N(loglogN)5logN)..