21.3 Модуль последовательностей над кольцом многочленов.

1. Если $f(x)=x^k$, то последовательность $v:=f(x)u=x^ku$ получается из последовательности $u$ сдвигом влево на $k$ членов, то есть для любого $i\in\mathbb{N}_0$ $v(i)=u(i+k)$.
2. Если $f(x)=\sum_{k\geq0}f_kx^k$, то $$v:=f(x)u:=\sum_{i\geq0}f_k(x^ku),$$ то есть $$\forall{i}\in\mathbb{N}_0\left(v(i):=\sum_{k\geq0}f_ku(i+k)\right),$$ где сложение последовательностей и умножение последовательности на элемент кольца определены в формулировке теоремы 21.1.

Утверждение 21.4:
Унитарный многочлен $F(x)\in{R}[x]$ является характерестическим многочленом последовательности $u\in{R}^{\infty}$ тогда и только тогда, когда $F(x)u=0$, то есть $$L_R(F)=\{u\in{R}^{\infty}\mid{F}(x)u=0\}.$$

Доказательство:

$\Rightarrow)$ Пусть $F(x):=x^m-c_{m-1}x^{m-1}-\cdots-c_1x-c_0$ характеристический многочлен последовательности $u$, тогда для любого $i\in\mathbb{N}_0$ $$ u(i+m)=c_{m-1}u(i+m-1)+\cdots+c_1u(i+1)+c_0u(i)\Rightarrow(F(x)u)(i)=\sum_{k\geq0}c_ku(i+k)=0, $$ где последнее равенство в силу того, что $c_m=1$ и для любого $k>m$ $c_k=0$.
$\Leftarrow)$ Пусть $F(x):=x^m+f_{m-1}x^{m-1}+\cdots+f_1x+f_0$, тогда для любого $i\in\mathbb{N}_0$ $$ \sum_{k\geq0}f_ku(i+k)=(F(x)u)(i)=0\Rightarrow{u}(i+m)=-f_{m-1}u(i+m-1)-\cdots-f_1u(i+1)-f_0u(i), $$ то есть $F(x)$ характеристический многочлен последовательности $u$.

Определение 21.11:
Будем говорить, что многочлен $A(x)\in{R}[x]$ аннулирует последовательность $u\in{R}^{\infty}$, если $A(x)u=0$.

Теорема 21.2:
Относительно введенной операции внешнего умножения абелева группа $(R^{\infty};+)$ является левым $R[x]$ модулем.

Доказательство:

Пусть $A(x),B(x)\in{R}[x]$, $u,v\in{R}^{\infty}$.

1. Очевидно, что $(A(x)+B(x))u=A(x)u+B(x)u$.
2. Очевидно, что $A(x)(u+v)=A(x)u+B(x)v$.
3. Очевидно, что $1u=u$.
4. Докажем, что $A(x)(B(x)u)=(A(x)B(x))u$.
   Очевидно, что для любых $k,l\in\mathbb{N}_0$, $a,b\in{R}$ $ax^k(bx^lu)=abx^{k+l}u$, тогда $$ (A(x)B(x))u=\left(\sum_{k,l}a_kb_lx^{k+l}\right)u=\sum_{k,l}a_kb_lx^{k+l}u=\sum_{k}\sum_{l}a_kx^kb_lx^lu=\sum_{k}a_kx^k\sum_{l}b_lx^lu=A(x)(B(x)u), $$ где последнее равенство справедливо в силу того, что многочлен имеет конечное число ненулевых коэффициентов, то есть суммы конечны.

Следствие 21.4:
Пусть $F(x)\in{R}[x]$ - унтарный многочлен, $u\in{L}_R(F)$, тогда

1. $A(x)u\in{L}_R(F)$,
2. для любого унитарного $G(x)\in{R}[x]$ $u\in{L}_R(FG)$,
3. множество $L_R(F)$ - подмодуль модулей ${}_{R}R^{\infty}$ и ${}_{R[x]}R^{\infty}$
4. множество $\alpha{R}^{\infty}$ всех ЛРП над $R$ является подмодулем модулей ${}_{R}R^{\infty}$ и ${}_{R[x]}R^{\infty}$.

