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

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

Теорема Семереди (ранее известная как гипотеза Эрдёша — Турана[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. arΧiv1011.0104, [1], также: [2]

Дальнейшее чтение[править | править вики-текст]

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