WikiSort.ru - Не сортированное

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

Является классическим примером теоремы аддитивной комбинаторике. Некоторые приёмы её доказательства были использованы при доказательстве теоремы Грина — Тао^[2].

История

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

Случаи ${\displaystyle k=1,2}$ тривиальны, случай ${\displaystyle k=3}$ (известен также как теорема Рота) был доказан в 1953 году Клаусом Ротом^[4] путём адаптации кругового метода Харди — Литлвуда.

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

Общий случай для любого ${\displaystyle k}$ доказал в 1975 году также Семереди^[7], использовав изобретательные и сложные комбинаторные аргументы. Основу его доказательства составляет так называемая лемма регулярности, описывающая устройство произвольных графов с точки зрения псевдослучайности.

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

Оценки

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

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

Нижняя оценка получена Берендом (Felix A. Behrend)^[10] (для ${\displaystyle k=3}$ ) и Рэнкином (Robert Alexander Rankin)^[11], а верхняя — Гауэрсом^[9]. Для случая ${\displaystyle k=3}$ известна оценка лучше — Бургейн^[12] доказал, что:

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

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

См. также

• Теорема об уголках
• Теорема Рота

Примечания

Литература

• Руэ, Хуанхо. Искусство подсчёта. Комбинаторика и перечисление. — М.: Де Агостини, 2014. — С. 123—132. — 144 с. — (Мир математики: в 45 томах, том 34). — ISBN 978-5-9774-0729-8.
• 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

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Проверить достоверность указанной в статье информации.