ヘンゼルの補題

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

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

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

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

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

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

還元と持ち上げ

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

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

を可換環、をのイデアルとする。の元を

による像で置き換えることを、を法とする還元、または法での還元と呼ぶ。

例えば、を

係数の多項式とするとき、その

を法とする還元

とは、の係数を

での像に置き換えることで得られる

の多項式のことをいう。の2つの多項式とが法で係数が等しくなるとき、つまり

であるとき、この2つの多項式は法で合同であるといい、で表す。の法での因数分解とは、を法で

の2つ（以上）の多項式の積として書き表す

ことをいう。

持ち上げとは還元の逆の操作である。つまり、の元を使って表されている対象があったとき、持ち上げとは対象の性質を保ったまま還元するとこの対象に等しくなるように（もしくはあるに対する）の元に置き換えることをいう。

例えば、多項式

が法で

と因数分解されているとき、この因数分解を法

へ持ち上げるとは、多項式

であって

を満たすものを見つけることである。ヘンゼルの補題は、この因数分解の持ち上げが緩い条件のもとで常に可能であることを主張するものである。

ヘンゼルの補題の主張

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

を可換環、をその極大イデアルの1つ、そして

を

の多項式で最高次の係数

が

に含まれないものとする。

を極大イデアルとしているので、その剰余環

は体である。したがって

は単項イデアル整域なので、特に一意分解環である。これは、任意のゼロではない

の多項式は

のゼロでない元とモニック（最高次の係数が1という意味）な既約多項式の積として一意的にかけることを意味する。

ヘンゼルの補題は、の法

での互いに素な多項式への因数分解は、任意の

に対して

を法とする因数分解に一意的に持ち上げられることを主張する。

もう少し詳しく書くと、上述の仮定のもとで、法でモニックかつな多項式とを使って

と分解できたとすると、全ての正の整数に対してモニック多項式

と

が存在して次の式

が成り立ち、しかもこのような性質を持つ

と

は法

で一意ということを主張する。

単根の持ち上げ

大切で特別な場合として

であるときを考える。この場合、互いに素という仮定はは

の単根であるということを意味する。したがってこの場合にはヘンゼルの補題の主張は次のようになる（これもヘンゼルの補題と言われる）。

記号と仮定は今までと同じとし、を

の単根とする。このとき、は全ての正の整数に対して

の単根に一意的に持ち上げることができる。つまり、任意の正の整数対して

の単根

であって

を満たすものが一意的に存在する。

完備化への持ち上げ

全ての正の整数に対して

に持ち上げることができるので、を限りなく大きくしていったときの"極限"を考えたくなる。これが進整数が考案された主な理由の1つである。

を可換環、を極大イデアルとすると、のベキたちはの進位相と呼ばれる位相についての基本近傍系になる。この位相による完備化は局所環

の完備化と同一視でき、また射影極限

とも同一視できる。この完備局所環は

と一般的に書き表される。が整数環で（は素数）であるときには、この完備局所環は進整数環

である。

完備化の射影極限を使った定義と上述のヘンゼルの補題の主張から、多項式

の法

での因数分解がどの2つの因子を取っても互いに素であるなら、それは

の

における像の因数分解に一意的に持ち上げられることが導かれる。同様に、の法

での任意の単根はの

における像の単根に持ち上げられる。

証明

ヘンゼルの補題は、での因数分解を

での因数分解に持ち上げる（#1次持ち上げ）ことを繰り返すか、または

での因数分解に持ち上げる（#2次持ち上げ）ことを繰り返すことにより証明されることが多い。

証明では、体を係数とするに対してベズーの等式が成り立つということが重要な役割を果たす。ベズーの等式とは、体（ここで使うのは

の場合）を係数とする互いに素な1変数多項式とがあったとすると、ある多項式とであって、かつ

かつ次の式

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

ベズーの等式が成り立てば

が極大イデアルではなくともヘンゼルの補題を証明することができる。

それゆえ、以下ではを可換環、をそのイデアル、を最高次係数が法で可逆（における像がの可逆元ということ）な多項式、もしくはの冪乗を法とするの因数分解に現れる因子が法でベズーの等式を満たす、という設定のもとで証明を行う。証明では、という式で

であることを表すことにする。

1次持ち上げ

を可換環、をそのイデアル、を

係数の1変数多項式で最高次の係数

が法で可逆（のにおける像がの可逆元という意味）であるものとする。

そして何らかの正の整数に対して

と因数分解でき、と

はモニック多項式で法

で互いに素だったとする。ここで、"互いに素"というのはある

が存在して

という意味で使っている。このとき、多項式

であって

かつ

かつ次の式

が成り立つものが存在する。しかもこれらの条件が成り立つ

と

は法

で一意的に定まる。

そして

と

はとが満たすベズーの等式を同様に満たす。つまり

が成り立つ。なぜ直前の主張からすぐにわかるこのことをあえて述べたかというと、の値を１つ大きくして反復計算を進めるときに、これが次のステップでの前提条件が満たされていることを意味するからである。

次に示す証明は、または

を係数とする多項式だけを使って

と

を計算することによりなされている。で

の場合には、これは法での剰余類だけを使って計算できることを意味する。

証明：仮定から

は法で可逆である。したがって、ある

と

で

を満たすものが存在する。

多項式

を、次数が

未満で

が成り立つものとする。と置いてもよいが、他のものを選んだ方が計算が簡単になることがある。例えば

で

の場合には、係数が区間に入る整数係数の多項式

を使って

と表せるようなものを取ることができるので、こう取ったほうがよい。

はモニックなので、多項式に対する除法の原理を

とに適用し、とで

かつ

となるものを見つけることができる。このとは

に入っている。同様に、で

かつ

となるものを取る。

このとき

である。実際、まず

が成り立っている。はモニックなので、の法

での次数が

の次数よりも小さくなるのは

のときだけである。

こうして、

を法とする合同を考えることにより次の式

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

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

一意性

記号、、、は前節と同じとする。が

と、となる互いに素な多項式（前述の意味で）に因数分解できたとする。1次持ち上げを

に適用して、多項式

と

であって

かつ

かつ次の式

を満たすものの存在がわかる。この多項式

と

は法

で一意に定まる。つまり、同じ条件を満たす組

が他にあったとすると、

が成り立つ。

証明: を法とする合同は

を法とする合同を意味するので、数学的帰納法を使って証明する。の場合は明らかである。の場合の一意性は証明されているものと仮定する。つまり、

と仮定する。仮定により

が成り立ち、これから

が成り立つ。帰納法の仮定から右辺の2番目の項は

に含まれ、（左辺もそうなので）同じことが初項についても成り立つ。は法で可逆なので、ある

と

が存在して

が成り立つ。これと帰納法の仮定から

が成り立つ。

法で互いに素という仮定から、ある

が存在して

が成り立つ。帰納法の仮定をもう一度使うと

となる。したがって、次数が

未満の多項式が法

でモニック多項式ともう1つの多項式の積と合同になったことになる。これが起こり得るのは

の場合だけなので、これから

が得られる。同様に

も

に含まれることが示せるので、これで一意性が証明できた。

2次持ち上げ

1次持ち上げは法

での因数分解を法

での因数分解に持ち上げるものであった。2次持ち上げでは法

での因数分解に一気に持ち上げる。しかし、ベズーの等式の持ち上げも必要になり、（上述の1次持ち上げでは）法での計算だけで済んだが法

での計算が必要になるため、追加の計算コストがかかる。

どちらの方法でも大きなに対して法

まで持ち上げることができる。例えば

の場合に法

まで因数分解を持ち上げるためには、1次持ち上げを使うと回の反復計算が必要になるが、 2次持ち上げを使えば回の反復計算で済む。しかし、2次持ち上げを使う方法では扱わなければならない係数のサイズが計算中に増大していく。これは、一番いい持ち上げの方法は、の値やの性質、使用する乗算アルゴリズム、ハードウェアの特性などの状況に依存することを意味する。

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

ある正の整数に対して因数分解

があったとし、とはモニック多項式で、ある

が存在し

が成り立つという意味で法

で互いに素だったとする。このとき、ある多項式

が存在し、かつ

かつ

が成り立つ。さらに

と

は次の形のベズーの等式

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

証明: 最初の主張は1次持ち上げをでの代わりにイデアルに対して適用することでわかる。

と置く。次の式

が、

と置くことで成り立つ。2つの多項式を

と

で定めると

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

具体例

多項式

を考えよう。

この多項式に対して法2でのヘンゼルの補題を適用することはできない。なぜなら

を法 2 で還元すると単に pg 15-16

となり、この6つの因子

はどの2つを取っても互いに素ではないからだ。しかし、アイゼンシュタインの既約判定法を使って多項式

が

で既約であることは示せる。

一方、では

となる。は

における2の平方根である。4は

における立方数ではないので、この2つの因子は

上既約である。したがって

の（または）における既約多項式への因数分解は

となる。ここで

は

における2の平方根で、先ほどの因数分解を持ち上げることで得られる。

最後に、この多項式は

においては

と分解する。これらの因子はどの2つを取っても互いに素なので、（または）において6つの多項式

の積に分解する。は（有理数ではない）727進数

である。

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

を整数（または進整数）を係数とする多項式とし、とを ≤ を満たす正の整数とする。整数に対して

