ヘンゼルの補題

数学のヘンゼルの補題（ヘンゼルのほだい、テンプレート:Lang-en-short）とは、1変数多項式が素数テンプレート:Mvar を法としてテンプレート:仮リンクを持つならば、その根はテンプレート:Math の任意の冪乗を法とする根に一意的に持ち上げられるという、合同算術における補題である。この補題は、多項式が法テンプレート:Math で2つのテンプレート:仮リンクに因数分解できるならば、その因数分解はテンプレート:Math の任意の冪乗を法とする因数分解に持ち上げることができるという補題に一般化できる。因数分解に現れる多項式の次数が1の場合が根の場合に相当する。ヘンゼルの持ち上げ補題（テンプレート:Lang-en-short）とも呼ばれる。名称はクルト・ヘンゼルに因む。

テンプレート:Mvar の冪指数を無限に大きくしていったときの（射影極限の意味での）極限を取ることにより、法テンプレート:Mvar での根（または因数分解）を [[P進数|テンプレート:Mvar 進整数]]上での根（または因数分解）に持ち上げることができる。

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

ヘンゼルの補題は、解析的整数論の一分野である [[p進解析|テンプレート:Mvar 進解析学]]の基礎である。

ヘンゼルの補題の証明はテンプレート:仮リンクであり、証明からヘンゼル持ち上げの効率的なアルゴリズムが得られる。これは多項式の因数分解のアルゴリズムの基礎である。また有理数体上の線型代数学についての最も効率の良いアルゴリズムが得られるテンプレート:要検証。

ヘンゼルの補題は、ヘンゼルよりも早く1846年にテンプレート:仮リンクによって証明されていたテンプレート:Sfn。また、「存在」についての主張だけならシェーネマンよりも早くカール・フリードリヒ・ガウスによっても知られていたテンプレート:Sfn。

還元と持ち上げ

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

この一般化を正確に書くためには、整数の場合の合同算術を一般化しておく必要があるので、この文脈で通常使われる用語を正確に定義しておこう。

テンプレート:Mvar を可換環、テンプレート:Mvar をテンプレート:Mvar のイデアルとする。テンプレート:Mvar の元をテンプレート:仮リンク $R \to R / I$ による像で置き換えることを、テンプレート:Mvar を法とする還元、または法テンプレート:Mvar での還元と呼ぶ。

例えば、 $f \in R [X]$ をテンプレート:Mvar 係数の多項式とするとき、そのテンプレート:Mvar を法とする還元 $f mod I$ とは、テンプレート:Mvar の係数を $R / I$ での像に置き換えることで得られる $(R / I) [X] = R [X] / I R [X]$ の多項式のことをいう。 $R [X]$ の2つの多項式テンプレート:Mvar とテンプレート:Mvar が法テンプレート:Mvar で係数が等しくなるとき、つまり $f - g \in I R [X]$ であるとき、この2つの多項式は法テンプレート:Mvar で合同であるといい、 $f \equiv g (\mod I)$ で表す。 $h \in R [X]$ の法テンプレート:Mvar での因数分解とは、テンプレート:Mvar を法テンプレート:Mvar で $R [X]$ の2つ（以上）の多項式テンプレート:Mvar の積として書き表す $h \equiv f g (\mod I)$ ことをいう。

持ち上げとは還元の逆の操作である。つまり、 $R / I$ の元を使って表されている対象があったとき、持ち上げとは対象の性質を保ったまま還元するとこの対象に等しくなるように $R$ （もしくはあるテンプレート:Math に対する $R / I^{k}$ ）の元に置き換えることをいう。

例えば、多項式 $h \in R [X]$ が法テンプレート:Mvar で $h \equiv f g (\mod I)$ と因数分解されているとき、この因数分解を法 $I^{k}$ へ持ち上げるとは、多項式 $f^{'}, g^{'} \in R [X]$ であって $f^{'} \equiv f (\mod I),$ $g^{'} \equiv g (\mod I),$ $h \equiv f g (\mod I^{k})$ を満たすものを見つけることである。ヘンゼルの補題は、この因数分解の持ち上げが緩い条件のもとで常に可能であることを主張するものである。

ヘンゼルの補題の主張

元々のヘンゼルの補題は、整数を係数とする多項式の素数テンプレート:Mvar を法とする因数分解をテンプレート:Mvar の冪乗を法とする因数分解、もしくは [[p進数|テンプレート:Mvar 進整数環]]上の因数分解に持ち上げることを主張（そして証明）するものであった。この補題は、整数を任意の可換環、素数を極大イデアル、そしてテンプレート:Mvar 進整数環をその極大イデアルについての完備化に置き換えることで簡単に一般化できる。証明の仕方も同じである。この一般化された補題も広く用いられる。本記事で述べるのもこれである。

テンプレート:Mvar を可換環、 $𝔪$ をその極大イデアルの1つ、そして

