Задача Данцера — Ґрюнбаума — проблема комбінаторної геометрії, що ставить питання про те, яку найбільшу кількість точок можна розмістити в багатовимірному просторі, щоб вони не утворювали між собою прямих або тупих кутів. Відомо, що на площині можна розташувати щонайбільше три такі точки, в тривимірному просторі можна розташувати п'ять таких точок. 2017 року доведено, що у просторі розмірності можна розташувати Θ таких точок.
Постановка задачі
Для даного позначимо через найбільшу кількість різних точок у -вимірному просторі, таких що будь-які три точки утворюють гострокутний трикутник, тобто, для будь-яких трьох скалярний добуток .
Як зростає відносно ?
Іншими словами, задача полягає в тому, щоб знайти просту формулу, яка виражає через з якомога кращою точністю (а також знайти алгоритм побудови множини з точок).
Множини, точки яких утворюють лише гострі кути, називають гострокутними множинами. Зауважимо, що з визначення випливає, що ніякі три точки в гострокутній множині не можуть лежати на одній прямій.
Станом на березень 2018 року відомо, що .
Суміжні задачі
Множини без тупих кутів Ердеш ще до появи класичного формулювання задачі Данцера — Ґрюнбаума поставив таку задачуThe Michigan Mathematical Journal, Volume 4, Issue 3 (1957), 291—300, Paul Erdős, Some unsolved problems , с. 296, задача 19: Для даного позначимо через найбільшу кількість різних точок у -вимірному просторі, ніякі три з яких не утворюють строго тупого кута, тобто для будь-яких трьох із яких .
Як зростає відносно ? Відомо що .
Вершини куба У першій справді проривній роботі з цієї теми Ердеш і Фюреді побудували множину, що задовольняє заданим умовам, з вершин -вимірного куба . Тому в подальших роботах, що покращують їхній результат, іноді розглядалась окремо така задача: Для даного позначимо через найбільшу кількість різних вершин -вимірного куба , ніякі три з яких не утворюють ні прямого, ні тупого кута, тобто для будь-яких трьох із яких
Як зростає відносно ?
Очевидно, що .
Історія вивчення
Перші згадки (Ердеш, 1948, 1957) Історія задачі починається 1948 року, коли в розділі «Додаткові задачі для розв'язування» журналу "The American Mathematical Monthly " Пал Ердеш опублікував такий окремий випадок майбутньої задачі Данцера — ҐрюнбаумаThe American Mathematical Monthly, Vol. 55, No. 7, Aug. — Sep., 1948; Paul Erdos, Problems for Solution 4305-4309 , с. 431, задача 4306: Нехай дано вісім точок у просторі . Доведіть, що завжди можна знайти три з них, які не утворюють гострокутного трикутника.
Тобто в задачі питалося, чи правильно, що .
1957 року в журналі , у статті з багатьма гіпотезами, Ердеш опублікував уже загальну гіпотезу, але щодо тупокутних множин.
Нехай — множина з точок у просторі розмірності . Чи правда, що тоді серед них обов'язково існують три точки, що утворюють тупий кут?
Тобто, гіпотеза стверджувала, що .
У статті говорилося, що для доведення знайшли і Бьордійк (Boerdijk), але їхнє доведення ще не опубліковано.
Поруч із гіпотезою містилося таке питання:
Чи правда, що існує множина зі шести (семи) точок у тривимірному просторі таких, що будь-які три з них утворюють гострий кут?
Або, іншими словами, чи правильно, що або .
Перша гіпотеза (Данцер, Ґрюнбаум, 1962) Першу загальну побудову для розв'язання цієї задачі виконали у статті 1962 року та Бранко Ґрюнбаум. Вони побудували в -вимірному просторі точку, матриця координат яких виглядала так (рядки — різні точки, стовпці — різні координати):
де — попарно різні числа, менші від одиниці.
Простий комбінаторний перебір різних типів кутів, що виникають, дозволяє показати, що ніякі три з цих точок не утворюють прямих або тупих кутів. З цього виходить що
У цій праці автори висловили гіпотезу, що більшої кількості точок, для яких виконується ця умова, побудувати не можна, тобто що .
Також у цій роботі доведено оцінку зверху , яку раніше припустив Ердеш.
Застосування імовірнісного методу (Ердеш, Фюреді, 1983) 1983 року Пал Ердеш і , скориставшись імовірнісним методом, спростували гіпотезу Данцера — Ґрюнбаума, показавши, що
Це дозволило побудувати контрприклади до гіпотези Данцера — Ґрюнбаума для .
Однак, зважаючи на особливості ймовірнісного методу, їхнє доведення було неефективним і не дозволяло побудувати цю множину явно (крім як прямим перебором).
Основна ідея Ердеша і Фюреді полягала в тому, щоб вибрати множину точок, у якій (з додатною ймовірністю) буде дуже мало прямих і тупих кутів, а потім просто видалити по одній точці у кожного з цих кутів, тим самим усунувши їх усі.
Поліпшення сталої в оцінці Ердеша — Фюреді
Поліпшення без зміни методу Навіть не змінюючи методу Ердеша в самій його суті, можна отримати кращу оцінку, просто вибравши інше число як параметр, який визначає, скільки випадкових точок слід вибирати.
Айґнер і Ціґлер 2003 року, описуючи теорему Ердеша у своїй оглядовій книзі «Доведення з Книги», виправили цей параметр і отримали, що . Це найкраще, що можна отримати в такий спосіб.
Беван (2006) 2006 року Д. Беван, трохи доповнивши побудову Ердеша — Фюреді, покращив оцінку до .
Однак, точки в його побудові не були вершинами одиничного куба, так що оцінку для він не покращив. Крім того, Беван отримав низку результатів для малих розмірностей , що спростувало гіпотезу Данцера — Ґрюнбаума для .
Бучок (2009) 2009 року Лариса Бучок, не змінюючи методів Ердеша, Фюреді та Бевана для генерування точок, підрахувала акуратніше втрати від видалення точок, що беруть участь у негострих кутах. Виявилося, що це дозволяє отримати такі оцінки:
Бучок (2009/2010) 2010 року Бучок опублікувала одразу два методи покращення попередніх нерівностей до результатів:
Доведення другого результату отримано не пізніше 2009 року, оскільки його згадано в огляді з цієї теми.
Поліпшення ймовірнісної схеми через гіперграфи (Аккерман, Бен-Цві, 2008/2009) Поки інші математики працювали над елементарними покращеннями методу Ердеша, Ейял Аккерман та Орен Бен-Цві незалежно від них 2009 року опублікували отримане 2008 року доведення існування сталої такої, що
Це стало першим асимптотичним покращенням оцінки від часу статті Ердеша — Фюреді.
Доказ займало лише одну сторінку і полягало в застосуванні до побудови Ердеша — Фюреді однієї доведеної раніше алгоритмічної леми, яка стосується розміру незалежної множини в гіперграфі за особливих умовEyal Ackerman, Oren Ben-Zwi, «On sets of points that determine only acute angles», European Journal of Combinatorics, Volume 30, Issue 4, May 2009, Pages 908—910.
Поліпшення основи степеня (Харангі, 2011) 2011 року Харангі довів експоненційну оцінку з кращою основою степеня, а саме довів існування сталої такої, що
Його доведення також було деякою модифікацією побудови Ердеша — Фюреді.
Перша конкретна побудова (Захаров, 2017) 30 квітня 2017 року Дмитро Захаров, учень Андрія Райгородського, навчаючись у 10 класі, опублікував препринт явної (не імовірнісної) побудови, що складається з точок, які утворюють лише гострі кути.
Побудова Захарова не була розвитком методу Ердеша, а використовувала нову, просту, описану на одній сторінці, ідею.
У листопаді того ж року доведення опубліковано в журналі " ".
Оцінка через числа Фібоначчі (Захаров, 2017) У липні 2017 року Захаров опублікував препринт роботи, яка доводить, що
де — -не число Фібоначчі, а — абсолютна стала. Друга нерівність випливає з формули Біне.
Оцінка порядку максимуму (Геренчер, Харангі, 2017)
Поява праці Захарова спровокувала спроби пошуку найкращих контрприкладів для малих розмірностей. Було висловлено гіпотезу, що , після чого побудовано приклади гострокутних множин, які доводять, що
Ідеєю, використаною при побудові цих прикладів, було невелике коливання точок -вимірного куба в , зокрема й за останньою координатою, яка не відноситься до -вимірного підпростору цього кубаУлучшено (?) решение Эрдёша по остроугольным треугольникам; копия этой страницы приложена к .
Ця ідея легко узагальнюється на старші розмірності, що й зробили Герінчер та Харангі. У вересні 2017 року вони випустили статтю, що доводить результат для будь-кого . Як і розв'язок grizzly, їхній результат дозволяє будувати гострокутну множину даного розміру з точок, як завгодно близьких до вершин куба (віддалених від них не більше ніж на ). У цій статті також згадано обговорення на форумі.
Примітки
Література