Аддитивная комбинаторика

Аддитивная комбинаторика (от англ. addition — сложение) — междисциплинарная^[1] область математики, изучающая взаимозависимость различных количественных интерпретаций понятия структурированности подмножества группы (как правило, конечной), а также аналогичные свойства производных от множества структур, использующихся при этих интерпретациях. Кроме того, аддитивная комбинаторика изучает структурированность в различных смыслах некоторых специфических множеств или классов множеств (например, подмножеств простых чисел или мультипликативных подгрупп).

Таким образом, основным объектом изучения являются конечные множества, по возможности как можно более абстрактные, ограниченные иногда только в своих размерах, что делает эту науку похожей на комбинаторику. Однако, в отличие от комбинаторики как таковой, где элементы множеств идентифицируются только отличием друг от друга и принадлежностью к тем или иным рассматриваемым множествам, в аддитивной комбинаторике у каждого элемента множества есть чёткое значение, и между ними появляются дополнительные взаимосвязи, вытекающие из их значений и свойств операции группы (и, возможно, специфических законов, характерных для заданной группы).

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

Вопросы представления чисел через суммы элементов из небольшого числа заданных множеств рассматривались математиками ещё с древних времён. Классическими примерами являются задачи представимости любого числа суммой четырёх квадратов (теорема Лагранжа о сумме четырёх квадратов) или любого чётного числа, которое больше трёх, суммой двух простых (проблема Гольдбаха). Если обозначить через ${\displaystyle Q=\left\lbrace {0}\right\rbrace \cup \left\lbrace {n^{2}:n\in {\mathbb {N} }}\right\rbrace }$ множество всех квадратов неотрицательных чисел, то в терминах аддитивной комбинаторики (см. раздел с обозначениями ниже) теорему Лагранжа можно записать как

${\displaystyle Q+Q+Q+Q={\mathbb {N} }}$

В ходе решения подобных задач возникали и другие аналогичные, с другими множествами, но похожими формулировками. Всё это сформировало область математики, называемую аддитивной теорией чисел.

Однако аддитивную комбинаторику не следует воспринимать как обобщение или развитие аддитивной теории чисел — хотя задачи последней могут быть удобно записаны в терминах аддитивной комбинаторики, но её общие методы к ним, как правило, не применимы. Теория чисел всегда рассматривает множества специального вида — простые числа, квадраты, другие степени, числа с малым количеством делителей и т. д. Аддитивная же комбинаторика пытается понять структуру сложения как таковую, вывести как можно более общие результаты.

Тем не менее, первые результаты, которые можно по духу отнести к аддитивно-комбинаторным, зарождались в начале XX века именно как часть теории чисел (называемая также комбинаторной теорией чисел).^[1] Таким, например, является метод Шнирельмана для решения проблемы Гольдбаха (который был также применён Линником для проблемы Варинга) — он основан на теореме Шнирельмана о множестве сумм чисел из двух произвольных множеств, о которых известна только их плотность^[2] (следует заметить, что при этом само специфическое определение плотности по Шнирельману, использовавшееся в этой теореме, в аддитивной комбинаторике как объект для изучения не прижилось).

Возникшая в первой половине XX века теория Рамсея также анализировала различные представления о структурированности. Утверждения теории Рамсея касаются наличия хотя бы малого «островка» структурности в достаточно сложных (по количеству элементарных частей) объектах.^[3]

Однако теория Рамсея рассматривает не подмножества, а разбиения заданного множества (например, множества рёбер графа, натуральных чисел или части булеана конечного множества), и результат о структуре имеет в виду наличие структурированности у одного из элементов разбиения, и, как правило, непонятно, у какого. Следовательно, о каком-то отдельном подмножестве ничего сказать нельзя.

Наглядным примером является теорема ван дер Вардена — она говорит, что при любом разбиении натуральных чисел на конечное число классов хотя бы в одном из классов будет присутствовать арифметическая прогрессия (любой заданной длины). При этом очевидно, что в любом разбиении есть класс, плотность чисел в котором больше, чем в других, и интуитивно кажется, что прогрессия должна находиться в этом множестве — ведь здесь больше всего элементов, то есть больше всего возможностей. Очевидно также, что самое большое множество будет иметь положительную (ненулевую) плотность. Однако доказать, что абсолютно любое бесконечное множество натуральных чисел положительной плотности содержит в себе арифметическую прогрессию, не получается просто через теорему ван дер Вардена — по ней прогрессия может оказаться в любом классе, даже самом маленьком. Для доказательства наличия прогрессии в любом плотном множестве приходится привлекать намного более сложные средства — решение этой задачи получило название теоремы Семереди, которая как раз считается классическим аддитивно-комбинаторным результатом.

