Далее я перешёл к случаю
, то есть 16 точек, 4 базовые координаты. Оптимальный результат
(5 дополнительных координат в моих терминах) для этого случая был обнаружен всего-то 12 лет тому (см. OEIS по ссылке в первом сообщении. Описанный выше метод попарных xor'ов даёт
. Но как нетрудно убедиться, можно выбросить все xor'ы кроме циклических, и заменить их общим xor'ом. Решение будет выглядеть так:
Дальше я сообразил, что можно вообще забыть про попарные xor'ы и минимизировать количество координат, выбирая их из всех возможных
xor'ов.
Поскольку рекорды в OEIS на этом закончились, я нашёл в литературе лучшие из опубликованных результатов (см. таблицу результатов на стр. 17 в
этой работе) и попытался их улучшить. Вот что получилось.
Для
и
я получил те же результаты.
Для
и
я получил размерности 20 и 24, соответственно. Это на 3--4 размерности лучше.
Дальше я взялся сразу за
и получил там размерность 31, что на 5 размерностей лучше.
Во вложении пример для
(128 точек в
). Остальные примеры я поленился пока оформлять.
На этом собственно всё. Осталось пояснить про возможные перспективы этого подхода.
Во-первых, все мои результаты могут, вероятно, быть улучшены. Для этого необходимо делать перебор возможных xor'ов не тупо, как я, а с использованием алгоритма задачи "set covering". Это несложные и достаточно продвинутые алгоритмы и с их помощью можно рассчитывать получить хорошие результаты жадным алгоритмом для очень больших размерностей. (Я думаю, что вплоть до
они должны хорошо сработать; а может и дальше).
Во-вторых, можно попытаться найти асимптотику решений по этому подходу. Несмотря на хорошие результаты для малых
, я не могу построить универсальную схему. Я пытался это делать, но потом потерял интерес. И вот почему.
В-третьих, все эти xor'ы есть просто линейная комбинация координат (над полем
) и мы автоматом попадаем в область задач теории кодирования, точнее -- в её подобласть, которая называется "linear code". И как мне уже объяснили знающие люди, эта область перепахана вдоль и поперёк и из
вот этой таблички видно, что асимптотику
здесь не получить, и даже на
(это есть гипотеза Эрдёша для данной задачи) рассчитывать не приходится. Поэтому, для того, чтобы получить существенно лучшие общие результаты, нужно искать другие подходы.
PS. Добавил результат для 1024 точек.