Доклады Российской академии наук. Математика, информатика, процессы управления, 2022, T. 506, № 1, стр. 45-48

1. ВВЕДЕНИЕ

Для метрического пространства $\mathbb{M}$ назовем его равносторонней размерностью наибольшее число равноудаленных друг от друга точек в $\mathbb{M}$ и обозначим это число через $e(\mathbb{M})$. Эта величина активно изучалась для пространств $\mathbb{R}_{p}^{n}$ при $1 < p < \infty $. Напомним, что ${{\ell }_{p}}$-расстояние между двумя точками ${\mathbf{x}},{\mathbf{y}} \in {{\mathbb{R}}^{n}}$ определяется по формуле

Нетрудно проверить (см. [12]), что в евклидовом случае $e(\mathbb{R}_{2}^{n}) = n + 1$, а в случае максимальной нормы $e(\mathbb{R}_{\infty }^{n}{{) = 2}^{n}}$. Нижние оценки представляются соответственно вершинами правильного тетраэдра и гиперкуба. Однако про $e(\mathbb{R}_{p}^{n})$ известно намного меньше, когда $p \ne 2,\infty $. Например, для Манхеттенской метрики ${{\ell }_{1}}$ Алон и Пудлак [1] показали, что $e(\mathbb{R}_{1}^{n}) < cn\log n$ для некоторой положительной константы c, в то время, как наилучшая известная нижняя оценка $e(\mathbb{R}_{1}^{n}) \geqslant 2n$ получается из рассмотрения вершин стандартного кроссполитопа (т.е. точек, у которых все координаты нулевые, кроме одной, равной $ \pm 1$). Каснер [9] выдвинул гипотезу о том, что нижняя оценка точна. Эта гипотеза была подтверждена лишь для n = 3 [2] и для n = 4 [10]. Лучшие известные оценки для других значений p на данный момент можно найти в [1, 14, 16, 17].

В настоящей работе мы рассматриваем две задачи, связанные с равносторонней размерностью. В первой задаче рассматриваются равноудаленные вправо последовательности. Последовательность x⁽¹⁾, ..., ${{{\mathbf{x}}}^{{(m)}}} \in \mathbb{R}_{p}^{n}$ назовем равноудаленной вправо, если ${\text{||}}{{{\mathbf{x}}}^{{({{j}_{1}})}}} - {{{\mathbf{x}}}^{{(i)}}}{\text{|}}{{{\text{|}}}_{p}} = {\text{||}}{{{\mathbf{x}}}^{{({{j}_{2}})}}} - {{{\mathbf{x}}}^{{(i)}}}{\text{|}}{{{\text{|}}}_{p}}$ для всех $1 \leqslant i$ < < ${{j}_{1}} \leqslant {{j}_{2}} \leqslant m$. Неформально говоря, каждая точка равноудалена от всех последующих.

В работе [11, Следствие 14] была доказана следующая общая теорема:

Теорема 1. Во всяком нормированном пространстве размерности $n$ размер наибольшей равноудаленной вправо последовательности не превосходит $O{{(6}^{n}}{{n}^{2}}\mathop {\log }\nolimits^2 n)$.

Позднее Полянский [13] улучшил эту оценку до $O{{(3}^{n}}n)$. Этот результат можно применить, в частности, для доказательства верхней оценки на размер множества с $k$ различными расстояниями.

Нетрудно видеть, что максимальный размер равноудаленной вправо последовательности в евклидовом пространстве $\mathbb{R}_{2}^{n}$ равен n + 2. В качестве примера можно привести центр правильного тетраэдра, после которого идут вершины тетраэдра в произвольном порядке¹¹. Иные результаты для других ${{\ell }_{p}}$ пока неизвестны.

В настоящей работе мы получаем оценки для равноудаленных вправо последовательностей с метриками ${{\ell }_{\infty }}$ и ${{\ell }_{1}}$.

Теорема 2. Для любого $n \in \mathbb{N}$ максимальный размер равноудаленной вправо последовательности точек из $\mathbb{R}_{\infty }^{n}$ равен ${{2}^{{n + 1}}} - 1$.

Теорема 3, Для любого $n \in N$ существует равноудаленная вправо последовательность из $4n - 1$ точки в $\mathbb{R}_{1}^{n}$.

Вторая задача, которую мы рассматриваем, происходит из работы [8]. Для данных $n \in \mathbb{N}$ и $p \in [1,\infty ]$ можно построить $e(\mathbb{R}_{p}^{n})$ точек в $\mathbb{R}_{p}^{n}$ с попарно единичными расстояниями. В частности, наибольшее число точек в $\mathbb{R}_{p}^{n}$ с попарно нечетными расстояниями не меньше $e(\mathbb{R}_{p}^{n})$. В работе [8] показано, что эта тривиальная нижняя оценка в сущности оптимальна в евклидовом случае. В частности, авторы работы доказали следующее.

Теорема 4 ([8]). Наибольшее число точек в $\mathbb{R}_{2}^{n}$ с попарно нечетными расстояниями равно n + 2, если $n \equiv 14\,\,(\bmod 16)$, и $n + 1$ в противном случае.

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

Теорема 5. Для любого $n \in \mathbb{N}$ наибольшее число точек в $\mathbb{R}_{\infty }^{n}$ с попарно нечетными расстояниями есть 2ⁿ.

