Арифметическая комбинаторика

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

Подход к понятию структуры здесь аналогичен аддитивной комбинаторике и базируется в основном на размере множества сумм (или произведений), аддитивной (или мультипликативной) энергии и различных их комбинациях. В качестве поля обычно рассматриваются вещественные или рациональные числа (${\mathbb {R} }$, ${\mathbb {Q} }$) и вычеты по простому модулю (${\mathbb {F} }_{p}$).

Неоднозначность терминологии и предмет статьи

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

Кроме того, здесь не затрагиваются вопросы об аддитивно-комбинаторных свойствах мультипликативных подгрупп ${\mathbb {F} }_{p}^{*}$ и связанных с ними множеств, поскольку, хотя их определение и связано с умножением, но их мультипликативная структура жёстко зафиксироана, а комбинаторная составляющая этой науки предполагает ту или иную общность относительно степени структурированности (хотя бы с параметром, выступающим в роли константы).

Мотивация

Развитие арифметической комбинаторики было во многом мотивировано появлением теоремы сумм-произведений, которая говорит о непременном разрастании множеств от применения к нему либо комбинаторного суммирования, либо перемножения, то есть одной из двух операций:

$A+A=\left\lbrace {a_{1}+a_{2}:a_{1},a_{2}\in A}\right\rbrace$

$A\times A=\left\lbrace {a_{1}\cdot a_{2}:a_{1},a_{2}\in A}\right\rbrace$

Из этого следует, что комбинирование этих операций также влечёт разрастание: если $\{0,1\}\subset A$, то

$|A(A+A)|\gg \max\{|A(A+0)|,|1(A+A)|\}=\max\{|AA|,|A+A|\}$,

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

Например, гипотеза Эрдёша — Семереди о суммах-произведениях гласит, что

$\max\{|A+A|,|AA|\}\geq |A|^{2-o(1)}\ \forall A\subset {\mathbb {R} }$

Из этой гипотезы следовало бы, что $|AA+A|\geq |A|^{2-o(1)}$, но для множеств $A\subset {\mathbb {N} }$ такой результат легко получить и без неё простым комбинаторным рассуждением.

Задачи и результаты

В этом разделе для описания результатов используется общепринятые записи (пояснение приведено в O-нотации):

• $X\ll Y$ означает, что $X=O(Y)$

• $X\lesssim Y$ означает, что $X\leq (\log |A|)^{O(1)}Y$

Рациональные выражения

Постановка вопроса

Пусть рациональным выражением над множествами $A_{1},\dots ,A_{k}$ называется любая комбинация арифметических операций ($+,-,\times ,/$) между ними. Под операцией здесь имеется в виду применение по принципу множества сумм:

$A\circ B=\{a\circ b\ :\ a\in A,\ b\in B\}$

Например, следующие множества являются рациональными выражениями над $A,B,C$:

• сами множества $A,\ B,\ C$;

• $A(A-A)=\{a(b-c)\ :\ a,b,c\in A\}$ — рациональное выражение над $A$;

• $A+BC=\{a+bc\ :\ a\in A,\ b\in B,\ c\in C\}$.

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

$E_{AB+C}=\#\{(a_{1},a_{2},b_{1},b_{2},c_{1},c_{2})\in A^{2}\times B^{2}\times C^{2}|:\ a_{1}+b_{1}c_{1}=a_{2}+b_{2}c_{2}\}$

Существенную часть проблематики арифметической комбинаторики можно выразить следующей постановкой вопроса.

