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

1. ИСТОРИЯ И ПОСТАНОВКА ЗАДАЧИ

Для произвольного $d \in \mathbb{N}$ и $\varepsilon \in (0,\;1)$ задача состоит в нахождении минимального количества $\mu (d$; ε) кубов ${{A}_{1}},\; \ldots ,\;{{A}_{\mu }}$, со стороной ε, покрывающих тор ${{T}^{d}}: = [\mathbb{R}{\text{/}}\mathbb{Z}{{]}^{d}}$. Как обычно, под кубом со стороной ε подразумевается множество вида $\{ ({{x}_{1}},\; \ldots ,\;{{x}_{d}}){\text{:}}\;{{x}_{i}} \in [x_{i}^{0},x_{i}^{0} + \varepsilon ]\} $, а под покрытием – такой набор множеств ${{A}_{1}}, \ldots ,{{A}_{\mu }}$, что ${{A}_{1}} \cup \; \ldots \; \cup {{A}_{\mu }}$ = = T^d. Известно [1], что для всех d и $\varepsilon $ справедливо

где ${{\left\lceil x \right\rceil }^{{(i)}}} = \left\lceil {x{{{\left\lceil x \right\rceil }}^{{(i - 1)}}}} \right\rceil $ и ${{\left\lceil x \right\rceil }^{{(1)}}} = \left\lceil x \right\rceil $. Довольно широко изучен случай растущей размерности d. Заметим, что ((1)) влечет $\mu (d;\varepsilon ) \geqslant {{(1{\text{/}}\varepsilon + o(1))}^{d}}$. Из общего результата Эрдеша и Роджерса о покрытиях [2] следует, что 1/ε – правильное основание экспоненты, т.е. μ(d; ε) = ${{(1{\text{/}}\varepsilon \, + \,o(1))}^{d}}$. Точнее Эрдеш и Роджерс доказали, что μ(d; ε) = $O(d{\text{log}}d{{(1{\text{/}}\varepsilon )}^{d}})$. Для дискретного тора T^d = ${{[\mathbb{Z}{\text{/}}t\mathbb{Z}]}^{d}}$, покрываемого кубами со стороной $s \in \{ 1,\; \ldots ,\;t\} $, с помощью вероятностного метода нетрудно (см., например, [3]) улучшить эту оценку, убрав логарифмический множитель (здесь подразумевается, что $\varepsilon = s{\text{/}}t$). Нам удалось показать (см. лемму 3 и лемму 3), что дискретная и непрерывная постановка эквивалентны. Тем самым, $\mu (d;\varepsilon ) = O(d{{(1{\text{/}}\varepsilon )}^{d}})$ (как для рациональных, так и для иррациональных ε). Отметим, что из нижней оценки (1) следует лишь $\mu (d;\varepsilon ) = \Omega ({{(1{\text{/}}\varepsilon )}^{d}})$.

Что касается малых значений размерности d, то нам известна лишь работа [1], в которой доказано, что при d = 2 нижняя оценка (1) точна, т.е. $\mu (2;\varepsilon ) = \left\lceil {1{\text{/}}\varepsilon \left\lceil {1{\text{/}}\varepsilon } \right\rceil } \right\rceil $.

Мы изучаем случай d = 3. Так как $\mu (1;\varepsilon ) = \left\lceil {1{\text{/}}\varepsilon } \right\rceil $ и $\mu (2;\varepsilon ) = \left\lceil {1{\text{/}}\varepsilon \left\lceil {1{\text{/}}\varepsilon } \right\rceil } \right\rceil $, то

Заметим, что в размерности 3 нижняя оценка уже не является точной. Так, например, как замечено в [1], $\mu (3;3{\text{/}}7) > \left\lceil {7{\text{/}}3\left\lceil {7{\text{/}}3\left\lceil {7{\text{/}}3} \right\rceil } \right\rceil } \right\rceil .$ Нам удалось найти точное значение $\mu (3;\varepsilon )$ при всех $\varepsilon \geqslant 7{\text{/}}15$ и при $\varepsilon $, близких к $1{\text{/}}r$, $r \in \mathbb{N}$.

