Множина Данцера

Побудова двовимірної множини Данцера зі швидкістю зростання $O(n^2\log n)$ з накладених прямокутних сіток зі співвідношеннями сторін 1:1, 1:9, 1:81, і т. д.

Множина́ Да́нцера — множина точок, що дотикається до будь-якого опуклого тіла одиничного об'єму. Шаблон:Нп поставив питання, чи можлива така множина обмеженої щільностіШаблон:SfnШаблон:Sfn. Деякі варіанти задачі залишаються нерозв'язаними.

Щільність

Один зі шляхів формальнішого формулювання задачі — розглядати швидкість зростання множини $S$ в $d$-вимірному евклідовому просторі, визначеному як функція, що відображає дійсні числа $r$ у точки $S$, розміщені на відстані $r$ від початку координат. Питання Данцера — чи може множина Данцера мати швидкість зростання $O(r^d)$, швидкість зростання цілком рознесених множин точок, подібних до цілочисельної ґратки (яка не є множиною Данцера)Шаблон:Sfn.

Можна побудувати множину Данцера зі швидкістю зростання в межах півлогарифмічного коефіцієнта $O(r^d)$. Наприклад, при накладанні прямокутних сіток, комірки яких мають постійний об'єм, але різні пропорції, можна досягти швидкості зростання $O(n^d{\log }^{d-1}n)$Шаблон:Sfn. Побудови множин Данцера відомі з трохи меншою швидкістю зростання $O(r^d\log r)$, але відповідь на питання Данцера залишається невідомоюШаблон:Sfn.

Обмежене покриття

Варіант задачі, який запропонував Тімоті Гауерс, запитує, чи існує множина Данцера $S$, для якої існує скінченна межа $C$ на кількість точок перетину $S$ та будь-якого опуклого тіла одиничного об'ємуШаблон:Sfn. Цей варіант розв'язано — така множина Данцера неможливаШаблон:Sfn.

Поділ

Третій варіант задачі, що залишається нерозв'язаним, — задача Конвея про мертвих мух. Джон Конвей згадував, що бувши дитиною, він спав у кімнаті зі шпалерами, на яких квіти нагадували купу мертвих мух, і він намагався знайти опуклу область, що не містить мухШаблон:Sfn. У формулюванні Конвея питається, чи існує множина Данцера, в якій точки множини (мертві мухи) відокремлені одна від одної на обмежену відстань. Така множина також обов'язково матиме верхню межу відстаней від кожної точки площини до мертвої мухи (щоб торкнутися всіх точок кола одиничної площі), так що вона повинна утворити множину Делоне, множину, що має як ненульову нижню межу, так і скінченну межу відстаней між точками. Ця множина обов'язково матиме швидкість зростання $O(r^d)$, отже, якщо вона існує, вона має розв'язувати й оригінальну версію задачі Данцера. Конвей запропонував приз $1000 за розв'язання задачіШаблон:Sfn, як частину добірки задач, до якої входять також задача Конвея про 99-вершинний граф, аналіз Шаблон:Не перекладено та гіпотеза про треклШаблон:Sfn.

Додаткові властивості

Можна також обмежити класи множин точок, які можуть бути множинами Данцера іншими способами. Зокрема, вони не можуть бути об'єднанням скінченної множини ґратокШаблон:Sfn, не можуть бути утвореними вибором точки з кожної плитки підстановки (у тій самій позиції для кожної плитки того ж типу), і їх не можна згенерувати методом виріж-і-спроєктуй побудови аперіодичних мозаїк. Тому вершини мозаїки «вертушка» та мозаїки Пенроуза не є множинами ДанцераШаблон:Sfn.

Див. також

• Шаблон:Не перекладено на множині точок, які не мають малої площі.
• Теорема Мінковського, що будь-яке замкнуте опукле тіло одиничного об'єму з центом симетрії на початку координат містить ненульове число точок напівцілочисельної ґратки.

Література

• Шаблон:Стаття. Див. також Шаблон:OEIS.
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття