Русская Википедия:Теорема об уголках
Теорема об уголках — доказанный результат в области аддитивной комбинаторики, утверждающий присутствие некой упорядоченной (в арифметическом смысле) структуры, называемой уголком, в достаточно больших двумерных множествах любой фиксированной плотности.
Для натуральных чисел фактически речь идёт о принадлежности достаточно плотному множеству клеток на двумерной решётке двух концов и точки излома прямого угла со сторонами одинаковой длины, параллельными осям координат.
Формулировка
Теорема касается двумерной решётки и рассматривает множества пар чисел (координат в двумерном пространстве). Для натуральных чисел <math>x,y,d\ (d \not = 0)</math> назовём тройку координат <math>\{{(x,y),(x+d,y),(x,y+d)}\}</math> уголком. Будем говорить, что множество содержит некоторый уголок если оно содержит в себе все три точки этого уголка.
Для подмножества двумерной решётки <math>A \subset \{{1,\dots,N}\}^2</math> определим его плотность как <math>{\rho_N} (A) = \frac{|A|}{N^2}</math>, то есть как долю клеток, принадлежащих множеству, среди всей решётки.
Шаблон:Рамка Теорема об уголках
Для любого <math>\delta</math> существует такое <math>N=N(\delta)</math>, что если множество <math>A \subset \{{1,\dots,N}\}^2</math> имеет плотность <math>\rho_N (A) \ge \delta</math>, то оно содержит уголок.
История улучшения результатов
Теорема об уголках была доказана[1][2] Шаблон:Нп2 и Эндре Семереди в 1974—1975 годах. В 1981 году этот результат был передоказан Шаблон:Нп2 с использованием методов эргодической теории. Также существует[3] доказательство Йожефа Шоймоши (Шаблон:Lang-hu), опирающееся на лемму об удалении треугольника из графа.
Кроме самого факта существования <math>N=N(\delta)</math>, достаточного для того, чтобы любое множество плотности <math>\delta</math> в квадрате <math>\{ 1 ,\dots , N \}^2</math> содержало уголок, уместно рассматривать также порядок роста функции <math>N(\delta)</math>, или, наоборот, <math>\delta(N)</math> как максимальной плотности <math>\delta</math> для данного <math>N</math>, при которой возможно подмножество без уголков.
Если обозначить как <math>L(N)</math> плотность максимального подмножества квадрата <math>\{ 1 ,\dots , N \}^2</math>, не содержащего уголков, то основная теорема об уголках будет эквивалентна утверждению о том, что <math>L(N)=o(1)</math>, и уместно рассматривать более общий вопрос об улучшении верхних оценок на <math>L(N)</math>. Этот вопрос впервые поставил[4] Уильям Тимоти Гауэрс в 2001 году.
В 2002 году Ву Ха Ван доказал[5], что <math>L(N) \le \frac{100}{(\log_{*} (N))^{1/4}}</math>, где <math>\log_{*}</math> — операция, обратная к тетрации по основанию 2 в том же смысле, в котором натуральный логарифм является обратной операцией для экспоненты.
В 2005—2006 годах Илья Шкредов улучшил[6] эту оценку сначала до <math>L(N) = O\left({\frac{1}{(\log \log \log N)^{C_1}}}\right)</math>, а потом[7] и до <math>L(N) = O\left({\frac{1}{(\log \log N)^{C_2}}}\right)</math>, где <math>C_1</math> и <math>C_2</math> — некоторые абсолютные константы.
Связь с теоремой Рота
Теорему об уголках можно считать двумерным аналогом теоремы Рота (частного случая теоремы Семереди для прогрессий длины <math>3</math>), ведь в постановке задачи важным является именно равенство двух «сторон» прямоугольного уголка, точно так же как в определении арифметической прогрессии важно равенство двух разностей между соседними числами.
Шаблон:Рамка Теорема Рота (1953)
Для любого <math>\delta</math> существует такое <math>N=N(\delta)</math>, что если множество <math>A \subset \{{1,\dots,N}\}</math> имеет плотность <math>\frac{|A|}{N}>\delta</math>, то оно содержит арифметическую прогрессию, то есть тройку чисел <math>\{a-d,a,a+d\}</math> при некоторых <math>a</math> и <math>d \not = 0</math>. Шаблон:Конец рамки
Из теоремы об уголках можно вывести теорему Рота как прямое следствие.
Обобщение для групп
Кроме визуально представимых уголков на решётке <math>\{ 1 ,\dots , N \}^2</math> можно рассматривать обобщённые «уголки» вида <math>\{ (x,y), (x \circ d,y), (x, y \circ d) \}</math>, где <math>x,y,d \in G</math>, а <math>G</math> — некоторая группа с операцией <math>\circ</math>.
Для пространства <math>{\mathbb Z}_2^n</math>
Бен Грин в 2005 году рассмотрел[8][9][10] вопрос об уголках в группе <math>{\mathbb Z}_2^n</math>, то есть не для множества натуральных чисел. а для множества битовых (состоящих из нулей и единиц) последовательностей длины <math>n</math>, для которых вместо сложения используется побитовое исключающее или.
Шаблон:Рамка Теорема (Грин, 2005)
Для любого <math>\delta</math> существует такое <math>n=n(\delta)</math>, что если множество <math>A \subset {\mathbb Z}_2^n \times {\mathbb Z}_2^n</math> имеет плотность <math>\frac{|A|}{2^{2n}} \ge \delta</math>, то оно содержит уголок вида <math>\{(x,y),(x+d,y),(x,y+d)\}</math>, где <math>x,y,d \in {\mathbb Z}_2^n</math>, а сложение производится по модулю 2. Шаблон:Конец рамки
Шаблон:Hider = \sum \limits_{x \in E} {(-1)^{x \cdot \xi}}</math>, то малое значение <math>\max \limits_{\xi \not = 0} {\widehat{E} (\xi)}</math> в некотором смысле означает близость множества <math>E</math> некоторому случайно распределённому множеству той же плотности, что означает присутствие в нём большего количество структурированных подмножеств, чем во многих остальных. Если <math>\max \limits_{\xi \not = 0} {\widehat{E} (\xi)} < 2^n \alpha</math> для некоторого <math>\alpha</math>, то говорят, что множество <math>E</math> является <math>\alpha</math>-равномерным.
Для множества <math>A \subset E_1 \times E_2 \subset {\mathbb Z}_2^n \times {\mathbb Z}_2^n</math> имеет смысл рассматривать балансовую функцию <math>{f_A} (x,y) = [(x,y) \in A] - \rho [(x,y) \in E_1 \times E_2]</math>, где <math>\rho = \rho (A) = \frac{|A|}{|E_1| |E_2|}</math> - плотность множества, а выражение в квадратных скобках означает индикатор принадлежности множеству. Для балансовой функции определяется так называемая прямоугольная норма <math>\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)}</math>. Если величина этой нормы в некотором смысле достаточно мала, то это также означает близость <math>A</math> к случайному множеству. Если <math>\lVert{f_A}\rVert^4 < \alpha |E_1|^2 |E_2|^2</math>, то множество <math>A</math> называется <math>\alpha</math>-равномерным по прямоугольной норме.
Описание алгоритма
Доказательство производится от противного, то есть изначально предполагается, что множество <math>A</math> имеет плотность <math>\delta</math> и не содержит уголков. Доказательство представляет собой алгоритм последовательного перехода от множества <math>A</math> к его подмножеству, содержащемуся в произведении пространств меньшей размерности и имеющего там бо́льшую плотность. Дальше переход по той же схеме осуществвляется от этого подмножества к его же подмножеству, и так далее, пока в очередном подмножестве не найдётся арифметическая прогрессия (которая, очевидно, будет принадлежать и самому <math>A</math>). Остановка алгоритма в некоторый момент гарантируется тем, что плотность множества не может превышать единицу, а от множества плотности <math>\delta</math> переход производится к его подмножеству плотности (в некотором более узком пространстве) <math>\delta + 2^{-32} \delta^{24}</math>, так что через <math>2^{32} \delta^{-24}</math> сужений подмножества алгоритм завершает свою работу.
Очередное подмножество <math>A_i \subset A</math> рассматривается не только как <math>A_i \subset W_i \times W_i</math>, где <math>W_i \subset {\mathbb Z}_2^n</math> - некоторое подпространство, но и более узко, как <math>A_i \subset E_1^{(i)} \times E_2^{(i)}</math>, где множества <math>E_1^{(i)}, E_2^{(i)} \subset W_i</math> - произвольные множества, но имеющие малые коэффициенты Фурье. Формально можно условиться, что <math>A_0=A</math>, <math>W_0={\mathbb Z}_2^n</math>, <math>E_1^{(0)} = E_2^{(0)} = {\mathbb Z}_2^n</math>
Далее мы будем рассматривать отдельный шаг алгоритма, и обозначать плотности множеств <math>E</math> как <math>\beta_1 = \frac{E_1^{(i)}}{|W|}</math> и <math>\beta_2 = \frac{E_2^{(i)}}{|W|}</math>. Эти плотнсти также имеют значение при доказательстве.
Во всех трёх рассматриваемых далее случаях <math>\alpha</math>-равномерность множеств <math>E</math> имеется ввиду относительно текущего пространства <math>W_i</math>
На каждом отдельном этапе алгоитма возможны три случая:
Случай 1
Множества <math>E_1^{(i)}</math> и <math>E_2^{(i)}</math> являются <math>\alpha_1</math>-равномерными для некоторого <math>\alpha_1 = \alpha_1 (\delta, \beta_1, \beta_2)</math>. Множество <math>A_i</math> является <math>\alpha_2</math>-равномерным для некоторого <math>\alpha_2 = \alpha_2 (\delta)</math>.
В этом случае наличие уголков можно доказать буквально, не углубляясь к подмножествам. Более того, можно доказать что множество <math>A</math> содержит не менее <math>\frac{\delta^3 \beta_1 \beta_2}{2} |W|^3</math> уголков. Это лучшая по порядку роста оценка, поскольку количество уголков, очевидно, не может превышать <math>|W|^3</math> (ведь уголок определяется тремя числами, <math>x,y,d \in W</math>).
Случай 2
Множество <math>A</math> не является <math>\alpha_2</math>-равномерным для того же <math>\alpha_2</math>, что и в предыдущем случае.
Тоода оказывается возможным выбрать подмножества <math>F_1 \subset E_1</math>, <math>F_1 \subset E_2</math> такие, что их размер не намного меньше размеров <math>E_1, E_2</math> (уменьшается не более чем в <math>p(\frac{1}{\delta})</math> раз, где <math>p</math> - полином), а плотность множества <math>A</math> среди <math>F_1 \times F_2</math> значительно превышает его плотность среди <math>E_1 \times E_2</math> (превышает на <math>q(\delta)</math> где <math>q</math> - полином)
Случай 3
Одно из множеств <math>E_1^{(i)}, E_2^{(i)}</math> не является <math>\alpha_1</math>-равномерными (для того же <math>\alpha_1</math>, что и в первом случае).
Заметим, что этот случай не может возникать на самом первом шаге, так как <math>E_1^{(0)} = E_2^{(0)} = {\mathbb Z}_2^n</math>, а пространство относительно самого себя, конечно, всегда <math>0</math>-равномерно.
В этом случае используется прирост множества c предыдущего шага, а именно, если множество <math>A_i</math> имеет плотность <math>\delta_0+\tau</math> среди <math>E_1^{(i)} \times E_2^{(i)}</math>, то доказывается существование некоторого подпространства <math>W_{i+1} \subset W_i</math> и некоторых сдвигов множеств <math>E_1^{(i)}, E_2^{(i)}, A</math>, таких, что при переходе к их (сдвигов) пересечениям с этим подпространством новые одномерные множества оказываются <math>\sigma</math>-равномерными для произвольного заранее выбранного <math>\sigma</math>, а плотность нового двумерного множества оказывается не меньше, чем <math>\delta_0 + \frac{\tau}{4}</math>.
В качестве <math>\sigma</math> здесь можно выбрать <math>\alpha_1</math>, а в качестве <math>\tau</math> прирост множества, обеспеченный на предыдущем шаге алгоритма. Таким образом, мы лишь немного (в четыре раза) уменьшаем скорость прироста плотности множества <math>A</math> по ходу алгоритма, но зато обеспечиваем на каждом шаге <math>\alpha_1</math>-равномерность множеств <math>E_1^{(i)}, E_2^{(i)}</math>, а это позволяет нам утверждать, что случаями 1 и 2 исчерпываются все возможные случаи.
}}
Для произвольных абелевых групп
Илья Шкредов в 2009 году доказал обобщение для абелевых групп.[11]
Шаблон:Рамка Теорема
Существует абсолютная константа <math>c>0</math> такая, что если <math>(G,\circ)</math> — абелева группа, <math>A \subset G \times G</math>, то из <math>|A| \ge \frac{|G|^2}{({\log\log{|G|}})^c}</math> следует присутствие в <math>A</math> уголка <math>\{(x, y), (x \circ d, y), (x, y \circ d)\}</math> Шаблон:Конец рамки
Примечания
- ↑ M. Ajtai, E. Szemerédi: Sets of lattice points that form no squares, Studia Sci. Math. Hungar., 9(1974), 9-11Шаблон:Недоступная ссылка
- ↑ Proof of the corners theorem Шаблон:Wayback on polymath
- ↑ J. Solymosi: Note on a generalization of Roth’s theorem, Algorithms Combin., 25, 2003,Springer, Berlin, 825—827
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ И. Д. Шкредов, Теорема Семереди и задачи об арифметических прогрессиях Шаблон:Wayback, стр. 147—159
- ↑ Шаблон:Cite web
