Теорема Семередиса - Szemerédis theorem

В арифметическая комбинаторика, Теорема Семереди это результат относительно арифметические прогрессии в подмножествах целых чисел. В 1936 г. Erds и Туран предполагаемый^[1] что каждый набор целых чисел А с положительным естественная плотность содержит k-срок арифметическая прогрессия для каждого k. Эндре Семереди доказал гипотезу в 1975 году.

Заявление

Подмножество А из натуральные числа имеет положительную верхнюю плотность, если

${\displaystyle \limsup _{n\to \infty }{\frac {|A\cap \{1,2,3,\dotsc ,n\}|}{n}}>0}$.

Теорема Семереди утверждает, что подмножество натуральных чисел с положительной верхней плотностью содержит бесконечно много арифметических прогрессий длины k для всех положительных целых чисел k.

Часто используемый эквивалентный финитарный вариант теоремы утверждает, что для любого положительного целого числа k и реальное число ${\displaystyle \delta \in (0,1]}$, существует натуральное число

${\displaystyle N=N(k,\delta )}$

такое, что каждое подмножество {1, 2, ..., N} размером не менее δN содержит арифметическую прогрессию длины k.

В другой формулировке используется функция р_k(N), размер наибольшего подмножества {1, 2, ..., N} без арифметической прогрессии длины k. Теорема Семереди эквивалентна асимптотической оценке

${\displaystyle r_{k}(N)=o(N)}$.

То есть, р_k(N) растет менее чем линейно с N.

История

Теорема Ван дер Вардена, предшественник теоремы Семереди, был доказан в 1927 году.

Случаи k = 1 и k = 2 теоремы Семереди тривиальны. Дело k = 3, известный как Теорема Рота, была основана в 1953 г. Клаус Рот^[2] через адаптацию Метод круга Харди – Литтлвуда. Эндре Семереди^[3] доказал правоту k = 4 через комбинаторику. Используя подход, аналогичный тому, который он использовал в случае k = 3, Рот^[4] дал второе доказательство этого в 1972 г.

Общее дело было урегулировано в 1975 году, также Семереди,^[5] который разработал остроумное и сложное расширение своего предыдущего комбинаторного аргумента в пользу k = 4 (названный "шедевром комбинаторного мышления" Erds^[6]). Теперь известно несколько других доказательств, наиболее важные из которых принадлежат Гилель Фюрстенберг^[7][8] в 1977 г., используя эргодическая теория, и по Тимоти Гауэрс^[9] в 2001 г., используя оба Анализ Фурье и комбинаторика. Теренс Тао назвал различные доказательства теоремы Семереди "Розеттский камень «для соединения разрозненных областей математики.^[10]

Количественные оценки

Это открытая проблема - определить точную скорость роста р_k(N). Наиболее известные общие оценки:

${\displaystyle CN\exp \left(-n2^{(n-1)/2}{\sqrt[{n}]{\log N}}+{\frac {1}{2n}}\log \log N\right)\leq r_{k}(N)\leq {\frac {N}{(\log \log N)^{2^{-2^{k+9}}}}},}$

куда ${\displaystyle n=\lceil \log k\rceil }$. Нижняя граница принадлежит О'Брайанту.^[11] опираясь на работу Беренд,^[12] Ранкин,^[13] и Элькин.^[14][15] Верхняя граница принадлежит Гауэрсу.^[9]

Для малых k, существуют более жесткие границы, чем в общем случае. Когда k = 3, Бургейн,^[16][17] Хит-Браун,^[18] Семереди,^[19] и Сандерс^[20] предоставлены все более низкие верхние границы. Текущие наилучшие оценки:

${\displaystyle N2^{-{\sqrt {8\log N}}}\leq r_{3}(N)\leq C{\frac {(\log \log N)^{4}}{\log N}}N}$

из-за О'Брайанта^[11] и Блум^[21] соответственно.

За k = 4, зеленый и дао^[22][23] доказал, что

${\displaystyle r_{4}(N)\leq C{\frac {N}{(\log N)^{c}}}}$

для некоторых c > 0.

Расширения и обобщения

Многомерное обобщение теоремы Семереди было впервые доказано Гилель Фюрстенберг и Ицхак Кацнельсон используя эргодическую теорию.^[24] Тимоти Гауэрс,^[25] Войтех Рёдль и Юзеф Скокан^[26][27] с Бренданом Нэглом, Рёдлем и Матиас Шахт,^[28] и Теренс Тао^[29] предоставил комбинаторные доказательства.