h = α_{0} X^{n} + \dots + α_{n - 1} X + α_{n}

を $R [X]$ の多項式で最高次の係数 $α_{0}$ が $𝔪$ に含まれないものとする。

$𝔪$ を極大イデアルとしているので、その剰余環 $R / 𝔪$ は体である。したがって $(R / 𝔪) [X]$ は単項イデアル整域なので、特に一意分解環である。これは、任意のゼロではない $(R / 𝔪) [X]$ の多項式は $(R / 𝔪)$ のゼロでない元とモニック（最高次の係数が1という意味）な既約多項式の積として一意的にかけることを意味する。

ヘンゼルの補題は、テンプレート:Mvar の法 $𝔪$ での互いに素な多項式への因数分解は、任意のテンプレート:Mvar に対して $𝔪^{k}$ を法とする因数分解に一意的に持ち上げられることを主張する。

もう少し詳しく書くと、上述の仮定のもとで、法 $𝔪$ でモニックかつテンプレート:仮リンクな多項式テンプレート:Mvar とテンプレート:Mvar を使って $h \equiv α_{0} f g (\mod 𝔪)$ と分解できたとすると、全ての正の整数テンプレート:Mvar に対してモニック多項式 $f_{k}$ と $g_{k}$ が存在して次の式

\begin{matrix} h & \equiv α_{0} f_{k} g_{k} (\mod 𝔪^{k}) \\ f_{k} & \equiv f (\mod 𝔪) \\ g_{k} & \equiv g (\mod 𝔪) \end{matrix}

が成り立ち、しかもこのような性質を持つ $f_{k}$ と $g_{k}$ は法 $𝔪^{k}$ で一意ということを主張する。

単根の持ち上げ

大切で特別な場合として $f = X - r$ であるときを考える。この場合、互いに素という仮定はテンプレート:Mvar は $h mod 𝔪$ の単根であるということを意味する。したがってこの場合にはヘンゼルの補題の主張は次のようになる（これもヘンゼルの補題と言われる）。

記号と仮定は今までと同じとし、テンプレート:Mvar を $h mod 𝔪$ の単根とする。このとき、テンプレート:Mvar は全ての正の整数テンプレート:Mvar に対して $h mod 𝔪^{n}$ の単根に一意的に持ち上げることができる。つまり、任意の正の整数テンプレート:Mvar 対して $h {mod 𝔪}^{n}$ の単根 $r_{n} \in R / 𝔪^{n}$ であって $r_{n} \equiv r (\mod 𝔪)$ を満たすものが一意的に存在する。

完備化への持ち上げ

全ての正の整数テンプレート:Mvar に対して $R / 𝔪^{n}$ に持ち上げることができるので、テンプレート:Mvar を限りなく大きくしていったときの"極限"を考えたくなる。これが [[p進数|テンプレート:Mvar 進整数]]が考案された主な理由の1つである。

テンプレート:Mvar を可換環、 $𝔪$ を極大イデアルとすると、 $𝔪$ のベキたちはテンプレート:Mvar の $𝔪$ 進位相と呼ばれる位相についての基本近傍系になる。この位相による完備化は局所環 $R_{𝔪}$ の完備化と同一視でき、また射影極限 $\lim_{\leftarrow} R / 𝔪^{n}$ とも同一視できる。この完備局所環は ${\hat{R}}_{𝔪}$ と一般的に書き表される。テンプレート:Mvar が整数環で $𝔪 = p ℤ$ （テンプレート:Mvar は素数）であるときには、この完備局所環はテンプレート:Mvar 進整数環 $ℤ_{p}$ である。

完備化の射影極限を使った定義と上述のヘンゼルの補題の主張から、多項式 $h \in R [X]$ の法 $𝔪$ での因数分解がどの2つの因子を取っても互いに素であるなら、それはテンプレート:Mvar の ${\hat{R}}_{𝔪} [X]$ における像の因数分解に一意的に持ち上げられることが導かれる。同様に、テンプレート:Mvar の法 $𝔪$ での任意の単根はテンプレート:Mvar の ${\hat{R}}_{𝔪} [X]$ における像の単根に持ち上げられる。

証明

ヘンゼルの補題は、 $R / 𝔪^{n}$ での因数分解を $R / 𝔪^{n + 1}$ での因数分解に持ち上げる（#1次持ち上げ）ことを繰り返すか、または $R / 𝔪^{2 n}$ での因数分解に持ち上げる（#2次持ち上げ）ことを繰り返すことにより証明されることが多い。

証明では、体を係数とするテンプレート:仮リンクに対してベズーの等式が成り立つということが重要な役割を果たす。ベズーの等式とは、体（ここで使うのは $R / 𝔪$ の場合）を係数とする互いに素な1変数多項式テンプレート:Mvar とテンプレート:Mvar があったとすると、ある多項式テンプレート:Mvar とテンプレート:Mvar であって、 $\deg a < \deg g$ かつ $\deg b < \deg f$ かつ次の式

