Henselの補題
概要
Henselの補題（Hensel's lemma）とは、多項式の法 $p$ の単純根を各法 $p^n$ の根へ一意に持ち上げ、完備な $p$ 進整数環 $\mathbb Z_p$ の根にする定理である。単純根は $f(a)\equiv0\pmod p$ かつ $f'(a)\not\equiv0\pmod p$ で判定する。一桁ずつの持ち上げでは各段階で一次合同式を解く。同じ根を $p$ 進 Newton 反復 $a\mapsto a-f(a)/f'(a)$ で求めると、導関数が単元であるため反復を続けられ、正しい桁数は少なくとも倍になる。例えば $X^2-2$ の法 $7$ の根 $3$ は法 $49$ で $10$、さらに $7$ 進整数の平方根へ持ち上がる。
整数係数の多項式について、法 $p$ で解を見つけたとき、その解は法 $p^2,p^3,\ldots$ でも解にできるだろうか。一般にはできない。しかし法 $p$ での解が単純根、すなわち導関数が $p$ で割り切れない根なら、解は各段階で一意に持ち上がる。すべての段階の解を合わせると、$p$ 進整数環 $\mathbb Z_p$ における本当の根が得られる。これが Hensel の補題（Hensel's lemma）の基本形である。
実数上のNewton法は、近似根から接線を使って次の近似根を作る。$p$ 進数でも同じ式を使える。ただし近さは通常の絶対値でなく $p$ 進付値で測る。単純根から始めると、Newton の各反復で正しい $p$ 進桁数が少なくとも倍になる。有限の合同式の解を一桁ずつ持ち上げる方法と、この速い反復は、同じ現象を二つの精度で見たものである（Neu99 第 II 章 §4）。
定義と主張
$p$ を素数とする。整数 $a,b$ について $a\equiv b\pmod {p^n}$ は $p^n$ が $a-b$ を割り切ることを表す。$p$ 進整数環 $\mathbb Z_p$ は、整合的な剰余類の列
$$
(a_n)_{n\geq1},\qquad a_n\in\mathbb Z/p^n\mathbb Z,\qquad
a_{n+1}\equiv a_n\pmod {p^n}
$$
とみなせる。$x\in\mathbb Z_p$ が $0$ に近いとは、$x$ が高い $p$ の冪で割り切れることである。$x\ne0$ に対する $v_p(x)$ は $x$ を割り切る $p$ の最大冪の指数であり、$v_p(0)=+\infty$ と約束する（p進数、p進付値）。
$f\in\mathbb Z_p[X]$ に対し、$\bar a\in\mathbb F_p=\mathbb Z/p\mathbb Z$ が $f$ の単純根であるとは
$$
f(\bar a)=0,\qquad f'(\bar a)\ne0\quad\text{in }\mathbb F_p
$$
が成り立つことをいう。係数と $a\in\mathbb Z_p$ を法 $p$ へ還元して評価している。$f'(\bar a)\ne0$ は、任意の持ち上げ $a$ に対して $f'(a)$ が $\mathbb Z_p$ の単元であることと同値である。
$f\in\mathbb Z_p[X]$ と $a_0\in\mathbb Z_p$ が
$$
f(a_0)\equiv0\pmod p,\qquad f'(a_0)\not\equiv0\pmod p
$$
を満たすとする。このとき
$$
f(\alpha)=0,\qquad \alpha\equiv a_0\pmod p
$$
を満たす $\alpha\in\mathbb Z_p$ がただ一つ存在する。また各 $n\geq1$ について、$a_0\bmod p$ と一致する法 $p^n$ の根もただ一つであり、これらは $\alpha\bmod p^n$ に等しい。
ここで「ただ一つ」は、指定した法 $p$ の剰余類の中での一意性である。$f$ に別の単純根が法 $p$ で存在すれば、その剰余類からは別の $p$ 進根が得られる。係数が $\mathbb Z$ にある場合は、$f'(a_0)\not\equiv0\pmod p$ は整数 $f'(a_0)$ と $p$ が互いに素であるという初等的な条件になる。
一桁ずつの持ち上げ
まず有限の合同式だけで補題を証明する。この方法は、所定の法 $p^n$ における整数の解を実際に計算するときに使いやすい。$f$ の係数が $\mathbb Z_p$ の場合も、各係数を必要な法 $p^{n+1}$ に還元すれば同じ計算ができる。
$n\geq1$ とし、$a_n\in\mathbb Z/p^n\mathbb Z$ が $f(a_n)\equiv0\pmod {p^n}$、$f'(a_n)\not\equiv0\pmod p$ を満たすとする。$a_n$ を法 $p^{n+1}$ へ持ち上げる剰余類の中に、$f$ の根 $a_{n+1}$ がちょうど一つある。
$a_n$ の代表を一つ選び、$f(a_n)=p^n u$ と書く。法 $p^{n+1}$ での持ち上げは $a_n+p^nt$（$t\in\mathbb F_p$）で尽くされる。多項式の展開で次数 $2$ 以上の項には $p^{2n}$ が付く。$2n\geq n+1$ だから
$$
f(a_n+p^nt)\equiv p^n\bigl(u+t f'(a_n)\bigr)
\pmod {p^{n+1}}.
$$
従って必要十分な条件は $u+t f'(a_n)\equiv0\pmod p$ である。$f'(a_n)$ は法 $p$ で可逆なので、$t\in\mathbb F_p$ は一意に定まる。新しい代表は $a_n$ と法 $p$ で一致するため、導関数の単元条件も保たれる。
主定理の証明．$a_0\bmod p$ を最初の根 $a_1$ として、命題を $n=1,2,\ldots$ と順に適用する。解の列は $a_{n+1}\equiv a_n\pmod {p^n}$ を満たすので、上に述べた $\mathbb Z_p$ の表示から一つの $\alpha$ を定める。各 $n$ で $f(\alpha)\equiv f(a_n)\equiv0\pmod {p^n}$ であり、すべての $p^n$ で割り切れる $p$ 進整数は $0$ だけだから $f(\alpha)=0$。別の根 $\beta\equiv a_0\pmod p$ があれば、その各法 $p^n$ の像も一段階の持ち上げの一意性により $a_n$ と一致し、$\beta=\alpha$ である。
一段階の計算では、法 $p^n$ まで正しい根に一つの新しい $p$ 進数字 $t$ を付け加える。この意味で Hensel の補題は、有限法での根の計算法と、完備な環における根の存在定理を同時に与える。完備性は最後の「すべての桁を合わせて $\alpha$ にする」段階で使った。有限個の持ち上げだけなら $\mathbb Z/p^n\mathbb Z$ の算術で完結する。
p 進 Newton 反復
単純根条件の下では、$f'(a)$ は $a\equiv a_0\pmod p$ の範囲で常に単元である。そこで
$$
N_f(a)=a-\frac{f(a)}{f'(a)}
$$
を $\mathbb Z_p$ の中で定め、$a_{r+1}=N_f(a_r)$ と反復する。除算が許されるのは分母が単元だからであり、一般の重根からはこの反復を始められない。
$m=v_p(f(a))\geq1$、$f'(a)\in\mathbb Z_p^\times$ とし、$b=N_f(a)$ とおく。このとき
$$
b\equiv a\pmod {p^m},\qquad
v_p(f(b))\geq2m,\qquad
f'(b)\in\mathbb Z_p^\times.
$$
従って $a_0$ からの反復は $\mathbb Z_p$ の一つの根に収束し、$r$ 回目には少なくとも法 $p^{2^r}$ で正しい。
$h=-f(a)/f'(a)$ と書けば、$f'(a)$ は単元なので $v_p(h)=m$ である。整数係数、より一般に $\mathbb Z_p$ 係数の多項式には
$$
f(a+h)=f(a)+h f'(a)+h^2g(a,h)
$$
を満たす $g(a,h)\in\mathbb Z_p$ がある。$b=a+h$ とすると最初の二項が消え、$f(b)=h^2g(a,h)$ だから $v_p(f(b))\geq2m$ となる。また $b\equiv a\pmod p$ なので $f'(b)\equiv f'(a)\not\equiv0\pmod p$ である。帰納法で $v_p(f(a_r))\geq2^r$、従って $v_p(a_{r+1}-a_r)\geq2^r$。差が $p$ 進的に $0$ へ向かうので $a_r$ は Cauchy 列であり、$\mathbb Z_p$ の完備性から $\alpha$ に収束する。多項式の連続性により $f(\alpha)=0$。$a_r\equiv a_0\pmod p$ も保たれ、主定理の一意性からこの $\alpha$ は先ほど一桁ずつ構成した根である。
「精度倍増」とは、$f(a)\equiv0\pmod {p^m}$ のとき、一回で $f(b)\equiv0\pmod {p^{2m}}$ が得られるという意味である。単純根の剰余類内では根との距離についても同じ評価になる。実際、根 $\alpha$ と $a$ が法 $p$ で一致すれば、多項式の差は $f(a)-f(\alpha)=(a-\alpha)u$ と書け、$u\equiv f'(a_0)\pmod p$ は単元である。ゆえに $v_p(f(a))=v_p(a-\alpha)$ である。この等式により、式の値が $p^m$ で割り切れることは、近似値の最初の $m$ 桁が正しいことに等しい。
同じ Newton の式を実数上で使うときは、初期値が根に十分近いか、途中で分母が小さくならないかを調べる。ここでは最初の法 $p$ の単純根条件だけで、各段階の分母が単元であることと収束が保証される。収束は通常の大小やグラフの接線の図でなく、$p$ 進付値が増えることによって表される。
導関数が単元でない近似根
単純根版より広い Newton 型の条件もある。ここでは $f'(a)$ が $p$ で割り切れても、$f(a)$ がそれより十分強く $p$ で割り切れれば反復を開始できることを述べる。これは「法 $p$ で重根なら何も言えない」という意味ではないことを明らかにする。
$f\in\mathbb Z_p[X]$、$a\in\mathbb Z_p$ とし、$d=v_p(f'(a))<+\infty$、$m=v_p(f(a))<+\infty$ とする。$m>2d$ なら、$f(\alpha)=0$ かつ
$$
v_p(\alpha-a)=m-d
$$
を満たす $\alpha\in\mathbb Z_p$ が存在する。さらに $v_p(x-a)>d$ を満たす範囲ではこの根は一意である。
最初の Newton 差 $h=-f(a)/f'(a)$ は $v_p(h)=m-d>d$ なので $h\in\mathbb Z_p$ である。$a_1=a+h$ とおくと、先ほどの多項式展開により $m_1:=v_p(f(a_1))\geq2(m-d)$。また $f'(a_1)-f'(a)$ は $h$ で割り切れる。$v_p(h)>d$ だから $v_p(f'(a_1))=d$ のままである。同じ議論を反復する。途中で $f(a_r)=0$ となればそこで止めてよい。そうでなければ $\delta_r:=m_r-2d$ とおいて
$$
\delta_{r+1}\geq2\delta_r,\qquad
v_p(a_{r+1}-a_r)=m_r-d=d+\delta_r.
$$
従って差の付値は無限大へ向かい、反復列は完備な $\mathbb Z_p$ で根 $\alpha$ に収束する。最初の差の付値は $m-d$、後の差の付値はそれより大きいので、$v_p(\alpha-a)=m-d$ となる。一意性については、$x,y\equiv a\pmod {p^{d+1}}$ なら $(f(x)-f(y))/(x-y)$ は $f'(a)$ と法 $p^{d+1}$ で合同であり、付値は $d$ である。従って $f(x)=f(y)=0$ なら $x=y$ である。
$d=0$ のとき条件 $m>2d$ は $m\geq1$ に等しく、主定理の単純根版に戻る。$d>0$ の場合の「一意」は法 $p$ の剰余類全体ではなく、より小さい球 $a+p^{d+1}\mathbb Z_p$ の中での一意性である。この違いを落とすと、重根の状況で誤った一意性を主張することになる。
計算例と使い方
$f(X)=X^2-2$ とし、$p=7$ をとる。$f(3)=7$、$f'(3)=6\not\equiv0\pmod7$ だから、$3\bmod7$ は単純根である。一桁持ち上げるには $x=3+7t$ と置く。
$$
f(3+7t)=7+42t+49t^2\equiv7(1+6t)\pmod {49}.
$$
$1+6t\equiv0\pmod7$ から $t\equiv1\pmod7$、従って根は $x\equiv10\pmod {49}$ となる。Newton の式では
$$
N_f(3)=3-\frac{7}{6}=\frac{11}{6}\equiv10\pmod {49}.
$$
ここで $6$ は $7$ 進単元なので分数は $\mathbb Z_7$ の元である。次の反復を続けると
$$
N_f\!\left(\frac{11}{6}\right)=\frac{193}{132}
\equiv2166\pmod {7^4},\qquad 2166^2\equiv2\pmod {7^4}.
$$
最初の反復で法 $7^2$、次で法 $7^4$ の精度になった。法 $7$ のもう一方の単純根 $4\equiv-3$ からは、異なる $7$ 進根 $-\alpha$ が得られる。
一桁ずつ持ち上げる方法では、同じ根の代表は法 $7,7^2,7^3,7^4$ に対して順に $3,10,108,2166$ となる。例えば $10+49t$ を法 $7^3$ へ代入すると $f(10)=49\cdot2$ と $f'(10)\equiv6\pmod7$ から $2+6t\equiv0\pmod7$、すなわち $t\equiv2$ を得る。次は $108+343t$ として同じ一次合同式を解く。この四つの整数は別々の根ではなく、同じ $7$ 進整数 $\alpha$ の精度の異なる表示である。
$p$ を奇素数、$u\in\mathbb Z_p^\times$ とする。$u$ が $\mathbb Z_p$ で平方数であることと、$u\bmod p$ が $\mathbb F_p$ で平方数であることは同値である。
$u=x^2$ なら法 $p$ へ還元して必要性が従う。逆に $\bar x^2=\bar u$ を満たす $\bar x\in\mathbb F_p$ があれば、$u$ が単元なので $\bar x\ne0$ である。$p$ は奇数だから $f(X)=X^2-u$ の導関数 $f'(\bar x)=2\bar x$ は $0$ でない。主定理により $\bar x$ は $\mathbb Z_p$ の根に一意に持ち上がる。
この系は平方剰余の判定を $p$ 進の方程式へ移す。例えば $2$ は法 $7$ で $3^2$ に等しいため、上の例のとおり $\mathbb Z_7$ で平方根をもつ。一方、法 $p$ で平方根がない単元は、$\mathbb Z_p$ でも平方根をもたない。$p=2$ では $f'(x)=2x$ が常に $2$ で割り切れるため、この単純根の系は使えない。$2$ 進数の平方根には、より細かい法 $8$ での判定が必要になる。
有限の合同式を解く目的なら、すべての法 $p$ の根をまず列挙する。単純根はそれぞれ一意に法 $p^n$ まで持ち上がる。法 $p$ の根がすべて単純なら、各 $n$ における根の個数は法 $p$ の根の個数と同じである。さらに法が互いに素な複数の素数冪の積であれば、各素数冪で求めた解を中国剰余定理で貼り合わせられる。この手順は剰余環の計算であり、$\mathbb Z_p$ に移らずに有限段階だけを使ってもよい。
条件を外すときの注意
$f(X)=X^2$ の法 $p$ の根 $0$ は $f'(0)=0$ を満たす。法 $p^2$ では $0,p,2p,\ldots,(p-1)p$ のすべてが根であり、法 $p$ の一つの根から $p$ 個の根が生じる。従って単純根条件なしに一意性は主張できない。$\mathbb Z_p$ での根自体は $0$ だけであっても、有限の各段階での持ち上げは一意とは限らない。
$f(X)=X^2-p$ では $0\bmod p$ が根だが、導関数 $2X$ はそこで $0$ である。$x\equiv0\pmod p$ として $x=py$ を代入すると $f(x)=p(py^2-1)$ であり、これは $p^2$ で割り切れない。従って法 $p^2$ への持ち上げは一つもない。実際、$x^2=p$ を満たす $x\in\mathbb Q_p$ もない。左辺の付値は偶数、右辺の付値は $1$ だからである。
この二つの例は、単純根条件が単なる技術上の仮定ではないことを示す。ただし導関数が法 $p$ で $0$ でも根が持ち上がる場合はある。例えば $X^2$ の $0$ はそのまま $\mathbb Z_p$ の根である。主定理は単純根に対する十分条件であり、重根の完全な分類ではない。
一般の Hensel の補題には、多項式を法 $p$ で互いに素な因子に分解できるときの因子分解の持ち上げや、導関数が単元でない場合にも $v_p(f(a))$ が十分大きければ根を得る形がある（Neu99 第 II 章 §4）。これらは単純根版を包含・拡張するが、ここで証明した精度倍増は分母が単元という明確な状況に絞ったものである。局所環を一般化した Hensel 局所環 では、剰余体上の単純根を持ち上げられることを性質の一つとして捉える。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
