Слепое пятно (ещё раз о задаче Эрдёша)

[grizzly]

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

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

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

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

[grizzly]

Рассмотрим следующую задачу. Дан единичный куб в $\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-класснику, если только объяснить ему понятие скалярного произведения или -- лучше -- не вводя этого понятия сказать, как отличить прямой угол от острого в вершинах единичного куба по координатам этих вершин.

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

[grizzly]

Далее я перешёл к случаю $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 точек.

[grizzly]

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