線形合同法とp進整数と縮小写像

$p$ を素数， $e$ を正整数， $a, b$ を整数とする． $f: \mathbb{Z}/p^e\mathbb{Z} \to \mathbb{Z}/p^e\mathbb{Z}$ を $$f(x) = a x + b$$ で定める．

命題1

$a$ が $p$ の倍数であると仮定する．このとき次が成立する．

$f$ の不動点，すなわち $$f(x) = x$$ を満たす $x \in \mathbb{Z}/p^e\mathbb{Z}$ が存在する．

$f$ の不動点は一意である．

任意の $x_0 \in \mathbb{Z}/p^e\mathbb{Z}$ について次で定義される数列: $$ x_n = f^n(x_0) $$ は不動点に収束する．（ここに $f^n$ は $f$ の $n$ 回合成）

証明．(1)と(2):

$$ f(x) = x \iff (a-1)x \equiv -b \pmod{p^e} $$ だが，今 $a$ が $p$ の倍数なので， $a-1$ は $p$ と互いに素．よってこの一次合同方程式には解が一意に存在する．

(3): 数列の一般項は $$ x_n = a^n x_0 + (1 + a + a^2 + \dots + a^{n-1})b $$ となる． $a$ が $p$ の倍数なので $a^{n_0} \equiv 0 \pmod{p^e}$ となる $n_0$ がある．すると $n > n_0$ なら $$ x_n = (1 + a + a^2 + \dots + a^{{n_0}-1})b $$ となって一定値をとる． ■

ところで次のようなよく知られた定理がある．

定理 (Banachの不動点定理)

$(X, d)$ を空でない完備距離空間， $f: X \to X$ を次を満たす写像とする: ある $k\ (0 \leq k \lt 1)$ があって任意の $x, y \in X$ について $$ d(f(x), f(y)) \leq k\,d(x, y). $$ このとき $f$ の不動点がただ一つ存在する．また任意の $x_0$ に対して数列 $x_n = f^n(x_0)$ は不動点に収束する．

Banachの不動点定理によって最初の命題を証明できないだろうか． $\mathbb{Z}/p^e\mathbb{Z}$ には距離は離散距離しか入らないので使えそうにない．そこで $p$ 進整数環 $\mathbb{Z}_p$ と呼ばれる空間を考える．

$p$ 進整数環の定義はここではしないが，次のような性質を持つ．

$\mathbb{Z}_p$ には環構造が入る
$\mathbb{Z} \subset \mathbb{Z}_p$ である
$x \in \mathbb{Z}_p$ に対して $x$ の $p$ 進絶対値 $|x|_p$ が定まる
$|x|_p = 0 \iff x = 0$
$|xy|_p = |x|_p |y|_p$
$|x + y|_p \leq \max\{|x|_p, |y|_p\}$
$x \in \mathbb{Z} \setminus \{0\}$ に対しては $x$ を素因数分解したときの $p$ の指数を $n$ としたとき $|x|_p = p^{-n}$
$d(x, y) = |x - y|_p$ と定めるとき $(\mathbb{Z}_p, d)$ は完備距離空間
全射環準同型 $\varphi_e: \mathbb{Z}_p \to \mathbb{Z}/p^e\mathbb{Z}$ があり，特に $x \in \mathbb{Z}$ なら $\varphi_e(x) = x \bmod p^e$

$f$ は $\mathbb{Z}/p^e\mathbb{Z}$ 上の写像であったが，これを $\mathbb{Z}_p$ 上に修正したものを $\tilde{f}$ で表す: $$ \tilde{f}: \mathbb{Z}_p \ni x \mapsto (ax+b) \in \mathbb{Z}_p$$

この $\tilde{f}$ はBanachの定理の仮定を満たす．実際，

\begin{align*} d(\tilde{f}(x), \tilde{f}(y)) &= |(ax+b)-(ay+b)|_p \\ &= |a(x-y)|_p \\ &= |a|_p |x-y|_p \\ &= |a|_p d(x, y) \end{align*}

であり， $a$ が $p$ の倍数だから $|a|_p \lt 1$ である．

よって $\tilde{f}$ の不動点 $x$ が存在し，それを $\varphi_e$ で移せば $f$ の不動点を得る．ゆえに命題の(1)が示された．また， $\mathbb{Z}/p^e\mathbb{Z}$ に離散位相を入れたとき， $\varphi_e$ が連続写像になるので，そこから命題の(3)を得る． (なお，残念ながら，命題の(2)はこの方法では示せない．)

以上よりBanachの不動点定理によって最初の命題を(一部分を除いて)示せることがわかった．

$a = {\rm 0x12344}$ (偶数なことに注意！), $b = {\rm 0x6073}, p = 2, e = 20, x_0 = 1$ としてみると次の表のようになる．下の桁から順に固定されていっている様子がわかる．

$n$	$x_n$
$0$	${\rm 0x00001}$
$1$	${\rm 0x183b7}$
$2$	${\rm 0x0620f}$
$3$	${\rm 0x1796f}$
$4$	${\rm 0xdceef}$
$5$	${\rm 0x504ef}$
$6$	${\rm 0x15cef}$
$7$	${\rm 0x0bcef}$
$8$	${\rm 0x63cef}$
$9$	${\rm 0xc3cef}$
$10$	${\rm 0x43cef}$
$11$	${\rm 0x43cef}$
$12$	${\rm 0x43cef}$