Гибким инструментом для оценки упорядоченности множества, сыгравшим значительную роль и в аддитивной теории чисел, являются тригонометрические суммы (суммы корней из единицы, соответствующих числам множества). Они стали инструментом и объектом для изучения и в аддитивной комбинаторике, поскольку допускают довольно общее применение.

Ещё Гаусс, первым исследовавший тригонометрические суммы, обнаружил через них связь распределения всех возможных разностей чисел из заданного множества и самого множества. Исследуя квадратичные вычеты, Гаусс рассматривал сумму

${\displaystyle S(a)=\sum \limits _{x=0}^{p-1}{e^{2\pi {\frac {ax^{2}}{p}}i}}}$

и выводил оценку для квадрата её модуля:

${\displaystyle |S(a)|^{2}=\sum \limits _{x,y}{e^{2\pi {\frac {a(x^{2}-y^{2})}{p}}i}}}$

Оценка этой суммы получалась чисто комбинаторно из свойств выражения ${\displaystyle x^{2}-y^{2}}$ при замене переменной ${\displaystyle x=y+h}$.^[4] Таким образом, мультимножество разностей давало информацию о структуре множества самих квадратичных вычетов. В аддитивной комбинаторике действует похожий по идее подход, когда уже множество, а не мультимножество разностей (или сумм, произведений и т. д.) элементов из заданного множества даёт информацию о структуре этого множества. Такой переход — от мультимножества ко множеству — связан с переходом от количества решений того или иного уравнения (например, ${\displaystyle a_{1}+b_{1}=a_{2}+b_{2},a_{i}\in A,b_{i}\in B}$) к представлению чисел в том или ином виде (например, в виде ${\displaystyle a+b,a\in A,b\in B}$), который в принципе характерен для метода тригонометрических сумм.

Отдельным фундаментом для развития новой науки о поэлементных суммах множеств (множествах сумм ${\displaystyle A+B=\left\lbrace {a+b:a\in A,b\in B}\right\rbrace }$) стала доказанная Григорием Фрейманом теорема о строении множеств с малым удвоением (то есть множеств, множество сумм двух элементов которых имеет малый размер, или проще говоря, суммы элементов из которых часто совпадают).^[5]

Вопросы о суммах элементов из того или иного множества рассматривались также Эрдёшем и Семереди без введения специальной символики для обозначения суммирования множеств.^[6]

Важным понятием аддитивной комбинаторики является множество сумм

${\displaystyle A+B=\left\lbrace {a+b:a\in A,b\in B}\right\rbrace }$

для конечных множеств ${\displaystyle A,B\in \mathrm {G} }$, где ${\displaystyle (\mathrm {G} ,+)}$ — группа. Размер такого множества определяется структурой ${\displaystyle A}$ и ${\displaystyle B}$ относительно операции ${\displaystyle +}$. Если ${\displaystyle A}$ и ${\displaystyle B}$ — арифметические прогрессии, то ${\displaystyle |A+B|}$ мало. А если, например, ${\displaystyle A,B\in {\mathbb {Z} }_{n}}$ выбраны случайно по схеме Бернулли, то ${\displaystyle |A+B|}$ очень велико. Промежуточные случаи между указанными двумя как раз и представляют аддитивно-комбинаторный интерес.

Кроме того, интересна сама по себе структура множеств ${\displaystyle A+B}$. В частности, по состоянию на 2018 год нет общих критериев (кроме прямого перебора), позволяющих определить, представляется ли заданное множество в виде ${\displaystyle A+A}$.

В таблице ниже представлены теоремы и неравенства аддитивной комбинаторики, связывающие различные характеристики подмножеств групп. Утверждение, указанное в ячейке, связывает характеристики, указанные в её строке и столбце. Приведены лишь некоторые, наиболее известные, из таких теорем.

Для краткости в заголовках используются следующие сокращения:

