Журнал вычислительной математики и математической физики, 2021, T. 61, № 10, стр. 1610-1617

3.1. Полезная лемма

Лемма 1. Пусть $m$ – положительное целое, $L \in R[\sigma ]$. Пусть $\operatorname{ord} L \leqslant m$ и при этом $L({{\omega }_{m}}) = 0$. Тогда $dim{{V}_{L}} = \infty $.

Доказательство. Пусть $L$ имеет вид

Если $L({{\omega }_{m}}) = 0$, то для всех $n \in \mathbb{Z}$ имеем где ${{i}_{n}}$ – единственное $i \in \{ 0,1, \ldots ,m\} $ такое, что $n \equiv m - i(modm + 1)$. Таким образом, для всех $n \in \mathbb{Z}$ и $i \in \{ 0,1, \ldots ,m\} $ имеем Пусть теперь $c(n)$ – произвольная последовательность из $R$. Пусть $g(n) \in R$ – последовательность, для которой Множество (параметризованное последовательностью $c(n) \in R$) всех таких $g(n)$ является бесконечномерным подпространством $\mathbb{Q}$-линейного пространства $R$. Согласно (1) имеем и, следовательно, равенство $L(g) = 0$ для всех таких $g$ означает, что $\dim \ker L = \infty $.

Пример 1. Пусть $m = 2$. Тогда ${{\omega }_{2}}(3k) = {{\omega }_{2}}(3k + 1) = 0$, ${{\omega }_{2}}(3k + 2) = 1$ для всех $k \in \mathbb{Z}$. Если $L = {{a}_{2}}(n){{\sigma }^{2}} + {{a}_{1}}(n)\sigma + {{a}_{0}}(n)$ аннулирует ${{\omega }_{2}}(n)$, то

Оператор $L$ аннулирует, например, и любую последовательность ${{g}_{s}}(n)$ такую, что ${{g}_{s}}(3k) = {{g}_{s}}(3k + 1) = 0$, ${{g}_{s}}(3k + 2) = {{k}^{s}}$. Последовательности ${{g}_{s}}(n)$, $s = 0, \pm 1, \ldots $, линейно независимы над $\mathbb{Q}$.

3.2. Аннулирующие операторы

Предложение 1. Для любого положительного целого $m$ существуют такие ${{f}_{1}}, \ldots ,{{f}_{m}} \in R$, что если для некоторого $L \in R[\sigma ]$, $\operatorname{ord} L \leqslant m$ выполнено

то $dim{{V}_{L}} = \infty $.

Доказательство. Вследствие леммы 1 любые ${{f}_{1}}, \ldots ,{{f}_{m}} \in R$ с ${{f}_{1}} = {{\omega }_{m}}$ обладают указанным свойством.

В связи с этим напомним, что в дифференциальном случае можно всегда найти такой оператор $L$, $\operatorname{ord} L \leqslant m$, аннулирующий заданные ${{f}_{1}}, \ldots ,{{f}_{m}}$, что размерность пространства его решений равна числу линейно независимых элементов среди ${{f}_{1}}, \ldots ,{{f}_{m}}$.

Следующий пример иллюстрирует предложение 1 и показывает существование других (но схожих) путей нахождения ${{f}_{1}}, \ldots ,{{f}_{m}}$.

Пример 2. Рассмотрим последовательности ${{f}_{1}},\;{{f}_{2}}$, где

Если $L = a{{\sigma }^{2}} + b\sigma + c$ аннулирует ${{f}_{1}}$ и ${{f}_{2}}$, то Отсюда следует, что $L(y) = 0$ для любой последовательности $y$ такой, что выполняется $y(2),\;y(4k)$ играют роль произвольных постоянных.

Заметим, что лемма 1 может быть переформулирована в более сильной форме.

Лемма 1*. Существуют такие последовательности, что если оператор $L$ (на его порядок не накладывается никаких ограничений) аннулирует хотя бы одну из них, то $dim{{V}_{L}} = \infty $.