Доказательство:

1. По теореме 21.2 $$ u\in{L}_R(F)\Rightarrow{F}(x)u=0\Rightarrow{A}(x)(F(x)u)=0\Rightarrow(A(x)F(x))u=0\Rightarrow (F(x)A(x))u=0\Rightarrow{F}(x)(A(x)u)=0\Rightarrow{A}(x)u\in{L}_R(F). $$
2. По теореме 21.2 $$ u\in{L}_R(F)\Rightarrow{F}(x)u=0\Rightarrow{G}(x)(F(x)u)=0\Rightarrow(G(x)F(x))u=0\Rightarrow{u}\in{L}_R(GF). $$
3. По п. 1 утверждения 21.1 $L_R(F)<{}_{R}R^{\infty}$.
   По пункту 1 $L_R(F)$ замкнуто относительно внешнего умножения на многочлен $f(x)\in{R}[x]$, следовательно, $L_R(F)<{}_{R[x]}R^{\infty}$.
4. Пусть $r\in{R}$, последовательности $u,v\in\alpha{L}_R^{\infty}$ такие, что $u\in{L}_R(F)$, $v\in{L}_R(G)$, тогда по пункту 2 $$u,v\in{L}_R(FG)\Rightarrow{u}+v\in{L}_R(FG)\Rightarrow{u}+v\in\alpha{R}^{\infty}.$$ При этом очевидно, что $ru\in{L}_R(F)$, таким образом, $\alpha{R}^{\infty}<{}_RR^{\infty}$.
   По пункту 1 множество $\alpha{R}^{\infty}$ замкнуто относительно операции внешнего умножения на многочлен, следовательно, $\alpha{R}^{\infty}<{}_{R[x]}R^{\infty}$.

Определение 21.12:
Пусть $F(x)\in{R}[x]$, $\deg{F}(x)=m$. Импульсной последовательностью с характеристическим многочленом $F(x)$ называется последовательность $e^F\in{L}_R(F)$ с начальным вектором $e^F(\overline{1,m-1})=(0,\ldots,0,e)$.

Определение 21.13:
Многочлены $A(x),B(x)\in{R}[x]$ называются взаимнопростыми, если существуют многочлены $U(x),V(x)\in{R}[x]$ такие, что $$A(x)U(x)+B(x)V(x)=e.$$

Теорема 21.3:
Пусть $F(x),G(x)\in{R}[x]$ - унитарные, $\deg{F(x)}=m$.

1. $L_R(F)\subset{L}_R(G)\Leftrightarrow{F}(x)|G(x)$.
2. Если $F(x),G(x)$ взаимнопросты, то $L_R(FG)=L_R(F)\dotplus{L}_R(G)$.

Доказательство:

1. $\Rightarrow)$ Разделим $G(x)$ на $F(x)$ c остатком, тогда $$\exists{Q}(x),r(x)\in{R}[x]:(G(x)=F(x)Q(x)+r(x)\,\wedge\,\deg{r(x)}<\deg{F(x)}).$$ Фиксируем $u\in{F}(x)$, так как $L_R(F)\subset{L}_R(G)$, то $u\in{G}(x)$ и по п. 2 следствия 21.3 $u\in{L}_R(FQ)$, тогда по утверждению 21.2 $$ (G(x)u=0\wedge(F(x)Q(x))u=0)\Rightarrow{v}:=r(x)u=(G(x)-F(x)Q(x))u=0. $$ Предположим что $0\leq{k}:=\deg{r(x)}<m$ и $r(x):=r_kx^k+\cdots+r_1x+r_0$, тогда $$ \forall{l}\in\overline{0,m-2}(e^F(l)=0)\Rightarrow{v}(m+k-1)=\sum_{l=0}^kr_le^F(m-k-1+l)=r_ke^F(m-1)=r_k=0. $$ Получено противоречие с предположением $0\leq{k}:=\deg{r(x)}$, то есть $\deg{r(x)}=-\infty$, $r(x)=0$, $F(x)|G(x)$.
   $\Leftarrow)$ Следует из п. 2 следствия 21.3
