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

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

Подмножество квадрата $6\times <!--\; \times \; -->6$$6\times 6$ плотности $\frac{1}{2}$${\frac {1}{2}}$ (ровно половина клеток) с двумя уголками (выделены цветами)

Для натуральных чисел фактически речь идёт о принадлежности достаточно плотному множеству клеток на двумерной решётке двух концов и точки излома прямого угла со сторонами одинаковой длины, параллельными осям координат.

ФормулировкаПравить

Теорема касается двумерной решётки и рассматривает множества пар чисел (координат в двумерном пространстве). Для натуральных чисел $x,y,d(d\ne 0)$$x,y,d\ (d\not =0)$  назовём тройку координат $\{(x,y),(x+d,y),(x,y+d)\}$$\{{(x,y),(x+d,y),(x,y+d)}\}$  уголком. Будем говорить, что множество содержит некоторый уголок если оно содержит в себе все три точки этого уголка.

Для подмножества двумерной решётки $A\subset <!--\; \subset \; -->\{1,\dots <!--\; \dots \; -->,N{\}}^2$$A\subset \{{1,\dots ,N}\}^{2}$  определим его плотность как ${\mathrm{\rho <!--\; \rho \; -->}}_N(A)=\frac{|A|}{N^2}$${\rho _{N}}(A)={\frac {|A|}{N^{2}}}$ , то есть как долю клеток, принадлежащих множеству, среди всей решётки.

Теорема об уголках Для любого $\mathrm{\delta <!--\; \delta \; -->}$$\delta$  существует такое $N=N(\mathrm{\delta <!--\; \delta \; -->})$$N=N(\delta )$ , что если множество $A\subset <!--\; \subset \; -->\{1,\dots <!--\; \dots \; -->,N{\}}^2$$A\subset \{{1,\dots ,N}\}^{2}$  имеет плотность ${\mathrm{\rho <!--\; \rho \; -->}}_N(A)\ge <!--\; \ge \; -->\mathrm{\delta <!--\; \delta \; -->}$$\rho _{N}(A)\geq \delta$ , то оно содержит уголок.

История улучшения результатовПравить

Теорема об уголках была доказана Миклошем Аитаи (англ. Miklos Ajtai) и Эндре Семереди в 1974—1975 годах. В 1981 году этот результат был передоказан Хиллелом Фюрстенбергом (англ. Hillel Furstenberg) с использованием методов эргодической теории. Также существует доказательство Йожефа Шоймоши (венг. Jozsef Solymosi), опирающееся на лемму об удалении треугольника из графа.

Кроме самого факта существования $N=N(\mathrm{\delta <!--\; \delta \; -->})$$N=N(\delta )$ , достаточного для того, чтобы любое множество плотности $\mathrm{\delta <!--\; \delta \; -->}$$\delta$  в квадрате $\{1,\dots <!--\; \dots \; -->,N{\}}^2$$\{1,\dots ,N\}^{2}$  содержало уголок, уместно рассматривать также порядок роста функции $N(\mathrm{\delta <!--\; \delta \; -->})$$N(\delta )$ , или, наоборот, $\mathrm{\delta <!--\; \delta \; -->}(N)$$\delta (N)$  как максимальной плотности $\mathrm{\delta <!--\; \delta \; -->}$$\delta$  для данного $N$$N$ , при которой возможно подмножество без уголков.

Если обозначить как $L(N)$$L(N)$  плотность максимального подмножества квадрата $\{1,\dots <!--\; \dots \; -->,N{\}}^2$$\{1,\dots ,N\}^{2}$ , не содержащего уголков, то основная теорема об уголках будет эквивалентна утверждению о том, что $L(N)=o(1)$$L(N)=o(1)$ , и уместно рассматривать более общий вопрос об улучшении верхних оценок на $L(N)$$L(N)$ . Этот вопрос впервые поставил Уильям Тимоти Гауэрс в 2001 году.

В 2002 году Ву Ха Ван доказал, что $L(N)\le <!--\; \le \; -->\frac{100}{({\log }_{\ast <!--\; \ast \; -->}<!--\; \; -->(N){)}^{1/4}}$$L(N)\leq {\frac {100}{(\log _{*}(N))^{1/4}}}$ , где ${\log }_{\ast <!--\; \ast \; -->}$$\log _{*}$  — операция, обратная к тетрации по основанию 2 в том же смысле, в котором натуральный логарифм является обратной операцией для экспоненты.

