Теорема об уголках — доказанный результат в области аддитивной комбинаторики, утверждающий присутствие некой упорядоченной (в арифметическом смысле) структуры, называемой уголком, в достаточно больших двумерных множествах любой фиксированной плотности.
Для натуральных чисел фактически речь идёт о принадлежности достаточно плотному множеству клеток на двумерной решётке двух концов и точки излома прямого угла со сторонами одинаковой длины, параллельными осям координат.
Формулировка Теорема касается двумерной решётки и рассматривает множества пар чисел (координат в двумерном пространстве). Для натуральных чисел назовём тройку координат уголком. Будем говорить, что множество содержит некоторый уголок если оно содержит в себе все три точки этого уголка.
Для подмножества двумерной решётки определим его плотность как , то есть как долю клеток, принадлежащих множеству, среди всей решётки.
Теорема об уголках
Для любого существует такое , что если множество имеет плотность , то оно содержит уголок.
История улучшения результатов Теорема об уголках была доказанаM. Ajtai, E. Szemerédi: Sets of lattice points that form no squares, Studia Sci. Math. Hungar., 9(1974), 9-11Proof of the corners theorem on polymath и Эндре Семереди в 1974—1975 годах. В 1981 году этот результат был передоказан Хиллелом Фюрстенбергом с использованием методов эргодической теории. Также существуетJ. Solymosi: Note on a generalization of Roth’s theorem, Algorithms Combin., 25, 2003,Springer, Berlin, 825—827 доказательство Йожефа Шоймоши (), опирающееся на лемму об удалении треугольника из графа.
Кроме самого факта существования , достаточного для того, чтобы любое множество плотности в квадрате содержало уголок, уместно рассматривать также порядок роста функции , или, наоборот, как максимальной плотности для данного , при которой возможно подмножество без уголков.
Если обозначить как плотность максимального подмножества квадрата , не содержащего уголков, то основная теорема об уголках будет эквивалентна утверждению о том, что , и уместно рассматривать более общий вопрос об улучшении верхних оценок на . Этот вопрос впервые поставил Уильям Тимоти Гауэрс в 2001 году.
В 2002 году Ву Ха Ван доказал, что , где — операция, обратная к тетрации по основанию 2 в том же смысле, в котором натуральный логарифм является обратной операцией для экспоненты.
В 2005—2006 годах Илья Шкредов улучшил эту оценку сначала до , а потом и до , где и — некоторые абсолютные константы.
Связь с теоремой Рота Теорему об уголках можно считать двумерным аналогом теоремы Рота (частного случая теоремы Семереди для прогрессий длины ), ведь в постановке задачи важным является именно равенство двух «сторон» прямоугольного уголка, точно так же как в определении арифметической прогрессии важно равенство двух разностей между соседними числами.
Теорема Рота (1953)
Для любого существует такое , что если множество имеет плотность , то оно содержит арифметическую прогрессию, то есть тройку чисел при некоторых и .
Из теоремы об уголках можно вывести теорему Рота как прямое следствие.
Обобщение для групп Кроме визуально представимых уголков на решётке можно рассматривать обобщённые «уголки» вида , где , а — некоторая группа с операцией .
Для пространства ℤ2n Бен Грин в 2005 году рассмотрелИ. Д. Шкредов, Теорема Семереди и задачи об арифметических прогрессиях , стр. 147—159 вопрос об уголках в группе , то есть не для множества натуральных чисел. а для множества битовых (состоящих из нулей и единиц) последовательностей длины , для которых вместо сложения используется побитовое исключающее или.
Теорема (Грин, 2005)
Для любого существует такое , что если множество имеет плотность , то оно содержит уголок вида , где , а сложение производится по модулю 2.
Для произвольных абелевых групп Илья Шкредов в 2009 году доказал обобщение для абелевых групп.
Теорема
Существует абсолютная константа такая, что если — абелева группа, , то из следует присутствие в уголка
Примечания
Категория:Теоремы теории чисел Категория:Комбинаторика Категория:Арифметическая комбинаторика