Ru.Wikipedia.Org - Задача Данцера

Меню
Главная
Случайная статья
Настройки

Задача Данцера — Грюнбаума
Материал из https://ru.wikipedia.org

Задача Данцера — Грюнбаума — проблема комбинаторной геометрии, ставящая вопрос о том, какое максимальное число точек можно разместить в многомерном пространстве, чтобы они не образовывали между собой прямых или тупых углов. Известно, что на плоскости можно расположить максимум три такие точки, в трёхмерном пространстве можно расположить пять таких точек. В 2017 году было доказано, что в пространстве размерности

d

можно расположить

(2^{d})

таких точек.

Содержание

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

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

Как растёт $f(d)$ относительно $d$ ?

Иными словами, задача состоит в том, чтобы найти простую формулу, выражающую

f(d)

через

d

с как можно лучшей точностью (а также найти алгоритм построения множества из

f(d)

точек).

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

По состоянию на март 2018 года известно, что

2^{d-1}+1\leq f(d)\leq 2^{d}

.

Смежные задачи

Следующая задача была поставлена Эрдёшем ещё раньше, чем классическая формулировка задачи Данцера — Грюнбаума^[1]:

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

Как растёт $g(d)$ относительно $d$ ?

Известно, что

g(d)=2^{d}

.

В первой по-настоящему прорывной работе по этой теме Эрдёш и Фюреди построили большое множество, удовлетворяющее заданным условиям, из вершин

d

-мерного куба

{\left\lbrace {0,1}\right\rbrace }^{d}

. Поэтому в дальнейших работах, улучшающих их результат, иногда рассматривалась отдельно следующая задача:

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

Как растёт $f_{\square }(d)$ относительно $d$ ?

Очевидно, что

f_{\square }(d)\leq f(d)

.

История изучения

Первые упоминания (Эрдёш, 1948, 1957)

История задачи начинается в 1948 году, когда в разделе «Дополнительные проблемы для решения» журнала «The American Mathematical Monthly» Пал Эрдёш опубликовал следующий частный случай будущей задачи Данцера — Грюнбаума^[2]:

Пусть даны восемь точек в пространстве ${\mathbb {R} }^{3}$ . Докажите, что всегда можно найти три из них, которые не образуют остроугольный треугольник.

То есть в задаче спрашивалось, верно ли, что

f(3)<8

В 1957 году в журнале Michigan Mathematical Journal^[англ.], в статье со множеством гипотез, Эрдёш опубликовал уже общую гипотезу, но относительно тупоугольных множеств.

Пусть $S$ — множество из $2^{d}+1$ точек в пространстве размерности $k$ . Верно ли, что тогда среди них обязательно существуют три точки, образующие тупой угол?

То есть гипотеза утверждала, что

g(d)\leq 2^{d}

.

В статье говорились, что для

d=3

доказательство нашли Николас Кёйпер и Бьёрдийк (Boerdijk), но их доказательство ещё не опубликовано.

Рядом с гипотезой содержался следующий вопрос:

Верно ли, что существует множество из шести (семи) точек в трёхмерном пространстве такие, что любые три из них образуют острый угол?

Или, другими словами, верно ли, что

f(3)\geq 6

или

f(3)\geq 7

.^[1]

Первая гипотеза (Данцер, Грюнбаум, 1962)

Первую общую конструкцию для решения этой задачи построили Людвиг Данцер и Бранко Грюнбаум в статье 1962 года. Они построили в

d

-мерном пространстве

2d-1

точку, матрица координат которых выглядела следующим образом (строки — разные точки, столбцы — разные координаты):

{\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}}

где

\delta _{1},\dots ,\delta _{d-1}

— попарно различные числа, все меньшие единицы.

Простой комбинаторный перебор разных типов возникающих углов позволяет показать, что никакие три из этих точек не образуют прямых или тупых углов. Из этого следует, что

f(d)\geq 2d-1

В этой же работе авторы высказали гипотезу, что большего количества точек, выполняющих это условие, построить нельзя, то есть что

f(d)=2d-1

^[3].

Также в этой работе была доказана оценка сверху

f(d)\leq g(d)\leq 2^{d}

, которая была ранее предположена Эрдёшем.

Применение вероятностного метода (Эрдёш, Фюреди, 1983)

В 1983 году Пол Эрдёш и Золтан Фюреди^[англ.], используя вероятностный метод, опровергли гипотезу Данцера — Грюнбаума, показав, что

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

Это дало возможность построить контрпримеры к гипотезе Данцера — Грюнбаума для

d\geq 35

.^[4]^[5]

Однако, ввиду особенностей вероятностного метода, их доказательство было неэффективным и не позволяло построить это множество явно (кроме как прямым перебором)^[3].

Основная идея Эрдёша и Фюреди состояла в том, чтобы выбрать некоторое множество точек, в котором (с положительной вероятностью) будет очень мало прямых и тупых углов, а потом просто удалить по одной точке у каждого из этих углов, тем самым устранив их все.

Доказательство Эрдёша и Фюреди заключалось в том, чтобы выбрать случайным образом и независимо друг от друга

2n

точек из единичного куба

\left\lbrace {0,1}\right\rbrace ^{d}

, где

n=\left\lfloor {{\frac {1}{2}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}}\right\rfloor

и доказать, что при таковым выборе вероятность того, что среди них окажутся лишь

n

тупоугольных или вырожденных треугольников, положительна.

Под случайным выбором точки здесь имеется в виду её генерация по схеме Бернулли с вероятностью

p={\frac {1}{2}}

генерации единицы или нуля на той или иной координате точки независимо от остальных координат.

Для доказательства оценки на количество тупоугольных треугольников использовалось свойство линейности математического ожидания. Вероятность того, что конкретная тройка точек образует прямой угол, равна

\left({\frac {3}{4}}\right)^{d}

- это легко доказать, рассматривая отдельно вклад каждой координаты в скалярное произведения. Умножая эту вероятность на количество таких троек, получим значение математического ожидания, а это уже даст, согласно неравенству Маркова, положительную вероятность того, что случайная величина его не превосходит.

Улучшения константы в оценке Эрдёша — Фюреди

Даже не изменяя метода Эрдёша в самой его сути, можно получить лучшее оценку, просто выбрав другое число в качестве параметра, определяющего, сколько случайных точек следует выбирать.

Айгнер и Циглер в 2003 году, описывая теорему Эрдёша в своей обзорной книге «Доказательства из Книги», исправили этот параметр и получили, что

f_{\square }(d)\geq 2\left\lfloor {{\frac {\sqrt {6}}{9}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}}\right\rfloor

.^[6] Это — лучшее, что можно получить таким способом.