В 2005—2006 годах Илья Шкредов улучшил эту оценку сначала до $L(N)=O\left(\frac{1}{(\log <!--\; \; -->\log <!--\; \; -->\log <!--\; \; -->N{)}^{C_1}}\right)$$L(N)=O\left({\frac {1}{(\log \log \log N)^{C_{1}}}}\right)$ , а потом и до $L(N)=O\left(\frac{1}{(\log <!--\; \; -->\log <!--\; \; -->N{)}^{C_2}}\right)$$L(N)=O\left({\frac {1}{(\log \log N)^{C_{2}}}}\right)$ , где $C_1$$C_{1}$  и $C_2$$C_{2}$  — некоторые абсолютные константы.

Связь с теоремой РотаПравить

Теорему об уголках можно считать двумерным аналогом теоремы Рота (частного случая теоремы Семереди для прогрессий длины $3$$3$ ), ведь в постановке задачи важным является именно равенство двух «сторон» прямоугольного уголка, точно так же как в определении арифметической прогрессии важно равенство двух разностей между соседними числами.

Теорема Рота (1953) Для любого $\mathrm{\delta <!--\; \delta \; -->}$$\delta$  существует такое $N=N(\mathrm{\delta <!--\; \delta \; -->})$$N=N(\delta )$ , что если множество $A\subset <!--\; \subset \; -->\{1,\dots <!--\; \dots \; -->,N\}$$A\subset \{{1,\dots ,N}\}$  имеет плотность $\frac{|A|}{N}>\mathrm{\delta <!--\; \delta \; -->}$${\frac {|A|}{N}}>\delta$ , то оно содержит арифметическую прогрессию, то есть тройку чисел $\{a-<!--\; -\; -->d,a,a+d\}$$\{a-d,a,a+d\}$  при некоторых $a$$a$  и $d\ne 0$$d\not =0$ .

Из теоремы об уголках можно вывести теорему Рота как прямое следствие.

Доказательство

 

Схематическое изображение связи уголка и трёхчленной прогрессии в конструкции из доказательства. Красные линии имеют одинаковую длину, так как число 2 "движется" равномерно вверх и вправо с каждой новой линией. Следовательно, равенство сторон уголка, даёт равенство разностей в прогрессии

Для доказательства от противного предположим, что теорема об уголках верна, а теорема Рота не верна, то есть существует какая-то плотность $\mathrm{\delta <!--\; \delta \; -->}>0$$\delta >0$  такая, что для любого $N$$N$  можно найти подмножество $A\subset <!--\; \subset \; -->\{1,\dots <!--\; \dots \; -->,N\}$$A\subset \{1,\dots ,N\}$  такой плотности, не содержащее арифметической прогрессии, но аналогичной плотности для покрытия квадрата произвольного размера без образования уголков не существует. Нам нужно, исходя из этого, прийти к противоречию.

Рассмотрим для произвольного $N$$N$  такое множество $A\subset <!--\; \subset \; -->\{1,\dots <!--\; \dots \; -->,N\}$$A\subset \{1,\dots ,N\}$  $(|A|>\mathrm{\delta <!--\; \delta \; -->}N)$$(|A|>\delta N)$  и сконструируем по нему двумерное подмножество квадрата размера $2N$$2N$ , которое будет контрпримером для теоремы об уголках, то есть будет иметь известную ненулевую плотность и должно будет не содержать уголков.

Таким множеством будет множество вида $X=\{(a+(i-<!--\; -\; -->1),i):i\in <!--\; \in \; -->1,\dots <!--\; \dots \; -->,N,a\in <!--\; \in \; -->A\}$$X=\{(a+(i-1),i):i\in {1,\dots ,N},a\in A\}$ , то есть последовательность строк, представляющих последовательные сдвиги множества $A$$A$ . Если бы в таком множестве был уголок, то это означало бы, что во множестве $A$$A$  была арифметическая прогрессия длины $3$$3$ , ведь $X$$X$  сконструировано так, что, если $(x,y+d)\in <!--\; \in \; -->X$$(x,y+d)\in X$ , то и $(x-<!--\; -\; -->d,y)\in <!--\; \in \; -->X$$(x-d,y)\in X$ , и тогда, кроме уголка, в нём присутствует тройка $(x-<!--\; -\; -->d,y),(x,y),(x+d,y)$$(x-d,y),(x,y),(x+d,y)$ , отображающая арифметическую прогрессию в конкретную строку.

