| Математические заметки |
|
|
|
|
|
Об аддитивной сложности некоторых числовых последовательностей И. С. Сергеев Научно-исследовательский институт "Квант", г. Москва
Англоязычная версия:
Mathematical Notes, 2024, Volume 115, Issue 3, Pages DOI: https://doi.org/10.1134/S0001434624030106 
Реферативные базы данных:
  ВведениеМодель целочисленных векторных аддитивных цепочек является одним из простейших средств вычислений: она использует только одну операцию сложения. При этом результаты о сложности аддитивных цепочек лежат в фундаменте теории синтеза управляющих систем и быстрых вычислений и имеют многочисленные приложения. Подробное введение в теорию аддитивных вычислений и обзор современных результатов в этой области можно найти, например, в [1], [2]. Напомним основные понятия. Векторная аддитивная цепочка в $\mathbb{Z}^n$ определяется как последовательность где $e_i=(0, \dots, 0, 1, 0, \dots, 0)$ – базисный вектор с $i$-й единичной и остальными нулевыми координатами, а остальные вектора являются суммами $y_k=g_k+h_k$, где $g_k,h_k \in \{e_1, \dots, e_n, y_1, \dots, y_{k-1} \}$ при любом $k$. Число $L\geqslant 0$ называется длиной цепочки.Векторная аддитивная цепочка (0.1) вычисляет матрицу $A$ размера ${m \times n}$ (т.е. матрицу из $m$ строк и $n$ столбцов), если все строки матрицы содержатся среди векторов $e_i$ и $y_k$. Аддитивной сложностью матрицы $A$ называется длина кратчайшей цепочки, вычисляющей ее, и обозначается через $\mathsf{L}(A)$. В частном случае $n=1$ речь идет о построении обыкновенной (одномерной) аддитивной цепочки $1, y_1, \dots, y_L$ для набора чисел $a_1, \dots, a_m$. Сложность вычисления набора чисел мы обозначаем через $\mathsf{L}(a_1, \dots, a_m)$. Изображение аддитивной цепочки в виде ациклического графа называется аддитивной схемой. Это схема из функциональных элементов над базисом из единственной операции сложения. С точки зрения сложности модели аддитивных схем и цепочек равнозначны. Некоторые рассуждения удобнее выполнять в терминах аддитивных схем. Обозначим $E_q=\{0, 1, \dots, q-1 \}$. Пусть $\mathsf{LL}(q,m,n)$ обозначает сложность класса всех $m \times n$ матриц c коэффициентами из $E_q$, т.е. сложность самой сложной матрицы из класса. Далее по тексту все логарифмы без указания основания – двоичные. Обобщая классические результаты Брауэра [3] и Эрдёша [4] о длине обыкновенных аддитивных цепочек, Пиппенджер [5] получил при $H=mn\log_2 q \to \infty$ универсальные верхнюю и нижнюю оценки
