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

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

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

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

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

Теорема стосується двовимірної ґратки і розглядає множину пар чисел (координат у двовимірному просторі). Для натуральних чисел ${\displaystyle x,y,d\ (d\not =0)}$ назвемо трійку координат ${\displaystyle \{{(x,y),(x+d,y),(x,y+d)}\}}$ кутиком. Будемо говорити, що множина містить деякий кутик, якщо вона містить у собі всі три точки цього кутика.

Для підмножини двовимірної ґратки ${\displaystyle A\subset \{{1,\dots ,N}\}^{2}}$ визначимо її щільність як ${\displaystyle {\rho _{N}}(A)={\frac {|A|}{N^{2}}}}$, тобто як частку клітинок, що належать множині, від усієї ґратки.

Теорема про кутики Для будь-якого ${\displaystyle \delta }$ існує таке ${\displaystyle N=N(\delta )}$, що якщо множина ${\displaystyle A\subset \{{1,\dots ,N}\}^{2}}$ має щільність ${\displaystyle \rho _{N}(A)\geq \delta }$, то вона містить кутик.

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

Теорема про кутики довели в 1974—1975 роках Миклош Айтаї та Ендре Семереді. 1981 року ^[en] передовів цей результат, скориставшись методами ергодичної теорії. Також існує доведення Йожефа Шоймоші (угор. Jozsef Solymosi), що спирається на лему про видалення трикутника з графа.

Окрім самого факту існування ${\displaystyle N=N(\delta )}$, достатнього для того, щоб будь-яка множина щільності ${\displaystyle \delta }$ в квадраті ${\displaystyle \{1,\dots ,N\}^{2}}$ містила кутик, доречно розглядати також порядок зростання функції ${\displaystyle N(\delta )}$, або навпаки, ${\displaystyle \delta (N)}$ як найбільшої щільності ${\displaystyle \delta }$ для даного ${\displaystyle N}$, за якої можлива підмножина без кутиків.

Якщо позначити як ${\displaystyle L(N)}$ щільність найбільшої підмножини квадрата ${\displaystyle \{1,\dots ,N\}^{2}}$, що не містить кутиків, то основна теорема про кутики буде еквівалентна твердженню про те, що ${\displaystyle L(N)=o(1)}$, і доречно розглядати загальніше питання про покращення верхніх оцінок на ${\displaystyle L(N)}$. Це питання вперше поставив Вільям Тімоті Гауерс 2001 року.

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

У 2005—2006 роках ^[ru] покращив цю оцінку спочатку до ${\displaystyle L(N)=O\left({\frac {1}{(\log \log \log N)^{C_{1}}}}\right)}$, а потім і до ${\displaystyle L(N)=O\left({\frac {1}{(\log \log N)^{C_{2}}}}\right)}$, де ${\displaystyle C_{1}}$ і ${\displaystyle C_{2}}$ — деякі абсолютні сталі.

Зв'язок з теоремою Рота

Докладніше: Теорема Рота

Теорему про кутики можна вважати двовимірним аналогом теореми Рота (часткового випадку теореми Семереді для прогресій довжини ${\displaystyle 3}$), адже в постановці задачі важливим є саме рівність двох «сторін» прямокутного кутика, так само як у визначенні арифметичної прогресії важлива рівність двох різниць між сусідніми числами.

Теорема Рота (1953) Для будь-якого ${\displaystyle \delta }$ існує таке ${\displaystyle N=N(\delta )}$, що якщо множина ${\displaystyle A\subset \{{1,\dots ,N}\}}$ має щільність ${\displaystyle {\frac {|A|}{N}}>\delta }$, то вона містить арифметичну прогресію, тобто трійку чисел ${\displaystyle \{a-d,a,a+d\}}$ за деяких ${\displaystyle a}$ і ${\displaystyle d\not =0}$.

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

Доведення  

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

Для доведення від супротивного припустимо, що теорема про кутики істинна, а теорема Рота хибна, тобто є якась щільність ${\displaystyle \delta >0}$ така, що для будь-якого ${\displaystyle N}$ можна знайти підмножину ${\displaystyle A\subset \{1,\dots ,N\}}$ такої щільності, яка не містить арифметичної прогресії, але аналогічної щільності покриття квадрата довільного розміру без утворення кутиків немає. Нам потрібно, виходячи з цього, дійти суперечності.

Розглянемо для довільного ${\displaystyle N}$ таку множину ${\displaystyle A\subset \{1,\dots ,N\}}$ ${\displaystyle (|A|>\delta N)}$ і побудуємо за нею двовимірну підмножину квадрата розміру ${\displaystyle 2N}$, яка буде контрприкладом для теореми про кутики, тобто матиме відому ненульову щільність і має не містити кутиків.

