https://tsujimotter.hatenablog.com/entry/proof-of-hensels-lemma-and-newton-method

今日のテーマはヘンゼルの補題です。

ヘンゼルの補題は、 $p$ 進数における方程式の解の存在に関わる定理で、このブログの過去の記事でも紹介したことがありました。
tsujimotter.hatenablog.com

「7進法人間」の記事では、定理の主張の紹介にとどめて、証明までは紹介していません。今回は証明まで踏み込んで紹介したいと思います。

ところで、前回の記事でニュートン法を用いた実数解の近似について紹介しました。
tsujimotter.hatenablog.com

方程式の実数解と、方程式の $p$ 進数解については、一見関連がなさそうに見えますが、実は両者が関係するのです。

ヘンゼルの補題の解を構成するのに、なんとニュートン法が関係するのです。ぜひ最後までご覧ください。

ヘンゼルの補題の主張（復習）

改めてヘンゼルの補題の主張を振り返ります。

ざっくり言ってしまうと、ある整数係数の多項式 $F(X)$ の $\bmod{p^n}$ における根の存在を保証する定理です。

定理（ヘンゼルの補題）

$p$ を素数とする．整数係数の多項式 $F(X)$ に対して，

$F(x_n) \equiv 0 \pmod{p^n}$ かつ $F'(x_n) \not\equiv 0 \pmod{p}$

なる整数 $x_n$ が存在するならば， $x_{n+1} \equiv x_{n} \pmod{p^n}$ を満たす整数 $x_{n+1}$ が $\bmod{p^{n+1}}$ で一意的に存在し

$F(x_{n+1}) \equiv 0 \pmod{p^{n+1}} \tag{1}$

を満たす．

見てほしいポイントは、この定理が

「 $x_n$ が存在するならば、 $x_{n+1}$ が存在する」

という形になっているという点です。

つまり、合同式

$F(X) \equiv 0 \pmod{p^n}$

の解 $X \equiv x_n\pmod{p^n}$ が条件を満たせば、 $n$ を一つ進めた合同式

$F(X) \equiv 0 \pmod{p^{n+1}}$

の解 $X \equiv x_{n+1}\pmod{p^{n+1}}$ も構成できるという主張です。

「7進法人間」の記事では、元の方程式を

$\displaystyle F(X) = X^2 - 2 = 0 \tag{2}$

として、この $\bmod{p}$ の解 $x_1$ から、 $\bmod{p^2}$ の解 $x_2$ 、 $\bmod{p^3}$ の解 $x_3$ 、 $\bmod{p^4}$ の解 $x_4$ 、 $\ldots$ と順に解を構成することを示しました。ヘンゼルの補題は、このような解がいつまでも構成し続けられることを保証しています。

結果的に、これらをまとめることで $p$ 進数解を得ることができるというわけです。

ヘンゼルの補題の具体例（復習）

$p = 7$ として再度具体的な解を計算してみましょう。復習の位置付けですが、この計算は後で証明の際のイメージを得るのに実は役に立ちます。

まず、合同式

$F(X) = X^2 - 2 \equiv 0 \bmod{7}$

の解を考えます。

$3^2 - 2 \equiv 9 - 2 \equiv 7 \equiv 0 \bmod{7}$

$4^2 - 2 \equiv 16 - 2 \equiv 14 \equiv 0 \bmod{7}$

となるので、 $\bmod{7}$ の解は $X \equiv 3, 4 \pmod{7}$ の2つあります。
（「7進法人間」の記事では $X \equiv 3$ の方を見落としていました。）

そこで、 $x_1 = 3$ または $x_1 = 4$ のときで場合分けを行い、それぞれのケースでヘンゼルの補題で解を持ち上げたいと思います。

(i) $x_1 = 3$ のとき：

$F'(X) = 2X$ であり、 $F'(x_1) = 2\cdot 3 \not\equiv 0 \pmod{7}$ が成り立つので、ヘンゼルの補題より $\bmod{p^2}, \; \bmod{p^3}, \; \bmod{p^4}, \; \ldots$ に持ち上げた解が存在します。

実際、 $\bmod{7^2}$ の解 $x_2$ は、 $x_2 \equiv x_1 \pmod{7}$ の条件を元に探せばよいので

$x_2 = 3 + A\cdot 7$ （ $0 \leq A \leq 7 - 1$ ）

と置いて探します。すると、 $A = 1$ のとき

$F(x_2) = F(10) = 10^2 - 2 = 98 = 2\cdot \mathbf{7^2} \equiv 0 \pmod{7^2}$

より、 $\bmod{7^2}$ の解 $x_2 = 10$ が見つかります。

同様に、 $\bmod{7^3}$ の解 $x_3$ は、 $x_3 \equiv x_2 \pmod{7^2}$ の条件を元に探せばよいので

