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

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

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

Для даного ${\displaystyle d}$ позначимо через ${\displaystyle f(d)}$ найбільшу кількість різних точок у ${\displaystyle d}$-вимірному просторі, таких що будь-які три точки утворюють (гострокутний трикутник), тобто, для будь-яких трьох ${\displaystyle x,y,z}$ скалярний добуток ${\displaystyle \langle {y-x,z-x}\rangle >0}$. Як зростає ${\displaystyle f(d)}$ відносно ${\displaystyle d}$?

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

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

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

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

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

Ердеш ще до появи класичного формулювання задачі Данцера — Ґрюнбаума поставив таку задачу:

Для даного ${\displaystyle d}$ позначимо через ${\displaystyle g(d)}$ найбільшу кількість різних точок у ${\displaystyle d}$-вимірному просторі, ніякі три з яких не утворюють строго тупого кута, тобто для будь-яких трьох ${\displaystyle x,y,z}$ із яких ${\displaystyle \langle {y-x,z-x}\rangle \geq 0}$. Як зростає ${\displaystyle g(d)}$ відносно ${\displaystyle d}$?

Відомо що ${\displaystyle g(d)=2^{d}}$.

Вершини куба

У першій справді проривній роботі з цієї теми Ердеш і Фюреді побудували множину, що задовольняє заданим умовам, з вершин ${\displaystyle d}$-вимірного куба ${\displaystyle {\left\lbrace {0,1}\right\rbrace }^{d}}$. Тому в подальших роботах, що покращують їхній результат, іноді розглядалась окремо така задача:

Для даного ${\displaystyle d}$ позначимо через ${\displaystyle f_{\square }(d)}$ найбільшу кількість різних вершин ${\displaystyle d}$-вимірного куба ${\displaystyle \left\lbrace {0,1}\right\rbrace ^{d}}$, ніякі три з яких не утворюють ні прямого, ні тупого кута, тобто для будь-яких трьох ${\displaystyle x,y,z}$ із яких ${\displaystyle \langle {y-x,z-x}\rangle >0}$ Як зростає ${\displaystyle f_{\square }(d)}$ відносно ${\displaystyle d}$?

Очевидно, що ${\displaystyle f_{\square }(d)\leq f(d)}$.

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

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

Історія задачі починається 1948 року, коли в розділі «Додаткові задачі для розв'язування» журналу "The American Mathematical Monthly " Пал Ердеш опублікував такий окремий випадок майбутньої задачі Данцера — Ґрюнбаума:

Нехай дано вісім точок у просторі ${\displaystyle {\mathbb {R} }^{3}}$. Доведіть, що завжди можна знайти три з них, які не утворюють гострокутного трикутника.

Тобто в задачі питалося, чи правильно, що ${\displaystyle f(3)<8}$.

1957 року в журналі ^[en], у статті з багатьма гіпотезами, Ердеш опублікував уже загальну гіпотезу, але щодо тупокутних множин.

Нехай ${\displaystyle S}$ — множина з ${\displaystyle 2^{d}+1}$ точок у просторі розмірності ${\displaystyle k}$. Чи правда, що тоді серед них обов'язково існують три точки, що утворюють тупий кут?

Тобто, гіпотеза стверджувала, що ${\displaystyle g(d)\leq 2^{d}}$.

У статті говорилося, що для ${\displaystyle d=3}$ доведення знайшли ^[en] і Бьордійк (Boerdijk), але їхнє доведення ще не опубліковано.

Поруч із гіпотезою містилося таке питання:

Чи правда, що існує множина зі шести (семи) точок у тривимірному просторі таких, що будь-які три з них утворюють гострий кут?

Або, іншими словами, чи правильно, що ${\displaystyle f(3)\geq 6}$ або ${\displaystyle f(3)\geq 7}$.

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

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

${\displaystyle {\begin{pmatrix}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\\\vdots &\vdots &\ddots &\vdots \\-\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{pmatrix}}}$

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

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

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

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

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

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