Пусть ${\mathbb {F} }$ — некоторое поле (либо бесконечное, либо достаточно большое из заданного семейства конечных), $R_{1},\dots ,R_{n}$ — рациональные выражения, причём хотя бы в одном из них используется $+$ или $-$ и хотя бы в одном $\cdot$ или $/$. Пусть также для некоторых $N$ и множеств $A_{1},\dots ,A_{k}\subset {\mathbb {F} }$ выполнены соотношения $|A_{j}|=N^{\alpha _{j}},\ j=1,\dots ,k$ $|R_{i}(A_{1},\dots ,A_{k})|=N^{\beta _{i}},\ i=1,\dots ,n$ $E_{R_{i}(A_{1},\dots ,A_{k})}=N^{\gamma _{i}},\ i=1,\dots ,n$ Вопрос Как при $N\to \infty$ ограничено множество возможных значений $(\alpha _{1},\dots ,\alpha _{k},\beta _{1},\dots ,\beta _{k},\gamma _{1},\dots ,\gamma _{n})$ в зависимости от ${\mathbb {F} },R_{1},\dots ,R_{n}$? Примечание Если поле конечное, то набор $(\alpha _{1},\dots ,\gamma _{n})$ уместно дополнить параметром $\varepsilon$, где $N=|{\mathbb {F} }|^{\varepsilon }$.

Например, гипотеза о суммах-произведениях утверждает, что если ${\mathbb {F} }={\mathbb {R} }$, $R_{1}(A)=A+A$, $R_{2}(A)=A\cdot A$, то $\max\{\gamma _{1},\gamma _{2}\}=2$ (здесь $k=1,\ n=2$).

Как правило, получается вывести линейные соотношения между величинами $\alpha _{1},\dots ,\gamma _{n}$, то есть неравенства между произведениями и степенями разных величин $|A_{j}|,\ |R_{i}(A_{1},\dots ,A_{k})|,\ E_{R_{i}(A_{1},\dots ,A_{k})}$.

Некоторые результаты

Об обобщении сумм и произведений:

$\forall A\subset {\mathbb {R} }:\ |AA+AA+AA+AA|\geq {\frac {1}{2}}|A|^{2}$

$\forall A\subset {\mathbb {F} }_{p}:|A|<p^{1/4}\Rightarrow |A(A-A+A-A)+A(A-A)|\geq |A|^{2}$

$\exists c>0:\ \forall B,C\subset {\mathbb {R} }:\ |(B+C)(B+C)|\geq |B+C|^{1+c}$;

$\exists c>0:\ \forall A\subset {\mathbb {R} }:\ |AA+A|\geq |A|^{{\frac {3}{2}}+c}$;

$\exists c_{1},c_{2}>0:\ \forall A\subset {\mathbb {R} }:\ |A+A|\leq |A|^{1+c_{1}}\Rightarrow |AAA|\geq |A|^{2+c_{2}}$

$\forall A\subset {\mathbb {R} }:\ |(A-A)(A-A)(A-A)|\gtrsim |A|^{2+{\frac {1}{8}}}$

Об обобщении энергий:

• $E_{A+B}^{2}\leq |A/B|E_{(A+B)/B}$

• для любого $k\in {\mathbb {N} }$ если $A\subset {\mathbb {F} }_{p},\ |A|\geq p^{c(k)}$, то $E_{(A-A)^{k}}\sim {\frac {|A|^{4k}}{p}}$, причём $c(k)\to {\frac {1}{2}}$ при $k\to \infty$

Сдвиги

Постановка вопроса

Идея оценки рациональных выражений, объединяющих разные операции, исходит из того, что применение ко множеству аддитивной операции лишает его мультипликативной структуры. Этот же принцип можно расширить на случай, когда множество изменяется не сложной комбинаторной операцией поэлементного сложения, а обычным аддитивным сдвигом — прибавлением ко всем элементам множества одного числа. Ожидается, что от этого мультипликативная структура множества должна в большинстве случаев меняться (например, что если $|AA|\ll |A|$, то $|(A+d)(A+d)|\gg |A|^{1+c}$ для некоторого $c>0$ при всех или почти всех $d$).

Вопрос Как при фиксированном (но произвольном) $A\subset {\mathbb {F} }$ зависят друг от друга мультипликативные свойства (размер множества произведений и мультипликативная энергия) множеств $A+u,\ u\in {\mathbb {F} }$. А также каковы совместные мультипликативные свойства множеств $A+u_{1},\dots ,A+u_{k}$ при различных $u_{1},\dots ,u_{k}$ (например, существуют ли нетрвииальные оценки на $|A(A+1)|$)?

