2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Слепое пятно (ещё раз о задаче Эрдёша)
Сообщение18.05.2018, 23:56 
Заслуженный участник
Аватара пользователя


09/09/14
5333
(В продолжение прошлогодней темы: «Улучшено (?) решение Эрдёша по остроугольным треугольникам».)

Речь снова пойдёт об остроугольных множествах, но теперь уже в единичном кубе в $\mathbb R^n$. Напомним в двух словах основные термины и историю вопроса.

Множество точек в $\mathbb R^n$ называется остроугольным, если любые 3 точки этого множества образуют остроугольный треугольник. В работе Грюнбаума и Данцера 1962 г. была высказано гипотеза, что остроугольное множество в $\mathbb R^n$ содержит $2n-1$ точку и не более. Через 20 лет гипотеза была опровергнута Эрдёшем в этой работе. Доказательство было неконструктивным: использовался один из любимых методов Эрдёша -- вероятностный. С помощью этого метода было доказано, что мощность остроугольного множества в $\mathbb R^n$ экспоненциально зависит от $n$. (За следующие 25 лет были достигнуты небольшие успехи в улучшении этих оценок, и только в прошлом году элементарными и совсем простыми методами оценки приобрели почти окончательный характер. Но речь пойдёт не об этом.)

Здесь я приведу совсем другой способ опровержения гипотезы Грюнбаума -- Данцера и благодаря использованной идее построю конструктивные примеры, улучшающие известные на сегодняшний день. Особой теоретической ценности этот результат не имеет (разве что для какого-нибудь Кванта или мат.кружка) -- я поясню в конце почему, но цель в том, чтобы привлечь внимание собственно к той задаче, которой занимался Эрдёш в упомянутой работе. Его оценки по единичному кубу были с тех пор совсем незначительно улучшены, а оказалось, что самые простые наблюдения прошли мимо математиков публиковавшихся в этом направлении.

 Профиль  
                  
 
 Re: Слепое пятно (ещё раз о задаче Эрдёша)
Сообщение19.05.2018, 00:59 
Заслуженный участник
Аватара пользователя


09/09/14
5333
Рассмотрим следующую задачу. Дан единичный куб в $\mathbb R^n$, нужно оценить мощность наибольшего остроугольного множества на вершинах этого куба.

Свои попытки работать над задачей я начал не с известных статей (которые всё же несколько трудны для меня, хоть и в принципе доступны). Я начал с рассмотрения примеров в OEIS: A089676 (за что ей особенно благодарен).

После часового тупления в экран я замечаю следующее. В самом простом случае в $\mathbb R^3$ имеем 4 точки:
000
011
101
110
И что я здесь вижу? 4 точки квадрата (первые 2 координаты) и пара диагональных точек поднята по третьей координате. Последнее, что осталось заметить: третья координата является функцией XOR от первых двух координат!

И вот теперь нужно пойти и посмотреть, что будет, если мы вместо базового квадрата (4 точки в прошлом примере) возьмём базовый кубик -- 8 точек. И будем к нему добавлять дополнительные координаты. Два вопроса: (а) сколько их потребуется? (б) можно ли обойтись только XOR'ами. Вот эти 8 точек (я только чуть подправил пример в OEIS, чтобы первые 3 координаты давали 8 точек $\mathbb R^3$ кубика):
0 0 0 0 0 0
0 0 1 0 1 1
0 1 0 1 1 0
0 1 1 1 0 1
1 0 0 1 0 1
1 0 1 1 1 0
1 1 0 0 1 1
1 1 1 0 0 0
Как несложно заметить, четвёртая координата (первая дополнительная координата) является функцией XOR от первых двух базовых координат; вторая дополнительная -- XOR от второй и третьей базовых, третья дополнительная (последняя) -- XOR от третьей и первой. Вывод: в этом примере имеем циклическую последовательность попарных XOR'ов. Ещё раз, ответы на вопросы: (а) потребовалось три дополнительные координаты, (б) все они XOR'ы базовых координат.

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

Для произвольного $k$ рассмотрим единичный куб в $\mathbb R^k$ и добавим к каждой точке $C_k^2$ дополнительных координат -- все возможные попарные XOR'ы (важно, чтобы они шли в одном порядке для каждой точки -- см. примеры выше). Получим в результате такого построения множество из $2^k$ точек в пространстве $\mathbb R^n, n=\frac {k(k+1)}{2}$. Осталось проделать два одинаково несложных упражнения, которые я пока оставлю читателям (доказательства вполне поместятся на полях):
1) Доказать, что любые три точки построенного множества образуют остроугольный треугольник.
2) Доказать, что количество точек ($=2^k$) в таком множестве растёт с ростом $n$ быстрее любого полинома от $n$ ($n=\frac {k(k+1)}{2}$).

