| Математический сборник |
|
|
|
|
|
Быстрые алгоритмы для считающих функций на свободных группах и свободных моноидах А. Л. Таламбуцаa, Т. Хартникb a Математический институт им. В. А. Стеклова Российской академии наук, г. Москва b Institut für Algebra und Geometrie, Karlsruher Institut für Technologie, Karlsruhe, Germany
Англоязычная версия:
Sbornik: Mathematics, 2023, Volume 214, Issue 10, Pages DOI: https://doi.org/10.4213/sm9683e 
Реферативные базы данных:
     § 1. Введение1.1. От комбинаторики слов к квазиморфизмамИзучение слов над конечным алфавитом $S$ является центральной темой исследований во многих областях математики и теоретической информатики, включающих в себя алгебру, комбинаторику, динамические системы, теорию вычислимости и многие другие. В частности, комбинаторика слов интенсивно исследовалась в течение последних 50 лет в алгебре и теоретической информатике, см., например, два разных подхода в книгах [18] и [16]. Фундаментальным для комбинаторики слов является отношение быть подсловом: слово $v=s_1\ldots s_l$, где $s_1, \dots, s_l \in S$ называется подсловом слова $w=r_1 \ldots r_m$, где $r_1, \dots, r_m \in S$, если существует некоторое $j \in \{1, \dots, m-l+1\}$ такое, что $s_i =r_{j+i}$ для всех $i \in \{1, \dots, l\}$; в этом случае мы называем множество $\{j+1, \dots, j+l\}$ вхождением $v$ в $w$. Многие известные задачи комбинаторики слов связаны с данным отношением. Например, вопрос о возможном восстановлении слова длины $N$ по множеству его подслов длины до $f(N)$ был разрешен в работе [16], а также независимо Левенштейном в [15]; было показано, что соответствующей длиной является $f(N)=\lceil (N+1)/2 \rceil$. Если заменить множество подслов на мультимножество подслов, то наилучшей известной на данный момент нижней оценкой является $f(N)\leqslant\lfloor\frac{16}7\sqrt{N}\rfloor+5$, что было установлено в работе Красикова и Родитти [14]. Настоящая работа посвящена следующему численному варианту отношения “быть подсловом”: для двух данных слов $v$ и $w$ над алфавитом $S$ обозначим через $\rho_v(w)$ количество (возможно пересекающихся между собой) вхождений $v$ в $w$; таким образом, по определению неравенство $\rho_v(w) > 0$ выполнено тогда и только тогда, когда $v$ является подсловом $w$. Множество $S^*$ всех слов над $S$ является свободным моноидом, и мы можем рассмотреть $\rho_v$ как функцию $\rho_v\colon S^* \to \mathbb N_0$, которая называется $v$-считающей функцией. Если $v$ окажется словом из одной буквы, то эта считающая функция является в действительности гомоморфизмом моноидов; в общем случае она будет только квазиморфизмом, в том смысле, что