Такою множиною буде множина вигляду ${\displaystyle X=\{(a+(i-1),i):i\in {1,\dots ,N},a\in A\}}$, тобто послідовність рядків, що представляють послідовні зсуви множини ${\displaystyle A}$. Якби в такій множині був кутик, то це означало б, що у множині ${\displaystyle A}$ була арифметична прогресія довжиною ${\displaystyle 3}$, адже ${\displaystyle X}$ побудовано так, що, якщо ${\displaystyle (x,y+d)\in X}$, то й ${\displaystyle (x-d,y)\in X}$, і тоді, крім кутика, в ній є трійка ${\displaystyle (x-d,y),(x,y),(x+d,y)}$, яка відображає арифметичну прогресію в конкретний рядок.

Однак нашим початковим припущенням було, що в ${\displaystyle A}$ немає таких прогресій. Отже, в ${\displaystyle X}$ немає кутиків. Тепер розглянемо щільність ${\displaystyle X}$ у квадраті ${\displaystyle \{1,\dots ,2N\}^{2}}$. Оскільки зсувів усього ${\displaystyle N}$, і вони всі входять у множину повністю, то щільність дорівнює ${\displaystyle {\frac {N|A|}{(2N)^{2}}}>{\frac {\delta N^{2}}{4N^{2}}}={\frac {\delta }{4}}}$.

Отже, ми навчилися будувати множину щільністю ${\displaystyle {\frac {\delta }{4}}}$, яка не містить кутиків, у квадраті довільного розміру. Однак це суперечить нашому початковому припущенню про те, що теорема про кутики істинна.

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

Окрім візуально представлених кутиків на ґратці ${\displaystyle \{1,\dots ,N\}^{2}}$ можна розглядати узагальнені «кутики» вигляду ${\displaystyle \{(x,y),(x\circ d,y),(x,y\circ d)\}}$, де ${\displaystyle x,y,d\in G}$, а ${\displaystyle G}$ — деяка група з операцією ${\displaystyle \circ }$.

Для простору ${\displaystyle {\mathbb {Z} }_{2}^{n}}$

^[en] 2005 року розглянув питання про кутики в групі ${\displaystyle {\mathbb {Z} }_{2}^{n}}$ тобто не для множини натуральних чисел, а для множини бітових (тобто, складених із нулів та одиниць) послідовностей довжини ${\displaystyle n}$, для яких замість додавання використовується побітове виключне або.

Теорема (Ґрін, 2005) Для будь-якого ${\displaystyle \delta }$ існує таке ${\displaystyle n=n(\delta )}$, що якщо множина ${\displaystyle A\subset {\mathbb {Z} }_{2}^{n}\times {\mathbb {Z} }_{2}^{n}}$ має щільність ${\displaystyle {\frac {|A|}{2^{2n}}}\geq \delta }$, то вона містить кутик вигляду ${\displaystyle \{(x,y),(x+d,y),(x,y+d)\}}$, де ${\displaystyle x,y,d\in {\mathbb {Z} }_{2}^{n}}$, а додавання виконується за модулем 2.

Загальна схема доведення для ${\displaystyle {\mathbb {Z} }_{2}^{n}}$  

Показники рівномірності

У доведенні використано два показники рівномірності розподілу множин - один для "одновимірних" підмножин ${\displaystyle E\subset {\mathbb {Z} }_{2}^{n}}$, а інший для "двовимірних" ${\displaystyle A\subset E_{1}\times E_{2}}$, де ${\displaystyle E_{1},E_{2}\subset {\mathbb {Z} }_{2}^{n}}$

Як показник рівномірності для одновимірних множин використовується в особливий спосіб адаптоване , де коефіцієнтами є корені з одиниці, а замість множення використано аналог скалярного добутку вигляду ${\displaystyle {\overline {x}}\cdot {\overline {y}}=\sum \limits _{i=1}^{n}{x_{i}y_{i}}{\pmod {2}}}$. Якщо ${\displaystyle {\widehat {E}}(\xi )=\sum \limits _{x\in E}{e^{-(x\cdot \xi )\pi i}}=\sum \limits _{x\in E}{(-1)^{x\cdot \xi }}}$, то мале значення ${\displaystyle \max \limits _{\xi \not =0}{{\widehat {E}}(\xi )}}$ у деякому сенсі означає близькість множини ${\displaystyle E}$ до деякої випадково розподіленої множини такої ж щільності, що означає наявність у ньому більшої кількості структурованих підмножин, ніж у багатьох інших. Якщо ${\displaystyle \max \limits _{\xi \not =0}{{\widehat {E}}(\xi )}<2^{n}\alpha }$ для деякого ${\displaystyle \alpha }$, то кажуть, що множина ${\displaystyle E}$ є ${\displaystyle \alpha }$-рівномірною.

