ヘンゼルの補題とは？わかりやすく解説

数学のヘンゼルの補題（ヘンゼルのほだい、英: Hensel's lemma）とは、1変数多項式が素数 $p$ を法として単根（英語版）を持つならば、その根は $p$ の任意の冪乗を法とする根に一意的に持ち上げられるという、合同算術における補題である。この補題は、多項式が法 $p$ で2つの互いに素な多項式（英語版）に因数分解できるならば、その因数分解は $p$ の任意の冪乗を法とする因数分解に持ち上げることができるという補題に一般化できる。因数分解に現れる多項式の次数が1の場合が根の場合に相当する。ヘンゼルの持ち上げ補題（英: Hensel's lifting lemma）とも呼ばれる。名称はクルト・ヘンゼルに因む。

$p$ の冪指数を無限に大きくしていったときの（射影極限の意味での）極限を取ることにより、法 $p$ での根（または因数分解）を $p$ 進整数上での根（または因数分解）に持ち上げることができる。

この補題は、任意の可換環を係数とする多項式に対して、 $p$ をイデアル、「互いに素な2つの多項式」を「2つの多項式が生成するイデアルが1を含む」に置き換えることにより一般化できる。一般化された補題も同じ名前で呼ばれる。

ヘンゼルの補題は、解析的整数論の一分野である $p$ 進解析学の基礎である。

ヘンゼルの補題の証明は構成的（英語版）であり、証明からヘンゼル持ち上げの効率的なアルゴリズムが得られる。これは多項式の因数分解のアルゴリズムの基礎である。また有理数体上の線型代数学についての最も効率の良いアルゴリズムが得られる^{[要検証 – ノート]}。

ヘンゼルの補題は、ヘンゼルよりも早く1846年にテオドル・シェーネマン（英語版）によって証明されていた^[1]。また、「存在」についての主張だけならシェーネマンよりも早くカール・フリードリヒ・ガウスによっても知られていた^[2]。

還元と持ち上げ

還元と持ち上げを図で表したもの。還元は何の困難もなく行えるが、持ち上げは可能ではないこともある。また、可能であっても一意でないこともある。

もともとのヘンゼルの補題は、整数を係数とする多項式の因数分解と、素数 $p$ 、もしくはその冪乗を法とする剰余類環を係数とする多項式の因数分解との関係についてのものであった。素数 $p$ を極大イデアルに置き換えることで、この補題は整数から任意の可換環へそのまま一般化できる（ $\mathbb {Z}$

この節は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方）
出典検索^?: "ヘンゼルの補題" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2021年12月）

仮定は今までと同じとし、既約多項式

f(x)=a_{0}+a_{1}x+\cdots +a_{n}x^{n}\in K[X]

が $a_{0},a_{n}\neq 0$ だったとすると、

|f|=\max\{|a_{0}|,|a_{n}|\}

である。 $f(X)=X^{6}+10X-1$ の場合だと、 $\mathbb {Q} _{2}[X]$ で

{\begin{aligned}|f(X)|&=\max\{|a_{0}|,\ldots ,|a_{n}|\}\\&=\max\{0,1,0\}=1\end{aligned}}

であるが、 $\max\{|a_{0}|,|a_{n}|\}=0$ なので、この多項式は既約ではありえない。一方 $\mathbb {Q} _{7}[X]$ では両方の値が等しいので既約である可能性がある。既約であるかどうか決定するためにはニュートンの多角形を使う必要がある^[4]^{pg 144}。

フロベニウス

$a\in \mathbb {F} _{p}$ に対してフロベニウス自己準同型 $(-)\mapsto (-)^{p}$ による多項式 $x^{p}-a$ を考える。この微分は

{\begin{aligned}{\frac {d}{dx}}x^{p}-a&=p\cdot x^{p-1}\\&\equiv 0\cdot x^{p-1}{\bmod {p}}\\&\equiv 0{\bmod {p}}\end{aligned}}