2. По п. 2 следствия 21.3 $L_R(F)\subset{L}_R(FG)$, $L_R(G)\subset{L}_R(FG)$. Следовательно, так как множество $L_R(FG)$ замкнуто относительно сложения, то $L_R(F)+L_R(G)\subset{L}_R(FG)$.
   С другой стороны, так как многочлены $F(x)$ и $G(x)$ взаимнопросты, то существуют $U(x),V(x)\in{R}[x]$ такие, что $F(x)U(x)+G(x)V(x)=e$. Фиксируем $u\in{L}_R(FG)$, тогда $u=eu=(F(x)U(x)+G(x)V(x))u$, при этом по утверждению 21.4 и по п. 1 следствия 21.3 $$ \begin{cases}G(x)((F(x)U(x))u)=U(x)((F(x)G(x))u)=0\Rightarrow (F(x)U(x))u\in{L}_R(G)\\F(x)((G(x)V(x))u)=V(x)((F(x)G(x))u)=0\Rightarrow(G(x)V(x))u\in{L}_R(F)\end{cases} $$ то есть ${u}\in{L}_R(F)+L_R(G)$. Таким образом, $L_R(F)+L_R(G)=L_R(FG)$, при этом по утверждению 21.4 и по п. 1 следствия 21.3 $$u\in{L}_R(F)\cap{L}_R(G)\Rightarrow{u}=(F(x)U(x)+G(x)V(x))u=0,$$ то есть сумма $L_R(F)+L_R(G)$ - прямая.

Теорема 21.4:
Пусть $P$ - поле, многочлены $F(x),G(x)\in{P}[x]$ унитарны, $D(x):=(F(x),G(x))$, $H(x):=[F(x),G(x)]$, тогда

1. $L_P(F)\cap{L}_P(G)=L_P(D)$,
2. $L_P(F)+L_P(G)=L_P(H)$.

Доказательство:

1. По лемме 7.4 существуют многочлены $U(x),V(x)\in{P}[x]$ такие, что $D(x)=F(x)U(x)+G(x)V(x)$, тогда по утверждению 21.4 и по п. 1 следствия 21.3 $$ u\in{L}_P(F)\cap{L}_P(G)\Rightarrow\begin{cases}F(x)u=0 \\ G(x)u=0\end{cases}\Rightarrow\begin{cases}(F(x)U(x))u=0 \\ (G(x)V(x))u=0\end{cases}\Rightarrow {D}(x)u=(F(x)U(x)+G(x)V(x))u=0\Rightarrow{u}\in{L}_P(D), $$ то есть $L_P(F)\cap{L}_P(G)\subset{L}_P(D)$. С другой стороны по п. 1 теоремы 21.3 $$ \begin{cases}D|F \\ D|G\end{cases}\Rightarrow \begin{cases}L_P(D)\subset{L}_P(F) \\ L_P(D)\subset{L}_P(G)\end{cases}\Rightarrow{L}_P(D)\subset{L}_P(F)\cap{L}_P(G). $$
2. По п. 1 теоремы 21.3 $$ \begin{cases}F|H \\ G|H\end{cases}\Rightarrow \begin{cases}L_P(F)\subset{L}_P(H) \\ {L}_P(G)\subset{L}_P(H)\end{cases}\Rightarrow{L}_P(F)+L_P(G)\subset{L}_P(H). $$ С другой стороны, по следствию 21.3, пункту 1, теореме 11.11, теореме 7.9, утверждению 11.6 $$ \dim(L_P(F)+L_P(G))=\dim{L_P(F)}+\dim{L_P(G)}-\dim{L_P(F)\cap{L}_P(G)}=\deg{F(x)}+\deg{G(x)}-\deg{D(x)}=\deg{H(x)}=\dim{L_P(H)}\Rightarrow\\ \Rightarrow{L}_P(F)+L_P(G)\cong{L}_P(H)\Rightarrow{L}_P(F)+L_P(G)=L_P(H). $$

