WikiSort.ru - Не сортированное

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

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

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

Теорема касается двумерной решётки и рассматривает множества пар чисел (координат в двумерном пространстве). Для натуральных чисел $x,y,d\ (d\not =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)\geq \delta$ , то оно содержит уголок.

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

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

Кроме самого факта существования $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)$ . Этот вопрос впервые поставил^[4] Уильям Тимоти Гауэрс в 2001 году.

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

В 2005—2006 годах Илья Шкредов улучшил^[6] эту оценку сначала до $L(N)=O\left({\frac {1}{(\log \log \log N)^{C_{1}}}}\right)$ , а потом^[7] и до $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\not =0$ .

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

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

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

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

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

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

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

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

Кроме визуально представимых уголков на решётке $\{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 году рассмотрел^[8]^[9]^[10] вопрос об уголках в группе ${\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}}}\geq \delta$ , то оно содержит уголок вида $\{(x,y),(x+d,y),(x,y+d)\}$ , где $x,y,d\in {\mathbb {Z} }_{2}^{n}$ , а сложение производится по модулю 2.

Общая схема доказательства для

{\mathbb {Z} }_{2}^{n}

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

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

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

Для множества $A\subset E_{1}\times E_{2}\subset {\mathbb {Z} }_{2}^{n}\times {\mathbb {Z} }_{2}^{n}$ имеет смысл рассматривать балансовую функцию ${f_{A}}(x,y)=[(x,y)\in A]-\rho [(x,y)\in E_{1}\times E_{2}]$ , где $\rho =\rho (A)={\frac {|A|}{|E_{1}||E_{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$ к случайному множеству. Если $\lVert {f_{A}}\rVert ^{4}<\alpha |E_{1}|^{2}|E_{2}|^{2}$ , то множество $A$ называется $\alpha$ -равномерным по прямоугольной норме.

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

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

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

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

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

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

Случай 1

Множества $E_{1}^{(i)}$ и $E_{2}^{(i)}$ являются $\alpha _{1}$ -равномерными для некоторого $\alpha _{1}=\alpha _{1}(\delta ,\beta _{1},\beta _{2})$ . Множество $A_{i}$ является $\alpha _{2}$ -равномерным для некоторого $\alpha _{2}=\alpha _{2}(\delta )$ .

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

Случай 2

Множество $A$ не является $\alpha _{2}$ -равномерным для того же $\alpha _{2}$ , что и в предыдущем случае.

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

Случай 3

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

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

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

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

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

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

Теорема

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

Примечания

↑ 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 on polymath
↑ J. Solymosi: Note on a generalization of Roth’s theorem, Algorithms Combin., 25, 2003,Springer, Berlin, 825—827
↑ A new proof of Szemerédi’s theorem
↑ Vu V. H, On a question of Gowers
↑ И. Д. Шкредов, Об одной задаче Гауэрса
↑ I. D. Shkredov, On a Generalization of Szemeredi’s Theorem (препринт)
↑ Ben Green, «Finite field models in additive combinatorics»
↑ Ben Green, «Finite field models in arithmetic combinatorics» (препринт)
↑ И. Д. Шкредов, Теорема Семереди и задачи об арифметических прогрессиях, стр. 147—159
↑ И. Д. Шкредов, О двумерном аналоге теоремы Семереди в абелевых группах

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .

Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2025
WikiSort.ru - проект по пересортировке и дополнению контента Википедии

[1] M. Ajtai, E. Szemerédi: Sets of lattice points that form no squares, Studia Sci. Math. Hungar., 9(1974), 9-11

[2] Proof of the corners theorem on polymath

[3] J. Solymosi: Note on a generalization of Roth’s theorem, Algorithms Combin., 25, 2003,Springer, Berlin, 825—827

[4] A new proof of Szemerédi’s theorem

[5] Vu V. H, On a question of Gowers

[6] И. Д. Шкредов, Об одной задаче Гауэрса

[7] I. D. Shkredov, On a Generalization of Szemeredi’s Theorem (препринт)

[8] Ben Green, «Finite field models in additive combinatorics»

[9] Ben Green, «Finite field models in arithmetic combinatorics» (препринт)

[10] И. Д. Шкредов, Теорема Семереди и задачи об арифметических прогрессиях, стр. 147—159

[11] И. Д. Шкредов, О двумерном аналоге теоремы Семереди в абелевых группах