メモ: ヘンゼルの補題 - 再帰の反復blog

ニュートン法との類似
完備化とp進数体
因数分解形のヘンゼルの補題

ニュートン法との類似
- 補足 $f'(x_0) \equiv 0 \, \pmod p$ の場合
完備化とp進数体
- 補足 p進距離感についての例
因数分解形のヘンゼルの補題

1. ニュートン法との類似

ヘンゼルの補題といっても色々な述べられ方があるけれどここでは次のものを考えて、ニュートン法との類似を見る。

(ヘンゼルの補題)
$p$ を素数とする。整数係数の多項式 $f(X)$ が、ある $x_0 \in \mathbb{Z}$ で

$f(x_0) \equiv 0 \, \pmod p$ 、 $f'(x_0) \not\equiv 0 \, \pmod p$

となったとする(ここで $f'(X)$ は、極限操作とは無関係に $f(X)$ を形式的に微分したもの)。
このとき、次を満たす整数の系列 $x_1,x_2, \ldots, x_k,\ldots$ を取れる。

$f(x_k) \equiv 0 \, \pmod {p^{k+1}} \\ x_k \equiv x_{k-1} \, \pmod {p^k}$

まずこの補題をp進距離的に解釈する。
p進距離の距離感では、 $a$ と $b$ は、 $a \equiv b \, \pmod p$ を満たすとき「近い」。さらに、より大きな $n$ で $a \equiv b \, \pmod {p^{n}}$ を満たせば満たすほど「より近い」。定量的には、 $a \equiv b \, \pmod {p^{n}}$ が成り立つ最大の $n$ をとって、 $\frac{1}{p^n}$ を $a$ と $b$ とのp進距離とする。
例えば通常の距離感で考えると、数列 $\frac{1}{p^2},\frac{1}{p^3},\frac{1}{p^4},\ldots$ はだんだん $0$ に近づいていき、 $p,p^2,p^3,\ldots$ はだんだん $0$ から離れていく。しかしp進距離の距離感では、 $p,p^2,p^3,\ldots$ はだんだん $0$ に近づいていく。(cf.p進展開について)
このp進距離感を前提にして考えると、補題の前提である

$f(x_0) \equiv 0 \, \pmod p$

は、

ある $x_0$ を取ると、 $f(x_0)$ が $0$ に近い値になる

と言っている。そして結論側の、

ある数列 $x_1,x_2, \ldots, x_k,\ldots$ が取れて、 $f(x_k) \equiv 0 \, \pmod {p^{k+1}}$

は、

$f(x_1),f(x_2),\ldots$ がどんどん $0$ に近づいていくように $x_1,x_2,\ldots$ を取れる

と言い換えられる。
このように言い換えるとニュートン法との類似が見えてくる。
ニュートン法では、

$x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}$