Теорема 21.5:
Пусть многочлен $F(x)\in{R}[x]$ унитарен, $\deg{F(x)}=m$, тогда $L_R(F)$ - циклический $R[x]$-модуль порождаемый последовательностью $e^F$, при этом $$\forall{u}\in{L}_R(F)\exists!\Phi(x)\in{R}[x]:(u=\Phi(x)e^F\,\wedge\,\deg{\Phi(x)}<m)$$ и если $F(x)=x^m+f_{m-1}x^{m-1}+\cdots+f_1x+f_0$, то $$ \Phi(x)=\sum_{k=0}^{m-1}(f_mu(k)+f_{m-1}u(k-1)+\cdots+f_{m-k}u(0))x^{m-k-1}=u(0)x^{m-1}+\sum_{k=1}^{m-1}(u(k)+f_{m-1}u(k-1)+\cdots+f_{m-k}u(0))x^{m-k-1}. $$

Доказательство:

Матрица размера $m\times{m}$ составленная из начальных векторов последовательностей $e^F,xe^F,\ldots,x^{m-1}e^F$ имеет треугольный вид, тогда по п. 2 утверждения 21.3 система $e^F,xe^F,\ldots,x^{m-1}e^F$ является базисом $L_R(F)$. Тогда для любого $u\in{L}_P(F)$ существует единственный набор $\varphi_0,\ldots,\varphi_{m-1}\in{R}$ такой, что $$u=\varphi_0e^F+\varphi_1xe^F+\cdots+\varphi_{m-1}x^{m-1}e^F=(\varphi_0+\varphi_1x+\cdots+\varphi_{m-1}x^{m-1})e^F.$$ Следовательно, существует единственный многочлен $\Phi(x)\in{R}[x]$ такой, что $u=\Phi(x)e^F$ и $\deg{\Phi(x)}<m$.
Докажем, что многочлен $$\Phi(x)=u(0)x^{m-1}+\sum_{k=1}^{m-1}(u(k)+f_{m-1}u(k-1)+\cdots+f_{m-k}u(0))x^{m-k-1}$$ удовлетворяет условию $\Phi(x)e^F=u$. Обозначим $v:=\Phi(x)e^F\in{L}_P(F)$, тогда достаточно доказать, что для любого $i\in\overline{1,m-1}$ $v(i)=u(i)$. Фиксируем $i\in\overline{0,m-1}$, тогда $$ v(i)=(\Phi(x)e^F)(i)=\sum_{k=0}^{m-1}(f_mu(k)+\cdots+f_{m-k}u(0))e^F(i+m-k-1)= \sum_{k=0}^{m-1}\sum_{s=0}^kf_{m-k+s}u(s)e^F(i+m-k-1)=\sum_{s=0}^{m-1}\sum_{k=s}^{m-1}f_{m-k+s}u(s)e^F(i+m-k-1)=\\= \sum_{s=0}^{m-1}u(s)\sum_{k=s}^{m-1}f_{m-k+s}e^F(i+m-k-1)=\sum_{s=0}^{m-1}u(s)(f_{s+1}e^F(i)+f_{s+2}e^F(i+1)+\cdots+f_me^F(i+m-s-1)). $$

1. Если $s>i$, то $i<i+1<\ldots<i+m-s-1<m-1$, следовательно, $e^F(i)=\cdots=e^F(i+m-s-1)=0$ и $s$-тое слагаемое суммы равно 0.
2. Если $s=i$, то только $f_me^F(m-1)=1\neq0$ и $s$-тое слагаемое равно $u(i)$.
3. Если $s<i$, то $$ e^F(i-s-1)=\cdots=e^F(i-1)=0\Rightarrow\sum_{k=s}^{m-1}f_{m-k+s}e^F(i+m-k-1)=\sum_{k=0}^mf_ke^F(i+k-s-1)=(F(x)e^F)(i-s-1)=0 $$ где последнее равенство в силу того, что $F(x)e^F\in{L}_P(F)$.

Определение 21.14:
Если $F(x)=x^m+f_{m-1}x^{m-1}+\cdots+f_1x+f_0$, $u\in{L}_R(F)$, то многочлен $$\Phi(x):=\sum_{k=0}^{m-1}(u(k)+f_{m-1}u(k-1)+\cdots+f_{m-k}u(0))x^{m-k-1}$$ называется генератором линейной рекуррентной последовательности $u$ относительно характеристического многочлена $F(x)$.

previous contents next