${\displaystyle f(d)\geq f_{\square }(d)\geq \left\lfloor {{\frac {1}{2}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}}\right\rfloor }$

Це дозволило побудувати контрприклади до гіпотези Данцера — Ґрюнбаума для ${\displaystyle d\geq 35}$.

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

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

 

Короткий опис ідеї доведення  

Доведення Ердеша та Фюреді полягало в тому, щоб вибрати випадково і незалежно одна від одної ${\displaystyle 2n}$ точок із одиничного куба ${\displaystyle \left\lbrace {0,1}\right\rbrace ^{d}}$, де ${\displaystyle n=\left\lfloor {{\frac {1}{2}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}}\right\rfloor }$ і довести, що за такого вибору ймовірність того, що серед них виявляться лише ${\displaystyle n}$ тупокутних або вироджених трикутників, додатна.

Під випадковим вибором точки тут мають на увазі її генерування за схемою Бернуллі з імовірністю ${\displaystyle p={\frac {1}{2}}}$ генерування одиниці чи нуля для тієї чи іншої координати точки незалежно від інших координат.

Для підтвердження оцінки кількості тупокутних трикутників використовували властивість лінійності математичного сподівання. Імовірність того, що конкретна трійка точок утворює прямий кут, дорівнює ${\displaystyle \left({\frac {3}{4}}\right)^{d}}$ - це легко довести, розглядаючи окремо внесок кожної координати до скалярного добутку. Помноживши цю ймовірність на кількість таких трійок, отримаємо значення математичного сподівання, а це вже дасть, згідно з нерівністю Маркова, додатну ймовірність того, що випадкова величина його не перевищує.

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

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

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

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

Доведення

Метод Ердеша для кількості ${\displaystyle k}$ вибираних точок встановлював, що хоча б раз серед них знайдеться не більше ${\displaystyle 3{\binom {k}{3}}{\left({\frac {3}{4}}\right)}^{n}\leq {\frac {k^{3}}{2}}{\left({\frac {3}{4}}\right)}^{d}}$ гострих кутів.

Це гарантує існування множини з ${\displaystyle h(k)=k-{\frac {k^{3}}{2}}{\left({\frac {3}{4}}\right)}^{d}}$ точок без прямих і тупих кутів.

Якщо взяти похідну і прооптимізувати цю функцію за ${\displaystyle k}$, то отримаємо