$$
\begin{equation}
\mathsf{LL}(q,m,n) \leqslant \min\{m,n\}\log_2 q+(1+\tau(H))\frac{H}{\log_2 H}+O(m+n),
\end{equation}
\tag{0.2}
$$
$$
\begin{equation}
\mathsf{LL}(q,m,n) \geqslant \min\{m,n\}\log_2 q+(1-\delta(H))\frac{H}{\log_2 H}-O(m+n),
\end{equation}
\tag{0.3}
$$
где1 $\tau(H) \asymp \sqrt{{\log\log H}/{\log H}}$ и $\delta(H) \asymp {\log\log H}/{\log H}$. В указанных оценках первое слагаемое отвечает размеру коэффициентов: оно доминирует, когда $m$ и $n$ малы относительно $q$. Второе слагаемое мощностное: оно отвечает разнообразию матриц и доминирует, когда $m$ и $n$ велики. Эти два слагаемых установлены асимптотически точно. Третье слагаемое в верхней оценке (0.2), как мы покажем далее, можно уточнить до $n$:
$$
\begin{equation}
\mathsf{LL}(q,m,n) \leqslant \min\{m,n\}\log_2 q+(1+\tau(H))\frac{H}{\log_2 H}+n.
\end{equation}
\tag{0.4}
$$
Это слагаемое отвечает за связность цепочки2 и соответствует размерности векторного пространства. Оно тоже асимптотически неустранимо, как показывает тривиальный пример $\mathsf{LL}(2,1,n)=n-1$. Доказательство получается непосредственным переносом аналогичного результата автора [6] о сложности вентильных схем на модель аддитивных цепочек. Отметим, что в случае $\min\{m,n\}=1$ (вычисление векторов) верхняя оценка (0.4) установлена Кочергиным [2] для более общей постановки задачи. Далее мы рассмотрим несколько задач о сложности вычисления специальных множеств (или последовательностей) чисел. В работе [7] поставлен вопрос о сложности набора чисел $2,2^2,\dots,2^{n-1},2^n-1$. Авторы показали, что
$$
\begin{equation}
n+\sqrt n - 2 \leqslant \mathsf{L}(2,2^2,\dots,2^{n-1},2^n-1) \leqslant n+\frac3{\sqrt2}\sqrt n+\log n.
\end{equation}
\tag{0.5}
$$
Мы докажем более точную в асимптотическом смысле оценку:
$$
\begin{equation}
\mathsf{L}(2,2^2,\dots,2^{n-1},2^n-1)=n+2\sqrt n+O(\sqrt[4]n),
\end{equation}
\tag{0.6}
$$
при этом существенно упростив доказательство из [7]. Фактически рассмотренный пример ставит вопрос о сложности вычислений в базисе из степеней двойки, когда в качестве входов цепочки можно бесплатно использовать любой вектор с одной ненулевой координатой вида $2^k$. Соответствующий функционал сложности обозначим через $\mathsf{L}^*(A)$. Соотношение (0.6) означает, что $\mathsf{L}^*(2^n-1)\sim2\sqrt n$. В общем случае несложно выводится оценка
$$
\begin{equation*}
\max_{n \leqslant N} \mathsf{L}^*(n) \sim \frac{\log N}{\log\log N}.
\end{equation*}
\notag
$$
В третьей части работы исследуется задача получения нетривиальных нижних оценок сложности явно (конструктивно) заданных3 числовых последовательностей $b_1, \dots, b_n$. Центральным вопросом является возможность получения нижних оценок вида $n+\Omega(n)$ для последовательностей с полиномиальным размером элементов, $b_k= n^{O(1)}$. Для наборов чисел экспоненциального размера подобные оценки получаются тривиально. Вероятно, рекордным известным результатом является оценка для степенных последовательностей $\mathsf{L}(2^p,3^p,\dots,n^p) \geqslant n+ n^{2/3-o(1)}$ при $p \geqslant 2$, доказанная Добкиным и Липтоном [8]. Мы покажем, что для свободных от сумм $\mathcal{B}_k$-множеств, т.е. множеств с попарно различными $k$-элементными суммами, имеют место оценки вида $n+ \Omega(n^{k/(k+1)})$. Доказательство опирается на верхнюю оценку максимального числа ребер в графе с $n$ вершинами без циклов четной длины от 4 до $2k$. Мы устанавливаем простую универсальную оценку для этой величины: $\operatorname{ex}(n,\overline{\mathcal{C}}_{2k}) \leqslant n^{1+1/k}+2n$. Известные верхние оценки, например, [9], дают правильный порядок роста только при постоянных или очень медленно растущих $k$. Как следствие доказанной нижней оценки сложности, известные конструкции $\mathcal{B}_k$-множеств (например, [10]) позволяют при любом $\varepsilon > 0$ построить явные примеры последовательностей длины $n$ и сложности $n+ \Omega(n^{1-\varepsilon})$ с полиномиальным размером элементов. Для этого параметр $k$ выбирается постоянным. При растущих $k$ явные примеры достаточно плотных $\mathcal{B}_k$-множеств, вероятно, не были раньше описаны. Мы покажем, как при любых $k,n$ конструктивно построить $\mathcal{B}_k$-множество мощности $n$, имеющее размер элементов $n^{k+o(k)}$. Как следствие, получаем пример множества $B$ мощности $n$ с размером элементов $n^{O(\log n)}$ и имеющего сложность $n+\Omega(n)$. В заключение мы покажем, что нижняя оценка сложности $\mathcal{B}_k$-множеств достигается, во всяком случае, при $k=2$: можно построить свободное от сумм $\mathcal{B}_2$-множество (множество Сидона) мощности $n$ и сложности $n+O(n^{2/3})$. 1. Сложность класса матрицНапомним, что вентильная схема – это ориентированный ациклический граф, некоторые вершины которого отмечены как входы, а некоторые вершины отмечены как выходы, с условием: вершины-входы не имеют входящих ребер, а вершины-выходы не имеют исходящих ребер. Вентильная схема с $n$ входами и $m$ выходами реализует целочисленную матрицу размера $m \times n$, которая определяется так: на пересечении $i$-й строки и $j$-го столбца стоит число ориентированных путей, соединяющих $j$-й вход и $i$-й выход схемы. Подробнее см., например, в [2], [6]. Сложность вентильной схемы – это число ее ребер. Простое соотношение между сложностью матриц в моделях вентильных схем и аддитивных цепочек устанавливает Лемма 1. Если матрица $A$ вычисляется вентильной схемой из $r$ ребер и $p$ вершин, не считая входов, то $\mathsf{L}(A) \leqslant r-p$. В частности, для матрицы размера $m \times n$ выполнено $\mathsf{L}(A) \leqslant r-m$. Доказательство. Вентильная схема преобразуется в аддитивную при помощи следующего правила, последовательно применяемого от входов к выходам. Пучок из $k$ ребер вентильной схемы, входящих в произвольную вершину, преобразуется в дерево из $k-1$ элементов сложения (или цепочку такой же длины). Лемма 1 доказана. Далее $\mathsf{W}(q,m,n)$ обозначает сложность класса4 $m \times n$ матриц с коэффициентами из $E_q$ при реализации вентильными схемами. Для $m \times n$ матрицы $A$ без нулевых строк и столбцов выполняется соотношение известное как принцип транспонирования. Принцип, видимо, впервые сформулирован в работе [11]. Как следствие, Вентильная сложность матриц не изменяется при транспонировании; таким образом, $\mathsf{W}(q,m,n)=\mathsf{W}(q,n,m)$.Модификация доказательства теоремы 3 и следствия 3 из [6] приводит к следующему результату. Теорема 1. Пусть $m \leqslant n$ и $H=mn\log_2 q \to \infty$. Тогда где $\tau(H) \asymp \sqrt{{\log\log H}/{\log H}}$. Доказательство. Случай I: $q \leqslant n/\log^3 n$. Если $m \geqslant \log^2 n$, то воспользуемся оценкой теоремы 2 из [6]:
$$
\begin{equation}
\mathsf{W}(q,m,n) \leqslant (1+\tau_1(n))\frac{H}{\log H}, \qquad \tau_1(n) \asymp \sqrt{\frac{\log\log n}{\log n}}.
\end{equation}
\tag{1.4}
$$
Если $m \leqslant \log^2 n$, то применим следствие 2 из [6]:
$$
\begin{equation*}
\mathsf{W}(q,m,n) \leqslant (1+\tau_2(m,n))\frac{H}{\log H}+n, \qquad \tau_2(m,n) \asymp \frac{\log(m\log n)}{\log n}.
\end{equation*}
\notag
$$
При помощи леммы 1 в обоих случаях получаем
Случай II: $q \geqslant n/\log^3 n$. Рассмотрим произвольную $m \times n$ матрицу $A$ над $E_q$. Пусть $2^{k(t-1)} < q \leqslant 2^{kt}$ при подходящих $k,t \in \mathbb N$. Используя запись в двоичной системе счисления, каждый из элементов $a_{i,j}$ матрицы $A$ представим в виде
$$
\begin{equation*}
a_{i,j}=b \cdot D_{i,j} \cdot c^T, \qquad b=(1,2^k,2^{2k},\dots, 2^{(t-1)k}), \qquad c=(1,2,2^2,\dots,2^{k-1}),
\end{equation*}
\notag
$$
где $D_{i,j}$ – матрица размера $t \times k$ над $E_2$. Тогда справедливо5
$$
\begin{equation*}
\begin{gathered} \, A=(a_{i,j})=B D C, \qquad B= \begin{pmatrix} b & 0 & \cdots & 0 \\ 0 & b & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & b \end{pmatrix}_{m \times mt}, \\ D=\begin{pmatrix} D_{1,1} & \cdots & D_{1,n} \\ \vdots & \ddots & \vdots \\ D_{m,1} & \cdots & D_{m,n} \end{pmatrix}_{mt \times nk}, \qquad C=\begin{pmatrix} c^T & 0 & \cdots & 0 \\ 0 & c^T & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & c^T \end{pmatrix}_{nk \times n}. \end{gathered}
\end{equation*}
\notag
$$
Схему для матрицы $A$ можно построить, соединяя последовательно схемы для матриц $C$, $D$ и $B$. Получаем
$$
\begin{equation}
\mathsf{L}(A) \leqslant \mathsf{L}(B)+\mathsf{L}(D)+\mathsf{L}(C) \leqslant m(k+1)(t-1)+ \mathsf{LL}(2,mt,nk)+(k-1)n.
\end{equation}
\tag{1.6}
$$
Подслучай II.1: $2^n \geqslant q \geqslant n/\log^3 n$. Выберем $k=1$, при этом $t=\lceil \log q \rceil$. Тогда (1.6) упрощается до
$$
\begin{equation*}
\mathsf{L}(A) \leqslant \mathsf{L}(B)+\mathsf{L}(D) \leqslant 2m(t-1)+\mathsf{LL}(2,mt,n).
\end{equation*}
\notag
$$
Для оценки величины $\mathsf{LL}(2,mt,n)$ воспользуемся анализом случая I. При $mt \leqslant n$ соотношение (1.5) влечет
$$
\begin{equation*}
\mathsf{LL}(2,mt,n) \leqslant (1+\tau_3(mnt))\frac{mnt}{\log (mnt)}+n - mt.
\end{equation*}
\notag
$$
При $mt \geqslant n$ (но $n\geqslant \log^2(mt)$ в силу $mt \leqslant n^2$) с помощью леммы 1 ввиду $\mathsf{W}(q,m,n)=\mathsf{W}(q,n,m)$ из (1.4) выводим
$$
\begin{equation*}
\mathsf{LL}(2,mt,n) \leqslant \mathsf{W}(2,n,mt)-mt \leqslant (1+\tau_1(mnt))\frac{mnt}{\log (mnt)} - mt.
\end{equation*}
\notag
$$
В обеих ситуациях с учетом $mnt=H(1+O(1/\log H))$ получаем
$$
\begin{equation}
\begin{aligned} \, \notag \mathsf{L}(A) &\leqslant 2m(t-1)+(1+\tau_3(mnt))\frac{mnt}{\log (mnt)}+n - mt \\ &\leqslant m\log q+(1+\tau_4(H))\frac{H}{\log H}+n, \qquad \tau_4(x) \asymp \sqrt{\frac{\log\log x}{\log x}}. \end{aligned}
\end{equation}
\tag{1.7}
$$
Подслучай II.2: $q \geqslant 2^n$. Выберем $t \leqslant k=\lceil \sqrt{\log q}\rceil$. Ввиду $mt \geqslant t \geqslant \sqrt{\log q} -1 \geqslant \log^2(nk)$, величину $\mathsf{LL}(2,mt,nk)$ в (1.6) можно оценить при помощи (1.4) и леммы 1 как
$$
\begin{equation*}
\mathsf{LL}(2,mt,nk) \leqslant (1+\tau_1(nk))\frac{mtnk}{\log(mtnk)} - mt.
\end{equation*}
\notag
$$
Замечая, что $\sqrt{H} \preceq nk \preceq H^{3/4}$ и
$$
\begin{equation*}
mtnk=mn\Bigl(\log q+O(\sqrt{\log q})\Bigr)=H\biggl(1+O\biggl(\frac{1}{\sqrt[6]{H}}\biggr)\biggr),
\end{equation*}
\notag
$$
окончательно получаем
$$
\begin{equation}
\begin{aligned} \, \notag \mathsf{L}(A) &\leqslant mk(t-1)+(1+\tau_1(nk))\frac{mtnk}{\log(mtnk)}+(k-1)n \\ &\leqslant m\log q+(1+\tau_5(H))\frac{H}{\log H}, \qquad \tau_5(x) \asymp \sqrt{\frac{\log\log x}{\log x}}. \end{aligned}
\end{equation}
\tag{1.8}
$$
Совместно (1.5), (1.7) и (1.8) влекут утверждение теоремы при $\tau=\max\{\tau_3,\tau_4,\tau_5\}$. Теорема 1 доказана. Применяя в случае $m \geqslant n$ принцип транспонирования (1.2), получаем уточнение оценки (0.2). Следствие 1. Пусть $H=mn\log_2 q \to \infty$. Тогда где $\tau(H) \asymp \sqrt{{\log\log H}/{\log H}}$. Отметим, что при некоторых соотношениях между $m$, $n$ и $q$ можно получать оценки типа (1.9) с “правильным” в свете (0.3) порядком величины остаточного члена $\tau(H) \asymp {\log\log H}/{\log H}$, см. [6]. 2. Цепочки в базисе из степеней двойкиВ этом пункте мы рассматриваем цепочки, в которых степени двойки можно использовать бесплатно. Для краткости будем называть их $0$-цепочками. Напомним, что соответствующий функционал сложности был обозначен через $\mathsf{L}^*$. Сначала приведем уточнение результата (0.5) о сложности набора чисел $2, 2^2, \dots, 2^{n-1}, 2^n-1$ из работы [7]. Очевидно, для любого $m$ при условии $m < 2^n$ выполняется
$$
\begin{equation*}
\mathsf{L}(2,2^2,\dots,2^{n-1},m)=\mathsf{L}^*(m)+n - 1.
\end{equation*}
\notag
$$
Поэтому оценка (0.6) автоматически вытекает из следующего результата. Доказательство. Нижняя оценка. Произвольную 0-цепочку можно представить как аддитивную схему со входами $x_i=2^i$ (или как векторную цепочку с базисными элементами $e_i$, соответствующими степеням двойки $2^i$). Пусть минимальная 0-цепочка вычисляет число $2^n-1$ в виде $\sum a_i 2^i$ (коэффициенты $a_i$ здесь какие угодно). Тогда эквивалентная ей схема вычисляет вектор $a=(a_0, a_1, \dots, a_{n-1})$.
Пусть $k$ – число ненулевых компонент вектора $a$. Далее $\nu(m)$ обозначает двоичный вес6 числа $m$. Положим $b=\max_i \nu(a_i)=\nu(a_j)$. Из $\nu(2^n-1)=n$ и из субаддитивности веса, $\nu(x+y) \leqslant \nu(x)+\nu(y)$, вытекает $b \geqslant n/k$. Используя принцип транспонирования (1.1) и простое неравенство $\mathsf{L}(x) \geqslant \nu(x)-1$, получаем требуемую оценку7:
$$
\begin{equation*}
\mathsf{L}^*(2^n-1)=\mathsf{L}(a)=\mathsf{L}(a^T)+k - 1 \geqslant \mathsf{L}(a_j)+k-1 \geqslant b+ k - 2 \geqslant\frac nk+k - 2 \geqslant 2\sqrt n -2.
\end{equation*}
\notag
$$
Верхняя оценка. Доказательство близко к оригинальному методу [7]. Выберем $m$ и $t$ из условий $(m-1)^2 < n \leqslant m^2$ и $m^2 - t^2 < n \leqslant m^2 - (t-1)^2$. Положим $k=m-t$ и $l=m+t-1$. Тогда
$$
\begin{equation*}
2^n-1=(2^k-1)(1+2^k+2^{2k}+\dots+2^{lk})+[2^{m^2-t^2+1}+2^{m^2-t^2+2}+\dots+ 2^{n-1}].
\end{equation*}
\notag
$$
Вычислим сумму $1+2^k+2^{2k}+\dots+2^{lk}$ при помощи $l$ операций, затем умножим ее на $2^k-1$, используя построенную методом Брауэра [3] аддитивную цепочку для $2^k-1$, используя еще $k+\mathsf{L}(k)-1 \leqslant k+2\log k$ сложений. К результату добавим слагаемые в квадратных скобках – по построению, их не более $2t$ штук. Окончательно имеем
$$
\begin{equation*}
\mathsf{L}^*(2^n-1) \leqslant l+k+2\log k+2t=n+2m+O(\sqrt m),
\end{equation*}
\notag
$$
поскольку $t \leqslant \sqrt{2m}$. Теорема 2 доказана. Установление асимптотики функции Шеннона сложности 0-цепочек значительно проще, чем в случае обычных аддитивных цепочек, поскольку фактор размера не действует, а остается только фактор разнообразия. Для демонстрации ограничимся самым простым одномерным случаем. Доказательство. Нижняя оценка. Оценим число $D_l$ различных 0-цепочек длины $l \leqslant \log N$ для вычисления чисел, не превосходящих $N$. Считаем, что элементы цепочки упорядочены по возрастанию. Входы для очередного элемента цепочки можно выбрать не более чем $(\log N+l)^2$ способами. Поэтому
$$
\begin{equation*}
D_l \leqslant C_{(\log N+l)^2}^l \leqslant \frac{(2\log N)^{2l}}{l!} \leqslant \biggl(\frac{4e\log^2 N}{l}\biggr)^l
\end{equation*}
\notag
$$
в силу стандартного неравенства $l! \geqslant (l/e)^l$. В предположении, что длины $l$ достаточно для вычисления любого числа в интервале8 $[l+1,N]$, накладываем условие $D_l \geqslant N-l$, откуда получаем требуемую оценку $l \geqslant (1-o(1))\log N / \log\log N$.
Верхняя оценка. Используем упрощенный вариант $2^k$-арного метода Брауэра [3]. Пусть $2^{(t-1)k} \leqslant n < 2^{tk}$. Запишем число $n$ в $2^k$-арной системе счисления: $n= \sum_{j=0}^{t-1} n_j 2^{jk}$, где $0 \leqslant n_j < 2^k$. Вычислим $n$ как
$$
\begin{equation}
n=\sum_{m=1}^{2^k-1} m\cdot \sum_{j\colon n_j=m} 2^{jk}.
\end{equation}
\tag{2.1}
$$
Внешние и внутренние суммы в (2.1) вычисляются в общей сложности не более чем за $t$ сложений. Умножение на $m$ выполняется аддитивной цепочкой длины $\mathsf{L}(m) \leqslant 2k$. При выборе $k=\lceil \log\log n - 3 \log\log\log n \rceil$ получаем
$$
\begin{equation*}
\mathsf{L}^*(n) \leqslant 2k2^k+t \leqslant 2k2^k +\frac{\log n}k+1\sim \frac{\log n}{\log\log n}.
\end{equation*}
\notag
$$
Теорема 3 доказана. Таким образом, в типичном случае $\mathsf{L}^*(N) \sim \mathsf{L}(N) - \log N$, а случай $N=2^n-1$ исключительный. Напомним, что $\mathsf{L}(2^n-1)=n-1 +O(\log n)$, см. [1], [3]. Представляет интерес получение нижних оценок вида $\mathsf{L}^*(n) \succ \sqrt{\log n}$ для конкретно заданных чисел $n$. 3. Сложность числовых последовательностейВ этом разделе мы обсудим методы получения нижних оценок сложности для конкретных числовых последовательностей. Начнем с тривиальной оценки, исходящей из экспоненциального размера чисел. Положим $\alpha > 1$. Возрастающую последовательность $b_1, b_2, \dots$ назовем $\alpha$-последовательностью, если для некоторых $a,c > 0$ выполнено ${|b_k - a\alpha^k| < c}$ при любом $k$. Лемма 2. Пусть $B=\{b_k\}$ – $\alpha$-последовательность, и $\alpha$ не является корнем никакого многочлена $x^p - x^q - 1$ при $p>q\geqslant0$. Тогда Доказательство. В силу определения $t$ – минимальное натуральное число, при котором $\alpha^t > \alpha^{t-1}+1$. Тогда при всех $n \geqslant n_0=n_0(\alpha,a,c)$ выполнено $b_{n} > b_{n-1}+b_{n-t}$. Поскольку множество $\{\alpha^p-\alpha^q -1 \mid t \geqslant p > q \geqslant 0 \}$ отделено от нуля, для любого $n \geqslant n_1 =n_1(\alpha,a,c)$ равенство $b_n=b_i+b_j$ при $i,j < n$ невозможно. Следовательно, любая цепочка, вычисляющая члены последовательности $B$, в каждом интервале $(b_{n-t},b_n)$, где $n \geqslant n_1$, содержит дополнительный элемент не из $B$. Лемма 2 доказана. Приведем пару простых примеров. Последовательность степеней тройки является быстрорастущей. Доказательство леммы влечет (так как $n_1=1$) Последовательность чисел Трибоначчи определяется как
$$
\begin{equation*}
T_0=1, \qquad T_1=2, \qquad T_2=4, \qquad T_{k}=T_{k-1}+T_{k-2}+T_{k-3}, \quad k\geqslant3.
\end{equation*}
\notag
$$
Рассуждение леммы 2 (в данном случае $n_1=3$) позволяет вывести Для медленно (т.е. субэкспоненциально) растущих последовательностей нижние оценки сложности вида $n+\Omega(n)$ вероятно до сих пор не были известны. Авторами [8] получены оценки $\mathsf{L}(2^p,3^p,\dots,n^p) \geqslant n+n^{2/3-o(1)}$ при $p \geqslant 2$. Наиболее удобным объектом для приложения предложенной в [8] схемы рассуждения являются множества Сидона, свободные от сумм. Множество $B$ элементов некоторой коммутативной группы называется $\mathcal{B}_k$-множеством, $k \geqslant 2$, если все $k$-элементные суммы над $B$ попарно различны, т.е. равенство выполняется только в том случае, когда совпадают мультимножества9 слагаемых: $\{a_1, \dots, a_k\}=\{b_1, \dots, b_k\}$. Отметим, что $\mathcal{B}_k$-множество одновременно является $\mathcal{B}_l$-множеством при любом $l < k$.$\mathcal{B}_2$-множества, т.е. множества с различными попарными суммами, называются множествами Сидона10. Далее обозначение $A+B$ используется для суммы Минковского двух множеств, $A+B=\{a+b \mid a \in A,\, b \in B\}$. Множество $B$ называется свободным от сумм, если $(B+B)\cap B=\emptyset$. Для доказательства нам понадобится достаточно точная по порядку оценка числа ребер в графе без коротких циклов четной длины. Напомним, что $\operatorname{ex}(n,{\mathcal G})$ обозначает максимальное число ребер в $n$-вершинном графе, не содержащем подграфов, изоморфных графам из семейства ${\mathcal G}$. Пусть $\mathcal{C}_l$ обозначает цикл длины $l$ (без самопересечений), а $\overline{\mathcal{C}}_{2k}=\{\mathcal{C}_4, \mathcal{C}_6, \dots, \mathcal{C}_{2k} \}$ – множество коротких четных циклов. Нас интересует возможность оценить сверху $\operatorname{ex}(n,\overline{\mathcal{C}}_{2k})$ величиной вида $cn^{1+1/k}$ с абсолютной константой $c$. Судя по всему, известные результаты не дают непосредственно такой оценки. Так, из работы [13] следует
$$
\begin{equation*}
\operatorname{ex}(n,\overline{\mathcal{C}}_{2k}) \leqslant \operatorname{ex}(n,\mathcal{C}_{2k}) \leqslant 100 k n^{1+1/k}
\end{equation*}
\notag
$$
(константа 100 впоследствии уточнялась). Эта оценка при непостоянном $k$ недостаточна для наших целей. В работе [9] получена более точная при малых $k$ оценка
$$
\begin{equation*}
\operatorname{ex}(n,\overline{\mathcal{C}}_{2k}) \leqslant \frac12n^{1+1/k}+2^{k^2}n,
\end{equation*}
\notag
$$
но она оказывается слишком грубой при $k \succ \sqrt[3]{\log n}$. Предполагается, что справедливо $\operatorname{ex}(n,\overline{\mathcal{C}}_{2k}) \asymp n^{1+1/k}$, но это пока не доказано даже для постоянных $k$. Мы заметим, что абсолютную верхнюю оценку, довольно грубую, но имеющую нужный порядок роста, несложно получить рассуждением в духе обоснования границы Мура для числа вершин в регулярном графе с ограничением на длину минимального цикла. Лемма 3. Справедливо неравенство $\operatorname{ex}(n,\overline{\mathcal{C}}_{2k}) \leqslant n^{1+1/k}+2n$. Доказательство. Рассмотрим произвольный граф $G$ на $n$ вершинах без циклов четной длины вплоть до $2k$. Сведем рассмотрение к графу, степени вершин которого ограничены снизу. Пусть $d \in \mathbb N$ – параметр, который будет выбран позже. Последовательно будем удалять из графа $G$ вершины степени $\leqslant d$ вместе с инцидентными им ребрами до тех пор, пока не получим граф $G'$, в котором все вершины имеют степень $>d$. (Возможно, при этом граф окажется пустым.)
Пусть в ходе процедуры удалено $s$ вершин. При этом удалено не более $ds$ ребер. Конечно, граф $G'$ так же, как и исходный граф, не содержит циклов из $\overline{\mathcal{C}}_{2k}$. Если граф $G'$ не пуст, то выберем произвольную вершину $v \in G'$. Обозначим через $V_r$ множество вершин, удаленных на расстояние $r$ от $v$. Задача состоит в оценке снизу мощности множества $V_k$. I. Сначала заметим, что кратчайший путь от $v$ до любой вершины $w \in V_r$, где $r \leqslant k$, – единственный. Действительно, предположим, что найдутся два таких пути. Поскольку оба пути кратчайшие, общие вершины в них одинаково удалены от $v$ (и от $w$). При этом пути имеют по крайней мере две общих вершины: $v$ и $w$. Поэтому в них найдутся отрезки равной длины $\geqslant 2$ с одинаковыми концами, не пересекающиеся по внутренним вершинам. Но объединение этих отрезков образует цикл четной длины от $4$ до $2k$, что противоречит условию на граф $G'$. II. Теперь проверим по индукции, что $|V_r| \geqslant (d-1)^r$ при $1 \leqslant r \leqslant k$. В случае $r=1$ утверждение очевидно. Докажем индуктивный переход от $r$ к $r+1$. По предположению, $V_r$ содержит не менее $(d-1)^r$ вершин. Каждая из этих вершин имеет не менее $d+1$ соседей, и только один из них находится ближе к $v$ (на кратчайшем пути). Следовательно, остальные соседние вершины удалены от $v$ на расстояние $r$ или $r+1$. Покажем, что произвольная вершина $w \in V_r$ имеет не более одного соседа в $V_r$. Предположим, что вершина $w$ имеет соседей $v_1, v_2 \in V_r$. Рассмотрим кратчайшие пути из $v$ в $v_1$ и $v_2$ и выделим в них отрезки от последней общей вершины до $v_1$ и $v_2$ (отрезки имеют одинаковую длину от $1$ до $r \leqslant k-1$ в силу сказанного выше). Объединив эти отрезки с ребрами $(w,v_1)$ и $(w,v_2)$, получим цикл четной длины от $4$ и $2k$, что невозможно. Следовательно, любая вершина в $V_r$ имеет не менее $d-1$ соседей из $V_{r+1}$. Общее число учтенных таким образом соседей не меньше ${(d-1)^{r+1}}$, и все они различны, поскольку кратчайший путь длины $r+1\leqslant k$ определен однозначно. Индуктивный переход доказан. Как следствие, число вершин в непустом графе $G'$ оценивается как Поэтому при выборе $d=\lceil n^{1/k} \rceil+1$ граф $G'$ всегда будет пуст. Следовательно, исходный граф $G$ содержит не более $nd \leqslant n^{1+1/k}+2n$ ребер. Лемма 3 доказана. Далее помимо графов, в которых по определению нет петель – ребер с одинаковыми концами – нам будет удобно рассматривать графы, в которых петли допускаются. Будем называть их псевдографами. Обыкновенный граф – это частный случай псевдографа. Стандартным образом из доказанной леммы вытекает Утверждение 1. Пусть $A \subset \mathbb{N}$ и $B \subset (A+A)$ – $\mathcal{B}_k$-множество. Тогда $|B| \leqslant |A|^{1+1/k}+3|A|$. Доказательство. Построим псевдограф на вершинах, помеченных элементами множества $A$, и имеющий ребра $(a,b)$ ровно в тех случаях, когда $a+b \in B$. Исключим из него повторы – если ребра $(a,b)$ и $(a',b')$ имеют одинаковую сумму $a+b=a'+b'$, то одно из ребер удаляется из графа. Полученный псевдограф обозначим через $G_B$. Через $G^*_B$ обозначим граф, получаемый из $G_B$ удалением петель.
Проверим, что граф $G^*_B$ не имеет циклов четной длины $2r$ при любом $r$ в пределах $2 \leqslant r \leqslant k$. Действительно, если бы некоторый цикл $(a_1,a_2, \dots,a_{2r})$, где $a_i \in A$, принадлежал графу, то выполнялось бы равенство
$$
\begin{equation*}
b_{1,2}+b_{3,4}+\dots+b_{2r-1,\,2r}=b_{2,3}+\dots+b_{2r-2,\,2r-1}+b_{2r,1}, \qquad b_{i,j}=a_i+a_j \in B,
\end{equation*}
\notag
$$
в котором все $b_{i,j}$ различны (в графе нет повторов). Но указанное равенство противоречит определению $B$ как $\mathcal{B}_k$-множества.
Пусть $|A|=n$. Согласно лемме 3, граф $G^*_B$ содержит не более $n^{1+1/k}+2n$ ребер, следовательно, псевдограф $G_B$ содержит не более $n^{1+1/k}+3n$ ребер. Утверждение 1 доказано. Доказательство теоремы 4. Рассмотрим минимальную аддитивную цепочку для $B$. По условию ни один из элементов $b \in B$ не может быть вычислен как сумма $b'+b''$, где $b',b'' \in B$.
Обозначим через $C$ множество элементов цепочки, являющихся разностями двух элементов из $B$. Если $c \in C$, то некоторый элемент $b \in B$ может быть вычислен как $b=b'+c$, где $b' \in B$. При этом элемент $b$ определяется однозначно: разности различных элементов из $B$ попарно различны11. Обозначим множество всех таких элементов $b$ как $B'=B \cap (B+C)$. Любой из оставшихся элементов $b \in B \setminus B'$ вычисляется в цепочке как сумма $a'+a''$, где $a',a'' \notin B$. Обозначим через $A$ множество всех элементов $a',a''$ в таких суммах (оно может пересекаться с $C$). Из утверждения 1 вытекает откуда $|B| \leqslant 5|A \cup C|^{1+1/k}$. Как следствие,
$$
\begin{equation*}
\mathsf{L}(B) \geqslant |B|+|A \cup C| \geqslant |B|+\frac15|B|^{k/(k+1)}.
\end{equation*}
\notag
$$
Теорема 4 доказана. Заметим, что при $k \geqslant 3$ условие быть свободным от сумм в формулировке теоремы 4 не слишком принципиально. Несложно проверить, что не более половины элементов $\mathcal{B}_3$-множества $B$ могут быть вычислены как суммы других элементов из $B$. В остальном повторяя доказательство теоремы, можно вывести оценку, аналогичную (3.1), для сложности произвольного $\mathcal{B}_k$-множества, $k \geqslant 3$, не обязательно свободного от сумм. При $k=2$ контрпримером служит множество $\{2, 2^2,\dots,2^n\}$. Впрочем, условие быть свободным от сумм можно ослабить до условия быть свободным от удвоений. Конкретные примеры $\mathcal{B}_k$-множеств известны. Напомним универсальную конструкцию практически максимально плотных $\mathcal{B}_k$-множеств, предложенную Боузом и Чоулой [10]. Пусть $GF(q)=\{\alpha_1,\dots,\alpha_q\}$, и $x$ – примитивный элемент поля $GF(q^k)$. Положим
$$
\begin{equation*}
D[q,k]=\{d_i \mid x^{d_i}=x+\alpha_i,\, 1\leqslant d_i < q^k \}.
\end{equation*}
\notag
$$
Множество $D[q,k]$ (как легко проверить) является $\mathcal{B}_k$-множеством мощности $q$ в $\mathbb N$ и даже в $\mathbb Z_{q^k-1}$. Пример $\mathcal{B}_k$-множества, свободного от сумм, можно получить при помощи сдвига. Таким множеством является, скажем, $D[q,k]+q^k$. Указанный пример доказуемо является явным12 только при постоянных (либо очень медленно растущих) $k$, потому что его построение фактически связано с решением задачи дискретного логарифмирования в группе, вообще говоря, негладкого порядка. По всей видимости, явные нетривиальные13 конструкции $\mathcal{B}_k$-множеств для растущих $k$ пока не были известны. Далее мы опишем явную конструкцию $\mathcal{B}_k$-множества, подходящую для наших целей. Пусть $p_1, p_2, \dots$ – записанные в порядке возрастания нечетные простые числа. Положим $r=1+\lceil k\log p_n \rceil$. Множество нечетных чисел-вычетов от 1 до $2^r-1$ образует мультипликативную подгруппу $\mathbb{Z}^*_{2^r}$ кольца $\mathbb{Z}_{2^r}$, которая при $r\geqslant3$ имеет вид прямого произведения циклических групп порядков 2 и $2^{r-2}$, а именно, $\mathbb{Z}^*_{2^r} \cong \langle -1 \rangle_2 \langle 5 \rangle_{2^{r-2}}$, где $-1$ и $5$ – порождающие элементы. Таким образом, любое нечетное число $x$ имеет однозначное представление $x \equiv (-1)^j\cdot 5^h\ (\operatorname{mod} 2^r)$, где $0 \leqslant j \leqslant 1$ и $0 \leqslant h < 2^{r-2}$. Обоснование см., например, в [14]. Положим
$$
\begin{equation*}
H[n,k]=\{h_i \mid p_i \equiv \pm 5^{h_i}\ (\operatorname{mod} 2^r),\, 0 \leqslant h_i < 2^{r-2},\,i=1,\dots,n\}.
\end{equation*}
\notag
$$
Проверим, что построенное множество является $\mathcal{B}_k$-множеством. Согласно выбору $r$, при различных наборах индексов $1 \leqslant i_1 \leqslant \dots \leqslant i_k \leqslant n$ все числа $\pm p_{i_1}\dotsb p_{i_k}$ различны и не превосходят $2^{r-1}-1$ по абсолютной величине. Поэтому различны все вычеты $5^{h_{i_1}+\dots+h_{i_k}}\ (\operatorname{mod} 2^r)$, а следовательно и всевозможные суммы $h_{i_1}+\dots+h_{i_k}$. Множества $H[n,k]$, хоть и уступают по плотности множествам типа $D[q,k]$, все же достаточно плотны в асимптотическом смысле: $\max h_i < 2^{r-2} < p_n^k < (2n\log (n+2))^k$ согласно известным фактам о распределении простых чисел, см., например, [15]. Дискретное логарифмирование в циклической группе порядка $2^{r-2}$ выполняется элементарно, за $O(r^2)$ арифметических операций с ее элементами14. Поэтому множество $H[n,k]$ строится с полиномиальной относительно $kn$ сложностью. Рассматривая при $k \asymp \log n$ свободное от сумм множество $H[n,k]+2^r$, получаем Следствие 4. Можно явно указать множество $B \subset \mathbb{N}$ мощности $n$ с размером элементов $n^{O(\log n)}$, для которого $\mathsf{L}(B)=n+ \Omega(n)$. При этом максимальная нижняя оценка сложности, которая извлекается из теоремы 4, имеет величину $(6/5-\varepsilon)n$ при произвольном $\varepsilon>0$. Отметим, что при растущем $k$ элементы $\mathcal{B}_k$-множества неизбежно имеют сверхполиномиальный размер. Вопрос о построении аналогичного примера с полиномиальным размером элементов остается открытым. В заключение покажем, что оценка теоремы 4 не может быть существенно улучшена, по крайней мере, для множеств Сидона. Теорема 5. При любом $n$ можно указать свободное от сумм множество Сидона $B$ мощности $|B|=n$ и сложности $\mathsf{L}(B)=n+O(n^{2/3})$. Доказательство. Положим $m=\lceil (4n)^{2/3}\rceil$ и $N=(4m)^4$. Используя конструкцию Боуза–Чоулы, можно предъявить $\mathcal{B}_4$-множество $A \subset {[N,\,2N-1]}$ мощности не меньше $m-1$. Для этого выберем ближайший сверху к $m$ примарный квадрат $q^2$. Как известно (теорема Чебышёва), всегда можно полагать $q \leqslant 2\sqrt m$. Положим $A=\{a_1, \dots, a_{q^2-1}\}=N+ (D[q^2,4]\setminus\{1\})$.
Заметим, что равенство $b_1+b_2=b_3+b_4$ для некоторых $b_1,b_2,b_3,b_4 \in (A+A)$ возможно лишь в том случае, когда при подстановке $b_i=a_j+a_k$ равенство обращается в тождество. Составим множество $B' \subset (A+A)$ из всевозможных сумм $a_i+ a_j$, для которых $[(i+j)\ \operatorname{mod} (q^2-1)] \in D[q,2]$. Такой способ гарантирует, что никакие четверки различных сумм $a_i+ a_j, {a_{i'}+a_{j'}}, a_i+a_{j'}, a_{i'}+a_{j}$ не могут принадлежать $B'$. Поэтому $B'$ является множеством Сидона. Оно свободно от сумм ввиду $b < 4N-1 < b'+b''$ при любых $b,b',b'' \in B'$. Мощность множества $B'$ не меньше $q(q^2-1)/2$, поэтому в нем можно выбрать подмножество $B$ мощности $n \leqslant m^{3/2}/4 \leqslant q^3/4 < q(q^2-1)/2$. Получаем согласно (0.2) или (1.9). Теорема 5 доказана.Возвращаясь к задаче о сложности степенных множеств $E_{p,n}=\{2^p, 3^p, \dots,n^p \}$, отметим, что при $p>2$ эти множества свободны от сумм (теорема Ферма), при $p>4$ они предположительно являются множествами Сидона (не доказано и не опровергнуто), а при некоторых $p$ – вероятно даже $\mathcal{B}_k$-множествами с $k>2$. Верхняя оценка $\mathsf{L}(E_{p,n})=n+ o(n)$ известна только в случае квадратов, т.е. при $p=2$ [8]. Автор благодарен рецензенту за замечания, способствовавшие улучшению изложения. 
Цитирование в формате AMSBIB
\RBibitem{Ser24} |
|
||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|