Некоторые результаты

• если $A\subset {\mathbb {F} }_{p}$ при простом $p$, то:

• • $|A|<p^{5/8}\Rightarrow |A(A+1)|\gg |A|^{6/5}$

• • $|A|<p^{1/4}\Rightarrow |A(A+1)|\gtrsim |A|^{11/9-o(1)}$

• $\forall A\subset {\mathbb {R} }_{+}:\ \forall a\in {\mathbb {R} }\setminus \{0\}:\ |A(A+1)|\ll |A|\Rightarrow E_{\times }(A,A+a)\lesssim |A|^{32/13}$

• $\forall A\subset {\mathbb {Q} }_{+}:\ |AA|\ll |A|\Rightarrow |(A+1)^{k}|\gg _{k}|A|^{k}$

• $\forall A\subset {\mathbb {R} }_{+}:\ |AA|^{4}|(A+1)(A+1)|\gtrsim |A|^{6}$

• $\forall A\subset {\mathbb {R} }_{+}:\ |(A+1)(A+1)(A+1)|^{16}|AA|^{78}\gtrsim |A|^{111}$

• $\forall A\subset {\mathbb {Q} }_{+}\forall u\subset {\mathbb {Q} }\setminus \{0\}:\ \max \left\lbrace {|A^{k}|,|(A+u)^{k}|}\right\rbrace \gg |A|^{b(k)}$, где $b(k)\to \infty$ при $k\in \infty$

Многочлены

Постановка вопроса

Идея комбинирования сложения и умножения естественным образом приводит к рассмотрению многочленов, то есть таких же рациональных выражений, но в которых одна переменная может появляться несколько раз (и тем самым оказывать более сложное влияние на структуру получающегося множества). Оказывается, в этом случае для обеспечения безусловного роста не обязательно использовать три копии множества (как в выражении $A+AA$), а достаточно подобрать нужный полином от двух переменных. Впервые такое свойство заметил Бургейн для многочлена $x^{2}+xy$.

Также, по аналогии с теоремой сумм-произведений, изучаются оценки снизу на $\max\{|A+A|,|f(A,A)|\}$ для произвольных многочленов $f$.

Некоторые результаты

Первый результат Бургейна: если $A,B\subset {\mathbb {F} }_{p},\ |A|\sim |B|\sim p^{\alpha },\ \alpha \in (0;1)$. Тогда для некоторого $\varepsilon =\varepsilon (\alpha )>0$ верно, что

$\#\{a^{2}+ab\ :\ a\in A,\ b\in B\}\geq N^{1+\varepsilon }$

При сравнении $|A+A|$ и $|f(A,A)|$ большое значение имеет вырожденность многочлена $f$. Если он вырожден, то есть представим в виде $f=g(l(x,y))$, где $l,g$ — многочлены и $\deg l=1$, то обе суммы могут оказаться малыми если $A$ — арифметическая прогрессия, ведь $|f(A,A)|\leq |l(A,A)|$. Поэтому результаты формулируются только для невырожденных многочленов:

• если $\deg f=2$ , то $\forall A\subset {\mathbb {F} }_{p}\ :\ |A|\leq p^{5/8}\Rightarrow \max\{|A+A|,|f(A,A)|\}\gg |A|^{6/5}$

• если $\deg f=d$, то $\forall A\subset {\mathbb {F} }_{p}\ :\ \max\{|A+A|,|f(A,A)|\}\gg \min \left\lbrace {{\frac {|A|^{3/2}}{dp^{1/4}}},{\frac {p^{1/3}|A|^{2/3}}{d^{1/3}}}}\right\rbrace$

Матричное умножение

Свойства

