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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Подмножество квадрата плотности (ровно половина клеток) с двумя уголками (выделены цветами)

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

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

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

[править | править код]

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

Для подмножества двумерной решётки определим его плотность как , то есть как долю клеток, принадлежащих множеству, среди всей решётки.

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

Для любого существует такое , что если множество имеет плотность , то оно содержит уголок.

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

[править | править код]

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

Кроме самого факта существования , достаточного для того, чтобы любое множество плотности в квадрате содержало уголок, уместно рассматривать также порядок роста функции , или, наоборот, как максимальной плотности для данного , при которой возможно подмножество без уголков.

Если обозначить как плотность максимального подмножества квадрата , не содержащего уголков, то основная теорема об уголках будет эквивалентна утверждению о том, что , и уместно рассматривать более общий вопрос об улучшении верхних оценок на . Этот вопрос впервые поставил[4] Уильям Тимоти Гауэрс в 2001 году.

В 2002 году Ву Ха Ван доказал[5], что , где  — операция, обратная к тетрации по основанию 2 в том же смысле, в котором натуральный логарифм является обратной операцией для экспоненты.

В 2005—2006 годах Илья Шкредов улучшил[6] эту оценку сначала до , а потом[7] и до , где и  — некоторые абсолютные константы.

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

[править | править код]

Теорему об уголках можно считать двумерным аналогом теоремы Рота (частного случая теоремы Семереди для прогрессий длины ), ведь в постановке задачи важным является именно равенство двух «сторон» прямоугольного уголка, точно так же как в определении арифметической прогрессии важно равенство двух разностей между соседними числами.

Теорема Рота (1953)

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

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

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

[править | править код]

Кроме визуально представимых уголков на решётке можно рассматривать обобщённые «уголки» вида , где , а  — некоторая группа с операцией .

Для пространства

[править | править код]

Бен Грин в 2005 году рассмотрел[8][9][10] вопрос об уголках в группе , то есть не для множества натуральных чисел. а для множества битовых (состоящих из нулей и единиц) последовательностей длины , для которых вместо сложения используется побитовое исключающее или.

Теорема (Грин, 2005)

Для любого существует такое , что если множество имеет плотность , то оно содержит уголок вида , где , а сложение производится по модулю 2.

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

[править | править код]

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

Теорема

Существует абсолютная константа такая, что если  — абелева группа, , то из следует присутствие в уголка

Примечания

[править | править код]
  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 Архивная копия от 30 августа 2012 на Wayback Machine 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 июля 2017. Архивировано 23 января 2018 года.
  5. Vu V. H, On a question of Gowers. Дата обращения: 5 июля 2017. Архивировано 9 января 2018 года.
  6. И. Д. Шкредов, Об одной задаче Гауэрса. Дата обращения: 5 июля 2017. Архивировано 9 января 2018 года.
  7. I. D. Shkredov, On a Generalization of Szemeredi’s Theorem (препринт). Дата обращения: 5 июля 2017. Архивировано 9 января 2018 года.
  8. Ben Green, «Finite field models in additive combinatorics». Дата обращения: 5 июля 2017. Архивировано 13 июня 2017 года.
  9. Ben Green, «Finite field models in arithmetic combinatorics» (препринт). Дата обращения: 5 июля 2017. Архивировано 9 января 2018 года.
  10. И. Д. Шкредов, Теорема Семереди и задачи об арифметических прогрессиях Архивная копия от 24 июля 2018 на Wayback Machine, стр. 147—159
  11. И. Д. Шкредов, О двумерном аналоге теоремы Семереди в абелевых группах. Дата обращения: 5 июля 2017. Архивировано 9 января 2018 года.