Александр Лейбман и Виталий Бергельсон^[30] обобщил Семереди на полиномиальные прогрессии: Если ${\displaystyle A\subset \mathbb {N} }$ - множество с положительной верхней плотностью и ${\displaystyle p_{1}(n),p_{2}(n),\dotsc ,p_{k}(n)}$ находятся целочисленные многочлены такой, что ${\displaystyle p_{i}(0)=0}$, то бесконечно много ${\displaystyle u,n\in \mathbb {Z} }$ такой, что ${\displaystyle u+p_{i}(n)\in A}$ для всех ${\displaystyle 1\leq i\leq k}$. Результат Лейбмана и Бергельсона справедлив и в многомерной ситуации.

Конечная версия теоремы Семереди может быть обобщена на конечные аддитивные группы включая векторные пространства над конечные поля.^[31] Аналог конечного поля можно использовать в качестве модели для понимания теоремы в натуральных числах.^[32] Проблема получения оценок в случае k = 3 теоремы Семереди в векторном пространстве ${\displaystyle \mathbb {F} _{3}^{n}}$ известен как набор крышек проблема.

В Теорема Грина – Тао утверждает, что простые числа содержат произвольные длинные арифметические прогрессии. Это не следует из теоремы Семереди, потому что простые числа имеют плотность 0 в натуральных числах. В качестве доказательства Бен Грин и Тао ввел «относительную» теорему Семереди, которая применяется к подмножествам целых чисел (даже с нулевой плотностью), удовлетворяющим определенным условиям псевдослучайности. Более общая относительная теорема Семереди была с тех пор дана Дэвид Конлон, Джейкоб Фокс, и Юфэй Чжао.^[33][34]

В Гипотеза Эрдеша об арифметических прогрессиях влечет как теорему Семереди, так и теорему Грина – Тао.

Смотрите также

• Задачи, связанные с арифметическими прогрессиями
• Эргодическая теория Рамсея
• Арифметическая комбинаторика
• Лемма Семереди о регулярности

Примечания

