Задача Данцера — Ґрюнбаума

Задача Данцера — Ґрюнбаума — проблема комбінаторної геометрії, що ставить питання про те, яку найбільшу кількість точок можна розмістити в багатовимірному просторі, щоб вони не утворювали між собою прямих або тупих кутів. Відомо, що на площині можна розташувати щонайбільше три такі точки, в тривимірному просторі можна розташувати п'ять таких точок. 2017 року доведено, що у просторі розмірності $d$ можна розташувати Θ$(2^d)$ таких точок.

Постановка задачі

Шаблон:Рамка Для даного $d$ позначимо через $f(d)$ найбільшу кількість різних точок у $d$-вимірному просторі, таких що будь-які три точки утворюють гострокутний трикутник, тобто, для будь-яких трьох $x,y,z$ скалярний добуток $⟨y-x,z-x⟩>0$.

Як зростає $f(d)$ відносно $d$? Шаблон:/рамка Іншими словами, задача полягає в тому, щоб знайти просту формулу, яка виражає $f(d)$ через $d$ з якомога кращою точністю (а також знайти алгоритм побудови множини з $f(d)$ точок).

Множини, точки яких утворюють лише гострі кути, називають гострокутними множинами. Зауважимо, що з визначення випливає, що ніякі три точки в гострокутній множині не можуть лежати на одній прямій.

Станом на березень 2018 року відомо, що $2^{d-1}+1\le f(d)\le 2^d$.

Суміжні задачі

Множини без тупих кутів

Ердеш ще до появи класичного формулювання задачі Данцера — Ґрюнбаума поставив таку задачу:Шаблон:Рамка Для даного $d$ позначимо через $g(d)$ найбільшу кількість різних точок у $d$-вимірному просторі, ніякі три з яких не утворюють строго тупого кута, тобто для будь-яких трьох $x,y,z$ із яких $⟨y-x,z-x⟩\ge 0$.

Як зростає $g(d)$ відносно $d$? Шаблон:/рамкаВідомо що $g(d)=2^d$.

Вершини куба

У першій справді проривній роботі з цієї теми Ердеш і Фюреді побудували множину, що задовольняє заданим умовам, з вершин $d$-вимірного куба ${\left\{0,1\right\}}^d$. Тому в подальших роботах, що покращують їхній результат, іноді розглядалась окремо така задача:Шаблон:Рамка Для даного $d$ позначимо через $f_{◻}(d)$ найбільшу кількість різних вершин $d$-вимірного куба ${\left\{0,1\right\}}^d$, ніякі три з яких не утворюють ні прямого, ні тупого кута, тобто для будь-яких трьох $x,y,z$ із яких $⟨y-x,z-x⟩>0$

Як зростає $f_{◻}(d)$ відносно $d$? Шаблон:/рамка Очевидно, що $f_{◻}(d)\le f(d)$.

Історія вивчення

Перші згадки (Ердеш, 1948, 1957)

Історія задачі починається 1948 року, коли в розділі «Додаткові задачі для розв'язування» журналу "The American Mathematical Monthly " Пал Ердеш опублікував такий окремий випадок майбутньої задачі Данцера — Ґрюнбаума:Шаблон:Рамка Нехай дано вісім точок у просторі ${ℝ}^3$. Доведіть, що завжди можна знайти три з них, які не утворюють гострокутного трикутника. Шаблон:/рамка Тобто в задачі питалося, чи правильно, що $f(3)<8$.

1957 року в журналі Шаблон:Не перекладено, у статті з багатьма гіпотезами, Ердеш опублікував уже загальну гіпотезу, але щодо тупокутних множин. Шаблон:Рамка Нехай $S$ — множина з $2^d+1$ точок у просторі розмірності $k$. Чи правда, що тоді серед них обов'язково існують три точки, що утворюють тупий кут? Шаблон:/рамка Тобто, гіпотеза стверджувала, що $g(d)\le 2^d$.

У статті говорилося, що для $d=3$ доведення знайшли Шаблон:Нп і Бьордійк (Boerdijk), але їхнє доведення ще не опубліковано.

Поруч із гіпотезою містилося таке питання: Шаблон:Рамка Чи правда, що існує множина зі шести (семи) точок у тривимірному просторі таких, що будь-які три з них утворюють гострий кут? Шаблон:/рамка Або, іншими словами, чи правильно, що $f(3)\ge 6$ або $f(3)\ge 7$.

