Определение 21.20:
Последовательность $u\in\Omega^{\infty}$ называется периодической, если
$$\exists{t}\in\mathbb{N}\,\lambda\in\mathbb{N}_0:\forall{i}\geq\lambda(u(i+t)=u(i)).$$
Наименьшее $t\in\mathbb{N}$ такое, что
$$\exists\lambda\in\mathbb{N}_0:\forall{i}\geq\lambda(u(i+t)=u(i))$$
называется периодом последовательности $u$ и обозначается $T(u)$.
Наименьшее $\lambda\in\mathbb{N}_0$ такое, что
$$\exists{t}\in\mathbb{N}:\forall{i}\geq\lambda(u(i+t)=u(i))$$
называется подходом последовательности $u$ и обозначается $\Lambda(u)$.
Теорема 21.10:
Пусть $u\in\Omega^{\infty}$ - периодическая последовательность, ${t\in\mathbb{N}}$, $\lambda\in\mathbb{N}_0$,
тогда $u(i+t)=u(i)$ для любого $i\geq\lambda$ тогда и только тогда, когда $\lambda\geq\Lambda(u)$ и $T(u)|t$.
Доказательство:
$\Rightarrow)$ Пусть для любого $i\geq\lambda$ $u(i+t)=u(i)$, тогда по определению периода и подхода $\lambda\geq\Lambda(u)$, $t\geq{T}(u)$.
Разделим $t$ на $T(u)$ с остатком, тогда
$$\exists{q},r\in\mathbb{N}_0:(t=T(u)q+r\,\wedge\,0\leq{r}<T(u)).$$
По определению $T(u)$
$$\exists\lambda_0\in\mathbb{N}_0:\forall{i}\geq\lambda_0(u(i+T(u))=u(i)),$$
тогда для любого $i\geq\max\{\lambda,\lambda_0\}$
$$
u(i)=u(i+t)=u(i+T(u)q+r)=u(i+r)\Rightarrow{r}=0\Rightarrow{T}(u)|t.
$$
$\Leftarrow)$ По определению периода и подхода
$$\exists\lambda_0\in\mathbb{N}_0:\forall{i}\geq\lambda_0(u(i+T(u))=u(i)),$$
$$\exists{t}_0\in\mathbb{N}:\forall{i}\geq\Lambda(u)(u(i+t_0)=u(i)).$$
Существует $k\in\mathbb{N}_0$ такое, что $kt_0\geq\lambda_0$, следовательно
$$
\forall{i}\geq\Lambda(u)(u(i)=u(i+kt_0)=u(i+kt_0+T(u))=u(i+T(u)))\Rightarrow
\forall{i}\geq\Lambda(u)\left(u(i)=u\left(i+\frac{t}{T(u)}T(u)\right)=u(i+t)\right)\Rightarrow\forall{i}\geq\lambda(u(i)=u(i+t)).
$$
Везде далее будем рассматривать периодические последовательности над коммутативным кольцом $R$ с единицей $e$.
Утверждение 21.12:
Всякая периодическая последовательность над коммутативным кольцом с единицей является линейной рекуррентной последовательностью.
Если кольцо конечно, то верно и обратное.
Доказательство:
$\Rightarrow)$ Если последовательность $u\in{R}^{\infty}$ переодическая, то
$$\exists\lambda\in\mathbb{N}_0\,t\in\mathbb{N}:\forall{i}\geq\lambda(u(i+t)=u(i))\Leftrightarrow
(x^{\lambda+t}-x^{\lambda})u=0\Leftrightarrow{u}\in{L}_P\bigl(x^{\lambda}(x^t-e)\bigr).$$
$\Leftarrow)$ Пусть кольцо $R$ конечно, $u\in{L}_R(F)$. Будет доказано позднее (см. следствие 21.10).
Утверждение 21.13:
Пусть $u,v\in{R}^{\infty}$ периодические последовательности, тогда $w:=u+v$ - периодическая последовательность такая,
что $\Lambda(w)\leq\max\{\Lambda(u),\Lambda(v)\}$, $T(w)\bigl|[T(u),T(v)]$, при этом
Доказательство:
Обозначим $\lambda=\max\{\Lambda(u),\Lambda(v)\}$, $t=[T(u),T(v)]$, тогда по теореме 21.10 и
утверждению 21.12
$$
\begin{cases}x^{\lambda}(x^t-e)u=0 \\ x^{\lambda}(x^t-e)v=0\end{cases}\Rightarrow{x}^{\lambda}(x^t-e)w=0\Rightarrow(\Lambda(w)\leq\lambda\,\wedge\,T(w)|t)
$$
Определение 21.21:
Последовательность $u$ является чисто периодической или реверсивной, если $\Lambda(u)=0$ и вырожденной если для любого $i\geq\Lambda(u)$ $u(i)=0$.
Утверждение 21.14:
Любая периодическая последовательность $u$ представима в виде суммы $u=u_0+u_1$, где $u_0$ - вырожденная последовательность,
$u_1$ - чисто периодическая последовательность при этом такое представление однозначно и $\Lambda(u)=\Lambda(u_0)$, $T(u)=T(u_1)$.
Доказательство:
Обозначим $\lambda:=\Lambda(u)$, $t:=T(u)$, тогда по утверждению 21.12
$u\in{L}_R\bigl(x^{\lambda}(x^t-e)\bigr)$.
Для многочленов над коммутативным кольцом аналогичным образом можно доказать утверждение подобное утверждению
п. 3 теоремы 7.8. Тогда из очевидного соотношения $(x,x^t-e)=e$ следует, что $(x^{\lambda},x^t-e)=e$.
Тогда по п. 3 теоремы 21.3
$$L_R\bigl(x^{\lambda}(x^t-e)\bigr)=L_R\bigl(x^{\lambda}\bigr)\dotplus{L}_R\bigl(x^t-e\bigr).$$
Так как все последовательности из $L_R\bigl(x^{\lambda}\bigr)$ вырожденные, а из $L_R\bigl(x^t-e\bigr)$ чисто периодические,
то существование разложения $u$ в сумму вырожденной и чисто периодической последовательности доказано. Докажем единственность такого разложения.
Для любых $u_0$, $u_1$ таких, что $u_0$ вырожденная, а $u_1$ чисто периодическая и $u=u_0+u_1$
$$\lambda:=\Lambda(u)=\max\{\Lambda(u_0),\Lambda(u_1)\}=\max\{\Lambda(u_0),0\}=\Lambda(u_0),$$
$$t:=T(u)=[T(u_0),T(u_1)]=[1,T(u_1)]=T(u_1),$$
следовательно, $u_0\in{L}_R\bigl(x^{\lambda}\bigr)$ и $u_1\in{L}_R\bigl(x^t-e\bigr)$.
Тогда, так как сумма $L_R\bigl(x^{\lambda}\bigr)\dotplus{L}_R\bigl(x^t-e\bigr)$ прямая, то $u_0$ и $u_1$ определены однозначно.
Определение 21.22:
Многочлен $F(x)\in{R}[x]$ называется периодическим, если
$$\exists\lambda\in\mathbb{N}_0\,t\in\mathbb{N}:F(x)|x^{\lambda}(x^t-1).$$
Наименьшее $t\in\mathbb{N}$ для которого существует $\lambda\in\mathbb{N}_0$ такое,
что $F(x)|x^{\lambda}(x^t-1)$ называестя периодом многочлена $F(x)$ и обозначается $T(F)$.
Наименьшее $\lambda\in\mathbb{N}_0$ для которого существует $t\in\mathbb{N}$ такое,
что $F(x)|x^{\lambda}(x^t-1)$ называестя длиной подхода многочлена $F(x)$ и обозначается $\Lambda(F)$.
Утверждение 21.15:
Пусть многочлен $F(x)\in{R}[x]$ унитарный.
Доказательство:
Утверждение 21.16:
Если $F(x),G(x)\in{R}[x]$ - периодические, унитарные, взаимнопростые многочлены,
то многочлен $H(x):=F(x)G(x)$ является периодическим и $\Lambda(H)=\max\{\Lambda(F),\Lambda(G)\}$, $T(H)=T(F)T(G)$.
Доказательство:
По п. 2 утверждения 21.15
$$
H(x)|x^{\lambda}(x^t-1)\Leftrightarrow\begin{cases}F(x)|x^{\lambda}(x^t-1) \\ G(x)|x^{\lambda}(x^t-1)\end{cases}\Leftrightarrow
\begin{cases}\lambda\geq\Lambda(F)\wedge{T}(F)|t \\ \lambda\geq\Lambda(G)\wedge{T}(G)|t\end{cases}\Leftrightarrow
\begin{cases}\lambda\geq\max\{\Lambda(F),\Lambda(G)\} \\ [T(F),T(G)]\bigl|t\end{cases}\Leftrightarrow
\begin{cases}\Lambda(H)=\max\{\Lambda(F),\Lambda(G)\} \\ T(H)=[T(F),T(G)]\end{cases}
$$
Следствие 21.9:
Если $F(x),G(x)\in{R}[x]$ периодические унитарные многочлены, $F(x)|G(x)$, то $\Lambda(F)\leq\Lambda(G)$, $T(F)|T(G)$.
Доказательство:
По п. 2 утверждения 21.15
$$G(x)|x^{\Lambda(G)}(x^{T(G)}-1)\Rightarrow{F}(x)|x^{\Lambda(G)}(x^{T(G)}-1)\Rightarrow(\Lambda(F)\leq\Lambda(G)\wedge{T}(F)|T(G)).$$
Теорема 21.11:
Пусть $R$ - конечное кольцо, $F(x)\in{R}[x]$ - унитарный многочлен, $m:=\deg{F(x)}$, тогда многочлен $F(x)$ периодический и если $|R|^m>2$,
то $\Lambda(F)+T(F)<|R|^m$.
Доказательство:
Рассмотрим кольцо вычетов $S:=R[x]/F(x)$. Так как кольцо $R$ конечно, то $|S|=|R|^m$, то есть последовательность
$$[e]_{F(x)},[x]_{F(x)},[x^2]_{F(x)},\ldots,[x^i]_{F(x)},\ldots$$
конечна. Следовательно, существуют $\lambda\in\mathbb{N}_0$, $t\in\mathbb{N}$ такие, что $t+\lambda\leq|R|^m$ и
$$[x^{\lambda}]_{F(x)}=[x^{\lambda+t}]_{F(x)}\Leftrightarrow[x^{\lambda+t}-x^{\lambda}]_{F(x)}=0\Leftrightarrow{F}(x)|x^{\lambda}(x^t-e),$$
то есть, многочлен $F(x)$ периодический и $\Lambda(F)+T(F)\leq\lambda+t\leq|R|^m$. Докажем от противного, что если $|R|^m>2$,
то $\Lambda(F)+T(F)<|R|^m$. Обозначим $k:=|R|^m$ и предположим, что
$\Lambda(F)+T(F)=k>2$, тогда вычеты
$$[e]_{F(x)},[x]_{F(x)},\ldots,[x^{k-1}]_{F(x)}$$
все различны, то есть
$$S=\{[e]_{F(x)},[x]_{F(x)},\ldots,[x^{k-1}]_{F(x)}\}.$$
Так как $0\in{S}$, то существует $i\in\overline{1,k-1}$ такое, что $[x^i]=0$, тогда $[x]$ - делитель нуля и для любого $i\in\overline{1,k-1}$ $[x^i]$ -
делитель нуля, то есть в $S$ только один обратимый элемент. Так как для любого
$i\in\overline{1,k-2}$ $[x^i]\neq0$, иначе $[x^{i+1}]=[x^i][x]=0=[x^i]$, то $[x^{k-1}]=0$. Тогда
$$[e-x]_{F(x)}[e+x+\cdots+x^{k-2}]_{F(x)}=[e-x^{k-1}]_{F(x)}=[e]_{F(x)}.$$
Следовательно, $[e-x]$ обратим и в силу единственности обратимого
$$[e-x]_{F(x)}=[e]_{F(x)}\Rightarrow[x]_{F(x)}=0\Rightarrow{S}=\{[0]_{F(x)},[e]_{F(x)}\}\Rightarrow|S|=|R|^m=2.$$
Таким образом, получено противоречие с предпосылкой $|R^m|>2$.
Следствие 21.10:
Если $R$ - конечное кольцо, $u$ - линейная рекуррентная последовательность над $R$ порядка $m$,
то $u$ - периодическая последовательность и если $|R^m|>2$, $\Lambda(u)+T(u)<|R|^m$.
Доказательство:
Пусть $u\in{L}_R(F)$, тогда по теореме 21.11 многочлен $F(x)$ периодический,
тогда по утверждению 21.15 последовательность $u$ периодическая и
$\Lambda(u)\leq{L}(F)$, $T(u)\leq{T}(F)$. Тогда по теореме 21.11 если $|R|^m>2$, то
$$\Lambda(u)+T(u)\leq\Lambda(F)+T(F)<|R|^m$$
Пример 21.13:
Пусть $R:=GF(2)$, $m=1$, тогда $|R|^m=2$ и условие
$$\Lambda(F)+T(F)<|R|^m$$
может не выполнятся. Например, при $F(x)=x$
$$\Lambda(F)+T(F)=1+1=2=|R|^m,$$
а при $F(x)=x+1$
$$\Lambda(F)+T(F)=0+1=1<|R|^m.$$
Определение 21.23:
Если кольцо $R$ конечно, многочлен $F(x)\in{R}[x]$ унитарный и $F(0)\in{R}^*$, то многочлен $F(x)$ называется регулярным или реверсивным.
Утверждение 21.17:
Пусть $R$ - конечное кольцо, многочлен $F(x)\in{R}[x]$ унитарен, тогда
$$\Lambda(F)=0\Leftrightarrow{F}(0)\in{R}^*.$$
Доказательство:
Так как кольцо $R$ конечно, то по теореме 21.11 многочлен $F(x)$ периодичный, то есть
$$\exists\lambda\in\mathbb{N}_0,t\in\mathbb{N}:F(x)|x^{\lambda}(x^t-e).$$
$\Rightarrow)$
$$
\Lambda(F)=0\Rightarrow{F}(x)|x^t-e\Rightarrow\exists{G}(x)\in{R}[x]:F(x)G(x)=x^t-e\Rightarrow{F}(0)G(0)=e\Rightarrow{F}(0)\in{R}^*.
$$
$\Leftarrow)$
$$
\exists{U}(x)\in{R}(x):F(x)=F(0)+xU(x)\Leftrightarrow{F}(x)-xU(x)=F(0)
$$
Так как $F(0)\in{R}^*$, то последнее равенство можно умножить на $F(0)^{-1}$, тогда
$$(F(x),x)=e\Rightarrow(F(x),x^{\lambda})=e\Rightarrow{F}(x)|x^t-e\Rightarrow\Lambda(F)=0.$$
previous contents next