WikiSort.ru - Не сортированное

Арифметическая комбинаторика — раздел математики, возникший на стыке теории чисел, комбинаторики, эргодической теории и гармонического анализа.

Пусть ${\displaystyle \mathbb {N} }$  — множество натуральных чисел, ${\displaystyle \mathbb {E} }$  — чётных, ${\displaystyle \mathbb {P} }$  — простых, а ${\displaystyle \mathbb {S} }$  — множество всех квадратов натуральных чисел.

Знаменитую теорему Лагранжа можно компактно сформулировать как равенство ${\displaystyle \mathbb {S} +\mathbb {S} +\mathbb {S} +\mathbb {S} =\mathbb {N} }$ , а не менее знаменитую гипотезу Гольдбаха — как ${\displaystyle \mathbb {P} +\mathbb {P} \supseteq \mathbb {E} }$ . Изучением поведения подмножеств целых чисел (а также более сложных алгебраических структур) относительно имеющихся операций занимается (в тесном сотрудничестве с традиционной теорией чисел) арифметическая комбинаторика.

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

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

Арифметическая комбинаторика объясняется в рецензии Грина на книгу «Аддитивная комбинаторика» Тао и Ву.

Пример задачи

Пусть A — множество, содержащее n целых чисел, каков будет размер множества сумм

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

множества разностей (не путать с разностью множеств)

${\displaystyle A-A:=\{x-y:x,y\in A\}}$ ,

или множества произведений (не путать с произведением множеств)

${\displaystyle A\times A:=\{xy:x,y\in A\}}$

Как связаны размеры этих множеств?

См. также

• Аддитивная теория чисел
• Теорема об уголках
• Эргодическая теория Рамсея
• Теорема Грина — Тао
• Плотность последовательности
• Лемма Шепли — Фолкмана
• Множество Сидона
• Свободное от сумм множество
• Теорема Семереди
• Теорема сумм-произведений
• Сумма Минковского
• Комбинаторная теорема о нулях

Примечания

Ссылки

• Łaba, Izabella (2008). “From harmonic analysis to arithmetic combinatorics”. Bull. Amer. Math. Soc. 45 (01): 77—115. DOI:10.1090/S0273-0979-07-01189-5.
• Additive Combinatorics and Theoretical Computer Science, Luca Trevisan, SIGACT News, June 2009
• Additive combinatorics with a view towards computer science and cryptography: An exposition, Khodakhast Bibak, 2012
• Open problems in additive combinatorics, E Croot, V Lev
• From Rotating Needles to Stability of Waves: Emerging Connections between Combinatorics, Analysis, and PDE, Тао, Теренс, AMS Notices March 2001
• Tao, Terence. Additive combinatorics / Terence Tao, Vu. — Cambridge : Cambridge University Press, 2006. — Vol. 105. — ISBN 0-521-85386-9.
• Additive Combinatorics. — American Mathematical Society, 2007. — Vol. 43. — ISBN 978-0-8218-4351-2.
• Mann, Henry. Addition Theorems: The Addition Theorems of Group Theory and Number Theory. — Corrected reprint of 1965 Wiley. — Huntington, New York : Robert E. Krieger Publishing Company, 1976. — ISBN 0-88275-418-1.
• Melvyn B. Nathanson. Additive Number Theory: the Classical Bases. — Springer-Verlag, 1996. — Vol. 164. — ISBN 0-387-94656-X.
• Melvyn B. Nathanson. Additive Number Theory: Inverse Problems and the Geometry of Sumsets. — Springer-Verlag, 1996. — Vol. 165. — ISBN 0-387-94655-1.
• Теренс Тао, Some Highlights of Arithmetic Combinatorics
• K Soundararajan, Additive Combinatorics: Winter 2007
• Luca Trevisan, Earliest Connections of Additive Combinatorics and Computer Science

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.