線形回帰数列

要点：$(qg)(E)=q(E)g(E)$ からイデアルであることが従い、$0$ でない元を最高次の係数で割ると漸化式が得られる。$K[x]$ が単項イデアル整域であることから生成元がとれる。

写像 $\Phi\colon K[x]\to K^{\mathbb N}$ を $\Phi(g):=g(E)a$ で定める。$\Phi$ は線形であり、$\Phi(x^j)=E^ja$ なので像はちょうど $V_a$ である。核は定義により $\operatorname{Ann}(a)$ である。
$V_a$ が有限次元で $\dim V_a=r$ とすると、$r+1$ 個の元 $a,Ea,\dots,E^ra$ は線形従属なので、すべては $0$ でない $b_0,\dots,b_r\in K$ で $\sum_jb_jE^ja=0$ となる。すなわち $0$ でない多項式 $\sum_jb_jx^j$ が $\operatorname{Ann}(a)$ に属し、prop-lrs-ideal の 2 により $a$ は線形回帰数列である。
逆に $a$ が線形回帰数列で $d=\deg\mu_a$ とする。$\operatorname{Ann}(a)=(\mu_a)$ なので、$\Phi$ は線形同型 $K[x]/(\mu_a)\to V_a$ を引き起こす。多項式の割り算により、すべての $g\in K[x]$ は $g=q\mu_a+r$（$\deg r< d$ または $r=0$）とただ 1 通りに書けるので、$1,x,\dots,x^{d-1}$ の類は $K[x]/(\mu_a)$ の基底である。その像 $a,Ea,\dots,E^{d-1}a$ は $V_a$ の基底であり、$\dim V_a=d$ である。$\square$

1：$f^*(x)=\sum_{i=0}^kq_ix^i$（$q_0=1$、$q_i=-c_i$）と書くと、$f^*(x)A(x)$ の $x^m$ の係数は $\sum_{i=0}^{\min(m,k)}q_ia_{m-i}$ である。$m\ge k$ ではこれは $a_m-c_1a_{m-1}-\cdots-c_ka_{m-k}=(f(E)a)_{m-k}$ に等しい。よって $f^*A$ の $x^k,x^{k+1},\dots$ の係数がすべて $0$ であることと、すべての $n\ge0$ で $(f(E)a)_n=0$ であることは同値である。
2：$a$ が漸化式を満たし、その特性多項式が $f$ なら、1 により $P:=f^*A$ は多項式であり、$Q:=f^*$ は $Q(0)=1$ を満たす。$Q$ は定数項が $K$ の単元なので $K[\![x]\!]$ の単元であり（形式的冪級数 の命題「定数項による単元判定」）、$A=P/Q$ である。
逆に $A=P/Q$、$Q(0)\ne0$ とする。$P=0$ なら $a=0$ で、これは $0$ 階の漸化式を満たす。$P\ne0$ とし、$Q$ を $Q(0)$ で割って $Q(0)=1$ としてよい。$Q(x)=1+q_1x+\cdots+q_ex^e$（$e=\deg Q$）と書き、$k:=\max\{e,\deg P+1\}$ とおくと、$f(x):=x^kQ(1/x)=x^k+q_1x^{k-1}+\cdots+q_ex^{k-e}$ は $k$ 次のモニック多項式で、$f^*=Q$ である。$f^*A=P$ の次数は $k$ 未満なので、1 により $f(E)a=0$ である。$\square$

$a$ が $k$ 階の漸化式を満たすとする（$k=0$ なら $a=0$ で、$k=1$、$u=0$ とすればよい）。$s_n:=(a_n,a_{n+1},\dots,a_{n+k-1})^{\top}$ とおき、
$$ C:=\begin{pmatrix}0&1&0&\cdots&0\\0&0&1&\cdots&0\\\vdots&&&\ddots&\vdots\\0&0&0&\cdots&1\\c_k&c_{k-1}&c_{k-2}&\cdots&c_1\end{pmatrix} $$
とすると、漸化式は $s_{n+1}=Cs_n$ を意味する（最後の成分が $a_{n+k}=c_ka_n+\cdots+c_1a_{n+k-1}$）。よって $s_n=C^ns_0$ であり、$e_1:=(1,0,\dots,0)^{\top}$ について $a_n=e_1^{\top}C^ns_0$ である。
逆に $a_n=u^{\top}M^nv$ とし、$M$ の固有多項式を $\chi_M(x)=x^k+b_1x^{k-1}+\cdots+b_k$ とする。Cayley–Hamiltonの定理 により $\chi_M(M)=O$ なので、すべての $n\ge0$ で
$$ a_{n+k}+b_1a_{n+k-1}+\cdots+b_ka_n=u^{\top}M^n\chi_M(M)v=0 $$
である。これは $a$ が特性多項式 $\chi_M$ の $k$ 階の漸化式を満たすことを意味する。$\square$