$x_3 = 10 + A\cdot 7^2$ （ $0 \leq A \leq 7 - 1$ ）

とおいて考えると、 $A = 2$ のとき

$F(x_3) = F(108) = 108^2 - 2 = 11662 = 34 \cdot \mathbf{7^3} \equiv 0 \pmod{7^3}$

より、 $\bmod{7^3}$ の解 $x_3 = 108$ が見つかります。

こんな要領で以下同様に続けることができます：

$F(2166) = 2166^2 - 2 = 4691554 = 1954 \cdot \mathbf{7^4} \equiv 0 \pmod{7^4}$
より $\bmod{7^4}$ の解は $x_4 = 2166$ 。

$F(4567) = 4567^2 - 2 = 20857487 = 1241 \cdot \mathbf{7^5} \equiv 0 \pmod{7^5}$
より $\bmod{7^5}$ の解は $x_5 = 4567$ 。

と続けていくことができます。

したがって、 $7$ 進整数環 $\mathbb{Z}_7$ において

$\mathbf{x} = (3, \; 10, \; 108, \; 2166, \; 4567, \; \ldots) \in \mathbb{Z}_7$

という数は存在し、これは $\mathbb{Z}_7$ における方程式

$F(\mathbf{x}) = \mathbf{x}^2 - 2 = 0$

の解となります。

(ii) $x_1 = 4$ のとき：

同様に、 $F'(x_1) = 2\cdot 4 \not\equiv 0 \pmod{7}$ が成り立つので、ヘンゼルの補題より $\bmod{p^2}, \; \bmod{p^3}, \; \bmod{p^4}, \; \ldots$ に持ち上げた解が存在します。

すなわち $\bmod{7^{n+1}}$ の解 $x_{n+1}$ を

$x_{n+1} = x_{n} + A\cdot 7$ （ $0 \leq A \leq 7 - 1$ ）

と置いて探していくと、順次解が見つかります。

$F(39) = 39^2 - 2 = 1519 = 31 \cdot \mathbf{7^2} \equiv 0 \pmod{7^2}$
より $\bmod{7^2}$ の解は $x_2 = 39$ 。

$F(235) = 235^2 - 2 = 55223 = 23 \cdot \mathbf{7^4} \equiv 0 \pmod{7^3}$
より $\bmod{7^3}$ の解は $x_3 = 235$ 。

上の合同式より $\bmod{7^4}$ の解は $x_4 = 235$ 。

$F(12240) = 12240^2 - 2 = 14981759 = 8914 \cdot \mathbf{7^5} \equiv 0 \pmod{7^5}$
より $\bmod{7^5}$ の解は $x_5 = 12240$ 。

したがって、 $7$ 進整数環 $\mathbb{Z}_7$ において

$\mathbf{x} = (4, \; 39, \; 235, \; 235, \; 12240, \; \ldots) \in \mathbb{Z}_7$

という数は存在し、これは $\mathbb{Z}_7$ における方程式

$F(\mathbf{x}) = \mathbf{x}^2 - 2 = 0$

の解となります。

解が上に上に伸びていく様子は次の図のように表されます：

ヘンゼルの補題が保証しているのは「一つの始点があれば、そこから枝分かれせず一本の線が無限に伸び続けること」です。

本題：ヘンゼルの補題の証明

ヘンゼルの補題の証明のためのアイデアは意外にシンプルです。

すなわち、解を求めたい方程式を定義する整係数多項式 $F(X)$ を具体的に

$\displaystyle F(X) = \sum_{k=0}^{d} a_k X^k \tag{3}$

とおいて、候補となる解を上の式に代入することで示されます。ここで $\operatorname{deg} F(X) = d$ としています。

まず $x_{n+1} = x_{n} + Ap^{n}$ （ $A$ は $0 \leq A \leq p-1$ なる整数）と置きます。すると、

$x_{n+1} \equiv x_{n} \pmod{p^{n}} \tag{4}$

を満たします。

この置き方は、前節の具体例の計算で行ったのとまったく同じことをやっています。

これを $F(X)$ に代入して、 $\bmod{p^{n+1}}$ で考えると

$\displaystyle \begin{align*} F(x_{n+1}) &\equiv \sum_{k=0}^{d} a_k x_{n+1}^k \\ &\equiv \sum_{k=0}^{d} a_k (x_{n} + Ap^{n})^k \\ &\equiv \sum_{k=0}^{d} a_k (x_{n}^k + kAp^{n}x_{n}^{k-1} + \cdots ) \\ &\equiv \sum_{k=0}^{d} a_k (x_{n}^k + kAp^{n}x_{n}^{k-1}) \\ &\equiv \sum_{k=0}^{d} a_k x_{n}^k + Ap^{n} \sum_{k=0}^{d} ka_k x_{n}^{k-1} \\ &\equiv F(x_n) + Ap^{n} F'(x_n) \pmod{p^{n+1}} \end{align*}$

