Множество сумм

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Иллюстрация определения множества сумм на примере нескольких 4-элементных множеств с разными размерами . Одинаковым цветом обозначены разные значения. В таблице первыми выделяются цветом значения с несколькими различными представлениями.

Множество сумм — концепт аддитивной комбинаторики, соответствующий сумме Минковского конечных множеств.

Определение

[править | править код]

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

Для одного множества его множеством сумм называют . Кратные суммы обозначаются сокращённо[1]

Связанные определения

[править | править код]

Аналогично определяются множество разностей, множество произведений, множество частных и тому подобные для любой операции. Например, множество произведений определяется так[2]:

Величину называют константой удвоения[3], а про множества, у которых она ограничена, говорят, что они имеют малое удвоение[4]. В связи с теоремой сумм-произведений часто рассматривают множества с малым мультипликативным удвоением, то есть для которых ограничена величина [5].

Мощность множества сумм связана с аддитивной энергией неравенством [6], поэтому последняя часто используется для её оценки.

Суммы одного множества

[править | править код]

Теорема Фреймана рассматривает размер как показатель структурированности множества (если константа удвоения ограничена, то структура похожа на обобщённую арифметическую прогрессию).[7][8]

Теорема сумм-произведений связывает размер множества сумм и множества произведений. Основная гипотеза гласит, что для .[9] Сочетание суммирования и произведения в одном выражении привело к возникновению арифметической комбинаторики.

Изучается влияние поэлементного применения выпуклой функции к суммируемым множествам на размер множества сумм. Для выпуклых последовательностей известны нижние оценки на и .[10] Более общо, для выпуклой функции и множества задачу оценки и некоторые похожие иногда рассматривают как обобщение теоремы сумм-произведений, поскольку и поэтому , а функция выпукла.[11]

Суммы нескольких множеств

[править | править код]

Неравенство Плюннеке — Ружа утверждает, что разрастание (увеличение размера относительно складываемых множеств) кратных сумм в среднем (относительно ) не сильно превышает разрастание .

Неравенство треугольника Ружа связывает размеры для любых множеств и показывает, что нормализованный размер разности множеств можно рассматривать как псевдометрику, отражающую близость структуры этих множеств.[12]

Один из фундаментальных вопросов аддитивной комбинаторики: какую структуру могут или должны иметь множества сумм. По состоянию на начало 2020 года не известно какого-либо нетривиально быстрого алгоритма, позволяющего определить, представимо ли заданное большое множество в виде или . Однако известны некоторые частные результаты о структуре множеств сумм.

Например, множества сумм вещественных чисел не могут иметь малого мультипликативного удвоения, то есть если , то для некоторого .[13] А в группе вычетов по простому модулю есть лишь множеств, представимых в виде .[14][15]

Известно, что если  — плотные множества натуральных чисел, то содержит длинные арифметические прогрессии.[16] Тем не менее, в известны примеры плотных множеств с сильной верхней оценкой на длину таких прогрессий.[17][18]

Литература

[править | править код]
  • Фрейман, Григорий Абелевич. Начала структурной теории множеств. — Типография "Татполиграф". — 1966.
  • G. Elekes, M. B. Nathanson, I. Z. Ruzsa. Convexity and Sumsets (англ.) // Journal of Number Theory. — 2000. — Vol. 83, iss. 2. — P. 194—201.

Примечания

[править | править код]
  1. Фрейман, 1966, с. 7-8
  2. Тао, Ву, 2006, с. 54, с. 92
  3. Тао, Ву, 2006, с. 57
  4. Тао, Ву, 2006, с. 240
  5. Тао, Ву, 2006, с. 188; Шкредов, 2013, § 5
  6. Согласно неравенству Коши — Буняковского, , где  — число представлений
  7. Фрейман, 1966.
  8. Этот вопрос часто называется обратной задачей аддитивной комбинаторики (см., например, Фрейман, 1966, раздел 1.8, с. 19)
  9. Erdős, Szemerédi, 1983; Shakan, 2019
  10. Shkredov, Schoen, 2011.
  11. Elekes, Nathanson, Ruzsa, 2000.
  12. Тао, Ву, 2006, с. 60
  13. Shkredov, Zhelezov, 2016, следствие 2
  14. Alon, Granville, Ubis, 2010.
  15. При том, что общее число множеств в этой группе, очевидно,
  16. Впервые это доказал Бургейн в Bourgain, 1990. Лучший на 2020 год результат получен в Green, 2002, а впоследствии передоказно новым, более общим, методом в Croot, Laba, Sisask, 2013
  17. Ruzsa, 1991.
  18. Обзор результатов на эту тему можно найти в статье (недоступная ссылка) Croot, Ruzsa, Schoen, 2007