1. Эрдеш, Пол; Туран, Пол (1936). «О некоторых последовательностях целых чисел» (PDF). Журнал Лондонского математического общества. 11 (4): 261–264. Дои:10.1112 / jlms / s1-11.4.261. МИСТЕР  1574918.
2. Рот, Клаус Фридрих (1953). «О некоторых наборах целых чисел». Журнал Лондонского математического общества. 28 (1): 104–109. Дои:10.1112 / jlms / s1-28.1.104. МИСТЕР  0051853. Zbl  0050.04002.
3. Семереди, Эндре (1969). «О наборах целых чисел, не содержащих четырех элементов в арифметической прогрессии». Acta Math. Акад. Sci. Подвешенный. 20 (1–2): 89–104. Дои:10.1007 / BF01894569. МИСТЕР  0245555. Zbl  0175.04301.
4. Рот, Клаус Фридрих (1972). «Неравномерность последовательностей относительно арифметических прогрессий, IV». Periodica Math. Hungar. 2 (1–4): 301–326. Дои:10.1007 / BF02018670. МИСТЕР  0369311.
5. Семереди, Эндре (1975). "На наборах целых чисел, не содержащих k элементы в арифметической прогрессии » (PDF). Acta Arithmetica. 27: 199–245. Дои:10.4064 / aa-27-1-199-245. МИСТЕР  0369312. Zbl  0303.10056.
6. Эрдеш, Пол (2013). «Некоторые из моих любимых задач и результатов». В Graham, Ronald L .; Нешетржил, Ярослав; Батлер, Стив (ред.). Математика Пола Эрдёша I (Второе изд.). Нью-Йорк: Спрингер. С. 51–70. Дои:10.1007/978-1-4614-7258-2_3. ISBN  978-1-4614-7257-5. МИСТЕР  1425174.
7. Фюрстенберг, Гилель (1977). "Эргодическое поведение диагональных мер и теорема Семереди об арифметических прогрессиях". J. d'Analyse Math. 31: 204–256. Дои:10.1007 / BF02813304. МИСТЕР  0498471..
8. Фюрстенберг, Гиллель; Кацнельсон, Ицхак; Орнштейн, Дональд Сэмюэл (1982). «Эргодическое теоретическое доказательство теоремы Семереди». Бык. Амер. Математика. Soc. 7 (3): 527–552. Дои:10.1090 / S0273-0979-1982-15052-2. МИСТЕР  0670131.
9. Гауэрс, Тимоти (2001). «Новое доказательство теоремы Семереди». Геом. Функц. Анальный. 11 (3): 465–588. Дои:10.1007 / s00039-001-0332-9. МИСТЕР  1844079.
10. Тао, Теренс (2007). «Дихотомия между структурой и случайностью, арифметическими прогрессиями и простыми числами». В Санс-Соле, Марта; Сория, Хавьер; Варона, Хуан Луис; Вердера, Жанна (ред.). Труды Международного конгресса математиков Мадрид, 22–30 августа 2006 г.. Международный конгресс математиков. 1. Цюрих: Европейское математическое общество. С. 581–608. arXiv:математика / 0512114. Дои:10.4171/022-1/22. ISBN  978-3-03719-022-7. МИСТЕР  2334204.
11. О'Брайант, Кевин (2011). «Наборы целых чисел, не содержащие длинных арифметических прогрессий». Электронный журнал комбинаторики. 18 (1). Дои:10.37236/546. МИСТЕР  2788676.
12. Беренд, Феликс А. (1946). «О наборах целых чисел, не содержащих трех членов в арифметической прогрессии». Труды Национальной академии наук. 32 (12): 331–332. Bibcode:1946ПНАС ... 32..331Б. Дои:10.1073 / pnas.32.12.331. МИСТЕР  0018694. ЧВК  1078964. PMID  16578230. Zbl  0060.10302.
13. Ранкин, Роберт А. (1962). «Наборы целых чисел, содержащие не более заданного числа членов в арифметической прогрессии». Proc. Рой. Soc. Эдинбург, секта. А. 65: 332–344. МИСТЕР  0142526. Zbl  0104.03705.
14. Елкин, Михаил (2011). «Улучшенная конструкция наборов без прогрессирования». Израильский математический журнал. 184 (1): 93–128. arXiv:0801.4310. Дои:10.1007 / s11856-011-0061-1. МИСТЕР  2823971.
15. Грин, Бен; Волк, Юля (2010). «Заметка об усовершенствовании Элькиным конструкции Беренда». В Чудновском, Давид; Чудновский, Григорий (ред.). Аддитивная теория чисел. Аддитивная теория чисел. Festschrift в честь шестидесятилетия Мелвина Б. Натансона. Нью-Йорк: Спрингер. С. 141–144. arXiv:0810.0732. Дои:10.1007/978-0-387-68361-4_9. ISBN  978-0-387-37029-3. МИСТЕР  2744752.
16. Бургейн, Жан (1999). «По троек в арифметической прогрессии». Геом. Функц. Анальный. 9 (5): 968–984. Дои:10.1007 / с000390050105. МИСТЕР  1726234.
17. Бургейн, Жан (2008). "Повторение теоремы Рота о прогрессиях". J. Anal. Математика. 104 (1): 155–192. Дои:10.1007 / s11854-008-0020-х. МИСТЕР  2403433.
18. Хит-Браун, Роджер (1987). «Целочисленные множества, не содержащие арифметических прогрессий». Журнал Лондонского математического общества. 35 (3): 385–394. Дои:10.1112 / jlms / s2-35.3.385. МИСТЕР  0889362.
19. Семереди, Эндре (1990). «Целочисленные множества, не содержащие арифметических прогрессий». Acta Math. Hungar. 56 (1–2): 155–158. Дои:10.1007 / BF01903717. МИСТЕР  1100788.
20. Сандерс, Том (2011). «О теореме Рота о прогрессиях». Анналы математики. 174 (1): 619–636. arXiv:1011.0104. Дои:10.4007 / летопись.2011.174.1.20. МИСТЕР  2811612.
21. Блум, Томас Ф. (2016). «Количественное улучшение теоремы Рота об арифметических прогрессиях». Журнал Лондонского математического общества. Вторая серия. 93 (3): 643–663. arXiv:1405.5800. Дои:10.1112 / jlms / jdw010. МИСТЕР  3509957.
22. Грин, Бен; Тао, Теренс (2009). «Новые оценки теоремы Семереди. II. Новая оценка для р₄(N) ". In Chen, William W. L .; Гауэрс, Тимоти; Хальберштам, Хайни; Шмидт, Вольфганг; Воан, Роберт Чарльз (ред.). Новые оценки теоремы Семереди, II: Новая оценка для r_4 (N). Аналитическая теория чисел. Эссе в честь Клауса Рота к 80-летию со дня рождения. Кембридж: Издательство Кембриджского университета. С. 180–204. arXiv:математика / 0610604. Bibcode:2006математика ..... 10604G. ISBN  978-0-521-51538-2. МИСТЕР  2508645. Zbl  1158.11007.
23. Грин, Бен; Тао, Теренс (2017). "Новые оценки теоремы Семереди, III: Полилогарифмическая оценка для r₄(N) ". Математика. 63 (3): 944–1040. arXiv:1705.01703. Дои:10.1112 / S0025579317000316. МИСТЕР  3731312.
24. Фюрстенберг, Гилель; Кацнельсон, Ицхак (1978). «Эргодическая теорема Семереди для коммутирующих преобразований». Журнал д'анализа математика. 38 (1): 275–291. Дои:10.1007 / BF02790016. МИСТЕР  0531279.
25. Гауэрс, Тимоти (2007). «Регулярность гиперграфа и многомерная теорема Семереди». Анналы математики. 166 (3): 897–946. arXiv:0710.3032. Дои:10.4007 / annals.2007.166.897. МИСТЕР  2373376.
26. Рёдль, Войтех; Скокан, Йозеф (2004). «Лемма о регулярности k-равномерных гиперграфов». Алгоритмы случайных структур. 25 (1): 1–42. Дои:10.1002 / rsa.20017. МИСТЕР  2069663.
27. Рёдль, Войтех; Скокан, Йозеф (2006). «Приложения леммы о регулярности для равномерных гиперграфов» (PDF). Алгоритмы случайных структур. 28 (2): 180–194. Дои:10.1002 / rsa.20108. МИСТЕР  2198496.
28. Нэгл, Брендан; Рёдль, Войтех; Шахт, Матиас (2006). «Считающая лемма для регулярных k-равномерных гиперграфов». Алгоритмы случайных структур. 28 (2): 113–179. Дои:10.1002 / rsa.20117. МИСТЕР  2198495.
29. Тао, Теренс (2006). «Вариант леммы об удалении гиперграфа». Журнал комбинаторной теории, серия А. 113 (7): 1257–1280. arXiv:математика / 0503572. Дои:10.1016 / j.jcta.2005.11.006. МИСТЕР  2259060.
30. Бергельсон, Виталий; Лейбман, Александр (1996). «Полиномиальные расширения теорем Ван дер Вардена и Семереди». Журнал Американского математического общества. 9 (3): 725–753. Дои:10.1090 / S0894-0347-96-00194-4. МИСТЕР  1325795.
31. Фюрстенберг, Гилель; Кацнельсон, Ицхак (1991). "Версия плотности теоремы Хейлса-Джеветта". Журнал д'анализа математика. 57 (1): 64–119. Дои:10.1007 / BF03041066. МИСТЕР  1191743.
32. Волк, Юлия (2015). «Модели конечного поля в арифметической комбинаторике - десять лет спустя». Конечные поля и их приложения. 32: 233–274. Дои:10.1016 / j.ffa.2014.11.003. МИСТЕР  3293412.
33. Конлон, Дэвид; Фокс, Джейкоб; Чжао, Юфэй (2015). «Относительная теорема Семереди». Геометрический и функциональный анализ. 25 (3): 733–762. arXiv:1305.5440. Дои:10.1007 / s00039-015-0324-9. МИСТЕР  3361771.
34. Чжао, Юфэй (2014). «Арифметическое переносное доказательство относительной теоремы Семереди». Математические труды Кембриджского философского общества. 156 (2): 255–261. arXiv:1307.4959. Bibcode:2014MPCPS.156..255Z. Дои:10.1017 / S0305004113000662. МИСТЕР  3177868.

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

• Тао, Теренс (2007). «Эргодический и комбинаторный подходы к теореме Семереди». В Гранвилле, Эндрю; Натансон, Мелвин Б .; Солимози, Йожеф (ред.). Аддитивная комбинаторика. CRM Proceedings & Lecture Notes. 43. Провиденс, Род-Айленд: Американское математическое общество. С. 145–193. arXiv:математика / 0604456. Bibcode:2006математика ...... 4456T. ISBN  978-0-8218-4351-2. МИСТЕР  2359471. Zbl  1159.11005.

внешняя ссылка

• Исходный код PlanetMath для начальной версии этой страницы
• Объявление Бена Грина и Теренса Тао - препринт доступен по адресу math.NT / 0404188
• Обсуждение теоремы Семереди (часть 1 из 5)
• Бен Грин и Теренс Тао: Теорема Семереди на Scholarpedia
• Вайсштейн, Эрик В. "Семередис Теорем". MathWorld.
• Грайм, Джеймс; Ходж, Дэвид (2012). «6,000,000: Эндре Семереди получает премию Абеля». Numberphile. Брэди Харан.