a f + b g = 1

を満たすものが存在するということである。

ベズーの等式が成り立てば $𝔪$ が極大イデアルではなくともヘンゼルの補題を証明することができる。

それゆえ、以下ではテンプレート:Mvar を可換環、テンプレート:Mvar をそのイデアル、 $h \in R [X]$ を最高次係数が法テンプレート:Mvar で可逆（ $R / I$ における像が $R / I$ の可逆元ということ）な多項式、テンプレート:Mvar もしくはテンプレート:Mvar の冪乗を法とするテンプレート:Mvar の因数分解に現れる因子が法テンプレート:Mvar でベズーの等式を満たす、という設定のもとで証明を行う。証明では、 $A \equiv B (\mod I)$ という式で $A - B \in I R [X]$ であることを表すことにする。

1次持ち上げ

テンプレート:Mvar を可換環、テンプレート:Mvar をそのイデアル、 $h \in R [X]$ をテンプレート:Mvar 係数の1変数多項式で最高次の係数 $α$ が法テンプレート:Mvar で可逆（ $α$ の $R / I$ における像が $R / I$ の可逆元という意味）であるものとする。

そして何らかの正の整数テンプレート:Mvar に対して

h \equiv α f g (\mod I^{k})

と因数分解でき、テンプレート:Mvar とテンプレート:Mvar はモニック多項式で法テンプレート:Mvar で互いに素だったとする。ここで、"互いに素"というのはある $a, b \in R [X]$ が存在して $a f + b g \equiv 1 (\mod I)$ という意味で使っている。このとき、多項式 $δ_{f}, δ_{g} \in I^{k} R [X]$ であって $\deg δ_{f} < \deg f$ かつ $\deg δ_{g} < \deg g$ かつ次の式

h \equiv α (f + δ_{f}) (g + δ_{g}) (\mod I^{k + 1})

が成り立つものが存在する。しかもこれらの条件が成り立つ $δ_{f}$ と $δ_{g}$ は法 $I^{k + 1} R [X]$ で一意的に定まる。

そして $f + δ_{f}$ と $g + δ_{g}$ はテンプレート:Mvar とテンプレート:Mvar が満たすベズーの等式を同様に満たす。つまり $a (f + δ_{f}) + b (g + δ_{g}) \equiv 1 (\mod I)$ が成り立つ。なぜ直前の主張からすぐにわかるこのことをあえて述べたかというと、テンプレート:Mvar の値を１つ大きくして反復計算を進めるときに、これが次のステップでの前提条件が満たされていることを意味するからである。

次に示す証明は、 $R / I$ または $I^{k} / I^{k + 1}$ を係数とする多項式だけを使って $δ_{f}$ と $δ_{g}$ を計算することによりなされている。 $R = ℤ$ で $I = p ℤ$ の場合には、これは法テンプレート:Mvar での剰余類だけを使って計算できることを意味する。

証明： 仮定から $α$ は法テンプレート:Mvar で可逆である。したがって、ある $β \in R$ と $γ \in I R [X]$ で $α β = 1 - γ$ を満たすものが存在する。

多項式 $δ_{h} \in I^{k} R [X]$ を、次数が $\deg h$ 未満で

δ_{h} \equiv h - α f g (\mod I^{k + 1})

が成り立つものとする。 $δ_{h} = h - α f g$ と置いてもよいが、他のものを選んだ方が計算が簡単になることがある。例えば $R = ℤ$ で $I = p ℤ$ の場合には、係数が区間テンプレート:Nowrap に入る整数係数の多項式 $δ'_{h}$ を使って $δ_{h} = p^{k} δ'_{h}$ と表せるようなものを取ることができるので、こう取ったほうがよい。

テンプレート:Mvar はモニックなので、多項式に対する除法の原理を $a δ_{h}$ とテンプレート:Mvar に適用し、テンプレート:Mvar とテンプレート:Mvar で $a δ_{h} = q g + c$ かつ $\deg c < \deg g$ となるものを見つけることができる。このテンプレート:Mvar とテンプレート:Mvar は $I^{k} R [X]$ に入っている。同様に、 $q^{'}, d \in I^{k} R [X]$ で $b δ_{h} = q^{'} f + d$ かつ $\deg d < \deg f$ となるものを取る。

