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

Построение двумерного множества Данцера со скоростью роста $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)$. Например, при наложении прямоугольных сеток, ячейки которых имеют постоянный объём, но различные Шаблон:Нп5, можно достичь скорости роста $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-вершинном графе, анализ Шаблон:Нп5 и гипотеза о треклеШаблон:Sfn.

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

Множества Данцера не могут быть

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

См. также

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

Литература

• Шаблон:Статья. См. также Шаблон:OEIS el.
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья