Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Сфера [ править ]

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

Бен Грин объясняет арифметическую комбинаторику в своем обзоре «Аддитивной комбинаторики» Тао и Ву . [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]

См. Также [ править ]

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

Заметки [ править ]

  1. ^ Грин, Бен (июль 2009 г.). «Обзоры книг: Аддитивная комбинаторика, Теренс К. Тао и Ван Х. Ву» (PDF) . Бюллетень Американского математического общества . 46 (3): 489–497. DOI : 10,1090 / s0273-0979-09-01231-2 .
  2. ^ Erdős, Пол ; Туран, Пол (1936). «О некоторых последовательностях целых чисел» (PDF) . Журнал Лондонского математического общества . 11 (4): 261–264. DOI : 10,1112 / jlms / s1-11.4.261 . Руководство по ремонту 1574918 .  .
  3. ^ Грин, Бен ; Тао, Теренс (2008). «Простые числа содержат произвольно длинные арифметические прогрессии». Анналы математики . 167 (2): 481–547. arXiv : math.NT / 0404188 . DOI : 10.4007 / анналы.2008.167.481 . Руководство по ремонту 2415379 . .
  4. ^ Тао, Теренс ; Циглер, Тамар (2008). «Простые числа содержат сколь угодно длинные полиномиальные прогрессии». Acta Mathematica . 201 (2): 213–305. arXiv : math.NT / 0610050 . DOI : 10.1007 / s11511-008-0032-5 . Руководство по ремонту 2461509 . .
  5. ^ Брейяр, Эммануэль ; Грин, Бен ; Тао, Теренс (2012). «Структура примерных групп». Публикации mathématiques de l'IHÉS . 116 : 115–221. arXiv : 1110.5008 . DOI : 10.1007 / s10240-012-0043-9 . Руководство по ремонту 3090256 . .
  6. ^ Бургейн, Жан; Кац, Сети; Тао, Теренс (2004). «Оценка суммарного произведения в конечных полях и приложениях». Геометрический и функциональный анализ . 14 (1): 27–57. arXiv : math / 0301343 . DOI : 10.1007 / s00039-004-0451-1 . Руководство по ремонту 2053599 . 

Ссылки [ править ]

  • Шаба, Изабелла (2008). «От гармонического анализа к арифметической комбинаторике» . Бык. Амер. Математика. Soc . 45 (01): 77–115. DOI : 10.1090 / S0273-0979-07-01189-5 .
  • Аддитивная комбинаторика и теоретическая информатика , Лука Тревизан, Новости SIGACT, июнь 2009 г.
  • Бибак, Ходахаст (2013). «Аддитивная комбинаторика с точки зрения информатики и криптографии». В Борвейне, Джонатан М .; Шпарлинский, Игорь Е .; Зудилин, Вадим (ред.). Теория чисел и смежные области: памяти Альфа ван дер Портена . 43 . Нью-Йорк: Труды Спрингера по математике и статистике. С. 99–128. 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 года, изд. Wiley). Хантингтон, Нью-Йорк: Издательство Роберта Э. Кригера. 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 г. , К. Саундарараджан
  • Ранние связи аддитивной комбинаторики и информатики , Лука Тревизан