Теорема сумм-произведений

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

Формулировка

Пусть $A\subset 𝔽$ — подмножество некоторого кольца $𝔽$ (обычно $𝔽$ является полем, но формально можно рассматривать и кольцо) с операциями $+$ и $\cdot$. Рассматриваются два производных от $A$ множества:

$A+A=\left\{a_1+a_2:a_1,a_2\in A\right\}$

$A\times A=\left\{a_1\cdot a_2:a_1,a_2\in A\right\}$

Если множество $A$ структурировано относительно сложения (например, в нём много арифметических прогрессий, или обобщённых арифметических прогрессий, или их больших кусков), то множество $A+A$ будет относительно невелико — ведь суммы многих пар элементов совпадут.

Если же $A$ структурировано относительно умножения, то не очень большим будет множество $A\times A$, по аналогичным причинам.

Теорема утверждает, что хотя бы одно из множеств $A+A$ и $A\times A$ очень велико относительно $A$, то есть относительно хотя бы одной из операций структура будет нерегулярна.

Конкретнее, теорема устанавливает степенной рост размера большего из производных множеств относительно размера исходного:

Шаблон:Рамка Теорема

Для некоторой константы $\delta =\delta (𝔽)>0$ и произвольного множества $A\subset 𝔽$ (для конечного $𝔽$ — с ограничениями на размер) верно, что

$\max \left\{|A+A|,|A\times A|\right\}>|A{|}^{1+\delta }$

Для разных колец удаётся получить оценки с разными $\delta$. Также для некоторых (особенно для конечных) колец возможно добавление условий на размер множества $A$, при которых выполняется теорема для данного $\delta$.

Крайние случаи

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

• few sums, many product (FSMP): если $|A+A|\ll |A|$, то $|AA|\ge |A{|}^{2-o(1)}$
• few products, many sums (FPMS): если $|AA|\ll |A|$, то $|A+A|\ge |A{|}^{2-o(1)}$

Примеры

Классическими примерами для иллюстрации теоремы сумм-произведений являются арифметическая прогрессия $A=\left\{1,\dots ,n\right\}$ и геометрическая прогрессия $B=\left\{1,2,4,\dots ,2^{n-1}\right\}$.

Арифметическая прогрессия максимально упорядочена относительно сложения, так что $|A+A|<2|A|$, однако из её чисел можно составить много разных произведений, так что $|A\times A|=\mathrm{\Omega }\left(\frac{|A{|}^2}{\log |A|}\right)$, так что относительно умножения она совершенно неупорядоченна.

Точно так же для геометрической прогрессии выполнено $|B\times B|<2|B|$, но очевидно (если рассмотреть двоичное представление чисел), что $|B+B|=\mathrm{\Omega }(|B{|}^2)$.

Результаты

Для вещественных чисел

При $𝔽=ℝ$ теорема сумм-произведений иногда называется также теоремой Эрдёша-Семереди, поскольку именно они в 1983 году подняли вопрос рассмотрения соотношения количеств сумм и произведений. В той же работе они выдвинули гипотезу о том, что величина $\epsilon$ может быть сколь угодно близка к единице (то есть $\max \left\{|A+A|,|A\times A|\right\}>|A{|}^{2-o(1)}$). Однако В той же статье они выдвинули ещё несколько гипотез, в частности, аналогичную для $k$ слагаемых и множеств: $\max \left\{|A+\dots +A|,|A\times \dots \times A|\right\}>|A{|}^{k-o(1)}$.