が成り立ったとする。このとき、任意の

に対してある整数が存在して

が成り立つ。このは法

で一意であり、次の式

で具体的に計算できる整数である。ここで

は次の式

を満たす整数である。先程の式でを定めれば、なので条件

は満たされている。なお、であるときは、持ち上げは存在しないかもしれないし複数存在するかもしれない（あとで「#ヘンゼル持ち上げ」で例示する）。

証明

のまわりでのテイラー展開

を使う。なのである整数が存在して

とかける。これを使うと

と計算できる。としていたので、

である。はで割り切れないという仮定から、は法

で逆元を持ち、しかもそれは一意でなければならない。したがって、最後の式の

についての解は法

で一意に存在し、は法

で一意に存在する。

関連する諸結果

多項式の既約性判定

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

が

だったとすると、

である。の場合だと、で

であるが、なので、この多項式は既約ではありえない。一方

では両方の値が等しいので既約である可能性がある。既約であるかどうか決定するためにはニュートンの多角形を使う必要があるpg 144。

フロベニウス

に対してフロベニウス自己準同型

による多項式

を考える。この微分は

となり常にゼロである。

1の冪根

1の

乗根は

に存在しないが、方程式

の解は存在する。次の式

は決してゼロにならないので、解が存在すればそれは

に持ち上げることができる。フロベニウスにより

なので、ゼロではない元全体

が解全体である。実は、に含まれる1の冪根はこれらだけであるConrad, p. 25. Theorem 3.1.。

ヘンゼル持ち上げ

補題を使って、多項式の法

での根を法

での新しい根に ≡ mod となるように持ち上げることができる。（と取る。数学的帰納法により大きいはしたがう）。

また、法

での根は法

での根でもあるので、法

での根はすべて法

での根の持ち上げである。

持ち上げた根は法で

と合同なので、新しい根も

を満たす。

したがって、最初の根

が

を満たせば持ち上げの操作は繰り返すことができ、の解

からはじめて、の高次冪に対して同じ合同式を満たす解の数列 , , ... を作れる。

このことはまた、の法

での根が全て単根であれば、

の法

での根の数は法 , , ... での根の数と同じであることを示している。

が法

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

を考えよう。このとき、は

を意味する。つまり任意の整数に対して

が成り立つ。それゆえ次の2つの場合がある。

ならの法へのの根の持ち上げは存在しない。

ならの任意の法への持ち上げはの法での根である。

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

とし、とする。このとき、で

である。なので、1の法4への持ち上げでの法4での根になるものは存在しない。

、とする。すると

かつ

である。また、であるので、この解を法4へ持ち上げることができ、2つの持ち上げ（1と3）はともに解である。これらの解に対しても微分は法2でやはり0であるので、アプリオリにはこれらを法8に持ち上げられるかどうかは分からない。しかし実際にはもも法8で0と合同であるので持ち上げることができる。法8では1, 3, 5, 7が解である。これらの中でとだけが法16で0なので、1と7だけが法16に持ち上げることができ、それらは1, 7, 9, 15である。これらの中では7と9だけが

なので、同様に法32での解7, 9, 23, 25が得られる。任意の整数に対して法2での

の根1の法

の根への持ち上げは4つ存在することがわかる。

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

進数では、の冪乗を法とする有理数の合同類というものを、分母が

の倍数でなければ考えることができる。このことを使うと、法での根

から法での根

を求める反復計算をずっと直感的に行うことができる。次の合同式

を解いて整数

を見つける代わりに、有理数

を次の式

で定める。分母にが出てくるように見えるが、が

で割れるため実際には出てこない。そして

と置く。これは整数にはならないかもしれないが、進整数にはなっている。数列

はある進整数に収束し、極限は

の解になっている。そして、から

を計算する漸化式をよく見てみると、実数の場合における求根アルゴリズムであるニュートン法の漸化式とまったく同じになっている。

進数の中で計算を行い進絶対値を使うことで

となってしまう

の解についても使えるようにしたヘンゼル補題がある。が0になってしまわないことは必要である。この一般化されたヘンゼルの補題は次のようになる。整数で

を満たすものがあったとすると、進整数でかつ

となるものが一意的に存在する。このを作るにはニュートン法の漸化式が初期値

で進数に収束することを示しその極限を

と置けばよい。条件を満たす根としてが一意であることを示すには追加の議論がいる。

先ほどのヘンゼルの補題のの場合はこの一般化された補題の特殊な場合になっている。条件

と

は

と

を意味するからである。

例を奇素数、を0ではないを法とする平方剰余とする。このとき、進整数環の中にの平方根が存在することをヘンゼルの補題を使って示すことができる。これを見るために

