定理１－３

【定理】

整数係数多項式 $\mathbf{f}(\mathbf{z})=\mathbf{a}\mathbf{z}^{\mathbf{2}}+\mathbf{b}\mathbf{z}+\mathbf{c}$ に対し，整数列 $\{\mathbf{z}_{\mathbf{r}}\}$ を $\mathbf{z}_{\mathbf{0}}=\mathbf{0}$ ， $\mathbf{z}_{\mathbf{r}+\mathbf{1}}=\mathbf{f}(\mathbf{z}_{\mathbf{r}})$ と定義する． $\{\mathbf{z}_{\mathbf{r}}\}$ が任意の自然数 $\mathbf{n}$ について $\mathbf{Z}/\mathbf{2}^{\mathbf{n}}\mathbf{Z}$ 上で周期 $\mathbf{2}^{\mathbf{n}}$ をもつための必要十分条件は， $\mathbf{b}\equiv\mathbf{c}\equiv\mathbf{1}{\rm mod}\mathbf{2}$ かつ $\mathbf{a}+\mathbf{b}\equiv\mathbf{1}{\rm mod}\mathbf{4}$ ．

［補題１］

$\{\mathbf{z}_{\mathbf{r}}\}$ が $\mathbf{Z}/\mathbf{2}\mathbf{Z}$ 上で周期 $\mathbf{2}$ をもつための必要十分条件は， $\mathbf{c}\equiv\mathbf{1}{\rm mod}\mathbf{2}$ かつ $\mathbf{a}+\mathbf{b}\equiv\mathbf{1}{\rm mod}\mathbf{2}$ ．

［補題１の証明］

$f(0)=c\equiv 1{\rm mod}2$ ， $f(1)=a+b+c\equiv 0{\rm mod}2 \Rightarrow a+b\equiv 1{\rm mod}2$ ．

［補題２］

$\mathbf{b}\equiv\mathbf{1}{\rm mod}\mathbf{2}$ のとき，任意の $\mathbf{n}$ について $\mathbf{f}(\mathbf{2}^{\mathbf{n}}+\mathbf{z})\equiv\mathbf{2}^{\mathbf{n}}+\mathbf{f}(\mathbf{z}) {\rm mod}\mathbf{2}^{\mathbf{n}+\mathbf{1}}$ ．逆に $\mathbf{b}\equiv\mathbf{0}{\rm mod}\mathbf{2}$ のとき， $\mathbf{f}(\mathbf{2}^{\mathbf{n}}+\mathbf{z})\equiv\mathbf{f}(\mathbf{z}) {\rm mod}\mathbf{2}^{\mathbf{n}+\mathbf{1}}$ より $\{\mathbf{z}_{\mathbf{r}}\}$ は $\mathbf{Z}/\mathbf{2}^{\mathbf{n}+\mathbf{1}}\mathbf{Z}$ 上で周期 $\mathbf{2}^{\mathbf{n}+\mathbf{1}}$ をもたない．

［補題２の証明］

$f(2^{n}+z)\equiv az^{2}+2^{n}b+bz+c\equiv 2^{n}b+f(z) {\rm mod}2^{n+1}$ ．

［補題３］

$\mathbf{b}\equiv\mathbf{1}{\rm mod}\mathbf{2}$ かつ $\{\mathbf{z}_{\mathbf{r}}\}$ が $\mathbf{Z}/\mathbf{2}^{\mathbf{n}}\mathbf{Z}$ 上で周期 $\mathbf{2}^{\mathbf{n}}$ をもつとき， $\{\mathbf{z}_{\mathbf{r}}\}$ が $\mathbf{Z}/\mathbf{2}^{\mathbf{n}+\mathbf{1}}\mathbf{Z}$ 上で周期 $\mathbf{2}^{\mathbf{n}+\mathbf{1}}$ をもつための必要十分条件は

$\sum_{\mathbf{r}=\mathbf{0}}^{\mathbf{2}^{\mathbf{n}}-\mathbf{1}}\mathbf{f}(\mathbf{r})-\sum_{\mathbf{r}=\mathbf{0}}^{\mathbf{2}^{\mathbf{n}}-\mathbf{1}}\mathbf{r}\equiv\mathbf{2}^{\mathbf{n}} {\rm mod}\mathbf{2}^{\mathbf{n}+\mathbf{1}}$ ．