Хронология улучшения $\delta$ в оценке $\max \{|A+A|,|AA|\}\ge |A{|}^{1+\delta -o(1)},A\subset ℝ$
Год	Значение $\delta$	Автор(ы)
1983	$1/31$(*)(**)	Эрдёш, Семереди $1+\delta$ вместо $1+\delta -o(1)$
1998	$1/15$(*)(**)	Шаблон:IwШаблон:Sfn
1997	$1/4$(**)	Шаблон:IwШаблон:Sfn
2005	$3/11$	Шаблон:IwШаблон:Sfn
2009	$1/3$	ШоймошиШаблон:Sfn
2015	$\frac{1}{3}+\frac{1}{20598}\approx 0.333381...$	Конягин, ШкредовШаблон:Sfn
2016	$\frac{1}{3}+\frac{5}{9813}\approx 0.333842...$	Конягин, ШкредовШаблон:Sfn
2016	$\frac{1}{3}+\frac{1}{1509}\approx 0.333996...$	Руднев, Шкредов, СтивенсШаблон:Sfn
2019	$\frac{1}{3}+\frac{5}{5277}\approx 0.334280...$	ШаканШаблон:Sfn
2020 (препринт)	$\frac{1}{3}+\frac{2}{1167}\approx 0.335047...$	Руднев, СтивенсШаблон:Sfn
(*) Только для $A\subset \mathbb{Z}$ (**) Верно и для степени $1+\delta$ вместо $1+\delta -o(1)$

Для полей вычетов по простому модулю

Теренс Тао в своей монографии отмечает, что задача о получении аналога результата Эрдёша и Семереди в полях ${𝔽}_p$ была поставлена в 1999 г. Т. Вольфом (в частной беседе) для подмножеств $A\subset {𝔽}_p$ мощности порядка $p^{1/2}$.

Задача сумм-произведений в ${𝔽}_p$ была решена в работах Бургейн, Глиббичука и Конягина и Бургейна, Каца и Тао. Они доказали следующую теорему

Шаблон:Рамка Для любого $\epsilon >0$ существует $\delta =\delta (\epsilon )>0$ такое, что если $A\subset {𝔽}_p$ и $|A|<p^{1-\epsilon }$, то выполняется оценка

$\max \left\{|A+A|,|A\times A|\right\}\ge |A{|}^{1+\delta }$

В условии теоремы требование $|A|<p^{1-\epsilon }$ является естественным, так как если $|A|$ имеет порядок близкий к $p$, то обе величины $|A+A|$ и $|A\times A|$ будут по порядку близки к $|A|$.Шаблон:Sfn

Для произвольных колец

Теренс Тао исследовал границы возможностей обобщения теоремы на произвольные кольца и, в частности, связь экстремальных случаев малых значений $|A+A|$ и $|A\cdot A|$ с количеством делителей нуля в множестве $A$ и близостью его структуры к подкольцу.

Методы доказательства

Для вещественных чисел

Первые доказательства

Доказательство Эрдёша и Семереди использовало тот факт, что при малых $|A+A|$ и $|A\times A|$ существует решение системы

