超幾何数列の基礎7：望遠鏡和による簡約化

　有理関数$r(n)$に対し 第二回の記事 の補題3から
\begin{align} r(n)&=\frac{a(n)}{b(n)}\frac{c(n+1)}{c(n)}\\ \frac{b(n)}{a(n)}&=\frac{b'(n)}{a'(n)}\frac{c'(n+1)}{c'(n)} \end{align}
なる多項式$a,b,c,a',b',c'$であって、任意の非負整数$h$に対し
$$\gcd(a(n),b(n+h))=\gcd(a'(n+h),b'(n))=1$$
を満たすようなものが取れる。
　このときその構成法から$a',b'$はそれぞれ$a,b$を割り切るので
$$\gcd(a'(n),b'(n+h))=\gcd(a'(n),b'(n-h))=1$$
が成り立つ、つまり$a'(n)/b'(n)$はshift-reducedとなるので
$$K(n)=\frac{a'(n)}{b'(n)},\quad S(n)=\frac{c(n)}{c'(n)}$$
とおくとこれは$r(n)$の標準形を定めることがわかる。

　$v(n)$がある既約多項式の累乗$b(n)^k$を因数に持つとき、ある整数$h$が存在して$v_2(n)$も$b(n+h)^k$を因数に持つことを示す。$b(n)^k\mid v_2(n)$のときは明らかなので$b(n)^k\nmid v_2(n)$としてよい。
　このとき$K(n)=p(n)/q(n)$に関する$T_1(n)$の殻を$S_1(n)=u_1(n)/v_1(n)$とおくと
$$\frac{u(n)}{v(n)} =\frac{p(n)}{q(n)}\frac{u_1(n+1)}{v_1(n+1)}-\frac{u_1(n)}{v_1(n)}+\frac{u_2(n)}{v_2(n)}$$
が成り立つので、この分母に注目すると
$$b(n)^k\mid v_1(n+1)\quad\mbox{または}\quad b(n)^k\mid v_1(n)$$
がわかる。

$b(n)^k\mid v_1(n+1)$のとき

　$h$を$b(n+h)^k\mid v_1(n)$を満たすような整数であって最小のものとする(仮定より$h\leq-1$に注意する)。このとき$h$の最小性から
$$b(n+h)^k\nmid v_1(n+1)$$
となるので再び上の分母に注目することで
$$b(n+h)^k\mid v_2(n)$$
がわかる。

$b(n)^k\mid v_1(n)$のとき

　$h$を$b(n+h)^k\mid v_1(n+1)$を満たすような整数であって最大のものとする(仮定より$h\leq1$に注意する)。このとき$h$の最大性から
$$b(n+h)^k\nmid v_1(n)$$
となるので再び上の分母に注目することで
$$b(n+h)^k\mid v_2(n)$$
がわかる($b(n+h)\nmid p(n)$に注意する)。
　以上よりどちらの場合にもある整数$h$が存在して$b(n+h)^k\mid v_2(n)$が成り立つことが示された。

　$S(n)$を適当に 部分分数分解 することで、まず$S(n)$がある既約多項式$b(n)$を用いて
$$S(n)=\frac{a(n)}{b(n)^k}$$
と表せる場合を考える。このとき以下の三通りの場合が考えられる($K(n)$の取り方から(1)と(2)は同時には起こらないことに注意する)。
(1) ある非負整数$h$に対し$b(n)\mid q(n+h)$が成り立つ
(2) ある非負整数$h$に対し$b(n)\mid p(n-h)$が成り立つ
(3) 任意の非負整数$h$に対し$b(n)$は$p(n-h)$も$q(n+h)$も割り切らない

(1)の場合

$$S'_1(n+1)=\frac1{K(n)}\frac{a(n)}{b(n)^k}$$
とおくとある非負整数$l\leq k$およびある多項式$c_0,c_1$が存在して
\begin{align} S(n) &=K(n)S'_1(n+1)-S'_1(n)+\frac{q(n-1)a(n-1)}{p(n-1)b(n-1)^k}\\ &=K(n)S'_1(n+1)-S'_1(n)+\l(\frac{c_0(n)}{b(n-1)^l}+\frac{c_1(n)}{p(n-1)}\r) \end{align}
が成り立つ。このときさらに
$$S''_1(n)=S'_1(n)-\frac{c_1(n)}{p(n-1)}$$
とおくと
$$S(n)=K(n)S''_1(n+1)-S''_1(n)+\l(\frac{c_0(n)}{b(n-1)^l}+\frac{c_1(n+1)}{q(n)}\r)$$
が成り立つ。
　また
$$S'(n)=\frac{c_0(n)}{b(n-1)^l}$$
に対して同様の操作を繰り返していくことで(3)の場合に帰着できる。

(2)の場合

$$S'_1(n)=-\frac{a(n)}{b(n)^k}$$
とおくとある非負整数$l\leq k$およびある多項式$c_0,c_1$が存在して
\begin{align} S(n) &=K(n)S'_1(n+1)-S'_1(n)+\frac{p(n)a(n+1)}{q(n)b(n+1)^k}\\ &=K(n)S'_1(n+1)-S'_1(n)+\l(\frac{c_0(n)}{b(n+1)^l}+\frac{c_1(n)}{q(n)}\r) \end{align}
が成り立つ。
　また
$$S'(n)=\frac{c_0(n)}{b(n+1)^l}$$
に対して同様の操作を繰り返していくことで(3)の場合に帰着できる。

一般の場合

　これによって一般の有理関数$S(n)$に対し
$$S(n) =K(n)S_1(n+1)-S_1(n)+\l(\frac{c_0(n)}{v(n)}+\frac{c_1(n)}{q(n)}\r)$$
なる多項式$v(n)$であって条件(ii)を満たすようなものが構成できる。
　また$v(n)$がshift-freeでなければ上と同様の操作によって
$$\frac{a_1(n)}{b(n)^k}+\frac{a_2(n)}{b(n+h)^{k'}} =K(n)S'_1(n+1)-S'_1(n)+\l(\frac{a_1(n)}{b(n)^k}+\frac{c_0(n)}{b(n)^l}+\frac{c_1(n)}{q(n)}\r)$$
と平行移動させることでshift-freeなるものが構成できる。

　$A(n)$の核$K(n)=p(n)/q(n)$と殻$S(n)$に対し上の補題のような有理関数$S_1(n)$と多項式$u(n),v(n)$を取る。
　このとき
$$A(n)=S(n)H(n),\quad T_1(n)=S_1(n)H(n),\quad T_2(n)=\frac{u(n)}{v(n)q(n)}H(n)$$
とおくと、この$T_1(n),T_2(n)$は所望の性質を満たす。実際そのことは核
$$K'(n)=\frac{p(n)}{q(n+1)}$$
に関する$T_2(n)$の殻が
$$S'_2(n)=\frac{u(n)}{v(n)}$$
となることからわかる。

　$A(n)$の核と殻として
\begin{align} K(n)&=\frac1{n+1}\\ S(n)&=\frac1{n^4+n^2+1}\\ &=\frac12\l(\frac{n+1}{n^2+n+1}-\frac{n-1}{n^2-n+1}\r) \end{align}
を取る。このとき
$$S_1(n+1)=\frac1{\frac1{n+1}}\frac{n+1}{n^2+n+1}$$
つまり
$$S_1(n)=\frac{n^2}{n^2-n+1}$$
とおくと
$$\frac{n-1}{n^2+n+1}=K(n)S_1(n+1)-S_1(n)+\frac{n^2}{n^2-n+1}$$
が成り立つので
\begin{align} 2S(n) &=K(n)S_1(n+1)-S_1(n)+\frac{n^2-(n-1)}{n^2-n+1}\\ &=K(n)S_1(n+1)-S_1(n)+1 \end{align}
を得る。したがって
$$T_1(n)=\frac{n^2}{2(n^2-n+1)n!},\quad T_2(n)=\frac1{2n!}$$
が求める超幾何数列となる。

　$W$の取り方から$V+W$が直和であることは明らか。
　任意の整数$k\geq0$に対し$x^k\in V\oplus W$が成り立つことを帰納法によって示す。$x^k\in W$であれば明らか。また$x^k\not\in W$であればある$k$次のモニック多項式$f(x)\in V$が存在し、帰納法の仮定により
$$x^k-f(x)\in\span\{1,x,\ldots,x^{k-1}\}\subset V\oplus W$$
が成り立つので
$$x^k=(x^k-f(x))+f(x)\in V\oplus W$$
を得る。

　$A(n)$の核$K(n)=p(n)/q(n)$と殻$S(n)$に対し補題5よりある有理関数$S_1(n)$と多項式$v(n),c_0(n),c_1(n)$であって
$$S(n)=K(n)S_1(n+1)-S_1(n)+\l(\frac{a(n)}{v(n)}+\frac{b(n)}{q(n)}\r)$$
および上の(i),(ii)を満たすようなものが取れる。
　いま$c_0(n)$を$v(n)$で割り
$$c_0(n)=c'_0(n)v(n)+a(n)$$
とおき、またこれに対し
$$c(n)=c'_0(n)q(n)+c_1(n)$$
とおくと
$$\frac{c_0(n)}{v(n)}+\frac{c_1(n)}{q(n)}=\frac{a(n)}{v(n)}+\frac{c(n)}{q(n)}$$
が成り立つ(これによって(iii)が満たされる)。
　また補題7より
$$c(n)=c'(n)+b(n)$$
なる$c'(n)\in V_K,b(n)\in W_K$が存在し、また$V_K$の取り方から
$$c'(n)=p(n)f(n+1)-q(n)f(n)=(K(n)f(n+1)-f(n))q(n)$$
なる多項式$f(n)$が取れる。このとき
$$S'_1(n)=S_1(n)+f(n)$$
とおくと
$$S(n)=K(n)S'_1(n+1)-S'_1(n)+\l(\frac{a(n)}{v(n)}+\frac{b(n)}{q(n)}\r)$$
が成り立つ。
　したがってこれに対し
$$T_1(n)=S'_1(n)\frac{A(n)}{S(n)},\quad T_2(n)=\l(\frac{a(n)}{v(n)}+\frac{b(n)}{q(n)}\r)\frac{A(n)}{S(n)}$$
とおくとこれらは所望の性質を満たすことがわかる。

　多項式$f(n)$に対し
$$g(n)=p(n)f(n+1)-q(n)f(n)$$
の次数が取り得る値の範囲について考えればよい。

$\deg p\neq\deg q$または$\la_p\neq\la_q$が成り立つとき

　このとき明らかに
$$\deg g=d+\deg f$$
が成り立つので$\deg g$の取り得る値の範囲は
$$\deg g\geq d$$
と求まる。

$\deg p=\deg q$かつ$\la_p=\la_q=\la$が成り立つとき

　このとき$f$をモニック多項式とすると
\begin{align} g(n) &=p(n)(f(n+1)-f(n))+(p(n)-q(n))f(n)\\ &=(\la k+P-Q)n^{d+\deg f-1}+\cdots \end{align}
と表せるので$\deg f\neq d'\ (=(Q-P)/\la)$であれば
$$\deg g=d+\deg f-1$$
が成り立つ。
　また($d'$が非負整数であり)$\deg f=d'$のときは
$$\deg g< d+d'-1$$
が成り立つので、これを次数$d+k-1\quad(0\leq k< d')$の多項式
$$g_k(n)=p(n)f_k(n+1)-q(n)f_k(n)\quad(\deg f_k=k)$$
を用いて次数下げすることによって
$$\deg g< d-1$$
とすることができる。
　したがって$\deg g$の取り得る値の範囲は$d'\not\in\Z_{\geq0}$のとき
$$\deg g\geq d-1$$
と求まり、$d'\in\Z_{\geq0}$のとき
$$\deg g\geq d-1\quad\mbox{かつ}\quad\deg g\neq d+d'-1$$
または
$$\deg g=\min\{\deg(p(n)f(n+1)-q(n)f(n))\mid \deg f=d'\}$$
と求まる。
　以上より主張を得る。

$$p(n)=n^4+1,\quad q(n)=(n+1)^4$$
より$d=d'=4$が成り立つことに注意する。
　いま$k=0,1,2,3,4$に対し
$$g_k(n)=p(n)(n+1)^k-q(n)n^k$$
とおくと
\begin{align} g_4(n)&=(n+1)^4\\ g_1(n)&=-(n+1)(3n^3+3n^2+n-1)\\ g_0(n)&=-(4n^3+6n^2+4n) \end{align}
が成り立つので$g_4(n)$は
$$g_4(n)+\frac13g_1(n)+\frac12g_0(n)=\frac53n^2+2n+\frac43$$
と次数下げできる。したがって$d''=2$つまり
$$W_K=\span\{1,n,n^7\}$$
を得る。

　$A(n)$の核と殻
$$K(n)=n+1,\quad S(n)=\frac{n^2}{n+1}=n-1+\frac1{n+1}$$
に対しAbramov-Petkovšek's algorithmを実行すると
$$S(n)=K(n)S_1(n+1)-S_1(n)+S_2(n)$$
なる有理関数$S_1(n),S_2(n)$として
$$S_1(n)=-\frac1{n+1},\quad S_2(n)=-\frac1{n+2}+\frac n1$$
が取れる。
　また$W_K=\span\{1\}$なのでこれはまだ簡約化することができ、実際
$$n=K(n)-1$$
より
$$S'_1(n)=S_1(n)+1=\frac n{n+1},\quad S'_2(n)=-\frac1{n+2}$$
つまり
$$T_1(n)=\frac n{n+1}n!,\quad T_2(n)=-\frac1{n+2}n!$$
とおくとこれが求める超幾何数列となる。

　$S(n)$が多項式ではない、特に$v(n)$がある既約多項式$b(n)$を因数に持つものとする。
　いま
$$A(n)=T(n+1)-T(n)$$
なる超幾何数列$T(n)$が存在する、つまり
$$S(n)=K(n)\frac{u_1(n+1)}{v_1(n+1)}-\frac{u_1(n)}{v_1(n)}$$
なる多項式$u_1(n),v_1(n)$が存在するならば定理5(の特別な場合の証明)と全く同様にして、ある$0$でない整数$h$が存在して
$$b(n+h)\mid v_1(n)\quad\mbox{かつ}\quad b(n+h)\nmid v_1(n+1)$$
または
$$b(n+h)\nmid v_1(n)\quad\mbox{かつ}\quad b(n+h)\mid v_1(n+1)$$
が成り立つことがわかる。このとき$v(n)$は$b(n+h)$も因数に持たなければならないが、これは$v(n)$がshift-freeであったことに矛盾。よって$v(n)$は定数でなければならないことが示された。

　residual form$A(n)$に対し(i)-(iv)を満たすような核と殻
$$K(n)=\frac{p(n)}{q(n)},\quad S(n)=\frac{a(n)}{v(n)}+\frac{b(n)}{q(n)}$$
を取る。このとき
$$K'(n)=\frac{p(n)}{q(n+1)},\quad S'(n)=\frac{a(n)q(n)}{v(n)}+b(n)$$
という核と殻を考えるとこれらは(i),(ii)を満たすので、命題9より$A(n)$がGosper総和可能でれば$S'(n)$は多項式となる。特に$v(n)$と$q(n)$が互いに素であることと$\deg a<\deg v$であることから$a(n)=0$でなければならない。
　また
$$A(n)=T(n+1)-T(n)$$
なる超幾何数列$T(n)$が存在する、つまり
$$b(n)=p(n)x(n+1)-q(n)x(n)$$
なる有理関数$x(n)$が存在するならば 第二回の記事 の定理4から$x(n)$は多項式となる。したがって$b(n)\in V_K\cap W_K$つまり$b(n)=0$が成り立たなければならないが超幾何数列の定義から$A(n)\neq0$であったことに矛盾。よって$A(n)$はGosper総和不可能である。