という数列を計算していく。このとき適当な条件を満たしているなら $f(x_k)$ は $0$ に収束する、というのがニュートン法。つまりこの方法によって、 $f(x_1),f(x_2),\ldots$ がどんどん $0$ に近づいていくように $x_1,x_2,\ldots$ を取ることができる。もちろんここで使っている距離は、p進距離ではなく通常の距離。
そしてこれと類似の手続きによってヘンゼルの補題が証明できる。
ただし整数の世界では割り算ができないので、 $\frac{1}{f'(x_k)}$ の部分を修正する必要がある。そこで次の性質を使う。

$a \not \equiv 0 \, \pmod p$ となる $a$ は、ある $s$ を取ると $a s \equiv 1 \, \pmod p$ となる。

このような $s$ はユークリッドの互除法によって $as+pt = 1$ となる $s,t$ を計算すれば得られる。この $s$ は、 $p$ で割った余りの世界での $a$ の逆数になるので $\frac{1}{a}$ のようなものだと考えることができる。
したがって $x_{k+1}$ を求めるためには、まずユークリッドの互除法によって

$f'(x_k) s_k + p t_k =1$

により $s_k$ を計算する( $f'(x_k) \not\equiv 0 \, \pmod p$ となることが示されるのでこの計算はうまくいく)。この $s_k$ が $f'(x_k)$ の逆数の役割を果たすので

$x_{k+1} = x_{k} - f(x_k) \, s_k$

とする。
一つ前のステップで $f(x_k) \equiv 0 \, \pmod {p^{k+1}}$ となっていれば、

$x_{k+1} \equiv x_{k} - f(x_k) \, s_k \equiv x_k \, \pmod {p^{k+1}}$

となり、 $x_{k+1} \equiv x_{k} \, \pmod {p^{k+1}}$ は満たされる。
またどんな多項式 $F(X)$ についても、 $a \equiv b \, \pmod p$ ならば $F(a) \equiv F(b) \, \pmod p$ となることを使うと、 $x_{k+1} \equiv x_{k} \equiv x_{k-1} \equiv \cdots \equiv x_0 \, \pmod {p}$ より

$f'(x_{k+1}) \equiv f'(x_{k}) \equiv f'(x_{k-1}) \equiv \cdots \equiv f'(x_0) \equiv 0 \, \pmod p$

となるので、次のステップで $f'(x_{k+1})$ の「逆数」を計算できる。
あとは $f(x_{k+1})$ と0とのp進距離を評価する必要があるけれど、この評価もニュートン法の場合と類似のやり方でできる。
ニュートン法の証明では、 $f(x)$ を2次までテーラー展開したものを考える。

$f(x) = f(x_k) + f'(x_k) (x - x_k) + \frac{f''(\xi_k)}{2}(x- x_k)^2$

ヘンゼルの補題の証明には、整数係数の多項式 $f(x)$ が

$f(x) = f(x_k) + f'(x_k) (x - x_k) + g(x)(x- x_k)^2$

と展開できることを使う(ここで $g(x)$ は整数係数の多項式)。 $f(x_{k+1})$ を計算すると

$\begin{eqnarray} f(x_{k+1}) &=& f(x_k) - f'(x_k) f(x_k) s_k + g(x_k) \left(f(x_k) \right)^2 s_k^2 \\ &=& f(x_k) + f(x_k) \left(t_k p -1 \right) + g(x_k) \left(f(x_k) \right)^2 s_k^2 \\ &=& f(x_k) t_k p + g(x_k) \left(f(x_k) \right)^2 s_k^2 \end{eqnarray}$

となり、 $f(x_k) \equiv 0 \, \pmod {p^{k+1}}$ 、 $\left( f(x_k) \right)^2 \equiv 0 \, \pmod {p^{2k+2}}$ なので

$f(x_{k+1}) \equiv 0 \, \pmod {p^{k+2}}$

となる。
よって提示した手続きにより、各ステップで

$f(x_k) \equiv 0 \, \pmod {p^{k+1}} \\ x_k \equiv x_{k-1} \, \pmod {p^k}$

を満たす $x_k$ が得られ、ヘンゼルの補題が証明される。

(補足) $f'(x_0) \equiv 0 \, \pmod p$ の場合

(※この部分はあとの話には関係しない)
上の証明では、 $f'(x_0) \not\equiv 0 \, \pmod p$ となることを前提している。しかし付加的な条件を付け加えれば、 $f'(x_0) \equiv 0 \, \pmod p$ となる場合にも拡張することができる。
ヘンゼルの補題の証明では、ユークリッドの互除法を使って $f'(x_k)$ の逆数の役割をする $s_k$ 、つまり

$f'(x_k) s_k + p t_k =1$

を満たす $s_k$ を計算した。
$f'(x_0) \equiv 0 \, \pmod p$ の場合は、次のようにする。
$f'(x_0) \equiv 0 \, \pmod {p^n}$ となる最大の $n$ をとり、 $f'(x_k)=p^n a_k$ とする。この $a_k$ と $p$ に対してユークリッドの互除法を適用し

$a_k s_k + p t_k =1$

となる $s_k$ を求める。すると

$f'(x_k) \cdot \frac{s_k}{p^n} =p^n a_k \cdot \frac{s_k}{p^n} =a_k s_k = 1 - p t_k \equiv 1 \, \pmod p$

となり、 $\frac{s_k}{p^n}$ が $f'(x_k)$ の逆数になることがわかる。そこで

$x_{k+1}=x_{k} - f(x_k)\frac{s_k}{p^n}$

として、前と同じように計算する。すると

$f(x_{k+1}) =f(x_k)pt_k+g(x_k)\left(\frac{f(x_k)}{p^n}\right)^2 s_k^2$

となる。ここで右辺第1項は前と同じで問題ないけれど、第2項で $f(x_k)$ を $p^n$ で割っているため、前と同じ前提ではうまくいかない。
そこで初期値 $x_0$ の時点で $f(x_0)$ の値がもっと $0$ に近い場合を考える。

$f(x_0) \equiv 0 \, \pmod {p^m}$

このとき、各ステップがうまくいき $f(x_k)$ がだんだん0に近づいていくなら

$f(x_k) \equiv 0 \, \pmod {p^{m+k}}$

となる。この式から $f(x_k)^2 \equiv 0 \, \pmod {p^{2m+2k}}$ なので

$\left( \frac{f(x_k)}{p^n} \right)^2 \equiv 0 \, \pmod {p^{2m+2k-2n}}$

となる。 $\bmod$ の右側が整数であるために、 $m \geq n$ でないといけない。さらに

$f(x_{k+1}) = f(x_k)pt_k+g(x_k)\left(\frac{f(x_k)}{p^n}\right)^2 s_k^2 \, \equiv 0 \, \pmod {p^{m+k+1}}$

となるためには、 $2m+2k-2n \geq m+k+1$ が必要なので

$m>2n$

でないといけない。この条件を満たしていると前と同様の計算により次が証明できる。

整数係数の多項式 $f(X)$ が、ある $x_0 \in \mathbb{Z}$ で、

$f(x_0) \equiv 0 \, \pmod {p^m}$ 、 $f'(x_0) \not\equiv 0 \, \pmod {p^{n+1}}$

となり、 $m>2n$ であるとする。
このとき、次を満たす整数の系列 $x_1,x_2, \ldots, x_k,\ldots$ を取れる。

$f(x_k) \equiv 0 \, \pmod {p^{k+m}} \\ x_k \equiv x_{k-1} \, \pmod {p^{m-n-1+k}}$

2. 完備化とp進数体

いったん普通の距離に戻って、 $f(x)=x^2 -2$ に通常のニュートン法を適用する。

$x_{k+1} = \frac{1}{2}\left(x_k + \frac{2}{x_k} \right)$

となるので、 $x_0=1$ から始めると

x0 = 1                            ;     = 1
x1 = 3/2                          ;     = 1.5
x2 = 17/12                        ;     = 1.4166……
x3 = 577/408                      ;     = 1.4142156……
x4 = 665857/470832                ;     = 1.4142135623746……
x5 = 886731088897/627013566048    ;     = 1.4142135623730950488016896……

                                  ; √2 = 1.4142135623730950488016887242……

という数列が得られる。この数列の各項はどれも有理数だけど、有理数の範囲では収束せず無理数 $\sqrt{2} \in \mathbb{R}$ に収束する。
このことを踏まえて、多項式 $f(X)=X^2 - 2$ にヘンゼルの補題を適用してみる。
平方剰余の第2補充則によると、 $X^2 - 2 \equiv 0 \, \pmod p$ は $p \equiv 1,7 \, \pmod 8$ のときに解を持つので、例として $p=7$ のときを考える。
$x_0 = 3$ を取ると、 $3^2-2 \equiv 0 \, \pmod 7$ となる。
ヘンゼルの補題の証明でおこなった手続きを適用していくと $x_{k+1}= x_k - (x_k^2 -2)6$ によって

x0 = 3
x1 = -39
x2 = -9153
x3 = -502673595
x4 = -1516084459164017733

という数列が得られる。
この数列が $x_k \equiv x_{k-1} \pmod{7^{k}}$ を満たしていることは、7進数の形で表して、さらに負数は7の補数表現にすると見やすい。

; 7進数での表示
x0 =                       3 = ...000000000000000000000000003
x1 =                     -54 = ...666666666666666666666666613
x2 =                  -35454 = ...666666666666666666666631213
x3 =            -15312440454 = ...666666666666666651354226213
x4 = -2500006420353054050454 = ...666664166660246313612616213


                               ...536623164112011266421216213

さらに $x_k^2$ も7進表示すれば、 $x_k^2 - 2 \equiv 0 \, \pmod {7^{k+1}}$ を満たしていることも判る。

; 7進数での表示
x0*x0 =                                              12
x1*x1 =                                            4302
x2*x2 =                                      2035045002
x3*x3 =                           311112161151641260002
x4*x4 =    10240050622025434663022515053464424103300002


        ...00000000000000000000000000000000000000000002

この数列 $x_0,x_1,\ldots,x_k,\ldots$ はp進距離で見るとコーシー列になっている。しかし整数の範囲でも有理数の範囲でも収束先は存在しない。
そこでコーシー列(p進距離のもとでのコーシー列)が必ず収束するように、コーシー列ごとに新たな数を追加する。このときコーシー列の収束先が同じなら追加する数は同じものと考える。(このような操作は「完備化」と言われる)。ここまでは整数の数列しか考えていなかったけれど、有理数に対してもp進距離は考えられるので有理数のコーシー列も考えてそれらの収束先も付け加える。
その結果、p進数体 $\mathbb{Q}_{p}$ と呼ばれるものが得られる。通常の距離感での完備化は「有理数だけが並んでいる数直線があって、その隙間をすべて埋める」というイメージになるけれど、p進距離感のもとでは有理数は直線的に並んでいるわけではないので完備化はイメージしにくい。
完備化すれば、上の数列 $x_0,x_1,\ldots,x_k,\ldots$ はある $\alpha \in \mathbb{Q}_{7}$ に収束して、 $\alpha^2 -2 = 0$ を満たす。 $\alpha^2=2$ なので $\alpha = \sqrt{2}$ と表記することにする(当然、実数の $\sqrt{2}$ とは異なる)。
同様に考えると、 $p=7$ に限らず $p \equiv 1,7 \, \pmod 8$ となる素数について、

$\sqrt{2} \in \mathbb{Q}_{p}$

となることがわかる。逆に $p \equiv 3,5 \, \pmod 8$ となる素数については

$\sqrt{2} \not\in \mathbb{Q}_{p}$

となる(これもヘンゼルの補題と $\mathbb{Q}_{p}$ についての性質から出る)。この場合 $\mathbb{Q}_{p}$ に $\sqrt{2}$ を追加してやると、 $\mathbb{Q}_{p}(\sqrt{2})$ は $\mathbb{Q}_{p}$ の2次拡大になる(一般に、素数 $p\not=2$ について $\mathbb{Q}_{p}$ の2次拡大はちょうど3つあり、その3つは $\sqrt{a} \not\in \mathbb{Q}_{p}$ となる $a$ をとったとき

$\mathbb{Q}_{p}(\sqrt{a}), \, \mathbb{Q}_{p}(\sqrt{p}), \, \mathbb{Q}_{p}(\sqrt{ap})$

と書ける。ついでに $p=2$ の場合は $\mathbb{Q}_{2}$ の2次拡大は7つある。いずれにしても $\mathbb{Q}$ の2次拡大が無数にあるのに比べると、2次拡大が有限個しかなく単純になっている(1の原始 $n$ 乗が含まれている体 $K$ に $K({}^{\small n}\large\sqrt{a})$ の形の拡大がどれくらいあるかはクンマー理論で扱われる)。

(補足) p進距離感についての例

(次も参照: 加藤和也『素数の歌が聞こえる』間奏の章1)
通常の距離感では当たり前の感覚がp進距離でも通用するとは限らない。例えば次のような例を考える。
ゼータ関数 $\zeta(s)$ は、負の整数 $s=1-r \leq -1$ で

$\zeta(1-r) = -\frac{B_r}{r} \, \in \mathbb{Q}$

という値をとり、この値について次のことが成り立つ。

(クンマーの合同式)
$r_1 \equiv r_2 \not\equiv 0 \, \pmod {p-1}$ かつ $r_1 \equiv r_2 \, \pmod {p^{n-1}}$ ならば

$\left(1-p^{r_1-1} \right) \zeta(1-r_1) \equiv \left(1-p^{r_2-1} \right) \zeta(1-r_2) \, \pmod {p^n}$

となる。

(有理数 $a,b \in \mathbb{Q}$ について $a \equiv b \, \pmod {p^n}$ というのは、 $a-b$ を既約分数の形にしたときに分子が $p^n$ で割りきれることを表す。 $a,b$ が整数のときは通常の余りによる合同関係と同じになる)
ここで負の整数 $1-r = -1,-2,-3,\ldots$ について

$f(1-r) = \left(1-p^{r-1} \right) \zeta(1-r)$

とおいて、クンマーの合同式を眺めると、 $r_1 \equiv r_2 \not\equiv 0 \, \pmod {p-1}$ の部分をとりあえず無視すれば、「 $r_1$ と $r_2$ が(p進距離感で)近いと、 $f(1 - r_1)$ と $f(1 - r_2)$ が(p進距離感で)近い」と読め、何か連続性のようなものが読み取れる。
そこで負の整数 $1-r$ で $f(1-r) = \left(1-p^{r-1} \right) \zeta(1-r)$ となっている関数を、 $\mathbb{Q}_p$ から $\mathbb{Q}_p$ への連続関数に拡張できるか、を考えてみる(当然ここでの連続性はp進距離感での連続性)。
$f(1-r)$ は通常の距離感で見ると $1-r=-1,-2,-3,-4,\ldots$ というまばらな点についてしか定義されていない。そのため通常の距離感に引きずられると、 $f(1-r)$ は連続関数としてかなり好き勝手に拡張できるように見えてしまう(つまり連続関数 $f(1-r)$ を一意に決めるためには、判っている値が少なすぎるように見える)。
しかしp進距離感のもとでは負整数は密に分布しているので、これらの点だけからでも連続性について考えることができる。そしてこの場合、 $f(1-r)$ は連続関数には拡張できない。なぜかというと、クンマーの合同式に $r_1 \equiv r_2 \not\equiv 0 \, \pmod {p-1}$ という余計な条件が入っているため $r_1$ と $r_2$ が近くなっても $f(1-r_1)$ と $f(1-r_2)$ が近くなるとは限らないので。

「条件を満たす連続関数は作れない」が結論では面白くないので、条件をゆるめる。
すべての負整数 $1-r$ での値を関数の満たす条件にするのではなく、適当に1点 $r_0 \not\equiv 0 \, \pmod {p-1}$ を取り、 $r \equiv r_0 \, \pmod {p-1}$ となる整数 $r>1$ について

$f_{r_0}(1-r) = \left(1-p^{r-1} \right) \zeta(1-r)$

を満たすことを $f_{r_0}(1-r)$ の条件とする(この条件を満たす連続関数は、p進ゼータ関数(p進L関数)と呼ばれるものの一種になる)。
条件を与えている点が前の設定よりもさらにまばらになっているように見えるけれど、これらの点だけでもp進距離感ではまばらではない。
例えば $r \not\equiv r_0 \, \pmod {p-1}$ となる整数 $r$ での $f_{r_0}(1-r)$ を考えてみる。

$x_k = r + (r-r_0)(p-2)p^k$

と置くと、

$x_k - r_0 \equiv (r-r_0) \left( (p-1)p^k - (p^k -1) \right) \equiv 0 \, \pmod {p-1}$

なので $x_k \equiv r_0 \, \pmod {p-1}$ となり、 $f_{r_0}(1 - x_k)$ の値は条件で定まっている。
そして $x_k \equiv r \, \pmod{p^n}$ なので $\lim_{k \to \infty} x_k = r$ となり、関数の連続性から

$f_{r_0}(1-r) = \lim_{x_k \to \infty}f_{r_0}(1- x_k) = \lim_{x_k \to \infty}\left(1-p^{x_k-1} \right) \zeta(1-x_k)$

によって値が定まる。
そして $1-r$ が負の整数のときに限らず、 $\mathbb{Q}_p$ のある範囲で連続関数 $f_{r_0}(1-r)$ の値が定まってしまう。このことは、p進距離感が通常の距離感とズレていることの一例になっている。

(補足の補足)
ついでに、さっき出てきた

$f_{r_0}(1-r) = \lim_{x_k \to \infty}\left(1-p^{x_k-1} \right) \zeta(1-x_k)$

の $1-p^{x_k-1}$ の部分をもうすこし詳しく調べてみる。 $x_k = r + (r-r_0)(p-2)p^k$ なので

$1 - p^{x_k - 1} = 1 - p^{(r-r_0)(p-2)p^k} p^{r-1}$

となる。さらに $p^{(r-r_0)(p-2)p^k}$ の部分を評価するために、 $\omega_k(a) = a^{p^k}$ を調べる。
オイラーの定理より $a^{p^k} \equiv a^{p^{k-1}} \, \pmod {p^k}$ となるので $\omega_k(a)$ は収束する(p進距離では、隣り合う項の距離だけを見て収束発散を判定できる)。そこで

$\omega(a) = \lim_{k \to \infty} \omega_k(a)$

と定義する(これはタイヒミュラー指標と呼ばれるものになる)。ふたたびオイラーの定理より

$\omega(a)^{p-1} = \lim_{k \to \infty} a^{p^k(p-1)} = 1$

となるので、 $\omega(a)$ は $\mathbb{Q}_p$ における $1$ の $p-1$ 乗根になる。

$\begin{eqnarray} \lim_{k \to \infty} p^{(r-r_0)(p-2)p^k} & = & \lim_{k \to \infty} p^{(r-r_0)(p-1)p^k - (r-r_0)p^k} \\ & = & \lim_{k \to \infty} p^{(r-r_0)(p-1)p^k} p^{p^k(r_0 -r)} \\ & = & = \omega(p)^{r_0 - r} \end{eqnarray}$

となることを使うと $1-p^{{x_k} - 1}$ は

$\lim_{k \to \infty} \left( 1 - p^{x_k - 1} \right) = \lim_{k \to \infty} \left( 1 - p^{(r-r_0)(p-2)p^k} p^{r-1} \right) = 1 - \omega(p)^{r_0 - r } p^{r-1}$

のように収束する。

3. 因数分解形のヘンゼルの補題

ヘンゼルの補題は多項式の因数分解の形で述べられることも多い。
まずヘンゼルの補題の前提のうち $f(x_0) \equiv 0 \, \pmod p$ を

$f(X) \equiv (X-x_0)g(x) \, \pmod p$ となる。

と言い換える。もうひとつの前提 $f'(x_0) \not\equiv 0 \, \pmod p$ は

$X-x_0$ と $g(X)$ は、 $\bmod p$ のもとで互いに素である( $\bmod p$ のもとで共通因子を持たない)

と言い換えられる(なぜなら $f(X)\equiv (X-x_0)g(X)\pmod p$ を形式的に微分して $f'(x_0)\pmod p$ を求めると $g(x_0) \not\equiv 0 \, \pmod p$ が得られ、これは $\bmod p$ のもとで $g(X)$ が $X-x_0$ を因数としないことを示しているので)。
そして結論の

$f(x_k) \equiv 0 \, \pmod {p^{k+1}} \\ x_k \equiv x_{k-1} \, \pmod {p^k}$
を満たす $x_k$ が取れる

というのを書き換えると、

$f(X) \equiv (X-x_k)g_k(X) \, \pmod {p^{k+1}} \\ X-x_k \equiv X - x_{k-1} \, \pmod {p^k}$
を満たす $x_k$ と $g_k(X)$ が取れる

となる。これは機械的に書き換えただけなので何か不自然な感じになっているけれど、もっと一般化した形でだいたい次のようなことが成り立つ。

(ヘンゼルの補題)
$f(X)$ が $\bmod p$ で

$f(X) \equiv g_0(X) h_0(X) \, \pmod p$

と因数分解でき、 $g_0(X)$ と $h_0(X)$ が $\bmod p$ のもとで互い素なら

$\begin{eqnarray} f(X) & \equiv & g_k(X) h_k(X) \, \pmod {p^{k+1}} \\ g_{k}(X) & \equiv & g_{k-1}(X) \, \pmod {p^{k}} \\ h_{k}(X) & \equiv & h_{k-1}(X) \, \pmod {p^{k}} \end{eqnarray}$