となり常にゼロである。したがって $a$ の $p$ 乗根は $\mathbb {Z} _{p}$ に存在しない。 $a=1$ の場合、これは $\mathbb {Z} _{p}$ には1の冪根 $\mu _{p}$ が含まれないことを意味する。^{[要検証 – ノート]}

1の冪根

1の $p$ 乗根は $\mathbb {F} _{p}$ に存在しないが、方程式 $x^{p}-x=x(x^{p-1}-1)$ の解は存在する。次の式

{\begin{aligned}{\frac {d}{dx}}x^{p}-x&=px^{p-1}-1\\&\equiv -1{\bmod {p}}\end{aligned}}

は決してゼロにならないので、解が存在すればそれは $\mathbb {Z} _{p}$ に持ち上げることができる。フロベニウスにより $a^{p}=a$ なので、ゼロではない元全体 $\mathbb {F} _{p}^{\times }$ が解全体である。実は、 $\mathbb {Q} _{p}$ に含まれる1の冪根はこれらだけである^[5]。

ヘンゼル持ち上げ

補題を使って、多項式 $f$ の法 $p k$ での根 $r$ を法 $p k +1$ での新しい根 $s$ に $r$ ≡ $s$ mod $p k$ となるように持ち上げることができる。（ $m =1$ と取る。数学的帰納法により大きい $m$ はしたがう）。

また、法 $p k +1$ での根は法 $p k$ での根でもあるので、法 $p k +1$ での根はすべて法 $p k$ での根の持ち上げである。

持ち上げた根 $s$ は法 $p$ で $r$ と合同なので、新しい根も $f'(s)\equiv f'(r)\not \equiv 0{\bmod {p}}$ を満たす。

したがって、最初の根 $r k$ が $f'(r_{k})\not \equiv 0{\bmod {p}}$ を満たせば持ち上げの操作は繰り返すことができ、 $f(x)\equiv 0{\bmod {p}}^{k}$ の解 $r k$ からはじめて、 $p$ の高次冪に対して同じ合同式を満たす解の数列 $r k +1$ , $r k +2$ , ... を作れる。

このことはまた、 $f$ の法 $p k$ での根が全て単根であれば、 $f$ の法 $p k$ での根の数は法 $p k +1$ , $p k +2$ , ... での根の数と同じであることを示している。

$r$ が法 $p$ で単根になっていないとき、このプロセスでは何が起きているのであろうか? これを見るために、次の状況

f(r)\equiv 0{\bmod {p}}^{k}\quad {\text{and}}\quad f'(r)\equiv 0{\bmod {p}}

を考えよう。このとき、 $s\equiv r{\bmod {p}}^{k}$ は $f(s)\equiv f(r){\bmod {p}}^{k+1}$ を意味する。つまり任意の整数 $t$ に対して $f(r+tp^{k})\equiv f(r){\bmod {p}}^{k+1}$ が成り立つ。それゆえ次の2つの場合がある。

$f(r)\not \equiv 0{\bmod {p}}^{k+1}$ なら $r$ の法 $p k +1$ への $f (x)$ の根の持ち上げは存在しない。

$f(r)\equiv 0{\bmod {p}}^{k+1}$ なら $r$ の任意の法 $p k +1$ への持ち上げは $f (x)$ の法 $p k +1$ での根である。

例: $p = 2$ として両方のケースを見てみよう。

$f(x)=x^{2}+1$ とし、 $r = 1$ とする。このとき、 $f(1)\equiv 0{\bmod {2}}$ で $f'(1)\equiv 0{\bmod {2}}$ である。 $f(1)\not \equiv 0{\bmod {4}}$ なので、1の法4への持ち上げで $f (x)$ の法4での根になるものは存在しない。