Однако нашим изначальным предположением было, что в $A$$A$  нет таких прогрессий. Значит, в $X$$X$  нет уголков. Теперь рассмотрим плотность $X$$X$  в квадрате $\{1,\dots <!--\; \dots \; -->,2N{\}}^2$$\{1,\dots ,2N\}^{2}$ . Так как сдвигов всего $N$$N$ , и они все входят в множество полностью, то плотность равна $\frac{N|A|}{(2N{)}^2}>\frac{\mathrm{\delta <!--\; \delta \; -->}{N}^2}{4N^2}=\frac{\mathrm{\delta <!--\; \delta \; -->}}{4}$${\frac {N|A|}{(2N)^{2}}}>{\frac {\delta N^{2}}{4N^{2}}}={\frac {\delta }{4}}$ .

Итак, мы научились строить множество плотности $\frac{\mathrm{\delta <!--\; \delta \; -->}}{4}$${\frac {\delta }{4}}$ , не содержащее уголков, в квадрате любого размера. Однако это противоречит нашему изначальному предположению о том, что теорема об уголках верна.

Обобщение для группПравить

Кроме визуально представимых уголков на решётке $\{1,\dots <!--\; \dots \; -->,N{\}}^2$$\{1,\dots ,N\}^{2}$  можно рассматривать обобщённые «уголки» вида $\{(x,y),(x\circ <!--\; \circ \; -->d,y),(x,y\circ <!--\; \circ \; -->d)\}$$\{(x,y),(x\circ d,y),(x,y\circ d)\}$ , где $x,y,d\in <!--\; \in \; -->G$$x,y,d\in G$ , а $G$$G$  — некоторая группа с операцией $\circ <!--\; \circ \; -->$$\circ$ .

Для пространства ${\mathbb{Z}}_2^n$${\mathbb {Z} }_{2}^{n}$ Править

Бен Грин в 2005 году рассмотрел вопрос об уголках в группе ${\mathbb{Z}}_2^n$${\mathbb {Z} }_{2}^{n}$ , то есть не для множества натуральных чисел. а для множества битовых (состоящих из нулей и единиц) последовательностей длины $n$$n$ , для которых вместо сложения используется побитовое исключающее или.

Теорема (Грин, 2005) Для любого $\mathrm{\delta <!--\; \delta \; -->}$$\delta$  существует такое $n=n(\mathrm{\delta <!--\; \delta \; -->})$$n=n(\delta )$ , что если множество $A\subset <!--\; \subset \; -->{\mathbb{Z}}_2^n\times <!--\; \times \; -->{\mathbb{Z}}_2^n$$A\subset {\mathbb {Z} }_{2}^{n}\times {\mathbb {Z} }_{2}^{n}$  имеет плотность $\frac{|A|}{2^{2n}}\ge <!--\; \ge \; -->\mathrm{\delta <!--\; \delta \; -->}$${\frac {|A|}{2^{2n}}}\geq \delta$ , то оно содержит уголок вида $\{(x,y),(x+d,y),(x,y+d)\}$$\{(x,y),(x+d,y),(x,y+d)\}$ , где $x,y,d\in <!--\; \in \; -->{\mathbb{Z}}_2^n$$x,y,d\in {\mathbb {Z} }_{2}^{n}$ , а сложение производится по модулю 2.

Общая схема доказательства для ${\mathbb{Z}}_2^n$${\mathbb {Z} }_{2}^{n}$ 

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

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

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

