Теорема об уголках

Показатели равномерности

В доказательстве используются два показателя равномерности распределения множеств - один для "одномерных" подмножеств ${\displaystyle E\subset {\mathbb {Z} }_{2}^{n}}$, а другой для "двумерных" ${\displaystyle A\subset E_{1}\times E_{2}}$, где ${\displaystyle E_{1},E_{2}\subset {\mathbb {Z} }_{2}^{n}}$

В качестве показателя равномерности для одномерных множеств используется специальным образом адаптированное преобразование Фурье, где в качестве коэффициентов используются корни из единицы, а в место умножения - аналог скалярного произведения вида ${\displaystyle {\overline {x}}\cdot {\overline {y}}=\sum \limits _{i=1}^{n}{x_{i}y_{i}}{\pmod {2}}}$. Если ${\displaystyle {\widehat {E}}(\xi )=\sum \limits _{x\in E}{e^{-(x\cdot \xi )\pi i}}=\sum \limits _{x\in E}{(-1)^{x\cdot \xi }}}$, то малое значение ${\displaystyle \max \limits _{\xi \not =0}{{\widehat {E}}(\xi )}}$ в некотором смысле означает близость множества ${\displaystyle E}$ некоторому случайно распределённому множеству той же плотности, что означает присутствие в нём большего количество структурированных подмножеств, чем во многих остальных. Если ${\displaystyle \max \limits _{\xi \not =0}{{\widehat {E}}(\xi )}<2^{n}\alpha }$ для некоторого ${\displaystyle \alpha }$, то говорят, что множество ${\displaystyle E}$ является ${\displaystyle \alpha }$-равномерным.

Для множества ${\displaystyle A\subset E_{1}\times E_{2}\subset {\mathbb {Z} }_{2}^{n}\times {\mathbb {Z} }_{2}^{n}}$ имеет смысл рассматривать балансовую функцию ${\displaystyle {f_{A}}(x,y)=[(x,y)\in A]-\rho [(x,y)\in E_{1}\times E_{2}]}$, где ${\displaystyle \rho =\rho (A)={\frac {|A|}{|E_{1}||E_{2}|}}}$ - плотность множества, а выражение в квадратных скобках означает индикатор принадлежности множеству. Для балансовой функции определяется так называемая прямоугольная норма ${\displaystyle \lVert {f_{A}}\rVert ^{4}=\sum \limits _{x_{1},y_{1},x_{2},y_{2}}{{f_{A}}(x_{1},y_{1}){f_{A}}(x_{1},y_{2}),{f_{A}}(x_{2},y_{1}),{f_{A}}(x_{2},y_{2})}}$. Если величина этой нормы в некотором смысле достаточно мала, то это также означает близость ${\displaystyle A}$ к случайному множеству. Если ${\displaystyle \lVert {f_{A}}\rVert ^{4}<\alpha |E_{1}|^{2}|E_{2}|^{2}}$, то множество ${\displaystyle A}$ называется ${\displaystyle \alpha }$-равномерным по прямоугольной норме.

Описание алгоритма

Доказательство производится от противного, то есть изначально предполагается, что множество ${\displaystyle A}$ имеет плотность ${\displaystyle \delta }$ и не содержит уголков. Доказательство представляет собой алгоритм последовательного перехода от множества ${\displaystyle A}$ к его подмножеству, содержащемуся в произведении пространств меньшей размерности и имеющего там бо́льшую плотность. Дальше переход по той же схеме осуществвляется от этого подмножества к его же подмножеству, и так далее, пока в очередном подмножестве не найдётся арифметическая прогрессия (которая, очевидно, будет принадлежать и самому ${\displaystyle A}$). Остановка алгоритма в некоторый момент гарантируется тем, что плотность множества не может превышать единицу, а от множества плотности ${\displaystyle \delta }$ переход производится к его подмножеству плотности (в некотором более узком пространстве) ${\displaystyle \delta +2^{-32}\delta ^{24}}$, так что через ${\displaystyle 2^{32}\delta ^{-24}}$ сужений подмножества алгоритм завершает свою работу.

Очередное подмножество ${\displaystyle A_{i}\subset A}$ рассматривается не только как ${\displaystyle A_{i}\subset W_{i}\times W_{i}}$, где ${\displaystyle W_{i}\subset {\mathbb {Z} }_{2}^{n}}$ - некоторое подпространство, но и более узко, как ${\displaystyle A_{i}\subset E_{1}^{(i)}\times E_{2}^{(i)}}$, где множества ${\displaystyle E_{1}^{(i)},E_{2}^{(i)}\subset W_{i}}$ - произвольные множества, но имеющие малые коэффициенты Фурье. Формально можно условиться, что ${\displaystyle A_{0}=A}$, ${\displaystyle W_{0}={\mathbb {Z} }_{2}^{n}}$, ${\displaystyle E_{1}^{(0)}=E_{2}^{(0)}={\mathbb {Z} }_{2}^{n}}$