$$
\begin{equation*}
\sup_{w_1, w_2 \in S^*}| \rho_v(w_1w_2)-\rho_v(w_1)-\rho_v(w_2)| < \infty.
\end{equation*}
\notag
$$
Подводя итог, скажем, что подсчет подслов естественным способом определяет квазиморфизмы на свободных моноидах. 1.2. Вычисления в ограниченных когомологиях свободных группХотя о квазиморфизмах моноидов известно не так уж много, существует довольно развитая теория квазиморфизмов на группах, поскольку последние тесно связаны с ограниченными когомологиями (см. [5]) и стабильной коммутаторной длиной (см. [2]). Заметим, что если $F_n$ – это свободная группа ранга $n \geqslant 2$ с базисом $S=\{a_1, \dots, a_n\}$, то мы можем сопоставить элементам $F_n$ несократимые слова над расширенным алфавитом $S^{\pm}=\{a_1, \dots, a_n, a_1^{-1}, \dots, a_n^{-1}\}$. Это позволяет определить для каждого $v \in F_n$ соответствующую $v$-считающую функцию $\rho_v\colon F_n \to \mathbb N_0$. В работе Р. Брукса [1] было отмечено, что симметризация
$$
\begin{equation*}
\varphi_v\colon F_n \to \mathbb Z, \qquad w \mapsto \rho_v(w)-\rho_v(w^{-1})
\end{equation*}
\notag
$$
такой считающей функции является квазиморфизмом на свободной группе; при этом симметризация нужна для того, чтобы компенсировать эффект сокращения в свободной группе. Далее функцию $\varphi_v$ мы будем называть $v$-считающим квазиморфизмом. Конечная линейная комбинация таких квазиморфизмов называется считающим квазиморфизмом, а также иногда квазиморфизмом конечного типа. Аналогично конечные линейные комбинации $v$-считающих функций известны просто как считающие функции. Каждый квазиморфизм $\varphi\colon F_n \to \mathbb R$ порождает ограниченный $2$-коцикл $d\varphi$ на $F_n$, заданный как $d\varphi(x,y):=\varphi(y)-\varphi(xy)+\varphi(x)$, и потому определяет класс во второй группе ограниченных когомологий $H^2_b(F_n; \mathbb R)$ (см. [5]). Мы говорим, что два квазиморфизма являются когомологичными, если они определяют одинаковый класс ограниченных когомологий. В частности, это происходит в случае, когда они находятся друг от друга на ограниченном расстоянии по норме $\ell^\infty$. Из наших предыдущих результатов в работе [9] следует, что вопрос о том, являются ли два данных квазиморфизма (скажем, с коэффициентами в $\mathbb Z$ или $\mathbb Q$) когомологичными, является алгоритмически разрешимым; на самом деле из работы [9] можно извлечь явный алгоритм, который дает ответ на этот вопрос. Этот алгоритм достаточен для многих приложений, см., например, работу Хазе [10], где этот алгоритм применяется для изучения действия группы внешних автоморфизмов $\operatorname{Out}(F_n)$ на группе $H^2_b(F_n; \mathbb R)$. Хотя алгоритм, предложенный в работе [9], вполне применим в теории, для практического применения он не вполне годится. Целью настоящей статьи является построение быстрого алгоритма и анализ его сложности. Наш основной результат может быть сформулирован следующим образом. Теорема 1.1. Пусть $n \geqslant 2$ и $\mathfrak N \in \{\mathbb Z, \mathbb Q\}$. Тогда существует алгоритм, который по двум поданным на вход считающим квазиморфизмам на $F_n$ с коэффициентами из $\mathfrak N$ определяет, являются ли они когомологичными. Более того, этот алгоритм может быть реализован так, что время его работы составит $O(N)$ в случае $\mathfrak N=\mathbb Z$ и $O(N \log N)$ в случае $\mathfrak N=\mathbb Q$, где $N$ обозначает размер входа, а требуемые константы зависят от $n$. Мы дадим более точную формулировку теоремы 1.1 в следствии 5.9 ниже, после того как будет уточнено, какие структуры данных нами используются для кодировки считающих квазиморфизмов. В частности, нами будет точно указано, что имеется в виду под “размером” входных данных. Что касается нашей модели вычислений, всюду далее мы будем работать в модели многоленточной машины Тьюринга. Мы бы хотели отметить несколько следующих модификаций теоремы 1.1. – Вместо того, чтобы определять, являются ли два данных счетных квазиморфизма когомологичными, мы решаем (по существу с тем же самым временем выполнения), находятся ли они на ограниченном расстоянии друг от друга (см. следствие 5.9). – Вместо считающих квазиморфизмов мы можем рассматривать считающие функции, т.е. линейные комбинации $v$-считающих функций. Построенные алгоритмы по-прежнему оказываются применимы с тем же самым временем выполнения. (см. следствие 5.9). – Вместо рассмотрения считающих функций над свободной группой $F_n$ мы также можем рассмотреть считающие функции над свободным моноидом $M_n$. Те же оценки времени выполнения, что и выше, оказываются справедливы и в этом случае, при условии, что $n \geqslant 3$ (см. следствие 3.3). Тот факт, что время выполнения является линейным в случае коэффициентов из $\mathbb Z$ связан с тем, что сложение целых чисел может быть реализовано за линейное время. Напротив, в настоящее время неизвестно, можно ли сложение больших рациональных чисел реализовать за линейное время. Ввиду недавней работы Харви и ван дер Хувена [11] асимптотика функции $T(N):=N \log N$ является лучшей известной на данный момент оценкой временной сложности сложения рациональных чисел размером не более $N$, если последние кодируются как (возможно, сократимые) смешанные дроби (см. обсуждение в § 6); именно по этой причине указанная функция $T(N)$ попадает в формулировки и доказательства наших результатов. Читатель может также удостовериться, что эти результаты верны и для более общих групп коэффициентов $\mathfrak N \subset \mathbb R$, а не только для $\mathbb Z$ или $\mathbb Q$, коль скоро сложение, вычитание и сравнение в $\mathfrak N$ могут быть эффективно выполнены на многоленточной машине Тьюринга. 1.3. О возможных приложенияхТеорему 1.1 можно рассматривать как отправную точку для эффективных вычислений в ограниченных когомологиях свободной группы или, точнее, для эффективных вычислений в ее подпространстве $H^2_{b, \mathrm{fin}}(F_2, \mathbb Q) \subset H^2_{b}(F_2, \mathbb R)$, которое порождается считающими квазиморфизмами с рациональными коэффициентами. Это подпространство весьма примечательно: как указал Григорчук в [6], оно является плотным в $H^2_{b}(F_2, \mathbb R)$ для подходящей топологии (а именно топологии поточечной сходимости однородных представителей, см. [7]), а кроме того, по результату Швайцера и второго автора оно инвариантно относительно естественного действия $\operatorname{Out}(F_n)$ и, следовательно, не зависит от выбранного базиса (см. [7]). Тем не менее нужно отметить, что существует много явных примеров классов в $H^2_{b}(F_2, \mathbb R)$, которые имеют бесконечный тип (т.е. не представимы с помощью конечных сумм $v$-считающих квазиморфизмов), и по-прежнему остается открытой важная проблема проверки, являются ли два таких квазиморфизма когомологичными. Последний вопрос на самом деле актуален за пределами теории свободных групп. А именно, если $G$ – произвольная группа, а $F \subset G$ – конечно порожденная свободная подгруппа, то каждый класс ограниченных когомологий в $G$ сужается до класса ограниченных когомологий группы $F$. Оказывается, что для большого класса групп со слабыми свойствами отрицательной кривизны (а именно, ацилиндрически гиперболических групп в смысле [17]) каждый второй класс ограниченных когомологий однозначно определяется своими ограничениями на (гиперболически встроенные) свободные подгруппы (см. [8]). Это дает сильную мотивацию для поиска алгоритмов, которые определяют, являются ли два заданных квазиморфизма на свободной группе когомологичными. Теорема 1.1 дает решение этой задачи для квазиморфизмов конечного типа, тогда как случай квазиморфизмов бесконечного типа пока остается открытым. 1.4. Структура статьиЦель этой статьи – доказательство теоремы 1.1 и всех вариаций, упомянутых после нее. Оказывается, что рассмотрение считающих функций над свободными моноидами проще, чем считающих квазиморфизмов над свободными группами, но по существу используются те же идеи. Таким образом, в основной части этого текста мы сначала обсудим алгоритмы, связанные со счетными функциями над свободными моноидами. Неформальное обсуждение будет дано в § 2, а после формализации в § 3 необходимых понятий в § 4 с помощью явного построения и анализа требуемого алгоритма будет доказана моноидная версия теоремы 1.1 (т.е. следствие 3.3). В § 5 будет объяснено, как построенный для моноида алгоритм следует модифицировать для группового случая – это требует много дополнительных обозначений, но очень мало дополнительных идей. В § 6 подробно обсуждается реализация арифметических операций для наших групп коэффициентов, поскольку это существенно влияет на время выполнения конструируемых алгоритмов. ОбозначенияВ дальнейшем через $\mathbb N=\{1, 2, \dots\}$ мы будем обозначать множество натуральных чисел (начиная с $1$), а через $\mathbb N_0=\{0, 1, 2, \dots \}$ его объединение с $\{0\}$. Буквы $\mathbb Z$ и $\mathbb Q$ обозначают соответственно кольцо целых чисел и поле рациональных чисел. Для вещественнозначных функций $f,g\colon \mathbb N \to [0, \infty)$ мы будем использовать стандартные обозначения Бахмана–Ландау
$$
\begin{equation*}
g(x)=O(f(x)) \quad\Longleftrightarrow \quad \limsup \frac{g(x)}{f(x)} < \infty.
\end{equation*}
\notag
$$
Надеясь, что это не запутает читателя, мы используем такие же обозначения и для функций, которые определены только на коконечном подмножестве $\mathbb N$. БлагодарностиПервый автор выражает благодарность Фонду Саймонса за поддержку его визита в Международный математический центр им. Стеклова. Второй автор выражает благодарность Математическому факультету Техниона за поддержку его визитов. Первый автор также хотел бы поблагодарить М. Н. Вялого за ценные обсуждения алгоритмов рациональной арифметики и П. С. Кияшко за внимательное чтение данного текста. § 2. Считающие функции на моноидахВсюду в этом параграфе мы считаем фиксированным целое число $n \geqslant 2$. Ниже мы обсудим проблему эквивалентности для считающих функций над свободным моноидом $M_n$ с коэффициентами либо в $\mathbb Z$, либо в $\mathbb Q$ и неформальным образом опишем алгоритм ее решения. 2.1. Задание считающих функцийПусть $\mathrm A=\{\mathrm a_1, \dots, \mathrm a_n\}$ – конечное множество мощности $n \geqslant 2$, называемое алфавитом. Стандартным образом мы отождествляем элементы свободного моноида $M_n$ с конечными словами над $\mathrm A$ (включая пустое слово $\varepsilon$), а для данного слова $w \in M_n$ обозначаем через $|w|$ длину слова слова $w$, т.е. количество букв в $w$. Мы также фиксируем группу коэффициентов $\mathfrak N \in \{\mathbb Z, \mathbb Q\}$. Для двух слов $v=s_1\dots s_l$ и $w=r_1 \dots r_m$ над алфавитом $\mathrm A$ с $m \geqslant l \geqslant 0$ обозначим через $\rho_v(w)$ число (возможно, перекрывающихся) вхождений $v$ в $w$, т.е.
$$
\begin{equation*}
\rho_v(w)=\bigl|\bigl\{j \in \{1, \dots, m-l+1\} \mid s_i=r_{j+i} \text{ для всех }i \in \{1, \dots, k\}\bigr\}\bigr|.
\end{equation*}
\notag
$$
Если $m<l$, по определению полагаем $\rho_v(w):=0$. Подобная функция $\rho_v\colon M_n \to \mathbb N$ называется $v$-считающей функцией на $M_n$. По такому определению получаем, что $\rho_\varepsilon(w)=|w|$. Под считающей функцией с коэффициентами в $\mathfrak N$ понимается функция вида
$$
\begin{equation*}
f=\sum_{i=1}^N x_i \rho_{w_i}\colon M_n \to \mathfrak N,
\end{equation*}
\notag
$$
где $N \in \mathbb N_0$, $w_1, \dots, w_n \in M_n$ – слова, а $x_1, \dots, x_N \in \mathfrak N$ – коэффициенты. Мы говорим, что две считающие функции $f_1$ и $f_2$ эквивалентны, обозначая это как $f_1 \sim f_2$, если выполнено условие, что В этом параграфе мы будем использовать два разных способа задания считающих функций над $M_n$ с коэффициентами в $\mathfrak N$, а именно словарно-числовые списки и взвешенные деревья. Хотя взвешенные деревья оказываются довольно полезны для визуализации, мы в основном будем описывать наши алгоритмы в терминах словарно-числовых списков, поскольку они тесно связаны со структурами данных, используемыми в реализациях наших алгоритмов.2.1.1. Словарно-числовые спискиБудем называть словарно-числовым списком односторонний список вида $L=((w_1, x_1), \dots, (w_N, x_N))$, где $N \in \mathbb N_0$, а $w_j \in M_n$ и $x_j \in \mathfrak N$ для всех $j \in \{1, \dots, N\}$. Нами также будет использоваться термин с.-ч. список, являющийся сокращением словарно-числового списка. Ассоциированной считающей функцией мы называем функцию Таким образом, каждый с.-ч. список задает считающую функцию, и по определению каждая считающая функция кодируется с помощью с.-ч. списка. Однако такой список не является единственным, так как, например, некоторые слова в списке могут повторяться.2.1.2. Взвешенные деревьяСледуя работе [9], мы визуализируем каждый словарно-числовой список в виде конечного взвешенного дерева следующим способом: обозначим через $T_n$ правое дерево Кэли моноида $M_n$ относительно свободного множества порождающих $\mathrm A$. Таким образом, по определению множество вершин $T_n$ задается равенством $V(T_n)=M_n$, а две вершины $x$ и $y$ соединены ребром тогда и только тогда, когда существует $i \in \{1, \dots, n\}$ такое, что $x= y\mathrm a_i$ или $y=x\mathrm a_i$. Мы рассматриваем $T_n$ как корневое дерево, корнем которого является пустое слово $\varepsilon$. Для заданного с.-ч. списка $L=((w_1, x_1), \dots, (w_N, x_N))$ обозначим через $T_L$ поддерево $T_n$, заданное выпуклой оболочкой множества вершин
$$
\begin{equation*}
V(T_L):=\{w \in M_n \mid \exists\, j \in \{1, \dots, N\}\colon w=w_j \} \cup \{\varepsilon\}.
\end{equation*}
\notag
$$
Тогда весовой функцией называется $\alpha_L\colon V(T_L) \to \mathfrak N$, определенная как Например, взвешенное дерево $(T_L, \alpha_L)$, соответствующее списку
$$
\begin{equation*}
L=\bigl((\varepsilon, -1), (\mathrm a_2, 6), (\mathrm a_3, -1), (\mathrm a_1^2, 4), (\mathrm {a}_1 \mathrm a_2, 4), (\mathrm a_1 \mathrm a_3, 4), (\mathrm a_3 \mathrm a_1, 1), (\mathrm a_3\mathrm a_2, 1), (\mathrm a_3^2, 1)\bigr),
\end{equation*}
\notag
$$
изображается рис. 1. Одному и тому же дереву могут соответствовать разные словарно-числовые списки, но все эти списки также соответствуют одной и той же считающей функции, поскольку В дальнейшем мы будем в основном работать со словарно-числовыми списками, а не со взвешенными деревьями, однако иногда мы будем использовать взвешенные деревья для визуализации некоторых наших алгоритмов.2.2. Проблема эквивалентности2.2.1. Эквивалентные считающие функции и словарно-числовые спискиНапомним, что считающие функции $f_1$ и $f_2$ называются эквивалентными (обозначается $f_1 \sim f_2$), если $f_1-f_2$ – ограниченная функция. Для каждого $w \in M_n$ имеются очевидные эквивалентности (см. [9])
$$
\begin{equation}
\rho_w \sim \sum_{i=1}^n \rho_{\mathrm a_iw}, \qquad \rho_w \sim \sum_{i= 1}^n \rho_{w \mathrm a_i}.
\end{equation}
\tag{2.2}
$$
Мы называем два вида основных эквивалентностей в (2.2) как эквивалентность левого расширения и эквивалентность правого расширения соответственно. В [9] было установлено, что эти базовые эквивалентности охватывают пространство всех линейных соотношений между классами эквивалентности считающих функций, поскольку $w$ пробегает все элементы $M_n$, однако в таком виде этот факт нам не понадобится1. Используя соотношения левого и правого расширения, мы можем преобразовать считающие функции в эквивалентные им считающие функции. Распространим понятие эквивалентности на с.-ч. списки естественным образом. Определение 2.1. Пусть $L_1$, $L_2$ – два словарно-числовых списка. Будем говорить, что $L_1$ и $L_2$ – строго эквивалентны и обозначим как $L_1 \sim L_2$, если $f_{L_1}=f_{L_2}$; – эквивалентны и обозначим как $L_1 \sim L_2$, если $f_{L_1}-f_{L_2}$ ограничена. Мы будем использовать эти определения и для конечных взвешенных деревьев. 2.2.2. Формулировка основной проблемыОсновная алгоритмическая проблема о считающих функциях на свободных моноидах, которую мы хотим решить в этой статье, состоит в следующем. Проблема 2.2 (проблема эквивалентности). По двум поданным на вход словарно-числовым спискам $L_1$, $L_2$ проверить, выполнено ли $L_1 \sim L_2$. Заметим, что по заданным с.-ч. спискам $L_1$, $L_2$ можно легко построить с.-ч. список $L_3$ с $f_{L_3}=f_{L_1}-f_{L_2}$. Таким образом, в формулировке проблемы 2.2 мы можем предположить, что $L_2=()$ является пустым с.-ч. списком. Для решения проблемы 2.2 нам понадобится понятие минимального с.-ч. списка. Определение 2.3. Пусть $L=((w_1, x_1), \dots, (w_N, x_N))$ – словарно-числовой список, для которого $N \in \mathbb N_0$. (i) Если $N \geqslant 1$, тогда максимальная глубина $L$ равна
$$
\begin{equation*}
\operatorname{depth}(L):=\max \{|w_j| \mid j=1, \dots, N\};
\end{equation*}
\notag
$$
если $N=0$, мы будем считать, что $\operatorname{depth}(L):=-1$. Мы будем говорить, что $L$ имеет имеет постоянную глубину, если $|w_j|=\operatorname{depth}(L)$ для каждого $j=1, \dots, N$. (Согласно такому определению, пустой список имеет постоянную глубину, которая равна $-1$.) (ii) Словарно-числовой список $L$ называется минимальным, если Аналогичную терминологию мы используем и для взвешенных деревьев. Замечание 2.4. Следующий полезный факт непосредственно следует из определения: если $L$ является с.-ч. списком максимальной глубины $\ell$, а $L'$ является с.-ч. списком максимальной глубины $\ell'<\ell$, то объединенный список $L \cup L'$ является минимальным с.-ч. списком тогда и только тогда, когда минимальным является список $L$. В этом смысле минимальность с.-ч. списка зависит только от его “нижнего уровня”. Замечание 2.5. По определению всякий с.-ч. список $L$ эквивалентен некоторому минимальному с.-ч. списку $L'$, и также можно заметить, что Таким образом, для того, чтобы решить проблему 2.2, достаточно будет решить следующую проблему. Проблема 2.6 (проблема минимальности). Дан с.-ч. список $L$; нужно найти минимальный с.-ч. список $L'$, который эквивалентен $L$. Таким образом, в оставшейся части этого параграфа мы сосредоточимся на проблеме 2.6. Замечание 2.7. Мы говорим, что с.-ч. список $L=((w_1, x_1), \dots, (w_N, x_N))$ является нормализованным, если все слова $w_i$ различны, упорядочены по длине и лексикографически упорядочены внутри слов одинаковой длины, а также $x_j \neq 0$ для всех $j \in \{1, \dots, N\}$. Ясно, что каждый с.-ч. список строго эквивалентен нормализованному с.-ч. списку, поэтому проблема 2.6 в основном будет рассматриваться нами для нормализованных списков. Позже мы увидим, что для выбранной нами кодировки существует эффективный алгоритм для нормализации любого заданного с.-ч. списка. 2.3. Родственные братства и минимальностьДля обсуждения наших алгоритмов введем следующую терминологию. Напомним, что $T_n$ обозначает правое дерево Кэли моноида $M_n$ относительно порождающих $\mathrm A$; мы также отождествляем элементы из $M_n$ с вершинами из $T_n$. 2.3.1. БратстваПусть $w \in M_n=V(T_n)$. Глубина слова $w$ определяется как расстояние от него до корня. Вершины на геодезической между $w$ и корнем (включая $w$ и корень) называются предками $w$. Начиная с этого момента будем предполагать, что $w$ не является корнем. Тогда $w$ допускает единственного предка $v=\operatorname{Fa}(w)$ на расстоянии $1$, который называется его отцом. Вершины с тем же отцом, что и $w$, называются его братьями, а их совокупность братством $w$ и обозначается $\{\operatorname{Fa}(w) \ast \}$. Таким образом, каждое братство по определению содержит ровно $n$ элементов. Глубина братства определяется как глубина любого из его $n$ элементов. Мы говорим, что два элемента $u,v$ из $M_n$ родственны, и обозначаем это как $u \smile v$, если они отличаются не более чем первой буквой. В этом случае мы также говорим, что братства $\{ \operatorname{Fa}(u)\ast \}$ и $\{ \operatorname{Fa}(v)\ast \}$ родственны. Если слово $w=\mathrm a_1 \dots \mathrm a_\ell \in M_n$ имеет длину $\ell \geqslant 2$, то (возможно, пустое) подслово $\mathrm a_2 \dots \mathrm a_{\ell-1}$ называется основой $w$. Если $B$ – братство, то все элементы $B$ имеют одну и ту же основу $\operatorname{stem}(B)$, и два братства $B_1$ и $B_2$ глубины $\geqslant 2$ родственны, если и только если $\operatorname{stem}(B_1)= \operatorname{stem}(B_2)$. Для заданного $u \in M_n$ существует ровно $n$ (попарно родственных) братств $B_1, \dots, B_n$ с основой $u$, и с точностью до переупорядочения они задаются как множества $B_i=\{ \mathrm a_i\mathrm u \ast \}$. 2.3.2. Взвешенные братстваЕсли $B$ – некоторое братство, то нормализованный словарно-числовой список $\mathcal B= ((w_1, x_1), \dots, (w_m, x_m))$ называется взвешенным братством типа $B$, если все слова $w_1, \dots, w_m$ принадлежат $B$ и $m \leqslant n$. Таким образом, мы явно допускаем, что взвешенное братство может содержать менее $n$ пар и даже быть пустым; если $\mathcal B$ – непустое взвешенное братство, то его тип однозначно определяется и обозначается $\operatorname{type}(\mathcal B)$. По определению каждое взвешенное братство представляет собой список постоянной глубины. Мы говорим, что два непустых взвешенных братства $\mathcal B$ и $\mathcal B'$ родственны, если их типы родственны; также по определению мы объявляем пустое взвешенное братство родственным каждому взвешенному братству. Взвешенное братство $\mathcal B=((w_1, x_1), \dots, (w_m, x_m))$ называется постоянным, если оно либо пусто, либо если $m=n$ и ${x}_1=\dots={x}_m$; иначе, это братство называется непостоянным. Если $L=((w_1, x_1), \dots, (w_N, x_N))$ – нормализованный с.-ч. список и $w \in M_n$, то через $L_{\{w\ast\}}$ обозначим нормализованный подсписок в $L$, состоящий из всех пар $(w_j, x_j)$ из $L$ с $w_j \in \{w\ast\}$. По определению это (возможно, пустое) взвешенное братство; мы называем его взвешенным подбратством $L$ типа $\{w\ast \}$. 2.3.3. Несбалансированные словарно-числовые списки и их минимальностьОпределение 2.8. Нормализованный словарно-числовой список $L$ максимальной глубины $\ell$ называется несбалансированным, если в $L$ существуют два связанных взвешенных подбратства $\mathcal B_1$ и $\mathcal B_2$ глубины $ \ell$, где $\mathcal B_1$ непостоянное, а $\mathcal B_2$ пустое; в ином случае список называется сбалансированным. В работе [9; теорема 4.2] с использованием терминологии взвешенных деревьев был установлен следующий результат. Теорема 2.9. Если словарно-числовой список является нормализованным и несбалансированным, то он является минимальным. Отметим, что по соответствующему взвешенному дереву можно сразу увидеть, является ли данный с.-ч. список несбалансированным, взглянув только на его нижний уровень. Например, следующее взвешенное дерево (определенное над моноидом $M_3$) представляет собой несбалансированный список, поскольку непостоянное взвешенное братство с пометкой $(4,2,1)$ связано с пустым взвешенным подбратством, отцом которого является вершина с меткой $-6$ (рис. 2). 2.4. Базовые преобразованияТеперь мы определим три типа базовых преобразований, позволяющих перевести заданный (нормализованный) с.-ч. список в эквивалентный ему; первые два типа преобразований соответствуют двум типам основных эквивалентностей (2.2). 2.4.1. ПодрезкаПусть $L$ – нормализованный с.-ч. список максимальной глубины $\ell \geqslant 1$, и пусть $B=\{ w \ast \}$ для некоторого $w \in M_n$ длины $|w|=\ell-1$. Будем говорить, что подсписок $L_B$ является подрезаемым, если он непустой и постоянный. В сущности, это означает, что подсписок $L_B$ имеет вид $L_B=((w\mathrm a_1, x_1), \dots, (w\mathrm a_n, x_n))$, где $x_1= \dots=x_n=: x$. Определение 2.10. Если подсписок $L_B$ является подрезаемым, то будем говорить, что с.-ч. список $\operatorname{Pr}_{w\ast}(L)$, получаемый из $L$ удалением подсписка $L_B$, добавлением пары $(w,x)$ и нормализацией полученного списка, получен из $L$ с помощью подрезки $B$. Из эквивалентности правого расширения непосредственно следует, что подрезка преобразует $L$ в эквивалентный с.-ч. список $\operatorname{Pr}_{w\ast}(L)$. Мы говорим, что нормализованный с.-ч. список является подрезанным, если он не содержит допускающих подрезку подбратств. Поскольку подрезка строго уменьшает количество элементов в заданном с.-ч. списке, то каждый с.-ч. список может быть преобразован в эквивалентный подрезанный с.-ч. список с помощью конечного числа подрезок, что показано на следующем примере (рис. 3). В этом примере подрезанный с.-ч. список, соответствующий дереву на картинке справа, несбалансирован и, следовательно, минимален по теореме 2.9, т.е. мы достигли минимального эквивалентного с.-ч. списка, используя только подрезки. Однако в общем случае нам также потребуется применять преобразования, связанные с эквивалентностями левого расширения. 2.4.2. ПереносРассмотрим случай, когда $L$ является подрезанным нормализованным сбалансированным с.-ч. списком максимальной глубины $\ell \geqslant 2$. Для основы $u \in M_n$ рассмотрим $n$ родственных братств $ \{\mathrm a_1 \mathrm u\ast\}, \dots, \{\mathrm a_n \mathrm u\ast\}$ глубины $\ell$. Так как $L$ имеет максимальную глубину $\ell$, существует некоторое слово $u \in M_n$ такое, что $|u|=\ell -2$ и $L_{\{\ast u \ast\}}:=L_{\{\mathrm a_1 \mathrm u\ast\}} \cup \dots \cup L_ {\{\mathrm a_n \mathrm u\ast\}}$ является непустым; мы зафиксируем такой элемент $u$. Теперь составим $(n \times n)$-матрицу $T(L, u)$ над $\mathfrak N$, для которой элемент $t_{ij}$, находящийся в позиции $(i,j)$, задается как $t_{ij}:=x_{ij}$, если существует пара вида $(\mathrm a_i\mathrm u \mathrm a_j, x_{ij})$ в $L_{ \{ \mathrm a_i \mathrm u\ast\}}$, и $t_{ij}:=0$ в противном случае. Эта матрица называется матрицей переноса для пары $(L, u)$. Отдельно отметим, что $T(L,u)$ не равно нулю из-за нашего выбора $u$. По определению имеем
$$
\begin{equation*}
\rho_{L_{\ast u \ast}}=\sum_{i=1}^n \sum_{j=1}^n t_{ij} \rho_{\mathrm a_i\mathrm u \mathrm a_j}.
\end{equation*}
\notag
$$
Если мы зафиксируем некоторое $i' \in \{1, \dots, n\}$, то мы можем использовать эквивалентность левого расширения (2.2), чтобы переписать это равенство как
$$
\begin{equation*}
\begin{aligned} \, \rho_{L_{\ast u \ast}} &= \sum_{i=1}^n \sum_{j=1}^n (t_{ij}-t_{i'j}) \rho_{\mathrm a_i\mathrm u \mathrm a_j}+\sum_{i=1}^n \sum_{j=1}^n t_{i'j} \rho_{\mathrm a_i\mathrm u \mathrm a_j} \\ &= \sum_{i\neq i'} \sum_{j=1}^n (t_{ij}-t_{i'j}) \rho_{\mathrm a_i\mathrm u \mathrm a_j}+\sum_{j=1}^n t_{i'j} \sum_{i=1}^n \rho_{\mathrm a_i\mathrm u \mathrm a_j} \\ &\sim \sum_{i\neq i'} \sum_{j=1}^n (t_{ij}-t_{i'j}) \rho_{\mathrm a_i\mathrm u \mathrm a_j}+\sum_{j=1}^n t_{i'j} \rho_{\mathrm u \mathrm a_j}. \end{aligned}
\end{equation*}
\notag
$$
Определение 2.11. Если $i'{\in}{\kern1pt}\{1,\dots, n\}$, то список $\operatorname{Tr}_{i', u}(L)$, полученный из $L$ удалением $L_{ \ast u \ast}$ и добавлением пар $(\mathrm a_i\mathrm u \mathrm a_j, t_{ij}-t_{i'j})$ для всех $i \in \{1, \dots, n\} \setminus\{i'\}$ и $j \in \{1, \dots, n\}$, а также добавлением пар $(\mathrm u \mathrm a_j, t_{i'j})$ для каждого $j \in \{1, \dots, n\}$ и нормализацией полученного списка, называется списком, полученным из $L$ с помощью переноса братства $L_{\{\mathrm a_{i'}u\ast \}}$. Из предыдущего вычисления следует, что $\operatorname{Tr}_{i', u}(L)$ эквивалентен $L$. На следующем рисунке показано влияние переноса (примененного к взвешенному братству, помеченному $(1,2,3)$) на соответствующем дереве (рис. 4). Определение 2.12. Матрица $M=(m_{ij}) \in \mathfrak N^{n \times n}$ называется суммой вектор-столбца $c=(c_1,\dots,c_n )^\top \in \mathfrak N^n$ и вектор-строки $r=(r_1,\dots,r_n)\in (\mathfrak N^{n})^*$, если $m_{ij}=c_i+r_j$ для любых $i,j\in \{ 1,2,\dots, n\}$. Для такой суммы будем использовать обозначение $M=c \boxplus r$ и сокращенный термин сумма строки и столбца. Заметим, что если матрица $M$ является суммой строки и столбца, то для любых двух ее строк, скажем, $m_i$ и $m_k$, разность $m_i-m_k$ удовлетворяет условию а значит, является постоянным вектором (т.е. вектором с одинаковыми координатами). Обратно, если $M$ – матрица со строками $m_1, \dots, m_k$ такая, что для всех $i,k \in \{1, \dots, n\}$ разность $m_i-m_k$ – постоянный вектор, все элементы которого равны константе $c_{ik}$, тогда $M$ – сумма строки и столбца, гдеПредложение 2.13. Если матрица переноса $T(L,u) \in \mathfrak N^{n \times n}$ не является суммой строки и столбца, то $L$ минимальна. Доказательство. Если $L':=\operatorname{Tr}_{i', u}(L)$, то $L'_{B_i'(u)}$ пусто. Тогда возможны два случая: если все братства $L'_{B_i(u)}$ с $i \in \{1, \dots, n\}$ постоянны, то для каждого $i \in \{ 1, \dots, n\}$ разность $t_{ij}-t_{i'j}:=c_j$ не зависит от $j$, поэтому матрица представляет собой сумму строки и столбца. Если хотя бы одно из взвешенных братств $L'_{B_i(u)}$ непостоянно (и, в частности, непусто), то $L'$ имеет глубину $\ell$ и является несбалансированным, а значит, минимальным по теореме 2.9. Поскольку списки $L$ и $L'$ эквивалентны и имеют одинаковую глубину $\ell$, мы заключаем, что список $L$ также минимален. Предложение доказано. 2.4.3. Перенос с подрезкойМы сохраняем прежние обозначения; в частности, $L$ – это подрезанный нормализованный сбалансированный с.-ч. список максимальной глубины $\ell \geqslant 2$, а слово $u \in M_n$ выбрано так, что $|u|=\ell -2$ и подбратство $L_{\{\ast u \ast\}}$ непусто. Если матрица переноса $T(L, u)$ не является суммой строки и столбца, то из предложения 2.13 мы уже знаем, что $L$ минимальна. Таким образом, мы рассматриваем случай, когда $T(L, u)$ является суммой строки и столбца и фиксируем $i' \in \{1, \dots, n\}$. Затем рассмотрим список $L':=\operatorname{Tr}_{i', u}(L)$, полученный из $L$ переносом взвешенного братства $L_{ \{\mathrm a_{i' } \mathrm u\ast\}}$. Поскольку матрица $T(L, u)$ является суммой строки и столбца, все взвешенные подбратства $L'_{ \{\mathrm a_{i'} \mathrm u\ast\} }$ для $i \in \{1, \dots, n\} \setminus\{i'\}$ постоянны (согласно доказательству предложения 2.13), поэтому мы можем подрезать их и получить новый эквивалентный список, который мы обозначаем через $\operatorname{TrP}_{i', u}(L)$ (что означает совмещение “переноса и подрезки”). Наша следующая цель – найти явную формулу для коэффициентов списка $\operatorname{TrP}_{i', u}(L)$. По условию матрица $T(L, u)$ может быть записана как сумма строки и столбца в виде $T(L, u)=c \boxplus r$, и мы хотим явно вычислить такое разложение. Для этого будет удобно зафиксировать некоторый индекс $j' \in \{1, \dots, n\}$; тогда, поскольку $T(L, u)$ является суммой строки и столбца, мы имеем
$$
\begin{equation}
{t}_{ij}-{t}_{i'j}={t}_{ij'}-{t}_{i'j'} \quad \text{для всех }\ i,j \in \{1, \dots, n\}.
\end{equation}
\tag{2.3}
$$
По данным $i,j \in \{1, \dots, n\}$ определим тогда откуда получаем, что
$$
\begin{equation*}
T(L, u)=(y_1, \dots, y_n)^\top \boxplus (z_1,\dots, z_n).
\end{equation*}
\notag
$$
Таким образом, мы нашли искомое разложение $T(L, u)$. Обратим внимание, что по условию (2.3) число $y_i$ не зависит от выбора $j'$ . Затем мы получаем
$$
\begin{equation*}
\begin{aligned} \, \rho_{L_{\ast u \ast}} &= \sum_{i=1}^n \sum_{j=1}^n t_{ij} \rho_{\mathrm a_i \mathrm u \mathrm a_j} = \sum_{i=1}^n \sum_{j=1}^n (t_{ij}-t_{i'j}) \rho_{\mathrm a_{i} \mathrm u \mathrm a_j}+ \sum_{i=1}^n \sum_{j=1}^n t_{i'j} \rho_{\mathrm a_{i} \mathrm u \mathrm a_j} \\ &= \sum_{i=1}^n (t_{ij'}-t_{i'j'}) \sum_{j=0}^n \rho_{\mathrm a_{i} \mathrm u \mathrm a_j}+\sum_{j=1}^n t_{i'j} \sum_{i=0}^n \rho_{\mathrm a_{i} \mathrm u \mathrm a_j} \sim \sum_{i=1}^n y_i \rho_{\mathrm a_i \mathrm u}+\sum_{j=1}^n z_j \rho_{\mathrm u \mathrm a_j}, \end{aligned}
\end{equation*}
\notag
$$
и можно проверить, что такое переписывание в точности соответствует применению переноса с последующей подрезкой полученных постоянных братств. Отсюда вытекает Предложение 2.14. Словарно-числовой список $\operatorname{TrP}_{i', u}(L)$ получается из словарно-числового списка $L$ удалением подсписка $L_{\{\ast u \ast\}}$, добавлением элементов $(\mathrm a_i \mathrm u, y_i)$ и $(\mathrm u \mathrm a_j, z_j)$ для $i,j \in \{1, \dots, n\}$ и последующей нормализацией получившегося списка. 2.4.4. Случай максимальной глубины $\leqslant 1$С помощью приведенных выше преобразований мы можем свести любой заданный с.-ч. список к минимальному с.-ч. списку или нормализованному с.-ч. списку максимальной глубины $\leqslant 1$. Таким образом, с этого момента будем считать, что $L$ – нормализованный с.-ч. список максимальной глубины $\leqslant 1$; теперь мы собираемся построить минимальный список $L'$, эквивалентный $L$. Если список $L$ пуст, то список $L':=L$ минимален по определению. Теперь предположим, что $L$ имеет глубину $0$; мы утверждаем, что тогда $L':=L$ также минимален. В самом деле, поскольку $L$ считается нормализованным, мы имеем $\rho_L=x\rho_\varepsilon$ для некоторого $x \neq 0$. Поскольку $\rho_\varepsilon(w)=|w|$ для всех $w \in M_n$, функция $\rho_L$ неограничена и, следовательно, не эквивалентна тождественной функции $0$, а значит, список $L$ не эквивалентен пустому списку, являющемуся единственным списком глубины меньше $0$. Наконец, рассмотрим случай, когда $L$ имеет максимальную глубину $1$; тогда
$$
\begin{equation}
\rho_L=x \rho_{\varepsilon}+\sum_{i=1}^n x_i \rho_{\mathrm a_i}.
\end{equation}
\tag{2.5}
$$
Если список $L$ подрезаемый (т.е. $x_1=\dots=x_n$), то применение подрезки к единственному братству глубины $1$ и нормализация дает либо пустой список $L'$ (который является минимальным по определению), либо список $L'$ максимальной глубины $1$, который, как видно выше, является минимальным. Мы утверждаем, что, с другой стороны, если нормализованный с.-ч. список $L$ максимальной глубины $1$ не является подрезаемым, то он уже минимален. В противном случае для $\rho_L$, как в (2.5), функция $\sum_{i=1}^n x_i \rho_{\mathrm a_i}$ будет эквивалентна $y\rho_{\varepsilon }$ для некоторого коэффициента $y$, а значит, функция $\sum_{i=1}^{n} (x_i-y) \rho_{a_i}$ будет ограниченной. Поскольку хотя бы один из коэффициентов $x_i-y$ отличен от нуля, это невозможно, в чем можно убедиться, вычисляя значения этой функции на словах вида $a_j^N$ при больших $N$. 2.5. Неформальное описание алгоритмаПредположим теперь, что у нас есть с.-ч. список $L$. Тогда, чтобы найти минимальный с.-ч. список в классе эквивалентности $L$, мы можем действовать следующим образом. – Нормализуем с.-ч. список $L$ и подрежем все постоянные братства на нижнем уровне, чтобы получить подрезанный с.-ч. список $L'$. Если $L'$ несбалансированный (или пустой), то мы нашли нужный минимальный с.-ч. список. – Предположим теперь, что список $L'$ сбалансирован и имеет максимальную глубину $\ell \geqslant 2$. Тогда мы можем найти некоторое слово $u \in M_n$ с $|u|=\ell -2$ такое, что $L'_{\{\ast u \ast\}}$ не пуст. Если матрица переноса $T(L', u)$ не является суммой строки и столбца, то $L'$ минимален, и мы закончили. В противном случае мы можем применить перенос и подрезку. Повторяем это до тех пор, пока возможно; если получающийся список $L'$ не станет минимальным, то в итоге получим список $L''$ меньшей глубины. – Теперь мы можем повторять предыдущий шаг, пока не получим либо минимальный список $L'''$, эквивалентный $L$, либо список $L'''$ глубины $\leqslant 1$. В последнем случае мы можем найти эквивалентный минимальный список, как было описано в п. 2.4.4. Замечание 2.15. К сожалению, описанный выше алгоритм при наивной реализации будет эффективен не во всех случаях. Вообще говоря, есть две проблемы, которых мы хотим избежать при применении переноса и подрезки. Мы не хотим создавать слишком много новых элементов в нашем списке и в то же самое время не хотим переносить братства с большими коэффициентами. Можно легко избежать одной из двух проблем (переносом братства с минимальным количеством ненулевых элементов и, соответственно, переносом братства с “наименьшими” коэффициентами), но, вообще говоря, не двух сразу. Чтобы оптимизировать время выполнения нашего алгоритма, мы будет применять смешанную стратегию. (1) Если с.-ч. список $L_{\{\ast u \ast\}}$ содержит не слишком много элементов (по сравнению с максимально возможным числом $n^2$ элементов), то мы будем переносить одно из взвешенных братств $L_{\{\mathrm a_iu\ast\}}$, а именно то, которое содержит наименьшее количество элементов. (Эту ситуацию будем в дальнейшем называть разреженным случаем.) (2) Если с.-ч. список $L_{\{\ast u \ast\}}$ содержит много записей, то мы переносим одно из братств $L_{\{\mathrm a_i u\ast\}}$, коэффициенты которого минимальны. (Эта ситуация будет называться неразреженным случаем.) Используя эту стратегию, мы сможем гарантировать, что наш алгоритм работает эффективно во всех случаях. § 3. Формальная постановка проблемыТеперь мы приступим к формализации алгоритмов, описанных в предыдущем параграфе. Напомним, что в качестве вычислительной модели нами будет использоваться модель многоленточной машины Тьюринга (см. [12; п. 8.4.1]). Подчеркнем тот факт, что наши алгоритмы предназначены для работы с коэффициентами, которые могут быть большими, поэтому мы не предполагаем, что арифметические операции с ними выполняются за постоянное время. 3.1. Кодирование коэффициентовДля формального описания алгоритма требуется обсудить формат хранения данных внутри многоленточной машины Тьюринга. В частности, нужно указать кодировку для коэффициентов. Следующий результат установлен в § 6. При этом функция $T$ может быть выбрана как $T(N):=N \log N$ или любая другая функция, удовлетворяющая условиям соглашения 6.3. Теорема 3.1. Для $\mathfrak N \in \{\mathbb Z, \mathbb Q\}$ существуют алфавиты $\Sigma_{\mathfrak N}$, кодирующие подмножества $ \operatorname{Num}_{\mathfrak N} \subset \Sigma^*$ и сюръективные кодирующие отображения а также отображения арифметических операций $\oplus, \ominus\colon \operatorname{Num}_{\mathfrak N} \times \operatorname{Num}_{\mathfrak N} \to \operatorname{Num}_{\mathfrak N}$ и отображение размера $\|\cdot\|\colon \operatorname{Num}_{\mathfrak N} \to \mathbb N_0$ со следующими свойствами. (i) $\langle \mathrm x_1 \oplus \mathrm x_2 \rangle=\langle \mathrm x_1 \rangle+ \langle \mathrm x_2 \rangle$ и $\langle \mathrm x_1 \ominus \mathrm x_2 \rangle= \langle \mathrm x_1 \rangle-\langle \mathrm x_2 \rangle$. (ii) Если $|\mathrm x|$ обозначает длину $\mathrm x \in \operatorname{Num}_{\mathfrak N}$ как слова в алфавите $\Sigma_{\mathfrak N}$, тогда длина слова и его размер связаны неравенством $|x| \leqslant \|x\| \leqslant 2 |x|$. (iii) Слова $\mathrm x_1 \oplus \mathrm x_2$ и $\mathrm x_1 \ominus \mathrm x_2$ имеют размер не более $\max\{\|\mathrm x_1\|,\|\mathrm x_2\|\}$, и они могут быть вычислены за время $O(\max\{\|\mathrm x_1\|,\|\mathrm x_2\|\}+1)$, если $\mathfrak N=\mathbb Z$; эти слова имеют размер не более $\| x_1 \|+\| x_2 \|$ и могут быть вычислены за время $O(T(\|\mathrm x_1\|+\|\mathrm x_2\|))$, если $\mathfrak N=\mathbb Q$. (iv) По данным $\mathrm x_1, \mathrm x_2 \in \operatorname{Num}_{\mathfrak N}$ истинность равенства $\langle\mathrm x_1 \rangle=\langle \mathrm x_2 \rangle$ может быть проверена за время $O(\max\{\|\mathrm x_1\|, \|\mathrm x_1\|\})$ для случая $\mathfrak N=\mathbb Z$ и за время $O(T(\|\mathrm x_1\|+\|\mathrm x_2\|))$ для случая $\mathfrak N=\mathbb Q$. Для того чтобы получить оценки в теореме 3.1 в случае $\mathfrak N=\mathbb Q$, нам пришлось выбрать кодировку, которая не является инъективной (а именно, кодировку возможно сократимыми смешанными дробями). Нам неизвестно, можно ли получить аналогичные оценки с помощью инъективного кодирования. Учитывая $\mathrm x_1, \mathrm x_2 \in \operatorname{Num}_{\mathfrak N}$, мы будем писать $\mathrm x_1 \equiv \mathrm x_2$ при условии $\langle \mathrm {x}_1 \rangle= \langle \mathrm x_2 \rangle$. С этого момента мы предполагаем, что наши коэффициенты и их арифметические операции между ними закодированы, как указано в формулировке теоремы 3.1. Для данного $x \in \operatorname{Num}_{\mathfrak N}$ мы называем $\|x\|$ размером $x$, поскольку он пропорционален объему памяти, необходимому для хранения $\mathrm x$. 3.2. Кодирование считающих функцийС этого момента фиксируем целое число $n \geqslant 2$. Мы хотим закодировать считающие функции над свободным моноидом $M_n$ с коэффициентами либо в $\mathbb Z$, либо в $\mathbb Q$. В нашем неформальном обсуждении в § 2 мы описали считающие функции с помощью словарно-числовых списков, т.е. списков вида $L=((w_1, x_1), \dots, (w_N, x_N))$, где $w_1, \dots, w_N$ – элементы $M_n$, а $x_1, \dots, x_N$ – элементы группы коэффициентов $\mathfrak N \in \{\mathbb Z, \mathbb Q\}$. В нашем формальном обсуждении мы будем использовать стандартную структуру данных, а именно двусвязный список (см. [4; п. 10.2]), хранение которого в многоленточной модели может быть осуществлено в виде длинного слова, написанного на отдельной ленте. Мы будем считать, что элементы списка $(w_i,x_i)$ разделены запятыми, но, конечно, еще будет нужно указать кодировку элементов $M_n$ и $\mathfrak N$ соответственно. Читатель сможет проследить, что в большинстве алгоритмов мы имеем дело не более чем с $n+1$ списками, и это число может служить оценкой количества необходимых лент. 3.2.1. Словарно-числовые парыДля кодирования элементов $M_n$ выберем множество $\mathrm A:=\{\mathrm a_1, \dots, \mathrm a_n\}$ мощности $n$ и идентифицируем $M_n$ с множеством $\mathrm A^*$ слов над $\mathrm A$. Это дает кодировку $M_n$ над алфавитом $\mathrm A$, и для $w \in M_n$ мы обозначаем через $|w|$ размер слова $w$ относительно алфавита $\mathrm {A}$ и назовем его размером $w$. На самом деле объем памяти, необходимый для кодирования $w$, пропорционален каноническому двоичному размеру $b(w)=\log_2(n) |w|$. Однако нас в первую очередь будет интересовать случай, когда ранг $n$ нашего моноида мал по сравнению с размером списка и/или размером коэффициентов, поэтому мы будем везде рассматривать $n$ как константу и, таким образом, считать, что размер $|w|$ пропорционален объему памяти, используемой $w$. Для коэффициентов мы используем кодировку $\operatorname{Num}_{\mathfrak N} \to \mathfrak N$, обсуждавшуюся в предыдущем пункте, и рассматриваемую более подробно в § 6. Учитывая, что $\mathrm x \in \operatorname{Num}_{\mathfrak N}$, мы используем другой размер $\|\mathrm x\|$, определенный в § 6, в качестве меры памяти, необходимой для хранения числа $\mathrm x$. Словарно-числовой парой (или просто парой) будем всюду далее называть пару вида $(w, \mathrm x) \in \mathrm A^* \times \operatorname{Num}_{\mathfrak N}$. Здесь первая компонента $w$ интерпретируется как элемент моноида $M_n \cong \mathrm A^*$, а вторая компонента $\mathrm x$ кодирует коэффициент $x=\langle \mathrm x \rangle$. Для данной пары $(w, \mathrm x)$ мы обозначаем ее полный размер через Ввиду обсуждения выше, данная величина пропорциональна объему памяти, необходимому для хранения такой пары.3.2.2. Кодовые спискиКонечный список $\mathcal L=((w_1, \mathrm x_1), \dots, (w_N, \mathrm x_N))$, состоящий из пар слов, называется кодовым списком, а словарно-числовой список
$$
\begin{equation*}
\langle \mathcal L \rangle:=((w_1, \langle \mathrm x_1\rangle), \dots, (w_N, \langle \mathrm x_N\rangle))
\end{equation*}
\notag
$$
называется его интерпретацией. Отметим, что поскольку наше кодирование коэффициентов не является инъективным, разные кодовые списки могут иметь одну и ту же интерпретацию. Будем говорить, что кодовые списки являются нормализованными, минимальными, подрезанными, эквивалентными и т.д., если их интерпретации обладают соответствующим свойством. Для данного кодового списка $\mathcal L= ((w_1, \mathrm x_1), \dots, (w_N, \mathrm x_N))$ мы положим
$$
\begin{equation*}
|\mathcal L|:=\sum_{i=1}^N |w_i|, \qquad \|\mathcal L\|:= \sum_{i=1}^N \|\mathrm x_i\|, \qquad |\mathcal L|_{\mathrm{tot}}:=|\mathcal L|+\|\mathcal L\|
\end{equation*}
\notag
$$
и будем называть эти величины словарным размером, числовым размером и общим размером списка $\mathcal L$ соответственно. С точностью до мультипликативной константы (зависящей от $n$) общий размер $\mathcal L$ – это объем памяти, используемый для хранения такого списка в нашей кодировке. Для данного кодового списка $\mathcal L$ его ассоциированную считающую функцию определим как $\rho_{\mathcal L}:=\rho_{\langle \mathcal L\rangle}$. Например, для $\mathfrak N=\mathbb Z$ кодовый список $\mathcal L:=((\mathrm a_1,+11), (\mathrm a_2\mathrm a_1, -100), (\mathrm a_2,-101))$ представляет считающую функцию $3\rho_{a_1}-4\rho_{a_2 a_1}-5\rho_{a_2}$. Наш выбор двусвязного списка как базовой структуры данных (в отличие от структуры наподобие взвешенного дерева) обусловлен тем фактом, что мы не хотим использовать излишнюю память для большого числа нулевых коэффициентов. Эффективность нашего выбора структуры данных будет также подтверждена в ходе анализа главного алгоритма настоящей работы. 3.3. Формулировка основного результатаОпределив кодовый список кодировкой считающей функции, мы можем теперь сформулировать основные результаты настоящей статьи, по крайней мере, для случая моноидов. Теорема 3.2. Для любого $n\geqslant 2$ существует алгоритм FindMinimalList, который по данному на вход кодовому списку $\mathcal L$ над $M_n$ дает на выход минимальный кодовый список $\mathcal M$, эквивалентный $\mathcal L$. Более того, если $n \geqslant 3$ этот алгоритм может быть реализован таким способом, что его временная сложность является следующей: (a) если $\mathfrak N=\mathbb Z$, тогда список $\mathcal M$ строится по списку $\mathcal L$ за линейное время, т.е. за время $O(|\mathcal L|)$; (b) если $\mathfrak N=\mathbb Q$, тогда список $\mathcal M$ строится по списку $\mathcal L$ за время $O(T(|\mathcal L|))$, где $T(N):=N \log N$. Ввиду замечания 2.5 мы получаем следующее непосредственное следствие. Следствие 3.3. Для любого $n \geqslant 2$ и для $\mathfrak N \in \{\mathbb Z, \mathbb Q\}$ существуют алгоритмы, определяющие, являются ли две считающие функции над моноидом $M_n$ с коэффициентами в $\mathfrak N$ (заданные в виде двух кодовых списков) эквивалентными. Кроме того, для $n \geqslant 3$ эти алгоритмы могут быть реализованы таким образом, что соответствующие им временные сложности будут такими, как описано в п. (a), (b) теоремы 3.2. Причиной появления нелинейной функции $T$ в теореме 3.2, (b) (и, соответственно, в следствии 3.3) является нелинейная сложность арифметических операций над $\mathbb Q$, а именно то, что наиболее известная на данный момент реализация сложения в $\mathbb Q$ имеет временную сложность $T(n)$. Если была бы известна более эффективная процедура сложения рациональных чисел, то указанную оценку сложности можно было бы улучшить; для более подробного обсуждения см. § 6. Хотя алгоритм работает для всех $n \geqslant 2$, наш метод оценки времени выполнения требует более строгого условия $n \geqslant 3$. Это условие используется в лемме 4.8 только один раз, чтобы показать, что в главном шаге алгоритма размеры рассматриваемых коэффициентов уменьшаются как минимум в $d_n$ раз, где $d_n>1$ при $n \geqslant 3$, что оказывается критически важным для оценки времени работы алгоритма. 3.4. Реализация базовых преобразованийТри главных процедуры из неформального описания алгоритма, указанные в п. 2.5, – это подрезка, вычисление матрицы переноса и преобразование “перенос с подрезкой”. Теперь мы приступим к описанию того, как эти процедуры могут быть реализованы посредством работы с кодовыми списками. Работая с кодовыми списками, мы будем использовать ту же терминологию, что и для словарно-числовых списков. В частности, для нормализованного с.-ч. списка $\mathcal L=((w_1, \mathrm x_1), \dots, (w_N, \mathrm x_N))$ и слова $w \in M_n$ мы определим взвешенное подбратство $L$ типа $\{ w\ast \}$ как нормализованный кодовый список $\mathcal L_{\{w\ast\}}$, состоящий из всех пар $(w_j, \mathrm x_j)$, где $w_j \in \{w\ast\}$. Аналогичным образом, если дано слово $u \in M_n$, то мы будем обозначать через $\mathcal L_{\{\ast u \ast\}}$ нормализованный кодовый список, получающийся объединением кодовых списков $\mathcal L_{\{\mathrm a_1 \mathrm u\ast\}}$, …, $\mathcal L_{\{\mathrm a_n \mathrm u\ast\}}$. 3.4.1. ПодрезкаПусть $\mathcal L$ – нормализованный кодовый список с интерпретацией $L=\langle \mathcal L \rangle$ максимальной глубины $\ell \geqslant 1$. Если слово $w \in M_n$ имеет длину $\ell -1$ и подбратство $L_{\{w\ast\}}$ и является подрезаемым, мы хотели бы найти кодовый список, который представляет $\operatorname{Pr}_{w\ast}(L)$. Для этого удалим подсписок $\mathcal L_{\{w\ast\}}$ из $\mathcal L$ и добавим пару вида $(w,\mathrm x)$ с кодом коэффициента $\mathrm x\equiv \mathrm x_1 \equiv \dots \equiv \mathrm x_n$. Обратим внимание, что при выполнении такого отображения подрезки на $\mathcal L$ у нас есть свобода выбора кода коэффициента $\mathrm x$. Мы всегда можем выбрать $\mathrm x:=\mathrm x_1$, но для получения эффективного алгоритма лучше выбрать в качестве $\mathrm x$ один из тех кодов $\mathrm x_j$, который имеет наименьший размер $\|\mathrm x_j\|$. 3.4.2. Вычисление матрицы переносаПусть $\mathcal L$ – нормализованный кодовый список с интерпретацией $L=\langle \mathcal L \rangle$ максимальной глубины $\ell$, а $u \in M_n$, где $|u|=\ell-2$. Нас будет интересовать вычисление матрицы переноса $T:=T(L, u)=(t_{ij})$. Мы говорим, что состоящая из слов матрица $\mathrm T=(\mathrm t_{ij}) \in \operatorname{Num}_{\mathfrak N}^{n \times n}$ представляет $T$, если $t_{ij}=\langle \mathrm t_{ij} \rangle$. В этом случае мы также называем $\mathrm T$ кодовой матрицей переноса и пишем $\mathrm T(\mathcal L, u)$ вместо $\mathrm T$. Чтобы вычислить такую матрицу переноса, мы сначала вычисляем $\mathcal L_{\{\ast u \ast\}}$. Затем мы читаем слова в этом списке, и всякий раз, когда мы находим слово, начинающееся с $\mathrm a_i$ и заканчивающееся на $\mathrm a_j$, мы считываем соответствующий коэффициент $\mathrm x_{ij}$ и полагаем $\mathrm t_{ij}:=\mathrm x_{ij}$. Все остальные элементы матрицы $\mathrm T$ устанавливаются равными $\varepsilon$. Мы увидим, что это можно сделать за линейное время от общего размера списка $\mathcal L_{\{\ast u \ast\}}$. 3.4.3. Перенос с подрезкойПусть $\mathcal L$ – нормализованный кодовый список с интерпретацией $L=\langle \mathcal L \rangle$ максимальной глубины $\ell \geqslant 2$. Предположим, что существует слово $u\in M_n$, где $|u|=\ell-2$, такое, что матрица переноса $T(L, u)$ представляет собой сумму столбца и строки. Тогда наша цель состоит в том, чтобы найти кодовый список $\mathcal L'$, который представляет с.-ч. список $\operatorname{TrP}_{i', u}(L)$ для некоторого $i' \in \{1, \dots, n\}$. Для этого сначала формируем кодовую матрицу переноса $\mathrm T(\mathcal L, u)=(\mathrm t_{ij})$. Затем для каждого $i \in \{1, \dots, n\}$ мы выбираем $\mathrm y_i \in \operatorname{Num}_{\mathfrak N}$ таким образом, что $\mathrm y_i \equiv \mathrm {t}_{ij}\ominus \mathrm t_{i'j}$ для некоторого $j \in \{1, \dots, n\}$. Затем для каждого $j \in \{1, \dots, n\}$ мы выбираем элементы $\mathrm z_j \in \operatorname{Num}_{\mathfrak N}$ такие, что $\mathrm z_j \equiv t_{i'j}$. Один из возможных вариантов выбора такой: $\mathrm z_j:=\mathrm t_{i'j}$ и $\mathrm y_{i}:=\mathrm t_{ij'}\ominus \mathrm t_{i'j'}$ для некоторого фиксированного $j' \in \{1, \dots, n\}$, однако, вообще говоря, этот выбор может оказаться неэффективным. В любом случае, мы можем модифицировать $\mathcal L$, удалив $\mathcal L_{\{\ast u \ast\}}$ и добавив элементы $(\mathrm a_i \mathrm u, \ \mathrm y_i)$ и $(\mathrm u \mathrm a_j, \mathrm z_j)$ для $i,j \in \{1, \dots, n\}$ (опуская при этом пары, коэффициенты которых равны $0$). По предложению 2.14 результирующий список будет представлять $\operatorname{TrP}_{i', u}(L)$. § 4. Описание алгоритма для случая моноидаТеперь мы формализуем алгоритм, описанный в п. 2.5. Затем будет проанализирована его сложность и установлена теорема 3.2. Наш алгоритм будет работать с кодовыми списками словарно-числовых пар. Для краткости мы будем называть словарно-числовую пару просто парой, а кодовый список – просто списком. Мы собираемся работать параллельно со случаями целых и рациональных коэффициентов. Положим $T(N):= N$, если выбрана группа коэффициентов $\mathfrak N=\mathbb Z$, и $T(N):=N \log N$ для группы коэффициентов $\mathfrak N=\mathbb Q$, тогда по теореме 3.1 сложение, вычитание и сравнение кодов коэффициентов $\mathrm x_1, \mathrm x_2 \in \operatorname{Num}_{\mathfrak N}$ можно выполнять за время $O(T(\|\mathrm x_1\|+\|\mathrm x_2\|))$, а сама функция $T$ удовлетворяет свойствам (T1)–(T3) соглашения 6.3. Замечание 4.1. В описании нашего основного алгоритма часто будут встречаться алгоритмы следующего вида: дан кодовый список $\mathcal L$, который разбивается на конечное число непустых подсписков $\mathcal L_1, \dots, \mathcal L_k $ с помощью некоторой процедуры, имеющей линейную временную сложность $O(|\mathcal L|_{\mathrm{tot}})$. Затем мы запускаем одну и ту же процедуру Proc для каждого из списков $\mathcal L_i$. К счастью, мы всегда будем находиться в ситуации, когда временная сложность процедуры Proc либо линейна, либо имеет вид $O(T(N))$, где $N$ – размер входных данных. В данной конкретной ситуации из леммы 6.4 будет следовать, что временная сложность всего алгоритма также имеет вид $O(|\mathcal L|_{\mathrm{tot}})$ (в линейном случае) или вид $O(T(|\mathcal L|_{\mathrm{tot}}))$ соответственно. 4.1. Нормализация списков и отсоединение братствНачнем описание нашего алгоритма с обсуждения некоторых вспомогательных процедур. Сначала рассмотрим процедуру преобразования заданного списка в нормализованный. Лемма 4.2. Существует процедура NormalizeList со свойствами: (i) входные данные NormalizeList представляют собой кодовый список $\mathcal L$, выходные данные – это нормализованный кодовый список $\mathcal N$, эквивалентный $\mathcal L$, для которого $|\mathcal N|_{\mathrm{tot}} \leqslant |\mathcal L|_{\mathrm{tot}}$; (ii) время выполнения процедуры составляет $O(T(|\mathcal L|_{\mathrm{tot}}))$. Доказательство. Напомним из [4; п. 8.3], что можно отсортировать заданный список за линейное время в предположении, что размер алфавита постоянен, используя знаменитый алгоритм сортировки RadixSort. (Совершенно ясно, что этот алгоритм может быть реализован на многоленточной машине Тьюринга с $n+1$ лентами, где $n$ – количество символов в алфавите сортируемых слов.) Для нормализации к входному списку $\mathcal L$ применяем RadixSort, используя соответствующие слова в качестве ключей сортировки. Результатом является новый список $\mathcal{L}'$, элементы которого упорядочены таким образом, что более короткие слова $w_i$ идут первыми, а при одинаковой длине слова упорядочиваются лексикографически. Очевидно, что такое переупорядочивание не меняет общего размера списка. Затем проходим по отсортированному списку $\mathcal{L'}$, и если находим несколько последовательных пар с одинаковым словом $w$ и коэффициентами $x_1, \dots, x_m$, то заменяем эти записи парой $ (w, x_1 \oplus \dots \oplus x_{m})$, если только не $x_1\oplus \dots \oplus x_m \equiv 0$, в этом случае мы их просто исключаем. Результатом является нормализованный список $\mathcal L$; время выполнения RadixSort является линейным, поэтому (ii) следует из “суммирующей” леммы 6.4, примененной к оценкам сложения и сравнения чисел из теоремы 3.1.
Неравенство $|\mathcal N|_{\mathrm{tot}}\leqslant |\mathcal L|_{\mathrm{tot}}$ следует из того, что в ходе работы алгоритма две соседние словарно-числовые пары $(w ,\mathrm x)$ и $(w,\mathrm y)$ заменяются одной парой $(w,\mathrm x \oplus \mathrm y)$, и поэтому мы имеем Лемма доказана.Одним из преимуществ нормализованных списков является то, что в них можно легко выделять подбратства. Лемма 4.3. Существует процедура DetachBrotherhood со свойствами: (i) входными данными для процедуры DetachBrotherhood является нормализованный список $\mathcal N$, а результатом является первое (в лексикографическом порядке) подбратство $\mathcal B$ из $\mathcal N$; также процедура изменяет список $\mathcal N$, удаляя из него подбратство $\mathcal B$; (ii) время выполнения процедуры составляет $O(|\mathcal B|)$. Доказательство. В начале этой процедуры нужно выделить первую пару $(\mathrm a_{i_1} \dotsb \mathrm a_{i_l}, \mathrm x)$ из $\mathcal N$ и переместить ее в отдельный список $\mathcal B$; далее нужно считать слово $w'$ из следующей пары $(w',\mathrm {x'})$ и переместить эту пару в список $\mathcal B$ в том случае, если $w'=\mathrm a_{i_1} \dots \mathrm a_{i_l-1}\mathrm a$ для некоторого $\mathrm a \in \mathrm A$. Это действие нужно повторять, пока не найдется пара, в которой слово не имеет указанную форму. Поскольку список $\mathcal N$ обрабатывается до тех пор, пока мы не обнаружим все элементы списка $\mathcal{B}$, а дополнительно будет обработано не больше чем $l+1$ буква еще одного слова, то время работы данной процедуры составляет $O(|\mathcal B|)$. 4.2. Процедура PruneListТеперь мы опишем процедуру, которая принимает нормализованный список $\mathcal N$ постоянной глубины $\ell \geqslant 1$ и удаляет из него все постоянные братства. При этом результат сохраняется в двух отдельных нормализованных списках: оставшиеся пары глубины $\ell$ будут сохранены в списке $\mathcal N'$, а вновь созданные пары глубины $\ell-1$ будут сохранены в списке $\mathcal L$. Список $\mathcal L$ будет иметь гораздо меньший размер, чем список $\mathcal N$, тогда как список $\mathcal N'$, который позже будет обрабатываться с помощью серии операций переноса и удаления, может иметь больший размер, сравнимый с размером $\mathcal N$ (и даже равный размеру $\mathcal N$, если список $\mathcal N$ являлся подрезанным с самого начала). Лемма 4.4. Существует процедура PruneList со следующими свойствами. (i) Входом является нормализованный список $\mathcal N$ постоянной глубины $\ell \geqslant 1$. (ii) Результатом является нормализованный подсписок $\mathcal N'$ списка $\mathcal N$ и еще один нормализованный список $\mathcal L$, который либо пуст, либо имеет постоянную глубину $\ell-1$. (iii) Список $\mathcal N'$ является подрезанным, а объединенный список $\mathcal N' \cup \mathcal L$ эквивалентен списку $\mathcal N$. (iv) Размер списка $\mathcal L$ удовлетворяет неравенству $|\mathcal L|_{\mathrm{tot}} \leqslant (|\mathcal N|_{\mathrm{tot}}-|\mathcal N'|_{\mathrm{tot}})/n$. (v) Время работы процедуры составляет $O(T(|\mathcal N|_{\mathrm{tot}}))$. В явном виде такая процедура может быть описана следующим образом. Вход: нормализованный список $\mathcal N$ постоянной глубины $\ell \geqslant 1$. Результат: нормализованный список $\mathcal N'$ постоянной глубины $\ell$ и нормализованный список $\mathcal L$ постоянной глубины $\ell-1$ такой, что $\mathcal N$ эквивалентен объединению $\mathcal N' \cup \mathcal L$.
Доказательство леммы 4.4. Довольно ясно, что свойства (ii) и (iii) выполняются, поскольку список $\mathcal N' \cup \mathcal L$ получается из списка $\mathcal N$ путем подрезки всех подрезаемых подбратств глубины $\ell$. (Отметим, что список $\mathcal N'$ является нормализованным как подсписок списка $\mathcal N$, а список $\mathcal L$ является нормализованным по построению.) Список $\mathcal N'$ получается из $\mathcal N$ удалением нескольких подсписков вида и каждый раз, когда мы удаляем такой подсписок, мы добавляем соответствующую пару $(w, \mathrm x_{i_0})$ к списку $\mathcal L$. Поскольку $|{w}| < |w\mathrm a_i|$ и $\|\mathrm x_{i_0}\| < \|\mathrm x_i\|$ для каждого $i \in \{1, \dots, n\}$, мы получаем $|\{(w,\mathrm x_{i_0})\}|_{\mathrm{tot}}<\frac{1}{n}|\mathcal C|_{\mathrm{tot}}$, откуда следует (iv).
Перейдем теперь к оценке времени работы данной процедуры. На отсоединение каждого братства $\mathcal B$ согласно лемме 4.3 тратится время $O(|\mathcal B|)$ . Сравнение значений $c_i$ и $c_{i-1}$ в шаге 2 занимает время $O(T(\|c_i\|+\|c_{i-1}\|))$ по теореме 3.1, и подобное сравнение проводится $n-1$ раз (для $i=2,\dots,n$). Поскольку мы считаем, что $n$ является константой, то на обработку братства $\mathcal B$ потребуется время $O(|\mathcal B|)+O(T(\|\mathcal B\|)=O(T(|\mathcal B|_{\mathrm{tot}})))$. Таким образом, из леммы 6.4 следует, что общая временная сложность ограничена сверху через $O(T(|\mathcal N|_{\mathrm{tot}}))$. 4.3. Процедура TransferAndPruneТеперь перейдем к основному шагу алгоритма, где мы хотим либо показать, что данный подрезанный с.-ч. список $L$ минимален, либо применить к нему перенос с подрезкой. Мы будем рассматривать по одному семейству родственных братств за раз, потому в качестве входных данных будет выступать один набор родственных и непостоянных взвешенных братств $(\mathcal B_1, \dots, \mathcal B_n)$. Мы можем предположить, что объединение $\mathcal B=\mathcal B_1 \cup \dots \cup \mathcal B_n$ нормализовано. Это означает, что если обозначить общую основу данных братств через ${u}$, то все элементы $\mathcal B_i$ будут иметь вид $(\mathrm a_i {u} \mathrm a_j, \mathrm x_{ij})$, где $\mathrm x_{ij} \not \equiv 0$. Вспомним, что кодовая матрица переноса $\mathrm T=\mathrm T(\mathcal B, u)$ задается как $\mathrm T=(\mathrm t_{ij})$, где $\mathrm t_{ij}:=\mathrm x_{ij}$ в случае, если $\mathcal B_i$ содержит пару со словом $\mathrm a_iu\mathrm a_j$, и $\mathrm t_{ij}:=\varepsilon$ иначе. В частности, общий размер элементов матрицы равен $\|\mathrm T\|=\|\mathcal B\|$, и мы будем называть нетривиальными такие элементы $\mathrm t_{ij}$ матрицы $\mathrm T$, для которых $\mathrm t_{ij} \neq \varepsilon$. Определение 4.5. Назовем кодовую матрицу переноса $\mathrm T$ разреженной, если либо $n \geqslant 4$ и $\mathrm T$ содержит менее $3n$ ненулевых элементов, либо $n=3$ и $\mathrm T$ содержит менее $2n$ ненулевых элементов. В этом пункте опишем и проанализируем процедуру TransferAndPrune, обладающую следующими свойствами. (i) Входом является такое семейство родственных непостоянных братств $(\mathcal B_1, \dots, \mathcal B_n)$ глубины $\ell \geqslant 2$, что объединение $\mathcal B:=\mathcal B_1 \cup \dots \cup \mathcal B_n$ нормализовано. (ii) Результатом является булева переменная minimal и список $\mathcal L$. (iii) Если minimal = true, то список $\mathcal B$ минимален (т.е. не эквивалентен ни одному списку глубины $\leqslant \ell-1$) и $\mathcal L=\mathcal B$. (iv) Если же minimal = false, то список $\mathcal L$ эквивалентен $\mathcal B$ и имеет постоянную глубину $\ell-1$. Будем конструировать $\mathcal L$ из $\mathcal B$ посредством применения переноса с подрезкой, покуда это возможно. Конкретная реализация данного преобразования будет зависеть от того, разрежена ли матрица переноса. В случае неразреженной матрицы наивная реализация переноса с подрезкой вполне подходит, однако в случае разреженной матрицы необходим более аккуратный подход, так как нужно избежать создания большого количества новых словарно-числовых пар. В явном виде эта процедура может быть описана следующим образом. Вход: семейство непостоянных взвешенных братств $(\mathcal B_1, \dots, \mathcal B_n)$ глубины $\ell \geqslant 2$ таких, что объединение $\mathcal B:=\mathcal B_1 \cup \dots \cup \mathcal B_n$ нормализовано. Результат: Булева переменная minimal и список $\mathcal L$.
Сначала покажем, что эта процедура корректна. Доказательство. Если выполнение процедуры остановится на шаге 3, тогда рассматриваемая кодовая матрица переноса не является суммой строки и столбца, и потому $\mathcal B$ минимален по предложению 2.13, и результат процедуры корректен. Теперь предположим, что матрица переноса является суммой строки и столбца; в этом случае мы должны применить перенос с подрезкой. Для этого нам нужно сначала выбрать некоторый индекс $i' \in \{1, \dots, n\}$, а затем выбрать такие $\mathrm y_i, \mathrm z_j \in \operatorname{Num}_{\mathfrak N}$, что В этом случае список $\mathcal L$ будет состоять из таких пар $(\mathrm a_i \mathrm u, \mathrm y_i)$ и $(\mathrm u \mathrm a_j, \mathrm z_j)$, для которых $\mathrm y_i \not \equiv 0 \not \equiv \mathrm z_j$. Рассмотрим два случая.
Случай 1. Если матрица $\mathrm T$ не разрежена, то на шаге 5 мы применяем перенос с $i':=i_0$. Коэффициенты в списке $\mathcal L$ будут равны $\mathrm z_j:= \mathrm t_{i_0j}$ и $y_i:= \mathrm t_{ij_0}-\mathrm t_{i_0j_0}$, где $j_0$ – индекс, выбранный на шаге 5, (b). (Причина такого выбора индекса будет объяснена в лемме 4.8.) В таком случае условие (4.1) выполняется по определению, и алгоритм корректен. Случай 2. Если же матрица $\mathrm T$ разрежена, то на шаге 6 мы применяем перенос с $i':=i_1$. Для каждого $i$ мы выбираем $\mathrm y_i:=\mathrm t_{ij_1}$, где $j_1$ – индекс, выбранный на шаге 6, (b), (i). По определению $j_1 \in Z$, потому $\mathrm t_{i_1j_1} \equiv 0$, и, следовательно $\mathrm y_i=\mathrm t_{ij_1} \equiv \mathrm t_{ij_1}-\mathrm t_{i_1j_1}$ удовлетворяет условию (4.1). Из соображений эффективности мы будем выбирать коэффициенты $\mathrm z_j$ по-разному в зависимости от того, выполняется ли условие $i_0=i_1$. Если $i_0=i_1$, то мы выбираем $\mathrm z_j:=\mathrm t_{i_1j}$, что, очевидно, корректно. Если же $i_0 \neq i_1$, то мы выбираем $\mathrm z_j:=\mathrm t_{i_0j} \ominus \mathrm t_{i_0j_0}$, где $j_0$ выбирается на шаге 6, (d), (i). Из того, что $j_0 \in Z$, следует, что $\mathrm t_{i_1j_0} \equiv 0$. С другой стороны, $\mathrm T$ – сумма строки и столбца, потому
$$
\begin{equation*}
\mathrm t_{i_1j_0}\ominus \mathrm t_{i_0j_0} \equiv \mathrm t_{i_1j}\ominus \mathrm t_{i_0j} \quad\Longleftarrow\quad \mathrm z_j=\mathrm t_{i_0j} \ominus \mathrm t_{i_0j_0} \equiv \mathrm t_{i_1j} \ominus \mathrm t_{i_1j_0} \equiv \mathrm t_{i_1j},
\end{equation*}
\notag
$$
потому (4.1) снова выполняется, и алгоритм корректен. Предложение доказано. Проанализируем временную сложность процедуры TransferAndPrune. Предложение 4.7. Время выполнения процедуры TransferAndPrune составляет $O(T(|\mathcal B|_{\mathrm{tot}}))$. Доказательство. Напомним, что в наших оценках $n$ считается константой, и потому все величины, подразумеваемые константами, могут зависеть от $n$.
Время выполнения шага 1 составляет $O(|\mathcal B|_{\mathrm{tot}})$. Основа семейства братств может быть вычислена из любой пары $(w, \mathrm x)$ за время $O(|w|) \leqslant O(|\mathcal B|_{\mathrm{tot}})$. Матрица переноса, в свою очередь, может быть вычислена за $O(|\mathcal B|_{\mathrm{tot}})$ путем сканирования всех пар и копирования нужных коэффициентов. Шаг 2 выполняется посредством последовательного суммирования размера коэффициентов из $\mathcal B_{i}$ и обновления минимума, потому на каждую строку матрицы тратится $O(\|\mathcal B_i\|)$ времени, и на всю матрицу тратится $O(\|\mathcal B\|)$ времени. (Отметим, что в этом шаге мы суммируем целые числа, даже если $\mathfrak N=\mathbb Q$.) В шаге 3 для проверки $\mathrm t_{ij} \ominus \mathrm t_{i_0 j}\equiv \mathrm t_{i{j-1}} \ominus \mathrm t_{i_0 {j-1}}$ требуется не более $O(T(\|\mathrm t_{ij}\|+\|\mathrm t_{i_0j}\|+\|\mathrm t_{i {j-1}}\|+\|\mathrm t_{i_0{j-1}}\|))$ времени по теореме 3.1. Из этого следует, что все сравнения на $i$-й итерации шага 3 занимают не более $O(T(2(\|\mathcal B_i\|+\|\mathcal B_{i_0}\|)))$ времени. Из нашего выбора $i_0$ и свойства (T3) функции $T$ (см. соглашение 6.3) следует, что $O(T(2(\|\mathcal B_i\|+\|\mathcal B_{i_0}\|)))=O(T(\|\mathcal B_i\|))$, и поэтому по лемме 6.4 шаг 3 в худшем случае занимает $O(T(|\mathcal B|_{\mathrm{tot}}))$ времени. Время работы шага 4, очевидно, равно $O(1)$. В случае неразреженной матрицы далее будет выполняться шаг 5. Здесь часть (a) занимает не более $|\mathcal B_{i_0}|_{\mathrm{tot}}$ времени, часть (b), аналогично шагу 2, занимает не более $O(\|\mathcal B\|)$, и часть (c) занимает не более $O(T(|\mathcal B|_{\mathrm{tot}}))$ времени, так как каждое вычитание $x_{i j_0}\ominus x_{i_0 j_0}$ занимает не более $O(T(\|\mathcal B_i\|+\|\mathcal B_{i_0}\|))$ времени. Следовательно, мы можем, как в шаге 3, применить лемму 6.4 для получения оценки времени обработки коэффициентов, равной $O(T(\|\mathcal B\|))$, и оценки для обработки слов, равной $O(|\mathcal B|)$, получая таким образом общую временную оценку, равную $O(T(|\mathcal B|_{\mathrm{tot}}))$. В случае разреженной матрицы, в свою очередь, будет выполняться шаг 6, временная сложность которого может быть проанализирована аналогично шагу 5. Шаг 7 же, снова, занимает $O(1)$ времени. Таким образом, каждый шаг алгоритма занимает не более $O(T(|\mathcal B|_{\mathrm{tot}}))$ времени, потому данная асимптотическая оценка также подходит для времени выполнения всей процедуры. Предложение доказано. Главное свойство процедуры TransferAndPrune заключается в том, что в случае, когда входной список не минимален, она сокращает размер входных данных с коэффициентом, меньшим $1$. Лемма 4.8. Предположим, что процедура TransferAndPrune вернула параметр minimal = false при применении ее к $(\mathcal B_1, \dots, \mathcal B_n)$. В случае $n \geqslant 3$ размер результата процедуры $\mathcal L$ и входных данных $\mathcal B:=\mathcal B_1 \cup \dots \cup \mathcal B_n$ удовлетворяют неравенству Доказательство. Поскольку $|\mathcal L|_{\mathrm{tot}}=|\mathcal L|+\|\mathcal L\|$ и $|\mathcal B|_{\mathrm{tot}}=|\mathcal B|_{\mathrm A}+\|\mathcal B\|$, достаточно будет оценить размер слов и коэффициентов по отдельности, т.е. показать, что Для этого мы воспользуемся тем фактов, что если $m_1, \dots, m_n$ – рациональные числа и $m_{i_0}$ – минимальное среди них, то Пусть $\mathrm T$ – матрица переноса, построенная в 1. Рассмотрим два случая.
Случай 1. Матрица $\mathrm T$ не разрежена. Вначале предположим, что $n \geqslant 4$. В этом случае во входном списке есть хотя бы $3n$ слов длины $\ell$, и потому $|\mathcal B| \geqslant 3n\ell$. Количество слов в выходном списке не превышает $n+(n-1)=2n-1$ (так как на шаге 5, (a) мы создаем не более $n$ слов, а на шаге 5, (c) мы создаем не более $(n-1)$ слов), длина каждого из них не превышает $\ell-1$, поэтому
$$
\begin{equation*}
|\mathcal L| \leqslant (2n-1)(\ell-1) < (2n-1)\ell \leqslant \frac{2n-1}{3n} |\mathcal B| \leqslant \frac {2}{3} |\mathcal B| \leqslant \frac {8}{9}{|\mathcal B|}.
\end{equation*}
\notag
$$
Для случая $n=3$ та же оценка аналогичным образом следует из того, что
$$
\begin{equation*}
{|\mathcal L|} \leqslant \frac{(2n-1)(\ell-1)}{2n\ell} |\mathcal B| \leqslant \frac{2n-1}{2n} |\mathcal B|=\frac{5}{6} |\mathcal B| \leqslant \frac {8}{9}{|\mathcal B|}.
\end{equation*}
\notag
$$
С другой стороны, $\|\mathcal B\|$ в точности равно общему размеру элементов $\mathrm T$, так как
$$
\begin{equation}
\|\mathcal B\|=\sum_{i=1}^n\sum_{j=1}^n \|\mathrm t_{ij}\|,
\end{equation}
\tag{4.3}
$$
в то время как в результате применения шага 5, (a) и шага 5, (c) числовой размер выходного списка становится равен
$$
\begin{equation*}
\|\mathcal L\|=\sum_{j=1}^n \|\mathrm t_{i_0j}\|+\sum_{i\neq i_0} \|\mathrm t_{ij_0}\ominus \mathrm t_{i_0j_0}\|.
\end{equation*}
\notag
$$
Благодаря нашему выбору $i_0$ на шаге 2 мы можем применить (4.2) для выведения оценки
$$
\begin{equation}
\sum_{j=1}^n \|\mathrm t_{i_0j}\| \leqslant \frac{1}{n} \sum_{i=1}^n \biggl(\sum_{j=1}^n \|\mathrm t_{ij}\|\biggr)=\frac{\|\mathcal B\|}{n}.
\end{equation}
\tag{4.4}
$$
Аналогично, благодаря нашему выбору $j_0$ на шаге 5, (b) мы можем оценить
$$
\begin{equation*}
(n-2) \|\mathrm t_{i_0j_0}\|+\sum_{i=1}^n \|\mathrm t_{ij_0}\| \leqslant \frac{1}{n} \sum_{j=1}^n \biggl((n-2) \|\mathrm t_{i_0j}\|+\sum_{i=1}^n \|\mathrm t_{ij}\| \biggr).
\end{equation*}
\notag
$$
Объединив эти две оценки, мы можем применить лемму 6.4 для получения следующей оценки:
$$
\begin{equation*}
\begin{aligned} \, \|\mathcal L\| &\leqslant \frac{\|\mathcal B\|}{n}+\sum_{i\neq i_0} (\|\mathrm t_{ij_0}\|+ \|\mathrm t_{i_0j_0}\|) =\frac{\|\mathcal B\|}{n}+(n-2) \|\mathrm t_{i_0j_0}\|+\sum_{i=1}^n\|\mathrm t_{ij_0}\| \\ &\leqslant \frac{\|\mathcal B\|}{n}+\frac{1}{n} \sum_{j=1}^n \biggl((n-2) \|\mathrm t_{i_0j}\|+\sum_{i=1}^n \|\mathrm t_{ij}\| \biggr) \\ &= \frac{\|\mathcal B\|}{n}+\frac{n-2}{n} \sum_{j=1}^n \|\mathrm t_{i_0j}\|+\frac{1}{n } \sum_{i=1}^n \sum_{j=1}^n \|\mathrm t_{ij}\| \\ &\leqslant \frac{\|\mathcal B\|}{n}+\frac{n-2}{n} \frac{\|\mathcal B\|}{n}+\frac{1}{n} \|\mathcal B\| =\frac{3n-2}{n^2} \|\mathcal B\|, \end{aligned}
\end{equation*}
\notag
$$
потому для $n \geqslant 3$ мы получаем, что
$$
\begin{equation*}
\|\mathcal L\| \leqslant \frac{7}{9} \|\mathcal B\| \leqslant \frac{8}{9} \|\mathcal B\|.
\end{equation*}
\notag
$$
Таким образом, случай 1 разобран.
Случай 2. Матрица $\mathrm T$ разрежена. Пусть $\lambda$ – минимальное количество ненулевых элементов в строке $\mathrm T$, или, иначе, размер множества $S$, построенного на шаге 6, (a). Взвешенные братства $\mathcal B_1, \dots \mathcal B_n$ не постоянны, потому $\lambda \geqslant 1$, а $\mathrm T$ разрежена, потому либо $\lambda \leqslant 2$ и $n \geqslant 4$, либо $\lambda \leqslant 1$ и $n=3$. В обоих случаях $|Z| \geqslant 2$ и $\lambda \in \{1,2\}$. Если $\lambda=1$, то $S$ состоит из одного элемента, допустим, что $S=\{j_s\}$. В этом случае определим множества
$$
\begin{equation*}
\begin{gathered} \, A:=\{i \in \{1, \dots, n\}\setminus\{ i_1 \} \mid \mathrm t_{ij_s} \equiv \mathrm t_{i_1j_s}\}, \\ A^c:=\{i \in \{1, \dots, n\}\setminus\{ i_1 \}\mid \mathrm t_{ij_s} \not \equiv \mathrm t_{i_1j_s}\}. \end{gathered}
\end{equation*}
\notag
$$
Положим $|A|:=r$, тогда $|A^c|=n-r-1$.
Для начала предположим, что $\lambda=2$. В этом случае $\mathcal B$ содержит не менее $2n$ слов, и потому $|\mathcal B| \geqslant 2\ell$. На шаге 6, (b), (ii) мы создаем не более $n-1$ слов длины $\ell-1$, а на шаге 6, (c) (или (d)) мы создаем не более $|S|=2$ слов. Следовательно, для случая $\lambda=2$ и $n \geqslant 3$ мы получаем, что
$$
\begin{equation*}
|\mathcal L| \leqslant (n+1)(\ell-1) < (n+1)\ell \leqslant \frac{n+1}{2n} |\mathcal B| \leqslant \frac{4}{6}|\mathcal B| \leqslant \frac{8}{9}|\mathcal B|.
\end{equation*}
\notag
$$
Теперь предположим, что $\lambda=1$. Матрица $\mathrm T$ является суммой строки и столбца, поэтому $i$-я строка $X$ становится постоянной после вычитания $\mathrm t_{i_1j_s}$ из $\mathrm t_{ij_s}$. Следовательно, если $i \in A$, то братство $\mathcal B_i$ содержит всего один элемент, в то время как если $i \in A^c$, то $\mathcal B_i$ содержит не менее $n-1$ элементов. Получается, что
$$
\begin{equation*}
|\mathcal B| \geqslant (1+|A|+|A^c| (n-1)) \ell \geqslant (1+r+2(n-r-1)) \ell \geqslant (2n-r-1) \ell.
\end{equation*}
\notag
$$
На шаге 6, (b), (ii) мы создаем $n-r-1$ слов, а на шаге 6, (c) (или 6, (d)) мы создаем не более одного слова, длина каждого из которых не превышает $\ell-1$, потому
$$
\begin{equation*}
|\mathcal L| \leqslant ((n-r-1)+1)(\ell-1) \leqslant (n-r) \ell \leqslant \frac{n-r}{2n-r-1} |\mathcal B|.
\end{equation*}
\notag
$$
Если $r=0$, то ${(n-r)}/{(2n-r-1)}=n/(2n-1) \leqslant 3/5$, а если $r \geqslant 1$, то $2n-r-1 \leqslant 2(n-r)$, потому ${(n-r)}/{(2n-r-1)} \leqslant 1/2$, и в этом случае также выполняется неравенство
Рассмотрим теперь числовые размеры. Во-первых, рассмотрим коэффициенты, созданные на шаге 6, (b), (ii). Для каждого индекса $i\in \{1,2,\dots,n\}\setminus \{i_1\}$ возможны два случая: либо пара вообще не создается (если $i$-я и $i_1$-я строки содержат равные вектора), либо в $i$-й строке есть хотя бы два ненулевых элемента $\mathrm t_{ij_2}$ и $\mathrm t_{ij_3}$ таких, что $\{j_2, j_3\} \subset Z$ (так как $|Z| \geqslant 2$), и наименьший по размеру из них копируется в $\mathcal N$. В любом случае суммарный размер коэффициентов, созданных на $i$-й итерации шага 6, (b), (ii), не превышает $\|\mathcal B_i\|/2$, и, следовательно, суммарный размер коэффициентов, созданных на этом шаге, не превышает $\|\mathcal B\|/2$. Теперь рассмотрим коэффициенты, созданные в частях (c) и (d) шага 6. Если $i_0 \neq i_1$, то их общий размер можно оценить следующим образом:
$$
\begin{equation*}
\begin{aligned} \, &\sum_{j \in S}\|\mathrm t_{i_0j} \ominus \mathrm t_{i_0j_0}\| \leqslant \sum_{j \in S}(\|\mathrm t_{i_0j}\|+\|\mathrm t_{i_0j_0}\|)\leqslant |S|\,\|\mathrm t_{i_0j_0}\|+\sum_{j \in S}\|\mathrm t_{i_0j}\| \\ &\qquad= |S| \min_{j \in \{1, \dots, n\}} \|\mathrm t_{i_0j}\|+\sum_{j \in S}\|\mathrm t_{i_0j}\| \leqslant \ |Z| \min_{j \in \{1, \dots, n\}} \|\mathrm t_{i_0j}\|+\sum_{j \in S}\|\mathrm t_{i_0j}\| \\ &\qquad \leqslant \sum_{j \in Z}\|\mathrm t_{i_0j}\|+\sum_{j \in S}\|\mathrm t_{i_0j}\| \leqslant \sum_{j=1}^n \|\mathrm t_{i_0j}\| \leqslant \frac{1}{n} \sum_{i=1}^n \sum_{j=1}^n \|\mathrm t_{ij}\|= \frac{1}{n} \|\mathcal B\|. \end{aligned}
\end{equation*}
\notag
$$
Во второй строке мы применили тот факт, что $|S| \leqslant 2 \leqslant |Z|$, а в третьей строке мы применили (4.2). Если $i_0=i_1$, то наш выбор $i_0$ на шаге 2 и оценка (4.4) приводят к тому, что суммарный размер коэффициентов, созданных на шаге 6, (c), ограничен сверху значением $\frac{1}{n} \|\mathcal B\|$. В любом случае, мы получаем, что для всех $n\geqslant 3$
$$
\begin{equation*}
\|\mathcal L\| \leqslant \frac{\|\mathcal B\|}{2}+\frac{\|\mathcal B\|}{n}=\frac{n+2}{2n} \|\mathcal B\| \leqslant \frac{5}{6} \|\mathcal B\| \leqslant \frac{8}{9} \|\mathcal B\|.
\end{equation*}
\notag
$$
Таким образом, случай 2 также разобран. Лемма 4.8 доказана. 4.4. Основной шаг алгоритмаВ этом пункте мы опишем процедуру MainProcessingStep и докажем лемму 4.9, которая будет использована позже при доказательстве основной теоремы 3.2. Лемма 4.9. Для любого $n\,{\geqslant}\, 2$ существует алгоритм MainProcessingStep, обладающий следующими свойствами: (i) входом является нормализованный список $\mathcal L$ постоянной глубины $\ell \geqslant 2$; (ii) результатом являются булева переменная minimal и нормализованный список $\mathcal L'$, эквивалентный $\mathcal L$; (iii) если minimal = true, то $\mathcal L'$ минимален; (iv) если minimal=false, то $\mathcal L'$ имеет постоянную глубину $\ell-1$; к тому же, если $n \geqslant 3$, то
$$
\begin{equation}
|\mathcal L'|_{\mathrm{tot}} \leqslant \frac89|\mathcal L|_{\mathrm{tot}};
\end{equation}
\tag{4.5}
$$
(v) временная сложность этого алгоритма равна $O(T(|\mathcal L|))$. В явном виде этот алгоритм может быть описан следующим образом. Вход: нормализованный список $\mathcal N$ постоянной глубины $\ell \geqslant 2$. Результат: булева переменная minimal и нормализованный список $\mathcal L$ постоянной глубины $\ell -1$.
Доказательство леммы 4.9. Процедура PruneList корректно подрезает все постоянные братства максимальной глубины в $\mathcal N$, а процедура TransferAndPrune корректно применяет перенос с подрезкой, если это возможно, и задает minimal равным true иначе, из чего можно сделать вывод о корректности процедуры MainProcessingStep.
Из леммы 4.4 следует, что шаг 2 за время $O(T(|\mathcal N|_{\mathrm{tot}}))$ превращает список $\mathcal N$ в эквивалентный список $\mathcal L \cup \mathcal N'$ такой, что
$$
\begin{equation*}
0 \leqslant |\mathcal L|_{\mathrm{tot}} \leqslant \frac{1}{n}(|\mathcal N|_{\mathrm{tot}}-|\mathcal N'|_{\mathrm{tot}}).
\end{equation*}
\notag
$$
На шаге 3 список $\mathcal N'$ делится на списки $\mathcal A_1, \mathcal A_2, \dots, \mathcal A_n$, объединение которых есть $\mathcal N'$, и на это тратится не более $O(|\mathcal N'|_{\mathrm{tot}})$ времени.
Теперь рассмотрим итерации на шаге 4. После каждой итерации длина списка $\mathcal A_1\cup \mathcal A_2\cup \dots\cup \mathcal A_n$ уменьшается на некоторое целое число $|\mathcal B|_{\mathrm{tot}}$, где $\mathcal B$ – объединение подсписков $\mathcal B_1\cup \dots \cup B_k$, созданных в части (a). Каждый такой этап занимает $O(|\mathcal B|_{\mathrm{tot}})$ времени по лемме 4.3, и при minimal = false размер выходного списка после этого этапа не превышает $\frac89 |\mathcal B|_{\mathrm{tot}}$. Воспользуемся леммой 6.4, чтобы убедиться, что временная сложность шага 4 не превышает
$$
\begin{equation*}
O(T(|\mathcal A_1 \cup \dots \cup \mathcal A_n|_{\mathrm{tot}})) \leqslant O(T(|\mathcal N'|_{\mathrm{tot}}))\leqslant O(T(|\mathcal N|_{\mathrm{tot}})).
\end{equation*}
\notag
$$
В случае, когда $n \geqslant 3$ и minimal = false после шага 4, список $\mathcal L$ оказывается расширен до списка $\mathcal L'$, общий размер которого ограничен сверху следующим значением:
$$
\begin{equation*}
|\mathcal L|_{\mathrm{tot}}+\frac{8}{9} |\mathcal N'|_{\mathrm{tot}} \leqslant \frac{1}{n} ( |\mathcal N|_{\mathrm{tot}}-|\mathcal N'|_{\mathrm{tot}} )+\frac 8 9 |\mathcal N'|_{\mathrm{tot}} \leqslant \max\biggl\{\frac 1 n, \frac 8 9\biggr\} |\mathcal N'|_{\mathrm{tot}} \leqslant \frac 8 9 |\mathcal N|_{\mathrm{tot}}.
\end{equation*}
\notag
$$
В любом случае список $\mathcal L'$, полученный путем присоединения $\mathcal A_1, \dots, \mathcal A_n$ к списку, полученному в шаге 4, всегда удовлетворяет следующему условию: $|\mathcal L'|_{\mathrm{tot}} \leqslant |\mathcal N|_{\mathrm tot}$ (даже если $n=2$ и/или minimal = true). Поэтому последний шаг также может быть выполнен за время, не превышающее $O(T(|\mathcal N|_{\mathrm{tot}}))$, и при его выполнении размер выхода не увеличивается. Получается, что в случае, когда $n=3$ и minimal = false, размер выходного списка меньше, чем размер входа, с коэффициентом $\leqslant \frac 8 9$. Лемма доказана. 4.5. Итоговый алгоритмВооружившись всеми вышеописанными процедурами, мы можем наконец описать итоговый алгоритм FindMinimalList, который, получив на вход некоторый кодовый список, находит эквивалентный ему минимальный список. Этот алгоритм будет использован для доказательства теоремы 3.2. Вход: кодовый список $\mathcal L$. Результат: нормализованный список $\mathcal M$, эквивалентный $\mathcal L$.
Доказательство теоремы 3.2. Для доказательства этой теоремы достаточно объединить результаты всех предыдущих лемм.
Во-первых, покажем, что алгоритм FindMinimalList возвращает корректный результат. Обозначим списки, созданные на шаге 4, через $\mathcal N_0, \dots, \mathcal N_d$. Тогда список $\mathcal N_d \cup \mathcal{N}_{d-1} \cup \dots \cup \mathcal N_1 \cup \mathcal N_0=\mathcal N$ эквивалентен $\mathcal L$. Теперь, при выполнении шага 6 происходит одно из двух: либо цикл не прерывается ни на одной из итераций и на выходе мы получаем набор списков $\mathcal M_d, \dots, \mathcal M_1$ (в этом случае, положим $t:=1$), либо создаются списки $\mathcal M_d, \dots, \mathcal M_t$ для некоторого $t \geqslant 2$ и цикл прерывается на следующей итерации. В обоих случаях по нисходящей индукции по $i$ можно доказать, что для любого $i \in \{d, d-1, \dots, t\}$ список $\mathcal M_i$ имеет постоянную глубину $\ell=i$ и эквивалентен объединению $\mathcal N_d \cup \dots \cup \mathcal N_i$. Действительно, для $i:=d$ этот факт очевиден, а если предположение верно для $i$ и алгоритм не остановился на следующей итерации, то из корректности MainProcessingStep следует, что $\mathcal M_{i-1}$ имеет постоянную глубину $i-1$ и удовлетворяет соотношению
$$
\begin{equation*}
\mathcal M_{i-1} \sim \mathcal N' \cup \mathcal N_{i-1} \sim \mathcal N_d \cup \dots \cup \mathcal N_i \cup \mathcal N_{i-1}.
\end{equation*}
\notag
$$
Таким образом, шаг индукции доказан.
На шаге 7 возможны два следующих случая. Случай I. Если на шаге 6 выполнение цикла было прервано после вычисления $\mathcal M_d, \dots, \mathcal M_t$ для некоторого $t \geqslant 2$, то из корректности процедуры MainProcessingStep следует, что $\mathcal M_t$ минимален и, к тому же, несбалансирован. Из этого, в свою очередь, следует, что $\mathcal M:=\mathcal M_t \cup \mathcal N_{t-1} \cup \dots \cup \mathcal N_0$ также несбалансирован, и потому минимален. Более того, из ранее описанной индукции следует, что
$$
\begin{equation*}
\mathcal M \sim \mathcal M_t \cup \mathcal N_{t-1} \cup \dots \cup \mathcal N_0 \sim \mathcal N_d \cup \dots \cup \mathcal N_{t} \cup \mathcal N_{t-1} \cup \dots \cup \mathcal N_0 \sim \mathcal L.
\end{equation*}
\notag
$$
Поэтому в этом случае $\mathcal M$ действительно минимален и эквивалентен $\mathcal L$.
Случай II. Если же все итерации цикла на шаге 6 были выполнены, то на выходе мы получаем список $\mathcal M_1$ постоянной глубины $1$, эквивалентный $\mathcal N_d \cup \dots \cup \mathcal N_1$ (это следует из вышеописанной индукции), и потому удовлетворяющий соотношению $\mathcal M_1 \cup \mathcal N_0 \sim \mathcal L$. Если список $\mathcal N'$, построенный на шаге 7, (a), не пуст, то $\mathcal M_1$ есть непостоянное братство глубины $1$. Поэтому можно, проведя рассуждение, аналогичное рассуждению из п. 2.4.4, понять, что список $\mathcal M:=\mathcal M_1\cup \mathcal N_0$ минимален, и потому минимален и эквивалентен $\mathcal L$. Если же список $\mathcal N'$ пуст, то $\mathcal M_1$ эквивалентен $\mathcal K$, и потому $\mathcal L \sim \mathcal M_1 \cup \mathcal N_0 \sim \mathcal K \cup \mathcal N_0$, т.е. $\mathcal L$ эквивалентен $\mathcal M:={}$NormalizeList$(\mathcal K \cup \mathcal N_0)$. Более того, $\mathcal M$ – нормализованный список с максимальной глубиной $\leqslant 0$, и потому минимальный. Таким образом корректность алгоритма для случая II доказана. Осталось лишь оценить временную сложность алгоритма. Будем действовать аналогично анализу из леммы 4.9. Достаточно показать, что каждый из семи шагов алгоритма выполняется за время $O(T(|\mathcal N|))_{\mathrm{tot}}$. Для шага 2 этот факт очевиден. В силу леммы 4.2 шаг 1 занимает время $O(T(|\mathcal L|_{\mathrm{tot}}))$ и на выходе дает список $\mathcal N$, удовлетворяющий $|\mathcal N|_{\mathrm{tot}}\leqslant|\mathcal L|_{\mathrm{tot}}$. Из этого ограничения следует, что шаг 3 может быть выполнен за время, равное $O(|\mathcal N|_{\mathrm{tot}})\leqslant O(|\mathcal L|_{\mathrm{tot}})$. Аналогично разложение на шаге 4 занимает не более $O(|\mathcal N|_{\mathrm{tot}})\leqslant O(|\mathcal L|_{\mathrm{tot}})$ времени, так как весь шаг выполняется за один проход по списку $\mathcal N$. Шаг 5 также имеет линейную сложность. Рассмотрим итерации цикла на шаге 6. Предположим, что в результате этих итераций будут построены списки $\mathcal M_d, \dots, \mathcal M_t$, после чего цикл прервется. Утверждается, что
$$
\begin{equation*}
|\mathcal M_{i}|_{\mathrm{tot}} \leqslant \frac89|\mathcal M_{i+1}|_{\mathrm{tot}}+|\mathcal N_i|_{\mathrm{tot}} \quad \text{для каждого }\ t \leqslant i \leqslant d-1.
\end{equation*}
\notag
$$
Действительно, если $\mathcal M_{i+1}$ пуст, то это неравенство, очевидно, выполняется, а если $\mathcal M_{i+1}$ не пуст, то оно следует из леммы 4.9, (iv). Если мы положим $\mathcal M_{d+1}$ равным пустому списку, то неравенство также будет выполняться для $i=d$, потому как $|\mathcal M_d|_{\mathrm{tot}}=|\mathcal N_d|_{\mathrm{tot}}$. Применив нисходящую индукцию по $i$, мы получаем, что
$$
\begin{equation*}
|\mathcal M_{i}|_{\mathrm{tot}} \leqslant \sum_{k=i}^d\biggl(\frac89\biggr)^{k-i}|\mathcal N_i|_{\mathrm{tot}}, \qquad i \in \{t, \dots, d\}.
\end{equation*}
\notag
$$
Просуммируем левую и правую части неравенства по $i=t, \dots, d$ и получим, что
$$
\begin{equation*}
\sum_{i=t}^{d}|\mathcal M_{i}|_{\mathrm{tot}} \leqslant \sum_{i=t}^{d}\biggl( \sum_{k=i}^d\biggl(\frac89\biggr)^{k-i}|\mathcal N_i|_{\mathrm{tot}}\biggr) \leqslant \sum_{i=t}^d \biggl( \sum_{j=0}^\infty \biggl(\frac89\biggr)^{j}\biggr)|\mathcal N_i|_{\mathrm{tot}}= 9\sum_{i=t}^d|\mathcal N_{i}|_{\mathrm{tot}}.
\end{equation*}
\notag
$$
Поэтому, если списки $\mathcal M_d, \dots, \mathcal M_t$ были созданы до остановки цикла, то
$$
\begin{equation}
\sum_{i=t}^{d}|\mathcal M_i|_{\mathrm{tot}} \leqslant 9\sum_{i=t}^d|\mathcal N_{i}|_{\mathrm{tot}}\leqslant 9 |\mathcal N|_{\mathrm{tot}}.
\end{equation}
\tag{4.6}
$$
При $i \in \{t, \dots, d\}$, по лемме 4.9, (v) получаем, что $(d-i+1)$-я итерация шага 6, (a) занимает время $O(T(|\mathcal M_i|_{\mathrm{tot}}))$. Из этого следует, что по лемме 6.4 все итерации шага 6, (a) вместе занимают не более $O(|\mathcal M_t|)+\dots+O(|\mathcal M_d|)$ времени, что в свою очередь не превышает $O(T(|\mathcal N|_{\mathrm{tot}}))$ по неравенству (4.6) и потому, что функция $T$ удовлетворяет свойству (T3) из соглашения 6.3. Для каждого $i \in \{t, \dots, d\}$ вызов процедуры NormalizeList на $(d-i+ 1)$-й итерации шага 6, (b) занимает не более $O(T(\frac89|\mathcal M_{i}|_{\mathrm{tot}}+|\mathcal N_{i-1}|_{\mathrm{tot}}))$ времени. Просуммировав эти значения по $i$ и применив лемму 6.4, получим, что вместе эти вызовы занимают $O(T(\frac89|\mathcal M_t|_{\mathrm{tot}}+\dots+ \frac89|\mathcal M_d|_{\mathrm{tot}}+|\mathcal N|_{\mathrm{tot}}))$, что, в свою очередь, не превышает $O(T(|\mathcal N|_{\mathrm{tot}}))$ в силу неравенства (4.6) и свойству (T3). Таким образом, мы показали, что весь шаг 6 может быть выполнен за время $O(|\mathcal N|_{\mathrm{tot}})$. Теперь предположим, что списки $\mathcal M_d, \dots, \mathcal M_t$ были созданы на шаге 6 до остановки цикла. Если $t \geqslant 2$, т.е. цикл был прерван досрочно, то на шаге 7 алгоритм вернет минимальный список $\mathcal M:=\mathcal M_t \cup \mathcal N_{t-1} \cup \dots \cup \mathcal N_0$ размера, не превышающего
$$
\begin{equation*}
|\mathcal M|_{\mathrm{tot}}= |\mathcal M_t|_{\mathrm{tot}}+\sum_{i=0}^{t-1} |\mathcal N_i|_{\mathrm{tot}}\leqslant 9\sum_{i=t}^{d}|\mathcal N_i|_{\mathrm{tot}}+9 \sum_{i=0}^{t-1}|\mathcal N_i|_{\mathrm{tot}}= 9 |\mathcal N|_{\mathrm{tot}}.
\end{equation*}
\notag
$$
Если же $t=1$, т.е. цикл был выполнен полностью, то шаг 7 принимает список $\mathcal M_1$, размер которого не превышает $m:=9 (|\mathcal N|_{\mathrm{tot}}-|\mathcal N_0|_{\mathrm{tot}})$ (4.6). Поэтому обрезка на шаге 7, (a) занимает не более $O(T(|\mathcal M_1|_{\mathrm{tot}}))=O(T(m))= O(|\mathcal N|_{\mathrm{tot}})$ времени и возвращает список $\mathcal N' \cup \mathcal K$, размер которого не превышает $m$ по лемме 4.4. Нормализация на шаге 7, (b) также занимает не более $O(T(m))= O(|\mathcal N|_{\mathrm{tot}})$ времени, и потому весь шаг 7 выполняется за время, не превышающее $O(|\mathcal N|_{\mathrm{tot}})$, и возвращает список $\mathcal M$, по размеру не превышающий $9 |\mathcal N|_{\mathrm{tot}}$.
Теорема 3.2 доказана. § 5. Случай свободной группыВ этом параграфе будет показано, как адаптировать методы, предложенные в предыдущем параграфе, для случая считающих функций на свободной группе. Как будет видно далее, несмотря на заметное усложнение обозначений, смысловых изменений будет немного. 5.1. Кодирование считающих функций на свободных группахКак и ранее, рассмотрим конечный алфавит $\mathrm A=\{\mathrm a_1, \dots, \mathrm a_n\}$ размера $n \geqslant 2$. Затем определим расширенный алфавит $\mathrm A^\pm:= \{\mathrm a_1, \dots, \mathrm a_n, \mathrm a^{-1}_1, \dots, \mathrm a^{-1}_n\}$, где $\mathrm a^{-1}_1, \dots, \mathrm a^{-1}_n$ – дополнительные символы, выбранные так, что $|\mathrm A^\pm|=2n$. Определим $F_n$ как подмножество $\mathrm A^{\pm \ast} \subset (\mathrm A^\pm)^*$, состоящее из несократимых слов, т.е. таких, которые не содержат ни одного подслова вида $\mathrm a_j\mathrm a^{-1}_j$ или $\mathrm a^{-1}_j\mathrm a_j$ для некоторого $j \in \{1, \dots, n\}$. Для данного слова $w \in \mathrm A^{\pm \ast}$ будем обозначать его первую и последнюю буквы через $w_{\mathrm{in}} \in \mathrm A^\pm$ и $w_{\mathrm{fin}} \in \mathrm A^\pm$ соответственно. Будем считать, что кольцо коэффициентов $\mathfrak N$ выбирается из множества $\{\mathbb Z, \mathbb Q\}$. Назовем пару $(w, \mathrm x)$, в которой $w \in \mathrm A^{\pm \ast}$ и $x \in \operatorname{Num}_{\mathfrak N}$, словарно-числовой парой (или просто парой) и назовем словарно-числовым-списком (или просто списком) любой двусвязный список словарно-числовых пар. Любой такой список представляет считающую функцию над $F_n$. К примеру, если список $\mathcal L$ записан как $((w_1, x_1), \dots, (w_N, x_N))$, то его ассоциированная считающая функция есть
$$
\begin{equation*}
\rho_{\mathcal L}=\sum_{i=1}^N \langle x_i \rangle \rho_{w_i}.
\end{equation*}
\notag
$$
Как и в случае моноида, мы определяем максимальную глубину списка $\mathcal L=((w_1, \mathrm x_1), \dots, (w_N, \mathrm x_N))$ как и мы называем $\mathcal L$ минимальным, если он не эквивалентен ни одному списку меньшей глубины. Мы также считаем $\mathcal L$ нормализованным, если все слова $w_j$ в нем различны, упорядочены по длине и в лексикографическом порядке (относительно некоторого полного порядка на $\mathrm A^\pm$) в рамках одной длины и если коэффициенты $\mathrm x_j \not \equiv 0$ для всех $j \in \{1, \dots, N\}$. Замечание 5.1. Как и в случае моноида, несложно устанавливается, что существует процедура NormalizeList, которая заменяет данный список $\mathcal L$ на эквивалентный ему нормализованный список $\mathcal N$ размера $|\mathcal N|_{\mathrm{tot}} \leqslant |\mathcal L|_{\mathrm{tot}}$ и занимает время $O(T(|\mathcal L|_{\mathrm{tot}}))$. Как и в случае моноидов, между функциями из $F_n$ есть два вида базовых соотношений (см [9]), но тут их формулы выглядят слегка иначе:
$$
\begin{equation}
\rho_w \sim \sum_{\mathrm a \in \mathrm A^\pm \setminus \{w_{\mathrm{in}}^{-1}\}} \rho_{\mathrm a w}, \qquad \rho_w \sim \sum_{\mathrm a \in \mathrm A^\pm \setminus \{w_{\mathrm{fin}}^{-1}\}} \rho_{w\mathrm a}.
\end{equation}
\tag{5.1}
$$
Для того чтобы учесть это небольшое изменение, нам придется слегка видоизменить обрезку и перенос. В особенности нам будут интересны антисимметричные функции (такие $f$, что $f(g^{-1})= -f(g)$), так как они представляют классы в ограниченной когомологии $F_n$ (см. [5]). Списки, представляющие антисимметричные функции, будут также называться антисимметричными. Как и ранее, два списка считаются эквивалентными, если их ассоциированные считающие функции эквивалентны, т.е. находятся на ограниченном расстоянии друг от друга, и это отношение эквивалентности обозначается как $\sim$. Мы также называем две антисимметричные функции $f_1$, $f_2$ и списки, их представляющие, когомологичными, если их разность $f_1-f_2$ находится на ограниченном расстоянии от гомоморфизма, т.е. если $f_1$ и $f_2$ определяют один и тот же класс в ограниченной когомологии. Отношение когомологичности обозначается как $f_1 \equiv f_2$. Мы хотим построить алгоритм для решения двух следующих алгоритмических проблем. Проблема 5.2 (проблема эквивалентности). По двум поданным на вход спискам $\mathcal L_1$, $\mathcal L_2$ понять, выполнено ли $\mathcal L_1 \sim \mathcal L_2$. Проблема 5.3 (проблема когомологичности). По двум поданным на вход антисимметричным спискам $\mathcal L_1$, $\mathcal L_2$ понять, выполнено ли $\mathcal L_1 \equiv \mathcal L_2$. Как и в случае моноида, обе эти проблемы можно свести к третьей проблеме, формулируемой ниже. Это сразу следует из того факта, что если некоторый список $\mathcal L$ эквивалентен антисимметричному списку $\mathcal L'$, то $\mathcal L$ когомологичен пустому списку тогда и только тогда, когда он эквивалентен списку глубины $\leqslant 1$. Проблема 5.4 (проблема минимальности). По поданному на вход списку $\mathcal L$ найти минимальный список $\mathcal L'$, эквивалентный $\mathcal L$. 5.2. Братства и базовые преобразованияОбозначим через $T_n$ правое дерево Кэли свободной группы $F_n$ относительно расширенного множества порождающих $\mathrm A^{\pm}$ и будем рассматривать его как ориентированное корневое дерево с корнем $\varepsilon$ и гранями, направленными от $\varepsilon$. Отождествим элементы $F_n$ с вершинами $T_n$. В контексте $T_n$ мы определяем отцов, братьев, братства и родственные братства так же, как и в случае моноида, и используем те же обозначения. Однако необходимо отметить, что $|\{\varepsilon \ast\}|=2n$, в то время как $|\{w\ast\}|=2n-1$ для каждого $w \neq \varepsilon$, т.е. единственное братство глубины $1$ отличается по размеру от всех остальных братств. Для данного нормализованного списка $\mathcal L$ и братства $B$ мы определяем взвешенное братство $\mathcal L_B$ аналогично случаю моноида. Как следствие, мы можем для группового случая определить процедуру DetachBrotherhood, удовлетворяющую свойствам и временной сложности, определенным в лемме 4.3. 5.2.1. ПодрезкаПусть $\mathcal L$ – нормализованный список максимальной $\ell \geqslant 1$. Как и в случае моноида, если $B=\{w\ast\}$ – братство и соответствующее взвешенное братство $\mathcal L_B= ((w\mathrm a_1, \mathrm x_1), \dots, (w\mathrm a_n^{-1}, \mathrm x_{2n}))$ не пусто и постоянно с $\mathrm x_1 \equiv \dots \equiv \mathrm x_{2n} \equiv \mathrm x_n \equiv \mathrm x$ для некоторого $\mathrm x \in \operatorname{Num}_{\mathfrak N}$, то мы можем удалить $\mathcal L_B$ из $\mathcal L$, добавить $\{\mathrm w, \mathrm x\}$ и нормализовать получившийся список. Данное преобразование будет называться подрезкой, а нормализованный список, который невозможно подрезать, будет называться подрезанным. Теперь становится возможным доопределить процедуру PruneList для случая свободной группы. Новая процедура состоит из всех тех же шагов, что и в случае моноида. Эта процедура будет удовлетворять всем свойствам, перечисленным в лемме 4.4, за исключением того, что оценка из п. (iv) будет иметь вид
$$
\begin{equation*}
|\mathcal L|_{\mathrm{tot}} \leqslant \frac{1}{h(n)}(|\mathcal N|_{\mathrm{tot}}-|\mathcal N'|_{\mathrm{tot}}),
\end{equation*}
\notag
$$
где $h(n)$ – размер непустого постоянного братства глубины $\ell$, или, что то же самое, $h(n)=2n-1$, если $\ell \geqslant 2$, и $h(n)=2n$, если $\ell=1$. 5.2.2. Обобщение переноса с подрезкойКак и в для моноида, в групповом случае также присутствует понятие переноса с подрезкой. На самом деле в данном случае у нас есть две вариации переноса с подрезкой, и выбор зависит от того, имеет ли переносимое братство глубину $\geqslant 3$ (общий случай), или же $2$ (особый случай). В этом подпункте мы разберем общий случай, а особый случай мы оставим для следующего подпункта. Итак, пусть $u \in F_n \setminus \{\varepsilon\}$, и пусть $\mathcal L$ – нормализованный список глубины $\ell \geqslant 3$, причем $|u|=\ell-2 \geqslant 1$. Положим
$$
\begin{equation*}
\mathrm A^{\pm}_{\mathrm{in}}:=\mathrm A^{\pm} \setminus \{u_{\mathrm{in}}^{-1}\}, \qquad \mathrm A^{\pm}_{\mathrm{fin}} :=\mathrm A^{\pm} \setminus \{u_{\mathrm{fin}}^{-1}\}.
\end{equation*}
\notag
$$
Как и в случае моноида, мы обозначаем через $\mathcal L_{\{\ast u \ast\}}$ объединение взвешенных братств вида $\mathcal L_{\{\mathrm a \mathrm u \ast\}}$, для которых $\mathrm a \in \mathrm A^{\pm}_{\mathrm{in}}$. Элементы $\mathcal L_{\{\ast u \ast\}}$ будут иметь вид
$$
\begin{equation}
(\mathrm {a} \mathrm u \mathrm a', \mathrm x_{\mathrm a\mathrm a'}), \quad\text{где }\ \mathrm a \in \mathrm A^{\pm}_{\mathrm{in}}, \quad \mathrm a' \in \mathrm A^{\pm}_{\mathrm{fin}}.
\end{equation}
\tag{5.2}
$$
Как следствие, мы можем определить кодовую матрицу переноса $\mathrm T(\mathcal L, u)$ как матрицу размера $(2\ell-1) \times (2\ell -1)$, строки и ряды которой соотносятся с $\mathrm A^{\pm}_{\mathrm{in}}$ и $\mathrm A^{\pm}_{\mathrm{fin}}$ соответственно, и для которой элемент $\mathrm t_{\mathrm a \mathrm a'}$ с индексом $(\mathrm a, \mathrm a') \in \mathrm A^{\pm}_{\mathrm{in}} \times \mathrm A^{\pm}_{\mathrm{fin}}$ равен $\mathrm x_{\mathrm a\mathrm a'}$, если $\mathcal L_{\{\ast u \ast\}}$ содержит элемент вида (5.2), и $t_{\mathrm a \mathrm a'}:=\varepsilon$ иначе. Если мы положим $\mathrm b \in \mathrm A^{\pm}_{\mathrm{in}}$, то получится, что
$$
\begin{equation*}
\begin{aligned} \, \rho_{\mathcal L_{\{\ast u \ast\}}} &= \sum_{\mathrm a \in \mathrm A^\pm_{\mathrm{in}}} \sum_{\mathrm a' \in \mathrm A^\pm_{\mathrm{fin}}} \mathrm t_{\mathrm a \mathrm a'}\rho_{\mathrm a u \mathrm a'} \\ &= \sum_{\mathrm a \in \mathrm A^\pm_{\mathrm{in}}} \sum_{\mathrm a' \in \mathrm A^\pm_{\mathrm{fin}}} (\mathrm t_{\mathrm a \mathrm a'}-\mathrm t_{\mathrm b \mathrm a'})\rho_{\mathrm a u \mathrm a'} \rho_{\mathrm a_i\mathrm u \mathrm a_j}+\sum_{\mathrm a \in \mathrm A^\pm_{\mathrm{in}}} \sum_{\mathrm a' \in \mathrm A^\pm_{\mathrm{fin}}}\mathrm t_{\mathrm b \mathrm a'} \rho_{\mathrm a u \mathrm a'} \\ &\sim \sum_{\mathrm a \in \mathrm A^\pm_{\mathrm{in}} \setminus\{\mathrm b\}} \sum_{\mathrm a' \in \mathrm A^\pm_{\mathrm{fin}}} (\mathrm t_{\mathrm a \mathrm a'}-\mathrm t_{\mathrm b \mathrm a'})\rho_{\mathrm a u \mathrm a'} +\sum_{\mathrm a' \in \mathrm A^\pm_{\mathrm{fin}}}\mathrm t_{\mathrm b \mathrm a'} \rho_{u \mathrm a'}. \end{aligned}
\end{equation*}
\notag
$$
Поэтому список $\mathcal L$ эквивалентен любому списку $\mathcal L'$, полученному из $\mathcal L$ путем удаления $\mathcal L_{\{\ast u \ast\}}$, добавления пары вида $(\mathrm a\mathrm u \mathrm a', \mathrm y_{\mathrm a\mathrm a'})$, где $\mathrm y_{\mathrm a\mathrm a'} \equiv \mathrm t_{\mathrm a \mathrm a'}-\mathrm t_{\mathrm b \mathrm a'}$ для всех $\mathrm a \in \mathrm A^\pm_{\mathrm{in}} \setminus\{\mathrm b\}$ и $\mathrm a' \in \mathrm A^\pm_{\mathrm{fin}}$, где $\mathrm t_{\mathrm a \mathrm a'}\not \equiv \mathrm t_{\mathrm b \mathrm a'}$, добавления пары вида $(\mathrm u \mathrm a', \mathrm z_{\mathrm a'})$, где $\mathrm z_{\mathrm a'} \equiv \mathrm t_{\mathrm b \mathrm a'}$ для каждого $\mathrm a' \in \mathrm A^\pm_{\mathrm{fin}}$, где $ \mathrm t_{\mathrm b \mathrm a'} \neq \varepsilon$, и нормализацией получившегося списка. Будем говорить, что любой подобный список $\mathcal L'$ получается из $\mathcal L$ путем переноса с основой $u$ и особой буквой $\mathrm b$. Согласно [9; теорема 4.2] теорема 2.9 с необходимыми изменениями также выполняется в случае свободной группы, т.е. список максимальной глубины $\ell$ минимален, если в нем есть два родственных братства максимальной глубины, одно из которых пусто, а второе – непостоянно. Если $\mathcal L'$ получается из $\mathcal L$ путем переноса с основой $u$ и специальной буквой $\mathrm b$, то $\mathcal L'_{\mathrm bu*}$ пусто, и потому $\mathcal L'$ будет минимальным, если все братства вида $\mathcal L'_{\mathrm au*}$ с $\mathrm a \in \mathrm A^\pm_{\mathrm{in}} \setminus\{\mathrm b\}$ не будут постоянными. Как и в случае моноидов, из этого следует, что если $\mathrm T(\mathcal L, u)$ не является суммой строки и столбца, то $\mathcal L'$ минимален. Теперь предположим, что $\mathrm T(\mathcal L, u)=(\mathrm t_{\mathrm a\mathrm a'})$ – сумма строки и столбца. Это значит, что для каждого $\mathrm a \in \mathrm A^\pm_{\mathrm{in}}$ значение $\langle \mathrm t_{\mathrm a\mathrm a'} \ominus \mathrm t_{\mathrm b\mathrm a'} \rangle$ не зависит от $\mathrm a' \in \mathrm A^\pm_{\mathrm{fin}}$. Следовательно, если мы выберем такие элементы $y_{\mathrm a}, z_{\mathrm a'} \in \operatorname{Num}_{\mathfrak N}$, что
$$
\begin{equation}
\mathrm y_{\mathrm a} \equiv \mathrm t_{\mathrm a\mathrm a'} \ominus \mathrm t_{\mathrm b\mathrm a'}, \quad \mathrm z_{\mathrm a'} \equiv \mathrm t_{\mathrm b \mathrm a'}, \qquad \mathrm a \in \mathrm A^\pm_{\mathrm{in}}, \quad \mathrm a' \in \mathrm A^\pm_{\mathrm{fin}},
\end{equation}
\tag{5.3}
$$
то из вышеприведенной формулы для $\rho_{\mathcal L_{\ast u \ast}}$ можно будет получить, что
$$
\begin{equation*}
\begin{aligned} \, \rho_{\mathcal L_{\ast u \ast}} &\sim \sum_{\mathrm a \in \mathrm A^\pm_{\mathrm{in}} \setminus\{\mathrm b\}} \sum_{\mathrm a' \in \mathrm A^\pm_{\mathrm{fin}}} (\mathrm t_{\mathrm a \mathrm a'}-\mathrm t_{\mathrm b \mathrm a'})\rho_{\mathrm a u \mathrm a'} +\sum_{\mathrm a' \in \mathrm A^\pm_{\mathrm{fin}}}\mathrm t_{\mathrm b \mathrm a'} \rho_{u \mathrm a'} \\ &=\sum_{\mathrm a \in \mathrm A^\pm_{\mathrm{in}} \setminus\{\mathrm b\}} \mathrm y_{\mathrm a}\rho_{\mathrm a u} +\sum_{\mathrm a' \in \mathrm A^\pm_{\mathrm{fin}}}\mathrm z_{\mathrm a'} \rho_{u \mathrm a'}. \end{aligned}
\end{equation*}
\notag
$$
Получается, что если $\mathrm T(\mathcal L, u)$ – сумма строки и столбца и $\mathcal L'$ получается из $\mathcal L$ путем удаления $\mathcal L_{\ast u \ast}$, добавления пар $(\mathrm au, \mathrm y_{\mathrm a})$ и $(u\mathrm a', \mathrm z_{\mathrm a'})$ в соответствии с (5.3) и нормализации, то $\mathcal L'$ эквивалентен $\mathcal L$. Будем говорить, что $\mathcal L'$ получается из $\mathcal L$ путем применения переноса с подрезкой с основой $u$ и особой буквой $\mathrm b$. С помощью этого преобразования мы можем обобщить результаты, полученные в п. 4.3. Лемма 5.5. Существует процедура TransferAndPrune, удовлетворяющая следующим свойствам: (i) входом является семейство непостоянных родственных братств $(\mathcal B_1, \dots, \mathcal B_n)$ глубины $\ell \geqslant 3$ таких, что $\mathcal B:=\mathcal B_1 \cup \dots \cup \mathcal B_n$ нормализован; (ii) результатом является булева переменная minimal и список $\mathcal L$; (iii) если minimal = true, то $\mathcal B$ не эквивалентен ни одному списку глубины $\leqslant \ell-1$, и $\mathcal L=\mathcal B$; (iv) если же minimal = false, то $\mathcal L$ имеет постоянную глубину $\ell-1$, эквивалентен $\mathcal B$ и имеет общий размер, удовлетворяющий оценке
$$
\begin{equation*}
|\mathcal L|_{\mathrm{tot}}\leqslant\frac{8}{9} |\mathcal B|_{\mathrm{tot}};
\end{equation*}
\notag
$$
(v) временная сложность процедуры равна $O(T(|\mathcal B|_{\mathrm{tot}}))$. Ключевых отличий от результата п. 4.3 два: во-первых, мы допускаем $n=2$, в то время как в случае моноида условие $n \geqslant 3$ было необходимо для выполнения оценки (iv). С другой стороны, нам приходится предполагать, что $\ell \geqslant 3$, но, несмотря на это, мы разберемся с случаем $\ell=2$ (для которого основа семейства братств есть пустое слово) отдельно. Доказательство леммы 5.5. Мы будем повторять шаги алгоритма, описанного в п. 4.3, там, где это будет возможно. В частности, данный алгоритм будет состоять из семи шагов, однозначно соответствующих семи шагам алгоритма для моноида.
На первом шаге мы вычисляем основу семейства братств и матрицу переноса, как и в случае моноида. Матрица переноса будет иметь размер $m \times m$, где $m:=(2n-1)$, и, так как $n \geqslant 2$, выполняется $m \geqslant 3$. Индексы получившейся матрицы переноса представляются множеством $\mathrm A^{\pm}_{\mathrm{in}} \times \mathrm A^{\pm}_{\mathrm{fin}}$, а не $\{1, \dots, m\} \times \{1, \dots, m\}$, но за исключением этого изменения в индексировании выполнение шагов 2 и 3 не отличается от случая моноида. На шаге 4 разреженность матрицы должна зависеть от размера матрицы $m$, а не от $n$. Поэтому мы полагаем Sparse${} :={}$true, если $m\geqslant 4$ (т.е. $n \geqslant 3$) и матрица $\mathrm T$ содержит менее $3m=6n-3$ ненулевых элементов или если $m=3$ (т.е. $n=2$) и $\mathrm T$ содержит менее $2m=4n-2=6$ ненулевых элементов. Оставшиеся шаги 5–7 будут выполняться так же, как и в случае моноида, за исключением различий в индексировании. Например, на шаге 5, (a) мы добавляем к результату пары вида $(u\mathrm a', \mathrm t_{\mathrm b\mathrm a'})$ для всех $\mathrm a'\in A^{\pm}_{\mathrm{fin}}$, где $\mathrm b \in \mathrm A^{\pm}_{\mathrm{in}}$ выбирается так, чтобы
$$
\begin{equation*}
\sum_{\mathrm a' \in A^{\pm}_{\mathrm{fin}}} \|\mathrm t_{\mathrm b\mathrm a'}\|= \min_{\mathrm a\in \mathrm A^{\pm}_{\mathrm{in}}} \sum_{\mathrm a' \in A^{\pm}_{\mathrm{fin}}} \|\mathrm t_{\mathrm a\mathrm a'}\|,
\end{equation*}
\notag
$$
и для остальных шагов изменения аналогичны. Очевидно, что изменения в индексировании не влияют ни на время выполнения алгоритма, ни на размер результата. Размер будет всегда удовлетворять свойству (iv), так как для всех $n\geqslant 2$ выполняется $m\geqslant 3$, и потому доказательство леммы 4.8 применимо к $(m \times m)$-матрице $\mathrm T$. Лемма доказана. 5.2.3. Особый перенос с подрезкойПреобразование переноса с подрезкой, описанное в предыдущем разделе, работает для $n \geqslant 2$ при условии, что переносимое братство имеет глубину не менее $3$. Для братств глубины $\ell=2$ также существует своя вариация преобразования, но ее описание будет несколько более сложным. Тем не менее можно сформулировать следующую лемму. Лемма 5.6. Утверждение леммы 5.5 верно и для $\ell=2$, за исключением того, что свойство (iv) заменяется на ($\mathrm{iv}'$) если minimal = false, то $\mathcal L$ имеет постоянную глубину $\ell-1=1$, эквивалентен $\mathcal B$, и его размер ограничен сверху В частности, $|\mathcal L|_{\mathrm{tot}} \leqslant 2n |\mathcal B|_{\mathrm{tot}}$.В действительности эта оценка далеко не оптимальная, но тем не менее ее вполне достаточно. Перейдем к доказательству леммы. Пусть $\mathcal L$ – нормализованный список постоянной глубины $2$. Зафиксируем некоторую букву $\mathrm b \in \mathrm A^\pm$ (мы не будем пытаться выбрать ее оптимально) и положим $\mathrm A^\pm_{\mathrm{in}}:=\mathrm A^\pm \setminus \{\mathrm b^{-1}\}$. Мы хотим определить преобразование, которое занулит подбратства $\mathcal L$ типа $\{\mathrm b\ast\}$. Во-первых, определим матрицу переноса $\mathrm T= (\mathrm t_{\mathrm a\mathrm a'})$ над множеством индексов $\mathrm A^\pm \times \mathrm A^\pm$ и положим элемент матрицы $\mathrm t_{\mathrm a\mathrm a'}$ равным коэффициенту при $\mathrm a\mathrm a'$ в $\mathcal L$, если такое слово присутствует в $\mathcal L$, и положим $\mathrm t_{\mathrm a\mathrm a'}:=\varepsilon$ иначе. (В частности, тогда $\mathrm t_{\mathrm a\mathrm a^{-1}}=\varepsilon$ для всех $\mathrm a \in \mathrm A^\pm$.) Поскольку для $a' \in \mathrm A^\pm_{\mathrm{in}} $ известно, что
$$
\begin{equation*}
\langle \mathrm t_{\mathrm b\mathrm a'}\rangle \rho_{\mathrm b\mathrm a'} \sim \langle\mathrm t_{\mathrm b\mathrm a'}\rangle\rho_{\mathrm a'}-\sum_{\mathrm a \neq (\mathrm a')^{-1}} \langle\mathrm t_{\mathrm b\mathrm a'}\rangle\rho_{\mathrm a\mathrm a'},
\end{equation*}
\notag
$$
мы получаем, что
$$
\begin{equation*}
\begin{aligned} \, \rho_{\mathcal L} &= \sum_{\mathrm a \in \mathrm A^\pm} \sum_{\mathrm a' \neq \mathrm a^{-1}} \langle\mathrm t_{\mathrm a\mathrm a'}\rangle\rho_{\mathrm a\mathrm a'} \\ &\sim \sum_{a' \in \mathrm A^\pm_{\mathrm{in}}} \langle\mathrm t_{\mathrm b\mathrm a'}\rangle\rho_{\mathrm a'}+\sum_{a \in \mathrm A^\pm\setminus\{b\}} \langle\mathrm t_{\mathrm a\mathrm b^{-1}}\rangle\rho_{\mathrm a\mathrm b^{-1}}+\sum_{\mathrm a \in \mathrm A^\pm \setminus\{\mathrm b\}}\sum_{\mathrm a'\in \mathrm A^\pm_{\mathrm{in}}\setminus\{\mathrm a^{-1}\}} \langle\mathrm t_{\mathrm a\mathrm a'}\ominus \mathrm t_{\mathrm b\mathrm a'}\rangle\rho_{\mathrm a\mathrm a'}. \end{aligned}
\end{equation*}
\notag
$$
Следовательно, список $\mathcal L$ не минимален, только если
$$
\begin{equation}
\mathrm t_{\mathrm a\mathrm b^{-1}}l \equiv \mathrm t_{\mathrm a\mathrm a'}\ominus \mathrm t_{\mathrm b\mathrm a'} \quad \text{для всех }\ \mathrm a \in \mathrm A^\pm \setminus\{\mathrm b\}, \quad \mathrm a' \in \mathrm A_{\mathrm{in}}^\pm \setminus\{\mathrm a^{-1}\}.
\end{equation}
\tag{5.4}
$$
С другой стороны, если условие (5.4) выполняется, то мы можем, подрезав список, получить, что
$$
\begin{equation*}
\begin{aligned} \, \rho_{\mathcal L} &\sim \sum_{a' \in \mathrm A^\pm_{\mathrm{in}}} \langle \mathrm t_{\mathrm b\mathrm a'}\rangle \rho_{\mathrm a'}+\sum_{a \in \mathrm A^\pm\setminus\{b\}} \langle \mathrm t_{\mathrm a\mathrm b^{-1}}\rangle \rho_{\mathrm a} \\ &= \langle \mathrm t_{\mathrm b\mathrm b}\rangle \rho_{\mathrm b}+\langle \mathrm t_{\mathrm b^{-1}\mathrm b^{-1}}\rangle \rho_{\mathrm b^{-1}}+\sum_{a \in \mathrm A^{\pm} \setminus\{b, b^{-1}\}} \langle \mathrm t_{\mathrm b\mathrm a} \oplus \mathrm t_{\mathrm a\mathrm b}^{-1}\rangle\rho_{\mathrm a}. \end{aligned}
\end{equation*}
\notag
$$
Из этого напрямую следует, что следующая процедура выполняется корректно. Процедура SpecialTransferAndPrune. Вход: семейство непостоянных родственных братств $(\mathcal B_1, \dots, \mathcal B_n)$ глубины $\ell\,{=}\,2$ таких, что список $\mathcal B:=\mathcal B_1 \cup \dots \cup \mathcal B_n$ нормализован. Результат: Булева переменная minimal и список $\mathcal L$.
Нетрудно заметить, что временная сложность процедуры есть $O(T(|\mathcal B|_{\mathrm{tot}}))$. Что же до свойства ($\mathrm{iv}'$), в случае не минимального списка $\|\mathcal L\| \leqslant \|\mathrm T\|=\|\mathcal B\|$, так как каждый ненулевой коэффициент из $\mathrm T$ копируется в $\mathcal L$ не более одного раза и, очевидно, $|\mathcal L| \leqslant |\mathrm A^\pm|=2n$, то ($\mathrm{iv}'$) также выполняется. 5.3. Алгоритм для свободных групп5.3.1. Основной шаг алгоритмаТеперь, когда мы обобщили процедуры NormalizeList, DetachBrotherhood, PruneList и TransferAndPrune на случай свободной группы, мы можем приступить к построению самого алгоритма. Последняя из перечисленных процедур применима лишь для списков глубины $\ell \geqslant 3$, но для случая глубины $\ell=2$ возможно применение процедуры SpecialTransferAndPrune из п. 5.2.3. С помощью этих процедур мы можем определить MainProcessingStep практически таким же образом, как и для случая моноида (см. п. 4.4), за тем отличием, что в шаге 4, (b) процедура TransferAndPrune заменяется на процедуру SpecialTransferAndPrune, если $\ell= 2$. Анализ, схожий с проведенным в случае моноида, позволяет доказать следующее утверждение. Лемма 5.7. Для любой свободной группы $F_n$ ранга $n\geqslant 2$ существует алгоритм MainProcessingStep, удовлетворяющий следующим свойствам: (i) входом является нормализованный список $\mathcal L$ постоянной глубины $\ell \geqslant 2$; (ii) результатом является булева переменная minimal и нормализованный список $\mathcal L'$, эквивалентный $\mathcal L$; (iii) если minimal = true, то $\mathcal L'$ минимален; (iv) если minimal = false, то $\mathcal L'$ имеет постоянную глубину $\ell-1$ и
$$
\begin{equation}
|\mathcal L'|_{\mathrm{tot}} \leqslant \begin{cases} \dfrac89|\mathcal L|_{\mathrm{tot}}, & \textit{если }\ell \geqslant 3, \\ 2n|\mathcal L|_{\mathrm{tot}}, & \textit{если }\ell=2; \end{cases}
\end{equation}
\tag{5.5}
$$
(v) временная сложность алгоритма равна $O(T(|\mathcal L|))$. Отличие свойства (iv) от описанного в лемме 4.9 возникает из-за использования процедуры SpecialTransferAndPrune в особом случае. 5.3.2. Итоговый алгоритмТеперь мы готовы доказать основной результат настоящей статьи. Как и ранее, положим $T(N):=N$, если $\mathfrak N=\mathbb Z$, и $T(N):=N \log N$, если $\mathfrak N=\mathbb Q$. Теорема 5.8. Для каждого $n\geqslant 2$ и $\mathfrak N \in \{\mathbb Z, \mathbb Q\}$ существует алгоритм FindMinimalList, который принимает на вход кодовый список $\mathcal L$ над $F_n$ с коэффициентами из $\mathfrak N$, занимает не более $O(T(|\mathcal L|_{\mathrm{tot}}))$ времени и возвращает в качестве результата кодовый список $\mathcal M$, эквивалентный $\mathcal L$. Из этой теоремы можно вывести более точную версию теоремы 1.1 из введения. Следствие 5.9. Для каждого $n \geqslant 2$ и $\mathfrak N \in \{\mathbb Z, \mathbb Q\}$ существует алгоритм с временной сложностью $O(T(N))$ (где $N$ – размер входа), который по двум считающим функциям (соответственно считающим квазиморфизмам) над $F_n$ с коэффициентами из $\mathfrak N$ (закодированным в виде кодовых списков) определяет, эквивалентны ли они (соответственно когомологичны ли они). Доказательство теоремы 5.8 крайне схоже с доказательством теоремы 3.2 из случая моноида. В действительности, если мы будем применять групповые версии процедур NormalizeList, PruneList и MainProcessingStep вместо используемых в случае моноида, то мы можем определить алгоритм FindMinimalList ровно так же, как и в случае свободного моноида. Доказательство корректности данного алгоритма будет такое же, как и в случае моноида. Что же до анализа временной сложности алгоритма для случая группы, есть лишь одно различие с случаем моноида, вызываемое различием между леммой 4.9 и леммой 5.7. Если быть точнее, на шаге 6 мы применяем процедуру MainProcessingStep для создания списков $\mathcal M_d, \dots, \mathcal M_t$. Здесь либо $t=1$, либо $t \geqslant 2$ и цикл прерывается до вычисления $\mathcal M_{t-1}$. До тех пор, пока $i \in \{t,\dots, d\}$ удовлетворяет $i \geqslant 2$, будет выполняться неравенство
$$
\begin{equation*}
|\mathcal M_{i}|_{\mathrm{tot}} \leqslant \frac89|\mathcal M_{i+1}|_{\mathrm{tot}}+|\mathcal N_i|_{\mathrm{tot}},
\end{equation*}
\notag
$$
как и в случае моноида, но ввиду различия между леммой 4.9 и леммой 5.7 для особого случая мы можем получить лишь более слабую оценку
$$
\begin{equation*}
|\mathcal M_1|_{\mathrm{tot}} \leqslant 2n |\mathcal M_{2}|_{\mathrm{tot}}+|\mathcal N_1|_{\mathrm{tot}}.
\end{equation*}
\notag
$$
Конечно, это различие проявляется только при $t=1$, т.е. в том случае, если цикл на шаге 6 не прерывается ни на одной итерации. Предположим, что это так. В этом случае, как и для моноида, мы можем оценить
$$
\begin{equation*}
|\mathcal M_2|_{\mathrm{tot}} \leqslant \sum_{i=2}^{d}|\mathcal M_i|_{\mathrm{tot}} \leqslant 9\sum_{i=2}^d|\mathcal N_{i}|_{\mathrm{tot}},
\end{equation*}
\notag
$$
и потому
$$
\begin{equation*}
\begin{aligned} \, \sum_{i=1}^d |\mathcal M_i|_{\mathrm{tot}} &\leqslant |\mathcal M_1|_{\mathrm{tot}}+9\sum_{i=2}^d|\mathcal N_{i}|_{\mathrm{tot}} \leqslant 2n |\mathcal M_{2}|_{\mathrm{tot}}+9\sum_{i=1}^d|\mathcal N_{i}|_{\mathrm{tot}} \\ &\leqslant (18n+9) \sum_{i=1}^d|\mathcal N_{i}|_{\mathrm{tot}}, \end{aligned}
\end{equation*}
\notag
$$
т.е. для всех $i \in \{1,\dots, d\}$ мы получаем, что
$$
\begin{equation*}
|\mathcal M_i| \leqslant \sum_{i=1}^d |\mathcal M_i|_{\mathrm{tot}} \leqslant (18n+9) (|\mathcal N|_{\mathrm{tot}}-|\mathcal N_0|_{\mathrm{tot}}).
\end{equation*}
\notag
$$
Полученное неравенство позволяет заменить неравенство (4.6) в дальнейшем анализе временной сложности. Оставшаяся часть доказательства теоремы 5.8 совпадает с доказательством теоремы 3.2, за исключением того, что используемая константа $18n+9$ несколько хуже, чем $9$. Нельзя не отметить, что данное доказательство работает только в том случае, когда $n$ достаточно мало, чтобы считаться константой. § 6. Кодирование арифметических операцийВ этом параграфе будут описаны способы кодирования арифметических операций, используемые в основной части статьи. Для каждого из двух случаев $\mathfrak N \in \{\mathbb Z, \mathbb Q\}$ мы выберем алфавит $\Sigma_{\mathfrak N}$, кодирующее подмножество $ \operatorname{Num}_{\mathfrak N} \subset \Sigma^*$ множества $\Sigma^*$, состоящего из слов над $\Sigma$, и сюръективное отображение
$$
\begin{equation*}
\operatorname{Num}_{\mathfrak N} \to \mathfrak{N}, \qquad \mathrm x \mapsto \langle \mathrm x \rangle.
\end{equation*}
\notag
$$
Для данных $\mathrm x, \mathrm y \in \operatorname{Num}_{\mathfrak N}$ мы будем писать $\mathrm x \equiv \mathrm y$, если $\langle \mathrm x \rangle=\langle \mathrm y \rangle$. 6.1. Кодирование арифметики целых чиселДля кодирования полукольца $\mathbb N_0$ неотрицательных целых чисел выберем вспомогательный алфавит $\Sigma_{\mathbb N_0}:=\{0,1\}$. Затем определим $\operatorname{Num}_{\mathbb N_0}$ как объединение множества $\{0\}$ и множества всех конечных слов над $\Sigma_{\mathbb N_0}$, начинающихся на 1. Таким образом, мы можем получить биективное кодирование
$$
\begin{equation*}
\operatorname{Num}_{\mathbb N_0} \to \mathbb N_0, \qquad \mathrm x \mapsto \langle \mathrm x \rangle,
\end{equation*}
\notag
$$
где каждое слово из $\operatorname{Num}_{\mathbb N_0}$ интерпретируется как двоичная запись натурального числа, так что, например, $111$ представляет $7$. Для кодирования всего кольца $\mathbb Z$ целых чисел воспользуемся алфавитом $\Sigma_{\mathbb Z}:=\{0,1,+,-\}$ и определим
$$
\begin{equation*}
\operatorname{Num}_{\mathbb Z}:=\{\varepsilon\} \cup \{+\mathrm x \mid \mathrm x \in \operatorname{Num}_{\mathbb N_0}\} \cup \{-\mathrm x \mid \mathrm x \in \operatorname{Num}_{\mathbb N_0}\},
\end{equation*}
\notag
$$
где $\varepsilon$ обозначает пустое слово. Тогда мы можем определить кодирование
$$
\begin{equation*}
\operatorname{Num}_{\mathbb Z} \to \mathbb Z, \qquad \mathrm x \mapsto \langle \mathrm x \rangle,
\end{equation*}
\notag
$$
следующим образом: пустое слово интерпретируется как $0$, а для непустых слов мы интерпретируем первую букву как знак числа, а остальное слово – как двоичное представление модуля числа, к примеру, $-111$ представляет $-7$. Это кодирование практически инъективно, за исключением того, что $\varepsilon \equiv +0 \equiv -0$. Это свойство в будущем будет изредка нам полезно. Если $\mathrm x \in \operatorname{Num}_{\mathbb Z} \setminus \{\varepsilon\}$, то количество памяти, необходимой для хранения $\mathrm x$, т.е. длина его слова в алфавите $\Sigma_\mathbb Z$, будет равняться
$$
\begin{equation*}
|\mathrm x|_{\Sigma_\mathbb Z}:=\lceil\log_2(|\langle \mathrm x \rangle|+1)\rceil+1,
\end{equation*}
\notag
$$
тогда как $|\varepsilon|_{\Sigma_\mathbb Z}=0$. Для данного $\mathrm x\in \Sigma_\mathbb Z$ мы также будем писать $\|x\|:=|\mathrm x|_{\Sigma_\mathbb Z}$ и называть $\|\mathrm x\|$ размером $\mathrm x$. Следующее утверждение представляет собой элементарное упражнение из теории вычислений. Лемма 6.1. Пусть $\mathrm x_1,\mathrm x_2 \in \operatorname{Num}_\mathbb Z$. Тогда существуют элементы $\mathrm x_3=: \mathrm x_1 \oplus \mathrm x_2 \in \operatorname{Num}_\mathbb Z$ и $\mathrm x_4 =: \mathrm x_1 \ominus \mathrm x_2 \in \operatorname{Num}_\mathbb Z$ размера $\|\mathrm x_3\|, \|\mathrm x_4\|\leqslant \max\{\|\mathrm x_1\|,\|\mathrm x_2\|\}$, вычислимые за время $O(\max\{\|\mathrm x_1\|,\|\mathrm x_2\|\}+1)$ и удовлетворяющие равенствам $\langle \mathrm x_3 \rangle=\langle \mathrm x_1 \rangle+\langle \mathrm x_2 \rangle$ и $\langle \mathrm x_4 \rangle=\langle \mathrm x_1 \rangle-\langle \mathrm x_2 \rangle$. Замечание 6.2. Нам понадобится не только складывать и вычитать целые числа, но и определять, представляют ли два элемента $\operatorname{Num}_\mathbb Z$ одно и то же число. Оказывается, что это равенство может быть проверено за линейное время. Действительно, для слов длины $\geqslant 3$ достаточно просто сравнить эти слова над $\Sigma_\mathbb Z$. Для более коротких слов стоит также принимать во внимание тот факт, что $+0 \equiv-0 \equiv \varepsilon$, но в этом случае проверка так или иначе занимает ограниченное время. Хотя сложение, вычитание и сравнение целых чисел может быть естественным способом выполнено за линейное время (по отношению к размеру входа), для умножения это уже не так. В действительности построение эффективного алгоритма умножения больших целых чисел является важной открытой проблемой теории вычислений. На практике умножение часто реализуется через алгоритм Тоома–Кука (см. [20], [3]), самый быстрый алгоритм для умножения чисел среднего размера из известных. Для данных $\mathrm x_1, \mathrm x_2 \in \operatorname{Num}_\mathbb Z$ он вычисляет выражение $\mathrm x_1 \odot \mathrm x_2 \in \operatorname{Num}_\mathbb Z$, представляющее произведение $\langle \mathrm x_1\rangle \langle \mathrm x_2 \rangle$, за время $O(T_1(\|\mathrm x_1\|+\|\mathrm x_2\|))$, где $T_1(N)=N^{\theta}$ и $\theta=\log 5/\log 3\approx 1.465$. Тем не менее для теоретических исследований (или очень больших входных данных) существуют более быстрые алгоритмы: Шенхаге и Штрассен разработали алгоритм, который по данным $\mathrm x_1, \mathrm x_2 \in \operatorname{Num}_\mathbb Z$ вычисляет выражение $\mathrm x_1 \odot \mathrm x_2 \in \operatorname{Num}_\mathbb Z$, представляющее $\langle \mathrm x_1\rangle \langle \mathrm x_2 \rangle$, за время $O(T_2(\|\mathrm x_1\|+\|\mathrm x_2\|))$, где $T_2(N):=N \log(N) \log\log(N)$, и предположили, что оптимальное время работы такого алгоритма будет равно $O(T_3(\|\mathrm x_1\|+\|\mathrm x_2\|))$, где $T_3(N):=N \log(N)$. Алгоритм с такой временной сложностью был разработан сравнительно недавно усилиями Харви и ван дер Хувена (см. [11]), но до сих пор неизвестно, является ли его временная сложность оптимальной. Более того, до сих пор неизвестна никакая суперлинейная нижняя оценка для временной сложности алгоритма умножения двух натуральных чисел. Соглашение 6.3. С этого момента зафиксируем функцию $T$, обладающую следующими свойствами: (T1) $T$ супераддитивна, т.е. $T(N_1+N_2) \geqslant T(N_1)+T(N_2)$; (T2) $T$ асимптотически хотя бы линейна, т.е. $N=O(T(N))$; (T3) для каждого $C>1$ выполняется, что $T(N)=O(T(CN))$; (T4) умножение двух натуральных чисел, двоичная запись которых имеет размер $N_1$ и $N_2$ соответственно, может быть выполнено за время $O(T(N_1+N_2))$. Легко убедиться, что вышеописанные функции $T_1$, $T_2$ и $T_3$ удовлетворяют свойствам (T1)–(T3); они также удовлетворяют (T4), что было продемонстрировано в работах Тоома–Кука, Шенхаге–Штрассена и Харви–ван дер Хувена соответственно. 6.2. Лемма о выпуклости временной сложностиВ п. 6.1 мы убедились, что временная сложность умножения целых чисел представляется функцией $T$, супераддитивной и как минимум линейной. Из этих свойств $T$ можно вывести ключевое следствие. Лемма 6.4. Пусть $g$ – действительнозначная функция, и пусть $T$ – действительнозначная функция, удовлетворяющая свойствам (T1) и (T2) соглашения 6.3. Тогда если $g(x)=O(T(x))$, то где подразумевающиеся константы не зависят от $k$. В более точной формулировке лемма утверждает, что
$$
\begin{equation*}
\limsup \biggl\{\frac{g(x_1)+\dots+g(x_k)}{T(x_1+\dots+x_k)} \biggm| k \in \mathbb N, x_1, \dots, x_k \in \mathbb N\biggr\}< \infty.
\end{equation*}
\notag
$$
Доказательство леммы 6.4. Пусть $x:=x_1+\dots+x_k$. Так как $x_j \in \mathbb N$, получается, что $x_j \geqslant 1$ для каждого $j=1, \dots, k$, и потому $k \leqslant x$. Поскольку $g(x)=O(T(x))$, существуют константы $C_0, C_1, C_2 \in \mathbb N$ такие, что С точностью до перестановки $x_j$ мы можем предположить, что $x_1, \dots, x_r > C_0$ и $x_{r+1}, \dots, x_k \leqslant C_0$. Благодаря этому мы можем воспользоваться супераддитивностью функции $T$, чтобы получить Так как $T$ асимптотически хотя бы линейна, из этого неравенства следует утверждение леммы. Значение этого свойства для анализа времени работы основного алгоритма разъяснено в замечании 4.1. 6.3. Кодирование арифметики рациональных чиселПерейдем теперь к кодированию поля рациональных чисел $\mathbb Q$. Мы будем хранить эти числа в виде смешанных дробей, и для многих из рассматриваемых нами алгоритмов важно, что мы будем оставлять дроби в виде несокращенных смешанных дробей. В частности, это необходимо для эффективного сложения рациональных чисел (так как сокращение дробей еще более времяемко, чем умножение целых чисел). При работе с несокращенными смешанными дробями проявляется один побочный эффект – одно и то же рациональное число может быть представлено бесконечным количеством дробей. Тем не менее в нашем случае это не вызовет никаких проблем. Для определения нашего кодирования определим алфавит $\Sigma_{\mathbb Q}{:=}\, \{0,1,+,-,\backslash\}$ и рассмотрим в нем множество слов
$$
\begin{equation*}
\operatorname{Num}_{\mathbb Q}:=\{\varepsilon\} \cup \{\mathrm s \mathrm K/\mathrm m/\mathrm n\mid \mathrm s \in \{+,-\},\; \mathrm K,\mathrm m,\mathrm n \in \operatorname{Num}_{\mathbb N_0}, \;\langle \mathrm m \rangle < \langle \mathrm n \rangle \}.
\end{equation*}
\notag
$$
Теперь мы можем определить кодирование
$$
\begin{equation*}
\operatorname{Num}_{\mathbb Q} \to \mathbb Q, \qquad \mathrm x \mapsto \langle \mathrm x \rangle
\end{equation*}
\notag
$$
следующим образом: пустое слово интерпретируется как $0$, и для тройки слов $K,m,n \in \operatorname{Num}_{\mathbb N_0}$ положим
$$
\begin{equation*}
\langle \mathrm s \mathrm K/\mathrm m/\mathrm n \rangle:=\langle \mathrm s\mathrm K \rangle+\frac{\langle \mathrm m\rangle}{\langle \mathrm n \rangle}.
\end{equation*}
\notag
$$
Поскольку мы не требуем, чтобы $\mathrm m$ и $\mathrm n$ были взаимно просты, отображение $\mathrm x \to \langle \mathrm x \rangle$ не инъективно. Например, как $-11/10/101$, так и $-11/100/1010$ представляют $-3\frac25=-3 \frac 4 {10}$. Если $ \mathrm s \mathrm K/\mathrm m/\mathrm n\in \operatorname{Num}_{\mathbb Q} \setminus \{\varepsilon\}$, то объем памяти, требуемый для хранения $ \mathrm s \mathrm K/\mathrm{m}/\mathrm{n} $, выражается как
$$
\begin{equation*}
| \mathrm s \mathrm{K}/\mathrm{m}/\mathrm{n}|_{\Sigma_\mathbb Q}=\lceil\log_2(|\langle \mathrm{K} \rangle|+1)\rceil+\lceil\log_2(|\langle \mathrm{m} \rangle|+1)\rceil+\lceil\log_2(|\langle \mathrm{n} \rangle|+1)\rceil+3,
\end{equation*}
\notag
$$
в то время как $|\varepsilon|_{\Sigma_\mathbb Q}=0$. Тем не менее для удобства вычислений мы будем использовать немного другое понятие размера. Определим размер элемента $\operatorname{Num}_{\mathbb Q}$ как $\|\varepsilon\|:=0$ и
$$
\begin{equation}
\| \mathrm s \mathrm{K}/\mathrm{m}/\mathrm{n}\|:=\lceil\log_2(|\langle \mathrm{K} \rangle|+1)\rceil+2\lceil\log_2(|\langle \mathrm{n} \rangle|+1)\rceil+3.
\end{equation}
\tag{6.1}
$$
Поскольку $0\leqslant m < n$, мы имеем, что Таким образом, мы можем перейти к использованию размера $\|\cdot\|$, который эквивалентен размеру $|x|_{\Sigma_\mathbb Q}$ с точностью до мультипликативной константы $2$. Основное преимущество размера $\|\cdot\|$ состоит в том, что он ведет себя более естественно при арифметических операциях, что будет продемонстрировано в следующей лемме. Лемма 6.5. Пусть $T$ – функция, удовлетворяющая соглашению 6.3. Тогда для любых двух $\mathrm x_1,\mathrm x_2 \in \operatorname{Num}_\mathbb Q$ существуют элементы $\mathrm x_3=: \mathrm x_1 \oplus \mathrm x_2 \in \operatorname{Num}_\mathbb Q$ и $\mathrm x_4 =: \mathrm x_1 \ominus \mathrm x_2 \in \operatorname{Num}_\mathbb Q$ размеров $\|\mathrm x_3\|, \|\mathrm x_4\| \leqslant \|\mathrm x_1\|+ \|\mathrm x_2\|$, вычислимые за время $O(T(\|\mathrm x_1\|+\|\mathrm x_2\|))$ и удовлетворяющие $\langle \mathrm x_3 \rangle=\langle \mathrm x_1 \rangle+\langle \mathrm x_2 \rangle$ и $\langle \mathrm x_4 \rangle=\langle \mathrm x_1 \rangle-\langle \mathrm x_2 \rangle$. Доказательство. Случай вычитания будет напрямую следовать из случая сложения, потому сконцентрируемся на последнем. Если хотя бы один элемент из $\mathrm x_1$ и $\mathrm x_2$ пуст, то лемма очевидно верна.
Теперь предположим, что $\mathrm x_1=\mathrm s_1\mathrm K_1/\mathrm m_1/\mathrm n_1$ и $\mathrm x_2= \mathrm s_2\mathrm K_2/\mathrm m_2/\mathrm n_2$, и $K_1$, $m_1$, $n_1$, $K_2$, $m_2$, $n_2$ обозначают соответствующие интерпретации $\mathrm K_1$, $\mathrm m_1$, $\mathrm n_1$, $\mathrm K_2$, $\mathrm m_2$, $\mathrm n_2$. Во-первых, рассмотрим случай, когда оба знака $\mathrm s_1$ и $\mathrm s_2$ положительны. Сумма дробных частей $\mathrm x_1$ и $\mathrm x_2$ равна
$$
\begin{equation*}
\frac{m_1}{n_1}+\frac{m_2}{n_2}=\frac{p}{q},\quad \text{где }\ p:=m_1n_2+m_2n_1, \quad q:= n_1n_2.
\end{equation*}
\notag
$$
Потому определим
$$
\begin{equation*}
\mathrm p:=(\mathrm{m}_1 \otimes \mathrm{n}_2) \oplus (\mathrm{m}_2 \otimes \mathrm{n}_1), \qquad \mathrm{q}:=\mathrm{n}_1 \otimes \mathrm{n}_2.
\end{equation*}
\notag
$$
Из этих формул очевидно, что оба кода $\mathrm p$ и $\mathrm{q}$ по размеру не превышают $O(\|\mathrm x_1\|+\|\mathrm x_2\|)$, и вследствие свойств (T1) и (T3) функции $T$ мы можем вычислить их за время $O(T(\|\mathrm x_1\|+\|\mathrm x_2\|))$ с использованием трех умножений и двух сложений.
После вычисления $\mathrm p$ и $\mathrm{q}$ мы можем перейти к вычислению целой части дроби $p/q$, что возможно сделать за линейное время $O(\|\mathrm x_1\|+\|\mathrm x_2\|)$. Действительно, так как $0\leqslant m_1<n_1$ и $0\leqslant m_2<n_2$, мы получаем, что $m_1n_2<n_1n_2$ и $m_2n_1<n_1n_2$, и потому $p<2q$. Целая часть $K'=\lfloor p/q \rfloor$ может быть равна $0$ или $1$, потому для нахождения $K'$ достаточно проверить условие $p<q$. Если оно выполняется, то $K'=0$, иначе – $K'=1$, и проверка может быть выполнена за время $O(\|\mathrm x_1\|+\|\mathrm x_2\|)$. Если $K'=1$, нам также нужно вычислить $\mathrm p'=\mathrm p\ominus \mathrm{q}$ за линейное время. Заметим, что в этом случае $p/q=K'\frac{p'}q$, где $p':=\langle \mathrm p' \rangle$. Наконец, положим $\mathrm{K}:=\mathrm K_1 \oplus \mathrm{K}_2$ если $K'=0$, и $\mathrm{K}:= \mathrm{K}_1\oplus \mathrm{K}_2 \oplus (+1)$ если $K'=1$. Опять же, все это вычислимо за линейное время. Если $K'=0$, мы определяем $\mathrm x_3:= +\mathrm K/\mathrm p/\mathrm q$. Если же $K'=1$, то мы определяем $\mathrm x_3:=+\mathrm K/\mathrm p'/\mathrm q$. В любом случае $\mathrm x_3$ представляет $ \langle \mathrm x_1 \rangle+\langle \mathrm x_2 \rangle$ и вычислимо за время $O(T(\|\mathrm x_1\|+\|\mathrm x_2\|))$. Осталось лишь доказать неравенство $\|\mathrm x_3\|\leqslant \|\mathrm x_1\|+\|\mathrm x_2\|$. Для любых двух $n_1,n_2\geqslant 1$ выполняется, что
$$
\begin{equation*}
\lceil\log_2(n_1n_2+1)\rceil \leqslant \log_2((n_1+1)(n_2+1))+1 \leqslant \log_2(n_1+1)+\log_2(n_2+1)+1.
\end{equation*}
\notag
$$
По этой причине знаменатель $n_1n_2$ можно хранить в виде слова длины
$$
\begin{equation}
\lceil\log_2(n_1+1)\rceil+\lceil\log_2(n_2+1)\rceil+1.
\end{equation}
\tag{6.3}
$$
Поскольку числитель дробной части (равный либо $p$, либо $p'$) строго меньше знаменателя $n_1n_2$, он может быть сохранен в виде слова меньшей длины.
Аналогично, для любых двух целых чисел $K_1,K_2 \geqslant 1$ имеем, что
$$
\begin{equation*}
\lceil\log_2(K_1+K_2+2)\rceil \leqslant \log_2((K_1+1)(K_2+1))+1 \leqslant \log_2(K_1+1)+\log_2(K_2+1)+1.
\end{equation*}
\notag
$$
Для случая $0\leqslant K_1, K_2 \leqslant 1$ это неравенство также выполняется и легко проверяется. Таким образом, $\mathrm{K}$ гарантировано возможно хранить, задействовав не более $\lceil\log_2(K_1+1)\rceil+\lceil\log_2(K_2+1)\rceil+1$ символов. Добавим к этому один символ для хранения знака, два символа-разделителя и два слова длины (6.3), используемые для хранения дробной части, и таким образом убедимся, что $\mathrm x_3$ содержит не более $N$ символов, где
$$
\begin{equation*}
\begin{aligned} \, N&=\lceil\log_2(K_1+1)\rceil+\lceil\log_2(K_2+1)\rceil +2(\lceil\log_2(n_1+1)\rceil+\lceil\log_2(n_2+1)\rceil)+6 \\ &= \|\mathrm x_1\|+\|\mathrm x_2\|. \end{aligned}
\end{equation*}
\notag
$$
Таким образом, доказательство для случая $\mathrm s_1=\mathrm s_2=+$ завершено.
Если оба знака $s_1$ и $s_2$ отрицательны, то мы можем прибегнуть к всем тем же вычислениям, но определить $\mathrm x_3:=-\mathrm K/\mathrm p/\mathrm q$ (или $\mathrm x_3:= -\mathrm K/\mathrm p'/\mathrm q$ если $K'=1$). Ясно, что это не влияет на результат, время работы и оценку размера. Если же знаки $s_1$ и $s_2$ различаются, то вычисления все еще будут похожими на предыдущие случаи, за исключением того, что суммы заменяются разностями и потребуется чуть больше сравнений для получения целой части и знака. Тем не менее временная сложность все еще будет равна $O(T(\|\mathrm x_1\|+\|\mathrm x_2\|))$, и оценка размера будет ровно такая же, потому как знаменатель дробной части снова будет равен $n_1n_2$, а модуль целой части не превысит $|K_1|+|K_2|+1$. Лемма 6.5 доказана. Что касается сравнения рациональных чисел, сформулируем следующее утверждение. Лемма 6.6. Пусть $\mathrm x_1,\mathrm x_2 \in \operatorname{Num}_\mathbb Q$. Тогда мы можем определить, выполняется ли $\mathrm x_1 \equiv \mathrm x_2$, за время $O(T(\|\mathrm x_1\|+\|\mathrm x_2\|))$. Доказательство. Воспользовавшись обозначениями из леммы 6.5, получим, что данная лемма явным образом следует из проверки одного из равенств $K_1n_1+m_1=K_2n_2+m_2$ или $K_1n_1+m_1=-(K_2n_2+m_2)$. Лемма доказана.
Цитирование в формате AMSBIB
\RBibitem{TalHar23} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|