• Плотность множества ${\displaystyle A\subset {\mathbb {G} }}$ для конечной группы ${\displaystyle {\mathbb {G} }}$ — это величина ${\displaystyle {\frac {|A|}{|{\mathbb {G} }|}}}$ или закон её асимптотического роста с ростом размера ${\displaystyle {\mathbb {G} }}$, а для бесконечных ${\displaystyle {\mathbb {G} }}$ — асимптотическая плотность (или закон распределения) ${\displaystyle A}$ в ${\displaystyle {\mathbb {G} }}$,
• ОАП (от «обобщённая арифметическая прогрессия») — присутствие во множестве больших арифметических прогрессий, нетривиальных обобщённых арифметических прогрессий или их больших частей, а также, наоборот, возможность покрыть множество (или большую его часть) не слишком большой арифметической прогрессией;
• ${\displaystyle A_{1}+\dots +A_{k}}$ — размер и строение множества сумм (а также разностей и комбинаций сумм и разностей) — в частности, возможность представить любой элемент группы как сумму заданного количества элементов данного множества;
• ${\displaystyle X=A_{1}+\dots +A_{k}}$ — представимость множества или большой его части как множества сумм (а также разностей и комбинаций сумм и разностей) чисел из небольшого числа множеств, то есть разрешимость уравнения множеств ${\displaystyle X=A_{1}+\dots +A_{k}}$ для заданного ${\displaystyle X}$, возможно, даже при определённых условиях на ${\displaystyle A_{1},\dots ,A_{k}}$ (например, ${\displaystyle A_{1}=\dots =A_{k}}$), где ${\displaystyle +}$ означает сумму Минковского
• коэффициенты Фурье имеются в виду для характеристической функции множества и функций, определяемых через неё, а также их статистика — разного рода нормы, количество элементов с большим значением и структура их множества;
• ЧРУ (от «число решений уравнения») — число решений различных линейных уравнений (в частности, аддитивная энергия) или систем уравнений, в которых переменные принимают значения из заданных множеств, а также соотношение количества их решений

Также в ячейках используется несколько специфических обозначений:

• ${\displaystyle {\widehat {A}}}$ — коэффициент Фурье характеристической функции множества ${\displaystyle A}$;
• ${\displaystyle E(A,B)}$ — аддитивная энергия
• ${\displaystyle \rho _{A}(x)=\mathbf {1} _{A}(x)-{\frac {|A|}{|{\mathbb {G} }|}}}$ — такая функция называется балансовой функцией множества ${\displaystyle A\in {\mathbb {G} }}$, поскольку ${\displaystyle \sum \limits _{x\in {\mathbb {G} }}{\rho _{A}(x)}=0}$.

	Плотность	ОАП	${\displaystyle A_{1}+\dots +A_{k}}$	${\displaystyle X=A_{1}+\dots +A_{k}}$	Коэффициенты Фурье	ЧРУ
Плотность
ОАП	Теорема Семереди
${\displaystyle A_{1}+\dots +A_{k}}$	Неравенство Шнирельмана, Теорема Фюрстенберга — Шаркози[англ.]	Теорема Фреймана[англ.]
${\displaystyle X=A_{1}+\dots +A_{k}}$		${\displaystyle A+B}$ при больших ${\displaystyle |A|}$ и ${\displaystyle |B|}$ содержат длинную а. п.[7][8]	Неравенство Плюннеке — Ружа
Коэффициенты Фурье	Принцип неопределённости[9]	Если ${\displaystyle A\subset {\mathbb {Z} }_{N}}$, ${\displaystyle ||{\widehat {\rho _{A}}}||_{\infty }}$ мало, то ${\displaystyle A}$ содержит а. п. длины 3[10]	Если ${\displaystyle ||{\widehat {A}}||_{\infty }}$ и ${\displaystyle ||{\widehat {B}}||_{\infty }}$ малы, то ${\displaystyle |A+B|}$ велико
ЧРУ	Теорема Рота	Если ${\displaystyle A}$ - а. п., то ${\displaystyle E(A,A)\geq \Omega (|A|^{3})}$	${\displaystyle |A|^{2}|B|^{2}\geq |A+B|E(A,B)}$[11]	Из соотношений аддитивных энергий можно сделать выводы о структуре множества[12]	Если ${\displaystyle A,B\in {\mathbb {Z} }_{N}}$, то ${\displaystyle E(A,B)=\sum \limits _{r=0}^{N-1}{|{\widehat {A}}(r)|^{2}|{\widehat {B}}(r)|^{2}}}$

