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

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

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

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

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

Теорема стосується двовимірної ґратки і розглядає множину пар чисел (координат у двовимірному просторі). Для натуральних чисел $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$, то вона містить кутик.

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

Теорема про кутики довели в 1974—1975 роках Миклош Айтаї та Ендре Семереді. 1981 року Гіллел Фюрстенберг передовів цей результат, скориставшись методами ергодичної теорії. Також існує доведення Йожефа Шоймоші (угор. 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)$. Це питання вперше поставив Вільям Тімоті Гауерс 2001 року.

2002 року Ван Ха Ву довів, що $L(N)\leq {\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\not =0$.

З теореми про кутики можна вивести теорему Рота як наслідок.

Доведення  

Схематичне зображення зв'язку кутика та тричленної прогресії в побудові з доведення. Червоні лінії мають однакову довжину, оскільки число 2 рухається рівномірно вгору і вправо з кожною новою лінією. Отже, рівність сторін кутика, дає рівність різниць у прогресії

Для доведення від супротивного припустимо, що теорема про кутики істинна, а теорема Рота хибна, тобто є якась щільність $\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 року розглянув питання про кутики в групі ${\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})}$. Якщо величина цієї норми у певному сенсі досить мала, це також означає близькість $\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$-рівномірний.

У цьому випадку використовується приріст множини з попереднього кроку, а саме, якщо множина $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 року довів узагальнення для груп.

Теорема Існує абсолютна стала $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)\}$