Множество Данцера

Нерешённые проблемы математики: Существует ли множество Данцера с ограниченной плотностью или ограниченной степенью разделения?

Построение двумерного множества Данцера со скоростью роста $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-вершинном графе, анализ игры с монетами и гипотеза о трекле.

Дополнительные свойства

Можно также ограничить классы множеств точек, которые могут служить множествами Данцера другими способами. В частности, они не могут быть объединением конечного множества решёток, не могут быть образованными выбором точки из каждой плитки подстановки (в той же позиции для каждой плитки того же типа) и не могут быть сгенерированы методом вырежь-и-спроецируй построения апериодичных мозаик. Поэтому вершины мозаики «Вертушка» и мозаики Пенроуза не являются множествами Данцера.

См. также

• Задача Хайльбронна о треугольниках на множестве точек, которые не имеют малой площади.
• Теорема Минковского, что любое замкнутое выпуклое тело единичного объёма с центом симметрии в начале координат содержит ненулевое число точек полу-целочисленной решётки.