Арифметическая комбинаторика
В математике комбинаторика арифметическая является областью на пересечении теории чисел , комбинаторики , эргодической теории и гармонического анализа .
Область применения [ править ]
Арифметическая комбинаторика занимается комбинаторными оценками, связанными с арифметическими операциями (сложение, вычитание, умножение и деление). Аддитивная комбинаторика — это особый случай, когда задействованы только операции сложения и вычитания.
Бен Грин объясняет арифметическую комбинаторику в своем обзоре «Аддитивной комбинаторики» Тао и Ву . [1]
Важные результаты [ править ]
Теорема Семереди [ править ]
Теорема Семереди является результатом арифметической комбинаторики, касающейся арифметических прогрессий в подмножествах целых чисел. В 1936 году Эрдеш и Туран предположили , что [2] что каждый набор целых чисел A с положительной натуральной плотностью содержит k членов арифметической прогрессии для каждого k . Эта гипотеза, ставшая теоремой Семереди, обобщает утверждение теоремы Ван дер Вардена .
Теорема Грина – Тао ее расширения и
Теорема Грина -Тао , доказанная Беном Грином и Теренсом Тао в 2004 году: [3] утверждает, что последовательность простых чисел содержит сколь угодно длинные арифметические прогрессии . Другими словами, существуют арифметические прогрессии простых чисел с k членами, где k может быть любым натуральным числом. Доказательство является расширением теоремы Семереди .
В 2006 году Теренс Тао и Тамар Зиглер расширили результат, включив в него полиномиальные прогрессии. [4] Точнее, для любых целочисленных многочленов P 1 ,..., P k от одного неизвестного m , все с постоянным членом 0, существует бесконечно много целых чисел x , m таких, что x + P 1 ( m ), ..., x + P k ( m ) одновременно просты. Особый случай, когда полиномами являются m , 2 m , ..., km, подразумевает предыдущий результат о том, что существуют длины k арифметические прогрессии простых чисел .
– Грина – Теорема Дао. Брейяра
Теорема Брейяра-Грина-Тао, доказанная Эммануэлем Брейяром , Беном Грином и Теренсом Тао в 2011 году: [5] дает полную классификацию приближенных групп. Этот результат можно рассматривать как неабелеву версию теоремы Фреймана и обобщение теоремы Громова о группах полиномиального роста .
Пример [ править ]
Если A — набор из N целых чисел, насколько большой или маленькой может быть сумма
разница установлена
и набор продуктов
быть, и как связаны размеры этих наборов? (Не путать: термины «набор разностей» и «набор продуктов» могут иметь и другие значения.)
Расширения [ править ]
Изучаемые множества также могут быть подмножествами алгебраических структур, отличных от целых чисел, например, групп , колец и полей . [6]
См. также [ править ]
- Аддитивная теория чисел
- Примерная группа
- Теорема об углах
- Эргодическая теория Рамсея
- Задачи, связанные с арифметическими прогрессиями
- Плотность Шнирельмана
- Лемма Шепли – Фолкмана.
- Сидон набор
- Набор без суммы
- Проблема суммы-продукта
Примечания [ править ]
- ^ Грин, Бен (июль 2009 г.). «Рецензии на книгу: Аддитивная комбинаторика Теренса К. Тао и Ван Х. Ву» (PDF) . Бюллетень Американского математического общества . 46 (3): 489–497. дои : 10.1090/s0273-0979-09-01231-2 .
- ^ Эрдеш, Пол ; Туран, Пол (1936). «О некоторых последовательностях целых чисел» (PDF) . Журнал Лондонского математического общества . 11 (4): 261–264. дои : 10.1112/jlms/s1-11.4.261 . МР 1574918 . .
- ^ Грин, Бен ; Тао, Теренс (2008). «Простые числа содержат сколь угодно длинные арифметические прогрессии». Анналы математики . 167 (2): 481–547. arXiv : math.NT/0404188 . дои : 10.4007/анналы.2008.167.481 . МР 2415379 . S2CID 1883951 . .
- ^ Тао, Теренс ; Зиглер, Тамар (2008). «Простые числа содержат сколь угодно длинные полиномиальные прогрессии». Акта Математика . 201 (2): 213–305. arXiv : math/0610050 . дои : 10.1007/s11511-008-0032-5 . МР 2461509 . S2CID 119138411 . .
- ^ Брейяр, Эммануэль ; Грин, Бен ; Тао, Теренс (2012). «Строение приближенных групп». Публикации IHÉS по математике . 116 : 115–221. arXiv : 1110.5008 . дои : 10.1007/s10240-012-0043-9 . МР 3090256 . S2CID 119603959 . .
- ^ Бурген, Жан; Кац, Нетс; Тао, Теренс (2004). «Оценка суммы произведения в конечных полях и приложениях». Геометрический и функциональный анализ . 14 (1): 27–57. arXiv : math/0301343 . дои : 10.1007/s00039-004-0451-1 . МР 2053599 . S2CID 14097626 .
Ссылки [ править ]
- Лаба, Изабелла (2008). «От гармонического анализа к арифметической комбинаторике» . Бык. амер. Математика. Соц . 45 (1): 77–115. дои : 10.1090/S0273-0979-07-01189-5 .
- Аддитивная комбинаторика и теоретическая информатика. Архивировано 4 марта 2016 г. в Wayback Machine , Лука Тревизан, SIGACT News, июнь 2009 г.
- Бибак, Ходахаст (2013). «Аддитивная комбинаторика с прицелом на информатику и криптографию». В Борвейне, Джонатан М.; Шпарлинский Игорь Евгеньевич; Зудилин, Вадим (ред.). Теория чисел и смежные области: памяти Альфа ван дер Портена . Том. 43. Нью-Йорк: Спрингерские труды по математике и статистике. стр. 99–128. arXiv : 1108.3790 . дои : 10.1007/978-1-4614-6642-0_4 . ISBN 978-1-4614-6642-0 . S2CID 14979158 .
- Открытые задачи аддитивной комбинаторики , Э. Крут, В. Лев
- От вращающихся игл к стабильности волн: новые связи между комбинаторикой, анализом и PDE , Теренс Тао , уведомления AMS, март 2001 г.
- Тао, Теренс ; Ву, Ван Х. (2006). Аддитивная комбинаторика . Кембриджские исследования по высшей математике. Том. 105. Кембридж: Издательство Кембриджского университета . ISBN 0-521-85386-9 . МР 2289012 . Збл 1127.11002 .
- Гранвилл, Эндрю ; Натансон, Мелвин Б.; Солимоси, Йожеф , ред. (2007). Аддитивная комбинаторика . Материалы CRM и конспекты лекций. Том. 43. Американское математическое общество . ISBN 978-0-8218-4351-2 . Збл 1124.11003 .
- Манн, Генри (1976). Теоремы сложения: Теоремы сложения теории групп и теории чисел (исправленное переиздание издания Wiley 1965 года). Хантингтон, Нью-Йорк: Издательство Роберта Э. Кригера. ISBN 0-88275-418-1 .
- Натансон, Мелвин Б. (1996). Аддитивная теория чисел: классические основы . Тексты для аспирантов по математике . Том. 164. Нью-Йорк: Springer-Verlag. ISBN 0-387-94656-Х . МР 1395371 .
- Натансон, Мелвин Б. (1996). Аддитивная теория чисел: обратные задачи и геометрия сумм . Тексты для аспирантов по математике . Том. 165. Нью-Йорк: Springer-Verlag. ISBN 0-387-94655-1 . МР 1477155 .
Дальнейшее чтение [ править ]
- Некоторые моменты арифметической комбинаторики , ресурсы Теренса Тао
- Аддитивная комбинаторика: зима 2007 г. , К. Саундарараджан
- «Ранние связи аддитивной комбинаторики и информатики» , Лука Тревизан
