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

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

Теорема Семереди (ранее известная как гипотеза Эрдёша — Турана[1]) — утверждение комбинаторной теории чисел о наличии длинных арифметических прогрессий в плотных множествах.

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

Формулировка[править | править код]

Изначальная формулировка теоремы содержала только условие на плотность множества в целом.

В любом бесконечном множестве положительной асимптотической плотности существует прогрессия любой длины .[3]

Существует эквивалентный приведённому выше[4] конечный вариант.

Для любого и достаточно больших любое множество размера содержит арифметическую прогрессию длины .

Конечный вариант важен в связи с возможностью формулировки количественных результатов о связи и . Он показывает, что в первом (бесконечном) варианте границей, за которой наличие прогрессий становится неизбежным, является не само по себе значение плотности, а некоторый закон распределения. Точное описание этой границы по состоянию на 2019 год неизвестно.

Конечный вариант теоремы останется эквивалентным если рассматривать и, соответственно, прогрессии в кольце вычетов по модулю . Такой подход открывает путь к доказательству с помощью тригонометрических сумм.

При или утверждение теоремы тривиально. Частный случай называется теоремой Рота. Его доказательство намного проще, чем для общего случая, и в литературе часто излагается отдельно. Кроме того, для теоремы рота известны намного лучшие по сравнению с общими оценки критических значений , в том числе для обобщений на различные группы.

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

Впервые утверждение теоремы было сформулировано в качестве гипотезы Эрдёшом и Тураном[5] в 1936 году.

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

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

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

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

Оценки[править | править код]

Говоря о количественных оценках для теоремы Семереди, обычно имеют в виду размер наибольшего подмножества интервала [12], не содержащего прогрессий заданной длины:

Таким образом, для вывода верхних оценок на нужны общие доказательства, а для доказательства нижних (то есть опровержения соответствующих верхних) достаточно предъявить конструкцию одного контрпримера.

Верхние оценки[править | править код]

Первое общее доказательство теоремы Семереди из-за использования леммы регулярности давало очень плохие оценки на зависимость , выражаемые через башни из экспонент.

Количественные оценки, сходные с соответствующими оценками для теоремы Рота, получил Гауэрс в 2001 году[11]:

, где

Для случая существуют намного лучшие оценки, полученные специфичными для этого случая методами.[13]

Нижние оценки[править | править код]

В случае наибольшей (на 2019 год) конструкцией множества без прогрессий является конструкция Беренда. Она даёт множества размера .

Ранкин в 1961 году обобщил эту конструкцию на произвольные , построив множество размера без прогрессий длины .[14]

Связь с другими теоремами[править | править код]

Теорема Семереди является прямым обобщением теоремы ван дер Вардена, поскольку при разделении натуральных чисел на конечное число классов хотя бы один из них будет иметь положительную плотность.

Из достаточно хороших верхних оценок на критические значения плотности в теореме Семереди может следовать гипотеза Эрдёша об арифметических прогрессиях.[15]

См. также[править | править код]

Литература[править | править код]

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

  1. Существует также другая гипотеза, названная именами этих учёных — гипотеза Эрдёша — Турана на аддитивных базисах
  2. Шкредов, 2006, с. 159-165.
  3. Из теоремы не следует существование в бесконечных арифметических прогрессий, и такое утверждение действительно было бы неверно. Например, контрпримером является множество чисел, содержащих единицу в первом разряде десятичной записи.
  4. Шкредов, 2006, с. 113.
  5. 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> .
  6. Roth, Klaus Friedrich (1953), On certain sets of integers, I, Journal of the London Mathematical Society Т. 28: 104–109, Zbl 0050.04002, MR: 0051853, DOI 10.1112/jlms/s1-28.1.104 .
  7. 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, MR: 0245555, DOI 10.1007/BF01894569 
  8. Roth, Klaus Friedrich (1972), Irregularities of sequences relative to arithmetic progressions, IV, Periodica Math. Hungar. Т. 2: 301–326, MR: 0369311, DOI 10.1007/BF02018670 .
  9. Szemerédi, Endre (1975), On sets of integers containing no k elements in arithmetic progression, Acta Arithmetica Т. 27: 199–245, Zbl 0303.10056, MR: 0369312, <http://matwbn.icm.edu.pl/ksiazki/aa/aa27/aa27132.pdf> .
  10. Furstenberg, Hillel (1977), Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions, J. D’Analyse Math. Т. 31: 204–256, MR: 0498471, DOI 10.1007/BF02813304 .
  11. 1 2 Gowers, Timothy (2001), A new proof of Szemerédi's theorem, Geom. Funct. Anal. Т. 11 (3): 465–588, MR: 1844079, doi:10.1007/s00039-001-0332-9, <http://www.dpmms.cam.ac.uk/~wtg10/sz898.dvi> .
  12. Или циклической группы , что совпадает с точностью до константы.
  13. A quantitative improvement for Roth's theorem on arithmetic progressions, Journal of the London Mathematical Society Т. 93 (3): 643-663, 2016 .
  14. 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, MR: 0142526 .
  15. Шкредов, 2006, с. 139-140.

Ссылки[править | править код]