${\displaystyle h'(k)=1-{\frac {3}{2}}{\left({\frac {3}{4}}\right)}^{d}k^{2}}$

${\displaystyle k^{2}={\frac {2}{3}}{\left({\frac {4}{3}}\right)}^{d}}$

${\displaystyle k_{best}={\sqrt {\frac {2}{3}}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}}$

${\displaystyle h(k_{best})={\left({\frac {2}{\sqrt {3}}}\right)}^{d}{\sqrt {\frac {2}{3}}}\left({1-{\frac {2}{3}}\cdot {\frac {1}{2}}}\right)={\left({\frac {2}{\sqrt {3}}}\right)}^{d}{\sqrt {\frac {2}{3}}}\cdot {\frac {2}{3}}={\frac {2{\sqrt {6}}}{9}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}}$

Беван (2006)

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

Однак, точки в його побудові не були вершинами одиничного куба, так що оцінку для ${\displaystyle f_{\square }(d)}$ він не покращив.

 

Короткий опис ідеї доведення  

У побудові Бевана до кожної з вибраних випадкових точок додавався дуже короткий випадковий вектор (для кожної свій), неперервно і рівномірно розподілений у ${\displaystyle d}$-вимірному кубі ${\displaystyle [-\varepsilon ;\varepsilon ]^{d}}$ для деякого достатньо малого ${\displaystyle \varepsilon }$.

Беван ввів кілька лем, які показують, що деякі многочлени від рівномірно і симетрично відносно нуля розподілених випадкових величин (що розглядаються як нова випадкова величина) мають імовірність бути додатними не меншу, ніж${\displaystyle {\frac {1}{2}}}$. Ці леми дозволили показати, що більш, ніж у половині випадків, зсув на додаткові вектори не робить гострим кут між точками, розміщеними до цього під прямим кутом (оскільки зміна скалярного добутку, що є кількісним показником гостроти кута, виражається через многочлени від координат додаткових векторів).

Все це дозволило посилити оцінку математичного сподівання кількості негострих кутів і показати, що серед вибраних випадково ${\displaystyle k}$ точок може бути лише ${\displaystyle {\frac {3}{2}}{\binom {k}{3}}{\left({\frac {3}{4}}\right)}^{n}}$ негострих кутів.

Крім того, Беван отримав низку результатів для малих розмірностей ${\displaystyle d}$, що спростувало гіпотезу Данцера — Ґрюнбаума для ${\displaystyle d\geq 7}$.

Бучок (2009)

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

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

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

Короткий опис ідеї доведення

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

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

Все це дозволяє, знаючи, що серед ${\displaystyle k}$ точок є ${\displaystyle s}$ негострих кутів, побудувати гострокутну множину з ${\displaystyle k-{\frac {k}{3}}-{\frac {3}{4}}\left({s-{\frac {k}{3}}}\right)={\frac {11}{12}}k-{\frac {3}{4}}s}$ точок, на відміну від тривіальної оцінки, коли вибирається лише ${\displaystyle k-s}$ точок.

Бучок (2009/2010)

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

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

Короткий опис ідеї доведення

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

Як і в методі Ердеша та Фюреді, Бучок вибирає точки випадково, і кожну координату незалежно, за схемою Бернуллі, але не з імовірностями

${\displaystyle P(v_{i}=0)=P(v_{i}=1)={\frac {1}{2}}}$

а з більшим числом варіантів, з імовірностями

${\displaystyle P(v_{i}=0)=P(v_{i}=1)=P(v_{i}=-\varepsilon _{i})=P(v_{i}=1+\varepsilon _{i})={\frac {1}{4}}}$

де ${\displaystyle \varepsilon _{1},\dots ,\varepsilon _{n}}$ - досить малі числа (окреме число для кожної координати), які задовольняють умови

${\displaystyle \sum \limits _{i=1}^{d}{(\varepsilon _{i}+{\varepsilon _{i}}^{2})}<1}$

${\displaystyle \varepsilon _{j}^{2}>\sum \limits _{i=j+1}^{d}{(\varepsilon _{i}+{\varepsilon _{i}}^{2})},1\leq j\leq d-1}$

Все це дозволяє через перебір 64 варіантів змінення внеску тієї чи іншої координати скалярного добутку знизити ймовірність того, що деякі точки утворюють негострий кут, до ${\displaystyle {\frac {2}{5}}{\left({\frac {3}{4}}\right)}^{d}+{\frac {3}{5}}{\left({\frac {7}{16}}\right)}^{d}}$ на відміну від стандартної ${\displaystyle {\left({\frac {3}{4}}\right)}^{d}}$ у методі Ердеша - Фюреді та відповідно знизити математичне сподівання кількості негострих кутів.

Після цього можна застосувати техніку Бучок для видалення тупих кутів з попередньої праці, що завершує доведення.

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

Краткое описание идеи доказательства

На відміну від першого методу з цієї праці, який полягав у зміненні самого алгоритму вибору випадкових точок, другий метод пропонував звичайний вибір за схемою Ердеша - Фюреді з імовірностями ${\displaystyle P(v_{i}=0)=P(v_{i}=1)={\frac {1}{2}}}$ для кожної координати кожної точки. Основний виграш при цьому давало "розумне" підсування точок у найкращій комбінації (з найменшою кількістю тупих кутів).

Як і в першому методі, точки підсувалися на вектор малої фіксованої довжини ${\displaystyle \varepsilon >0}$ (достатньо взяти ${\displaystyle \varepsilon <{\frac {1}{4}}}$) в бік від куба, але тільки за однією координатою і строго залежно від того, чи існують для даної центральної точки тупого кута інші тупі кути, для яких вона є бічною точкою (тобто, як і в першій праці Бучок, прямокутні трикутники поділялися на перетинні й неперетинні, але аналізувалися трохи інакше, ніж у першій праці).

Точніше кажучи, всі точки найкращої комбінації поділялися на чотири класи за задоволенням властивостей:

• ${\displaystyle Q_{1}}$: всі кути з вершиною в цій точці - гострі;
• ${\displaystyle Q_{2}}$: точка є вершиною хоча б одного прямого кута, і всі гострі кути з вершиною в цій точці належать гострокутним трикутникам;
• ${\displaystyle Q_{3}}$: точка є вершиною хоча б одного прямого кута і рівно одного гострого кута прямокутного трикутника;
• ${\displaystyle Q_{4}}$: точка є вершиною хоча б одного прямого кута і не менше ніж двох гострих кутів прямокутних трикутників.

Точки, які задовольняють властивість ${\displaystyle Q_{4}}$, просто видалялися з набору (оскільки їх може бути багато), а координати решти змінювалися, як описано вище.

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

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

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

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

${\displaystyle f_{\square }(d)\geq c{\sqrt {d}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}}$

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

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

Короткий опис ідеї доведення

Аккерман і Цві використали окремий випадок леми з огляду Бертрам-Кретцберг і Лефман про алгоритмічні аспекти пошуку незалежних множин у гіперграфах. Розглянутий окремий випадок стверджував таке:

Нехай дано сталі ${\displaystyle c,\varepsilon >0}$. Нехай ${\displaystyle H}$ — гіперграф, усі ребра якого складаються з трьох вершин, який містить ${\displaystyle n}$ вершин і середній степінь вершин якого не перевищує ${\displaystyle t^{2}}$, де ${\displaystyle t\to \infty }$ при ${\displaystyle n\to \infty }$. Нехай також кількість пар ребер типу ${\displaystyle \left({\left\lbrace {a,b,c}\right\rbrace ,\left\lbrace {a,b,d}\right\rbrace }\right)}$ (своєрідних «циклів» у сенсі гіперграфа) не перевищує ${\displaystyle cnt^{3-\varepsilon }}$. Тоді можна за поліноміальний від${\displaystyle n}$ час знайти в ${\displaystyle H}$ незалежну множину вершин розміру ${\displaystyle \Omega \left({\frac {n{\sqrt {\log t}}}{t}}\right)}$

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

Незалежна множина точок у такому гіперграфі якраз і буде множиною, що не містить тупокутних трикутників, і вона при виборі параметрів ${\displaystyle n=c_{1}{\left({\frac {2}{\sqrt {3}}}\right)}^{{\frac {101}{100}}d},t=c_{2}{\left({\frac {2}{\sqrt {3}}}\right)}^{\frac {d}{100}}}$ має розмір ${\displaystyle \Omega \left({{\sqrt {d}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}}\right)}$

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

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

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

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

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

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

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

У листопаді того ж року доведення опубліковано в журналі "^[en] ".

Короткий опис ідеї доведення

Метод Захарова полягав у тому, щоб будувати множину точок рекурентно. При цьому перехід здійснювався від множини для простору розмірності ${\displaystyle d}$ до множини для простору розмерності ${\displaystyle d+2}$

За основу брався принцип побудови куба (або паралелепіпеда), коли всі точки "копіюються" і копії переносяться на деяку відстань за новим виміром, ортогональним усім відрізкам між точками в попередній побудові (і взагалі всім прямим у попередньому просторі). Це збільшило б кількість точок удвічі і змінило б величини кутів, що були (для кутів, точки яких належать різним копіям) лише ненабагато (скалярний добуток зміниться не більше, ніж на величину, пропорційну квадрату зсуву за новим виміром). Однак за такої побудови виникають прямі кути вигляду ${\displaystyle \angle {v_{2}v_{1}w_{1}}}$, де ${\displaystyle v_{1}}$ і ${\displaystyle v_{2}}$ - різні копії однієї точки.

Щоб позбутися прямих кутів, Захаров проводив зсув відразу за двома новими вимірами, на вектор однієї довжини, але в різні боки, причому рухалися за новими вимірами обидві копії кожної точки, на відміну від побудови куба, коли всі точки попередньої побудови залишаються в межах колишнього свого простору. Все це дозволило трохи "скосити" виниклі "вертикальні" (протяжні за новим уведеним виміром) відрізки між точками щоб позбутися від кутів, утворених ними з відрізками, які лежать виключно в попередньому просторі, меншої розмірності.

Конкретніше, маючи множину ${\displaystyle S}$ в ${\displaystyle {\mathbb {R} }^{d}}$ без прямих і тупих кутів, Захаров вибирає для кожної точки ${\displaystyle x\in S}$ двовимірний вектор ${\displaystyle \phi (x)=\left({\alpha (x),\beta (x)}\right)}$ достатньо малої (і, що важливо, однакової для всіх) довжини, причому так, щоб виконувалося ${\displaystyle \phi (x)\not =\pm \phi (y)}$ для будь-яких різних ${\displaystyle x,y\in S}$. Тоді, за досить малої довжини векторів ${\displaystyle \phi (x)}$ можна довести, що точки множини

${\displaystyle S'=\left\lbrace {(x_{1},\dots ,x_{d},\alpha (x),\beta (x)):x\in S}\right\rbrace \cup \left\lbrace {(x_{1},\dots ,x_{d},-\alpha (x),-\beta (x)):x\in S}\right\rbrace }$

також не утворюють прямих або тупих кутів (а те, що ці множини не перетинаються. очевидно з побудови${\displaystyle \phi (x)}$).

Це доводить рекурентну залежність ${\displaystyle f(d+2)\geq 2f(d)}$ і, за індукцією, всю теорему.

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

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

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

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

Короткий опис ідеї доведення

Ідея була така ж, що й у першій роботі - копіювання точок із наступним зсувом на досить малий двовимірний вектор за новими розмірностями.

Однак тепер розглядалася комбінація точок у ${\displaystyle d}$-вимірній множині, серед яких ${\displaystyle f(d-1)}$ точок (найбільша можлива кількість) лежали в деякій одній гіперплощині ${\displaystyle H\subset {\mathbb {R} }^{d}}$ розмірності ${\displaystyle d-1}$. Відповідно, операція з копіюванням і зсувом здійснювалася тільки для них, причому нові розмірності вводилися ортогональними ${\displaystyle H}$, так що внаслідок операції загальна кількість розмірностей збільшувалася лише на одиницю, а для кількості точок виходив рекурентний вираз

${\displaystyle f(n+1)=f(n)+f(n-1)}$

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

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

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

${\displaystyle f(4)\geq 9}$

${\displaystyle f(5)\geq 17}$

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

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

 

Короткий опис ідеї доведення  

Для формалізації доведення використано дві леми:

• підсуванням однієї з точок ${\displaystyle (d-1)}$-вимірного куба на як завгодно малу відстань можна зробити гострими всі кути, що містили цю точку (кути, для яких точка була бічною, зникають через властивості куба, а кути, де ця точка центральною, не стають тупими завдяки додатковому зміщенню точки за ${\displaystyle d}$-тою координатою);
• для будь-якої скінченної множини точок існує ${\displaystyle \varepsilon >0}$ таке, що підсування будь-якої з точок у будь-який бік на відстань менше ${\displaystyle \varepsilon }$ не робить утворювані точками множини гострі кути прямими або тупими. Це твердження доводиться через взяття мінімуму з усіх додатних скалярних добутків відрізків кутів між точками з цієї множини. Оскільки у "найгіршого" кута скалярний добуток все одно буде додатним, то він має допустимі межі змінювання.

Далі для кожної вершини куба робилося таке:

• з'ясовувалося, за якого ${\displaystyle \varepsilon }$ наявні гострі кути не буде пошкоджено;
• ця вершина підсувалася в потрібний бік на вектор довжини меншої від ${\displaystyle \varepsilon }$ так, щоб тупі кути з нею стали гострими.

В кінці додавалася ще одна точка, дуже віддалена від куба за ${\displaystyle d}$-тою координатою, яка за рештою координат збігалася з центром куба. Кути, утворені цією точкою з іншими, також виявлялися гострими.

Примітки

1. The Michigan Mathematical Journal, Volume 4, Issue 3 (1957), 291—300, Paul Erdős, Some unsolved problems [ 2018-06-03 у Wayback Machine.], с. 296, задача 19
2. The American Mathematical Monthly, Vol. 55, No. 7, Aug. — Sep., 1948; Paul Erdos, Problems for Solution 4305-4309 [ 2018-08-28 у Wayback Machine.], с. 431, задача 4306
3. Райгородский А.М. Остроугольные множества // Квант. — 2018. — Вып. 3 (7 июля). — С. 10–13.
4. (PDF). Архів оригіналу (PDF) за 28 серпня 2018. Процитовано 19 березня 2018.
5. Райгородский, 2009.
6. Айгнер, 2006, с. 93—94.
7. D. Bevan, «Sets of Points Determining Only Acute Angles and Some Related Colouring Problems», Electron. J. Combin., 13:1 (2006), 24 p. оригіналу за 2 травня 2018. Процитовано 19 березня 2018.
8. Л. В. Бучок, «Остроугольные треугольники Данцера — Грюнбаума», УМН, 2009, том 64, выпуск 3(387), страницы 181—182. оригіналу за 3 червня 2018. Процитовано 19 березня 2018.
9. Л. В. Бучок, «О двух новых подходах к получению оценок в проблеме Данцера — Грюнбаума, Матем. заметки, 2010, том 87, выпуск 4, страницы 519—527». оригіналу за 12 травня 2018. Процитовано 19 березня 2018.
10. Райгородский, 2009, с. 21.
11. 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
12. Claudia Bertram-Kretzberg, Hanno Lefmann, "The Algorithmic Aspects of Uncrowded Hypergraphs", SIAM J. Comput., 29(1), 201–230
13. Viktor Harangi, «Acute Sets In Euclidean Spaces», SIAM J. Discrete Math., 25(3), 1212—1229. оригіналу за 31 травня 2019. Процитовано 19 березня 2018.
14. arXiv:1705.01171 D. Zakharov, «Acute sets». оригіналу за 28 серпня 2018. Процитовано 19 березня 2018.
15. Dmitriy Zakharov, «Acute Sets», «Discrete & Computational Geometry». оригіналу за 10 червня 2018. Процитовано 19 березня 2018.
16. D. Zakharov, «Acute sets». оригіналу за 28 серпня 2018. Процитовано 19 березня 2018.
17. Улучшено (?) решение Эрдёша по остроугольным треугольникам; копия этой страницы приложена к arXiv:0906.0290
18. arXiv:1709.03411, Balázs Gerencsér, Viktor Harangi, «Acute sets of exponentially optimal size». оригіналу за 28 серпня 2018. Процитовано 19 березня 2018.
19. Трунин, Дмитрий. Посетители форума улучшили оценку Эрдёша. N + 1 — главное издание о науке, технике и технологиях (рос.). Процитовано 22 січня 2024.

Література

• Райгородский, А. М.. Остроугольные треугольники Данцера — Грюнбаума. — М. : МЦНМО, 2009. — 31 с. — . Архівовано травень 8, 2018 на сайті Wayback Machine.
• Айгнер М. Циглер Г. Доказательства из Книги. Лучшие доказательства со времен Евклида до наших дней. — Мир, 2006.