Доказательство. В самом деле, пусть последовательность $c$ такова, что $c(n) = 1$, если $n = {{k}^{2}}$ для некоторого целого $k$, и $c(n) = 1$ в противном случае. Использование той же самой идеи, что и в доказательсьтве леммы 1, позволяет установить, что если $L(c) = 0$ и при этом $\operatorname{ord} L = m$, то $L$ аннулирует, например, любую последовательность $d$, для которой неравенство $d(n) \ne 0$ влечет $n = {{k}^{2}},$ $k > \sqrt m $.

(Общее соображение таково: пусть $\nu $ является последовательностью положительных целых чисел $\nu (0),\;\nu (1),\; \ldots $, для которой $\nu (k + 1) - \nu (k) \to \infty $ при $k \to \infty $: например, $\nu (k) = {{k}^{2}}$ или $\nu (k) = {{2}^{k}}$. Определим последовательность c так: $c(n) = 1$, если ${{\exists }_{{k \geqslant 1}}}\left( {\left| n \right| = \nu (k)} \right)$, и $c(n) = 0$ в противном случае. Каждая последовательность такого рода состоит из единиц и нулей, и при этом расстояние между соседними единицами неограниченно возрастает. Легко заметить, что последовательности вида ${{\omega }_{m}}$ этим свойством не обладают.)

Соответственно и предложение 1 может быть усилено отказом от ограничения $\operatorname{ord} L \leqslant m$.

Пример 3. Пусть $r$ – произвольное неотрицательное целое. Последовательность ${{c}_{\nu }}$ из единиц и нулей, определенная с помощью последовательности $\nu $ так, как это описано выше, аннулируется, например, любым оператором порядка $r$ вида

где $a = 1 - {{c}_{\nu }}$ и ${{b}_{0}}, \ldots ,{{b}_{{r - 1}}} \in R$. (Старший коэффициент оператора – ненулевая последовательность.) Такого вида оператор аннулирует любую последовательность вида $g{{c}_{\nu }}$, $g \in R$.

Напомним, что в дифференциалом случае мы всегда можем найти такой оператор первого порядка, который аннулирует данный элемент $c$ исходного дифференциального поля, и пространство решений которого одномерно.

3.3. Наименьшее левое общее кратное

Определение 1. Определим для операторов ${{L}_{1}},{{L}_{2}} \in R[\sigma ]$ их наименьшее левое общее кратное ${\text{lclm}}({{L}_{1}},{{L}_{2}})$ как множество всех таких операторов $L \in R[\sigma ]$, что

• $L$ не есть нулевой оператор,

• $L$ является общим левым кратным для ${{L}_{1}}$ и ${{L}_{2}}$,

• не существует такого ненулевого оператора $M$, являющегося общим левым кратным для ${{L}_{1}}$ и ${{L}_{2}}$, для которого $\operatorname{ord} M < \operatorname{ord} L$.

Замечание 1. Для некоторых $L \in R[\sigma ]$ имеем $L \notin {\text{lclm}}(L,L)$. Например, пусть $L = a\sigma + 1$, где $a = {{\omega }_{1}}$. Если $f = \sigma (a)$, то $fa = 0$ и, таким образом, оператор $fL = fa\sigma + f = f$ является левым кратным для $L$. Так как $\operatorname{ord} f = 0$ является наименьшим возможным порядком ненулевого оператора, то $f \in {\text{lclm}}(L,L)$, но $L \notin {\text{lclm}}(L,L)$, так как $\operatorname{ord} L = 1$.

Заметим, что рассматриваемый оператор $L$ обратим в $R[\sigma ]$ и ${{L}^{{ - 1}}} = - a\sigma + 1$ в силу того, что $\sigma (a)a = a\sigma (a) = 0$. Отсюда $1 \in {\text{lclm}}(L,L)$.

Возможно также, что для двух заданных операторов ${{L}_{1}},{{L}_{2}} \in R[\sigma ]$ их единственным общим левым кратным служит $0$.

Пример 4. Рассмотрим два оператора нулевого порядка: ${{L}_{1}}$ – это последовательность $c(2k) = 0,\;c(2k + 1) = 1$, а ${{L}_{2}}$ – последовательность $d(2k) = 1,\;d(2k + 1) = 0$, $k = 0, \pm 1, \pm 2, \ldots $.

