Теорема Семередиса - Википедия - Szemerédis theorem

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

Заявление

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

.

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

Часто используемый эквивалентный финитарный вариант теоремы утверждает, что для любого положительного целого числа k и реальное число , существует натуральное число

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

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

.

То есть, р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). Наиболее известные общие оценки:

куда . Нижняя граница принадлежит О'Брайанту.[11] опираясь на работу Беренд,[12] Ранкин,[13] и Элькин.[14][15] Верхняя граница принадлежит Гауэрсу.[9]

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

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

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

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

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

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

Александр Лейбман и Виталий Бергельсон[30] обобщил Семереди на полиномиальные прогрессии: Если - множество с положительной верхней плотностью и находятся целочисленные многочлены такой, что , то бесконечно много такой, что для всех . Результат Лейбмана и Бергельсона справедлив и в многомерной ситуации.

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

В Теорема Грина – Тао утверждает, что простые числа содержат произвольные длинные арифметические прогрессии. Это не следует из теоремы Семереди, потому что простые числа имеют плотность 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. Новая оценка для р4(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: Полилогарифмическая оценка для r4(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.

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

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