と置く。を法でのの平方根とすると

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

が成り立つように作ることができる。この列はある進整数に収束し

を満たす。

このは、法でと合同になる

における

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

以上の議論をもっと具体的に理解するために、7進整数環の中で"2の平方根"、つまり方程式

の解を見つけてみよう。この方程式の法7での解の1つは3（もう1つの解は4）なので、としよう。ヘンゼルの補題における

の計算式に現れる各種の数値は

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

は

となり、これは

を意味する。したがって、

と計算できた。簡単に確かめられるように、が成り立っている（ニュートン法の反復を直接7進数で使うと、となる。なので整合している）。

次の反復計算を行うと

となる。この計算を1回繰り返すごとに（つまりの値が1つ増えていく度に）次の7の冪乗の項が追加され7進数での桁が1つが増えていく。7進整数環の中でこの数列は収束し、その極限は

での2の平方根となる。その7進展開の初めの方は

となる。

最初に

を選んだ場合でも

における2の平方根が得られる。これは法7で3ではなく4に合同になるもので、実は最初に得られた平方根を-1倍したものになっている（これは

であることと辻褄があっている）。

元々のヘンゼルの補題は適用できないが一般化されたものなら適用できる例として

を考える。とすると

であり、また

であるので、

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

を満たすものが一意に存在する。二番目の式は

を意味する。2進整数の中には17の平方根が2つ存在し、それらは符号が異なり、法2では合同であるが法4では合同ではない。これは、一般化された形のヘンゼルの補題から得られるのが法2ではなく法4で1と合同な17の2進平方根で、法4で一意であることと整合的である。最初の近似根として

を取った場合でも一般化されたヘンゼルの補題を適用することができ、法4で3と合同になる唯一の17の2進平方根をやはり見つけることができる。これがもう1つの17の2進平方根である。

の根を法

から法

へ持ち上げるやり方の場合、法2での根1からの持ち上げの過程は次のようになる。

はに持ち上がる。はに、はに持ち上がる。はに、はに持ち上がる。一方、とはでの根に持ち上がらない。はに、はに持ち上がる。一方、とはでの根に持ち上がらない。

が3以上であれば

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

とと

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

となっている。

基本形は使えないが一般化された形のヘンゼルの補題なら使えるもう１つの例として、である任意の3進整数は

で立方数になることの証明を見よう。と置き、最初の近似根として

を取る。任意のに対して

となってしまうので、基本形のヘンゼルの補題を使って

の根を見つけることはできない。

一般形のヘンゼルの補題を適用するためには

である必要がある。これは

ということである。つまり、

であれば一般形のヘンゼルの補題から

が3進根を持つことがわかり、が3進立方数であることがわかる。しかし、

というより弱い条件のもとでこの結果が欲しい。であれば、である。この3つの

の値に応じて初期値を使い分けて一般形のヘンゼルの補題を適用する。なら、を使う。なら、を使う（4は法27でのの根）。なら、を使う。なお、任意の

は3進立方数になる、という主張は正しくない。例えば、4は法9で立方数にならないので3進立方数ではない。

同様にして、少し準備が必要だが、ヘンゼルの補題を使って任意の奇素数に対して法

で1と合同な全ての進整数は

の冪乗数であることを示すことができる（の場合はこれは成り立たない）Conrad, p. 6. Theorem 4.5. を使う。。

多変数への一般化

1つの多項式

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

を考える。これがある素数に対して（は非負整数）で解

を持ったとする。つまり

が成り立ったとする。さらに、少なくとも1つの変数についての偏微分のにおける値がでゼロではなかったとする。このとき、はでと等しい

での解に持ち上がる。同様にの解に持ち上げることもできるので、このディオファントス方程式は進整数環 Z で解を持つ。

複数の多項式

をイデアル

について完備な可換環とし、とする。次の式

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

を満たすが存在する。さらに、が零因子でないならば、は一意的である。

このことは多変数の場合に次のように一般化できるが進整数環の場合の証明が次にある: .。

定理: を可換環でイデアルについて完備なものとする。を係数の個の変数多項式とする。をから自身への写像と考え、をそのヤコビ行列とする。 = をの近似解、つまり

が成り立つものとする。このとき、あるでを満たすもの、つまり

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

が成り立つという意味でに"近い"解である。

この定理の特別な場合として、がすべてのに対して成り立ち、しかも

が

の単数なら、解

ですべてのに対して

が成り立つものが存在することがわかる。

の場合、

はの元で

である。したがって、この多変数のヘンゼルの補題の仮定は1変数の場合には通常のヘンゼルの補題の仮定と同じになっている。

ヘンゼルの補題

Źródło i licencja