線形合同法と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

apの倍数であると仮定する. このとき次が成立する.

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

  2. f不動点は一意である.

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

証明.(1)と(2):

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

(3): 数列の一般項は $$ x_n = a^n x_0 + (1 + a + a^2 + \dots + a^{n-1})b $$ となる.apの倍数なので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に対してxp進絶対値|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*}

であり,apの倍数だから|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}