$g(x)=x^{2}-17$ 、 $r = 1$ とする。すると $g(1)\equiv 0{\bmod {2}}$ かつ $g'(1)\equiv 0{\bmod {2}}$ である。また、 $g(1)\equiv 0{\bmod {4}}$ であるので、この解を法4へ持ち上げることができ、2つの持ち上げ（1と3）はともに解である。これらの解に対しても微分は法2でやはり0であるので、アプリオリにはこれらを法8に持ち上げられるかどうかは分からない。しかし実際には $g (1)$ も $g (3)$ も法8で0と合同であるので持ち上げることができる。法8では1, 3, 5, 7が解である。これらの中で $g (1)$ と $g (7)$ だけが法16で0なので、1と7だけが法16に持ち上げることができ、それらは1, 7, 9, 15である。これらの中では7と9だけが $g (x) = 0 mod 32$ なので、同様に法32での解7, 9, 23, 25が得られる。任意の整数 $k \geq 3$ に対して法2での $g (x)$ の根1の法 $2 k$ の根への持ち上げは4つ存在することがわかる。

$p$ 進数の場合のヘンゼルの補題

$p$ 進数では、 $p$ の冪乗を法とする有理数の合同類というものを、分母が $p$ の倍数でなければ考えることができる。このことを使うと、法 $p k$ での根 $r k$ から法 $p k +1$ での根 $r k +1$ を求める反復計算をずっと直感的に行うことができる。次の合同式

tf'(r_{k})\equiv -(f(r_{k})/p^{k}){\bmod {p}}^{m}

を解いて整数 $t$ を見つける代わりに、有理数 $t$ を次の式

-(f(r_{k})/p^{k})/f'(r_{k})

で定める。分母に $p k$ が出てくるように見えるが、 $f (r k)$ が $p k$ で割れるため実際には出てこない。そして

