Sturmの定理

同義語：シュトゥルムの定理Sturm's theorem

概要

前提知識: 多項式環, Euclidの互除法, 中間値の定理

実数係数の多項式 $P$ が区間 $(a,b)$ に実数解をいくつもつかは、解を求めなくても分かる。$P$ と導関数 $P'$ から割り算だけで多項式の列を作り、その列を $a$ と $b$ で評価して符号の並びを比べればよい。これが Sturm の定理（Sturm's theorem）である（BPR16 Theorem 2.62, p. 62）。2 次方程式なら判別式の符号で実数解の個数が分かるが（2次不等式）、Sturm の定理はこれを任意の次数へ広げ、しかも区間を指定して数えられる。
数えるのは 相異なる 実数解の個数で、重解も 1 個と数える。証明に使うのは多項式の割り算と、多項式についての中間値の定理だけなので、定理は実数体 $\mathbb{R}$ だけでなく任意の実閉体で成り立つ。区間を半分ずつに分けながら数えれば、すべての実数解を 1 つずつ区間に閉じ込め（根の分離）、好きな精度で近似できる。

定義

以下、$R$ は実閉体とする。$R=\mathbb{R}$ と思って読んでよい。$R$ は順序体なので $1+1+\dots+1>0$ であり、標数は $0$ である。

符号の変化の数

$R$ の元の有限列 $c_0,c_1,\dots,c_k$ から $0$ に等しい項を取り除いた列を $c'_0,c'_1,\dots,c'_l$ とする。隣り合う 2 項で $c'_{j-1}c'_j<0$ となる $j$ の個数を、もとの列の 符号の変化の数 といい、$\operatorname{Var}(c_0,\dots,c_k)$ と書く。

たとえば $\operatorname{Var}(1,-3,-1,2)=2$、$\operatorname{Var}(-1,0,1,2)=1$ である。$0$ でない同じ数 $d$ を全項に掛けても、符号の変化の数は変わらない。

Sturm 列

$P\in R[x]$ を $0$ でない多項式とする。$S_0:=P$、$S_1:=P'$ とし、$S_i\ne0$ である限り
$$ S_{i+1}:=-\bigl(S_{i-1}\text{ を }S_i\text{ で割った余り}\bigr) $$
と定める。次数は真に減るので、ある $k\ge0$ で $S_k\ne0$、$S_{k+1}=0$ となる。列 $S_0,S_1,\dots,S_k$ を $P$ の Sturm 列 という。$x\in R$ について
$$ V(x):=\operatorname{Var}\bigl(S_0(x),S_1(x),\dots,S_k(x)\bigr) $$
とおく。

Euclidの互除法との違いは、余りに $-1$ を掛けて次の項にする点である。この符号の付け方がないと定理は成り立たない（下の「条件を外した反例」の表の 2 行目）。
$0$ でない多項式 $F$ の最高次の係数を $c$、次数を $d$ とするとき、$F$ の $+\infty$ での符号を $c$ の符号、$-\infty$ での符号を $(-1)^dc$ の符号と定める。$V(+\infty)$、$V(-\infty)$ は、Sturm 列の各項の $\pm\infty$ での符号の列の符号の変化の数とする。

主定理

Sturm の定理

$R$ を実閉体、$P\in R[x]$ を $0$ でない多項式とし、$a< b$ を $P(a)\ne0$、$P(b)\ne0$ をみたす $R$ の元とする。このとき、$P$ の開区間 $(a,b)$ にある相異なる根の個数は $V(a)-V(b)$ に等しい。

証明の考え方

$x$ を $a$ から $b$ へ動かすと、$V(x)$ が変わりうるのは Sturm 列のどれかの項が $0$ になる点だけである。途中の項が $0$ になる点では、その両隣の項が逆の符号をもつので、変化の数は変わらない。$P$ の根を通るときだけ、$P$ と $P'$ の符号が「異なる」から「同じ」へ変わり、変化が 1 つ減る。証明は prf-sturm で与える。

根の総数と半直線

同じ記号で、$P$ の $R$ における相異なる根の個数は $V(-\infty)-V(+\infty)$ に等しい。$a\in R$ が $P$ の根でなければ、$(a,+\infty)$ にある根の個数は $V(a)-V(+\infty)$、$(-\infty,a)$ にある根の個数は $V(-\infty)-V(a)$ である。

