Перегляд вихідного коду сторінки Теорема про кутики

[[Файл:Иллюстрация_уголков.png|міні|200x200пкс| Підмножина квадрата <math>6 \times 6</math> щільності <math>\frac{1}{2}</math> (рівно половина клітинок) із двома кутиками (виділено кольорами)]]
'''Теорема про кутики'''&nbsp;— доведений результат в галузі [[Адитивна комбінаторика|адитивної комбінаторики]], що стверджує наявність якоїсь упорядкованої (в арифметичному сенсі) структури, яку називають кутиком, у досить великих двовимірних множинах будь-якої фіксованої щільності.

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

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

Для підмножини двовимірної ґратки <math>A \subset \{{1,\dots,N}\}^2</math> визначимо її щільність як <math>{\rho_N} (A) = \frac{|A|}{N^2}</math>, тобто як частку клітинок, що належать множині, від усієї ґратки.{{Рамка}}
'''Теорема про кутики'''

Для будь-якого <math>\delta</math> існує таке <math>N=N(\delta)</math>, що якщо множина <math>A \subset \{{1,\dots,N}\}^2</math> має щільність <math>\rho_N (A) \ge \delta</math>, то вона містить кутик.
{{/рамка}}

== Історія покращення результатів ==
Теорема про кутики довели<ref>[https://dcg.epfl.ch/files/content/sites/dcg/files/courses/2017%20-%20Additive%20Combinatorics/AjtaiSzemeredi-1974-SetsOfLatticePointsThatFormNoSquares.pdf M. Ajtai, E. Szemerédi: Sets of lattice points that form no squares, ''Studia Sci. Math. Hungar.'', '''9'''(1974), 9-11]{{Недоступная ссылка|date=Февраль 2020|bot=InternetArchiveBot}}</ref> в 1974—1975 роках [[Миклош Айтаї]] та [[Ендре Семереді]]. 1981 року {{Iw|Гіллел Фюрстенберг||en|Hillel Furstenberg}} передовів цей результат, скориставшись методами [[Ергодичність|ергодичної теорії]]. Також існує<ref>J. Solymosi: Note on a generalization of Roth's theorem, ''Algorithms Combin.'', '''25''', 2003,Springer, Berlin, 825—827</ref> доведення Йожефа Шоймоші ({{Lang-hu|Jozsef Solymosi}}), що спирається на [[Лема про видалення графа|лему про видалення трикутника]] з [[Теорія графів|графа]].

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

Якщо позначити як <math>L(N)</math> щільність найбільшої підмножини квадрата <math>\{ 1 ,\dots, N \}^2</math>, що не містить кутиків, то основна теорема про кутики буде еквівалентна твердженню про те, що <math>L(N)=o(1)</math>, і доречно розглядати загальніше питання про покращення верхніх оцінок на <math>L(N)</math>. Це питання вперше поставив<ref>{{Cite web|url=https://zbmath.org/?q=an:1028.11005|title=A new proof of Szemerédi’s theorem|accessdate=2017-07-05|archivedate=2018-01-23|archiveurl=https://web.archive.org/web/20180123190623/https://zbmath.org/?q=an:1028.11005|deadurl=no}}</ref> [[Тімоті Гауерс|Вільям Тімоті Гауерс]] 2001 року.

2002 року {{Нп|Ван Ха Ву|3=en|4=Van H. Vu}} довів<ref>{{Cite web|url=https://zbmath.org/?q=an:1009.05130|title=Vu V. H, On a question of Gowers|accessdate=2017-07-05|archivedate=2018-01-09|archiveurl=https://web.archive.org/web/20180109181633/https://zbmath.org/?q=an:1009.05130|deadurl=no}}</ref>, що <math>L(N) \le \frac{100}{(\log_{*} (N))^{1/4}}</math>, де <math>\log_{*}</math>&nbsp;— операція, обернена до [[Тетрація|тетрації]] за основою 2 в тому сенсі, в якому [[натуральний логарифм]] є оберненою операцією для [[Експонента (функція)|експоненти]].

У 2005—2006 роках {{Нп|Шкредов Ілля Дмитрович|Ілля Шкредов|ru|Шкредов, Илья Дмитриевич}} покращив<ref>{{Cite web|url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=im&paperid=912&option_lang=rus|title=И. Д. Шкредов, Об одной задаче Гауэрса|accessdate=2017-07-05|archivedate=2018-01-09|archiveurl=https://web.archive.org/web/20180109181515/http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=im&paperid=912&option_lang=rus|deadurl=no}}</ref> цю оцінку спочатку до <math>L(N) = O\left({\frac{1}{(\log \log \log N)^{C_1}}}\right)</math>, а потім<ref>{{Cite web|url=https://arxiv.org/abs/math/0503639|title=I. D. Shkredov, On a Generalization of Szemeredi’s Theorem (препринт)|accessdate=2017-07-05|archivedate=2018-01-09|archiveurl=https://web.archive.org/web/20180109181544/https://arxiv.org/abs/math/0503639|deadurl=no}}</ref> і до <math>L(N) = O\left({\frac{1}{(\log \log N)^{C_2}}}\right)</math>, де <math>C_1</math> і <math>C_2</math>&nbsp;— деякі абсолютні сталі.

== Зв'язок з теоремою Рота ==
{{Докладніше|Теорема Рота}}
Теорему про кутики можна вважати двовимірним аналогом [[Теорема Рота|теореми Рота]] (часткового випадку [[Теорема Семереді|теореми Семереді]] для прогресій довжини <math>3</math>), адже в постановці задачі важливим є саме рівність двох «сторін» прямокутного кутика, так само як у визначенні [[Арифметична прогресія|арифметичної прогресії]] важлива рівність двох різниць між сусідніми числами.{{Рамка}}
''' Теорема Рота (1953) '''

Для будь-якого <math>\delta</math> існує таке <math>N=N(\delta)</math>, що якщо множина <math>A \subset \{{1,\dots,N}\}</math> має щільність <math>\frac{|A|}{N}>\delta</math>, то вона містить арифметичну прогресію, тобто трійку чисел <math>\{a-d,a,a+d\}</math> за деяких <math>a</math> і <math>d \not = 0</math>.
{{/рамка}}З теореми про кутики можна вивести теорему Рота як наслідок.
{{Hider|title=Доведення|title-style=text-align: left;|content-style=text-align: left;|hidden=1|content=[[Файл:Следствие теоремы Рота из теоремы об уголках.gif|thumb|Схематичне зображення зв'язку кутика та тричленної прогресії в побудові з доведення. Червоні лінії мають однакову довжину, оскільки число 2 рухається рівномірно вгору і вправо з кожною новою лінією. Отже, рівність сторін кутика, дає рівність різниць у прогресії]]

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

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

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

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

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

== Узагальнення для груп ==
Окрім візуально представлених кутиків на ґратці <math>\{ 1 ,\dots, N \}^2</math> можна розглядати узагальнені «кутики» вигляду <math>\{ (x,y), (x \circ d,y), (x, y \circ d) \}</math>, де <math>x,y,d \in G</math>, а <math>G</math>&nbsp;— деяка [[Група (математика)|група]] з операцією <math>\circ</math>.

=== Для простору <math>{\mathbb Z}_2^n</math> ===
{{Нп|Бен Ґрін|3=en|4=Ben Green (mathematician)}} 2005 року розглянув<ref>{{Cite web|url=http://www.ams.org/mathscinet-getitem?mr=2187732|title=Ben Green, «Finite field models in additive combinatorics»|accessdate=2017-07-05|archivedate=2017-06-13|archiveurl=https://web.archive.org/web/20170613213236/http://www.ams.org/mathscinet-getitem?mr=2187732|deadurl=no}}</ref><ref>{{Cite web|url=https://arxiv.org/abs/math/0409420|title=Ben Green, «Finite field models in arithmetic combinatorics» (препринт)|accessdate=2017-07-05|archivedate=2018-01-09|archiveurl=https://web.archive.org/web/20180109180956/https://arxiv.org/abs/math/0409420|deadurl=no}}</ref> питання про кутики в групі <math>{\mathbb Z}_2^n</math> тобто не для множини натуральних чисел, а для множини бітових (тобто, складених із нулів та одиниць) послідовностей довжини <math>n</math>, для яких замість додавання використовується побітове [[Виключна диз'юнкція|виключне або]].{{Рамка}}
''' Теорема (Ґрін, 2005) '''

Для будь-якого <math>\delta</math> існує таке <math>n=n(\delta)</math>, що якщо множина <math>A \subset {\mathbb Z}_2^n \times {\mathbb Z}_2^n</math> має щільність <math>\frac{|A|}{2^{2n}} \ge \delta</math>, то вона містить кутик вигляду <math>\{(x,y),(x+d,y),(x,y+d)\}</math>, де <math>x,y,d \in {\mathbb Z}_2^n</math>, а додавання виконується [[Виключна диз'юнкція|за модулем 2]].
{{/рамка}}{{Hider|title=Загальна схема доведення для <math>{\mathbb Z}_2^n</math>|hidden=1|title-style=text-align: left;|content-style=text-align: left;|content===== Показники рівномірності ====
У доведенні використано два показники рівномірності розподілу множин - один для "одновимірних" підмножин <math>E \subset {\mathbb Z}_2^n</math>, а інший для "двовимірних" <math>A \subset E_1 \times E_2</math>, де <math>E_1, E_2 \subset {\mathbb Z}_2^n</math>

Як показник рівномірності для одновимірних множин використовується в особливий спосіб адаптоване [[Дискретне перетворення Фур'є над скінченним полем|перетворення Фур'є]], де коефіцієнтами є [[корені з одиниці]], а замість множення використано аналог [[Скалярний добуток|скалярного добутку]] вигляду <math>\overline{x} \cdot \overline{y} = \sum \limits_{i=1}^{n} {x_i y_i}\pmod 2</math>. Якщо <math>\widehat{E} (\xi) = \sum \limits_{x \in E} {e^{-(x \cdot \xi) \pi i}} = \sum \limits_{x \in E} {(-1)^{x \cdot \xi}}</math>, то мале значення <math>\max \limits_{\xi \not = 0} {\widehat{E} (\xi)}</math> у деякому сенсі означає близькість множини <math>E</math> до деякої [[Схема Бернуллі|випадково розподіленої]] множини такої ж щільності, що означає наявність у ньому більшої кількості структурованих підмножин, ніж у багатьох інших. Якщо <math>\max \limits_{\xi \not = 0} {\widehat{E} (\xi)} < 2^n \alpha</math> для деякого <math>\alpha</math>, то кажуть, що множина <math>E</math> є <math>\alpha</math>-рівномірною.

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

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

Чергова підмножина <math>A_i \subset A</math> розглядається не лише як <math>A_i \subset W_i \times W_i</math>, де <math>W_i \subset {\mathbb Z}_2^n</math> - деякий підпростір, але й вужче, як <math>A_i \subset E_1^{(i)} \times E_2^{(i)}</math>, де множини <math>E_1^{(i)}, E_2^{(i)} \subset W_i</math> - довільні множини, але з малими коефіцієнтами Фур'є.
Формально можна домовитися, що <math>A_0=A</math>, <math>W_0={\mathbb Z}_2^n</math>, <math>E_1^{(0)} = E_2^{(0)} = {\mathbb Z}_2^n</math>

Далі ми розглядатимемо окремий крок алгоритму, і позначатимемо щільності множин <math>E</math> як <math>\beta_1 = \frac{E_1^{(i)}}{|W|}</math> і <math>\beta_2 = \frac{E_2^{(i)}}{|W|}</math>. Ці щільності також мають значення при доведенні.

У всіх трьох розглянутих нижче випадках <math>\alpha</math>-рівномірність множин <math>E</math> мається на увазі відносно поточного простору <math>W_i</math>.

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

==== Випадок 1 ====
Множини <math>E_1^{(i)}</math> і <math>E_2^{(i)}</math> є <math>\alpha_1</math>-рівномірними для деякого <math>\alpha_1 = \alpha_1 (\delta, \beta_1, \beta_2)</math>. Множина <math>A_i</math> є <math>\alpha_2</math>-рівномірною для деякого <math>\alpha_2 = \alpha_2 (\delta)</math>.

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

==== Випадок 2 ====
Множина <math>A</math> не є <math>\alpha_2</math>-рівномірною для того ж <math>\alpha_2</math>, що й у попередньому випадку.

Тоді виявляється можливим вибрати підмножини <math>F_1 \subset E_1</math>, <math>F_1 \subset E_2</math> такі, що їх розмір не набагато менший від розмірів <math>E_1, E_2</math> (зменшується не більше ніж у <math>p(\frac{1}{\delta})</math> разів, де <math>p</math> - [[поліном]]), а щільність множини <math>A</math> серед <math>F_1 \times F_2</math> значно перевищує її щільність серед <math>E_1 \times E_2</math> (перевищує на <math>q(\delta)</math> де <math>q</math> - поліном)

==== Випадок 3 ====
Одна з множин <math>E_1^{(i)}, E_2^{(i)}</math> не є <math>\alpha_1</math>-рівномірною (для того ж <math>\alpha_1</math>, що й у першому випадку).

Зауважимо, що цей випадок не може виникати на першому кроці, оскільки <math>E_1^{(0)} = E_2^{(0)} = {\mathbb Z}_2^n</math>, а простір відносно самого себе, звичайно, завжди <math>0</math>-рівномірний.

У цьому випадку використовується приріст множини з попереднього кроку, а саме, якщо множина <math>A_i</math> має щільність <math>\delta_0+\tau</math> серед <math>E_1^{(i)} \times E_2^{(i)}</math>, то доводиться існування деякого підпростору <math>W_{i+1} \subset W_i</math> і деяких [[Паралельне перенесення|зсувів]] множин <math>E_1^{(i)}, E_2^{(i)}, A</math>, таких, що при переході до їхніх (зсувів) перетинів із цим підпростором нові одновимірні множини виявляються <math>\sigma</math>-рівномірними для довільного раніше вибраного <math>\sigma</math>, а щільність нової двовимірної множини виявляється не меншою, ніж <math>\delta_0 + \frac{\tau}{4}</math>.

Як <math>\sigma</math> тут можна вибрати <math>\alpha_1</math>, а як <math>\tau</math> - приріст множини, забезпечений на попередньому етапі алгоритму. Таким чином, ми лише трохи (вчетверо) зменшуємо швидкість приросту щільності множини <math>A</math> по ходу алгоритму, але зате забезпечуємо на кожному кроці <math>\alpha_1</math>-рівномірність множин <math>E_1^{(i)}, E_2^{(i)}</math>, а це дозволяє нам стверджувати, що випадками 1 і 2 вичерпуються всі можливі випадки.}}

=== Для довільних абелевих груп ===
Ілля Шкредов 2009 року довів узагальнення для груп<ref>{{Cite web|url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=im&paperid=2657&option_lang=rus|title=И. Д. Шкредов, О двумерном аналоге теоремы Семереди в абелевых группах|accessdate=2017-07-05|archivedate=2018-01-09|archiveurl=https://web.archive.org/web/20180109235255/http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=im&paperid=2657&option_lang=rus|deadurl=no}}</ref>.{{Рамка}}
''' Теорема '''

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

== Примітки ==
{{примітки|2}}
[[Категорія:Арифметична комбінаторика]]
[[Категорія:Комбінаторика]]
[[Категорія:Теореми в теорії чисел]]
[[Категорія:1974 у науці]]
[[Категорія:1975 у науці]]
[[Категорія:1981 у науці]]