Единственным левым общим кратным будет нулевая последовательность. В самом деле, предположим, что ${{M}_{1}}{{L}_{1}} = {{M}_{2}}{{L}_{2}}$, где $i$-е слагаемое оператора ${{M}_{1}}$ имеет вид ${{a}_{i}}{{\sigma }^{i}}$, а $i$-е слагаемое оператора ${{M}_{2}}$, в свою очередь, – вид ${{b}_{i}}{{\sigma }^{i}}$, при этом ${{a}_{i}}$ и ${{b}_{i}}$ суть последовательности. Тогда $i$-е слагаемое произведения ${{M}_{1}}{{L}_{1}} = {{M}_{1}}c$ имеет вид ${{a}_{i}}({{\sigma }^{i}}c){{\sigma }^{i}} = {{a}_{i}}(n)c(n + i){{\sigma }^{i}}$, в то же время $i$-е слагаемое произведения ${{M}_{2}}{{L}_{2}} = {{M}_{2}}d$ имеет вид ${{b}_{i}}({{\sigma }^{i}}d){{\sigma }^{i}} = {{b}_{i}}(n)d(n + i)\sigma _{n}^{i}$. В точности одна из двух величин $c(n + i),\;d(n + i)$ равна нулю для любых $i$ и $n$. Если ${{M}_{1}}{{L}_{1}} = {{M}_{2}}{{L}_{2}}$, то ${{a}_{i}}(n)c(n + i) = {{b}_{i}}(n)d(n + i) = 0$ для всех $i$ и $n$, отсюда ${{a}_{i}}({{\sigma }^{i}}c) = {{b}_{i}}({{\sigma }^{i}}d)$ для всех $i$. Следовательно, ${{M}_{1}}{{L}_{1}} = {{M}_{2}}{{L}_{2}} = 0$.

Предложение 2. Найдутся такие операторы первого порядка ${{L}_{1}},\;{{L}_{2}}$, что

(i) $dim{{V}_{{{{L}_{1}}}}} = dim{{V}_{{{{L}_{2}}}}} = 1$,

(ii) существует левое общее кратное $L$ для ${{L}_{1}},\;{{L}_{2}}$, имеющее порядок $2$,

(iii) для любого такого левого общего кратного $A$ для ${{L}_{1}},\;{{L}_{2}}$, что $\operatorname{ord} A \leqslant 2$, выполнено $dim{{V}_{A}} = \infty $.

Доказательство. (i), (iii). Положим

где $b(3k) = 1$, $b(3k + 1) = b(3k + 2) = - 1$, $k = 0, \pm 1, \ldots $. Тогда пространства ${{V}_{{{{L}_{1}}}}},\;{{V}_{{{{L}_{2}}}}}$ одномерны: ${{V}_{{{{L}_{1}}}}}$ порождается последовательностью $s(n)$, для которой $s(3k) = s(3k + 1) = - 1$, $s(3k + 2) = 1$, в то же время ${{V}_{{{{L}_{2}}}}}$ порождается последовательностью $t(n)$, для которой $t(n) = 1$ при всех $n \in \mathbb{Z}$. Если ${{V}_{{{{L}_{1}}}}},{{V}_{{{{L}_{2}}}}} \subseteq {{V}_{A}}$ для некоторого оператора $A$, то ${{V}_{A}}$ содержит $f(n) = (s(n) + t(n)){\text{/}}2$. Для последовательности $f(n)$ имеем $f(3k) = f(3k + 1) = 0$, $f(3k + 2) = 1$. Из леммы 1 следует, что если $\operatorname{ord} A \leqslant 2$, то $dim{{V}_{A}} = \infty $. Итак, (i), (iii) доказаны.

(ii). Легко проверить, что

Очевидно, что левая и правая части равенства (3) являются ненулевыми общими кратными для ${{L}_{1}},{{L}_{2}}$.

Как следствие, операторы ${{L}_{1}},{{L}_{2}} \in R[\sigma ]$ могут быть такими, что пространства ${{V}_{{{{L}_{1}}}}},\;{{V}_{{{{L}_{2}}}}}$ конечномерны, но $dim{{V}_{L}} = \infty $ для $L \in {\text{lclm}}({{L}_{1}},{{L}_{2}})$.

