Теорема про кутики

Підмножина квадрата $6\times 6$ щільності $\frac{1}{2}$ (рівно половина клітинок) із двома кутиками (виділено кольорами)

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

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

Формулювання

Теорема стосується двовимірної ґратки і розглядає множину пар чисел (координат у двовимірному просторі). Для натуральних чисел $x,y,d(d=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)\ge \delta$, то вона містить кутик. Шаблон:/рамка

Історія покращення результатів

Теорема про кутики довели в 1974—1975 роках Миклош Айтаї та Ендре Семереді. 1981 року Шаблон:Iw передовів цей результат, скориставшись методами ергодичної теорії. Також існує доведення Йожефа Шоймоші (Шаблон:Lang-hu), що спирається на лему про видалення трикутника з графа.

Окрім самого факту існування $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)$. Це питання вперше поставив Вільям Тімоті Гауерс 2001 року.

2002 року Шаблон:Нп довів, що $L(N)\le \frac{100}{({\log }_{*}(N){)}^{1/4}}$, де ${\log }_{*}$ — операція, обернена до тетрації за основою 2 в тому сенсі, в якому натуральний логарифм є оберненою операцією для експоненти.

У 2005—2006 роках Шаблон:Нп покращив цю оцінку спочатку до $L(N)=O\left(\frac{1}{(\log \log \log N{)}^{C_1}}\right)$, а потім і до $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=0$. Шаблон:/рамкаЗ теореми про кутики можна вивести теорему Рота як наслідок. Шаблон:Hider

Узагальнення для груп

Окрім візуально представлених кутиків на ґратці $\{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 року розглянув питання про кутики в групі ${\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}}\ge \delta$, то вона містить кутик вигляду $\{(x,y),(x+d,y),(x,y+d)\}$, де $x,y,d\in {\mathbb{Z}}_2^n$, а додавання виконується за модулем 2. Шаблон:/рамкаШаблон:Hider

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

Ілля Шкредов 2009 року довів узагальнення для груп.Шаблон:Рамка Теорема

Існує абсолютна стала $c>0$ така, що якщо $(G,\circ )$ — абелева група, $A\subset G\times G$, то з $|A|\ge \frac{|G{|}^2}{(\log \log |G|{)}^c}$ випливає наявність у $A$ кутика $\{(x,y),(x\circ d,y),(x,y\circ d)\}$ Шаблон:/рамка