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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

История[править | править вики-текст]

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

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

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

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

Позднее были найдены другие доказательства теоремы, среди них наиболее важные — это доказательство Фюрстенберга (нем. Hillel Fürstenberg)[7] 1977 года, использующее эргодическую теорию, и доказательство Гауэрса[8] 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)[9] (для k = 3) и Рэнкином (Robert Alexander Rankin)[10], а верхняя — Гауэрсом[8]. Для случая k = 3 известна оценка лучше — Бургейн[11] доказал, что:

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).[12].

Примечания[править | править вики-текст]

  1. Существует также другая гипотеза, названная именами этих учёных — гипотеза Эрдёша — Турана на аддитивных базисах
  2. Erdős, Paul & Turán, Paul (1936), "On some sequences of integers", Journal of the London Mathematical Society Т. 11 (4): 261–264, doi:10.1112/jlms/s1-11.4.261, <http://www.renyi.hu/~p_erdos/1936-05.pdf> .
  3. Roth, Klaus Friedrich (1953), "On certain sets of integers, I", Journal of the London Mathematical Society Т. 28: 104–109, Zbl 0050.04002, MR0051853, DOI 10.1112/jlms/s1-28.1.104 .
  4. Szemerédi, Endre (1969), "On sets of integers containing no four elements in arithmetic progression", Acta Math. Acad. Sci. Hung. Т. 20: 89–104, Zbl 0175.04301, MR0245555, DOI 10.1007/BF01894569 
  5. Roth, Klaus Friedrich (1972), "Irregularities of sequences relative to arithmetic progressions, IV", Periodica Math. Hungar. Т. 2: 301–326, MR0369311, DOI 10.1007/BF02018670 .
  6. Szemerédi, Endre (1975), "On sets of integers containing no k elements in arithmetic progression", Acta Arithmetica Т. 27: 199–245, Zbl 0303.10056, MR0369312, <http://matwbn.icm.edu.pl/ksiazki/aa/aa27/aa27132.pdf> .
  7. Furstenberg, Hillel (1977), "Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions", J. D’Analyse Math. Т. 31: 204–256, MR0498471, DOI 10.1007/BF02813304 .
  8. 1 2 Gowers, Timothy (2001), "A new proof of Szemerédi's theorem", Geom. Funct. Anal. Т. 11 (3): 465–588, MR1844079, doi:10.1007/s00039-001-0332-9, <http://www.dpmms.cam.ac.uk/~wtg10/sz898.dvi> .
  9. Behrend, Felix A. (1946), "On the sets of integers which contain no three in arithmetic progression", Proceedings of the National Academy of Sciences Т. 23 (12): 331–332, Zbl 0060.10302, DOI 10.1073/pnas.32.12.331 .
  10. Rankin, Robert A. (1962), "Sets of integers containing not more than a given number of terms in arithmetical progression", Proc. Roy. Soc. Edinburgh Sect. A Т. 65: 332–344, Zbl 0104.03705, MR0142526 .
  11. Bourgain, Jean (1999), "On triples in arithmetic progression", Geom. Func. Anal. Т. 9 (5): 968–984, MR1726234, DOI 10.1007/s000390050105 
  12. arXiv:1011.0104, [1], также: [2]

Литература[править | править вики-текст]

  • Руэ, Хуанхо. Искусство подсчёта. Комбинаторика и перечисление. — М.: Де Агостини, 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.

Ссылки[править | править вики-текст]