Для множини ${\displaystyle A\subset E_{1}\times E_{2}\subset {\mathbb {Z} }_{2}^{n}\times {\mathbb {Z} }_{2}^{n}}$ є сенс розглядати балансову функцію ${\displaystyle {f_{A}}(x,y)=[(x,y)\in A]-\rho [(x,y)\in E_{1}\times E_{2}]}$, де ${\displaystyle \rho =\rho (A)={\frac {|A|}{|E_{1}||E_{2}|}}}$ - щільність множини, а вираз у квадратних дужках означає індикатор належності множині. Для балансової функції визначається так звана прямокутна норма ${\displaystyle \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})}}$. Якщо величина цієї норми у певному сенсі досить мала, це також означає близькість ${\displaystyle \lVert {f_{A}}\rVert ^{4}<\alpha |E_{1}|^{2}|E_{2}|^{2}}$, то множину ${\displaystyle A}$ називають ${\displaystyle \alpha }$-рівномірною за прямокутною нормою.

Опис алгоритму

Доведення виконується від супротивного, тобто спочатку припускається, що множина ${\displaystyle A}$ має щільність ${\displaystyle \delta }$ і не містить кутиків. Доведення являє собою алгоритм послідовного переходу від множини ${\displaystyle A}$ до її підмножини, яка міститься в добутку просторів меншої розмірності та має там більшу щільність. Далі перехід за тією ж схемою здійснюється від цієї підмножини до її підмножини, і так далі, поки в черговій підмножині не знайдеться арифметична прогресія (яка, очевидно, належатиме й самій ${\displaystyle A}$). Зупинка алгоритму в певний момент гарантується тим, що щільність множини не може перевищувати одиниці, а від множини щільності ${\displaystyle \delta }$ перехід виконується до її підмножини щільності (в деякому вужчому просторі) ${\displaystyle \delta +2^{-32}\delta ^{24}}$, так що через ${\displaystyle 2^{32}\delta ^{-24}}$ звужень підмножини алгоритм завершує свою роботу.

Чергова підмножина ${\displaystyle A_{i}\subset A}$ розглядається не лише як ${\displaystyle A_{i}\subset W_{i}\times W_{i}}$, де ${\displaystyle W_{i}\subset {\mathbb {Z} }_{2}^{n}}$ - деякий підпростір, але й вужче, як ${\displaystyle A_{i}\subset E_{1}^{(i)}\times E_{2}^{(i)}}$, де множини ${\displaystyle E_{1}^{(i)},E_{2}^{(i)}\subset W_{i}}$ - довільні множини, але з малими коефіцієнтами Фур'є. Формально можна домовитися, що ${\displaystyle A_{0}=A}$, ${\displaystyle W_{0}={\mathbb {Z} }_{2}^{n}}$, ${\displaystyle E_{1}^{(0)}=E_{2}^{(0)}={\mathbb {Z} }_{2}^{n}}$

Далі ми розглядатимемо окремий крок алгоритму, і позначатимемо щільності множин ${\displaystyle E}$ як ${\displaystyle \beta _{1}={\frac {E_{1}^{(i)}}{|W|}}}$ і ${\displaystyle \beta _{2}={\frac {E_{2}^{(i)}}{|W|}}}$. Ці щільності також мають значення при доведенні.

У всіх трьох розглянутих нижче випадках ${\displaystyle \alpha }$-рівномірність множин ${\displaystyle E}$ мається на увазі відносно поточного простору ${\displaystyle W_{i}}$.

На кожному окремому етапі алгоритму можливі три випадки:

Випадок 1

Множини ${\displaystyle E_{1}^{(i)}}$ і ${\displaystyle E_{2}^{(i)}}$ є ${\displaystyle \alpha _{1}}$-рівномірними для деякого ${\displaystyle \alpha _{1}=\alpha _{1}(\delta ,\beta _{1},\beta _{2})}$. Множина ${\displaystyle A_{i}}$ є ${\displaystyle \alpha _{2}}$-рівномірною для деякого ${\displaystyle \alpha _{2}=\alpha _{2}(\delta )}$.

У цьому випадку наявність кутиків можна довести буквально, не заглиблюючись до підмножин. Ба більше, можна довести, що множина ${\displaystyle A}$ містить не менше ${\displaystyle {\frac {\delta ^{3}\beta _{1}\beta _{2}}{2}}|W|^{3}}$ кутиків. Це найкраща за порядком зростання оцінка, оскільки кількість кутиків, очевидно, не може перевищувати ${\displaystyle |W|^{3}}$ (адже кутик визначається трьома числами, ${\displaystyle x,y,d\in W}$).

