Теорема про кутики — доведений результат в галузі адитивної комбінаторики, що стверджує наявність якоїсь упорядкованої (в арифметичному сенсі) структури, яку називають кутиком, у досить великих двовимірних множинах будь-якої фіксованої щільності.
Для натуральних чисел фактично йдеться про належність досить щільній множині клітин на двовимірній ґратці двох кінців і точки зламу прямого кута зі сторонами однакової довжини, паралельними осям координат.
Формулювання Теорема стосується двовимірної ґратки і розглядає множину пар чисел (координат у двовимірному просторі). Для натуральних чисел назвемо трійку координат кутиком. Будемо говорити, що множина містить деякий кутик, якщо вона містить у собі всі три точки цього кутика.
Для підмножини двовимірної ґратки визначимо її щільність як , тобто як частку клітинок, що належать множині, від усієї ґратки. Теорема про кутики
Для будь-якого існує таке , що якщо множина має щільність , то вона містить кутик.
Історія покращення результатів Теорема про кутики довелиM. Ajtai, E. Szemerédi: Sets of lattice points that form no squares, Studia Sci. Math. Hungar., 9(1974), 9-11 в 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)
Для будь-якого існує таке , що якщо множина має щільність , то вона містить арифметичну прогресію, тобто трійку чисел за деяких і . З теореми про кутики можна вивести теорему Рота як наслідок.
Узагальнення для груп Окрім візуально представлених кутиків на ґратці можна розглядати узагальнені «кутики» вигляду , де , а — деяка група з операцією .
Для простору 2005 року розглянув питання про кутики в групі тобто не для множини натуральних чисел, а для множини бітових (тобто, складених із нулів та одиниць) послідовностей довжини , для яких замість додавання використовується побітове виключне або. Теорема (Ґрін, 2005)
Для будь-якого існує таке , що якщо множина має щільність , то вона містить кутик вигляду , де , а додавання виконується за модулем 2.
Для довільних абелевих груп Ілля Шкредов 2009 року довів узагальнення для груп. Теорема
Існує абсолютна стала така, що якщо — абелева група, , то з випливає наявність у кутика
Примітки