Норма Гауэрса^[англ.] — обобщение понятия коэффициентов Фурье, придуманное Уильямом Гауэрсом в ходе доказательства теоремы Семереди.

Изоморфизм Фреймана — это отображение из подмножества одной группы в подмножество другой, сохраняющее отношение равенства сумм заданного количества элементов множества.

Конечное множество ${\displaystyle A=\left\lbrace {a_{1}\leq \dots \leq a_{n}}\right\rbrace }$ вещественных чисел называется выпуклой последовательностью (или выпуклым множеством) если ${\displaystyle a_{i+1}-a_{i}<a_{i+2}-a_{i+1}}$ для ${\displaystyle i=1,\dots ,n-2}$, то есть если ${\displaystyle A}$ является образом отрезка ${\displaystyle \left\lbrace {1,\dots ,n}\right\rbrace }$ для некоторой строго выпуклой функции.^[13] Свойства таких множеств широко изучаются в аддитивной комбинаторике.^{[14][15][16][17]} Это понятие не стоит путать с выпуклым множеством в обычном смысле.

Множество Бора — структура с малым удвоением, используемая иногда в доказательствах как ослабленный аналог понятия подпространства.^[18]. Определяется как множество элементов поля, на которых все аддитивные характеры из заданного семейства имеют малое значение. Множества Бора содержат в себе большие обобщённые арифметические прогрессии, так что наличие во множестве прогрессий иногда доказывается через наличие в нём нужного множества Бора.

Почти периодичная функции^[англ.] — функция ${\displaystyle f}$ такая, что норма ${\displaystyle ||f(x+t)-f(x)||_{p}}$ достаточно мала для некоторого ${\displaystyle p}$ и для всех ${\displaystyle t\in T}$, где ${\displaystyle T}$ — некоторое множество (например, множество Бора). На таких множествах построено одно из доказательств теоремы Рота.^[19]

Множество больших тригонометрических сумм (иногда называется также спектром) множества ${\displaystyle A\subset {\mathbb {Z} }_{p}}$ — это множество вычетов ${\displaystyle r}$, для которых сумма ${\displaystyle \sum \limits _{a\in A}{e_{p}(ar)}}$ (коэффициент Фурье) имеет большой модуль.^[20]

Диссоциативным множеством ${\displaystyle A}$ называется множество, для которого линейные комбинации ${\displaystyle \sum \limits _{a\in A}{\varepsilon _{a}a}=0}$ равны нулю, где ${\displaystyle \forall a\in A:\varepsilon _{a}\in \left\lbrace {-1,0,1}\right\rbrace }$, только когда все ${\displaystyle \varepsilon _{a}}$ равны нулю. В частности, это означает что суммы элементов из двух различных подмножеств всегда различны ^[20]. Диссоциативность можно рассматривать как аналог линейной независимости над ${\displaystyle \left\lbrace {-1,0,1}\right\rbrace }$.

Конечно, несмотря на существование мощных и сложных методов изучения теорем аддитивной комбинаторики, некоторые приёмы и задачи поддаются элементарному описанию. Из неравенства Коши ${\displaystyle \left({\sum \limits _{i=1}^{n}{a_{i}}}\right)^{2}\leq n\sum \limits _{i=1}^{n}{{a_{i}}^{2}}}$ выводятся свойства аддитивной энергии, применяемые почти повсеместно. Вообще при элементарном подходе часто анализируется число решений тех или иных уравнений. Также часто применяется аргумент среднего^[англ.] — например, при разложении числа решений уравнения на сумму числа решений при том или ином значении отдельной переменной.^[21]

Элементарными методами можно доказать теорему Рота^[22] и теорему Коши — Давенпорта^[23].

Однако многие доказательства, полученные другими методами, не имеют элементарных аналогов.

Одним из самых знаковых комбинаторных доказательств аддитивной комбинаторики является первое из появившихся доказательство теоремы Семереди^[24] — в нём Семереди сформулировал и использовал так называемую лемму о регулярности, касающуюся чистой теории графов. Аналогии с этой теорией применяются и при доказательстве особых версий неравенства Плюннеке-Ружа или оценок типа Балога-Семереди-Гауэрса^[25].

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

Примером инструмента для применения такого метода является комбинаторная теорема о нулях. С помощью неё может доказываться теорема Коши-Давенпорта и некоторые её обобщения.^[23]