Случай с Манхеттенской метрикой не так прозрачен. Для всех $n \in \mathbb{N}$ мы нашли явную конструкцию из 7n точек в $\mathbb{R}_{1}^{{3n}}$ с попарно нечетными расстояниями. Из этого следует, что вершины стандартного кроссполитопа не представляют оптимальную конструкцию. С другой стороны, лучшая верхняя оценка, которую мы получаем, растет асимптотически как $n!$

Теорема 6. Число точек $\mathbb{R}_{1}^{n}$ с попарно нечетными расстояниями не превосходит $n! \cdot n \cdot \ln n \cdot (4$ + + o(1)) при $n \to \infty $.

Вообще говоря, найденная нами верхняя оценка также является верхней оценкой хроматического числа пространства $\mathbb{R}_{1}^{n}$ с запрещенными нечетными расстояниями. Интересно, что для евклидовой плоскости неизвестно, конечно ли ее хроматическое число с запрещенными нечетными расстояниями (см. [7]).

2. ИДЕИ ДОКАЗАТЕЛЬСТВ ВЕРХНИХ ОЦЕНОК

При работе с метрикой ${{\ell }_{\infty }}$ в обоих результатах используется следующий инструмент. Напомним, что частично упорядоченным множеством (сокращенно чум) называется пара $\mathcal{P} = (S, \preccurlyeq )$, где S есть множество, а $ \preccurlyeq $ – рефлексивное антисимметричное транзитивное отношение на его элементах. Назовем $x,y \in S$ сравнимыми, если $x \preccurlyeq y$ или $y \preccurlyeq x$. В противном случае будем называть их несравнимыми. Множество попарно сравнимых элементов будем называть цепью, а попарно несравнимых – антицепью.

Теорема Дилворта [4] утверждает, что размер наибольшей антицепи во всяком чуме равен наименьшему количеству цепей, в объединении дающих все множество. Для доказательства наших результатов в метрике ${{\ell }_{\infty }}$ мы строим чумы, в котором нет больших цепей, а антицепями служат конструкции меньшей размерности. В частности, мы говорим, что $x \preccurlyeq y$, если $x = y$ или если ${\text{|}}{{x}_{n}} - {{y}_{n}}{\text{|}} > {\text{|}}{{x}_{i}} - {{y}_{i}}{\text{|}}$ для всех $i < n$ и при этом x_n< y_n.

Например, в случае множеств с нечетными расстояниями при таком построении всякая антицепь есть пример для размерности n – 1, а все цепи имеют размеры не более 2. В таком случае теорема Дилворта дает рекуррентное соотношение $f(n) \leqslant 2f(n - 1)$ на искомую оценку, что эквивалентно $f(n) \leqslant {{2}^{n}}$. В случае равноудаленных вправо последовательностей может найтись одна цепь длины 3, после удаления которой все цепи имеют длины не более 2, что приводит к похожему соотношению $f(n) \leqslant 2f(n - 1) + 1$, которое эквивалентно $f(n) \leqslant {{2}^{{n + 1}}} - 1$.

Для доказательства верхней оценки случая нечетных расстояний в ${{\ell }_{1}}$ рассматривается решетка $\Lambda $, порожденная векторами ${{{\mathbf{e}}}_{1}} + {{{\mathbf{e}}}_{n}}, \ldots ,{{{\mathbf{e}}}_{{n - 1}}} + {{{\mathbf{e}}}_{n}}$, 2e_n, где ${{e}_{i}}$ есть i-й базисный вектор. В каждой точке этой решетки устанавливается копия уменьшенного кроссполитопа $C = \{ {\mathbf{x}} \in {{\mathbb{R}}^{n}}{\kern 1pt} :\;{\text{||}}{\mathbf{x}}{\text{|}}{{{\text{|}}}_{1}} < 1{\text{/}}2\} $. Оказывается, что никакие две точки объединения копий этого тела не находятся на нечетном расстоянии друг от друга. Также оказывается, что асимптотически достаточно $\frac{{{\text{det}}(\Lambda )}}{{{\text{vol}}(C)}} \cdot (2\, + \,o(1))n{\text{ln}}n$ копий этого объединения, чтобы покрыть все пространство, см. [5]. Из этого наблюдения и получается верхняя оценка.

3. ПОСТРОЕНИЕ КОНФИГУРАЦИИ, ДАЮЩЕЙ НИЖНЮЮ ОЦЕНКУ

Для того, чтобы построить пример равноудаленной вправо последовательности в $\mathbb{R}_{\infty }^{n}$ или в $\mathbb{R}_{\infty }^{n}$, достаточно рассмотреть вершины соответственно правильного гиперкуба или кроссполитопа. Если у этого многогранника m вершин, то последовательность размера $2m - 1$ можно построить, зафиксировав вершину x, которая будет последней, и затем в некотором порядке для каждой из остальных вершин y добавлять в последовательность $\lambda {\mathbf{y}}$ и $2\lambda {\mathbf{y}}$, постоянно уменьшая λ. Порядок выбора вершин задается отдельно в каждом случае. Оказывается, что при достаточном уменьшении λ (например, на каждом шаге в 2 раза) полученная последовательность действительно оказывается равноудаленной вправо в данной метрике.