Теорема сумм-произведений
Теорема сумм-произведений — теорема арифметической комбинаторики, устанавливающая неструктурированность любого достаточно большого множества относительно хотя бы одной из операций поля (сложения и умножения). В качестве показателя структурированности используются, соответственно, размеры множества сумм и множества произведений.
Формулировка
Пусть — подмножество некоторого кольца (обычно является полем, но формально можно рассматривать и кольцо) с операциями и . Рассматриваются два производных от множества:
Если множество структурировано относительно сложения (например, в нём много арифметических прогрессий, или обобщённых арифметических прогрессий, или их больших кусков), то множество будет относительно невелико — ведь суммы многих пар элементов совпадут.
Если же структурировано относительно умножения, то не очень большим будет множество , по аналогичным причинам.
Теорема утверждает, что хотя бы одно из множеств и очень велико относительно , то есть относительно хотя бы одной из операций структура будет нерегулярна.
Конкретнее, теорема устанавливает степенной рост размера большего из производных множеств относительно размера исходного:
Теорема Для некоторой константы и произвольного множества (для конечного — с ограничениями на размер) верно, что |
Для разных колец удаётся получить оценки с разными . Также для некоторых (особенно для конечных) колец возможно добавление условий на размер множества , при которых выполняется теорема для данного .
Крайние случаи
Наиболее удобными для изучения оказываются крайние случаи гипотезы:
- few sums, many product (FSMP): если , то [1]
- few products, many sums (FPMS): если , то [2]
Примеры
Классическими примерами для иллюстрации теоремы сумм-произведений являются арифметическая прогрессия и геометрическая прогрессия .
Арифметическая прогрессия максимально упорядочена относительно сложения, так что , однако из её чисел можно составить много разных произведений, так что [3], так что относительно умножения она совершенно неупорядоченна.
Точно так же для геометрической прогрессии выполнено , но очевидно (если рассмотреть двоичное представление чисел), что .
Результаты
Для вещественных чисел
При теорема сумм-произведений иногда называется также теоремой Эрдёша-Семереди, поскольку именно они в 1983 году подняли вопрос рассмотрения соотношения количеств сумм и произведений. В той же работе они выдвинули гипотезу о том, что величина может быть сколь угодно близка к единице (то есть ). Однако В той же статье они выдвинули ещё несколько гипотез, в частности, аналогичную для слагаемых и множеств: .
Хронология улучшения в оценке | ||
---|---|---|
Год | Значение | Автор(ы) |
1983 | (*)(**) | Эрдёш, Семереди[4]
вместо |
1998 | (*)(**) | Форд[англ.][5] |
1997 | (**) | Элекеш[англ.][6] |
2005 | Шоймоши[англ.][7] | |
2009 | Шоймоши[8] | |
2015 | Конягин, Шкредов[9] | |
2016 | Конягин, Шкредов[10] | |
2016 | Руднев, Шкредов, Стивенс[11] | |
2019 | Шакан[12] | |
2020 (препринт) |
Руднев, Стивенс[13] | |
(*) Только для (**) Верно и для степени вместо |
Для полей вычетов по простому модулю
Теренс Тао в своей монографии отмечает, что задача о получении аналога результата Эрдёша и Семереди в полях была поставлена в 1999 г. Т. Вольфом (в частной беседе) для подмножеств мощности порядка .
Задача сумм-произведений в была решена в работах Бургейн, Глиббичука и Конягина и Бургейна, Каца и Тао. Они доказали следующую теорему
Для любого существует такое, что если и , то выполняется оценка |
В условии теоремы требование является естественным, так как если имеет порядок близкий к , то обе величины и будут по порядку близки к .[14]
Для произвольных колец
Теренс Тао исследовал границы возможностей обобщения теоремы на произвольные кольца и, в частности, связь экстремальных случаев малых значений и с количеством делителей нуля в множестве и близостью его структуры к подкольцу.[15]
Методы доказательства
Для вещественных чисел
Первые доказательства
Доказательство Эрдёша и Семереди использовало тот факт, что при малых и существует решение системы
где принадлежат некоторым (разным) подмножествам , а на само множество налагаются специальные условия. Используя такое утверждение как лемму, можно доказать теорему и для произвольного множества .[16]
Теорема Семереди — Троттера (Элекеш, 1997)
Если все элементы имеют много представлений в виде для некоторых небольших множеств , то для оценки числа решений уравнения
с любыми множествами можно использовать уравнение
С другой стороны, решения такого уравнения соответствуют инциденциям между прямыми, которые параметризуются парами , и точками, которые параметризуются парами . Поэтому для их оценки оказывается удобно использовать общие результаты об инциденциях, наилучший из которых — теорема Семереди — Троттера.[17][18]
Именно это использовал Элекеш при доказательстве теоремы с показателем .[6] Неявно его доказательство можно разделить на два этапа:
- анализ уравнения (тривиально, с помощью разложения )
- применение полученных оценок (тривиально, для )
Такая декомпозиция важна для осмысления возникших позже методов.
Конструкция Шоймоши (Шоймоши, 2009)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/79/Sum-product-solymosi-construction.png/300px-Sum-product-solymosi-construction.png)
Зелёные точки соответствуют суммам красных с соседних прямых. Все они гарантированно различны и принадлежат .
Количество линий с красными точками выражается через
Шоймоши использовал тот факт, что если , то
Из этого следует, что если , то
В то же время при фиксированных значениях все пары , образуемые представлениями
будут различны, поэтому, просуммировав их по «соседним» парам , можно получить оценку на в терминах числа таких представлений. А оно, в свою очередь, выражается (опосредовано) через .[19]
Наиболее наглядно эту идею можно выразить геометрически, как суммирование точек из , которые лежат на соседних прямых, исходящих из центра координат.
Разбиение конструкции Шоймоши (Конягин, Шкредов, 2015)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/bc/Sum-product-konyagin-shkredov-construction.png/300px-Sum-product-konyagin-shkredov-construction.png)
Цвета линий, исходящих из центра координат, соответствуют блокам, в каждом из которых оценивается количество совпадений сумм.
Синие и фиолетовые линии обозначают суммируемые пары красных точек с одинаковыми суммами.
Если в конструкции Шоймоши убрать условие о том, что суммируемые точки должны принадлежать соседним прямым, то уже ничто не будет гарантировать, что все получающиеся суммы будут различны. Например, вообще все суммы точек из могут быть различны только в экстремальном случае , а он уже удовлетворяет гипотезе сумм-произведений.
Исходя из этого, Конягин и Шкредов оценили минимальное число совпадений таких сумм в промежуточном случае (когда и равны нижней оценке, то есть ). Чтобы оценить число совпадений, они разбили все прямые на блоки из одинакового числа идущих подряд и оценивали число совпадений в каждом блоке для большинства из них. Используя эти оценки, они получили результат с .[20]
Нетривиальное мультипликативное разложение (Руднев, Стивенс, 2020)
Совпадения двух сумм точек, которые рассматривали Конягин и Шкредов, означают наличие решения системы уравнений
где и все и пары различны. Редуцируя систему по методу Гаусса (в одно действие), можно получить уравнение
с постоянными и теми же условиями на . Руднев и Стивенс применили это для явного построения мультипликативного разложения большого подмножества с лучшими свойствами, чем у тривиального.[21]
По аналогии с доказательством Элекеша, это позволяет разделить доказательство оценок с показателем на два этапа:
- применение нового мультипликативного разложения;
- нетривиальное применение уравнения для оценки .[22]
Использование старших энергий
Наиболее популярный путь использования уравнений для оценки — использование аддитивной энергии и её обобщений. Результаты применения теоремы Семереди-Троттера позволяют лучше всего анализировать уравнения вида
для произвольного . Руднев и Стивенс предложили метод использования такой аддитивной энергии с помощью рассмотрения уравнения
где соответствует множеству популярных (с большим количеством представлений) разностей, а принадлежит множеству популярных сумм. Кроме задачи сумм-произведений, разработка подобных методов актуальна для оценки сумм выпуклых последовательностей.[23]
Существует похожий операторный метод, который менее эффективен для оценки , но позволяет лучше изучать связь между и .[24]
Для простых полей
При доказательстве теоремы для широко используются понятие аддитивной энергии, неравенство Плюннеке — Ружа и оценки Балога-Семереди-Гауэрса. Одно из возможных доказательств использует нижнюю оценку на размер множества и тот факт, что из верхних оценок на размеры и следует противоречащая нижней верхняя оценка на размер .[25][26]
Приложения
Бургейн, Глибичук и Конягин[27] использовали частны случай теоремы при для оценки полилинейных тригонометрических сумм. Это, в частности, позволило получить нетривиальные верхние оценки для сумм Гаусса по малым мультипликативным подгруппам .[28] Бургейн, Кац и Тао, используя этот же случай, усилили оценку в проблеме Семереди-Троттера в , доказав, что для множества пар для множества точек из и прямых при выполняеся оценка при некотором . [29]
В этой же работе они применили теорему для исследования множеств Какейи в многомерном пространстве . Для размера такого множества ими была получена оценка .[26][29]
Границы возможного улучшения гипотезы
В той же статье, где Эрдёш и Семереди выдвинули гипотезу о том, что для , они предъявили и пример построения сколь угодно большого множества , для которого . В качестве такого множества выступало множество чисел, получаемых произведением не более чем простых чисел (не обязательно различных), каждое из которых не превышает , где — произвольное достаточно большое число.[16]
Обобщения
Для комбинации операций
Бургейн и Чанг[англ.] рассматривали оценки вида
для произвольного и .[30]
Во многих работах сложение и умножение соединяют в одном выражении: например, получают безусловные нижние оценки для .[31]
Для набора пар слагаемых/множителей
Одно из обобщений гипотезы — вопрос о суммах и произведениях, соответствующие рёбрам произвольного графа на элементах множества.
Пусть — граф, , . Обозначим и через равенства
Как зависят друг от друга значения и при ? |
В отличие от случая , здесь может не наблюдаться экстремального роста ни сумм, ни произведений: при возможна ситуация, когда [32]. Поэтому кроме нижних оказывается актуален вопрос верхних оценок на . Впрочем, нижние оценки тоже исследуются.[33][34]
Для оценки энергий
Нижние оценки на размер множества сумм легко выводить из верхних оценок на аддитивную энергию, поэтому гипотезу о первых естественно обобщить до гипотезы о вторых, используя аналогичное понятие мультипликативной энергии.
Но у множества чисел вполне могут быть большими одновременно обе энергии, поскольку нижняя оценка может контролироваться вкладом отдельного подмножества. Например, если , то для множества верно, что
Поэтому при формулировке соответствующей теоремы об энергиях используется соотношение энергий разных подмножеств.
Теорема Балога-Вули Существует константа такая, что для любого множества существует разбиение с условием |
Наилучший вариант этой теоремы доказан для .[12] Известно, что аналогичное не верно для .[35]
Для произвольных выпуклых функций
Умножение двух чисел можно представить как функцию от сложения их логарифмов: . Поэлементное применение строго возрастающей функции ко множеству не меняет его размера, поэтому
и основную гипотезу сумм-произведений можно переформулировать как
или (подставляя ) как
Оказывается, что похожие оценки можно доказать для произвольной выпуклой функции вместо .
Теорема[36] Если — произвольное множество, — произвольная строго выпуклая функция, то |
Вопрос о том, верны ли такие же оценки с показателем в правой части, остаётся открытым.
Аналогичные результаты получены и для большего числа слагаемых.[37]
Литература
- Гараев М. З. Суммы и произведения множеств и оценки рациональных тригонометрических сумм в полях простого порядка, // Успехи математических наук. — Российская академия наук, 2010. — Т. 65, вып. 4 (394). — С. 5—66. — doi:10.4213/rm9367.
- P. Erdös, E. Szemerédi. On sums and products of integers (англ.) // Birkhäuser Verlag. — 1983. — P. 213–218.
- M. Nathanson. On sums and products of integers (англ.) // Proceedings of the American Mathematical. — 1997. — Vol. 125, iss. 1.
- K. Ford. Sums and Products from a Finite Set of Real Numbers (англ.) // The Ramanujan Journal. — 1998. — Vol. 2. — P. 59–66.
- G. Elekes. On the number of sums and products (англ.) // Acta Arithmetica. — 1997. — Vol. 81, iss. 4. — P. 365–367.
- J. Solymosi. Bounding multiplicative energy by the sumset (англ.) // Advances in Mathematics. — 2009. — Vol. 222, iss. 2. — P. 402–408. — arXiv:0806.1040v3.
- S. V. Konyagin, I. D. Shkredov. On sum sets of sets having small product set (англ.) // Proceedings of the Steklov Institute of Mathematics. — 2015. — Vol. 290. — P. 288–299. — arXiv:1503.05771.
- S. V. Konyagin, I. D. Shkredov. New results on sum-products in (англ.). — 2016. — arXiv:1602.03473.
- M. Rudnev, I. D. Shkredov, S. Stevens. On The Energy Variant of the Sum-Product Conjecture (англ.) // Revista Matemática Iberoamericana. — 2020. — Vol. 36, iss. 1. — P. 207–232. — arXiv:1607.05053.
- G. Shakan. On higher energy decompositions and the sum–product phenomenon (англ.) // Mathematical Proceedings of the Cambridge Philosophical Society. — 2019. — Vol. 167, iss. 3. — P. 599–617. — arXiv:1803.04637.
- M. Rudnev, S. Stevens. An update on the sum-product problem (англ.). — 2020. — arXiv:2005.11145.
- G. Elekes, I. Z. Ruzsa. Few sums, many products (англ.) // Studia Scientiarum Mathematicarum Hungarica. — 2003. — Vol. 40, iss. 3. — P. 301–308.
- B. Murphy, M. Rudnev, I. Shkredov, Y. Shteinikov. On the few products, many sums problem (англ.) // Journal de Théorie des Nombres de Bordeaux. — 2019. — Vol. 31, iss. 3. — P. 573–602. — arXiv:1712.00410.
- N. Alon, I. Ruzsa, J. Solymosi. Sums, products and ratios along the edges of a graph (англ.) // Publicacions Matemàtiques. — 2020. — Vol. 64, iss. 1. — P. 143–155. — arXiv:1802.06405.
- N. Alon, O. Angel, I. Benjamini, E. Lubetzky. Sums and products along sparse graphs (англ.) // Israel Journal of Mathematics. — 2012. — Vol. 188, iss. 1. — P. 353–384. — arXiv:0905.0135.
- I. Shkredov, J. Solymosi. The Uniformity Conjecture in Additive Combinatorics (англ.). — 2020. — arXiv:2005.11559.
- J. Solymosi. On the number of sums and products (англ.) // Bulletin of the London Mathematical Society. — 2005. — Vol. 37, iss. 4. — P. 491–494.
- A. Balog, T. D. Wooley. A low-energy decomposition theorem (англ.) // The Quarterly Journal of Mathematics. — 2017. — Vol. 68, iss. 1. — P. 207–226. — arXiv:1510.03309.
- B. Hanson, O. Roche-Newton, M. Rudnev. Higher convexity and iterated sum sets (англ.). — 2020. — arXiv:2005.00125.
- L. Li, O. Roche-Newton. Convexity and a sum-product type estimate (англ.) // Acta Arithmetica. — 2012. — Vol. 156. — P. 247–255. — arXiv:1111.5159v1.
- J. Bourgain, M.-C. Chang. On the size of -fold sum and product sets of integers (англ.) // Journal of the American Mathematical Society. — 2004. — Vol. 17, iss. 2. — P. 473–497. — arXiv:math/0309055.
- К. И. Ольмезов, А. С. Семченков, И. Д. Шкредов. О популярных суммах и разностях для множеств с малым мультипликативным удвоением // Математические заметки. — 2020. — Т. 108, вып. 4. — С. 561–571. — arXiv:1911.12005.
Примечания
- ↑ Решена в Elekes, Ruzsa, 2003
- ↑ В Murphy, Rudnev, Shkredov, Shteinikov, 2019 получены лучшие результаты, чем в общем случае
- ↑ http://oeis.org/A027424
- ↑ В первой работе Erdös, Szemerédi, 1983 не уточнялось значение , а лишь доказвалось существование. Тем не менее, прямое следование рассуждениям той работы показывает, что она верна для . В явном виде это значение упомянуто позже в Nathanson, 1997
- ↑ Ford, 1998.
- ↑ 1 2 Elekes, 1997.
- ↑ Solymosi, 2005.
- ↑ Solymosi, 2009.
- ↑ Konyagin, Shkredov, 2015.
- ↑ Konyagin, Shkredov, 2016.
- ↑ Rudnev, Shkredov, Stevens, 2020.
- ↑ 1 2 Shakan, 2019.
- ↑ Rudnev, Stevens, 2020.
- ↑ Гараев, 2010, с. 1—2.
- ↑ Tao, Terence (2009), "The sum-product phenomenon in arbitrary rings", Contributions to Discrete Mathematics, 4 (2): 59—82, arXiv:0806.2497, MR 2592424, hdl:10515/sy5r78637.
- ↑ 1 2 Erdös, Szemerédi, 1983.
- ↑ См. Rudnev, Stevens, 2020, лемма 3
- ↑ Похожим образом разложение можно использовать для анализа . См. Rudnev, Stevens, 2020, лемма 4.
- ↑ См. Solymosi, 2009, формула (2).
- ↑ См. Konyagin, Shkredov, 2015, доказательство леммы 10
- ↑ См. Rudnev, Stevens, 2020, с. 10 (после предложения 1)
- ↑ Если применять эти оценки тривиально, так же, как и у Элекеша, то результатом будет
- ↑ См. Rudnev, Stevens, 2020, теорема 5, в особенности формулу (25)
- ↑ См. Olmezov, Semchankau, Shkredov, 2020, теорема 2
- ↑ Гараев, 2010, с. 14—25.
- ↑ 1 2 Mini course of additive combinatorics, заметки по лекциям Принстонского университета
- ↑ J. Bourgain, A. A. Glibichuk, S. V. Konyagin, «Estimates for the number of sums and products and for exponential sums in fields of prime order», J. London Math. Soc. (2), 73:2 (2006), 380—398.
- ↑ Гараев, 2010, с. 7—9.
- ↑ 1 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
- ↑ Bourgain, Chang, 2004.
- ↑ Rudnev, Stevens, 2020, теорема 2
- ↑ Alon, Ruzsa, Solymosi, 2020, теорема 3
- ↑ Alon, Angel, Benjamini, Lubetzky, 2012, следствие 4
- ↑ Shkredov, Solymosi, 2020, теорема 3
- ↑ Balog, Wooley, 2017, теорема 1.2
- ↑ Li, Roche-Newton, 2012, теоремы 1.1, 1.2
- ↑ Hanson, Roche-Newton, Rudnev, 2020, теорема 1.4