r_{k+1}=r_{k}+tp^{k}=r_{k}-{\frac {f(r_{k})}{f'(r_{k})}}

と置く。これは整数にはならないかもしれないが、 $p$ 進整数にはなっている。数列 $r k$ はある $p$ 進整数に収束し、極限は $f (x) = 0$ の解になっている。そして、 $r k$ から $r k +1$ を計算する漸化式をよく見てみると、実数の場合における求根アルゴリズムであるニュートン法の漸化式とまったく同じになっている。

$p$ 進数の中で計算を行い $p$ 進絶対値を使うことで $f'(a)\equiv 0{\bmod {p}}$ となってしまう $f (a) \equiv 0 mod p$ の解についても使えるようにしたヘンゼル補題がある。 $f'(a)$ が0になってしまわないことは必要である。この一般化されたヘンゼルの補題は次のようになる。整数 $a$ で

|f(a)|_{p}<|f'(a)|_{p}^{2}

を満たすものがあったとすると、 $p$ 進整数 $b$ で $f (b) = 0$ かつ $|b-a|_{p}<|f'(a)|_{p}$ となるものが一意的に存在する。この $b$ を作るにはニュートン法の漸化式が初期値 $a$ で $p$ 進数に収束することを示しその極限を $b$ と置けばよい。条件 $|b-a|_{p}<|f'(a)|_{p}$ を満たす根として $b$ が一意であることを示すには追加の議論がいる。

先ほどのヘンゼルの補題の $m=1$ の場合はこの一般化された補題の特殊な場合になっている。条件 $f (a) \equiv 0 mod p$ と $f'(a)\not \equiv 0{\bmod {p}}$ は $|f(a)|_{p}<1$ と $|f'(a)|_{p}=1$ を意味するからである。

例

$p$ を奇素数、 $a$ を0ではない $p$ を法とする平方剰余とする。このとき、 $p$ 進整数環 $\mathbb {Z} _{p}$ の中に $a$ の平方根が存在することをヘンゼルの補題を使って示すことができる。これを見るために $f(x)=x^{2}-a$ と置く。 $r$ を法 $p$ での $a$ の平方根とすると

f(r)=r^{2}-a\equiv 0{\bmod {p}}\quad {\text{and}}\quad f'(r)=2r\not \equiv 0{\bmod {p}}

が成り立つ。2番目の式は $p$ が奇数であることによる。基本形のヘンゼルの補題を使って、 $r 1 = r$ から出発して反復計算を行うことにより整数の列 $\{r_{k}\}$ を

r_{k+1}\equiv r_{k}{\bmod {p}}^{k},\quad r_{k}^{2}\equiv a{\bmod {p}}^{k}

が成り立つように作ることができる。この列はある $p$ 進整数 $b$ に収束し $b 2 = a$ を満たす。

この $b$ は、法 $p$ で $r 1$ と合同になる $\mathbb {Z} _{p}$ における $a$ の唯一の平方根である。逆に、 $a$ を $\mathbb {Z} _{p}$ の平方数で $p$ で割り切れないものとすると、これは0ではない法 $p$ での平方剰余である。 $a$ が法 $p$ でゼロではない平方剰余かどうかは平方剰余の相互法則で簡単に判定できるので、これで（奇素数 $p$ に対する） $p$ 進数が $p$ 進平方根を持つかどうかを決定する実用的な方法が得られたことになる。 $p = 2$ の場合にも、一般化されたヘンゼルの補題を用いることでこの方法を拡張することができる（17の2進平方根の例を後で見る）。

以上の議論をもっと具体的に理解するために、7進整数環の中で"2の平方根"、つまり方程式 $x^{2}-2=0$ の解を見つけてみよう。この方程式の法7での解の1つは3（もう1つの解は4）なので、 $r_{1}=3$ としよう。ヘンゼルの補題における $r_{2}$ の計算式に現れる各種の数値は

{\begin{aligned}f(r_{1})&=3^{2}-2=7\\f(r_{1})/p^{1}&=7/7=1\\f'(r_{1})&=2r_{1}=6\end{aligned}}

となる。これらの式から、次の式

tf'(r_{1})\equiv -(f(r_{1})/p^{k}){\bmod {p}}

は

t\cdot 6\equiv -1{\bmod {7}}

となり、これは $t=1$ を意味する。したがって、

r_{2}=r_{1}+tp^{1}=3+1\cdot 7=10=13_{7}

と計算できた。簡単に確かめられるように、 $10^{2}\equiv 2{\bmod {7}}^{2}$ が成り立っている（ニュートン法の反復を直接7進数で使うと、 $r_{2}=r_{1}-f(r_{1})/f'(r_{1})=3-7/6=11/6$ となる。 $11/6\equiv 10{\bmod {7}}^{2}$ なので整合している）。

次の反復計算を行うと $r_{3}=108=3+7+2\cdot 7^{2}=213_{7}$ となる。この計算を1回繰り返すごとに（つまり $k$ の値が1つ増えていく度に）次の7の冪乗の項が追加され7進数での桁が1つが増えていく。7進整数環の中でこの数列は収束し、その極限は $\mathbb {Z} _{7}$ での2の平方根となる。その7進展開の初めの方は

3+7+2\cdot 7^{2}+6\cdot 7^{3}+7^{4}+2\cdot 7^{5}+7^{6}+2\cdot 7^{7}+4\cdot 7^{8}+\cdots

となる。

最初に $r_{1}=4$ を選んだ場合でも $\mathbb {Z} _{7}$ における2の平方根が得られる。これは法7で3ではなく4に合同になるもので、実は最初に得られた平方根を-1倍したものになっている（これは $4 = -3 mod 7$ であることと辻褄があっている）。

元々のヘンゼルの補題は適用できないが一般化されたものなら適用できる例として $f(x)=x^{2}-17$ を考える。 $a=1$ とすると $f(a)=-16$ であり、また $f'(a)=2$ であるので、

|f(a)|_{2}<|f'(a)|_{2}^{2}

が成り立つ。これから、ある2進整数 $b$ で

b^{2}=17\quad {\text{and}}\quad |b-a|_{2}<|f'(a)|_{2}={\frac {1}{2}}

を満たすものが一意に存在する。二番目の式は $b \equiv 1 mod 4$ を意味する。2進整数の中には17の平方根が2つ存在し、それらは符号が異なり、法2では合同であるが法4では合同ではない。これは、一般化された形のヘンゼルの補題から得られるのが法2ではなく法4で1と合同な17の2進平方根で、法4で一意であることと整合的である。最初の近似根として $a = 3$ を取った場合でも一般化されたヘンゼルの補題を適用することができ、法4で3と合同になる唯一の17の2進平方根をやはり見つけることができる。これがもう1つの17の2進平方根である。

$x^{2}-17$ の根を法 $2 k$ から法 $2 k +1$ へ持ち上げるやり方の場合、法2での根1からの持ち上げの過程は次のようになる。

1 mod 2

は

1, 3 mod 4

に持ち上がる。

1 mod 4

は

1, 5 mod 8

に、

3 mod 4

は

3, 7 mod 8

に持ち上がる。

1 mod 8

は

1, 9 mod 16

に、

7 mod 8

は

7, 15 mod 16

に持ち上がる。一方、

3 mod 8

と

5 mod 8

は

mod 16

での根に持ち上がらない。

9 mod 16

は

9, 25 mod 32

に、

7 mod 16

は

7, 23 mod 16

に持ち上がる。一方、

1 mod 16

と

15 mod 16

は

mod 32

での根に持ち上がらない。

$k$ が3以上であれば $x 2 - 17 mod 2 k$ には4つの根がある。しかし2進極限は2つしかない。持ち上げられた根と極限の2進展開を比べてみよう。例えば、法32での4つの根を法16で等しくなるものを組にして書くと次のようになる。

9 = 1 + 2 3

と

25 = 1 + 2 3 + 2 4

7 = 1 + 2 + 2 2

と

23 = 1 + 2 + 2 2 + 2 4

一方、17の2進平方根の展開は

1+2^{3}+2^{5}+2^{6}+2^{7}+2^{9}+2^{10}+\cdots

1+2+2^{2}+2^{4}+2^{8}+2^{11}+\cdots

となっている。

基本形は使えないが一般化された形のヘンゼルの補題なら使えるもう１つの例として、 $c \equiv 1 mod 9$ である任意の3進整数は $\mathbb {Z} _{3}$ で立方数になることの証明を見よう。 $f(x)=x^{3}-c$ と置き、最初の近似根として $a = 1$ を取る。任意の $r$ に対して $f'(r)\equiv 0{\bmod {3}}$ となってしまうので、基本形のヘンゼルの補題を使って $f (x)$ の根を見つけることはできない。

一般形のヘンゼルの補題を適用するためには $|f(1)|_{3}<|f'(1)|_{3}^{2}$ である必要がある。これは $c\equiv 1{\bmod {2}}7$ ということである。つまり、 $c \equiv 1 mod 27$ であれば一般形のヘンゼルの補題から $f (x)$ が3進根を持つことがわかり、 $c$ が3進立方数であることがわかる。しかし、 $c \equiv 1 mod 9$ というより弱い条件のもとでこの結果が欲しい。 $c \equiv 1 mod 9$ であれば、 $c \equiv 1, 10, or 19 mod 27$ である。この3つの $c mod 27$ の値に応じて初期値を使い分けて一般形のヘンゼルの補題を適用する。 $c \equiv 1 mod 27$ なら、 $a = 1$ を使う。 $c \equiv 10 mod 27$ なら、 $a = 4$ を使う（4は法27での $f (x)$ の根）。 $c \equiv 19 mod 27$ なら、 $a = 7$ を使う。なお、任意の $c \equiv 1 mod 3$ は3進立方数になる、という主張は正しくない。例えば、4は法9で立方数にならないので3進立方数ではない。

同様にして、少し準備が必要だが、ヘンゼルの補題を使って任意の奇素数 $p$ に対して法 $p 2$ で1と合同な全ての $p$ 進整数 $c$ は $\mathbb {Z} _{p}$ の $p$ 冪乗数であることを示すことができる（ $p = 2$ の場合はこれは成り立たない）^[6]。

多変数への一般化

1つの多項式

ヘンゼルの補題は多変数の多項式への一般化もある。 $f (X 1, X 2, ..., X n)$ を整数係数の多項式とし、ディオファントス方程式

f (X 1, X 2, ..., X n) = 0

を考える。これがある素数 $p$ に対して $mod p 2 m + 1$ （ $m$ は非負整数）で解 $a = (a 1, a 2, ..., a n)$ ∈ Z^$n$ を持ったとする。つまり $f (a 1, a 2, ..., a n) \equiv 0 mod p 2 m + 1$ が成り立ったとする。さらに、少なくとも1つの変数について $f$ の偏微分の $a$ における値が $mod p m + 1$ でゼロではなかったとする。このとき、 $a$ は $mod p m + 1$ で $a$ と等しい $mod p 2 m + 2$ での解に持ち上がる^[7]。同様に Z $n$
$p$ の解に持ち上げることもできるので、このディオファントス方程式は $p$ 進整数環 Z_$p$ で解を持つ^[8]。

複数の多項式

$A$ をイデアル ${\mathfrak {m}}$ について完備な可換環とし、 $f(x)\in A[x]$ とする。次の式

f(a)\equiv 0{\bmod {f}}'(a)^{2}{\mathfrak {m}}.

を満たす $a \in A$ のことを $f$ の近似根と呼ぶ。 $f$ が近似根を持つなら、 $a$ に"近い"本当の根 $b \in A$ も持つ。つまり、次の式

f(b)=0\quad {\text{and}}\quad b\equiv a{\bmod {\mathfrak {m}}}

を満たす $b$ が存在する。さらに、 $f'(a)$ が零因子でないならば、 $b$ は一意的である。

このことは多変数の場合に次のように一般化できる^[9]。

定理:

A

を可換環でイデアル

{\mathfrak {m}}\subset A

について完備なものとする。

f_{1},\ldots ,f_{n}\in A[x_{1},\ldots ,x_{n}]

を

A

係数の

n

個の

n

変数多項式とする。

\mathbf {f} =(f_{1},\ldots ,f_{n})

を

A n

から自身への写像と考え、

J_{\mathbf {f} }(\mathbf {x} )

をそのヤコビ行列とする。

a

=

(a 1, ..., a n) \in A n

を

f = 0

の近似解、つまり

f_{i}(\mathbf {a} )\equiv 0{\bmod {(}}\det J_{\mathbf {f} }(a))^{2}{\mathfrak {m}},\qquad 1\leqslant i\leqslant n

が成り立つものとする。このとき、ある

b = (b 1, ..., b n) \in A n

で

f (b) = 0

を満たすもの、つまり

f_{i}(\mathbf {b} )=0,\qquad 1\leqslant i\leqslant n

が成り立つものが存在する。さらに、この解は

b_{i}\equiv a_{i}{\bmod {\det }}J_{\mathbf {f} }(a){\mathfrak {m}},\qquad 1\leqslant i\leqslant n

が成り立つという意味で

a

に"近い"解である。

この定理の特別な場合として、 $f_{i}(\mathbf {a} )\equiv 0{\bmod {\mathfrak {m}}}$ がすべての $i$ に対して成り立ち、しかも $\det J_{\mathbf {f} }(\mathbf {a} )$ が $A$ の単数なら、解 $f (b) = 0$ ですべての $i$ に対して $b_{i}\equiv a_{i}{\bmod {\mathfrak {m}}}$ が成り立つものが存在することがわかる。