Эти упражнения доступны продвинутому 7-класснику, если только объяснить ему понятие скалярного произведения или -- лучше -- не вводя этого понятия сказать, как отличить прямой угол от острого в вершинах единичного куба по координатам этих вершин.

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

 Профиль  
                  
 
 Re: Слепое пятно (ещё раз о задаче Эрдёша)
Сообщение19.05.2018, 07:50 
Заслуженный участник
Аватара пользователя


09/09/14
5333
Далее я перешёл к случаю $k=4$, то есть 16 точек, 4 базовые координаты. Оптимальный результат $n=9$ (5 дополнительных координат в моих терминах) для этого случая был обнаружен всего-то 12 лет тому (см. OEIS по ссылке в первом сообщении. Описанный выше метод попарных xor'ов даёт $n=10$. Но как нетрудно убедиться, можно выбросить все xor'ы кроме циклических, и заменить их общим xor'ом. Решение будет выглядеть так:
$x^i_1,x^i_2,x^i_3,x^i_4, \ \mathop{\rm xor}(x^i_1,x^i_2),\mathop{\rm xor}(x^i_2,x^i_3),\mathop{\rm xor}(x^i_3,x^i_4),\mathop{\rm xor}(x^i_4,x^i_1),\mathop{\rm xor}(x^i_1,x^i_2,x^i_3,x^i_4); \quad i=1,...,16.$

Дальше я сообразил, что можно вообще забыть про попарные xor'ы и минимизировать количество координат, выбирая их из всех возможных $2^k$ xor'ов.
Поскольку рекорды в OEIS на этом закончились, я нашёл в литературе лучшие из опубликованных результатов (см. таблицу результатов на стр. 17 в этой работе) и попытался их улучшить. Вот что получилось.

Для $k=5$ и $k=6$ я получил те же результаты.
Для $k=7$ и $k=8$ я получил размерности 20 и 24, соответственно. Это на 3--4 размерности лучше.
Дальше я взялся сразу за $k=10$ и получил там размерность 31, что на 5 размерностей лучше.

Во вложении пример для $k=7$ (128 точек в $\mathbb R^{20}$). Остальные примеры я поленился пока оформлять.

На этом собственно всё. Осталось пояснить про возможные перспективы этого подхода.

Во-первых, все мои результаты могут, вероятно, быть улучшены. Для этого необходимо делать перебор возможных xor'ов не тупо, как я, а с использованием алгоритма задачи "set covering". Это несложные и достаточно продвинутые алгоритмы и с их помощью можно рассчитывать получить хорошие результаты жадным алгоритмом для очень больших размерностей. (Я думаю, что вплоть до $k=15$ они должны хорошо сработать; а может и дальше).

Во-вторых, можно попытаться найти асимптотику решений по этому подходу. Несмотря на хорошие результаты для малых $k$, я не могу построить универсальную схему. Я пытался это делать, но потом потерял интерес. И вот почему.

В-третьих, все эти xor'ы есть просто линейная комбинация координат (над полем $\mathbb F_2$) и мы автоматом попадаем в область задач теории кодирования, точнее -- в её подобласть, которая называется "linear code". И как мне уже объяснили знающие люди, эта область перепахана вдоль и поперёк и из вот этой таблички видно, что асимптотику $2^{n/3}$ здесь не получить, и даже на $2^{n/4}$ (это есть гипотеза Эрдёша для данной задачи) рассчитывать не приходится. Поэтому, для того, чтобы получить существенно лучшие общие результаты, нужно искать другие подходы.

PS. Добавил результат для 1024 точек.


Вложения:
1024 points R^31.txt [66 Кб]
Скачиваний: 11
128 points R^20.txt [5.5 Кб]
Скачиваний: 7
 Профиль  
                  
 
 Re: Слепое пятно (ещё раз о задаче Эрдёша)
Сообщение14.06.2018, 12:30 
Заслуженный участник
Аватара пользователя


09/09/14
5333
Upd. Как оказалось, эти (другие подобные и даже некоторые намного лучшие) примеры косвенно были уже известны в кругу людей, специализирующихся в теории кодирования. Но они не дошли до OEIS, поскольку не формулировались в терминах остроугольных множеств. То есть примеры были известны, но они не были проверены на остроугольность специалистами, работающими в области комбинаторной геометрии. Как минимум они не попали в статьи 2006 и 2011 г.г. двух разных авторов. В общем, немного странная и не совсем понятная мне история, но как-то так.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group