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

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

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


 Теорема касается двумерной решётки и рассмотривает множества пар чисел(координат в двумерном пространстве). Для натуральных чисел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), где C1 иC2 - некоторые абсолютные константы.

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


 Теорему об уголках можно считать двумерным аналогом теоремы Рота(частного случая теоремы Семереди для прогрессий длины 3), ведь впостановке задачи важным является именно равенство двух ``сторон''прямоугольного уголка, точно так же как в определении арифметическойпрогрессии важно равенство двух разностей между соседними числами.
 ''' Теорема Рота (1953) '''
 Для любого δ существует такое N=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\}$ такой плотности, не содержащее арифметическойпрогрессии, но аналогичной плотности для покрытия квадрата произвольногоразмера без образования уголков не существует. Нам нужно, исходя изэтого, прийти к противоречию.
 Рассмотрим для произвольного N такое множествоA{1,,N} (|A|>δN) и сконструируем по немудвумерное подмножество квадрата размера 2N, которое будетконтрпримером для теоремы об уголках, то есть будет иметь известнуюненулевую плотность и должно будет не содержать уголков.
 Таким множеством будет множество видаX={(a+(i1),i):i1,,N,aA}, то естьпоследовательность строк, представляющих последовательные сдвигимножества A. Если бы в таком множестве был уголок, то это означало бы,что во множестве A была арифметическая прогрессия длины 3, ведь Xсконструировано так, что, если (x,y+d)X, то и (xd,y)X, итогда, кроме уголка, в нём присутствует тройка (xd,y),(x,y),(x+d,y),отображающая арифметическую прогрессию в конкретную строку.
 Однако нашим изначальным предположением было, что в A нет такихпрогрессий. Значит, в X нет уголков. Теперь рассмотрим плотность X вквадрате {1,,2N}2. Так как сдвигов всего N, и они всевходят в множество полностью, то плотность равнаN|A|(2N)2>δN24N2=δ4.
 Итак, мы научились строить множество плотности δ4, несодержащее уголков, в квадрате любого размера. Однако это противоречитнашему изначальному предположению о том, что теорема об уголках верна.
 \}\}

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


 Кроме визуально представимых уголков на решётке {1,,N}2можно рассматривать обобщённые ``уголки'' вида{(x,y),(xd,y),(x,yd)}, где x,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\{