$V(\pm\infty)$ は各項の最高次の係数と次数だけで決まるので、根の総数は Sturm 列を作るだけで、どの点でも評価せずに分かる。

例

3 つの実数解をもつ 3 次式

$P=x^3-3x+1$ とする。$S_1=P'=3x^2-3$ で、$P=\tfrac x3S_1+(-2x+1)$ なので $S_2=2x-1$ である。$S_1$ を $S_2$ で割ると $S_1=\bigl(\tfrac32x+\tfrac34\bigr)S_2-\tfrac94$ なので $S_3=\tfrac94$ であり、$S_4=0$ である。符号は次のとおり。

$x$	$S_0$	$S_1$	$S_2$	$S_3$	$V(x)$
$-\infty$	$-$	$+$	$-$	$+$	$3$
$0$	$+$	$-$	$-$	$+$	$2$
$1$	$-$	$0$	$+$	$+$	$1$
$2$	$+$	$+$	$+$	$+$	$0$
$+\infty$	$+$	$+$	$+$	$+$	$0$

よって実数解は全部で $3-0=3$ 個あり、$(-\infty,0)$、$(0,1)$、$(1,2)$ に 1 個ずつある。$x=1$ では $S_1(1)=0$ だが、$1$ は $P$ の根でないので定理はそのまま使え、$0$ の項を除いて数える。

2 次式と判別式

$P=x^2+px+q$、$D:=p^2-4q$ とする。$P=\bigl(\tfrac x2+\tfrac p4\bigr)(2x+p)+q-\tfrac{p^2}4$ なので、$D\ne0$ なら Sturm 列は $P,\ 2x+p,\ D/4$ である。$\pm\infty$ での符号は $(+,-,\operatorname{sgn}D)$ と $(+,+,\operatorname{sgn}D)$ なので、$D>0$ なら $V(-\infty)-V(+\infty)=2-0=2$、$D<0$ なら $1-1=0$ である。$D=0$ なら余りが $0$ なので列は $P,\ 2x+p$ で終わり、根の個数は $1-0=1$（重解を 1 個と数える）である。判別式による実数解の個数の判定が、Sturm の定理の特別な場合として得られる。

重根をもつ多項式

$P=(x-1)^2(x+1)=x^3-x^2-x+1$ とする。$S_1=3x^2-2x-1=(3x+1)(x-1)$、$S_2=\tfrac89(x-1)$ で、$S_1$ は $S_2$ で割り切れるので列はここで終わる。$S_2$ は $P$ と $P'$ の最大公約元の定数倍である。$\pm\infty$ での符号は $(-,+,-)$ と $(+,+,+)$ なので根の個数は $2-0=2$ で、相異なる根 $1,-1$ の個数に一致する。重複度を込めた個数 $3$ ではない。

証明

Sturm 列 $S_0,\dots,S_k$ の最後の項を $D:=S_k$ とおく。

Sturm 列の性質

$D$ は $P$ と $P'$ の最大公約元である（$0$ でない定数倍を除く）。とくに各 $S_i$ は $D$ で割り切れ、$T_i:=S_i/D$ とおくと $T_k=1$ である。
$1\le i\le k-1$ について、$S_{i-1}$ を $S_i$ で割った商を $Q_i$ とすると $T_{i-1}=Q_iT_i-T_{i+1}$ である。
$0\le i\le k-1$ について、$T_i$ と $T_{i+1}$ は $R$ に共通の根をもたない。
$P$ の根全体と $T_0$ の根全体は一致する。

互除法の不変量と重複度

1, 2：定義から $S_{i-1}=Q_iS_i-S_{i+1}$（$1\le i\le k$、$S_{k+1}=0$）である。この式から、$S_{i-1}$ と $S_i$ の公約元全体と、$S_i$ と $S_{i+1}$ の公約元全体は一致する。$i=1,\dots,k$ とたどると、$P,P'$ の公約元全体は $S_k,0$ の公約元全体、すなわち $D$ の約元全体である。よって $D$ は $P,P'$ の最大公約元で、同じ議論で各 $S_{i-1},S_i$ の最大公約元でもある。とくに $D$ は全部の $S_i$ を割り切る。式を $D$ で割れば 2 を得る。
3：$R[x]$ は単項イデアル整域なので、$US_i+WS_{i+1}=D$ となる $U,W\in R[x]$ がある（単項イデアル整域）。$D$ で割ると $UT_i+WT_{i+1}=1$ であり、共通の根 $c$ があれば $0=1$ となって矛盾する。
4：$P=DT_0$ なので $T_0$ の根は $P$ の根である。逆に $c$ を $P$ の重複度 $m\ge1$ の根とし、$P=(x-c)^mg$、$g(c)\ne0$ と書く。
$$ P'=(x-c)^{m-1}\bigl(mg+(x-c)g'\bigr) $$
であり、標数が $0$ なので括弧内の $c$ での値 $mg(c)$ は $0$ でない。よって $(x-c)^m$ は $P'$ を割り切らず、その約元 $D$ も割り切らない。$P=DT_0$ の $(x-c)$ の重複度を比べると、$T_0$ は $x-c$ で割り切れる。$\square$

符号が一定である範囲

$F\in R[x]$ を $0$ でない多項式とする。

区間 $I\subset R$ が $F$ の根を含まなければ、$F$ は $I$ の上で一定の符号をとる。
$F$ の最高次の係数を $c$、次数を $d$ とし、$F=cx^d+c_{d-1}x^{d-1}+\dots+c_0$、$B:=1+\sum_{i< d}\lvert c_i/c\rvert$ とおく。$x\ge B$ なら $F(x)$ は $c$ と同符号、$x\le-B$ なら $(-1)^dc$ と同符号である。とくに $F$ の根はすべて $(-B,B)$ にある。

多項式の中間値の定理と係数の評価

1：$x< y$ を $I$ の 2 点として $F(x)F(y)<0$ なら、実閉体の命題「多項式の中間値の定理」により $x$ と $y$ の間に根があり、それは $I$ に属するので仮定に反する。
2：$\lvert x\rvert\ge B$ とする。$\lvert x\rvert\ge1$ なので $i< d$ について $\lvert x\rvert^{i-d}\le\lvert x\rvert^{-1}$ であり、
$$ \Bigl\lvert\sum_{i< d}\frac{c_i}{c}x^{i-d}\Bigr\rvert\le\frac1{\lvert x\rvert}\sum_{i< d}\Bigl\lvert\frac{c_i}{c}\Bigr\rvert<1 $$
である（$\lvert x\rvert>\sum_{i< d}\lvert c_i/c\rvert$）。よって $F(x)=cx^d\bigl(1+\sum_{i< d}(c_i/c)x^{i-d}\bigr)$ の括弧は正で、$F(x)$ は $cx^d$ と同符号である。$x^d$ は $x>0$ なら正、$x< 0$ なら $(-1)^d$ と同符号である。$\square$

根の近くでの $PP'$ の符号

$c$ を $P$ の根とする。ある $\varepsilon>0$ があって、$c-\varepsilon< x< c$ では $P(x)P'(x)<0$、$c< x< c+\varepsilon$ では $P(x)P'(x)>0$ である。

prf-sturm-sequence の 4 の記号で $PP'=(x-c)^{2m-1}h$、$h:=g\bigl(mg+(x-c)g'\bigr)$ であり、$h(c)=mg(c)^2>0$ である。$h$ の根は有限個なので、$(c-\varepsilon,c+\varepsilon)$ が $h$ の根を含まない $\varepsilon>0$ がとれ、lem-sturm-sign の 1 によりこの区間で $h>0$ である。$2m-1$ は奇数なので $(x-c)^{2m-1}$ は $x-c$ と同符号である。$\square$

根を通るたびに変化が 1 つ減る

段 1（$D$ で割る）：各 $x\in R$ について $W(x):=\operatorname{Var}\bigl(T_0(x),\dots,T_k(x)\bigr)$ とおく。$P(x)\ne0$ なら $D(x)\ne0$ であり（$D$ は $P$ を割り切る）、$S_i(x)=D(x)T_i(x)$ なので $V(x)=W(x)$ である。
段 2（1 点の近くでの $W$）：$c\in R$ を固定し、$Z:=\{i\mid1\le i\le k-1,\ T_i(c)=0\}$ とおく。lem-sturm-sequence の 3 により $Z$ は隣り合う番号を含まず、$i\in Z$ なら $T_{i-1}(c)\ne0$、$T_{i+1}(c)\ne0$ であり、2 により $T_{i-1}(c)=-T_{i+1}(c)$ である。$T_0,\dots,T_k$ の根は有限個なので、$c$ 以外にどの $T_j$ の根も含まない区間 $J=(c-\varepsilon,c+\varepsilon)$ がとれる。$c$ で $0$ でない $T_j$ は $J$ に根をもたず、lem-sturm-sign の 1 により $J$ で一定の符号をとる。
符号の変化の数について次が成り立つ：$u,w$ が $uw<0$ をみたせば、$y$ の値（$0$ を含む）によらず $\operatorname{Var}(u,y,w)=1=\operatorname{Var}(u,w)$ である。$i\in Z$ の両隣の $T_{i-1},T_{i+1}$ は $J$ 全体で逆の符号をとり、しかも $Z$ に属さない。よって $J$ の各点 $x$ で、$W(x)$ は $Z$ の番号の項を取り除いた列 $(T_j(x))_{j\notin Z}$ の符号の変化の数に等しい。この列の $j\ge1$ の項は $J$ で一定の符号をとる。

$P(c)\ne0$ のとき：lem-sturm-sequence の 4 により $T_0(c)\ne0$ なので、$T_0$ も $J$ で一定の符号をとり、$W$ は $J$ で一定である。
$P(c)=0$ のとき：$T_0(c)=0$、$T_1(c)\ne0$ である。$D$ の根は $P$ の根であり、lem-sturm-sequence の 4 により $T_0$ の根でもあるので、$J$ の $c$ 以外の点で $D(x)\ne0$ である。よって $x\ne c$ では $T_0(x)T_1(x)=P(x)P'(x)/D(x)^2$ なので、$\varepsilon$ を小さくとり直せば、lem-sturm-near-root により $c$ の左で $T_0T_1<0$、右で $T_0T_1>0$ である。ほかの隣り合う項の符号は $J$ で変わらないので、$c$ の左の点 $x$ と右の点 $x'$ について $W(x)=W(x')+1$ であり、$W$ は $c$ の左右それぞれで一定である。

段 3（区間をたどる）：$(a,b)$ に含まれる $T_0,\dots,T_{k-1}$ の根を $e_1< \dots< e_r$ とし、$e_0:=a$、$e_{r+1}:=b$ とおく。各開区間 $(e_{j},e_{j+1})$ では全部の $T_i$ が $0$ でないので、lem-sturm-sign の 1 により $W$ は一定である。その値を $w_j$ とする。段 2 を $c=a$、$c=b$（$P(a),P(b)\ne0$）に当てると $W(a)=w_0$、$W(b)=w_r$ であり、$c=e_j$（$1\le j\le r$）に当てると、$w_{j-1}-w_j$ は $P(e_j)=0$ なら $1$、そうでなければ $0$ である。$P$ の $(a,b)$ の根は $T_0$ の根なので $e_j$ のどれかである。足し合わせると
$$ V(a)-V(b)=W(a)-W(b)=\sum_{j=1}^{r}(w_{j-1}-w_j)=\#\{x\in(a,b)\mid P(x)=0\} $$
である。$\square$

根の総数と半直線の場合

各 $S_i$ に lem-sturm-sign の 2 の $B$ をとり、その最大値以上の元を $M$ とする。$S_i$ の根はすべて $(-M,M)$ にあり、$S_i(M)$、$S_i(-M)$ の符号はそれぞれ $+\infty$、$-\infty$ での符号に等しいので、$V(M)=V(+\infty)$、$V(-M)=V(-\infty)$ である。$P$ の根はすべて $(-M,M)$ にあるので、thm-sturm を $(-M,M)$ に当てれば前半を得る。$a$ が根でないとき、$M>\lvert a\rvert$ ととって $(a,M)$、$(-M,a)$ に当てれば後半を得る。$\square$

条件を外した反例

外す条件	反例	成り立たなくなること
区間の端が根でない	$P=x$、$a=-1$、$b=0$	$V(-1)-V(0)=1$ だが $(-1,0)$ に根はない
余りに $-1$ を掛ける	$P=x^2-1$ で余りをそのまま並べた列 $x^2-1,\ 2x,\ -1$	両端の差が $1-1=0$ で、根 $\pm1$ の個数 $2$ と合わない
2 項目が導関数 $P'$	$P=x^2-1$ で 2 項目を $1$ にした列 $x^2-1,\ 1$	両端の差が $0-0=0$ で、根の個数 $2$ と合わない
係数の体が実閉体	$R=\mathbb{Q}$、$P=x^2-2$	Sturm 列 $x^2-2,\ 2x,\ 2$ から $V(-\infty)-V(+\infty)=2$ だが、$\mathbb{Q}$ に根はない

表の各行の確かめ

各行の対象は、左の列の条件以外の仮定をみたしている。

確かめを開く

1 行目：Sturm 列は $x,\ 1$ である。$V(-1)=\operatorname{Var}(-1,1)=1$、$V(0)=\operatorname{Var}(0,1)=0$ である。$b=0$ が根なので仮定を破る。

2 行目：$x^2-1=\tfrac x2\cdot2x-1$ なので、互除法の余りは $-1$ である。$\pm\infty$ での符号は $(+,-,-)$ と $(+,+,-)$ で、どちらも変化は $1$ 回である。余りに $-1$ を掛けた正しい Sturm 列 $x^2-1,\ 2x,\ 1$ なら $(+,-,+)$ と $(+,+,+)$ で、$2-0=2$ になる。

3 行目：$x^2-1$ を $1$ で割った余りは $0$ なので列は $x^2-1,\ 1$ で終わり、$\pm\infty$ での符号はどちらも $(+,+)$ である。

4 行目：$x^2-2=\tfrac x2\cdot2x-2$ なので $S_2=2$ である。$\pm\infty$ での符号は $(+,-,+)$ と $(+,+,+)$ である。$\mathbb{Q}$ では多項式の中間値の定理が成り立たず（$x^2-2$ は $1$ で負、$2$ で正だが $\mathbb{Q}$ に根がない）、数えられた $2$ は $\mathbb{Q}$ の実閉包の中の根 $\pm\sqrt2$ の個数である。

使い方と広がり

根の分離と近似

lem-sturm-sign の 2 により、$P$ の実数解はすべて $(-B,B)$ にある。Sturm 列を一度作れば、区間の端点での符号を調べるだけで、どの区間にいくつ解があるかが分かる。解を含む区間を中点で 2 つに分け、それぞれの個数を数えることをくり返すと、有限回で各区間に解がちょうど 1 個ずつ入るように分けられる（中点が解に当たったら、その点を解として記録し、両側の区間を少し縮めて続ければよい）。こうして区間に閉じ込めた解は、さらに中点で分ける二分法で好きな精度まで近似できる。高校数学の解の配置で扱う「区間の中に解がいくつあるか」という問いは、この方法で次数によらずに機械的に答えられる。

実閉体での意味

thm-sturm の証明は、$R$ の順序と多項式の中間値の定理しか使っていない。したがって、多項式が実閉体 $R$ に根をもつかどうか、いくつもつかは、係数の加減乗除と符号の判定だけで決まる。たとえば $P\in R[x]$ の係数がすべて部分体 $R_0$（$R$ の順序を制限した順序体とみる）に属するなら、$P$ の $R$ における相異なる根の個数は、$R_0$ の中だけで計算した $V(-\infty)-V(+\infty)$ に等しく、$R_0$ の順序を延ばす実閉体 $R$ のとり方によらない。この「根の個数が順序だけで決まる」という性質は、実閉包の一意性の証明に使われる（実閉体の注意「実閉包とArtin–Schreierの定理の出典」）。多変数への広がりが Tarski–Seidenbergの定理である。

一般化：Tarski の定理

Sturm 列の 2 項目を $P'$ から $P'Q$（$Q\in R[x]$）に替えて同じ規則で列を作ると、$a,b$ が $P$ の根でないとき、$V(a)-V(b)$ は
$$ \#\{x\in(a,b)\mid P(x)=0,\ Q(x)>0\}-\#\{x\in(a,b)\mid P(x)=0,\ Q(x)< 0\} $$
に等しい（BPR16 Theorem 2.73, p. 67。証明は Cauchy 指数を経由する Theorem 2.70, p. 65 による）。$Q=1$ が thm-sturm である。この一般化はこの記事では証明しない。これを使うと、$P$ の根のうち別の多項式 $Q$ が正になるものの個数も数えられ、実閉体の量化子消去の 1 変数の場合の基礎になる。

Descartes の符号法則との比較

係数列 $c_0,\dots,c_d$ の符号の変化の数は、$P=\sum c_ix^i$ の正の根の個数（重複度を込める）以上で、差は偶数である（Descartes の符号法則。BPR16 Theorem 2.44, p. 54。この記事では証明しない）。こちらは割り算がいらない代わりに上界しか与えない。Sturm の定理は列を作る手間がかかるが、相異なる根の個数を正確に与える。