2行目から3行目は、二項展開

$(X + Y)^k = X^k + kX^{k-1}Y^1 + \cdots$

を $(x_{n} + Ap^{n})^k$ に適用したものです。

3行目から4行目についてですが、二項展開の第3項以降は $(p^n)^2, (p^n)^3, \ldots$ が掛かってくるので、 $\bmod{p^{n+1}}$ をとると第3項目以降がすべて消えることから分かります。

ここで仮定 $F(x_n) \equiv 0 \pmod{p^n}$ より

$F(x_n) = B p^n$

と置きます。すると合同式

$\displaystyle F(x_{n+1}) \equiv (B + A F'(x_n)) p^{n} \pmod{p^{n+1}} \tag{5}$

が得られます。

ここで $F(x_{n+1}) \equiv 0 \pmod{p^{n+1}}$ となるための条件は

$B + A F'(x_n) \equiv 0 \pmod{p} \tag{6}$

です。

合同式 $(6)$ を満たす $A$ は $\bmod{p}$ で一意的に取れ、 $\bmod{p^{n+1}}$ における $F'(x_n)$ の逆元 $F'(x_n)^{-1}$ を用いて

$A \equiv -B\cdot F'(x_n)^{-1} \pmod{p} \tag{7}$

と表せることが、次の枠内の議論によりわかります。
（枠内の議論で仮定「 $F'(x_n) \not\equiv 0 \pmod{p}$ 」を用いることに注意。）

仮定 $F'(x_n) \not\equiv 0 \pmod{p}$ より、 $F'(x_n)$ と $p^n$ は互いに素です。ユークリッドの互除法から

$F'(x_n) \cdot U + p^{n+1} V = 1 \tag{8}$

を満たす整数 $U, V$ が取れます。これはユークリッドの互除法からしたがいます。よって、 $\bmod{p^{n+1}}$ をとると

$F'(x_n) \cdot U \equiv 1 \pmod{p^{n+1}}$

を満たす $U$ が取れます。この $U$ は $\bmod{p^{n+1}}$ における $F'(x_{n})$ の逆元だと思うことができますので、 $U = F'(x_n)^{-1}$ とおきます。

もちろん、 $F'(x_n)^{-1}$ は $\bmod{p}$ における $F'(x_n)$ の逆元でもあります（式 $(8)$ で $\bmod{p}$ をとればよい）。よって、式 $(6)$ の両辺に $F'(x_n)^{-1}$ を掛けて

$A \equiv -B\cdot F'(x_n)^{-1} \pmod{p} \tag{7再掲}$

が得られます。すなわち、 $F(x_{n+1}) \equiv 0 \pmod{p^{n+1}}$ の必要十分条件 $(6)$ を満たす $A$ が $\bmod{p}$ で一意的に得られました。

以上をまとめると、 $F(x_{n+1}) \equiv 0 \pmod{p^{n+1}}$ かつ $x_{n+1} \equiv x_n \pmod{p^n}$ を満たす $x_{n+1}$ は $\bmod{p^{n+1}}$ で一意的に定まり

$x_{n+1} \equiv x_n - F(x_n) \cdot F'(x_n)^{-1} \pmod{p^{n+1}} \tag{9}$

と表されます。

ニュートン法との関係とp進距離

実は、先ほど得られたヘンゼルの補題の解を構成する合同式 $(9)$ は、ニュートン法の $p$ 進的な類似における更新式だと考えることができます。

$x_{n+1} \equiv x_n - F(x_n) \cdot F'(x_n)^{-1} \pmod{p^{n+1}} \tag{9再掲}$

実数値関数に関するニュートン法を思い出すと、実数値関数 $f(x)$ について、 $f(x) = 0$ を満たす解を求める方法でした。

具体的には、適当な解候補 $x = x_0$ を定めて、これを漸化式

$\displaystyle x_{n+1} = x_n - f(x_n) \cdot f'(x_n)^{-1} \tag{10}$

によって順次更新していくというものでした。

実数値を考えているか $\bmod{p^{n+1}}$ を考えているかを除けば、式の形が完全に対応していますね。

実数値のニュートン法では、 $x = x_0, x_1, x_2, x_3, \ldots$ と更新していくことで、徐々に $f(x_n)$ の値が $0$ に近づいていきます。

実際、 $f(x) = x^2 - 2$ の場合、 $x_0 = 2$ からスタートして

$x_0 = 2$

$x_1 = 1.5$

$x_2 = 1.416666667$

$x_3 = 1.414215686$

$x_4 = 1.414213562$

$x_5 = 1.414213562$

と計算されますが、これに対応する $f(x)$ の値は

$f(x_0) = 2$

$f(x_1) = 0.25$

$f(x_2) = 0.00694444\ldots$

$f(x_3) = 0.00000000\ldots$

$f(x_4) = 0.00000000\ldots$

$f(x_5) = 0.00000000\ldots$

となり $0$ に近づいていきます。

これにより、 $f(x) = 0$ の解を近似的に得ることができるのでした。

一方、ヘンゼルの補題についてはどうでしょうか。

$F(X) = X^2 - 2$ において、 $x_1 = 3$ から始まる解について考えると

$x_1 = 3$

$x_2 = 10$

$x_3 = 108$

$x_4 = 2166$

$x_5 = 4567$

となり、これに対応する $F(X)$ の値は次のようになります：

$F(x_1) = 7$

$F(x_2) = 98$

$F(x_3) = 11662$

$F(x_4) = 4691554$

$F(x_5) = 20857487$

これを数直線上で表現すると次の図のようになります。

数直線上では、だんだんと $0$ から離れていくように見えて、とても $0$ に収束していくようには見えません。

実は、ヘンゼルの補題の更新式において収束を考える上では、「通常の距離」ではなく「別の距離」を考えるのが適切だったということなのです。

実際、ここで考えるべきなのは、「p進距離」と呼ばれる距離です。

数直線上で通常用いられる距離はユークリッド距離ですが、これは数直線上の実数 $x, y$ に対し

$d(x, y) = |x - y|$

で定まる距離でした。ここで右辺の $|\cdot |$ は通常の意味での絶対値です。

一方の $p$ 進距離は、通常の絶対値の代わりに「 $p$ 進絶対値」を用いて定義されます。

整数を $x = u p^n$ （ $u$ は $p$ で割り切れない数）とするとき、 $p$ 進絶対値 $|\cdot |_p$ は

$\displaystyle |x|_p = \frac{1}{p^n}$

によって定義されます。要するに、 $p$ で割り切れる回数 $n$ が多ければ多いほど、絶対値は $0$ に近くなります。

この $p$ 進絶対値 $|\cdot |_p$ によって

$d_p(x, y) = |x - y|_p$

で定めるのが $p$ 進距離です。

「 $x, y$ の差が $p$ で割り切れる回数が多いほど近い」という新しい距離感を与えているものだと考えてください。

今回考えているのは $p = 7$ における $7$ 進距離ですが、このとき $0$ と $343 = 7^3$ は

$\displaystyle |343 - 0|_7 = |343|_7 = |7^3| = \frac{1}{7^3} = 0.0029154\ldots$

なので両者は割と近くにいます。一方で $0$ と $1$ は、 $1 - 0 = 1$ が $7$ で割り切れないので

$\displaystyle |1 - 0|_7 = |1|_7 = \frac{1}{7^0} = 1$

となり、両者は相対的にかなり遠くなります（距離が343倍も違います）。

このように定義された $7$ 進距離における「距離感」の下では、ヘンゼルの補題の更新式は、まさに $F(x_n)$ の値は徐々に $0$ に近づいていくといえます。

実際、先の計算結果において「 $7$ で割り切れる回数」を考えてみると

$F(x_1) = \mathbf{7^1}$

$F(x_2) = 98 = 2 \cdot \mathbf{7^2}$

$F(x_3) = 11662 = 34 \cdot \mathbf{7^3}$

$F(x_4) = 4691554 = 1954 \cdot \mathbf{7^4}$

$F(x_5) = 20857487 = 1241 \cdot \mathbf{7^5}$

となります。 $7$ 進絶対値で $0$ と $F(x_n)$ の距離を測ると次のようになります：

$\displaystyle |F(x_1) - 0|_7 = \frac{1}{7}$

$\displaystyle |F(x_2) - 0|_7 = \frac{1}{7^2}$

$\displaystyle |F(x_3) - 0|_7 = \frac{1}{7^3}$

$\displaystyle |F(x_4) - 0|_7 = \frac{1}{7^4}$

$\displaystyle |F(x_5) - 0|_7 = \frac{1}{7^5}$

$7$ のべきが大きくなっていますので、「7進距離」の下ではだんだんと $F(x_n)$ は $0$ に近づいていくということがわかりますね。

図に表すと次のようになります：

すなわち、ヘンゼルの補題の更新式は $p$ 進的なニュートン法であり、更新式を用いることで $F(X) = 0$ の解 $x$ に「 $p$ 進的に」近い解を得ることができる数値計算手法だったというわけです。

面白いですね！

以上で今日の話はおしまいですが、最後まで読んでいただきありがとうございます。

それでは今日はこの辺で！