Для множества $A\subset <!--\; \subset \; -->E_1\times <!--\; \times \; -->E_2\subset <!--\; \subset \; -->{\mathbb{Z}}_2^n\times <!--\; \times \; -->{\mathbb{Z}}_2^n$$A\subset E_{1}\times E_{2}\subset {\mathbb {Z} }_{2}^{n}\times {\mathbb {Z} }_{2}^{n}$  имеет смысл рассматривать балансовую функцию $f_A(x,y)=[(x,y)\in <!--\; \in \; -->A]-<!--\; -\; -->\mathrm{\rho <!--\; \rho \; -->}[(x,y)\in <!--\; \in \; -->E_1\times <!--\; \times \; -->E_2]$${f_{A}}(x,y)=[(x,y)\in A]-\rho [(x,y)\in E_{1}\times E_{2}]$ , где $\mathrm{\rho <!--\; \rho \; -->}=\mathrm{\rho <!--\; \rho \; -->}(A)=\frac{|A|}{|E_1||E_2|}$$\rho =\rho (A)={\frac {|A|}{|E_{1}||E_{2}|}}$  - плотность множества, а выражение в квадратных скобках означает индикатор принадлежности множеству. Для балансовой функции определяется так называемая прямоугольная норма $\Vert <!--\; \Vert \; -->f_A{\Vert <!--\; \Vert \; -->}^4=\underset{x_1,y_1,x_2,y_2}{\sum <!--\; \sum \; -->}{f}_A(x_1,y_1)f_A(x_1,y_2),f_A(x_2,y_1),f_A(x_2,y_2)$$\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})}$ . Если величина этой нормы в некотором смысле достаточно мала, то это также означает близость $A$$A$  к случайному множеству. Если $\lVert {f_{A}}\rVert ^{4}<\alpha |E_{1}|^{2}|E_{2}|^{2}$ , то множество $A$$A$  называется $\mathrm{\alpha <!--\; \alpha \; -->}$$\alpha$ -равномерным по прямоугольной норме.

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

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

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

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

Во всех трёх рассматриваемых далее случаях $\mathrm{\alpha <!--\; \alpha \; -->}$$\alpha$ -равномерность множеств $E$$E$  имеется ввиду относительно текущего пространства $W_i$$W_i$ 

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

Случай 1

Множества $E_1^{(i)}$$E_{1}^{(i)}$  и $E_2^{(i)}$$E_{2}^{(i)}$  являются ${\mathrm{\alpha <!--\; \alpha \; -->}}_1$$\alpha _{1}$ -равномерными для некоторого ${\mathrm{\alpha <!--\; \alpha \; -->}}_1={\mathrm{\alpha <!--\; \alpha \; -->}}_1(\mathrm{\delta <!--\; \delta \; -->},{\mathrm{\beta <!--\; \beta \; -->}}_1,{\mathrm{\beta <!--\; \beta \; -->}}_2)$$\alpha _{1}=\alpha _{1}(\delta ,\beta _{1},\beta _{2})$ . Множество $A_i$$A_{i}$  является ${\mathrm{\alpha <!--\; \alpha \; -->}}_2$$\alpha_2$ -равномерным для некоторого ${\mathrm{\alpha <!--\; \alpha \; -->}}_2={\mathrm{\alpha <!--\; \alpha \; -->}}_2(\mathrm{\delta <!--\; \delta \; -->})$$\alpha _{2}=\alpha _{2}(\delta )$ .

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

Случай 2

Множество $A$$A$  не является ${\mathrm{\alpha <!--\; \alpha \; -->}}_2$$\alpha_2$ -равномерным для того же ${\mathrm{\alpha <!--\; \alpha \; -->}}_2$$\alpha_2$ , что и в предыдущем случае.

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

Случай 3

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

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

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

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

Для произвольных абелевых группПравить

Илья Шкредов в 2009 году доказал обобщение для абелевых групп.

Теорема Существует абсолютная константа $c>0$$c>0$  такая, что если $(G,\circ <!--\; \circ \; -->)$$(G,\circ )$  — абелева группа, $A\subset <!--\; \subset \; -->G\times <!--\; \times \; -->G$$A\subset G\times G$ , то из $|A|\ge <!--\; \ge \; -->\frac{|G{|}^2}{(\log <!--\; \; -->\log <!--\; \; -->|G|{)}^c}$$|A|\geq {\frac {|G|^{2}}{({\log \log {|G|}})^{c}}}$  следует присутствие в $A$$A$  уголка $\{(x,y),(x\circ <!--\; \circ \; -->d,y),(x,y\circ <!--\; \circ \; -->d)\}$$\{(x,y),(x\circ d,y),(x,y\circ d)\}$