Замечание 2. Равенство

в общем случае не выполняется. Можно при этом вспомнить, что в дифференциальном случае, когда ${{L}_{1}},\;{{L}_{2}}$ суть операторы над дифференциальным полем $\mathbb{K}$, равенство (4) выполнено при рассмoтрении решений, принадлежащих расширению Пикара–Вессио поля $\mathbb{K}$. Это верно также для случая дифференциальных систем (см. [8]). Равенство (4) имеет место и в скалярном разностном случае, когда коэффициенты принадлежат разностному полю, обладающему некоторыми специальными свойствами (см. [9]). Предложение 2 и, равным образом, его следствие о том, что равенство (4) в общем случае не выполняется, сохраняют свою силу, если рассматривать решения как последовательности с элементами, принадлежащими некоторому расширению поля $\mathbb{Q}$. В самом деле, ведущий и трейлинговый коэффициенты операторов (2) не обращаются в нуль и пространства решений операторов ${{L}_{1}}$ и ${{L}_{2}}$ одномерны. В то же время пространство решений оператора ${\text{lclm}}({{L}_{1}},{{L}_{2}})$ содерждит обсуждавшееся бесконечномерное пространство.

4.1. Следствие одного из классических результатов Тьюринга

Ниже мы доказываем неразрешимость некоторых алгоритмических задач, связанных с операторами, имеющими коэффициенты в $R$. Доказательства, главным образом, основаны на представленном ниже следствии одного из классических результатов Тьюринга о неразрешимости задачи проверки завершимости выполнения алгоритма (см. [10]):

Пусть $M$ – множество, содержащее, по крайней мере, два элемента, например, $0$ и $1$. В этой ситуации не существует алгоритма ответа на вопрос, является ли заданная алгоритмически последовательность с элементами, принадлежащими $M$ (односторонняя $c(0),\;c(1),\; \ldots $ или двусторонняя $ \ldots ,\;c( - 1),\;c(0),\;c(1),\; \ldots $), такой, что каждый ее элемент равен данному $v \in M$; то же самое – для случая последовательности, не имеющей ни одного равного $v$ элемента.

4.2. Проверка обратимости и делимости в $R[\sigma ]$

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

Лемма 2. Проверка для произвольной вычислимой последовательности $c \in R$ и неотрицательного целого $r$ истинности утверждения

является неразрешимой алгоритмической задачей.

Доказательство. Определим последовательность $a$: для $n \geqslant 0$ положим

Для $n < 0$ положим $a(n) = 0$. Вычислимость последовательности $c$ влечет вычислимость последовательности $a$. Последовательность $a$ такова, что отсутствие нулевых элементов среди имеет следствием ${{\forall }_{{k \in \mathbb{Z},n \geqslant kr - 1}}}(a(n)a(n + r) \ldots a(n + kr) \ne 0)$. Если $c(m) = 0$, $m \geqslant 0$, то $k \geqslant \left\lceil {\tfrac{m}{r}} \right\rceil $. Мы имеем так как произведение $a(n)a(n + kr)$ является нулевой последовательностью.

Таким образом, ${\mathbf{P}}(a,r)$ истинно, если и только если имеется хотя бы один нулевой элемент в (6).

Если некоторый алгоритм $\mathcal{A}$ позволял бы проверять истинность ${\mathbf{P}}$ для произвольной последовательности из $R$ и произвольного неотрицательного целого $r$, то с помощью этого алгоритма мы могли бы проверять наличие нулевого элемента в данной последовательности вида (6), применив $\mathcal{A}$ к последовательности

Последовательность (6) имеет нулевой элемент, если и только если истинно ${\mathbf{P}}(\tilde {c},r)$ (в качестве $r$ может быть взято любое неотрицательное целое). Но алгоритмическая проверка существования нулевых элементов в произвольной вычислимой последовательности невозможна (п. 1). Поэтому $\mathcal{A}$ не может существовать.

