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

Нерозв'язана проблема математики: Чи існує множина Данцера з обмеженою щільністю чи обмеженим ступенем поділу? (більше нерозв'язаних проблем математики)

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

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

Щільність

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

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

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

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

Поділ

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

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

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

Див. також

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

Література

• John Horton Conway. Five $1,000 Problems. — On-Line Encyclopedia of Integer Sequences, 2017. Процитовано 2019-02-12.. Див. також послідовність A248380 з Онлайн енциклопедії послідовностей цілих чисел, OEIS.
• Bambah R. P., Woods A. C. On a problem of Danzer // Pacific Journal of Mathematics. — 1971. — Т. 37.
• Hallard T. Croft, Kenneth J. Falconer, Richard K. Guy. E14: Positioning convex sets relative to discrete sets // Unsolved problems in geometry. — Springer-Verlag, New York, 1991. — С. 148. — (Problem Books in Mathematics) — ISBN 0-387-97506-3. — DOI:10.1007/978-1-4612-0963-8.
• Werner Fenchel. Problems // Proceedings of the Colloquium on Convexity, Copenhagen, 1965. — Copenhagen : Kobenhavns Universitets Matematiske Institut, 1967.
• Gowers W. T. Rough structure and classification // Geometric and Functional Analysis. — 2000. — Вип. Special Volume, Part I. — DOI:10.1007/978-3-0346-0422-2_4.
• Siobhan Roberts. Genius at Play: The Curious Mind of John Horton Conway. — New York : Bloomsbury Press, 2015. — ISBN 978-1-62040-593-2.
• Omri Solan, Yaar Solomon, Barak Weiss. On problems of Danzer and Gowers and dynamics on the space of closed subsets of $\mathbb {R} ^{d}$ // International Mathematics Research Notices. — 2017. — Вип. 21. — arXiv:1510.07179. — DOI:10.1093/imrn/rnw204.
• Yaar Solomon, Barak Weiss. Dense forests and Danzer sets // Annales Scientifiques de l'École Normale Supérieure. — 2016. — Т. 49, вип. 5. — arXiv:1406.3807. — DOI:10.24033/asens.2303.