ヘンゼルの補題
数学のヘンゼルの補題(ヘンゼルのほだい、Hensel's lemma)とは、1変数多項式が素数 p を法として単根を持つならば、その根は p の任意の冪乗を法とする根に一意的に持ち上げられるという、合同算術における補題である。この補題は、多項式が法 p で2つの最大公約多項式に因数分解できるならば、その因数分解は p の任意の冪乗を法とする因数分解に持ち上げることができるという補題に一般化できる。因数分解に現れる多項式の次数が1の場合が根の場合に相当する。ヘンゼルの持ち上げ補題(Hensel's lifting lemma)とも呼ばれる。名称はクルト・ヘンゼルに因む。
p の冪指数を無限に大きくしていったときの(射影極限の意味での)極限を取ることにより、法 p での根(または因数分解)を p 進整数上での根(または因数分解)に持ち上げることができる。
この補題は、任意の可換環を係数とする多項式に対して、p をイデアル、「互いに素な2つの多項式」を「2つの多項式が生成するイデアルが1を含む」に置き換えることにより一般化できる。一般化された補題も同じ名前で呼ばれる。
ヘンゼルの補題は、解析的整数論の一分野である p 進解析学の基礎である。
ヘンゼルの補題の証明は構成的証明であり、証明からヘンゼル持ち上げの効率的なアルゴリズムが得られる。これは多項式の因数分解のアルゴリズムの基礎である。また有理数体上の線型代数学についての最も効率の良いアルゴリズムが得られる。
ヘンゼルの補題は、ヘンゼルよりも早く1846年にテオドル・シェーネマンによって証明されていた。また、「存在」についての主張だけならシェーネマンよりも早くカール・フリードリヒ・ガウスによっても知られていた。
もともとのヘンゼルの補題は、整数を係数とする多項式の因数分解と、素数 p、もしくはその冪乗を法とする剰余類環を係数とする多項式の因数分解との関係についてのものであった。素数
p を極大イデアルに置き換えることで、この補題は整数から任意の可換環へそのまま一般化できる(\Z の極大イデアルはある素数 p で p\Z と書けるのであった)。
この一般化を正確に書くためには、整数の場合の合同算術を一般化しておく必要があるので、この文脈で通常使われる用語を正確に定義しておこう。
R\to R/I
による像で置き換えることを、I を法とする還元、または法 I での還元と呼ぶ。
例えば、f\in R[X]
係数の多項式とするとき、その
f \bmod I
とは、f の係数を
R/I
(R/I)[X]=R[X]/IR[X]
の多項式のことをいう。R[X]
の2つの多項式 f と g が法
I で係数が等しくなるとき、つまり
f-g\in IR[X]
であるとき、この2つの多項式は法 I で合同であるといい、f\equiv g \pmod I
で表す。h\in R[X]
の法 I での因数分解とは、h を法 I で
R[X]
の2つ(以上)の多項式 f, g の積として書き表す
h\equiv fg \pmod I
ことをいう。
持ち上げとは還元の逆の操作である。つまり、R/I
の元を使って表されている対象があったとき、持ち上げとは対象の性質を保ったまま還元するとこの対象に等しくなるように
R(もしくはある k > 1 に対する R/I^k)の元に置き換えることをいう。
例えば、多項式
h\in R[X]
が法 I で
h\equiv fg \pmod I
と因数分解されているとき、この因数分解を法
I^k
へ持ち上げるとは、多項式
f',g'\in R[X]
f'\equiv f \pmod I,
g'\equiv g \pmod I,
h\equiv fg \pmod {I^k}
を満たすものを見つけることである。ヘンゼルの補題は、この因数分解の持ち上げが緩い条件のもとで常に可能であることを主張するものである。
元々のヘンゼルの補題は、整数を係数とする多項式の素数 p を法とする因数分解を
p の冪乗を法とする因数分解、もしくは
p 進整数環上の因数分解に持ち上げることを主張(そして証明)するものであった。この補題は、整数を任意の可換環、素数を極大イデアル、そして
p 進整数環をその極大イデアルについての完備化に置き換えることで簡単に一般化できる。証明の仕方も同じである。この一般化された補題も広く用いられる。本記事で述べるのもこれである。
R を可換環、\mathfrak m をその極大イデアルの1つ、そして
h=\alpha_0X^n+\cdots +\alpha_{n-1}X+\alpha_n
R[X]
\alpha_0
\mathfrak m
に含まれないものとする。
\mathfrak m
を極大イデアルとしているので、
R/\mathfrak m
は体である。したがって
(R/\mathfrak m)[X]
は単項イデアル整域なので、
特に一意分解環である。これは、任意のゼロではない
(R/\mathfrak m)[X]
(R/\mathfrak m)
のゼロでない元とモニック(最高次の係数が1という意味)な既約多項式の積として一意的にかけることを意味する。
ヘンゼルの補題は、h の法
\mathfrak m
での互いに素な多項式への因数分解は、任意の
\mathfrak m^k
を法とする因数分解に一意的に持ち上げられることを主張する。
もう少し詳しく書くと、上述の仮定のもとで、法
\mathfrak m でモニックかつ最大公約多項式な多項式
h\equiv \alpha_0 fg\pmod \mathfrak m
と分解できたとすると、全ての正の整数 k に対してモニック多項式
f_k
g_k
\begin{align}
h&\equiv \alpha_0 f_kg_k \pmod{\mathfrak m^k}\\
f_k&\equiv f\pmod{\mathfrak m}\\
g_k&\equiv g\pmod{\mathfrak m}
\end{align}
が成り立ち、しかもこのような性質を持つ
f_k
g_k
\mathfrak m^k
で一意ということを主張する。
f=X-r
であるときを考える。この場合、互いに素という仮定は
r は
h \bmod \mathfrak m
の単根であるということを意味する。したがってこの場合にはヘンゼルの補題の主張は次のようになる(これもヘンゼルの補題と言われる)。
記号と仮定は今までと同じとし、r を
h \bmod \mathfrak m
の単根とする。このとき、r は全ての正の整数 n に対して
h \bmod {\mathfrak m^n}
の単根に一意的に持ち上げることができる。つまり、任意の正の整数 n 対して
h \bmod \mathfrak m^n
r_n\in R/{\mathfrak m}^n
r_n\equiv r \pmod \mathfrak m
を満たすものが一意的に存在する。
全ての正の整数 n に対して
R/\mathfrak m^n
に持ち上げることができるので、n
を限りなく大きくしていったときの"極限"を考えたくなる。これが p 進整数が考案された主な理由の1つである。
R を可換環、\mathfrak m
を極大イデアルとすると、\mathfrak m
R の \mathfrak m 進位相と呼ばれる位相についての基本近傍系になる。この位相による完備化は局所環
R_\mathfrak m
の完備化と同一視でき、また射影極限
\lim_\leftarrow R/\mathfrak m^n
とも同一視できる。この完備局所環は
\widehat R_\mathfrak m
と一般的に書き表される。R が整数環で
\mathfrak m=p\Z(p は素数)であるときには、この完備局所環は p 進整数環
\Z_p
である。
完備化の射影極限を使った定義と上述のヘンゼルの補題の主張から、多項式
h\in R[X]
\mathfrak m
での因数分解がどの2つの因子を取っても互いに素であるなら、それは
\widehat R_\mathfrak m[X]
における像の因数分解に一意的に持ち上げられることが導かれる。同様に、h の法
\mathfrak m
h の
\widehat R_\mathfrak m[X]
における像の単根に持ち上げられる。
ヘンゼルの補題は、R/\mathfrak m^n
R/\mathfrak m^{n+1}
での因数分解に持ち上げる(#1次持ち上げ)ことを繰り返すか、または
R/\mathfrak m^{2n}
での因数分解に持ち上げる(#2次持ち上げ)ことを繰り返すことにより証明されることが多い。
証明では、体を係数とする最大公約多項式に対してベズーの等式が成り立つということが重要な役割を果たす。ベズーの等式とは、体(ここで使うのは
R/\mathfrak m
の場合)を係数とする互いに素な1変数多項式
があったとすると、ある多項式 a と b であって、\deg a <\deg g
\deg b <\deg f
af+bg=1
を満たすものが存在するということである。
\mathfrak m
が極大イデアルではなくともヘンゼルの補題を証明することができる。
それゆえ、以下では
で可逆(R/I における像が R/I の可逆元ということ)な多項式、I もしくは I の冪乗を法とする
でベズーの等式を満たす、という設定のもとで証明を行う。証明では、 A\equiv B \pmod I という式で
A-B\in IR[X]
であることを表すことにする。
R を可換環、I をそのイデアル、h\in R[X]
\alpha
が法 I で可逆(\alphaの R/I における像が R/I の可逆元という意味)であるものとする。
そして何らかの正の整数 k に対して
h\equiv \alpha fg \pmod {I^k}
と因数分解でき、f と
で互いに素だったとする。ここで、"互いに素"というのはある
a,b \in R[X]
af+bg\equiv 1\pmod I
という意味で使っている。このとき、多項式
\delta_f, \delta_g\in I^k R[X]
\deg \delta_f <\deg f
\deg \delta_g <\deg g
h\equiv \alpha(f+\delta_f)(g+\delta_g) \pmod {I^{k+1}
が成り立つものが存在する。しかもこれらの条件が成り立つ
\delta_f
\delta_g
I^{k+1}R[X]
で一意的に定まる。
f+\delta_f
g+\delta_g
f と g が満たすベズーの等式を同様に満たす。つまり
a(f+\delta_f)+b(g+\delta_g)\equiv 1\pmod I
が成り立つ。なぜ直前の主張からすぐにわかるこのことをあえて述べたかというと、k の値を1つ大きくして反復計算を進めるときに、これが次のステップでの前提条件が満たされていることを意味するからである。
次に示す証明は、R/I
I^k/I^{k+1}
\delta_f
\delta_g
を計算することによりなされている。R=\Z
I=p\Z
の場合には、これは法
p での剰余類だけを使って計算できることを意味する。
証明: 仮定から
\alpha
は法 I で可逆である。したがって、ある
\beta\in R
\gamma\in IR[X]
\alpha\beta=1-\gamma
を満たすものが存在する。
\delta_h\in I^kR[X]
を、次数が
\deg h
\delta_h\equiv h-\alpha fg \pmod{I^{k+1}
が成り立つものとする。\delta_h=h-\alpha fg
と置いてもよいが、他のものを選んだ方が計算が簡単になることがある。例えば
R=\Z
I=p\Z
の場合には、係数が区間 [0,p-1]
\delta'_h
\delta_h=p^k\delta'_h
と表せるようなものを取ることができるので、こう取ったほうがよい。
g はモニックなので、多項式に対する除法の原理を
a\delta_h
g に適用し、q と c で
a\delta_h = qg+c
\deg c <\deg g
となるものを見つけることができる。この
q と c は
I^{k} R[X]
に入っている。同様に、q', d\in I^{k} R[X]  で
b\delta_h = q'f+d
\deg d <\deg f
となるものを取る。
q+q'\in I^{k+1}R[X]
である。実際、まず
fc+gd=af\delta_h +bg\delta_h -fg(q+q')\equiv \delta_h-fg(q+q') \pmod{I^{k+1}
が成り立っている。fg
はモニックなので、fg(q+q')
I^{k+1}
\deg fg
q+q'\in I^{k+1}R[X]
のときだけである。
こうして、
I^{k+1}
\begin{align}
\alpha(f+\beta d)&(g+\beta c)-h\\
&\equiv \alpha fg-h+ \alpha \beta (f(a\delta_h-qg)+g(b\delta_h-q'f))\\
&\equiv \delta_h(-1 +\alpha\beta(af+bg)) - \alpha\beta fg(q+q')\\
&\equiv 0 \pmod{I^{k+1}
\end{align}
が成り立つことがわかる。そして、
\delta_f=\beta d, \qquad \delta_g=\beta c
と置けば求めるものになっているので、存在が示せた。
記号 R、I、h、\alpha
は前節と同じとする。h が
h\equiv \alpha fg {\pmod I}
と、\deg f_0+\deg g_0=\deg h
となる互いに素な多項式(前述の意味で)に因数分解できたとする。1次持ち上げを
k=1, 2, \ldots, n-1 \ldots
に適用して、多項式
\delta_f
\delta_g
\deg \delta_f <\deg f
\deg \delta_g <\deg g
h\equiv \alpha (f+\delta_f)(g+\delta_g) {\pmod I^n}
を満たすものの存在がわかる。この多項式
\delta_f
\delta_g
I^n
で一意に定まる。つまり、同じ条件を満たす組
(\delta'_f, \delta'_g)
が他にあったとすると、
\delta'_f\equiv \delta_f \pmod{I^n}\qquad\text{and}\qquad \delta'_g\equiv \delta_g \pmod{I^n}
が成り立つ。
証明: I^n
I^{n-1}
を法とする合同を意味するので、
数学的帰納法を使って証明する。
n = 0 の場合は明らかである。
n − 1 の場合の一意性は証明されているものと仮定する。つまり、
\delta_f- \delta'_f \in I^{n-1} R[X]\qquad\text{and}\qquad \delta_g - \delta'_g  \in I^{n-1} R[X]
と仮定する。仮定により
h\equiv \alpha(f+\delta_f)(g+\delta_g) \equiv \alpha(f+\delta'_f)(g+\delta'_g)\pmod {I^n}
が成り立ち、これから
\begin{align}
\alpha(f+\delta_f)(g+\delta_g) &- \alpha(f+\delta'_f)(g+\delta'_g)\\
&= \alpha(f(\delta_g-\delta'_g) +g(\delta_f-\delta'_f)) +\alpha (\delta_f\delta_g-\delta'_f\delta'_g) \in I^n R[X]
\end{align}
が成り立つ。帰納法の仮定から右辺の2番目の項は
I^n
に含まれ、(左辺もそうなので)同じことが初項についても成り立つ。\alpha
は法 I で可逆なので、ある
\beta\in R
\gamma \in I
\alpha\beta=1+\gamma
が成り立つ。これと帰納法の仮定から
\begin{align}
f(\delta_g-\delta'_g) &+g(\delta_f-\delta'_f)\\
&= \alpha\beta (f(\delta_g-\delta'_g) +g(\delta_f-\delta'_f))-\gamma(f(\delta_g-\delta'_g) +g(\delta_f-\delta'_f)) \in I^n R[X]
\end{align}
が成り立つ。
法 I で互いに素という仮定から、ある
a,b\in R[X]
1\equiv af+bg\pmod I
が成り立つ。帰納法の仮定をもう一度使うと
\begin{align}
\delta_g-\delta'_g &\equiv (af+bg)(\delta_g-\delta'_g)\\
&\equiv g(b(\delta_g-\delta'_g) - a(\delta_f-\delta'_f))\pmod {I^n}
\end{align}
となる。したがって、次数が
\deg g
I^n
でモニック多項式 g ともう1つの多項式 w の積と合同になったことになる。これが起こり得るのは
w\in I^n R[X]
の場合だけなので、これから
\delta_g-\delta'_g \in I^n R[X]
が得られる。同様に
\delta_f-\delta'_f
I^n R[X]
に含まれることが示せるので、これで一意性が証明できた。
I^n
I^{n+1}
での因数分解に持ち上げるものであった。2次持ち上げでは法
I^{2n}
での因数分解に一気に持ち上げる。しかし、ベズーの等式の持ち上げも必要になり、(上述の1次持ち上げでは)法
I での計算だけで済んだが法
I^n
での計算が必要になるため、追加の計算コストがかかる。
N に対して法
I^N
まで持ち上げることができる。例えば
N=2^k
I^N
まで因数分解を持ち上げるためには、1次持ち上げを使うと
N − 1 回の反復計算が必要になるが、
k − 1 回の反復計算で済む。しかし、2次持ち上げを使う方法では扱わなければならない係数のサイズが計算中に増大していく。これは、一番いい持ち上げの方法は、N の値や
R の性質、
使用する乗算アルゴリズム、
ハードウェアの特性などの状況に依存することを意味する。
2次持ち上げは次の性質を利用する。
ある正の整数 k に対して因数分解
h\equiv \alpha fg \pmod {I^k}
があったとし、f と g はモニック多項式で、ある
a,b \in R[X]
af+bg\equiv 1\pmod {I^k}
で互いに素だったとする。このとき、ある多項式
\delta_f, \delta_g\in I^k R[X]
が存在し、\deg \delta_f <\deg f
\deg \delta_g <\deg g
h\equiv \alpha(f+\delta_f)(g+\delta_g) \pmod {I^{2k}
が成り立つ。さらに
f+\delta_f
g+\delta_g
(a+\delta_a)(f+\delta_f)+(b+\delta_b)(g+\delta_g)\equiv 1\pmod {I^{2k}
を満たす(つまり2次持ち上げの反復計算を行うための前提が満たされる)。
証明: 最初の主張は1次持ち上げを
k = 1 で
I の代わりにイデアル I^k に対して適用することでわかる。
\alpha=af+bg-1\in I^k R[X]
と置く。次の式
a(f+\delta_f)+b(g+\delta_g)=1+\Delta
が、
\Delta=\alpha+a\delta_f+b\delta_g\in I^k R[X]
と置くことで成り立つ。2つの多項式を
\delta_a=-a\Delta
\delta_b=-b\Delta
(a+\delta_a)(f+\delta_f)+(b+\delta_b)(g+\delta_g)=1-\Delta^2\in I^{2k} R[X]
が成り立つ。これで2番目の主張も証明できた。
f(X)= X^6 - 2 \in \mathbb{Q}[X]
を考えよう。
この多項式に対して法2でのヘンゼルの補題を適用することはできない。なぜなら
f(X)
を法 2 で還元すると単に
pg 15-16
\bar{f}(X) = X^6 - \overline{2} = X^6
となり、この6つの因子
X
はどの2つを取っても互いに素ではないからだ。しかし、アイゼンシュタインの既約判定法を使って多項式
f(X)
\Q_2[X]
で既約であることは示せる。
一方、k = \mathbb{F}_7 では
\bar{f}(X) = X^6 - \overline{2} = X^6 - \overline{16} = (X^3 - \overline{4})\;(X^3 + \overline{4})
となる。4
\mathbb{F}_7
における2の平方根である。4は
\mathbb F_7
における立方数ではないので、この2つの因子は
\mathbb F_7
上既約である。したがって
X^6-2
\Z_7[X](または\Q_7[X])における既約多項式への因数分解は
f(X) = X^6 - 2 = (X^3-\alpha)\;(X^3 + \alpha),
となる。ここで
\alpha = \ldots 450\,454_7右下の7は7進数の意。
\Z_7
における2の平方根で、先ほどの因数分解を持ち上げることで得られる。
最後に、この多項式は
\mathbb F_{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つを取っても互いに素なので、\Z_{727}[X] (または\Q_{727}[X] )において6つの多項式
X - \beta
の積に分解する。\beta
は(有理数ではない)727進数
\beta = \left\{ \begin{array}{rrr} 3 \; +& \!\!\! 545\cdot 727 \; +& \!\!\! 537 \cdot 727^2 \,+& \!\!\! 161 \cdot 727^3 +\ldots \\116\; +& \!\!\! 48\cdot 727\; +& \!\!\! 130\cdot 727^2 \,+& \!\!\! 498 \cdot 727^3 +\ldots \\119\; +& \!\!\! 593\cdot 727\; +& \!\!\! 667\cdot 727^2 \,+& \!\!\! 659 \cdot 727^3 +\ldots \\608\; +& \!\!\! 133\cdot 727\; +& \!\!\! 59 \cdot 727^2 \,+& \!\!\! 67 \cdot 727^3 +\ldots \\611\; +& \!\!\! 678\cdot 727\; +& \!\!\! 596\cdot 727^2 \,+& \!\!\! 228 \cdot 727^3 +\ldots \\724\; +& \!\!\!181 \cdot 727\; +& \!\!\! 189\cdot 727^2 \,+& \!\!\! 565 \cdot 727^3 +\ldots \end{array} \right.
である。
f(x)
を整数(または p 進整数)を係数とする多項式とし、m と k を
を満たす正の整数とする。整数 r に対して
f(r) \equiv 0 \bmod p^k \quad \text{and} \quad f'(r) \not\equiv 0 \bmod p
が成り立ったとする。このとき、任意の
m>0
に対してある整数 s が存在して
f(s) \equiv 0 \bmod p^{k+m} \quad \text{and} \quad r \equiv s \bmod p^k
が成り立つ。この s は法
で一意であり、次の式
s = r - f(r)\cdot a
で具体的に計算できる整数である。ここで
a
a \equiv [f'(r)]^{-1} \bmod p^m
を満たす整数である。先程の式で s を定めれば、f(r) \equiv 0 \bmod p^k
s \equiv r \bmod p^k
は満たされている。なお、f'(r) \equiv 0 \bmod p
であるときは、持ち上げ s は存在しないかもしれないし複数存在するかもしれない(あとで「#ヘンゼル持ち上げ」で例示する)。
f の r まわりでのテイラー展開
f(s) = \sum_{n=0}^N c_n (s-r)^n, \qquad c_n = f^{(n)}(r)/n!
を使う。r \equiv s \bmod p^k
なのである整数 t が存在して
とかける。これを使うと
\begin{align}
f(s) &= \sum_{n=0}^N c_n \left(tp^k\right)^n \\
&= f(r) + t p^k f'(r) + \sum_{n=2}^N c_n t^n p^{kn} \\
&= f(r) + t p^k f'(r) + p^{2k}t^2g(t) && g(t) \in \Z[t] \\
&= zp^k + t p^k f'(r) + p^{2k}t^2g(t) && f(r) \equiv 0 \bmod p^k \\
&= (z+tf'(r)) p^k + p^{2k}t^2g(t)
\end{align}
と計算できる。m \leqslant k としていたので、
\begin{align}
f(s) \equiv 0 \bmod p^{k+m} &\Longleftrightarrow (z + tf'(r))p^k \equiv 0 \bmod p^{k+m} \\
&\Longleftrightarrow z + tf'(r) \equiv 0 \bmod p^m \\
&\Longleftrightarrow tf'(r) \equiv -z \bmod p^m \\
&\Longleftrightarrow t \equiv -z [f'(r)]^{-1} \bmod p^m && p \nmid f'(r)
\end{align}
である。f'(r) は
p で割り切れないという仮定から、f'(r)
p^m
で逆元を持ち、しかもそれは一意でなければならない。したがって、最後の式の
p^m
で一意に存在し、s は法
p^{k+m}
で一意に存在する。
仮定は今までと同じとし、既約多項式
f(x) = a_0+a_1x + \cdots + a_nx^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{align}
|f(X)| &= \max\〔a_0|,\ldots,|a_n|\} \\
&= \max\{0,1,0 \} = 1
\end{align}
であるが、\max\〔a_0|, |a_n|\} = 0 なので、この多項式は既約ではありえない。一方
\mathbb{Q}_7[X]