Существуют результаты о множествах произведений набора матриц из той или иной матричной подгруппы (например, ${\mbox{SL}}_{2}({\mathbb {R} })$ или группы Гейзенберга). Строго говоря, эти результаты касаются одной групповой операции (матричного умножения), так что их можно отнести к аддитивной комбинаторике. Но слияние внутри определения этой операции и сложения, и умножения элементов, а также возникающая из этого некоммутативность делают её свойства очень нетипичными по сравнению с обычными групповыми операциями, вроде сложения вещественных чисел.

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

Некоторые результаты

Большинство результатов о матричных группах, когда они касаются произвольных наборов матриц, анализирует велличину $|AAA|$, а не $|AA|$. Это не случайность, а техническая необходимость, связанная с некоммутативностью.

• если $A\subset {\mathbb {R} }$, то для множества матриц ${\mathcal {A}}=\left\lbrace {{\begin{pmatrix}1&a&0\\0&1&b\\0&0&1\end{pmatrix}}\ :\ a,b\in A}\right\rbrace$ (оно лежит в группе Гейзенберга) верно, что $|{\mathcal {A}}{\mathcal {A}}|\gg |{\mathcal {A}}|^{7/4+c}$, где $c>0$

• пусть $A\subset {\mbox{SL}}_{2}({\mathbb {F} }_{p})$ порождает всю группу ${\mbox{SL}}_{2}({\mathbb {F} }_{p})$ и $\forall a\in A\ :\ a^{-1}\in A$. Тогда $|AAA|\gg \min\{|A|^{21/20},\ |{\mbox{SL}}_{2}({\mathbb {F} }_{p})|\}$

• $\forall A\subset {\mbox{SL}}_{n}({\mathbb {F} }_{p})\ :\ |A|>2|G|^{1-{\frac {1}{3(n+1)}}}\Rightarrow AAA={\mbox{SL}}_{n}({\mathbb {F} }_{p})$ (для других групп возможна аналогичная оценка, зависящая от размерности её представлений)

• если $A\subset {\mbox{SL}}_{3}({\mathbb {F} }_{p})$ и $|AAA|\ll |A|^{1+\delta },\ \delta >0$, то структура $A$ сильно связана с подгруппами $A\subset {\mbox{SL}}_{3}({\mathbb {F} }_{p})$ (эта связь может быть выражена в терминах $\delta$)

Приложения

Аналитические методы изучения роста в группе ${\mbox{SL}}_{2}({\mathbb {F} }_{p})$ и группах Шевале можно использовать для вывода специальной формы гипотезы Зарембы.

См. также

• Аддитивная комбинаторика
• Аддитивная теория чисел
• Теорема сумм-произведений

Список литературы

• P. Erdös, E. Szemerédi. On sums and products of integers (англ.) // Birkhäuser Verlag. — 1983. — P. 213–218.

• Oliver Roche-Newton, Imre Z. Ruzsa, Chun-Yen Shen, Ilya D. Shkredov. On the size of the set $AA+A$ (англ.). — 2018. — arXiv:1801.10431v1.

• Oliver Roche-Newton, Ilya D. Shkredov. If $A+A$ is small then $AAA$ is superquadratic (англ.). — 2019. — arXiv:1810.10842v2.

• Antal Balog. A note on sum-product estimates (англ.) // Publicationes mathematicae. — 2011. — Vol. 79, iss. 3. — doi:10.5486/PMD.2011.5104.

• М. З. Гараев. Суммы и произведения множеств и оценки рациональных тригонометрических сумм в полях простого порядка, (рус.) // Успехи математических наук. — Российская академия наук, 2010. — Т. 65, вып. 4 (394). — С. 5—66. — doi:10.4213/rm9367.

• Ilya D. Shkredov, Dmitrii Zhelezov. On additive bases of sets with small product set (англ.). — 2016. — arXiv:math/1606.02320.

• А. А. Глибичук. Комбинаторные свойства множеств вычетов по простому модулю и задача Эрдёша — Грэхэма (рус.) // Математические заметки. — 2006. — Т. 79, вып. 3. — С. 384–395.

• Brandon Hanson, Oliver Roche-Newton, Dmitrii Zhelezov. On iterated product sets with shifts (англ.). — 2018. — arXiv:1801.07982v1.

• Brandon Hanson, Oliver Roche-Newton, Dmitrii Zhelezov. On iterated product sets with shifts II (англ.). — 2018. — arXiv:math/1806.01697v1.

• Sophie Stevens, Frank de Zeeuw. An improved point-line incidence bound over arbitrary fields (англ.) // Bulletin of the London Mathematical Society. — 2017. — Vol. 49, iss. 5. — doi:10.1112/blms.12077. — arXiv:1609.06284.

• Audie Warren. On Products of Shifts in Arbitrary Fields (англ.). — 2019. — arXiv:1812.01981v2.

• Antal Balog, Oliver Roche-Newton, Dmitry Zhelezov. Expanders with Superquadratic Growth (англ.) // The electronic journal of combinatorics. — 2016. — Vol. 24, iss. 3. — doi:10.37236/7050. — arXiv:1611.05251v1.

• И. Д. Шкредов. Несколько замечаний о множествах с малым частным (рус.) // Математический сборник. — 2017. — Т. 208, вып. 12. — doi:10.4213/sm8733. — arXiv:1603.04948v2.

• Bryce Kerr, Simon Macourt. Multilinear Exponential Sums With A General Class Of Weights (англ.). — 2019. — arXiv:1901.00975v2.

• Konstantin I. Olmezov, Aliaksei S. Semchankau, Ilya D. Shkredov. On popular sums and differences of sets with small products (англ.). — 2019. — arXiv:1911.12005v1.

• Brandon Hanson, Oliver Roche-Newton, Misha Rudnev. Higher convexity and iterated sum sets (англ.). — 2020. — arXiv:2005.00125v1.

• И. Д. Шкредов. Несколько новых результатов о старших энергиях (рус.) // Труды Московского математического общества. — 2013. — Т. 74, вып. 1.

• J. Bourgain. More on the sum-product phenomenon in prime fields and its applications (англ.) // International Journal of Number Theory. — 2005. — Vol. 1, iss. 1. — doi:10.1142/S1793042105000108.

• Doowon Koh, Hossein Nassajian Mojarrad, Thang Pham, Claudiu Valculescu. Four-variable expanders over the prime fields (англ.) // Proceedings of the American Mathematical Society. — 2018. — Vol. 146, iss. 12. — doi:10.1090/proc/14177. — arXiv:1705.04255.

• Van Vu. Sum-product estimates via directed expanders (англ.) // Mathematical Research Letters. — 2007. — Vol. 15, iss. 2. — doi:10.4310/MRL.2008.v15.n2.a14. — arXiv:0705.0715.

• Ilya D. Shkredov. Some remarks on products of sets in the Heisenberg group and in the affine group (англ.). — 2019. — arXiv:1907.03357.

• Misha Rudnev, Ilya D. Shkredov. On growth rate in ${\mbox{SL}}_{2}({\mathbb {F} }_{p})$, the affine group and sum-product type implications (англ.). — 2019. — arXiv:1812.01671v3.

• H. A. Helfgott. Growth in ${\mbox{SL}}_{3}({\mathbb {Z} }/p{\mathbb {Z} })$ (англ.). — 2009. — arXiv:0807.2027.

• Nikolay Nikolov, László Pyber. Product decompositions of quasirandom groups and a Jordan type theorem (англ.) // Journal of the European Mathematical Society. — 2007. — Vol. 13, iss. 4. — doi:10.4171/JEMS/275. — arXiv:0703343.

• Nikolay G. Moshchevitin, Ilya D. Shkredov. On a modular form of Zaremba's conjecture (англ.). — 2019. — arXiv:1911.07487.

• Ilya D. Shkredov. Growth in Chevalley groups relatively to parabolic subgroups and some applications (англ.). — 2020. — arXiv:2003.12785.