Отметим напоследок, что при $\varepsilon = 2{\text{/}}r$, $r \in \mathbb{N}$, соответствующая задача об упаковке (т.е. нахождение минимального количества $\nu (d;\varepsilon )$ непересекающихся кубов со стороной $\varepsilon $ в T^d) связана с нахождением емкости Шеннона $c({{C}_{r}})$ простого цикла на r вершинах [4], а именно, справедливо равенство $c({{C}_{r}}) = \mathop {\sup }\nolimits_{d \geqslant 1} {{(\nu (d;2{\text{/}}r))}^{{1/d}}}$ (аналогичная связь имеется и при всех других рациональных $\varepsilon $, но соответствующие графы сложнее описать). Для четного r, очевидно, $c({{C}_{r}}) = r{\text{/}}2$. Если же r нечетно, то значение емкости Шеннона известно лишь при $r = 5$: $c({{C}_{5}}) = \sqrt 5 $ [5].

2. НОВЫЕ РЕЗУЛЬТАТЫ

Рассмотрим сперва $\varepsilon \geqslant 1{\text{/}}2$.

Теорема 1. Справедливы равенства

Заметим, что при $\varepsilon \in [1{\text{/}}2,1)$ величина $\mu (3;\varepsilon )$ равна своей нижней оценке в (2) тогда и только тогда, когда $\varepsilon \in [1{\text{/}}2,4{\text{/}}7) \cup [2{\text{/}}3,1)$.

Так как при целых $r \geqslant 2$ и $\varepsilon \in \left[ {\frac{1}{r},\frac{1}{{r - 1{\text{/}}{{r}^{2}}}}} \right)$ нижняя и верхняя оценка в (2) совпадают, то, очевидно, $\mu (3;\varepsilon ) = {{r}^{3}}$. Мы также нашли такую левую окрестность 1/r, что при всех $\varepsilon $ из этой окрестности нижняя оценка точна. Заметим, что при таких $\varepsilon $ разность между верхней и нижней оценкой, наоборот, велика.

Теорема 2. Пусть $r \in \mathbb{N}$, ε ∈ ∈ $\left[ {\frac{1}{{r\, + \,1{\text{/}}({{r}^{2}}\, + \,r\, + \,1)}}} \right.$, $\left. {\frac{1}{r}} \right)$. Тогда $\mu (3;\varepsilon ) = {{r}^{3}} + {{r}^{2}}$ + r + 1.

Кроме того, мы расширили упомянутую правую окрестность.

Теорема 3. Пусть $r \geqslant 2$ – целое число, $\varepsilon \in \left[ {\frac{1}{r},\frac{{{{r}^{2}} - 1}}{{{{r}^{3}} - r - 1}}} \right)$. Тогда $\mu (3;\varepsilon ) = {{r}^{3}}$.

В некоторых случаях нам удалось усилить нижнюю оценку в (2).

Теорема 4. Пусть $r \geqslant 2$ – целое число, а $\xi \in \{ 1,\; \ldots ,\;r\} $ таково, что

Пусть, кроме того,

1) $s = {{r}^{2}} + r + \xi $,

2) $t = {{r}^{3}} + {{r}^{2}} + 2\xi r + \left\lfloor {\frac{{{{\xi }^{2}}}}{{r + 1}}} \right\rfloor $ взаимно просто с s.

Тогда $\mu \left( {3;\frac{s}{t}} \right) \geqslant t + 1$.

Заметим, что так как условие ξ² ≤ ξ + (r + + $1)\left\lfloor {\frac{{{{\xi }^{2}}}}{{r\, + \,1}}} \right\rfloor $ влечет, что либо $\xi \geqslant \sqrt {r + 1} $, либо ξ = 1, то в интервале [1/3, 1/2) найдутся только два таких значения $\frac{s}{t} \in \left\{ {\frac{7}{{16}},\frac{8}{{21}}} \right\}$.

Наконец, в некоторых случаях нам удалось усилить и верхнюю оценку в (2).

Теорема 5. Пусть $r \geqslant 2$ – целое число, $\xi \in \{ 1,\; \ldots ,\;r\} $. Пусть, кроме того,

1) $s = {{r}^{2}} + r + \xi $,

2) $t = {{r}^{3}} + {{r}^{2}} + \xi (r + 1)$.

Тогда $\mu \left( {3;\frac{s}{t}} \right) \leqslant t$.