このとき $q + q^{'} \in I^{k + 1} R [X]$ である。実際、まず

f c + g d = a f δ_{h} + b g δ_{h} - f g (q + q^{'}) \equiv δ_{h} - f g (q + q^{'}) (\mod I^{k + 1})

が成り立っている。 $f g$ はモニックなので、 $f g (q + q^{'})$ の法 $I^{k + 1}$ での次数が $\deg f g$ の次数よりも小さくなるのは $q + q^{'} \in I^{k + 1} R [X]$ のときだけである。

こうして、 $I^{k + 1}$ を法とする合同を考えることにより次の式

\begin{matrix} α (f + β d) & (g + β c) - h \\ \equiv α f g - h + α β (f (a δ_{h} - q g) + g (b δ_{h} - q^{'} f)) \\ \equiv δ_{h} (- 1 + α β (a f + b g)) - α β f g (q + q^{'}) \\ \equiv 0 (\mod I^{k + 1}) \end{matrix}

が成り立つことがわかる。そして、

δ_{f} = β d, δ_{g} = β c

と置けば求めるものになっているので、存在が示せた。

一意性

記号テンプレート:Mvar、テンプレート:Mvar、テンプレート:Mvar、 $α$ は前節と同じとする。テンプレート:Mvar が

h \equiv α f g (\mod I)

と、 $\deg f_{0} + \deg g_{0} = \deg h$ となる互いに素な多項式（前述の意味で）に因数分解できたとする。1次持ち上げを $k = 1, 2, \dots, n - 1 \dots$ に適用して、多項式 $δ_{f}$ と $δ_{g}$ であって $\deg δ_{f} < \deg f$ かつ $\deg δ_{g} < \deg g$ かつ次の式

h \equiv α (f + δ_{f}) (g + δ_{g}) {(\mod I)}^{n}

を満たすものの存在がわかる。この多項式 $δ_{f}$ と $δ_{g}$ は法 $I^{n}$ で一意に定まる。つまり、同じ条件を満たす組 $(δ'_{f}, δ'_{g})$ が他にあったとすると、

δ'_{f} \equiv δ_{f} (\mod I^{n}) and δ'_{g} \equiv δ_{g} (\mod I^{n})

が成り立つ。

証明: $I^{n}$ を法とする合同は $I^{n - 1}$ を法とする合同を意味するので、数学的帰納法を使って証明する。テンプレート:Math の場合は明らかである。テンプレート:Math の場合の一意性は証明されているものと仮定する。つまり、

δ_{f} - δ'_{f} \in I^{n - 1} R [X] and δ_{g} - δ'_{g} \in I^{n - 1} R [X]

と仮定する。仮定により

h \equiv α (f + δ_{f}) (g + δ_{g}) \equiv α (f + δ'_{f}) (g + δ'_{g}) (\mod I^{n})

が成り立ち、これから

\begin{matrix} α (f + δ_{f}) (g + δ_{g}) & - α (f + δ'_{f}) (g + δ'_{g}) \\ = α (f (δ_{g} - δ'_{g}) + g (δ_{f} - δ'_{f})) + α (δ_{f} δ_{g} - δ'_{f} δ'_{g}) \in I^{n} R [X] \end{matrix}

が成り立つ。帰納法の仮定から右辺の2番目の項は $I^{n}$ に含まれ、（左辺もそうなので）同じことが初項についても成り立つ。 $α$ は法テンプレート:Mvar で可逆なので、ある $β \in R$ と $γ \in I$ が存在して $α β = 1 + γ$ が成り立つ。これと帰納法の仮定から

\begin{matrix} f (δ_{g} - δ'_{g}) & + g (δ_{f} - δ'_{f}) \\ = α β (f (δ_{g} - δ'_{g}) + g (δ_{f} - δ'_{f})) - γ (f (δ_{g} - δ'_{g}) + g (δ_{f} - δ'_{f})) \in I^{n} R [X] \end{matrix}

が成り立つ。

法テンプレート:Mvar で互いに素という仮定から、ある $a, b \in R [X]$ が存在して $1 \equiv a f + b g (\mod I)$ が成り立つ。帰納法の仮定をもう一度使うと

\begin{matrix} δ_{g} - δ'_{g} & \equiv (a f + b g) (δ_{g} - δ'_{g}) \\ \equiv g (b (δ_{g} - δ'_{g}) - a (δ_{f} - δ'_{f})) (\mod I^{n}) \end{matrix}

となる。したがって、次数が $\deg g$ 未満の多項式が法 $I^{n}$ でモニック多項式テンプレート:Mvar ともう1つの多項式テンプレート:Mvar の積と合同になったことになる。これが起こり得るのは $w \in I^{n} R [X]$ の場合だけなので、これから $δ_{g} - δ'_{g} \in I^{n} R [X]$ が得られる。同様に $δ_{f} - δ'_{f}$ も $I^{n} R [X]$ に含まれることが示せるので、これで一意性が証明できた。

2次持ち上げ

1次持ち上げは法 $I^{n}$ での因数分解を法 $I^{n + 1}$ での因数分解に持ち上げるものであった。2次持ち上げでは法 $I^{2 n}$ での因数分解に一気に持ち上げる。しかし、ベズーの等式の持ち上げも必要になり、（上述の1次持ち上げでは）法テンプレート:Mvar での計算だけで済んだが法 $I^{n}$ での計算が必要になるため、追加の計算コストがかかる。

どちらの方法でも大きなテンプレート:Mvar に対して法 $I^{N}$ まで持ち上げることができる。例えば $N = 2^{k}$ の場合に法 $I^{N}$ まで因数分解を持ち上げるためには、1次持ち上げを使うとテンプレート:Math 回の反復計算が必要になるが、 2次持ち上げを使えばテンプレート:Math 回の反復計算で済む。しかし、2次持ち上げを使う方法では扱わなければならない係数のサイズが計算中に増大していく。これは、一番いい持ち上げの方法は、テンプレート:Mvar の値やテンプレート:Mvar の性質、使用する乗算アルゴリズム、ハードウェアの特性などの状況に依存することを意味するテンプレート:要出典。

2次持ち上げは次の性質を利用する。

ある正の整数テンプレート:Mvar に対して因数分解

h \equiv α f g (\mod I^{k})

があったとし、テンプレート:Mvar とテンプレート:Mvar はモニック多項式で、ある $a, b \in R [X]$ が存在し $a f + b g \equiv 1 (\mod I^{k})$ が成り立つという意味で法テンプレート:Mvar で互いに素だったとする。このとき、ある多項式 $δ_{f}, δ_{g} \in I^{k} R [X]$ が存在し、 $\deg δ_{f} < \deg f$ かつ $\deg δ_{g} < \deg g$ かつ

h \equiv α (f + δ_{f}) (g + δ_{g}) (\mod I^{2 k})

が成り立つ。さらに $f + δ_{f}$ と $g + δ_{g}$ は次の形のベズーの等式

(a + δ_{a}) (f + δ_{f}) + (b + δ_{b}) (g + δ_{g}) \equiv 1 (\mod I^{2 k})

を満たす（つまり2次持ち上げの反復計算を行うための前提が満たされる）。

証明: 最初の主張は1次持ち上げをテンプレート:Math でテンプレート:Mvar の代わりにイデアル $I^{k}$ に対して適用することでわかる。

$α = a f + b g - 1 \in I^{k} R [X]$ と置く。次の式

a (f + δ_{f}) + b (g + δ_{g}) = 1 + Δ

が、

Δ = α + a δ_{f} + b δ_{g} \in I^{k} R [X]

と置くことで成り立つ。2つの多項式を $δ_{a} = - a Δ$ と $δ_{b} = - b Δ$ で定めると

(a + δ_{a}) (f + δ_{f}) + (b + δ_{b}) (g + δ_{g}) = 1 - Δ^{2} \in I^{2 k} R [X]

が成り立つ。これで2番目の主張も証明できた。

具体例

多項式 $f (X) = X^{6} - 2 \in ℚ [X]$ を考えよう。

この多項式に対して法2でのヘンゼルの補題を適用することはできない。なぜなら $f (X)$ を法 2 で還元すると単に ^[1]^{pg 15-16}

\bar{f} (X) = X^{6} - \overline{2} = X^{6}

となり、この6つの因子 $X$ はどの2つを取っても互いに素ではないからだ。しかし、アイゼンシュタインの既約判定法を使って多項式 $f (X)$ が $ℚ_{2} [X]$ で既約であることは示せる。

一方、 $k = 𝔽_{7}$ では

\bar{f} (X) = X^{6} - \overline{2} = X^{6} - \overline{16} = (X^{3} - \overline{4}) (X^{3} + \overline{4})

となる。 $4$ は $𝔽_{7}$ における2の平方根である。4は $𝔽_{7}$ における立方数ではないので、この2つの因子は $𝔽_{7}$ 上既約である。したがって $X^{6} - 2$ の $ℤ_{7} [X]$ （または $ℚ_{7} [X]$ ）における既約多項式への因数分解は

f (X) = X^{6} - 2 = (X^{3} - α) (X^{3} + α),

となる。ここで $α = \dots 450 45 4_{7}$ テンプレート:Efn は $ℤ_{7}$ における2の平方根で、先ほどの因数分解を持ち上げることで得られる。

最後に、この多項式は $𝔽_{727} [X]$ においては

\bar{f} (X) = X^{6} - \overline{2} = (X - \overline{3}) (X - \overline{116}) (X - \overline{119}) (X - \overline{608}) (X - \overline{611}) (X - \overline{724})

と分解する。これらの因子はどの2つを取っても互いに素なので、 $ℤ_{727} [X]$ （または $ℚ_{727} [X]$ ）において6つの多項式 $X - β$ の積に分解する。 $β$ は（有理数ではない）727進数

β = {\begin{matrix} 3 + & 545 \cdot 727 + & 537 \cdot 72 7^{2} + & 161 \cdot 72 7^{3} + \dots \\ 116 + & 48 \cdot 727 + & 130 \cdot 72 7^{2} + & 498 \cdot 72 7^{3} + \dots \\ 119 + & 593 \cdot 727 + & 667 \cdot 72 7^{2} + & 659 \cdot 72 7^{3} + \dots \\ 608 + & 133 \cdot 727 + & 59 \cdot 72 7^{2} + & 67 \cdot 72 7^{3} + \dots \\ 611 + & 678 \cdot 727 + & 596 \cdot 72 7^{2} + & 228 \cdot 72 7^{3} + \dots \\ 724 + & 181 \cdot 727 + & 189 \cdot 72 7^{2} + & 565 \cdot 72 7^{3} + \dots \end{matrix}

である。

微分を用いた根の持ち上げ

$f (x)$ を整数（またはテンプレート:Mvar 進整数）を係数とする多項式とし、テンプレート:Mvar とテンプレート:Mvar をテンプレート:Mvar ≤ テンプレート:Mvar を満たす正の整数とする。整数テンプレート:Mvar に対して

f (r) \equiv 0 {mod p}^{k} and f^{'} (r) \equiv̸ 0 mod p

が成り立ったとする。このとき、任意の $m > 0$ に対してある整数テンプレート:Mvar が存在して

f (s) \equiv 0 {mod p}^{k + m} and r \equiv s {mod p}^{k}

が成り立つ。このテンプレート:Mvar は法テンプレート:Math で一意であり、次の式

s = r - f (r) \cdot a

で具体的に計算できる整数である。ここで $a$ は次の式

a \equiv [f^{'} (r)]^{- 1} {mod p}^{m}

を満たす整数である。先程の式でテンプレート:Mvar を定めれば、 $f (r) \equiv 0 {mod p}^{k}$ なので条件 $s \equiv r {mod p}^{k}$ は満たされている。なお、 $f^{'} (r) \equiv 0 mod p$ であるときは、持ち上げテンプレート:Mvar は存在しないかもしれないし複数存在するかもしれない（あとで「#ヘンゼル持ち上げ」で例示する）。

証明

テンプレート:Mvar のテンプレート:Mvar まわりでのテイラー展開

f (s) = \sum_{n = 0}^{N} c_{n} (s - r)^{n}, c_{n} = f^{(n)} (r) / n!

を使う。 $r \equiv s {mod p}^{k}$ なのである整数テンプレート:Mvar が存在してテンプレート:Math とかける。これを使うと

\begin{matrix} f (s) & = \sum_{n = 0}^{N} c_{n} {(t p^{k})}^{n} \\ = f (r) + t p^{k} f^{'} (r) + \sum_{n = 2}^{N} c_{n} t^{n} p^{k n} \\ = f (r) + t p^{k} f^{'} (r) + p^{2 k} t^{2} g (t) & g (t) \in ℤ [t] \\ = z p^{k} + t p^{k} f^{'} (r) + p^{2 k} t^{2} g (t) & f (r) \equiv 0 {mod p}^{k} \\ = (z + t f^{'} (r)) p^{k} + p^{2 k} t^{2} g (t) \end{matrix}

と計算できる。 $m ⩽ k$ としていたので、

\begin{matrix} f (s) \equiv 0 {mod p}^{k + m} & ⟺ (z + t f^{'} (r)) p^{k} \equiv 0 {mod p}^{k + m} \\ ⟺ z + t f^{'} (r) \equiv 0 {mod p}^{m} \\ ⟺ t f^{'} (r) \equiv - z {mod p}^{m} \\ ⟺ t \equiv - z [f^{'} (r)]^{- 1} {mod p}^{m} & p ∤ f^{'} (r) \end{matrix}

である。 $f^{'} (r)$ はテンプレート:Mvar で割り切れないという仮定から、 $f^{'} (r)$ は法 $p^{m}$ で逆元を持ち、しかもそれは一意でなければならない。したがって、最後の式のテンプレート:Mvar についての解は法 $p^{m}$ で一意に存在し、テンプレート:Mvar は法 $p^{k + m}$ で一意に存在する。

ヘンゼル持ち上げ

補題を使って、多項式テンプレート:Mvar の法テンプレート:Math での根テンプレート:Mvar を法テンプレート:Math での新しい根テンプレート:Mvar にテンプレート:Mvar ≡ テンプレート:Mvar mod テンプレート:Math となるように持ち上げることができる。（テンプレート:Math と取る。数学的帰納法により大きいテンプレート:Mvar はしたがう）。

また、法テンプレート:Math での根は法テンプレート:Math での根でもあるので、法テンプレート:Math での根はすべて法テンプレート:Math での根の持ち上げである。

持ち上げた根テンプレート:Mvar は法テンプレート:Mvar でテンプレート:Mvar と合同なので、新しい根も $f^{'} (s) \equiv f^{'} (r) \equiv̸ 0 mod p$ を満たす。

したがって、最初の根テンプレート:Math が $f^{'} (r_{k}) \equiv̸ 0 mod p$ を満たせば持ち上げの操作は繰り返すことができ、 $f (x) \equiv 0 {mod p}^{k}$ の解テンプレート:Math からはじめて、テンプレート:Mvar の高次冪に対して同じ合同式を満たす解の数列テンプレート:Math, テンプレート:Math, ... を作れる。

このことはまた、テンプレート:Mvar の法テンプレート:Math での根が全て単根であれば、テンプレート:Mvar の法テンプレート:Math での根の数は法テンプレート:Math, テンプレート:Math, ... での根の数と同じであることを示している。

テンプレート:Mvar が法テンプレート:Math で単根になっていないとき、このプロセスでは何が起きているのであろうか? これを見るために、次の状況

f (r) \equiv 0 {mod p}^{k} and f^{'} (r) \equiv 0 mod p

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

$f (r) \equiv̸ 0 {mod p}^{k + 1}$ ならテンプレート:Mvar の法テンプレート:Math へのテンプレート:Math の根の持ち上げは存在しない。

$f (r) \equiv 0 {mod p}^{k + 1}$ ならテンプレート:Mvar の任意の法テンプレート:Math への持ち上げはテンプレート:Math の法テンプレート:Math での根である。

例: テンプレート:Math として両方のケースを見てみよう。

$f (x) = x^{2} + 1$ とし、テンプレート:Math とする。このとき、 $f (1) \equiv 0 mod 2$ で $f^{'} (1) \equiv 0 mod 2$ である。 $f (1) \equiv̸ 0 mod 4$ なので、1の法4への持ち上げでテンプレート:Math の法4での根になるものは存在しない。

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

テンプレート:Mvar 進数の場合のヘンゼルの補題

テンプレート:Mvar 進数では、テンプレート:Mvar の冪乗を法とする有理数の合同類というものを、分母がテンプレート:Mvar の倍数でなければ考えることができる。このことを使うと、法テンプレート:Math での根テンプレート:Math から法テンプレート:Math での根テンプレート:Math を求める反復計算をずっと直感的に行うことができる。次の合同式

t f^{'} (r_{k}) \equiv - (f (r_{k}) / p^{k}) {mod p}^{m}

を解いて整数テンプレート:Mvar を見つける代わりに、有理数テンプレート:Mvar を次の式

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

で定める。分母にテンプレート:Math が出てくるように見えるが、テンプレート:Math がテンプレート:Math で割れるため実際には出てこない。そして

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

と置く。これは整数にはならないかもしれないが、テンプレート:Mvar 進整数にはなっている。数列テンプレート:Math はあるテンプレート:Mvar 進整数に収束し、極限はテンプレート:Math の解になっている。そして、テンプレート:Math からテンプレート:Math を計算する漸化式をよく見てみると、実数の場合における求根アルゴリズムであるニュートン法の漸化式とまったく同じになっている。

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

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

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

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

例

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

f (r) = r^{2} - a \equiv 0 mod p and f^{'} (r) = 2 r \equiv̸ 0 mod p

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

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

が成り立つように作ることができる。この列はあるテンプレート:Mvar 進整数テンプレート:Mvar に収束しテンプレート:Math を満たす。

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

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

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

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

t f^{'} (r_{1}) \equiv - (f (r_{1}) / p^{k}) mod p

は

t \cdot 6 \equiv - 1 mod 7

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

r_{2} = r_{1} + t p^{1} = 3 + 1 \cdot 7 = 10 = 1 3_{7}

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

次の反復計算を行うと $r_{3} = 108 = 3 + 7 + 2 \cdot 7^{2} = 21 3_{7}$ となる。この計算を1回繰り返すごとに（つまりテンプレート:Mvar の値が1つ増えていく度に）次の7の冪乗の項が追加され7進数での桁が1つが増えていく。7進整数環の中でこの数列は収束し、その極限は $ℤ_{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} + \dots

となる。

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

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

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

が成り立つ。これから、ある2進整数テンプレート:Mvar で

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

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

$x^{2} - 17$ の根を法テンプレート:Math から法テンプレート:Math へ持ち上げるやり方の場合、法2での根1からの持ち上げの過程は次のようになる。

テンプレート:Math はテンプレート:Math に持ち上がる。

テンプレート:Math はテンプレート:Math に、テンプレート:Math はテンプレート:Math に持ち上がる。

テンプレート:Math はテンプレート:Math に、テンプレート:Math はテンプレート:Math に持ち上がる。一方、テンプレート:Math とテンプレート:Math はテンプレート:Math での根に持ち上がらない。

テンプレート:Mvar が3以上であればテンプレート:Math には4つの根がある。しかし2進極限は2つしかない。持ち上げられた根と極限の2進展開を比べてみよう。例えば、法32での4つの根を法16で等しくなるものを組にして書くと次のようになる。

テンプレート:Math とテンプレート:Math

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

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

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

となっている。

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

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

同様にして、少し準備が必要だが、ヘンゼルの補題を使って任意の奇素数テンプレート:Mvar に対して法テンプレート:Math で1と合同な全てのテンプレート:Mvar 進整数テンプレート:Mvar は $ℤ_{p}$ のテンプレート:Mvar 冪乗数であることを示すことができる（テンプレート:Math の場合はこれは成り立たない）^[4]。

多変数への一般化

1つの多項式

ヘンゼルの補題は多変数の多項式への一般化もある。テンプレート:Math を整数係数の多項式とし、ディオファントス方程式

テンプレート:Math

を考える。これがある素数テンプレート:Mvar に対してテンプレート:Math （テンプレート:Mvar は非負整数）で解テンプレート:Nowrap を持ったとする。つまりテンプレート:Math が成り立ったとする。さらに、少なくとも1つの変数についてテンプレート:Mvar の偏微分のテンプレート:Math における値がテンプレート:Math でゼロではなかったとする。このとき、テンプレート:Math はテンプレート:Math でテンプレート:Math と等しいテンプレート:Math での解に持ち上がるテンプレート:Sfn。同様にテンプレート:SubSup の解に持ち上げることもできるので、このディオファントス方程式はテンプレート:Mvar 進整数環 Z_{テンプレート:Mvar} で解を持つテンプレート:Sfn。

複数の多項式

テンプレート:Mvar をイデアル $𝔪$ について完備な可換環とし、 $f (x) \in A [x]$ とする。次の式

f (a) \equiv 0 {mod f}^{'} (a)^{2} 𝔪 .

を満たすテンプレート:Math のことをテンプレート:Mvar の近似根と呼ぶ。テンプレート:Mvar が近似根を持つなら、テンプレート:Mvar に"近い"本当の根テンプレート:Math も持つ。つまり、次の式

f (b) = 0 and b \equiv a mod 𝔪

を満たすテンプレート:Mvar が存在する。さらに、 $f^{'} (a)$ が零因子でないならば、テンプレート:Mvar は一意的である。

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

定理: テンプレート:Mvar を可換環でイデアル

𝔪 \subset A

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

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

をテンプレート:Mvar 係数のテンプレート:Mvar 個のテンプレート:Mvar 変数多項式とする。

𝐟 = (f_{1}, \dots, f_{n})

をテンプレート:Math から自身への写像と考え、

J_{𝐟} (𝐱)

をそのヤコビ行列とする。テンプレート:Math = テンプレート:Math をテンプレート:Math の近似解、つまり

f_{i} (𝐚) \equiv 0 mod (\det J_{𝐟} (a))^{2} 𝔪, 1 ⩽ i ⩽ n

が成り立つものとする。このとき、あるテンプレート:Math でテンプレート:Math を満たすもの、つまり

f_{i} (𝐛) = 0, 1 ⩽ i ⩽ n

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

b_{i} \equiv a_{i} mod \det J_{𝐟} (a) 𝔪, 1 ⩽ i ⩽ n

が成り立つという意味でテンプレート:Math に"近い"解である。

この定理の特別な場合として、 $f_{i} (𝐚) \equiv 0 mod 𝔪$ がすべてのテンプレート:Mvar に対して成り立ち、しかも $\det J_{𝐟} (𝐚)$ がテンプレート:Mvar の単数なら、解テンプレート:Math ですべてのテンプレート:Mvar に対して $b_{i} \equiv a_{i} mod 𝔪$ が成り立つものが存在することがわかる。

テンプレート:Math の場合、テンプレート:Math はテンプレート:Mvar の元で $J_{𝐟} (𝐚) = J_{f} (a) = f^{'} (a)$ である。したがって、この多変数のヘンゼルの補題の仮定は1変数の場合には通常のヘンゼルの補題の仮定と同じになっている。

脚注

テンプレート:脚注ヘルプ

注釈

テンプレート:Notelist

出典

テンプレート:Reflist

ヘンゼルの補題

目次

還元と持ち上げ

ヘンゼルの補題の主張

単根の持ち上げ

完備化への持ち上げ

証明

1次持ち上げ

一意性

2次持ち上げ

具体例

微分を用いた根の持ち上げ

証明

関連する諸結果

多項式の既約性判定

フロベニウス

1の冪根

ヘンゼル持ち上げ

テンプレート:Mvar 進数の場合のヘンゼルの補題

例

多変数への一般化

1つの多項式

複数の多項式

関連概念

脚注

注釈

出典

参考文献

関連項目

ナビゲーションメニュー

ヘンゼルの補題

還元と持ち上げ

ヘンゼルの補題の主張

単根の持ち上げ

完備化への持ち上げ

証明

1次持ち上げ

一意性

2次持ち上げ

具体例

微分を用いた根の持ち上げ

証明

関連する諸結果

多項式の既約性判定

フロベニウス

1の冪根

ヘンゼル持ち上げ

テンプレート:Mvar 進数の場合のヘンゼルの補題

例

多変数への一般化

1つの多項式

複数の多項式

関連概念

脚注

注釈

出典

参考文献

関連項目

ナビゲーション メニュー

検索

ナビゲーションメニュー