thm-lrs-finite-dim を使う。$E^j(a+b)=E^ja+E^jb$ なので $V_{a+b}\subset V_a+V_b$ であり、$\dim V_{a+b}\le d+e$ である。$\lambda a$ と $Ea$ については $V_{\lambda a}\subset V_a$、$V_{Ea}\subset V_a$ である。
項ごとの積：$u_1,\dots,u_d$ を $V_a$ の基底、$w_1,\dots,w_e$ を $V_b$ の基底とし、$de$ 個の数列 $u_iw_l$（項ごとの積）の張る空間を $W$ とする。$E$ は項ごとの積を保つ（$E(uw)=(Eu)(Ew)$）ので、$E^j(ab)=(E^ja)(E^jb)$ である。$E^ja=\sum_i\alpha_iu_i$、$E^jb=\sum_l\beta_lw_l$ と書けば $E^j(ab)=\sum_{i,l}\alpha_i\beta_lu_iw_l\in W$ である。よって $V_{ab}\subset W$、$\dim V_{ab}\le de$ である。
畳み込み：$a,b$ の最小多項式を $f,g$ とすると、thm-lrs-rational の 1 により $f^*A=P_1$、$g^*B=P_2$ で、$\deg P_1< d$、$\deg P_2< e$（または $0$）である。$h:=fg$ は $d+e$ 次のモニック多項式で、$h^*=f^*g^*$ である。$h^*\cdot AB=P_1P_2$ の次数は $d+e-2$ 以下なので、ふたたび thm-lrs-rational の 1 により $h(E)(a\star b)=0$ である。$\square$

$\mathbb Z/m\mathbb Z$ の元を成分とする長さ $k$ の組の集合を $S:=(\mathbb Z/m\mathbb Z)^k$ とし、$s_n:=(a_n,a_{n+1},\dots,a_{n+k-1})\bmod m\in S$ とおく。写像 $\tau\colon S\to S$ を
$$ \tau(y_1,\dots,y_k):=(y_2,\dots,y_k,\ c_ky_1+c_{k-1}y_2+\cdots+c_1y_k) $$
で定めると、漸化式から $s_{n+1}=\tau(s_n)$ である。
1：$S$ の元は $m^k$ 個なので、$m^k+1$ 個の $s_0,s_1,\dots,s_{m^k}$ のうち 2 つは等しい（鳩の巣原理）。$s_i=s_j$（$0\le i< j\le m^k$）とし、$n_0:=i$、$T:=j-i$ とおく。$s_{n+1}=\tau(s_n)$ により $r\ge0$ について帰納的に $s_{i+r}=s_{j+r}$ であり、第 1 成分を比べると $n\ge n_0$ で $a_{n+T}\equiv a_n\pmod m$ である。$n_0+T=j\le m^k$ である。
2：$c_k$ が $m$ と互いに素なら、$c_kc'\equiv1\pmod m$ となる整数 $c'$ がある（合同式）。$\tau(y)=\tau(y')$ なら $y_2=y'_2,\dots,y_k=y'_k$ で、最後の成分から $c_ky_1=c_ky'_1$、両辺に $c'$ を掛けて $y_1=y'_1$ である。よって $\tau$ は単射であり、有限集合からそれ自身への単射なので全単射である（鳩の巣原理 の命題「同じ個数の有限集合の間の写像」）。1 の $s_i=s_j$ に $\tau^{-1}$ を $i$ 回施すと $s_0=s_{T}$ となり、同じ帰納法ですべての $n\ge0$ で $a_{n+T}\equiv a_n\pmod m$ である。$\square$

1：$M_n:=\max\{\lvert a_n\rvert,\dots,\lvert a_{n+k-1}\rvert\}$ とおく。$\lvert a_{n+k}\rvert\le\sum_i\lvert c_i\rvert\lvert a_{n+k-i}\rvert\le RM_n$ であり、$R\ge1$ なので $M_{n+1}\le\max\{M_n,RM_n\}=RM_n$ である。よって $M_n\le R^nM_0=C_0R^n$ であり、$\lvert a_n\rvert\le M_n$ である。
2：$a_m,\dots,a_{m+k-1}$ が $0$ なら、漸化式から $a_{m+k}=0$ であり、$k$ 個ずつずらして帰納的にすべての $n\ge m$ で $a_n=0$ である。$\square$