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