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

Теорема Семереди (ранее известная как гипотеза Эрдёша — Турана) — утверждение в теории чисел, согласно которому для любой плотности $\delta \in (0,1)$ и для любого $k \in \mathbb N$ имеется число $N(k, \delta)$ такое, что любое подмножество $A \subseteq \{ 1, \dots, N \}$ мощности $\delta N$ содержит арифметическую прогрессию длины $k$ для любого $N > N(k, \delta)$.

Играет важную роль в арифметической комбинаторике. Обобщение теоремы использовано при доказательстве теоремы Грина — Тао.

История

Утверждение было сформулировано в 1936 году Палом Эрдёшом и Палом Тураном, как гипотеза, обобщающая утверждение теоремы Ван дер Вардена.

Случаи $k=1,2$ тривиальны, случай $k = 3$ был доказан в 1953 году Клаусом Ротом путём адаптации кругового метода Харди — Литлвуда.

Случай $k = 4$ доказал в 1969 году Эндре Семереди используя комбинаторный метод, близкий к тому, какой был применён для доказательства случая $k = 3$. Рот дал второе доказательство этого же случая в 1972 году.

Общий случай для любого $k$ доказал в 1975 году также Семереди, использовав изобретательные и сложные комбинаторные аргументы. Основу его доказательства составляет так называемая лемма регулярности, которая является одним из важнейших инструментов исследования графов.

Позднее были найдены другие доказательства теоремы, среди них наиболее важные — это доказательство Фюрстенберга (нем. Hillel Fürstenberg) 1977 года, использующее эргодическую теорию, и доказательство Гауэрса 2001 года, использующее гармонический анализ и комбинаторику.

Оценки

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

$C^{\log(1/\delta)^{k-1}} \leq N(k,\delta) \leq 2^{2^{\delta^{-2^{2^{k+9}}}}}$ с $C > 1$.

Нижняя оценка получена Берендом (Felix A. Behrend) (для $k = 3$) и Рэнкином (Robert Alexander Rankin), а верхняя — Гауэрсом. Для случая $k = 3$ известна оценка лучше — Бурген доказал, что:

$N(3,\delta) \leq C^{\delta^{-2}\log(1/\delta)}$.

В 2010 году Сандерс доказал, что подмножество множества $\{ 1, 2, \dots , N \}$, не имеющее арифметической прогрессии длины 3, имеет размер $O\left(\frac{N (\log \log N)^5}{\log N}\right)$..

Дальнейшее чтение

• Tao Terence The ergodic and combinatorial approaches to Szemerédi's theorem // Additive Combinatorics. — American Mathematical Society, 2007. — Vol. 43. — P. 145–193. — ISBN 978-0-8218-4351-2

Ссылки

• PlanetMath source for initial version of this page
• Announcement by Ben Green and Terence Tao — the preprint is available at math.NT/0404188
• Discussion of Szemerédi’s theorem (part 1 of 5)
• Ben Green and Terence Tao: Szemerédi’s theorem on Scholarpedia
• Weisstein, Eric W. SzemeredisTheorem (англ.) на сайте Wolfram MathWorld.
• Шкредов И. Д., Теорема Семереди и задачи об арифметических прогрессиях, УСПЕХИ МАТЕМАТИЧЕСКИХ НАУК, 2006 г. ноябрь — декабрь т. 61, вып. 6 (372), УДК 511.218+511.336