Аддитивная комбинаторика (от — сложение) — междисциплинарная область математики, изучающая взаимозависимость различных количественных интерпретаций понятия структурированности подмножества группы (как правило, конечной), а также аналогичные свойства производных от множества структур, использующихся при этих интерпретациях. Кроме того, аддитивная комбинаторика изучает структурированность в различных смыслах некоторых специфических множеств или классов множеств (например, подмножеств простых чисел или мультипликативных подгрупп).
Таким образом, основным объектом изучения являются конечные множества, по возможности как можно более абстрактные, ограниченные иногда только в своих размерах, что делает эту науку похожей на комбинаторику. Однако, в отличие от комбинаторики как таковой, где элементы множеств идентифицируются только отличием друг от друга и принадлежностью к тем или иным рассматриваемым множествам, в аддитивной комбинаторике у каждого элемента множества есть чёткое значение, и между ними появляются дополнительные взаимосвязи, вытекающие из их значений и свойств операции группы (и, возможно, специфических законов, характерных для заданной группы).
Аддитивная комбинаторика тесно связана с арифметической комбинаторикой, где предметом изучения является соотношение подмножества поля (а не просто группы, как здесь) сразу с двумя операциями — сложением и умножением.
Предпосылки возникновения
Аддитивная теория чисел
Вопросы представления чисел через суммы элементов из небольшого числа заданных множеств рассматривались математиками ещё с древних времён. Классическими примерами являются задачи представимости любого числа суммой четырёх квадратов (теорема Лагранжа о сумме четырёх квадратов) или любого чётного числа, которое больше трёх, суммой двух простых (проблема Гольдбаха). Если обозначить через множество всех квадратов неотрицательных чисел, то в терминах аддитивной комбинаторики (см. раздел с обозначениями ниже) теорему Лагранжа можно записать как
В ходе решения подобных задач возникали и другие аналогичные, с другими множествами, но похожими формулировками. Всё это сформировало область математики, называемую аддитивной теорией чисел.
Однако аддитивную комбинаторику не следует воспринимать как обобщение или развитие аддитивной теории чисел — хотя задачи последней могут быть удобно записаны в терминах аддитивной комбинаторики, но её общие методы к ним, как правило, не применимы. Теория чисел всегда рассматривает множества специального вида — простые числа, квадраты, другие степени, числа с малым количеством делителей и т. д. Аддитивная же комбинаторика пытается понять структуру сложения как таковую, вывести как можно более общие результаты.
Тем не менее, первые результаты, которые можно по духу отнести к аддитивно-комбинаторным, зарождались в начале XX века именно как часть теории чисел (называемая также комбинаторной теорией чисел). Таким, например, является метод Шнирельмана для решения проблемы Гольдбаха (который был также применён Линником для проблемы Варинга) — он основан на теореме Шнирельмана о множестве сумм чисел из двух произвольных множеств, о которых известна только их плотность (следует заметить, что при этом само специфическое определение плотности по Шнирельману, использовавшееся в этой теореме, в аддитивной комбинаторике как объект для изучения не прижилось).
Теория Рамсея
Возникшая в первой половине XX века теория Рамсея также анализировала различные представления о структурированности. Утверждения теории Рамсея касаются наличия хотя бы малого «островка» структурности в достаточно сложных (по количеству элементарных частей) объектах.
Однако теория Рамсея рассматривает не подмножества, а разбиения заданного множества (например, множества рёбер графа, натуральных чисел или части булеана конечного множества), и результат о структуре имеет в виду наличие структурированности у одного из элементов разбиения, и, как правило, непонятно, у какого. Следовательно, о каком-то отдельном подмножестве ничего сказать нельзя.
Наглядным примером является теорема ван дер Вардена — она говорит, что при любом разбиении натуральных чисел на конечное число классов хотя бы в одном из классов будет присутствовать арифметическая прогрессия (любой заданной длины). При этом очевидно, что в любом разбиении есть класс, плотность чисел в котором больше, чем в других, и интуитивно кажется, что прогрессия должна находиться в этом множестве — ведь здесь больше всего элементов, то есть больше всего возможностей. Очевидно также, что самое большое множество будет иметь положительную (ненулевую) плотность. Однако доказать, что абсолютно любое бесконечное множество натуральных чисел положительной плотности содержит в себе арифметическую прогрессию, не получается просто через теорему ван дер Вардена — по ней прогрессия может оказаться в любом классе, даже самом маленьком. Для доказательства наличия прогрессии в любом плотном множестве приходится привлекать намного более сложные средства — решение этой задачи получило название теоремы Семереди, которая как раз считается классическим аддитивно-комбинаторным результатом.
Тригонометрические суммы
Гибким инструментом для оценки упорядоченности множества, сыгравшим значительную роль и в аддитивной теории чисел, являются тригонометрические суммы (суммы корней из единицы, соответствующих числам множества). Они стали инструментом и объектом для изучения и в аддитивной комбинаторике, поскольку допускают довольно общее применение.
Ещё Гаусс, первым исследовавший тригонометрические суммы, обнаружил через них связь распределения всех возможных разностей чисел из заданного множества и самого множества. Исследуя квадратичные вычеты, Гаусс рассматривал сумму
и выводил оценку для квадрата её модуля:
Оценка этой суммы получалась чисто комбинаторно из свойств выражения при замене переменной . Таким образом, мультимножество разностей давало информацию о структуре множества самих квадратичных вычетов. В аддитивной комбинаторике действует похожий по идее подход, когда уже множество, а не мультимножество разностей (или сумм, произведений и т. д.) элементов из заданного множества даёт информацию о структуре этого множества. Такой переход — от мультимножества ко множеству — связан с переходом от количества решений того или иного уравнения (например, ) к представлению чисел в том или ином виде (например, в виде ), который в принципе характерен для метода тригонометрических сумм.
Теорема Фреймана
Отдельным фундаментом для развития новой науки о поэлементных суммах множеств (множествах сумм ) стала доказанная Григорием Фрейманом теорема о строении множеств с малым удвоением (то есть множеств, множество сумм двух элементов которых имеет малый размер, или проще говоря, суммы элементов из которых часто совпадают).
Вопросы о суммах элементов из того или иного множества рассматривались также Эрдёшем и Семереди без введения специальной символики для обозначения суммирования множеств. .
Предмет изучения
Множество сумм
Важным понятием аддитивной комбинаторики является множество сумм
для конечных множеств , где — группа. Размер такого множества определяется структурой и относительно операции . Если и — арифметические прогрессии, то мало. А если, например, выбраны случайно по схеме Бернулли, то очень велико. Промежуточные случаи между указанными двумя как раз и представляют аддитивно-комбинаторный интерес.
Кроме того, интересна сама по себе структура множеств . В частности, по состоянию на 2018 год нет общих критериев (кроме прямого перебора), позволяющих определить, представляется ли заданное множество в виде .
Связываемые характеристики множеств В таблице ниже представлены теоремы и неравенства аддитивной комбинаторики, связывающие различные характеристики подмножеств групп. Утверждение, указанное в ячейке, связывает характеристики, указанные в её строке и столбце. Приведены лишь некоторые, наиболее известные, из таких теорем.
Для краткости в заголовках используются следующие сокращения:
Плотность множества для конечной группы — это величина или закон её асимптотического роста с ростом размера , а для бесконечных — асимптотическая плотность (или закон распределения) в , ОАП (от «обобщённая арифметическая прогрессия») — присутствие во множестве больших арифметических прогрессий, нетривиальных обобщённых арифметических прогрессий или их больших частей, а также, наоборот, возможность покрыть множество (или большую его часть) не слишком большой арифметической прогрессией; — размер и строение множества сумм (а также разностей и комбинаций сумм и разностей) — в частности, возможность представить любой элемент группы как сумму заданного количества элементов данного множества; — представимость множества или большой его части как множества сумм (а также разностей и комбинаций сумм и разностей) чисел из небольшого числа множеств, то есть разрешимость уравнения множеств для заданного , возможно, даже при определённых условиях на (например, ), где означает сумму Минковского коэффициенты Фурье имеются в виду для характеристической функции множества и функций, определяемых через неё, а также их статистика — разного рода нормы, количество элементов с большим значением и структура их множества; ЧРУ (от «число решений уравнения») — число решений различных линейных уравнений (в частности, аддитивная энергия) или систем уравнений, в которых переменные принимают значения из заданных множеств, а также соотношение количества их решений
Также в ячейках используется несколько специфических обозначений:
— коэффициент Фурье характеристической функции множества ; — аддитивная энергия — такая функция называется балансовой функцией множества , поскольку .
+ Плотность ОАП Коэффициенты Фурье ЧРУ Плотность ОАП Теорема Семереди Неравенство Шнирельмана, при больших и содержат длинную а. п. Неравенство Плюннеке — Ружа Коэффициенты Фурье Принцип неопределённости Если , мало, то содержит а. п. длины 3 Если и малы, то велико ЧРУ Теорема Рота Если - а. п., то Из соотношений аддитивных энергий можно сделать выводы о структуре множестваОбщеинститутский семинар «Математика и её приложения» Математического института им. В. А. Стеклова РАН, 18.09.14, И. Д. Шкредов, "Структурные теоремы в аддитивной комбинаторике" Если , то
Некоторые используемые понятия — обобщение понятия коэффициентов Фурье, придуманное Уильямом Гауэрсом в ходе доказательства теоремы Семереди.
Изоморфизм Фреймана — это отображение из подмножества одной группы в подмножество другой, сохраняющее отношение равенства сумм заданного количества элементов множества.
Конечное множество вещественных чисел называется выпуклой последовательностью (или выпуклым множеством) если для , то есть если является образом отрезка для некоторой строго выпуклой функции. Свойства таких множеств широко изучаются в аддитивной комбинаторике. Это понятие не стоит путать с выпуклым множеством в обычном смысле.
Множество Бора — структура с малым удвоением, используемая иногда в доказательствах как ослабленный аналог понятия подпространства.. Определяется как множество элементов поля, на которых все аддитивные характеры из заданного семейства имеют малое значение. Множества Бора содержат в себе большие обобщённые арифметические прогрессии, так что наличие во множестве прогрессий иногда доказывается через наличие в нём нужного множества Бора.
Почти периодичная функции — функция такая, что норма достаточно мала для некоторого и для всех , где — некоторое множество (например, множество Бора). На таких множествах построено одно из доказательств теоремы Рота.
Множество больших тригонометрических сумм (иногда называется также спектром) множества — это множество вычетов , для которых сумма (коэффициент Фурье) имеет большой модуль.
Диссоциативным множеством называется множество, для которого линейные комбинации равны нулю, где , только когда все равны нулю.