Русская Википедия:Теорема сумм-произведений
Теорема сумм-произведений — теорема арифметической комбинаторики, устанавливающая неструктурированность любого достаточно большого множества относительно хотя бы одной из операций поля (сложения и умножения). В качестве показателя структурированности используются, соответственно, размеры множества сумм и множества произведений.
Формулировка
Пусть <math>A \subset {\mathbb F}</math> — подмножество некоторого кольца <math>{\mathbb F}</math> (обычно <math>{\mathbb F}</math> является полем, но формально можно рассматривать и кольцо) с операциями <math>+</math> и <math>\cdot</math>. Рассматриваются два производных от <math>A</math> множества:
- <math>A+A = \left\lbrace{a_1 + a_2 : a_1, a_2 \in A}\right\rbrace</math>
- <math>A \times A = \left\lbrace{a_1 \cdot a_2 : a_1, a_2 \in A}\right\rbrace</math>
Если множество <math>A</math> структурировано относительно сложения (например, в нём много арифметических прогрессий, или обобщённых арифметических прогрессий, или их больших кусков), то множество <math>A+A</math> будет относительно невелико — ведь суммы многих пар элементов совпадут.
Если же <math>A</math> структурировано относительно умножения, то не очень большим будет множество <math>A \times A</math>, по аналогичным причинам.
Теорема утверждает, что хотя бы одно из множеств <math>A+A</math> и <math>A \times A</math> очень велико относительно <math>A</math>, то есть относительно хотя бы одной из операций структура будет нерегулярна.
Конкретнее, теорема устанавливает степенной рост размера большего из производных множеств относительно размера исходного:
Шаблон:Рамка Теорема
Для некоторой константы <math>\delta = \delta({\mathbb F}) > 0</math> и произвольного множества <math>A \subset {\mathbb F}</math> (для конечного <math>{\mathbb F}</math> — с ограничениями на размер) верно, что
- <math>\max \left\lbrace{|A+A|,|A \times A|}\right\rbrace > |A|^{1 + \delta}</math>
Для разных колец удаётся получить оценки с разными <math>\delta</math>. Также для некоторых (особенно для конечных) колец возможно добавление условий на размер множества <math>A</math>, при которых выполняется теорема для данного <math>\delta</math>.
Крайние случаи
Наиболее удобными для изучения оказываются крайние случаи гипотезы:
- few sums, many product (FSMP): если <math>|A+A| \ll |A|</math>, то <math>|AA| \ge |A|^{2-o(1)}</math>[1]
- few products, many sums (FPMS): если <math>|AA| \ll |A|</math>, то <math>|A+A| \ge |A|^{2-o(1)}</math>[2]
Примеры
Классическими примерами для иллюстрации теоремы сумм-произведений являются арифметическая прогрессия <math>A=\left\lbrace{1,\dots,n}\right\rbrace</math> и геометрическая прогрессия <math>B=\left\lbrace{1,2,4,\dots,2^{n-1}}\right\rbrace</math>.
Арифметическая прогрессия максимально упорядочена относительно сложения, так что <math>|A+A| < 2 |A|</math>, однако из её чисел можно составить много разных произведений, так что <math>|A \times A| = \Omega \left({\frac{|A|^2}{\log |A|}}\right)</math>[3], так что относительно умножения она совершенно неупорядоченна.
Точно так же для геометрической прогрессии выполнено <math>|B \times B| < 2 |B|</math>, но очевидно (если рассмотреть двоичное представление чисел), что <math>|B+B| = \Omega(|B|^2)</math>.
Результаты
Для вещественных чисел
При <math>Шаблон:\mathbb F = Шаблон:\mathbb R</math> теорема сумм-произведений иногда называется также теоремой Эрдёша-Семереди, поскольку именно они в 1983 году подняли вопрос рассмотрения соотношения количеств сумм и произведений. В той же работе они выдвинули гипотезу о том, что величина <math>\varepsilon</math> может быть сколь угодно близка к единице (то есть <math>\max \left\lbrace{|A+A|,|A \times A|}\right\rbrace > |A|^{2 - o(1)}</math>). Однако В той же статье они выдвинули ещё несколько гипотез, в частности, аналогичную для <math>k</math> слагаемых и множеств: <math>\max \left\lbrace{|A+\dots+A|,|A \times \dots \times A|}\right\rbrace > |A|^{k - o(1)}</math>.
| Хронология улучшения <math>\delta</math> в оценке <math>\max \{ |A+A|, |AA| \} \ge |A|^{1 + \delta - o(1)},\ A \subset {\mathbb R}</math> | ||
|---|---|---|
| Год | Значение <math>\delta</math> | Автор(ы) |
| 1983 | <math>1/31</math>(*)(**) | Эрдёш, Семереди[4]
<math>1 + \delta</math> вместо <math>1 + \delta - o(1)</math> |
| 1998 | <math>1/15</math>(*)(**) | Шаблон:IwШаблон:Sfn |
| 1997 | <math>1/4</math>(**) | Шаблон:IwШаблон:Sfn |
| 2005 | <math>3/11</math> | Шаблон:IwШаблон:Sfn |
| 2009 | <math>1/3</math> | ШоймошиШаблон:Sfn |
| 2015 | <math>\frac{1}{3}+\frac{1}{20598} \approx 0.333381...</math> | Конягин, ШкредовШаблон:Sfn |
| 2016 | <math>\frac{1}{3}+\frac{5}{9813} \approx 0.333842...</math> | Конягин, ШкредовШаблон:Sfn |
| 2016 | <math>\frac{1}{3}+\frac{1}{1509} \approx 0.333996...</math> | Руднев, Шкредов, СтивенсШаблон:Sfn |
| 2019 | <math>\frac{1}{3}+\frac{5}{5277} \approx 0.334280...</math> | ШаканШаблон:Sfn |
| 2020 (препринт) |
<math>\frac{1}{3}+\frac{2}{1167} \approx 0.335047...</math> | Руднев, СтивенсШаблон:Sfn |
| (*) Только для <math>A \subset {\mathbb Z}</math> (**) Верно и для степени <math>1 + \delta</math> вместо <math>1 + \delta - o(1)</math> | ||
Для полей вычетов по простому модулю
Теренс Тао в своей монографии отмечает, что задача о получении аналога результата Эрдёша и Семереди в полях <math>{\mathbb F}_p</math> была поставлена в 1999 г. Т. Вольфом (в частной беседе) для подмножеств <math>A \subset {\mathbb F}_p</math> мощности порядка <math>p^{1/2}</math>.
Задача сумм-произведений в <math>{\mathbb F}_p</math> была решена в работах Бургейн, Глиббичука и Конягина и Бургейна, Каца и Тао. Они доказали следующую теорему
Шаблон:Рамка Для любого <math>\varepsilon > 0</math> существует <math>\delta = \delta(\varepsilon) > 0</math> такое, что если <math>A \subset {\mathbb F}_p</math> и <math>|A| < p^{1-\varepsilon}</math>, то выполняется оценка
- <math>\max \left\lbrace{|A+A|, |A \times A|}\right\rbrace \ge |A|^{1+\delta}</math>
В условии теоремы требование <math>|A| < p^{1 - \varepsilon}</math> является естественным, так как если <math>|A|</math> имеет порядок близкий к <math>p</math>, то обе величины <math>|A+A|</math> и <math>|A \times A|</math> будут по порядку близки к <math>|A|</math>.Шаблон:Sfn
Для произвольных колец
Теренс Тао исследовал границы возможностей обобщения теоремы на произвольные кольца и, в частности, связь экстремальных случаев малых значений <math>|A+A|</math> и <math>|A \cdot A|</math> с количеством делителей нуля в множестве <math>A</math> и близостью его структуры к подкольцу.[5]
Методы доказательства
Для вещественных чисел
Первые доказательства
Доказательство Эрдёша и Семереди использовало тот факт, что при малых <math>|A + A|</math> и <math>|A \times A|</math> существует решение системы
- <math>\begin{cases} b_1 + b_3 = b_2 + b_4 \\ b_1 b_5 = b_2 b_6\ , \end{cases}</math>
где <math>b_i</math> принадлежат некоторым (разным) подмножествам <math>A</math>, а на само множество <math>A</math> налагаются специальные условия. Используя такое утверждение как лемму, можно доказать теорему и для произвольного множества <math>A</math>.Шаблон:Sfn
Теорема Семереди — Троттера (Элекеш, 1997)
Если все элементы <math>a \in A</math> имеют много представлений в виде <math>a = p_1 p_2,\ p_1 \in \Pi_1,\ p_2 \in \Pi_2</math> для некоторых небольших множеств <math>\Pi_1 \Pi_2</math>, то для оценки числа решений уравнения
- <math>a+b=c,\ a \in A,\ b \in B,\ c \in C\ .</math>
с любыми множествами <math>B, C</math> можно использовать уравнение
- <math>p_1 p_2 + b = c,\ p_1 \in \Pi_1,\ p_2 \in \Pi_2,\ b \in B,\ c \in C\ .</math>
С другой стороны, решения такого уравнения соответствуют инциденциям между прямыми, которые параметризуются парами <math>(p_1, b)</math>, и точками, которые параметризуются парами <math>(p_2, c)</math>. Поэтому для их оценки оказывается удобно использовать общие результаты об инциденциях, наилучший из которых — теорема Семереди — Троттера.[6][7]
Именно это использовал Элекеш при доказательстве теоремы с показателем <math>\delta=\frac{1}{4}</math>.Шаблон:Sfn Неявно его доказательство можно разделить на два этапа:
- анализ уравнения <math>a+b=c,\ a \in A, b \in B, c \in C</math> (тривиально, с помощью разложения <math>\Pi_1:=AA,\ \Pi_2:=1/A</math>)
- применение полученных оценок (тривиально, для <math>B:=A,\ C:=A+A</math>)
Такая декомпозиция важна для осмысления возникших позже методов.
Конструкция Шоймоши (Шоймоши, 2009)
Шоймоши использовал тот факт, что если <math>\frac{a}{b} < \frac{c}{d}</math>, то
- <math>\frac{a}{b} < \frac{a+c}{b+d} < \frac{c}{d}\ .</math>
Из этого следует, что если <math>\frac{a_1}{b_1} < \frac{a_2}{b_2} < \frac{a_3}{b_3}</math>, то
- <math>\frac{a_1+a_2}{b_1+b_2} < \frac{a_2+a_3}{b_2+b_3}\ .</math>
В то же время при фиксированных значениях <math>\lambda \in A/A,\ \mu \in A/A</math> все пары <math>(a+c, b+d)</math>, образуемые представлениями
- <math>\lambda = \frac{a}{b},\ \mu = \frac{c}{d},\ a,b,c,d \in A</math>
будут различны, поэтому, просуммировав их по «соседним» парам <math>(\lambda, \mu)</math>, можно получить оценку на <math>|A+A|</math> в терминах числа таких представлений. А оно, в свою очередь, выражается (опосредовано) через <math>|AA|</math>.[8]
Наиболее наглядно эту идею можно выразить геометрически, как суммирование точек из <math>A \times A</math>, которые лежат на соседних прямых, исходящих из центра координат.
Разбиение конструкции Шоймоши (Конягин, Шкредов, 2015)
Цвета линий, исходящих из центра координат, соответствуют блокам, в каждом из которых оценивается количество совпадений сумм.
Синие и фиолетовые линии обозначают суммируемые пары красных точек с одинаковыми суммами.
Если в конструкции Шоймоши убрать условие о том, что суммируемые точки должны принадлежать соседним прямым, то уже ничто не будет гарантировать, что все получающиеся суммы будут различны. Например, вообще все суммы точек из <math>A \times A</math> могут быть различны только в экстремальном случае <math>|A+A| \gg |A|^2</math>, а он уже удовлетворяет гипотезе сумм-произведений.
Исходя из этого, Конягин и Шкредов оценили минимальное число совпадений таких сумм в промежуточном случае (когда <math>|A+A|</math> и <math>|AA|</math> равны нижней оценке, то есть <math>|A|^{4/3}</math>). Чтобы оценить число совпадений, они разбили все прямые на блоки из одинакового числа идущих подряд и оценивали число совпадений в каждом блоке для большинства из них. Используя эти оценки, они получили результат с <math>\delta > \frac{1}{3}</math>.[9]
Нетривиальное мультипликативное разложение (Руднев, Стивенс, 2020)
Совпадения двух сумм точек, которые рассматривали Конягин и Шкредов, означают наличие решения системы уравнений
- <math>\begin{cases} \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{cases}</math>
где <math>(a_i, \lambda_i a_i) \in A \times A</math> и все <math>\lambda_i</math> и пары <math>(\lambda_1, \lambda_2), (\lambda_3, \lambda_4)</math> различны. Редуцируя систему по методу Гаусса (в одно действие), можно получить уравнение
- <math>a_3 = c_1 a_1 - c_2 a_2</math>
с постоянными <math>c_1, c_2</math> и теми же условиями на <math>a_1, a_2</math>. Руднев и Стивенс применили это для явного построения мультипликативного разложения большого подмножества <math>A</math> с лучшими свойствами, чем у тривиального.[10]
По аналогии с доказательством Элекеша, это позволяет разделить доказательство оценок с показателем <math>\delta = \frac{1}{3} + c</math> на два этапа:
- применение нового мультипликативного разложения;
- нетривиальное применение уравнения <math>a-b=c</math> для оценки <math>|A+A|</math>.[11]
Использование старших энергий
Наиболее популярный путь использования уравнений для оценки <math>|A+A|</math> — использование аддитивной энергии и её обобщений. Результаты применения теоремы Семереди-Троттера позволяют лучше всего анализировать уравнения вида
- <math>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 \}</math>
для произвольного <math>D</math>. Руднев и Стивенс предложили метод использования такой аддитивной энергии с помощью рассмотрения уравнения
- <math>d = (a+b) - (a+c)\,\ a,b,c \in A,\ d \in D\ ,</math>
где <math>D</math> соответствует множеству популярных (с большим количеством представлений) разностей, а <math>a+b</math> принадлежит множеству популярных сумм. Кроме задачи сумм-произведений, разработка подобных методов актуальна для оценки сумм выпуклых последовательностей.[12]
Существует похожий операторный метод, который менее эффективен для оценки <math>|A+A|</math>, но позволяет лучше изучать связь между <math>E(A)</math> и <math>|AA|</math>.[13]
Для простых полей
При доказательстве теоремы для <math>{\mathbb F} = {\mathbb F}_p</math> широко используются понятие аддитивной энергии, неравенство Плюннеке — Ружа и оценки Балога-Семереди-Гауэрса. Одно из возможных доказательств использует нижнюю оценку на размер множества <math>R(A) = A \left({\frac{A \times A - A \times A}{A - A} + A}\right)</math> и тот факт, что из верхних оценок на размеры <math>A+A</math> и <math>A \times A</math> следует противоречащая нижней верхняя оценка на размер <math>R(A)</math>.Шаблон:Sfn[14]
Приложения
Бургейн, Глибичук и Конягин[15] использовали частны случай теоремы при <math>{\mathbb F} = {\mathbb F}_p</math> для оценки полилинейных тригонометрических сумм. Это, в частности, позволило получить нетривиальные верхние оценки для сумм Гаусса <math>\Bigg\vert{\sum \limits_{g \in G} {e^{2 \pi \frac{a g}{p} i}}}\Bigg\vert = \Bigg\vert{\sum \limits_{x=0}^{p-1} {e^{2 \pi \frac{a x^n}{p} i}}}\Bigg\vert</math> по малым мультипликативным подгруппам <math>G \subset {\mathbb F}_p^{*},\ |G|=\frac{p-1}{n}</math>.Шаблон:Sfn Бургейн, Кац и Тао, используя этот же случай, усилили оценку в проблеме Семереди-Троттера в <math>Шаблон:\mathbb F_p</math>, доказав, что для множества пар <math>I = \left\lbrace{(p,l) : p \in l, p \in P, l \in L}\right\rbrace</math> для множества <math>P</math> точек из <math>\left({Шаблон:\mathbb F_p}\right)^2</math> и прямых <math>L</math> при <math>|P|=|L|=n</math> выполняеся оценка <math>|I| \le n^{\frac{3}{2}-\varepsilon}</math> при некотором <math>\varepsilon > 0</math>. [16]
В этой же работе они применили теорему для исследования множеств Какейи в многомерном пространстве <math>({\mathbb F}_p)^d</math>. Для размера такого множества ими была получена оценка <math>|S| > p^{\frac{d}{2}+1+10^{-10}}</math>.[14][16]
Границы возможного улучшения гипотезы
В той же статье, где Эрдёш и Семереди выдвинули гипотезу о том, что <math>\max \left\lbrace{|A+A|,|A \times A|}\right\rbrace > c(\delta) |A|^{2 - \delta}</math> для <math>A \subset {\mathbb Z},\ \delta > 0</math>, они предъявили и пример построения сколь угодно большого множества <math>A</math>, для которого <math>|A+A| + |A \times A| \le |A|^{2 - \frac{c}{\log \log |A|}}</math>. В качестве такого множества выступало множество чисел, получаемых произведением не более чем <math>2 \left\lfloor{\frac{\log x}{6 \log \log x}}\right\rfloor</math> простых чисел (не обязательно различных), каждое из которых не превышает <math>(\log x)^3</math>, где <math>x</math> — произвольное достаточно большое число.Шаблон:Sfn
Обобщения
Для комбинации операций
Бургейн и Шаблон:Iw рассматривали оценки вида
- <math>\max \{ |\underbrace{A + \dots + A}_{k}|, |\underbrace{A \times \dots \times A}_{k}| \} \ge |A|^{b(k)}</math>
для произвольного <math>k</math> и <math>b(k) \to \infty</math>.Шаблон:Sfn
Во многих работах сложение и умножение соединяют в одном выражении: например, получают безусловные нижние оценки для <math>|AA+AA|</math>.[17]
Для набора пар слагаемых/множителей
Одно из обобщений гипотезы — вопрос о суммах и произведениях, соответствующие рёбрам произвольного графа на элементах множества.
Шаблон:Рамка Пусть <math>G=(A, E)</math> — граф, <math>E \subset A \times A</math>, <math>|A|=n</math>. Обозначим <math>c</math> и <math>\delta</math> через равенства
- <math>|E| = n^{1+c}</math>
- <math>\max \{ |A +_G A|, |A \cdot_G A| \} = n^{1 + \delta}</math>, где <math>A +_G A := \{ a + b : (a, b) \in E \}</math>, <math>A \cdot_G A := \{ ab : (a, b) \in E \}</math>
Как зависят друг от друга значения <math>c</math> и <math>\delta</math> при <math>|A| \to \infty</math>? Шаблон:Конец рамки
В отличие от случая <math>G = A \times A</math>, здесь может не наблюдаться экстремального роста ни сумм, ни произведений: при <math>c < 1</math> возможна ситуация, когда <math>\delta < c</math>[18]. Поэтому кроме нижних оказывается актуален вопрос верхних оценок на <math>\max \{ |A+A|, |AA| \}</math>. Впрочем, нижние оценки тоже исследуются.[19][20]
Для оценки энергий
Нижние оценки на размер множества сумм легко выводить из верхних оценок на аддитивную энергию, поэтому гипотезу о первых естественно обобщить до гипотезы о вторых, используя аналогичное понятие мультипликативной энергии.
Но у множества чисел вполне могут быть большими одновременно обе энергии, поскольку нижняя оценка может контролироваться вкладом отдельного подмножества. Например, если <math>E^+(A_1) \gg |A|^3, E^{\times}(A_2) \gg |A|^3</math>, то для множества <math>A = A_1 \cup A_2</math> верно, что
- <math>\min \{ E^+(A), E^\times(A) \} \ge \min \{ E^+(A_1), E^\times(A_2) \} \gg |A|^3\ .</math>
Поэтому при формулировке соответствующей теоремы об энергиях используется соотношение энергий разных подмножеств.
Шаблон:Рамка Теорема Балога-Вули
Существует константа <math>\delta > 0</math> такая, что для любого множества <math>A \subset {\mathbb R}</math> существует разбиение <math>A = B \sqcup C</math> с условием
- <math>E^+(B) \le |A|^{3-\delta},\ E^\times(C) \le |A|^{3-\delta}</math>
Наилучший вариант этой теоремы доказан для <math>\delta = \frac{7}{26}-o(1)</math>.Шаблон:Sfn Известно, что аналогичное не верно для <math>\delta > \frac{2}{3}</math>.[21]
Для произвольных выпуклых функций
Умножение двух чисел можно представить как функцию от сложения их логарифмов: <math>ab = \exp(\log a + \log b)</math>. Поэлементное применение строго возрастающей функции ко множеству не меняет его размера, поэтому
- <math>|AA| = |\exp(\log A + \log A)| = |\log A + \log A|</math>
и основную гипотезу сумм-произведений можно переформулировать как
- <math>\max \{ |A+A|, |\log A + \log A| \} \ge |A|^{2-o(1)}</math>
или (подставляя <math>A:=\log A</math>) как
- <math>\max \{ |\exp(A)+\exp(A)|, |A + A| \} \ge |A|^{2-o(1)}\ .</math>
Оказывается, что похожие оценки можно доказать для произвольной выпуклой функции вместо <math>\exp</math>.
Шаблон:Рамка Теорема[22]
Если <math>A \subset {\mathbb R}</math> — произвольное множество, <math>f : {\mathbb R} \to {\mathbb R}</math> — произвольная строго выпуклая функция, то
- <math>\max \{ |A-A|, |f(A) + f(A)| \} \ge |A|^{14/11-o(1)}</math>
- <math>\max \{ |A+A|, |f(A) + f(A)| \} \ge |A|^{24/19-o(1)}</math>
Вопрос о том, верны ли такие же оценки с показателем <math>2-o(1)</math> в правой части, остаётся открытым.
Аналогичные результаты получены и для большего числа слагаемых.[23]
Литература
Примечания
- ↑ Решена в Шаблон:Sfn0
- ↑ В Шаблон:Sfn0 получены лучшие результаты, чем в общем случае
- ↑ Шаблон:Cite web
- ↑ В первой работе Шаблон:Sfn0 не уточнялось значение <math>\delta</math>, а лишь доказвалось существование. Тем не менее, прямое следование рассуждениям той работы показывает, что она верна для <math>\delta=1/31</math>. В явном виде это значение упомянуто позже в Шаблон:Sfn0
- ↑ Шаблон:Citation.
- ↑ См. Шаблон:Sfn0, лемма 3
- ↑ Похожим образом разложение <math>a = p_1 - p_2,\ p_1 \in \Pi_1,\ p_2 \in \Pi_2</math> можно использовать для анализа <math>E^{\times}(A)</math>. См. Шаблон:Sfn0, лемма 4.
- ↑ См. Шаблон:Sfn0, формула (2).
- ↑ См. Шаблон:Sfn0, доказательство леммы 10
- ↑ См. Шаблон:Sfn0, с. 10 (после предложения 1)
- ↑ Если применять эти оценки тривиально, так же, как и у Элекеша, то результатом будет <math>\delta=\frac{1}{3}</math>
- ↑ См. Шаблон:Sfn0, теорема 5, в особенности формулу (25)
- ↑ См. Шаблон:Sfn0, теорема 2
- ↑ 14,0 14,1 Mini course of additive combinatorics Шаблон:Wayback, заметки по лекциям Принстонского университета
- ↑ Шаблон:Cite web
- ↑ 16,0 16,1 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 Шаблон:Wayback
- ↑ Шаблон:Sfn0, теорема 2
- ↑ Шаблон:Sfn0, теорема 3
- ↑ Шаблон:Sfn0, следствие 4
- ↑ Шаблон:Sfn0, теорема 3
- ↑ Шаблон:Sfn0, теорема 1.2
- ↑ Шаблон:Sfn0, теоремы 1.1, 1.2
- ↑ Шаблон:Sfn0, теорема 1.4
