Арифметическая комбинаторика

В математике арифметическая комбинаторика - это область пересечения теории чисел, комбинаторики, эргодической теории и гармонический анализ.

• 1 Область применения
• 2 Важные результаты
  • 2.1 Теорема Семереди
  • 2.2 Теорема Грина – Тао и расширения
• 3 Пример
• 4 Расширения
• 5 См. Также
• 6 Примечания
• 7 Ссылки
• 8 Дополнительная литература

Арифметическая комбинаторика - это комбинаторные оценки, связанные с арифметическими операциями (сложение, вычитание, умножение и деление).). Аддитивная комбинаторика - это особый случай, когда задействованы только операции сложения и вычитания.

Бен Грин объясняет арифметическую комбинаторику в своем обзоре «Аддитивной комбинаторики» Тао и Vu.

Теорема Семереди

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

и ее расширений

Теорема Грина – Тао, доказанная с помощью Бен Грин и Теренс Тао в 2004 году утверждает, что последовательность простых чисел содержит произвольно длинные арифметические прогрессии. Другими словами, существуют арифметические прогрессии простых чисел с k членами, где k может быть любым натуральным числом. Доказательство является расширением теоремы Семереди.

В 2006 году Теренс Тао и Тамар Зиглер распространили результат на полиномиальные прогрессии. Точнее, для любых целочисленных многочленов P1,..., P k от одного неизвестного m все с постоянным членом 0, существует бесконечно много целых чисел x, m таких, что x + P 1 (m),..., x + P k (m) одновременно являются простыми числами. Частный случай, когда многочлены равны m, 2m,..., km, подразумевает предыдущий результат о том, что существуют арифметические прогрессии простых чисел длины k.

Если A - это набор из N целых чисел, насколько большим или маленьким может быть sumset

$A\; +\; A:\; =\; \{x\; +\; y:\; x,\; y\; \in \; A\; \},\; \{\backslash \; displaystyle\; A\; +\; A:\; =\; \backslash \; \{x\; +\; y:\; x,\; y\; \backslash \; in\; A\; \backslash \},\}$

набор разностей

$A\; -\; A:\; =\; \{x\; -\; y:\; x,\; y\; \in \; A\; \},\; \{\backslash \; displaystyle\; AA:\; =\; \backslash \; \{xy:\; x,\; y\; \backslash \; in\; A\; \backslash \},\}$

и набор продуктов

$A\; \cdot \; A:\; =\; \{xy:\; x,\; y\; \in \; A\}\; \{\backslash \; displaystyle\; A\; \backslash \; cdot\; A:\; =\; \backslash \; \{xy:\; x,\; y\; \backslash \; in\; A\; \backslash \}\}$

be, и как связаны размеры этих множеств? (Не путать: термины набор различий и набор продуктов могут иметь другие значения.)

Изучаемые наборы также могут быть подмножествами алгебраических структур, отличных от целых чисел, например, группы, кольца и поля.

• Аддитивная теория чисел
• Теорема об углах
• Эргодическая теория Рамсея
• Задачи, связанные с арифметическими прогрессиями
• Плотность Шнирельмана
• Лемма Шепли – Фолкмана
• Множество Сидона
• Множество без сумм

• Таба, Изабелла (2008). «От гармонического анализа к арифметической комбинаторике». Бык. Амер. Математика. Soc. 45 (01): 77–115. doi : 10.1090 / S0273-0979-07-01189-5.
• Аддитивная комбинаторика и теоретическая информатика, Лука Тревизан, SIGACT News, июнь 2009 г.
• Бибак, Ходахаст ( 2013). «Аддитивная комбинаторика с точки зрения информатики и криптографии». В Борвейне, Джонатан М.; Шпарлинский, Игорь Е.; Зудилин, Вадим (ред.). Теория чисел и смежные области: памяти Альфа ван дер Портена. 43 . Нью-Йорк: Труды Спрингера по математике и статистике. С. 99–128. DOI : 10.1007 / 978-1-4614-6642-0_4. ISBN 978-1-4614-6642-0.
• Открытые проблемы в аддитивной комбинаторике, Э. Крут, В. Лев
• От вращающихся игл к устойчивости волн: возникающие связи между Комбинаторика, анализ и PDE, Теренс Тао, AMS Notices March 2001
• Тао, Теренс ; Ву, Ван Х. (2006). Аддитивная комбинаторика. Кембриджские исследования в области высшей математики. 105 . Кембридж: Cambridge University Press. ISBN 0-521-85386-9. MR 2289012. Zbl 1127.11002.
• Грэнвилл, Эндрю ; Натансон, Мелвин Б.; Солимози, Йожеф, ред. (2007). Аддитивная комбинаторика. CRM Proceedings Lecture Notes. 43. Американское математическое общество. ISBN 978-0-8218-4351-2. Zbl 1124.11003.
• Манн, Генри (1976). Теоремы сложения: теоремы сложения теории групп и теории чисел (исправленное переиздание изд. Wiley 1965 г.). Хантингтон, Нью-Йорк: Издательство Роберта Кригера. ISBN 0-88275-418-1.
• Натансон, Мелвин Б. (1996). Аддитивная теория чисел: классические основы. Тексты для выпускников по математике. 164 . Нью-Йорк: Springer-Verlag. ISBN 0-387-94656-X. MR 1395371.
• Натансон, Мелвин Б. (1996). Аддитивная теория чисел: обратные задачи и геометрия сумм. Тексты для выпускников по математике. 165 . Нью-Йорк: Springer-Verlag. ISBN 0-387-94655-1. MR 1477155.

• Некоторые основные моменты арифметической комбинаторики, ресурсы от Теренс Тао
• Аддитивная комбинаторика : Winter 2007, K Soundararajan
• Early Connections of Additive Combinatorics and Computer Science, Luca Trevisan