Перша гіпотеза (Данцер, Ґрюнбаум, 1962)

Першу загальну побудову для розв'язання цієї задачі виконали у статті 1962 року Шаблон:Не перекладено та Бранко Ґрюнбаум. Вони побудували в $d$-вимірному просторі $2d-1$ точку, матриця координат яких виглядала так (рядки — різні точки, стовпці — різні координати):

$\left(\begin{array}{cccccc}1& 0& 0& \cdots & 0& 0\\ -{\delta }_1& 1& 0& \cdots & 0& 0\\ -{\delta }_1& -1& 0& \cdots & 0& 0\\ -{\delta }_2& 0& 1& \cdots & 0& 0\\ -{\delta }_2& 0& -1& \cdots & 0& 0\\ ⋮& ⋮& \ddots & ⋮\\ -{\delta }_{d-2}& 0& 0& \cdots & 1& 0\\ -{\delta }_{d-2}& 0& 0& \cdots & -1& 0\\ -{\delta }_{d-1}& 0& 0& \cdots & 0& 1\\ -{\delta }_{d-1}& 0& 0& \cdots & 0& -1\end{array}\right)$

де ${\delta }_1,\dots ,{\delta }_{d-1}$ — попарно різні числа, менші від одиниці.

Простий комбінаторний перебір різних типів кутів, що виникають, дозволяє показати, що ніякі три з цих точок не утворюють прямих або тупих кутів. З цього виходить що $f(d)\ge 2d-1$

У цій праці автори висловили гіпотезу, що більшої кількості точок, для яких виконується ця умова, побудувати не можна, тобто що $f(d)=2d-1$.

Також у цій роботі доведено оцінку зверху $f(d)\le g(d)\le 2^d$, яку раніше припустив Ердеш.

Застосування імовірнісного методу (Ердеш, Фюреді, 1983)

1983 року Пал Ердеш і Шаблон:Не перекладено, скориставшись імовірнісним методом, спростували гіпотезу Данцера — Ґрюнбаума, показавши, що

$f(d)\ge f_{◻}(d)\ge \lfloor \frac{1}{2}{\left(\frac{2}{\sqrt{3}}\right)}^d\rfloor$

Це дозволило побудувати контрприклади до гіпотези Данцера — Ґрюнбаума для $d\ge 35$Шаблон:Sfn.

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

Основна ідея Ердеша і Фюреді полягала в тому, щоб вибрати множину точок, у якій (з додатною ймовірністю) буде дуже мало прямих і тупих кутів, а потім просто видалити по одній точці у кожного з цих кутів, тим самим усунувши їх усі.  Шаблон:Hider

Поліпшення сталої в оцінці Ердеша — Фюреді

Поліпшення без зміни методу

Навіть не змінюючи методу Ердеша в самій його суті, можна отримати кращу оцінку, просто вибравши інше число як параметр, який визначає, скільки випадкових точок слід вибирати.

Айґнер і Ціґлер 2003 року, описуючи теорему Ердеша у своїй оглядовій книзі «Доведення з Книги», виправили цей параметр і отримали, що $f_{◻}(d)\ge 2\lfloor \frac{\sqrt{6}}{9}{\left(\frac{2}{\sqrt{3}}\right)}^d\rfloor$.Шаблон:Sfn Це найкраще, що можна отримати в такий спосіб. Шаблон:Hidden

Беван (2006)

2006 року Д. Беван, трохи доповнивши побудову Ердеша — Фюреді, покращив оцінку до $f(d)\ge 2\lfloor \frac{1}{3}{\left(\frac{2}{\sqrt{3}}\right)}^{d+1}\rfloor$.

Однак, точки в його побудові не були вершинами одиничного куба, так що оцінку для $f_{◻}(d)$ він не покращив.  Шаблон:HiderКрім того, Беван отримав низку результатів для малих розмірностей $d$, що спростувало гіпотезу Данцера — Ґрюнбаума для $d\ge 7$.

Бучок (2009)

2009 року Лариса Бучок, не змінюючи методів Ердеша, Фюреді та Бевана для генерування точок, підрахувала акуратніше втрати від видалення точок, що беруть участь у негострих кутах. Виявилося, що це дозволяє отримати такі оцінки:

$f_{◻}(d)\ge \frac{3}{2}\lfloor \frac{11\sqrt{66}}{243}{\left(\frac{2}{\sqrt{3}}\right)}^d\rfloor$

$f(d)\ge \frac{3}{2}\lfloor \frac{22\sqrt{33}}{243}{\left(\frac{2}{\sqrt{3}}\right)}^d\rfloor$

Бучок (2009/2010)

2010 року Бучок опублікувала одразу два методи покращення попередніх нерівностей до результатів:

$f(d)\ge \frac{3}{2}\lfloor \frac{11\sqrt{165}}{243}{\left(\frac{2}{\sqrt{3}}\right)}^d\rfloor$

$f(d)\ge \frac{2}{3}\lfloor \sqrt{2}{\left(\frac{2}{\sqrt{3}}\right)}^d\rfloor$

Доведення другого результату отримано не пізніше 2009 року, оскільки його згадано в огляді з цієї темиШаблон:Sfn.

Поліпшення ймовірнісної схеми через гіперграфи (Аккерман, Бен-Цві, 2008/2009)

Поки інші математики працювали над елементарними покращеннями методу Ердеша, Ейял Аккерман та Орен Бен-Цві незалежно від них 2009 року опублікували отримане 2008 року доведення існування сталої $c>0$ такої, що

$f_{◻}(d)\ge c\sqrt{d}{\left(\frac{2}{\sqrt{3}}\right)}^d$

Це стало першим асимптотичним покращенням оцінки від часу статті Ердеша — Фюреді.

Доказ займало лише одну сторінку і полягало в застосуванні до побудови Ердеша — Фюреді однієї доведеної раніше алгоритмічної леми, яка стосується розміру незалежної множини в гіперграфі за особливих умов.

Поліпшення основи степеня (Харангі, 2011)

2011 року Харангі довів експоненційну оцінку з кращою основою степеня, а саме довів існування сталої $c>0$ такої, що

$f(n)\ge c{\left(\sqrt[10]{\frac{144}{23}}\right)}^d>c\cdot 1.201^d$

Його доведення також було деякою модифікацією побудови Ердеша — Фюреді.

Перша конкретна побудова (Захаров, 2017)

30 квітня 2017 року Дмитро Захаров, учень Андрія Райгородського, навчаючись у 10 класі, опублікував препринт явної (не імовірнісної) побудови, що складається з $2^{\lceil \frac{d}{2}\rceil }$ точок, які утворюють лише гострі кути.

Побудова Захарова не була розвитком методу Ердеша, а використовувала нову, просту, описану на одній сторінці, ідею.

У листопаді того ж року доведення опубліковано в журналі "Шаблон:Не перекладено ".

Оцінка через числа Фібоначчі (Захаров, 2017)

У липні 2017 року Захаров опублікував препринт роботи, яка доводить, що

$f(d)>F_n>c{\left(\frac{1+\sqrt{5}}{2}\right)}^d>c\cdot 1.618^d$

де $F_n$ — $n$-не число Фібоначчі, а $c>0$ — абсолютна стала. Друга нерівність випливає з формули Біне.

Оцінка порядку максимуму (Геренчер, Харангі, 2017)

Приклад побудови в ${ℝ}^3$ за методом Геренчера та Харангі

Поява праці Захарова спровокувала спроби пошуку найкращих контрприкладів для малих розмірностей. Було висловлено гіпотезу, що $f(d)\ge 2^{d-1}+1$, після чого побудовано приклади гострокутних множин, які доводять, що

$f(4)\ge 9$

$f(5)\ge 17$

Ідеєю, використаною при побудові цих прикладів, було невелике коливання точок $(d-1)$-вимірного куба в ${ℝ}^d$, зокрема й за останньою координатою, яка не відноситься до $(d-1)$-вимірного підпростору цього куба.

Ця ідея легко узагальнюється на старші розмірності, що й зробили Герінчер та Харангі. У вересні 2017 року вони випустили статтю, що доводить результат $f(d)\ge 2^{d-1}+1$ для будь-кого $d$. Як і розв'язок grizzly, їхній результат дозволяє будувати гострокутну множину даного розміру з точок, як завгодно близьких до вершин куба (віддалених від них не більше ніж на $\epsilon >0$). У цій статті також згадано обговорення на форумі.  Шаблон:Hider

Література

• Шаблон:Книга Шаблон:Wayback
• Шаблон:Книга