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

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

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


 Теорема касается двумерной решётки и рассмотривает множества пар чисел (координат в двумерном пространстве). Для натуральных чисел x,y,d (d0)x,y,d (d0) назовём тройку координат {(x,y),(x+d,y),(x,y+d)}{(x,y),(x+d,y),(x,y+d)} уголком. Будем говорить, что множество содержит некоторый уголок если оно содержитт в себе все три точки этого уголка.
 Для подмножества двумерной решётки A{1,,N}2A{1,,N}2 определим его плотность как ${\rho_N} (A) = \frac{|
 {{рамка}} ''' Теорема об уголках '''
 Для любого \deltaсуществовуеттакоесуществовуеттакоеN=N(\delta),чтоеслимножество,чтоеслимножествоA \subset \{{1,\dots,N}\}^2имеетплотностьимеетплотность\rho_N (A) \ge \delta$, то оно содержит уголок.

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


 Теорема об уголках была доказана и Эндре Семереди в 1974-1975 годах. Более того, они доказали обязательность существования в множестве не только уголков, но и соответствующих им ``квадратов'', то есть четвёрок вида {(x,y),(x+d,y),(x,y+d),(x+d,y+d)}{(x,y),(x+d,y),(x,y+d),(x+d,y+d)}. В 1981 году этот результат был передоказан с использованием методов эргодической теории. Также существует доказательство Йожефа Шоймоши , опирающееся на лемму об удалении треугольника из графа.
 Кроме самого факта существования N=N(δ)N=N(δ), достаточного для того, чтобы любое множество плотности δδ в квадрате {1,,N}2{1,,N}2 содержало уголок, уместно рассматривать также порядок роста функции N(δ)N(δ), или, наоборот, δ(N)δ(N) как максимальной плотности δδ для данного NN, при которой возможно подмножество без уголков.
 Если обозначить как L(N)L(N) плотность максимального подмножества квадрата {1,,N}2{1,,N}2, не содержащего уголков, то основная теорема об уголках будет эквивалентна утверждению о том, что L(N)=o(1)L(N)=o(1), и уместно рассматривать более общий вопрос об улучшении верхних оценок на L(N)L(N). Этот вопрос впервые поставил Уильям Тимоти Гауэрс в 2001 году.
 В 2002 году Ву Ха Ван доказал, что L(N)100(log(N))1/4L(N)100(log(N))1/4, где loglog - операция, обратная к тетрации по основанию 2 в том же смысле, в котором натуральный логарифм является обратной операцией для экспоненты.
 В 2005-2006 годах Илья Шкредов улучшил эту оценку сначала до L(N)=O(1(logloglogN)C1)L(N)=O(1(logloglogN)C1), а потом и до L(N)=O(1(loglogN)C2)L(N)=O(1(loglogN)C2), где C1C1 и C2C2 - некоторые абсолютные константы.

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


 Теорему об уголках можно считать двумерным аналогом теоремы Рота (частного случая теоремы Семереди для прогрессий длины 33), ведь в постановке задачи важным является именно равенство двух ``сторон'' прямоугольного уголка, точно так же как в определении арифметической прогрессии важно равенство двух разностей между соседними числами.
 ''' Теорема Рота (1953) '''
 Для любого δδ существует такое N=N(δ)N=N(δ), что если множество A{1,,N}A{1,,N} имеет плотность $\frac{| {{конец рамки}}
 Из теоремы об уголках можно вывести теорему Рота как прямое следствие.
 {{Hider| title = Доказательство| hidden = 1 | title-style = text-align: left; | content-style = text-align: left; | content =

 Для доказательства от противного предположим, что теорема об уголках верна, а теорема Рота не верна, то есть существует какая-то плотность \delta > 0такая,чтодлялюбоготакая,чтодлялюбогоNможнонайтиподмножествоможнонайтиподмножествоA \subset \{1,\dots,N\}$ такой плотности, не содержащее арифметической прогрессии, но аналогичной плотности для покрытия квадрата произвольного размера без образования уголков не существует. Нам нужно, исходя из этого, прийти к противоречию.
 Рассмотрим для произвольного NN такое множество A{1,,N}A{1,,N} (|A|>δN)(|A|>δN) и сконструируем по нему двумерное подмножество квадрата размера 2N2N, которое будет контрпримером для теоремы об уголках, то есть будет иметь известную ненулевую плотность и должно будет не содержать уголков.
 Таким множеством будет множество вида X={(a+(i1),i):i1,,N,aA}X={(a+(i1),i):i1,,N,aA}, то есть последовательность строк, представляющих последовательные сдвиги множества AA. Если бы в таком множестве был уголок, то это означало бы, что во множестве AA была арифметическая прогрессия длины 33, ведь XX сконструировано так, что, если (x,y+d)X(x,y+d)X, то и (xd,y)X(xd,y)X, и тогда, кроме уголка, в нём присутствует тройка (xd,y),(x,y),(x+d,y)(xd,y),(x,y),(x+d,y), отображающая арифметическую прогрессию в конкретную строку.
 Однако нашим изначальным предположением было, что в AA нет таких прогрессий. Значит, в XX нет уголков. Теперь рассмотрим плотность XX в квадрате {1,,2N}2{1,,2N}2. Так как сдвигов всего NN, и они все входят в множество полностью, то плотность равна N|A|(2N)2>δN24N2=δ4N|A|(2N)2>δN24N2=δ4.
 Итак, мы научились строить множество плотности δ4δ4, не содержащее уголков, в квадрате любого размера. Однако это противоречит нашему изначальному предположению о том, что теорема об уголках верна.
 \}\}

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


 Кроме визуально представимых уголков на решётке {1,,N}2{1,,N}2 можно рассматривать обобщённые ``уголки'' вида {(x,y),(xd,y),(x,yd)}{(x,y),(xd,y),(x,yd)}, где x,y,dGx,y,dG, а G - некоторая группа с операцией .

Для пространства ${\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{| {{конец рамки}}
 {{Hider| title = Общая схема доказательства для {\mathbb Z}_2^n$
 \texttt hidden = 1 \\\texttt title-style = text-align: left; \\\texttt content-style = text-align: left; \\\texttt content =

agraphПоказатели равномерности
 В доказательстве используются два показателя равномерности распределения множеств - один для ``одномерных'' подмножеств EZn2, а другой для ``двумерных'' AE1×E2, где E1,E2Zn2
 В качестве показателя равномерности для одномерных множеств используется специальным образом адаптированное преобразование Фурье, где в качестве коэффициентов используются корни из единицы, а в место умножения - аналог скалярного произведения вида ¯x¯y=ni=1xiyi(mod2). Если ˆE(ξ)=xEe(xξ)πi=xE(1)xξ, то малое значение maxξ0ˆE(ξ) в некотором смысле означает близость множества E некоторому случайно распределённому множеству той же плотности, что означает присутствие в нём большего количество структурированных подмножеств, чем во многих остальных. Если maxξ0ˆE(ξ)<2nα для некоторого α, то говорят, что множество E является α-равномерным.
 Для множества AE1×E2Zn2×Zn2 имеет смысл рассматривать балансовую функцию fA(x,y)=[(x,y)A]ρ[(x,y)E1×E2], где $\rho = \rho (A) = \frac{|
 ==== Описание алгоритма ==== Доказательство производится от противного, то есть изначально предполагается, что множество Aимеетплотность\deltaинесодержитуголков.ДоказательствопредставляетсобойалгоритмпоследовательногопереходаотмножестваAкегоподмножеству,содержащемусявпроизведениипространствменьшейразмерностииимеющеготамбольшуюплотность.Дальшепереходпотойжесхемеосуществвляетсяотэтогоподмножествакегожеподмножеству,итакдалее,покавочередномподмножествененайдётсяарифметическаяпрогрессия(которая,очевидно,будетпринадлежатьисамомуA).Остановкаалгоритмавнекоторыймоментгарантируетсятем,чтоплотностьмножестванеможетпревышатьединицу,аотмножестваплотности\deltaпереходпроизводитсякегоподмножествуплотности(внекоторомболееузкомпространстве)\delta + 2^{-32} \delta^{24},такчточерез2^{32} \delta^{-24}$ сужений подмножества алгоритм завершает свою работу.
 Очередное подмножество AiA рассматривается не только как AiWi×Wi, где WiZn2 - некоторое подпространство, но и более узко, как AiE(i)1×E(i)2, где множества E(i)1,E(i)2Wi - произвольные множества, но имеющие малые коэффициенты Фурье. Формально можно условиться, что A0=A, W0=Zn2, E(0)1=E(0)2=Zn2
 Далее мы будем рассматривать отдельный шаг алгоритма, и обозначать плотности множеств E как $\beta_1 = \frac{E_1^{(i)}}{|
 Во всех трёх рассматриваемых далее случаях \alphaравномерностьмножествEимеетсяввидуотносительнотекущегопространстваW_i$
 На каждом отдельном этапе алгоитма возможны три случая:

agraphСлучай 1
 Множества E(i)1 и E(i)2 являются α1-равномерными для некоторого α1=α1(δ,β1,β2). Множество Ai является α2-равномерным для некоторого α2=α2(δ).
 В этом случае наличие уголков можно доказать буквально, не углубляясь к подмножествам. Более того, можно доказать что множество A содержит не менее δ3β1β22|W|3 уголков. Это лучшая по порядку роста оценка, поскольку количество уголков, очевидно, не может превышать |W|3 (ведь уголок определяется тремя числами, x,y,dW).

agraphСлучай 2
 Множество A не является α2-равномерным для того же α2, что и в предыдущем случае.
 Тоода оказывается возможным выбрать подмножества F1E1, F1E2 такие, что их размер не намного меньше размеров E1,E2 (уменьшается не более чем в p(1δ) раз, где p - полином), а плотность множества A среди F1×F2 значительно превышает его плотность среди E1×E2 (превышает на q(δ) где q - полином)

agraphСлучай 3
 Одно из множеств E(i)1,E(i)2 не является α1-равномерными (для того же α1, что и в первом случае).
 Заметим, что этот случай не может возникать на самом первом шаге, так как E(0)1=E(0)2=Zn2, а пространство относительно самого себя, конечно, всегда 0-равномерно.
 В этом случае используется прирост множества c предыдущего шага, а именно, если множество Ai имеет плотность δ0+τ среди E(i)1×E(i)2, то доказывается существование некоторого подпространства Wi+1Wi и некоторых сдвигов множеств E(i)1,E(i)2,A, таких, что при переходе к их (сдвигов) пересечениям с этим подпространством новые одномерные множества оказываются σ-равномерными для произвольного заранее выбранного σ, а плотность нового двумерного множества оказывается не меньше, чем δ0+τ4.
 В качестве σ здесь можно выбрать α1, а в качестве τ прирост множества, обеспеченный на предыдущем шаге алгоритма. Таким образом, мы лишь немного (в четыре раза) уменьшаем скорость прироста плотности множества A по ходу алгоритма, но зато обеспечиваем на каждом шаге α1-равномерность множеств E(i)1,E(i)2, а это позволяет нам утверждать, что случаями 1 и 2 исчерпываются все возможные случаи.
 \}\}

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


 Илья Шкредов в 2009 году доказал обобщеие для абелевых групп.
 ''' Теорема '''
 Существует абсолютная константа c>0 такая, что если (G,) - абелева группа, AG×G, то из A \{ge \{frac\{