Для доказательства полученных результатов мы установили, что задача нахождения $\mu (d;\varepsilon )$ сводится к своему дискретному аналогу – к задаче нахождения минимального количества кубов со стороной s, покрывающих ${{[\mathbb{Z}{\text{/}}t\mathbb{Z}]}^{d}}$ для некоторых s, t таких, что $s{\text{/}}t$ близко к $\varepsilon $. Таким образом, эти вспомогательные утверждения влекут, что задача сводится к рассмотрению счетного множества значений $\varepsilon $, причем количество таких значений в каждом интервале вида $[1{\text{/}}r,1{\text{/}}(r - 1)]$ конечно.

3. ПЕРЕХОД К ДИСКРЕТНОМУ СЛУЧАЮ

Лемма 1. Существует такая бесконечная последовательность рациональных чисел $1 > \frac{{{{s}_{1}}}}{{{{t}_{1}}}} > \frac{{{{s}_{2}}}}{{{{t}_{2}}}}$ > > ... > 0, что для каждого $i \in \mathbb{N}$ справедливо ${{t}_{i}} \leqslant \mu \left( {d;\frac{{{{s}_{i}}}}{{{{t}_{i}}}}} \right)$ и $\mu (d;\varepsilon ) = \mu \left( {d;\frac{{{{s}_{i}}}}{{{{t}_{i}}}}} \right)$ для всех $\varepsilon \in \left[ {\frac{{{{s}_{i}}}}{{{{t}_{i}}}},\frac{{{{s}_{{i - 1}}}}}{{{{t}_{{i - 1}}}}}} \right)$, где ${{s}_{0}} = {{t}_{0}} = 1$.

Из (2) несложно заметить, для каждого $r \geqslant 2$ для решения задачи для всех ε в интервале $\left[ {\frac{1}{r},\frac{1}{{r\, - \,1}}} \right)$ достаточно рассмотреть не более $\frac{{{{r}^{2}}({{r}^{3}}\, + \,1)}}{{2(r\, - \,1)}}$ + + r³ различных значений $\varepsilon $.

Пусть $s \leqslant t$ – натуральные числа. Пусть ${{\mu }_{0}}(d;s,t)$ – наименьшее количество кубов со стороной, состоящей из $s$ точек, покрывающих тор ${{[\mathbb{Z}{\text{/}}t\mathbb{Z}]}^{d}}$.

Лемма 2. Пусть $r \geqslant 2$ – целое число, $\varepsilon \in \left[ {\frac{1}{r},\frac{1}{{r - 1}}} \right)$. Пусть, кроме того, $\frac{s}{t} \leqslant \varepsilon $ – ближайшее к $\varepsilon $ рациональное число с $t \leqslant {{r}^{d}}$. Тогда $\mu (d;\varepsilon ) = {{\mu }_{0}}(d;s,t)$.

4. НЕКОТОРЫЕ ЧАСТНЫЕ СЛУЧАИ

При $\varepsilon \in \left[ {\frac{1}{2},1} \right)$ точные значения $\mu (3;\varepsilon )$ приведены в теореме 2. Перечислим точные результаты и некоторые оценки, которые влекут теоремы 2, 3, 4, 5 и лемма 1 для $\varepsilon \in \left[ {\frac{1}{3},\;\frac{1}{2}} \right)$:

• при $\varepsilon \in \left[ {\frac{1}{3},\frac{8}{{23}}} \right)$ справедливо $\mu (3;\varepsilon ){\text{'}}$ = 27;

• при $\varepsilon \in \left[ {\frac{8}{{21}},\frac{5}{{13}}} \right)$ справедливо $\mu (3;\varepsilon ) \in [22,24]$;

• при $\varepsilon \in \left[ {\frac{7}{{16}},\frac{4}{9}} \right)$ справедливо $\mu (3;\varepsilon ) \in [17,21]$;

• при $\varepsilon \in \left[ {\frac{4}{9},\frac{7}{{15}}} \right)$ справедливо $\mu (3;\varepsilon ) \in [16,18]$;

• при $\varepsilon \in \left[ {\frac{7}{{15}},\frac{1}{2}} \right)$ справедливо $\mu (3;\varepsilon ) = 15$.