Предложение 3. Пусть $r$ – неотрицательное целое. Не существует алгоритма проверки для произвольного $L \in R[\sigma ]$, $\operatorname{ord} L = r$, является ли $L$ обратимым в $R[\sigma ]$.

Доказательство. Если $r = 0$, то $L$ – это последовательность из $R$. Эта последовательность обратима, если и только если в ней нет нулевых элементов. Не существует алгоритма проверки этого свойства.

Пусть $r > 0$. Рассмотрим множество операторов вида

где последовательность $c \in R$ такова, что $c(0) = 1$, и, следовательно, $c$ – ненулевая последовательность. Порядок каждого из $L$ вида (7) равен $r$. Если обратный ${{L}^{{ - 1}}}$ для $L$ существует, то существует и такое $k \geqslant 1$, что ${{L}^{{ - 1}}}$ имеет вид при Таким образом, $L$ вида (7) обратим, если и только если выполнено (9). Следовательно, если у нас есть алгоритм проверки обратимости, то мы можем воспользоваться им для проверки истинности (9). Но последнее, согласно лемме 2, является неразрешимой алгоритмической задачей.

Замечание 3. Пусть $r$ – неотрицательное целое. Тогда существует обратимый оператор порядка $r$ в $R[\sigma ]$. В самом деле, если $r = 0$, то ${\mathbf{1}} \cdot {\mathbf{1}} = {\mathbf{1}}$. Иначе, пусть $c(n) = {{\delta }_{0}}(n)$. Имеем $({\mathbf{1}} - c(n){{\sigma }^{r}})({\mathbf{1}} + c(n){{\sigma }^{r}}) = {\mathbf{1}}$.

Предложение 4. Пусть $r,s$ – неотрицательные целые. Не существует алгоритма проверки для произвольных ${{L}_{1}},{{L}_{2}} \in R[\sigma ]$, $\operatorname{ord} {{L}_{1}} = r$, $\operatorname{ord} {{L}_{2}} = s$, верно ли, что ${{L}_{1}}$ делится справа на ${{L}_{2}}$ в $R[\sigma ]$.

Доказательство. Если бы упомянутый алгоритм существовал, то мы могли бы использовать его для проверки обратимости данного оператора $L \in R[\sigma ]$ порядка $s$. В самом деле, возьмем любой оператор $M$ порядка $r$, например, положим $M = {{\sigma }^{r}}$. Очевидно, что $L$ обратим, если и только если $M$ и $M + 1$ оба делятся на $L$. Таким образом, если мы можем проверять делимость, то мы можем проверять и обратимость. Но, согласно предложению 3, последняя задача алгоритмически неразрешима.

4.3. О проверке существования ненулевого левого общего кратного

Обсудим задачу проверки существования ненулевого левого общего кратного для данных ${{L}_{1}},{{L}_{2}} \in R$.

Отметим, что отсутствие общего алгоритма проверки существования ненулевого левого общего кратного может быть доказано просто рассмотрением случая операторов нулевого порядка, т.е. случая последовательностей.

Предложение 5. Не существует алгоритма проверки существования ненулевого левого общего кратного для данных последовательностей $a,\;b$.

Доказательство. Во-первых, докажем, что не существует алгоритма проверки истинности утверждения

для данных вычислимых последовательностей $a,\;b$. В самом деле, если бы мы имели такой алгоритм, то он позволил бы нам алгоритмически проверять, является ли данная последовательность $a$ тождественно нулевой. (Такая проверка невозможна.) Мы можем взять $b = {\mathbf{1}}$, тогда (10) истинно, если и только если $a$ тождественно нулевая.

Мы можем теперь доказать, что задача проверки существования ненулевого левого общего кратного неразрешима алгоритмически уже в случае операторов нулевого порядка, т.е. когда операторы ${{L}_{1}},\;{{L}_{2}}$ суть некоторые последовательности $a$ и $b$. Видно, что $a$ и $b$ имеют ненулевое общее кратное, если и только если не выполняется (10). Фактически, доказательство отсутствия ненулевого левого общего кратного при выполнении (10) аналогично доказательству из примера 4. Если для некоторого $n$ произведение $a(n)b(n)$ не равно нулю, то последовательность $ab$ является ненулевым левым общим кратным.

