WikiSort.ru - Не сортированное

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

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

Доказательство Эрдёша для случая ${\displaystyle {\mathbb {F} }={\mathbb {Z} }}$ элементарно, оно использует вывод существования в случае малых ${\displaystyle |A+A|}$ и ${\displaystyle |A\times A|}$ решения системы уравнений ${\displaystyle b_{1}+b_{3}=b_{2}+b_{4},\ b_{1}b_{5}=b_{2}b_{6}}$ , где ${\displaystyle b_{i}}$ принадлежат некоторым (разным) подмножествам ${\displaystyle A}$ , а на само множество ${\displaystyle A}$ налагаются специальные условия. Используя такое утверждение как лемму, можно доказать теорему и для произвольного множества ${\displaystyle A}$ ^[1]

При доказательстве теоремы для ${\displaystyle {\mathbb {F} }={\mathbb {F} }_{p}}$ широко используются понятие аддитивной энергии, неравенство Плюннеке — Ружа и оценки Балога-Семереди-Гауэрса.^[8][9]

Одно из возможных доказательств использует нижнюю оценку на размер множества ${\displaystyle R(A)=A\left({{\frac {A\times A-A\times A}{A-A}}+A}\right)}$ и тот факт, что из верхних оценок на размеры ${\displaystyle A+A}$ и ${\displaystyle A\times A}$ следует противоречащая нижней верхняя оценка на размер ${\displaystyle R(A)}$ .^[8]

Приложения

Теорема сумм-произведений находит много приложений в различных областях математики.

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

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

Литература

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

Примечания