Другие применения алгебраического метода можно найти в доказательствах теоремы Рота для некоторых групп специального вида^[26][27][28] или в оценке размера пересечений сдвигов мультипликативных подгрупп полей ${\displaystyle {\mathbb {F} }_{p}}$ и доказательстве проблемы Варинга для простого поля (для этого используется, в частности, метод Степанова).^[29]

Основным аналитическим инструментом в аддитивной комбинаторике являются коэффициенты Фурье. Это обусловлено тесной связью операции взятия коэффициента Фурье с операцией свёртки функций. Коэффициенты Фурье были применены ещё при первом доказательстве теоремы Рота.^[30] Их обобщением являются нормы Гауэрса, науку о которых также называют анализом Фурье высших порядков.^[20]

На примере коэффициентов Фурье (в частности, их применения к доказательству теоремы Рота) лучше всего иллюстрируется так называемый итеративный аргумент, когда рассмотрение произвольного множества разбивается на два случая — когда у множества нет больших (относительно размера множества) коэффициентов Фурье и когда есть. В первом случае можно напрямую воспользоваться свойствами коэффициентов Фурье, а во втором — найти подструктуру множества с большей плотностью в бесконечной арифметической прогрессии, причём с настолько большей, что количество таких возможных шагов до достижения предельной плотности будет ограничено величиной, зависящей от общей плотности начального множества. Это обнаруживает идею разделения на случай псевдослучайного множества и множества с некой глобальной структурой. Такая идея нашла отражение и в других методах.^[1][10]

Другой аналитический подход заключается в исследовании почти периодичности функций, связанных с характеристическими функциями исследуемых множеств.^[31]

Эргодический подход предполагает применение к задачам аддитивной комбинаторики результатов из теории динамических систем. Впервые этот подход был применён Хиллелем Фюрстенбергом к теореме Семереди^[32], но вскоре оказалось, что он допускает обобщение на намного более широкий круг задач.

Теория динамических систем часто позволяет доказать результаты, недоступные для переформулировки другими методами, но при этом не способна дать никаких количественных оценок (например, оценок на плотность множества в теореме Семереди).^[33]

К рассматриваемой науке имеют приложения и некоторые другие области:

• теорема Семереди — Троттера из комбинаторной геометрии (особенно в вопросах, касающихся выпуклых множеств)^[13][16][17];
• геометрия чисел^[34];
• теория представлений симметрических групп^{[англ.][35]}.
• теория собственных чисел (может использоваться для вывода неравенства между количеством решений некоторых систем линейных уравнений;^[36]);

• Пол Эрдёш
• Григорий Фрейман
• Имре Ружа^[англ.]
• Эндре Семереди
• Уильям Гауэрс
• Бен Грин
• Теренс Тао
• Роджер Хиз-Браун^[англ.]
• Жан Бургейн
• Том Сандерс^[англ.]
• Хиллель Фюрстенберг^[англ.]
• Сергей Конягин
• Илья Шкредов

• Сумма Минковского
• Арифметическая комбинаторика

• Грэхем, Рональд. Начала теории Рамсея. — М.: Мир, 1984. — ISBN 5-09-002630-0.

• М. З. Гараев. Суммы и произведения множеств и оценки рациональных тригонометрических сумм в полях простого порядка (рус.) // Успехи математических наук. — 2010. — Вып. 4. — С. 5—66.

• И. Д. Шкредов. Теорема Семереди и задачи об арифметических прогрессиях (рус.) // Успехи математических наук. — 2006. — Вып. 6. — С. 111—179.

• И. Д. Шкредов. Анализ Фурье в комбинаторной теории чисел (рус.) // Успехи математических наук. — 2010. — Вып. 3. — С. 127—184.

• Terence Tao, Van H. Vu. Additive combinatorics (англ.). — Cambridge University Press. — 2006. — ISBN 0-511-24530-0.

• Imre Ruzsa. Sumsets and structure (англ.).

• Фрейман, Григорий Абелевич. Начала структурной теории множеств (рус.). — Типография "Татполиграф". — 1966.

• И. М. Гельфанд, Ю. В. Линник. Элементарные методы в аналитической теории чисел (рус.). — М.: Физматгиз. — 1962.

• И. М. Виноградов. Метод тригонометрических сумм в теории чисел (рус.). — Издательство "Наука". — 1971.