Теорема сумм-произведений — теорема арифметической комбинаторики, устанавливающая неструктурированность любого достаточно большого множества относительно хотя бы одной из операций поля (сложения и умножения). В качестве показателя структурированности используются, соответственно, размеры множества сумм и множества произведений.
Формулировка Пусть — подмножество некоторого кольца (обычно является полем, но формально можно рассматривать и кольцо) с операциями и . Рассматриваются два производных от множества:
Если множество структурировано относительно сложения (например, в нём много арифметических прогрессий, или обобщённых арифметических прогрессий, или их больших кусков), то множество будет относительно невелико — ведь суммы многих пар элементов совпадут.
Если же структурировано относительно умножения, то не очень большим будет множество , по аналогичным причинам.
Теорема утверждает, что хотя бы одно из множеств и очень велико относительно , то есть относительно хотя бы одной из операций структура будет нерегулярна.
Конкретнее, теорема устанавливает степенной рост размера большего из производных множеств относительно размера исходного:
Теорема
Для некоторой константы и произвольного множества (для конечного — с ограничениями на размер) верно, что
Для разных колец удаётся получить оценки с разными . Также для некоторых (особенно для конечных) колец возможно добавление условий на размер множества , при которых выполняется теорема для данного .
Крайние случаи Наиболее удобными для изучения оказываются крайние случаи гипотезы:
few sums, many product (FSMP): если , то Решена в few products, many sums (FPMS): если , то В получены лучшие результаты, чем в общем случае
Примеры Классическими примерами для иллюстрации теоремы сумм-произведений являются арифметическая прогрессия и геометрическая прогрессия .
Арифметическая прогрессия максимально упорядочена относительно сложения, так что , однако из её чисел можно составить много разных произведений, так что , так что относительно умножения она совершенно неупорядоченна.
Точно так же для геометрической прогрессии выполнено , но очевидно (если рассмотреть двоичное представление чисел), что .
Результаты
Для вещественных чисел При теорема сумм-произведений иногда называется также теоремой Эрдёша-Семереди, поскольку именно они в 1983 году подняли вопрос рассмотрения соотношения количеств сумм и произведений. В той же работе они выдвинули гипотезу о том, что величина может быть сколь угодно близка к единице (то есть ). Однако В той же статье они выдвинули ещё несколько гипотез, в частности, аналогичную для слагаемых и множеств: .
Хронология улучшения в оценке Год Значение Автор(ы) 1983 (*)(**) Эрдёш, СемередиВ первой работе не уточнялось значение , а лишь доказвалось существование. Тем не менее, прямое следование рассуждениям той работы показывает, что она верна для . В явном виде это значение упомянуто позже в
вместо 1998 (*)(**) 1997 (**) 2005 2009 Шоймоши 2015 Конягин, Шкредов 2016 Конягин, Шкредов 2016 Руднев, Шкредов, Стивенс 2019 Шакан 2020(препринт) Руднев, Стивенс (*) Только для (**) Верно и для степени вместо
Для полей вычетов по простому модулю Теренс Тао в своей монографии отмечает, что задача о получении аналога результата Эрдёша и Семереди в полях была поставлена в 1999 г. Т. Вольфом (в частной беседе) для подмножеств мощности порядка .
Задача сумм-произведений в была решена в работах Бургейн, Глиббичука и Конягина и Бургейна, Каца и Тао. Они доказали следующую теорему
Для любого существует такое, что если и , то выполняется оценка
В условии теоремы требование является естественным, так как если имеет порядок близкий к , то обе величины и будут по порядку близки к .
Для произвольных колец Теренс Тао исследовал границы возможностей обобщения теоремы на произвольные кольца и, в частности, связь экстремальных случаев малых значений и с количеством делителей нуля в множестве и близостью его структуры к подкольцу..
Методы доказательства
Для вещественных чисел
Первые доказательства Доказательство Эрдёша и Семереди использовало тот факт, что при малых и существует решение системы
где принадлежат некоторым (разным) подмножествам , а на само множество налагаются специальные условия. Используя такое утверждение как лемму, можно доказать теорему и для произвольного множества .
Теорема Семереди — Троттера (Элекеш, 1997)
Если все элементы имеют много представлений в виде для некоторых небольших множеств , то для оценки числа решений уравнения
с любыми множествами можно использовать уравнение
С другой стороны, решения такого уравнения соответствуют инциденциям между прямыми, которые параметризуются парами , и точками, которые параметризуются парами . Поэтому для их оценки оказывается удобно использовать общие результаты об инциденциях, наилучший из которых — теорема Семереди — Троттера.См. , лемма 3Похожим образом разложение можно использовать для анализа . См. , лемма 4.
Именно это использовал Элекеш при доказательстве теоремы с показателем . Неявно его доказательство можно разделить на два этапа:
анализ уравнения (тривиально, с помощью разложения ) применение полученных оценок (тривиально, для )
Такая декомпозиция важна для осмысления возникших позже методов.
Конструкция Шоймоши (Шоймоши, 2009)
Шоймоши использовал тот факт, что если , то
Из этого следует, что если , то
В то же время при фиксированных значениях все пары , образуемые представлениями
будут различны, поэтому, просуммировав их по «соседним» парам , можно получить оценку на в терминах числа таких представлений. А оно, в свою очередь, выражается (опосредовано) через .См. , формула (2).
Наиболее наглядно эту идею можно выразить геометрически, как суммирование точек из , которые лежат на соседних прямых, исходящих из центра координат.
Разбиение конструкции Шоймоши (Конягин, Шкредов, 2015)
Если в конструкции Шоймоши убрать условие о том, что суммируемые точки должны принадлежать соседним прямым, то уже ничто не будет гарантировать, что все получающиеся суммы будут различны. Например, вообще все суммы точек из могут быть различны только в экстремальном случае , а он уже удовлетворяет гипотезе сумм-произведений.
Исходя из этого, Конягин и Шкредов оценили минимальное число совпадений таких сумм в промежуточном случае (когда и равны нижней оценке, то есть ). Чтобы оценить число совпадений, они разбили все прямые на блоки из одинакового числа идущих подряд и оценивали число совпадений в каждом блоке для большинства из них. Используя эти оценки, они получили результат с .См. , доказательство леммы 10
Нетривиальное мультипликативное разложение (Руднев, Стивенс, 2020) Совпадения двух сумм точек, которые рассматривали Конягин и Шкредов, означают наличие решения системы уравнений
где и все и пары различны. Редуцируя систему по методу Гаусса (в одно действие), можно получить уравнение
с постоянными и теми же условиями на . Руднев и Стивенс применили это для явного построения мультипликативного разложения большого подмножества с лучшими свойствами, чем у тривиального.См. , с. 10 (после предложения 1)
По аналогии с доказательством Элекеша, это позволяет разделить доказательство оценок с показателем на два этапа:
применение нового мультипликативного разложения; нетривиальное применение уравнения для оценки .Если применять эти оценки тривиально, так же, как и у Элекеша, то результатом будет
Использование старших энергий Наиболее популярный путь использования уравнений для оценки — использование аддитивной энергии и её обобщений. Результаты применения теоремы Семереди-Троттера позволяют лучше всего анализировать уравнения вида
для произвольного . Руднев и Стивенс предложили метод использования такой аддитивной энергии с помощью рассмотрения уравнения
где соответствует множеству популярных (с большим количеством представлений) разностей, а принадлежит множеству популярных сумм. Кроме задачи сумм-произведений, разработка подобных методов актуальна для оценки сумм выпуклых последовательностей.См. , теорема 5, в особенности формулу (25)
Существует похожий операторный метод, который менее эффективен для оценки , но позволяет лучше изучать связь между и .См. , теорема 2
Для простых полей При доказательстве теоремы для широко используются понятие аддитивной энергии, неравенство Плюннеке — Ружа и оценки Балога-Семереди-Гауэрса. Одно из возможных доказательств использует нижнюю оценку на размер множества и тот факт, что из верхних оценок на размеры и следует противоречащая нижней верхняя оценка на размер .
Приложения Бургейн, Глибичук и Конягин использовали частны случай теоремы при для оценки полилинейных тригонометрических сумм. Это, в частности, позволило получить нетривиальные верхние оценки для сумм Гаусса по малым мультипликативным подгруппам . Бургейн, Кац и Тао, используя этот же случай, усилили оценку в проблеме Семереди-Троттера в , доказав, что для множества пар для множества точек из и прямых при выполняеся оценка при некотором . K. N. Bourgain, J. and T. Tao. A Sum-Product Estimate in Finite Fields, and Applications. GAFA, 14(1):27-57, 2004. arXiv: math/0301343
В этой же работе они применили теорему для исследования множеств Какейи в многомерном пространстве . Для размера такого множества ими была получена оценка .Mini course of additive combinatorics , заметки по лекциям Принстонского университета
Границы возможного улучшения гипотезы В той же статье, где Эрдёш и Семереди выдвинули гипотезу о том, что для , они предъявили и пример построения сколь угодно большого множества , для которого . В качестве такого множества выступало множество чисел, получаемых произведением не более чем простых чисел (не обязательно различных), каждое из которых не превышает , где — произвольное достаточно большое число.
Обобщения
Для комбинации операций Бургейн и рассматривали оценки вида
для произвольного и .
Во многих работах сложение и умножение соединяют в одном выражении: например, получают безусловные нижние оценки для ., теорема 2
Для набора пар слагаемых/множителей Одно из обобщений гипотезы — вопрос о суммах и произведениях, соответствующие рёбрам произвольного графа на элементах множества.
Пусть — граф, , . Обозначим и через равенства
, где ,
Как зависят друг от друга значения и при ?
В отличие от случая , здесь может не наблюдаться экстремального роста ни сумм, ни произведений: при возможна ситуация, когда , теорема 3. Поэтому кроме нижних оказывается актуален вопрос верхних оценок на . Впрочем, нижние оценки тоже исследуются., следствие 4, теорема 3
Для оценки энергий Нижние оценки на размер множества сумм легко выводить из верхних оценок на аддитивную энергию, поэтому гипотезу о первых естественно обобщить до гипотезы о вторых, используя аналогичное понятие мультипликативной энергии.
Но у множества чисел вполне могут быть большими одновременно обе энергии, поскольку нижняя оценка может контролироваться вкладом отдельного подмножества. Например, если , то для множества верно, что
Поэтому при формулировке соответствующей теоремы об энергиях используется соотношение энергий разных подмножеств.
Теорема Балога-Вули
Существует константа такая, что для любого множества существует разбиение с условием
Наилучший вариант этой теоремы доказан для . Известно, что аналогичное не верно для ., теорема 1.2
Для произвольных выпуклых функций Умножение двух чисел можно представить как функцию от сложения их логарифмов: . Поэлементное применение строго возрастающей функции ко множеству не меняет его размера, поэтому
и основную гипотезу сумм-произведений можно переформулировать как
или (подставляя ) как
Оказывается, что похожие оценки можно доказать для произвольной выпуклой функции вместо .
Теорема, теоремы 1.1, 1.2
Если — произвольное множество, — произвольная строго выпуклая функция, то
Вопрос о том, верны ли такие же оценки с показателем в правой части, остаётся открытым.
Аналогичные результаты получены и для большего числа слагаемых., теорема 1.4
Литература