Далее мы будем рассматривать отдельный шаг алгоритма, и обозначать плотности множеств ${\displaystyle E}$ как ${\displaystyle \beta _{1}={\frac {E_{1}^{(i)}}{|W|}}}$ и ${\displaystyle \beta _{2}={\frac {E_{2}^{(i)}}{|W|}}}$. Эти плотнсти также имеют значение при доказательстве.

Во всех трёх рассматриваемых далее случаях ${\displaystyle \alpha }$-равномерность множеств ${\displaystyle E}$ имеется ввиду относительно текущего пространства ${\displaystyle W_{i}}$

На каждом отдельном этапе алгоитма возможны три случая:

Случай 1

Множества ${\displaystyle E_{1}^{(i)}}$ и ${\displaystyle E_{2}^{(i)}}$ являются ${\displaystyle \alpha _{1}}$-равномерными для некоторого ${\displaystyle \alpha _{1}=\alpha _{1}(\delta ,\beta _{1},\beta _{2})}$. Множество ${\displaystyle A_{i}}$ является ${\displaystyle \alpha _{2}}$-равномерным для некоторого ${\displaystyle \alpha _{2}=\alpha _{2}(\delta )}$.

В этом случае наличие уголков можно доказать буквально, не углубляясь к подмножествам. Более того, можно доказать что множество ${\displaystyle A}$ содержит не менее ${\displaystyle {\frac {\delta ^{3}\beta _{1}\beta _{2}}{2}}|W|^{3}}$ уголков. Это лучшая по порядку роста оценка, поскольку количество уголков, очевидно, не может превышать ${\displaystyle |W|^{3}}$ (ведь уголок определяется тремя числами, ${\displaystyle x,y,d\in W}$).

Случай 2

Множество ${\displaystyle A}$ не является ${\displaystyle \alpha _{2}}$-равномерным для того же ${\displaystyle \alpha _{2}}$, что и в предыдущем случае.

Тоода оказывается возможным выбрать подмножества ${\displaystyle F_{1}\subset E_{1}}$, ${\displaystyle F_{1}\subset E_{2}}$ такие, что их размер не намного меньше размеров ${\displaystyle E_{1},E_{2}}$ (уменьшается не более чем в ${\displaystyle p({\frac {1}{\delta }})}$ раз, где ${\displaystyle p}$ - полином), а плотность множества ${\displaystyle A}$ среди ${\displaystyle F_{1}\times F_{2}}$ значительно превышает его плотность среди ${\displaystyle E_{1}\times E_{2}}$ (превышает на ${\displaystyle q(\delta )}$ где ${\displaystyle q}$ - полином)

Случай 3

Одно из множеств ${\displaystyle E_{1}^{(i)},E_{2}^{(i)}}$ не является ${\displaystyle \alpha _{1}}$-равномерными (для того же ${\displaystyle \alpha _{1}}$, что и в первом случае).

Заметим, что этот случай не может возникать на самом первом шаге, так как ${\displaystyle E_{1}^{(0)}=E_{2}^{(0)}={\mathbb {Z} }_{2}^{n}}$, а пространство относительно самого себя, конечно, всегда ${\displaystyle 0}$-равномерно.

В этом случае используется прирост множества c предыдущего шага, а именно, если множество ${\displaystyle A_{i}}$ имеет плотность ${\displaystyle \delta _{0}+\tau }$ среди ${\displaystyle E_{1}^{(i)}\times E_{2}^{(i)}}$, то доказывается существование некоторого подпространства ${\displaystyle W_{i+1}\subset W_{i}}$ и некоторых сдвигов множеств ${\displaystyle E_{1}^{(i)},E_{2}^{(i)},A}$, таких, что при переходе к их (сдвигов) пересечениям с этим подпространством новые одномерные множества оказываются ${\displaystyle \sigma }$-равномерными для произвольного заранее выбранного ${\displaystyle \sigma }$, а плотность нового двумерного множества оказывается не меньше, чем ${\displaystyle \delta _{0}+{\frac {\tau }{4}}}$.

В качестве ${\displaystyle \sigma }$ здесь можно выбрать ${\displaystyle \alpha _{1}}$, а в качестве ${\displaystyle \tau }$ прирост множества, обеспеченный на предыдущем шаге алгоритма. Таким образом, мы лишь немного (в четыре раза) уменьшаем скорость прироста плотности множества ${\displaystyle A}$ по ходу алгоритма, но зато обеспечиваем на каждом шаге ${\displaystyle \alpha _{1}}$-равномерность множеств ${\displaystyle E_{1}^{(i)},E_{2}^{(i)}}$, а это позволяет нам утверждать, что случаями 1 и 2 исчерпываются все возможные случаи.