Випадок 2

Множина ${\displaystyle A}$ не є ${\displaystyle \alpha _{2}}$-рівномірною для того ж ${\displaystyle \alpha _{2}}$, що й у попередньому випадку.

Тоді виявляється можливим вибрати підмножини ${\displaystyle F_{1}\subset E_{1}}$, ${\displaystyle F_{1}\subset E_{2}}$ такі, що їх розмір не набагато менший від розмірів ${\displaystyle E_{1},E_{2}}$ (зменшується не більше ніж у ${\displaystyle p({\frac {1}{\delta }})}$ разів, де ${\displaystyle p}$ - поліном), а щільність множини ${\displaystyle A}$ серед ${\displaystyle F_{1}\times F_{2}}$ значно перевищує її щільність серед ${\displaystyle E_{1}\times E_{2}}$ (перевищує на ${\displaystyle q(\delta )}$ де ${\displaystyle q}$ - поліном)

Випадок 3

Одна з множин ${\displaystyle E_{1}^{(i)},E_{2}^{(i)}}$ не є ${\displaystyle \alpha _{1}}$-рівномірною (для того ж ${\displaystyle \alpha _{1}}$, що й у першому випадку).

Зауважимо, що цей випадок не може виникати на першому кроці, оскільки ${\displaystyle E_{1}^{(0)}=E_{2}^{(0)}={\mathbb {Z} }_{2}^{n}}$, а простір відносно самого себе, звичайно, завжди ${\displaystyle 0}$-рівномірний.

У цьому випадку використовується приріст множини з попереднього кроку, а саме, якщо множина ${\displaystyle A_{i}}$ має щільність ${\displaystyle \delta _{0}+\tau }$ серед ${\displaystyle E_{1}^{(i)}\times E_{2}^{(i)}}$, то доводиться існування деякого підпростору ${\displaystyle W_{i+1}\subset W_{i}}$ і деяких зсувів множин ${\displaystyle E_{1}^{(i)},E_{2}^{(i)},A}$, таких, що при переході до їхніх (зсувів) перетинів із цим підпростором нові одновимірні множини виявляються ${\displaystyle \sigma }$-рівномірними для довільного раніше вибраного ${\displaystyle \sigma }$, а щільність нової двовимірної множини виявляється не меншою, ніж ${\displaystyle \delta _{0}+{\frac {\tau }{4}}}$.

Як ${\displaystyle \sigma }$ тут можна вибрати ${\displaystyle \alpha _{1}}$, а як ${\displaystyle \tau }$ - приріст множини, забезпечений на попередньому етапі алгоритму. Таким чином, ми лише трохи (вчетверо) зменшуємо швидкість приросту щільності множини ${\displaystyle A}$ по ходу алгоритму, але зате забезпечуємо на кожному кроці ${\displaystyle \alpha _{1}}$-рівномірність множин ${\displaystyle E_{1}^{(i)},E_{2}^{(i)}}$, а це дозволяє нам стверджувати, що випадками 1 і 2 вичерпуються всі можливі випадки.

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

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

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

Примітки

1. M. Ajtai, E. Szemerédi: Sets of lattice points that form no squares, Studia Sci. Math. Hungar., 9(1974), 9-11^{[недоступне посилання з Февраль 2020]}
2. J. Solymosi: Note on a generalization of Roth's theorem, Algorithms Combin., 25, 2003,Springer, Berlin, 825—827
3. A new proof of Szemerédi’s theorem. оригіналу за 23 січня 2018. Процитовано 5 липня 2017.
4. Vu V. H, On a question of Gowers. оригіналу за 9 січня 2018. Процитовано 5 липня 2017.
5. И. Д. Шкредов, Об одной задаче Гауэрса. оригіналу за 9 січня 2018. Процитовано 5 липня 2017.
6. I. D. Shkredov, On a Generalization of Szemeredi’s Theorem (препринт). оригіналу за 9 січня 2018. Процитовано 5 липня 2017.
7. Ben Green, «Finite field models in additive combinatorics». оригіналу за 13 червня 2017. Процитовано 5 липня 2017.
8. Ben Green, «Finite field models in arithmetic combinatorics» (препринт). оригіналу за 9 січня 2018. Процитовано 5 липня 2017.
9. И. Д. Шкредов, О двумерном аналоге теоремы Семереди в абелевых группах. оригіналу за 9 січня 2018. Процитовано 5 липня 2017.