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

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

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

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

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

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

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

Шаблон:Рамка Теорема об уголках

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

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

Теорема об уголках была доказана Шаблон:Нп2 и Эндре Семереди в 1974—1975 годах. В 1981 году этот результат был передоказан Шаблон:Нп2 с использованием методов эргодической теории. Также существует доказательство Йожефа Шоймоши (Шаблон:Lang-hu), опирающееся на лемму об удалении треугольника из графа.

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

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

В 2002 году Ву Ха Ван доказал, что $L(N)\le \frac{100}{({\log }_{*}(N){)}^{1/4}}$, где ${\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 N{)}^{C_2}}\right)$, где $C_1$ и $C_2$ — некоторые абсолютные константы.

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

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

Шаблон:Рамка Теорема Рота (1953)

Для любого $\delta$ существует такое $N=N(\delta )$, что если множество $A\subset \{1,\dots ,N\}$ имеет плотность $\frac{|A|}{N}>\delta$, то оно содержит арифметическую прогрессию, то есть тройку чисел $\{a-d,a,a+d\}$ при некоторых $a$ и $d=0$. Шаблон:Конец рамки

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

Обобщение для групп

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

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

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

Шаблон:Рамка Теорема (Грин, 2005)

Для любого $\delta$ существует такое $n=n(\delta )$, что если множество $A\subset {\mathbb{Z}}_2^n\times {\mathbb{Z}}_2^n$ имеет плотность $\frac{|A|}{2^{2n}}\ge \delta$, то оно содержит уголок вида $\{(x,y),(x+d,y),(x,y+d)\}$, где $x,y,d\in {\mathbb{Z}}_2^n$, а сложение производится по модулю 2. Шаблон:Конец рамки

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

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

Шаблон:Рамка Теорема

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