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

Теорема Семереди (ранее известная как гипотезаЭрдёша — Турана) — утверждение в теории чисел, согласно которомудля любой плотности δ(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)..