Отсюда следует, что алгоритм проверки существования ненулевого левого общего кратного для произвольных данных операторов ${{L}_{1}}$, ${{L}_{2}}$ невозможен. Мы докажем более сильное утверждение.

Предложение 6. Пусть $r,\;s$ – неотрицательные целые. Тогда не существует алгоритма для проверки существования ненулевого левого общего кратного для произвольных данных операторов ${{L}_{1}},{{L}_{2}} \in R[\sigma ]$, $\operatorname{ord} {{L}_{1}} = r$, $\operatorname{ord} {{L}_{2}} = s$.

Доказательство основывается на следующей лемме.

Лемма 3. Пусть $a,b$ – ненулевые последовательности и $r,\;s$ – неотрицательные целые, $r \geqslant s$. Тогда $a{{\sigma }^{r}}$, $b{{\sigma }^{s}}$ обладают ненулевым общим кратным если и только если ($ \Leftrightarrow $) найдется такое целое $m$, что

Доказательство леммы 3. $ \Rightarrow $: Пусть $Ua{{\sigma }^{r}} = Wb{{\sigma }^{s}}$, где левая и правая части являются ненулевыми операторами. Пусть $u = \operatorname{ord} U$, $w = \operatorname{ord} W$. Можно считать, что

(в противном случае некоторые из старших слагаемых операторов $U,\;W$ могли бы быть удалены из операторов). В этом предположении пусть $c{{\sigma }^{u}}$ и $d{{\sigma }^{w}}$ служат старшими слагаемыми операторов $U$ и $W$. Ненулевые последовательности $c(n)a(n + u)$ и $d(n)b(n + w)$ одинаковы. Отсюда получаем, что равенство выполняется для всех $n$. В соответствии с (12), последнее равенство может быть записано как Поскольку левая и правая части последнего равенства суть ненулевые последовательности, существует такое целое $m$, что Отсюда $a(m) \ne 0,$ $b(m + s - t) \ne 0$.

$ \Leftarrow $: Если $m$ существует, то положим

$U = \tfrac{1}{{a(m)}}{{\delta }_{m}}(n)$, $W = \tfrac{1}{{b(m + r - s)}}{{\delta }_{m}}(n){{\sigma }^{{r - s}}}$.

Получаем

Доказательство предложения 6. Прежде всего, докажем следующее. Пусть $t$ – неотрицательное целое. Невозможен алгоритм ${{\mathcal{A}}_{t}}$ проверки для произвольных $a,b \in R$ существования такого $m \in \mathbb{Z}$, что $a(m)b(m + t) \ne 0$. Покажем, что если бы такой алгоритм ${{\mathcal{A}}_{t}}$ существовал, то мы могли бы с его помощью проверять, содержит ли произвольная вычислимая последовательность

хотя бы один ненулевой элемент. Но последняя алгоритмическая проблема неразрешима (см. п. 4.1), что будет означать невозможность ${{\mathcal{A}}_{t}}$.

Пусть последовательность $c$ такая же, как в (13). Определим двусторонние последовательности $a$ и $b$:

Тогда Как следствие, двусторонняя последовательность $a(n)b(n + t)$ содержит ненулевой элемент, если и только если односторонняя последовательность ${{c}^{2}}$ содержит ненулевой элемент. В свою очередь, последнее справедливо, если и только если односторонняя последовательность $c$ содержит ненулевой элемент.

Ненулевые последовательности $a,\;b$ вычислимы. Видно, что $m \in \mathbb{Z}$ такое, что $a(m)b(m + t) \ne 0$ существует, если и только если $c(m - 2) \ne 0$. Таким образом, если бы алгоритм ${{\mathcal{A}}_{t}}$ существовал, то для любой последовательности $c$ можно было бы проверить алгоритмически существование ненулевого элемента в $c$. Но эта проблема алгоритмически неразрешима, как это следует из утверждения п. 4.1. Отсюда следует, что алгоритм ${{\mathcal{A}}_{t}}$ не может существовать для каждого неотрицательного $t$. По лемме 3 это влечет справедливость предложения 4.