Арифметическая комбинаторика - Arithmetic combinatorics
В математике арифметическая комбинаторика - это область пересечения теории чисел , комбинаторики , эргодической теории и гармонического анализа .
Сфера
Арифметическая комбинаторика - это комбинаторные оценки, связанные с арифметическими операциями (сложение, вычитание, умножение и деление). Аддитивная комбинаторика - это частный случай, когда задействованы только операции сложения и вычитания.
Бен Грин объясняет арифметическую комбинаторику в своем обзоре «Аддитивной комбинаторики» Тао и Ву .
Важные результаты
Теорема Семереди
Теорема Семереди - результат арифметической комбинаторики, касающийся арифметических прогрессий в подмножествах целых чисел. В 1936 году Эрдеш и Туран предположили, что каждый набор целых чисел A с положительной естественной плотностью содержит k- членную арифметическую прогрессию для каждого k . Эта гипотеза, ставшая теоремой Семереди, обобщает формулировку теоремы ван дер Вардена .
Теорема Грина – Тао и расширения
Теорема Грина – Тао , доказанная Беном Грином и Теренсом Тао в 2004 году, утверждает, что последовательность простых чисел содержит сколь угодно длинные арифметические прогрессии . Другими словами, существуют арифметические прогрессии простых чисел с k членами, где k может быть любым натуральным числом. Доказательство является расширением теоремы Семереди .
В 2006 году Теренс Тао и Тамар Циглер расширили результат на полиномиальные прогрессии. Более точно, для любых целочисленных многочленов P 1 , ..., P k от одного неизвестного m, все с постоянным членом 0, существует бесконечно много целых чисел x , m таких, что x + P 1 ( m ), ..., x + P k ( m ) одновременно просты. Частный случай, когда многочлены равны m , 2 m , ..., km, подразумевает предыдущий результат о том, что существуют арифметические прогрессии простых чисел длины k .
Теорема Брейяра – Грина – Тао.
Теорема Брейяра – Грина – Тао, доказанная Эммануэлем Брейяром , Беном Грином и Теренсом Тао в 2011 году, дает полную классификацию приближенных групп. Этот результат можно рассматривать как неабелев версию теоремы Фреймана и обобщение теоремы Громова о группах полиномиального роста .
Пример
Если A - набор из N целых чисел, насколько большим или малым может быть набор сумм.
набор различий
и набор продуктов
быть, и как связаны размеры этих наборов? (Не следует путать: термины разностный набор и набор продуктов может иметь и другие значения.)
Расширения
Изучаемые множества также могут быть подмножествами алгебраических структур, отличных от целых чисел, например, группы , кольца и поля .
Смотрите также
- Аддитивная теория чисел
- Примерная группа
- Теорема об углах
- Эргодическая теория Рамсея
- Задачи, связанные с арифметическими прогрессиями
- Плотность Шнирельмана
- Лемма Шепли – Фолкмана.
- Сидон набор
- БЕСПЛАТНЫЙ набор
- Суммарная проблема произведения
Заметки
Рекомендации
- Шаба, Изабелла (2008). «От гармонического анализа к арифметической комбинаторике» . Бык. Амер. Математика. Soc . 45 (1): 77–115. DOI : 10.1090 / S0273-0979-07-01189-5 .
- Аддитивная комбинаторика и теоретическая информатика , Лука Тревизан, Новости SIGACT, июнь 2009 г.
- Бибак, Ходахаст (2013). «Аддитивная комбинаторика с точки зрения информатики и криптографии». В Борвейне, Джонатан М .; Шпарлинский, Игорь Е .; Зудилин, Вадим (ред.). Теория чисел и смежные области: памяти Альфа ван дер Портена . 43 . Нью-Йорк: Труды Спрингера по математике и статистике. С. 99–128. arXiv : 1108.3790 . DOI : 10.1007 / 978-1-4614-6642-0_4 . ISBN 978-1-4614-6642-0.
- Открытые задачи аддитивной комбинаторики , Э. Кроут, В. Лев
- От вращающихся игл к стабильности волн: новые связи между комбинаторикой, анализом и PDE , Теренс Тао , Уведомления AMS, март 2001 г.
- Тао, Теренс ; Ву, Ван Х. (2006). Аддитивная комбинаторика . Кембриджские исследования в области высшей математики. 105 . Кембридж: Издательство Кембриджского университета . ISBN 0-521-85386-9. Руководство по ремонту 2289012 . Zbl 1127.11002 .
- Гранвиль, Эндрю ; Натансон, Мелвин Б .; Солимози, Йожеф , ред. (2007). Аддитивная комбинаторика . CRM Proceedings & Lecture Notes. 43 . Американское математическое общество . ISBN 978-0-8218-4351-2. Zbl 1124.11003 .
- Манн, Генри (1976). Теоремы сложения: теоремы сложения теории групп и теории чисел (исправленное переиздание изд. Вили 1965 г.). Хантингтон, Нью-Йорк: Издательство Роберта Э. Кригера. ISBN 0-88275-418-1.
- Натансон, Мелвин Б. (1996). Аддитивная теория чисел: классические основы . Тексты для выпускников по математике . 164 . Нью-Йорк: Springer-Verlag. ISBN 0-387-94656-X. Руководство по ремонту 1395371 .
- Натансон, Мелвин Б. (1996). Аддитивная теория чисел: обратные задачи и геометрия сумм . Тексты для выпускников по математике . 165 . Нью-Йорк: Springer-Verlag. ISBN 0-387-94655-1. Руководство по ремонту 1477155 .
дальнейшее чтение
- Некоторые основные моменты арифметической комбинаторики , ресурсы Теренс Тао
- Аддитивная комбинаторика: зима 2007 , К. Саундарараджан
- Ранние связи аддитивной комбинаторики и информатики , Лука Тревизан