［補題３の証明］

$\{z_{r}\}$ の $Z/2^{n+1}Z$ への射影を最上位ビット成分 $\{y_{r}\}$ と下位 $n$ ビット成分 $\{z_{r}\}$ に分解し，

$z_{r}\equiv 2^{n}y_{r}+x_{r} {\rm mod}2^{n+1}$ （ $y_{r}\in\{0, 1\}$ ， $x_{r}\in[0, 2^{n}-1]$ ）

とする．補題２より

$2^{n}y_{r+1}+x_{r+1}\equiv f(2^{n}y_{r}+x_{r})\equiv 2^{n}y_{r}+f(x_{r}) {\rm mod}2^{n+1}$ （以下 ${\rm mod}2^{n+1}$ を省略）

$2^{n}(y_{r+1}-y_{r})\equiv f(x_{r})-x_{r+1}$ ．

$0\leq r\leq 2^{n}-1$ について両辺の総和をとると， $y_{0}=0$ より

$2^{n}y_{2^{n}}\equiv\sum_{r=0}^{2^{n}-1}f(x_{r})-\sum_{r=0}^{2^{n}-1}x_{r+1}$ ．

$\{z_{r}\}$ が $Z/2^{n}Z$ 上で周期 $2^{n}$ をもつことから，右辺の $x_{r}$ および $x_{r+1}$ は $[0, 2^{n}-1]$ の値を一度ずつとり，

$2^{n}y_{2^{n}}\equiv\sum_{r=0}^{2^{n}-1}f(r)-\sum_{r=0}^{2^{n}-1}r$ ．

ここで， $\{z_{r}\}$ の $Z/2^{n+1}Z$ 上の周期は $2^{n}$ と $2^{n+1}$ のいずれかであるが， $z_{2^{n}}\equiv 2^{n}y_{2^{n}}$ より周期が $2^{n+1}$ となるための必要十分条件は $y_{2^{n}}=1$ であり，これにより補題が証明される．

【定理の証明】

補題１および補題２より， $b\equiv c\equiv 1{\rm mod}2$ かつ $a\equiv 0{\rm mod}2$ が定理の必要条件となる．この条件のもとで，ある $n$ について $\{z_{r}\}$ が $Z/2^{n}Z$ 上で周期 $2^{n}$ をもつと仮定する．（ $n=1$ では成立）

このとき補題３より， $\{z_{r}\}$ が $Z/2^{n+1}Z$ 上で周期 $2^{n+1}$ をもつための必要十分条件は

$\sum_{r=0}^{2^{n}-1}f(r)-\sum_{r=0}^{2^{n}-1}r\equiv\sum_{r=0}^{2^{n}-1}(ar^{2}+br+c)-\sum_{r=0}^{2^{n}-1}r\equiv a\sum_{r=0}^{2^{n}-1}r^{2}+(b-1)\sum_{r=0}^{2^{n}-1}r+2^{n}c\equiv 2^{n} {\rm mod}2^{n+1}$

$\Leftrightarrow a\sum_{r=0}^{2^{n}-1}r^{2}+(b-1)\sum_{r=0}^{2^{n}-1}r\equiv 0 {\rm mod}2^{n+1}$

$\Leftrightarrow a\frac{(2^{n+1}-1)(2^{n}-1)}{3}2^{n-1}+(b-1)(2^{n}-1)2^{n-1}\equiv 0 {\rm mod}2^{n+1}$

$\Leftrightarrow a\frac{(2^{n+1}-1)(2^{n}-1)}{3}+(b-1)(2^{n}-1)\equiv 0 {\rm mod}4$

$\Leftrightarrow a+b\equiv 1 {\rm mod}4$ ．

したがって，これらの条件をまとめて $b\equiv c\equiv 1{\rm mod}2$ かつ $a+b\equiv 1{\rm mod}4$ とすると，補題３および数学的帰納法により任意の自然数 $n$ について $\{z_{r}\}$ が $Z/2^{n}Z$ 上で周期 $2^{n}$ をもつ．■

戻る