$\{\begin{array}{c}{b}_1+b_3=b_2+b_4\\ b_1{b}_5=b_2{b}_6,\end{array}$

где $b_i$ принадлежат некоторым (разным) подмножествам $A$, а на само множество $A$ налагаются специальные условия. Используя такое утверждение как лемму, можно доказать теорему и для произвольного множества $A$.Шаблон:Sfn

Теорема Семереди — Троттера (Элекеш, 1997)

Если все элементы $a\in A$ имеют много представлений в виде $a=p_1{p}_2,p_1\in {\mathrm{\Pi }}_1,p_2\in {\mathrm{\Pi }}_2$ для некоторых небольших множеств ${\mathrm{\Pi }}_1{\mathrm{\Pi }}_2$, то для оценки числа решений уравнения

$a+b=c,a\in A,b\in B,c\in C.$

с любыми множествами $B,C$ можно использовать уравнение

$p_1{p}_2+b=c,p_1\in {\mathrm{\Pi }}_1,p_2\in {\mathrm{\Pi }}_2,b\in B,c\in C.$

С другой стороны, решения такого уравнения соответствуют инциденциям между прямыми, которые параметризуются парами $(p_1,b)$, и точками, которые параметризуются парами $(p_2,c)$. Поэтому для их оценки оказывается удобно использовать общие результаты об инциденциях, наилучший из которых — теорема Семереди — Троттера.

Именно это использовал Элекеш при доказательстве теоремы с показателем $\delta =\frac{1}{4}$.Шаблон:Sfn Неявно его доказательство можно разделить на два этапа:

• анализ уравнения $a+b=c,a\in A,b\in B,c\in C$ (тривиально, с помощью разложения ${\mathrm{\Pi }}_1:=AA,{\mathrm{\Pi }}_2:=1/A$)
• применение полученных оценок (тривиально, для $B:=A,C:=A+A$)

Такая декомпозиция важна для осмысления возникших позже методов.

Конструкция Шоймоши (Шоймоши, 2009)

Конструкция Шоймоши. Красные точки имеют координаты из $A\times A$.
Зелёные точки соответствуют суммам красных с соседних прямых. Все они гарантированно различны и принадлежат $(A+A)\times (A+A)$.
Количество линий с красными точками выражается через $|AA|$

Шоймоши использовал тот факт, что если $\frac{a}{b}<\frac{c}{d}$, то

$\frac{a}{b}<\frac{a+c}{b+d}<\frac{c}{d}.$

Из этого следует, что если $\frac{a_1}{b_1}<\frac{a_2}{b_2}<\frac{a_3}{b_3}$, то

$\frac{a_1+a_2}{b_1+b_2}<\frac{a_2+a_3}{b_2+b_3}.$

В то же время при фиксированных значениях $\lambda \in A/A,\mu \in A/A$ все пары $(a+c,b+d)$, образуемые представлениями

$\lambda =\frac{a}{b},\mu =\frac{c}{d},a,b,c,d\in A$

будут различны, поэтому, просуммировав их по «соседним» парам $(\lambda ,\mu )$, можно получить оценку на $|A+A|$ в терминах числа таких представлений. А оно, в свою очередь, выражается (опосредовано) через $|AA|$.

Наиболее наглядно эту идею можно выразить геометрически, как суммирование точек из $A\times A$, которые лежат на соседних прямых, исходящих из центра координат.

Разбиение конструкции Шоймоши (Конягин, Шкредов, 2015)

Разбиение конструкции Шоймоши по методу Конягина-Шкредова
Цвета линий, исходящих из центра координат, соответствуют блокам, в каждом из которых оценивается количество совпадений сумм.
Синие и фиолетовые линии обозначают суммируемые пары красных точек с одинаковыми суммами.

Если в конструкции Шоймоши убрать условие о том, что суммируемые точки должны принадлежать соседним прямым, то уже ничто не будет гарантировать, что все получающиеся суммы будут различны. Например, вообще все суммы точек из $A\times A$ могут быть различны только в экстремальном случае $|A+A|\gg |A{|}^2$, а он уже удовлетворяет гипотезе сумм-произведений.

Исходя из этого, Конягин и Шкредов оценили минимальное число совпадений таких сумм в промежуточном случае (когда $|A+A|$ и $|AA|$ равны нижней оценке, то есть $|A{|}^{4/3}$). Чтобы оценить число совпадений, они разбили все прямые на блоки из одинакового числа идущих подряд и оценивали число совпадений в каждом блоке для большинства из них. Используя эти оценки, они получили результат с $\delta >\frac{1}{3}$.

Нетривиальное мультипликативное разложение (Руднев, Стивенс, 2020)

Совпадения двух сумм точек, которые рассматривали Конягин и Шкредов, означают наличие решения системы уравнений

$\{\begin{array}{c}{\lambda }_1{a}_1+{\lambda }_2{a}_2={\lambda }_3{a}_3+{\lambda }_4{a}_4\\ a_1+a_2=a_3+a_4,\end{array}$

где $(a_i,{\lambda }_i{a}_i)\in A\times A$ и все ${\lambda }_i$ и пары $({\lambda }_1,{\lambda }_2),({\lambda }_3,{\lambda }_4)$ различны. Редуцируя систему по методу Гаусса (в одно действие), можно получить уравнение

$a_3=c_1{a}_1-c_2{a}_2$

с постоянными $c_1,c_2$ и теми же условиями на $a_1,a_2$. Руднев и Стивенс применили это для явного построения мультипликативного разложения большого подмножества $A$ с лучшими свойствами, чем у тривиального.

По аналогии с доказательством Элекеша, это позволяет разделить доказательство оценок с показателем $\delta =\frac{1}{3}+c$ на два этапа:

• применение нового мультипликативного разложения;
• нетривиальное применение уравнения $a-b=c$ для оценки $|A+A|$.

Использование старших энергий

Наиболее популярный путь использования уравнений для оценки $|A+A|$ — использование аддитивной энергии и её обобщений. Результаты применения теоремы Семереди-Троттера позволяют лучше всего анализировать уравнения вида

$E_3(A,D):=\{(a_1,a_2,a_3,d_1,d_2,d_3)\in A^3\times D^3:a_1-d_1=a_2-d_2=a_3-d_3\}$

для произвольного $D$. Руднев и Стивенс предложили метод использования такой аддитивной энергии с помощью рассмотрения уравнения

$d=(a+b)-(a+c)a,b,c\in A,d\in D,$

где $D$ соответствует множеству популярных (с большим количеством представлений) разностей, а $a+b$ принадлежит множеству популярных сумм. Кроме задачи сумм-произведений, разработка подобных методов актуальна для оценки сумм выпуклых последовательностей.

Существует похожий операторный метод, который менее эффективен для оценки $|A+A|$, но позволяет лучше изучать связь между $E(A)$ и $|AA|$.

Для простых полей

При доказательстве теоремы для $𝔽={𝔽}_p$ широко используются понятие аддитивной энергии, неравенство Плюннеке — Ружа и оценки Балога-Семереди-Гауэрса. Одно из возможных доказательств использует нижнюю оценку на размер множества $R(A)=A\left(\frac{A\times A-A\times A}{A-A}+A\right)$ и тот факт, что из верхних оценок на размеры $A+A$ и $A\times A$ следует противоречащая нижней верхняя оценка на размер $R(A)$.Шаблон:Sfn

Приложения

Бургейн, Глибичук и Конягин использовали частны случай теоремы при $𝔽={𝔽}_p$ для оценки полилинейных тригонометрических сумм. Это, в частности, позволило получить нетривиальные верхние оценки для сумм Гаусса $\left|\sum _{g\in G}{e}^{2\pi \frac{ag}{p}i}\right|=\left|\sum _{x=0}^{p-1}{e}^{2\pi \frac{a{x}^n}{p}i}\right|$ по малым мультипликативным подгруппам $G\subset {𝔽}_p^{*},|G|=\frac{p-1}{n}$.Шаблон:Sfn Бургейн, Кац и Тао, используя этот же случай, усилили оценку в проблеме Семереди-Троттера в ${𝔽}_p$, доказав, что для множества пар $I=\left\{(p,l):p\in l,p\in P,l\in L\right\}$ для множества $P$ точек из ${\left({𝔽}_p\right)}^2$ и прямых $L$ при $|P|=|L|=n$ выполняеся оценка $|I|\le n^{\frac{3}{2}-\epsilon }$ при некотором $\epsilon >0$.

В этой же работе они применили теорему для исследования множеств Какейи в многомерном пространстве $({𝔽}_p{)}^d$. Для размера такого множества ими была получена оценка $|S|>p^{\frac{d}{2}+1+10^{-10}}$.

Границы возможного улучшения гипотезы

В той же статье, где Эрдёш и Семереди выдвинули гипотезу о том, что $\max \left\{|A+A|,|A\times A|\right\}>c(\delta )|A{|}^{2-\delta }$ для $A\subset \mathbb{Z},\delta >0$, они предъявили и пример построения сколь угодно большого множества $A$, для которого $|A+A|+|A\times A|\le |A{|}^{2-\frac{c}{\log \log |A|}}$. В качестве такого множества выступало множество чисел, получаемых произведением не более чем $2\lfloor \frac{\log x}{6\log \log x}\rfloor$ простых чисел (не обязательно различных), каждое из которых не превышает $(\log x{)}^3$, где $x$ — произвольное достаточно большое число.Шаблон:Sfn

Обобщения

Для комбинации операций

Бургейн и Шаблон:Iw рассматривали оценки вида

$\max \{|\underset{k}{\underbrace{A+\dots +A}}|,|\underset{k}{\underbrace{A\times \dots \times A}}|\}\ge |A{|}^{b(k)}$

для произвольного $k$ и $b(k)\to \mathrm{\infty }$.Шаблон:Sfn

Во многих работах сложение и умножение соединяют в одном выражении: например, получают безусловные нижние оценки для $|AA+AA|$.

Для набора пар слагаемых/множителей

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

Шаблон:Рамка Пусть $G=(A,E)$ — граф, $E\subset A\times A$, $|A|=n$. Обозначим $c$ и $\delta$ через равенства

• $|E|=n^{1+c}$
• $\max \{|A{+}_{G}A|,|A{\cdot }_{G}A|\}=n^{1+\delta }$, где $A{+}_{G}A:=\{a+b:(a,b)\in E\}$, $A{\cdot }_{G}A:=\{ab:(a,b)\in E\}$

Как зависят друг от друга значения $c$ и $\delta$ при $|A|\to \mathrm{\infty }$? Шаблон:Конец рамки

В отличие от случая $G=A\times A$, здесь может не наблюдаться экстремального роста ни сумм, ни произведений: при $c<1$ возможна ситуация, когда $\delta <c$. Поэтому кроме нижних оказывается актуален вопрос верхних оценок на $\max \{|A+A|,|AA|\}$. Впрочем, нижние оценки тоже исследуются.

Для оценки энергий

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

Но у множества чисел вполне могут быть большими одновременно обе энергии, поскольку нижняя оценка может контролироваться вкладом отдельного подмножества. Например, если $E^{+}(A_1)\gg |A{|}^3,E^{\times }(A_2)\gg |A{|}^3$, то для множества $A=A_1\cup A_2$ верно, что

$\min \{E^{+}(A),E^{\times }(A)\}\ge \min \{E^{+}(A_1),E^{\times }(A_2)\}\gg |A{|}^3.$

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

Шаблон:Рамка Теорема Балога-Вули

Существует константа $\delta >0$ такая, что для любого множества $A\subset ℝ$ существует разбиение $A=B\bigsqcup C$ с условием

$E^{+}(B)\le |A{|}^{3-\delta },E^{\times }(C)\le |A{|}^{3-\delta }$

Наилучший вариант этой теоремы доказан для $\delta =\frac{7}{26}-o(1)$.Шаблон:Sfn Известно, что аналогичное не верно для $\delta >\frac{2}{3}$.

Для произвольных выпуклых функций

Умножение двух чисел можно представить как функцию от сложения их логарифмов: $ab=\exp (\log a+\log b)$. Поэлементное применение строго возрастающей функции ко множеству не меняет его размера, поэтому

$|AA|=|\exp (\log A+\log A)|=|\log A+\log A|$

и основную гипотезу сумм-произведений можно переформулировать как

$\max \{|A+A|,|\log A+\log A|\}\ge |A{|}^{2-o(1)}$

или (подставляя $A:=\log A$) как

$\max \{|\exp (A)+\exp (A)|,|A+A|\}\ge |A{|}^{2-o(1)}.$

Оказывается, что похожие оценки можно доказать для произвольной выпуклой функции вместо $\exp$.

Шаблон:Рамка Теорема

Если $A\subset ℝ$ — произвольное множество, $f:ℝ\to ℝ$ — произвольная строго выпуклая функция, то

$\max \{|A-A|,|f(A)+f(A)|\}\ge |A{|}^{14/11-o(1)}$

$\max \{|A+A|,|f(A)+f(A)|\}\ge |A{|}^{24/19-o(1)}$

Вопрос о том, верны ли такие же оценки с показателем $2-o(1)$ в правой части, остаётся открытым.

Аналогичные результаты получены и для большего числа слагаемых.

Литература

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья