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

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

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

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

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

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

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

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

${\displaystyle 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}\}}$[4]

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

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

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

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

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

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

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

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

${\displaystyle \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}}}$[10]

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

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

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

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

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

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

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

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

• ${\displaystyle \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}}$[17]

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

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

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

• ${\displaystyle \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)}}$, где ${\displaystyle b(k)\to \infty }$ при ${\displaystyle k\in \infty }$[21]

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

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

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

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

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

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

• если ${\displaystyle \deg f=d}$, то ${\displaystyle \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 } [26]

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

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

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

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

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

• ${\displaystyle \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})} (для других групп возможна аналогичная оценка, зависящая от размерности её представлений)[31]

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

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