Арифметическая комбинаторика
Математический предмет

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

Объем

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

Бен Грин объясняет арифметическую комбинаторику в своем обзоре «Аддитивной комбинаторики» Тао и Ву . [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 целых чисел, насколько большой или маленькой может быть сумма набора?

А + А := { х + у : х , у ∈ А } , {\displaystyle A+A:=\{x+y:x,y\in A\},}

разница установлена

А − А := { х − у : х , у ∈ А } , {\displaystyle AA:=\{xy:x,y\in A\},}

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

А ⋅ А := { х у : х , у ∈ А } {\displaystyle A\cdot A:=\{xy:x,y\in A\}}

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

Расширения

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

Смотрите также

Примечания

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

Ссылки

  • Łaba, Izabella (2008). «От гармонического анализа к арифметической комбинаторике». Bull. Amer. Math. Soc . 45 (1): 77– 115. doi : 10.1090/S0273-0979-07-01189-5 .
  • Аддитивная комбинаторика и теоретическая информатика Архивировано 2016-03-04 в Wayback Machine , Лука Тревизан, SIGACT News, июнь 2009 г.
  • Бибак, Ходахаст (2013). «Аддитивная комбинаторика с видом на компьютерную науку и криптографию». В Borwein, Jonathan M.; Shparlinski, Igor E.; Zudilin, Wadim (ред.). Теория чисел и смежные области: памяти Альфа ван дер Поортена . Том 43. Нью-Йорк: Springer Proceedings in Mathematics & Statistics. С.  99–128 . arXiv : 1108.3790 . doi :10.1007/978-1-4614-6642-0_4. ISBN 978-1-4614-6642-0. S2CID  14979158.
  • Открытые проблемы аддитивной комбинаторики, Э. Крут, В. Лев
  • От вращающихся игл к устойчивости волн: возникающие связи между комбинаторикой, анализом и уравнениями в частных производных, Теренс Тао , AMS Notices, март 2001 г.
  • Тао, Теренс ; Ву, Ван Х. (2006). Аддитивная комбинаторика . Кембриджские исследования по высшей математике. Том 105. Кембридж: Cambridge University Press . ISBN 0-521-85386-9. MR  2289012. Zbl  1127.11002.
  • Грэнвилл, Эндрю ; Натансон, Мелвин Б.; Солимоши, Йожеф , ред. (2007). Аддитивная комбинаторика . Труды и лекции CRM. Том 43. Американское математическое общество . ISBN 978-0-8218-4351-2. Збл  1124.11003.
  • Манн, Генри (1976). Addition Theorems: The Addition Theorems of Group Theory and Number Theory (Исправленное переиздание Wiley ed. 1965). Хантингтон, Нью-Йорк: Robert E. Krieger Publishing Company. ISBN 0-88275-418-1.
  • Натансон, Мелвин Б. (1996). Аддитивная теория чисел: классические основы . Graduate Texts in Mathematics . Vol. 164. Нью-Йорк: Springer-Verlag. ISBN 0-387-94656-X. МР  1395371.
  • Натансон, Мелвин Б. (1996). Аддитивная теория чисел: обратные задачи и геометрия сумм . Graduate Texts in Mathematics . Vol. 165. New York: Springer-Verlag. ISBN 0-387-94655-1. МР  1477155.

Дальнейшее чтение

  • Некоторые основные моменты арифметической комбинаторики, ресурсы Теренса Тао
  • Аддитивная комбинаторика: Зима 2007, К. Сундараджан
  • Ранние связи аддитивной комбинаторики и компьютерных наук, Лука Тревизан
Взято с "https://en.wikipedia.org/w/index.php?title=Арифметическая_комбинаторика&oldid=1273263000"