パラメータ付き多項式と量化子消去 | 数値解析 I

定義 1.1. $r\in\N$ とし、 $q_1,\ldots,q_r\in\Q[t][x]$ とする。 $q=\sum_iu_ix^i\in\Q[t][x]$ （ $u_i\in\Q[t]$ ）と $a,b\in\R$ に対して $q(a,b):=\sum_iu_i(a)b^i$ と置く。

族 $(q_1,\ldots,q_r)$ 上の符号条件式 (sign condition formula) を次の規則で帰納的に定める。 $\top$ と、 $1\le j\le r$ に対する $q_j<0$ 、 $q_j=0$ 、 $q_j>0$ は符号条件式である。 $\Phi$ と $\Phi'$ が符号条件式ならば、 $\neg\Phi$ 、 $(\Phi\wedge\Phi')$ 、 $(\Phi\vee\Phi')$ は符号条件式である。
符号条件式 $\Phi$ に対して、 $\{-1,0,1\}^r$ の部分集合 $[\Phi]$ を、 $[\top]:=\{-1,0,1\}^r$ 、 $[q_j<0]:=\{\sigma\mid\sigma_j=-1\}$ 、 $[q_j=0]:=\{\sigma\mid\sigma_j=0\}$ 、 $[q_j>0]:=\{\sigma\mid\sigma_j=1\}$ 、 $[\neg\Phi]:=\{-1,0,1\}^r\setminus[\Phi]$ 、 $[(\Phi\wedge\Phi')]:=[\Phi]\cap[\Phi']$ 、 $[(\Phi\vee\Phi')]:=[\Phi]\cup[\Phi']$ によって帰納的に定める。
$a,b\in\R$ に対して $\sigma(a,b):=\bigl(\operatorname{sgn}q_1(a,b),\ldots,\operatorname{sgn}q_r(a,b)\bigr)$ と置き、 $\sigma(a,b)\in[\Phi]$ であるとき $\Phi(a,b)$ が成り立つという。 $a\in\R$ に対して $S(a):=\{\sigma(a,b)\mid b\in\R\}$ と置く。
$\bot:=\neg\top$ と置き、 $q_j\le0$ 、 $q_j\ge0$ 、 $q_j\ne0$ をそれぞれ $(q_j<0\vee q_j=0)$ 、 $(q_j>0\vee q_j=0)$ 、 $\neg\,q_j=0$ の略記とする。連言と選言の括弧は省略して書き、有限個の符号条件式の選言を $\bigvee$ で書いて、空の選言を $\bot$ とする。すべての $q_j$ が $\Q[t]$ に属するならば $\sigma(a,b)$ は $b$ によらないので、 $\Phi(a,b)$ を $\Phi(a)$ と書く。

定義 2.1. $\Q[t]$ の分数体を $\Q(t)$ と書き、§E6.6 命題 3.2の単射 $u\mapsto u/1$ によって $\Q[t]\subset\Q(t)$ 、 $\Q[t][x]\subset\Q(t)[x]$ とみなす。 $\varphi\in\Q(t)$ と $u,v\in\Q[t]$ 、 $v\ne0$ が $\varphi=u/v$ を満たすとき、組 $(u,v)$ を $\varphi$ の分数表示 (fraction representation) といい、 $v$ をその分母という。 $a\in\R$ に対して、 $v(a)\ne0$ を満たす分数表示 $(u,v)$ をもつ $\varphi\in\Q(t)$ の全体を $\mathcal O_a$ と書く。

補題 2.2. $a\in\R$ とする。

任意の正の整数 $k$ に対して、 $\Q(t)$ において $k\cdot1\ne0$ である。 $\mathcal O_a$ は $\Q[t]$ を含む $\Q(t)$ の部分環である。 $\varphi\in\mathcal O_a$ に対して、 $v(a)\ne0$ を満たす分数表示 $(u,v)$ を取り $\ev_a(\varphi):=u(a)/v(a)$ と置くと、 $\ev_a(\varphi)$ は分数表示の取り方によらず、 $\ev_a\colon\mathcal O_a\to\R$ は単位元を保つ環準同型であって、 $u\in\Q[t]$ に対して $\ev_a(u)=u(a)$ である。
$f=\sum_i\varphi_ix^i\in\mathcal O_a[x]$ に対して $f_a:=\sum_i\ev_a(\varphi_i)x^i\in\R[x]$ と置く。 $f\mapsto f_a$ は $\mathcal O_a[x]$ から $\R[x]$ への単位元を保つ環準同型である。§E20.40 定義 4.6の導関数について $f'\in\mathcal O_a[x]$ かつ $(f')_a=(f_a)'$ である。 $f\in\Q[t][x]$ ならば、任意の $b\in\R$ に対して $f_a(b)=f(a,b)$ である。
$I\subset\R$ を開区間とし、 $\varphi\in\Q(t)$ が分母が $I$ 上で零にならない分数表示 $(u,v)$ をもつとする。このとき任意の $a\in I$ について $\varphi\in\mathcal O_a$ であり、 $I\to\R$ 、 $a\mapsto\ev_a(\varphi)$ は $C^1$ 級である。
$\Q(t)$ の元を分数表示で与える。このとき、 $\Q(t)$ の和・差・積と零でない元の逆元の分数表示、 $\Q(t)$ の元が零であるかどうかの判定、 $\Q(t)[x]$ における除法の商と剰余、零でない二元のモニック最大公約元と正規化後の Bézout 等式の係数、導関数、および成分が $\Q(t)$ の元である正方行列の行列式の分数表示は、有理数の四則演算と比較の有限回で得られる。

証明.(1)を示す。 $k\cdot1=k/1$ であり、 $\Q[t]$ において $k\ne0$ であるから、§E6.6 命題 3.2の単射性により $k/1\ne0$ である。 $u\in\Q[t]$ は分数表示 $(u,1)$ をもつので、 $\Q[t]\subset\mathcal O_a$ である。 $\varphi,\psi\in\mathcal O_a$ が $v(a)\ne0$ 、 $v'(a)\ne0$ を満たす分数表示 $(u,v)$ 、 $(u',v')$ をもつとする。§E6.6 定義 3.1により

-\varphi=\frac{-u}{v},\qquad\varphi+\psi=\frac{uv'+u'v}{vv'},\qquad\varphi\psi=\frac{uu'}{vv'}

であり、 $(vv')(a)=v(a)v'(a)\ne0$ であるから、 $-\varphi$ 、 $\varphi+\psi$ 、 $\varphi\psi$ は $\mathcal O_a$ に属する。したがって $\mathcal O_a$ は部分環である。 $(u,v)$ と $(u',v')$ が同じ $\varphi$ の分数表示であって $v(a)v'(a)\ne0$ を満たすならば、§E6.6 定義 3.1により $uv'=u'v$ であり、 $a$ を代入すると $u(a)v'(a)=u'(a)v(a)$ であるから、 $u(a)/v(a)=u'(a)/v'(a)$ である。上の三つの分数表示に $a$ を代入すると、 $\ev_a$ が負元、和、積を保つことを得る。分数表示 $(u,1)$ から $\ev_a(u)=u(a)$ であり、特に $\ev_a(1)=1$ である。

(2)を示す。 $\mathcal O_a[x]$ の二元の和と積の各係数は、二元の係数の和と積の有限和であり、 $\ev_a$ は和と積を保つので、 $f\mapsto f_a$ は和と積を保ち、 $1_a=1$ である。 $f'$ の $x^{i-1}$ の係数 $i\varphi_i$ は $\mathcal O_a$ に属し、 $\ev_a(i\varphi_i)=i\,\ev_a(\varphi_i)$ であるから、 $(f')_a=(f_a)'$ である。 $f=\sum_iu_ix^i\in\Q[t][x]$ ならば $f_a=\sum_iu_i(a)x^i$ であり、 $f_a(b)=f(a,b)$ である。

(3)を示す。 $a\in I$ ならば $v(a)\ne0$ であるから、 $\varphi\in\mathcal O_a$ かつ $\ev_a(\varphi)=u(a)/v(a)$ である。多項式関数 $u,v$ は $C^1$ 級であり、 $v$ は $I$ 上で零にならないので、商 $u/v$ は $I$ 上で $C^1$ 級である。

(4)を示す。 $\Q[t]$ の元の和・差・積は係数の有理数の四則演算の有限回で得られ、 $\Q[t]$ の元が零であるかどうかは係数を $0$ と比較して判定される。前段の式により、 $\Q(t)$ の負元、和、積の分数表示は $\Q[t]$ の演算で得られる。§E6.6 定義 3.1により $u/v=0/1$ であることは $u=0$ と同値であり、 $u\ne0$ ならば、§E6.6 命題 3.2により $(v,u)$ は $u/v$ の逆元の分数表示である。したがって $\Q(t)[x]$ の零でない元の次数と最高次係数は、係数を上から零と比較して得られる。§E6.28 定理 2.1の存在の証明による商と剰余の計算は、被除式が零ならば最高次項の消去を行わずに停止する。被除式が零でなく、その次数を $n$ 、零でない除式の次数を $m$ とすると、この計算は最高次項の消去を高々 $\max\{0,n-m+1\}$ 回行う。 $n<m$ ならば消去は一度も行われない。 $n\ge m$ ならば、消去は次数が $m$ 以上 $n$ 以下の零でない多項式に対してだけ行われ、各回の消去で得られる多項式は零であるか、消去前の多項式より次数が真に小さいので、消去の回数は $n-m+1$ 以下である。各回の消去は $\Q(t)$ の四則演算と零の判定からなる。§E6.28 命題 3.1の Euclid アルゴリズムは剰余の次数が真に減る有限回の除法であり、Bézout 等式の係数は各除法の商から得られ、正規化は最高次係数の逆元を掛ける操作である。導関数の係数は係数の整数倍である。§E20.40 定義 4.1の行列式は、有限個の置換にわたる成分の積の和である。▨

補題 3.1. $F$ を、任意の正の整数 $k$ に対して $k\cdot1\ne0$ を満たす体とし、 $F[x]$ の元の導関数を§E20.40 定義 4.6で定める。 $f,g\in F[x]$ 、 $\alpha,\beta\in F$ とする。

$(\alpha f+\beta g)'=\alpha f'+\beta g'$ である。
$(fg)'=f'g+fg'$ であり、正の整数 $e$ に対して $(f^e)'=ef^{e-1}f'$ である。

証明.(1)は、各 $i$ における係数の等式 $i(\alpha a_i+\beta b_i)=\alpha\,ia_i+\beta\,ib_i$ から従う。(1)により $(fg)'$ と $f'g+fg'$ はいずれも $f$ と $g$ のそれぞれについて $F$ -線形であるから、二つが等しいことは $f=x^i$ 、 $g=x^j$ （ $i,j\in\N$ ）の場合に帰着する。 $x^0$ の導関数は $0$ であり、 $k\ge1$ について $x^k$ の導関数は $kx^{k-1}$ である。したがって、 $i+j\ge1$ ならば両辺はともに $(i+j)x^{i+j-1}$ に等しく、 $i=j=0$ ならば両辺はともに $0$ である。 $(f^e)'=ef^{e-1}f'$ は $e=1$ で成り立ち、 $e$ で成り立つならば $(f^{e+1})'=(f^e)'f+f^ef'=(e+1)f^ef'$ である。▨

補題 3.2. $F$ を、任意の正の整数 $k$ に対して $k\cdot1\ne0$ を満たす体とし、 $F[x]$ のモニック既約多項式の全体を $\mathcal P$ 、 $\pi\in\mathcal P$ に対する指数を§E20.39 補題 3.3の $v_\pi$ とする。 $f\in F[x]$ の次数を $n\ge1$ とし、 $f$ と $f'$ のモニック最大公約元を $D$ とする。

$D=\prod_{\pi\in\mathcal P}\pi^{\max\{v_\pi(f)-1,\,0\}}$ である。 $f$ の $D$ による除法の剰余は零であり、その商を $f/D$ として $h:=\operatorname{lc}(f/D)^{-1}(f/D)$ と置くと、 $h=\prod_{\pi\in\mathcal P,\ v_\pi(f)\ge1}\pi$ である。特に $h$ はモニックで次数が $1$ 以上であり、 $h\mid f$ である。
$f\mid h^n$ である。
$h$ と $h'$ のモニック最大公約元は $1$ である。

証明.

主張 3.2.1. $\pi\in\mathcal P$ と零でない $g\in F[x]$ が $e:=v_\pi(g)\ge1$ を満たすならば、 $g'\ne0$ かつ $v_\pi(g')=e-1$ である。

証明.§E20.39 補題 3.3 (3)により $\pi^e\mid g$ であるから $g=\pi^ek$ と書くことができ、§E20.39 補題 3.3 (2)により $v_\pi(k)=0$ である。補題 3.1 (2)により

g'=e\pi^{e-1}\pi'k+\pi^ek'=\pi^{e-1}\bigl(e\pi'k+\pi k'\bigr)

である。 $\pi$ は既約であるから次数が $1$ 以上であり、§E20.40 定義 4.6により $\pi'\ne0$ かつ $\deg\pi'=\deg\pi-1$ である。 $\pi\mid\pi'$ ならば§E6.28 命題 1.2により $\deg\pi\le\deg\pi'$ となるので、 $\pi\nmid\pi'$ であり、§E20.39 補題 3.3 (3)により $v_\pi(\pi')=0$ である。 $e\cdot1$ は $F$ の零でない定数であるから、§E20.39 補題 3.3 (2)により $v_\pi(e\pi'k)=0$ である。 $\pi\mid e\pi'k+\pi k'$ ならば $\pi\mid e\pi'k$ となり、§E20.39 補題 3.3 (3)により $v_\pi(e\pi'k)\ge1$ となるので、 $v_\pi(e\pi'k)=0$ と両立しない。したがって $\pi\nmid e\pi'k+\pi k'$ であり、零は $\pi$ で割り切れるから $e\pi'k+\pi k'\ne0$ かつ $v_\pi(e\pi'k+\pi k')=0$ である。§E20.39 補題 3.3 (2)により $g'\ne0$ かつ $v_\pi(g')=e-1$ である。▨

(1)を示す。 $e_\pi:=v_\pi(f)$ と置く。§E20.40 定義 4.6により $f'\ne0$ である。主張 3.2.1により、 $e_\pi\ge1$ ならば $\min\{e_\pi,v_\pi(f')\}=e_\pi-1$ であり、 $e_\pi=0$ ならばこの最小値は $0$ であるから、§E20.39 補題 3.3 (4)により $D=\prod_\pi\pi^{\max\{e_\pi-1,0\}}$ である。§E20.39 補題 3.3 (1)により

f=\operatorname{lc}(f)\prod_\pi\pi^{e_\pi}=D\cdot\operatorname{lc}(f)\prod_{e_\pi\ge1}\pi

であるから、§E6.28 定理 2.1の一意性により剰余は零であり、 $f/D=\operatorname{lc}(f)\prod_{e_\pi\ge1}\pi$ である。モニック多項式の積はモニックであるから、§E6.28 命題 1.2により $\operatorname{lc}(f/D)=\operatorname{lc}(f)$ であり、 $h=\prod_{e_\pi\ge1}\pi$ である。 $f$ は定数でないので、§E20.39 補題 3.3 (1)により $e_\pi\ge1$ を満たす $\pi$ が存在し、 $h$ の次数は $1$ 以上である。 $v_\pi(h)$ は $e_\pi\ge1$ ならば $1$ 、そうでなければ $0$ であるから、§E20.39 補題 3.3 (3)により $h\mid f$ である。

(2)を示す。§E6.28 命題 1.2により $n=\sum_\pi e_\pi\deg\pi$ であるから、任意の $\pi$ で $e_\pi\le n$ である。§E20.39 補題 3.3 (2)により $v_\pi(h^n)=n\,v_\pi(h)$ であり、 $e_\pi\ge1$ ならば $v_\pi(f)=e_\pi\le n=v_\pi(h^n)$ 、 $e_\pi=0$ ならば $v_\pi(f)=0\le v_\pi(h^n)$ である。§E20.39 補題 3.3 (3)により $f\mid h^n$ である。

(3)を示す。 $h$ の次数は $1$ 以上であるから、§E20.40 定義 4.6により $h'\ne0$ である。 $v_\pi(h)=1$ ならば主張 3.2.1により $v_\pi(h')=0$ であるから、任意の $\pi$ で $\min\{v_\pi(h),v_\pi(h')\}=0$ である。§E20.39 補題 3.3 (4)により、 $h$ と $h'$ のモニック最大公約元は $1$ である。▨

定義 3.3. $r\in\N$ とし、 $p_1,\ldots,p_r\in\Q[t][x]$ とする。 $\Q(t)[x]$ の元としての次数と最高次係数を用い、 $J_0:=\{j\mid p_j=0\}$ 、 $J_t:=\{j\mid p_j\ne0,\ \deg p_j=0\}$ 、 $J_+:=\{j\mid p_j\ne0,\ \deg p_j\ge1\}$ と置く。 $j\in J_+$ ならば $\operatorname{lc}(p_j)\in\Q[t]$ である。 $\Q[t]$ の有限部分集合 $\Delta$ に対して、 $Z(\Delta):=\{a\in\R\mid\text{ある }\delta\in\Delta\text{ について }\delta(a)=0\}$ と置く。

$J_+\ne\emptyset$ とする。 $\Q(t)[x]$ において $P:=\prod_{j\in J_+}p_j$ 、 $n:=\deg P$ と置き、 $P$ と $P'$ のモニック最大公約元を $D$ とし、補題 3.2 (1)の $h$ を $f=P$ について取ったものを $H$ 、 $d:=\deg H$ とする。 $P$ の $H$ による除法の商を $A$ 、 $H^n$ の $P$ による除法の商を $B$ とする。各 $j\in J_+$ について、 $H$ と $p_j$ のモニック最大公約元を $G_j$ 、 $H$ の $G_j$ による除法の商を $B_j$ 、 $p_j$ の $G_j$ による除法の商を $C_j$ とし、 $U_jH+V_jp_j=G_j$ を満たす $U_j,V_j\in\Q(t)[x]$ を一組取る。 $H$ 、 $A$ 、 $B$ と各 $G_j$ 、 $B_j$ 、 $C_j$ 、 $U_j$ 、 $V_j$ の係数の分数表示を一つずつ取り、 $\operatorname{Res}(H,H')$ の分数表示 $(u_R,v_R)$ を一つ取る。補題 3.2 (1)により $d\ge1$ であるから、 $\operatorname{Res}(H,H')$ は定まる。
$J_+\ne\emptyset$ ならば、 $\{\operatorname{lc}(p_j)\mid j\in J_+\}$ 、 $\{p_j\mid j\in J_t\}$ 、(1)で取った係数の分数表示の分母の全体、および $\{u_R,v_R\}$ の和集合を $\Delta$ と置く。 $J_+=\emptyset$ ならば $\Delta:=\{p_j\mid j\in J_t\}$ と置く。 $\Delta$ を $(p_1,\ldots,p_r)$ の射影族 (projection family) という。

命題 3.4.定義 3.3の記号の下で $J_+\ne\emptyset$ とする。

$H$ はモニックで $d\ge1$ であり、 $\Q(t)[x]$ において $P=HA$ と $H^n=PB$ が成り立ち、各 $j\in J_+$ について $H=G_jB_j$ 、 $p_j=G_jC_j$ 、 $U_jH+V_jp_j=G_j$ が成り立つ。
$\operatorname{Res}(H,H')\ne0$ であり、 $\Delta$ は $\Q[t]$ の零でない元からなる有限集合である。
$U_j,V_j$ を§E6.28 命題 3.1の正規化後の Bézout 等式の係数として取るとき、 $P$ 、 $D$ 、 $H$ 、 $A$ 、 $B$ 、 $G_j$ 、 $B_j$ 、 $C_j$ 、 $U_j$ 、 $V_j$ 、 $\operatorname{Res}(H,H')$ の分数表示と $\Delta$ は、有理数の四則演算と比較の有限回で得られる。

証明.(1)を示す。補題 2.2 (1)により、 $\Q(t)$ は任意の正の整数 $k$ に対して $k\cdot1\ne0$ を満たす。 $J_+$ の各 $p_j$ の次数は $1$ 以上であるから、§E6.28 命題 1.2により $n\ge1$ である。補題 3.2を $F=\Q(t)$ 、 $f=P$ に適用すると、 $H$ はモニックで $d\ge1$ であり、 $H\mid P$ かつ $P\mid H^n$ である。 $G_j$ は $H$ と $p_j$ の公約元である。§E6.28 定理 2.1の一意性により、割り切る多項式による除法の剰余は零であるから、 $P=HA$ 、 $H^n=PB$ 、 $H=G_jB_j$ 、 $p_j=G_jC_j$ である。 $U_jH+V_jp_j=G_j$ は $U_j,V_j$ の取り方による。

(2)を示す。§E20.40 定義 4.6により $H'\ne0$ かつ $\deg H'=d-1$ であるから、 $\deg H+\deg H'=2d-1\ge1$ である。補題 3.2 (3)により $H$ と $H'$ のモニック最大公約元は $1$ であるから、§E20.40 定理 4.5を $F=\Q(t)$ で適用して $\operatorname{Res}(H,H')\ne0$ を得る。したがって $u_R\ne0$ である。 $\operatorname{lc}(p_j)$ （ $j\in J_+$ ）、 $p_j$ （ $j\in J_t$ ）、分数表示の分母および $v_R$ は零でない。 $\Delta$ は有限個の有限集合の和集合である。

(3)を示す。 $P$ は $p_j$ の積であり、 $P'$ 、 $H'$ は導関数である。 $D$ と $G_j$ は Euclid アルゴリズムで得られ、 $U_j,V_j$ は正規化後の Bézout 等式の係数である。 $H$ は $P$ の $D$ による除法の商に最高次係数の逆元を掛けて得られ、 $A$ 、 $B$ 、 $B_j$ 、 $C_j$ は除法の商である。 $\operatorname{Res}(H,H')$ は $H$ と $H'$ の係数を成分とする Sylvester 行列の行列式である。いずれも補題 2.2 (4)により有理数の四則演算と比較の有限回で得られ、 $\Delta$ はそれらの分母と分子および $p_j$ の最高次係数を集めて得られる。▨

命題 3.5.定義 3.3の記号の下で $a\in\R\setminus Z(\Delta)$ とする。 $j\in J_t$ ならば $p_j(a)\ne0$ である。 $J_+\ne\emptyset$ ならば、 $H$ 、 $A$ 、 $B$ と各 $G_j$ 、 $B_j$ 、 $C_j$ 、 $U_j$ 、 $V_j$ は $\mathcal O_a[x]$ に属し、補題 2.2 (2)の $f_a$ を $G_{j,a}:=(G_j)_a$ などと書くと、次が成り立つ。

$\R[x]$ において $P_a=H_aA_a$ 、 $H_a^n=P_aB_a$ が成り立ち、各 $j\in J_+$ について $H_a=G_{j,a}B_{j,a}$ 、 $(p_j)_a=G_{j,a}C_{j,a}$ 、 $U_{j,a}H_a+V_{j,a}(p_j)_a=G_{j,a}$ が成り立つ。 $j\in J_+$ ならば $\deg(p_j)_a=\deg p_j$ である。
$H_a$ はモニックで次数が $d$ であり、 $H_a(\theta)=0$ を満たす任意の $\theta\in\R$ に対して $H_a'(\theta)\ne0$ である。
$\{\theta\in\R\mid H_a(\theta)=0\}=\bigcup_{j\in J_+}\{\theta\in\R\mid p_j(a,\theta)=0\}$ である。
$j\in J_+$ と $H_a(\theta)=0$ を満たす $\theta\in\R$ に対して、 $G_{j,a}(\theta)$ と $B_{j,a}(\theta)$ のちょうど一方が零であり、 $p_j(a,\theta)=0$ であることは $G_{j,a}(\theta)=0$ であることと同値である。

証明. $j\in J_t$ ならば $p_j\in\Delta$ であるから、 $p_j(a)\ne0$ である。 $J_+\ne\emptyset$ とする。 $H$ 、 $A$ 、 $B$ と各 $G_j$ 、 $B_j$ 、 $C_j$ 、 $U_j$ 、 $V_j$ の係数は、分母が $\Delta$ に属する分数表示をもち、その分母は $a$ で零にならないので、 $\mathcal O_a$ に属する。補題 2.2 (1)により $\Q[t][x]\subset\mathcal O_a[x]$ である。

(1)を示す。命題 3.4 (1)の等式に補題 2.2 (2)の環準同型を施すと、表示した等式を得る。 $j\in J_+$ について、 $(p_j)_a$ の $x^{\deg p_j}$ の係数は $\operatorname{lc}(p_j)(a)$ であり、 $\operatorname{lc}(p_j)\in\Delta$ から零でなく、より高い次数の係数は零であるから、 $\deg(p_j)_a=\deg p_j$ である。

(2)を示す。 $\ev_a(1)=1$ であるから、 $H_a$ はモニックで次数が $d$ である。 $u_R,v_R\in\Delta$ であるから $u_R(a)\ne0$ かつ $v_R(a)\ne0$ であり、 $\operatorname{Res}(H,H')\in\mathcal O_a$ かつ $\ev_a(\operatorname{Res}(H,H'))=u_R(a)/v_R(a)\ne0$ である。 $\operatorname{Res}(H,H')=\det S_{d,d-1}(H,H')$ の成分は $H$ と $H'$ の係数であって $\mathcal O_a$ に属し、 $\mathcal O_a$ は $\Q(t)$ の部分環であるから、この行列式は $\mathcal O_a$ の元として計算しても同じ元である。§E20.40 命題 4.9 (2)を $A=\mathcal O_a$ 、 $F=\R$ 、 $\psi=\ev_a$ 、 $f=H$ 、 $g=H'$ 、 $m=d$ 、 $n=d-1$ に適用する。 $\ev_a(1)=1\ne0$ と $\ev_a(d\cdot1)=d\ne0$ から、 $\ev_a(\operatorname{Res}(H,H'))=\operatorname{Res}(H_a,(H')_a)$ であり、補題 2.2 (2)により $(H')_a=H_a'$ である。したがって $\operatorname{Res}(H_a,H_a')\ne0$ である。 $H_a(\theta)=H_a'(\theta)=0$ を満たす $\theta\in\R$ が存在すれば、§E20.40 定理 4.5を $F=L=\R$ で適用して $\operatorname{Res}(H_a,H_a')=0$ となり、 $\operatorname{Res}(H_a,H_a')\ne0$ と両立しない。

(3)を示す。補題 2.2 (2)により $P_a=\prod_{j\in J_+}(p_j)_a$ であり、 $(p_j)_a(\theta)=p_j(a,\theta)$ である。 $H_a(\theta)=0$ ならば、 $P_a=H_aA_a$ から $P_a(\theta)=0$ であり、 $\R$ は整域であるから、ある $j\in J_+$ で $p_j(a,\theta)=0$ である。逆にある $j\in J_+$ で $p_j(a,\theta)=0$ ならば $P_a(\theta)=0$ であり、 $H_a^n=P_aB_a$ から $H_a(\theta)^n=0$ 、すなわち $H_a(\theta)=0$ である。

(4)を示す。 $H_a(\theta)=0$ とする。 $G_{j,a}(\theta)B_{j,a}(\theta)=H_a(\theta)=0$ であるから、二つの値の少なくとも一方は零である。補題 3.1 (2)を $F=\R$ で用いると $H_a'=G_{j,a}'B_{j,a}+G_{j,a}B_{j,a}'$ であるから、二つの値がともに零ならば $H_a'(\theta)=0$ となり、(2)と両立しない。したがってちょうど一方が零である。 $G_{j,a}(\theta)=0$ ならば $p_j(a,\theta)=G_{j,a}(\theta)C_{j,a}(\theta)=0$ である。 $p_j(a,\theta)=0$ ならば $G_{j,a}(\theta)=U_{j,a}(\theta)H_a(\theta)+V_{j,a}(\theta)p_j(a,\theta)=0$ である。▨

補題 4.1. $I\subset\R$ を開区間、 $d\ge1$ とし、 $\varphi_0,\ldots,\varphi_{d-1}\colon I\to\R$ を $C^1$ 級関数として、 $(t,x)\in I\times\R$ に対して $F(t,x):=x^d+\sum_{i=0}^{d-1}\varphi_i(t)x^i$ と置く。任意の $a\in I$ と $F(a,\theta)=0$ を満たす任意の $\theta\in\R$ に対して $\frac{\partial F}{\partial x}(a,\theta)\ne0$ であるとする。このとき、 $N\in\N$ と $C^1$ 級関数 $\theta_1,\ldots,\theta_N\colon I\to\R$ が存在して、任意の $a\in I$ に対して $\theta_1(a)<\cdots<\theta_N(a)$ かつ $\{x\in\R\mid F(a,x)=0\}=\{\theta_1(a),\ldots,\theta_N(a)\}$ である。

証明.

主張 4.1.1. 任意の $a_0\in I$ に対して、 $\delta>0$ と $m\in\N$ と $C^1$ 級関数 $g_1,\ldots,g_m\colon(a_0-\delta,a_0+\delta)\to\R$ が存在して、 $(a_0-\delta,a_0+\delta)\subset I$ であり、 $|t-a_0|<\delta$ を満たす任意の $t$ について $g_1(t)<\cdots<g_m(t)$ かつ $\{x\in\R\mid F(t,x)=0\}=\{g_1(t),\ldots,g_m(t)\}$ である。

証明. $F$ は $x$ の単項式と $\varphi_i$ の積の和であるから、開集合 $I\times\R$ 上で $C^1$ 級である。 $F(a_0,\cdot)$ は次数 $d$ のモニック多項式であるから、§E20.39 命題 2.1 (1)によりその実根は有限個であり、それらを $\xi_1<\cdots<\xi_m$ （ $m\in\N$ ）とする。各 $k$ について仮定により $\frac{\partial F}{\partial x}(a_0,\xi_k)\ne0$ であるから、§E4.8 系 3.1を $(a_0,\xi_k)$ に適用し、 $a_0$ の開近傍 $A_k$ 、 $\xi_k$ の開近傍 $B_k$ と $C^1$ 級関数 $g_k\colon A_k\to B_k$ で、 $(t,x)\in A_k\times B_k$ について $F(t,x)=0$ と $x=g_k(t)$ が同値になるものを取る。 $F(a_0,\xi_k)=0$ であるから $g_k(a_0)=\xi_k$ である。各 $k$ で $(\xi_k-\varepsilon,\xi_k+\varepsilon)\subset B_k$ を満たし、 $1\le k<m$ で $2\varepsilon<\xi_{k+1}-\xi_k$ を満たす $\varepsilon>0$ を取り、 $O_k:=(\xi_k-\varepsilon,\xi_k+\varepsilon)$ と置く。 $k<k'$ ならば、 $O_k$ の任意の元は $O_{k'}$ の任意の元より小さい。 $R:=2+\max_{0\le i<d}|\varphi_i(a_0)|$ と置く。 $g_k$ と $\varphi_i$ の $a_0$ での連続性により、 $\delta_0>0$ を、 $(a_0-\delta_0,a_0+\delta_0)$ が $I$ と $A_1,\ldots,A_m$ に含まれ、 $|t-a_0|<\delta_0$ ならば各 $k$ で $g_k(t)\in O_k$ 、各 $i$ で $|\varphi_i(t)|<|\varphi_i(a_0)|+1$ となるように取る。 $|t-a_0|<\delta_0$ とすると、 $x\in O_k$ について $F(t,x)=0$ と $x=g_k(t)$ は同値である。最高次係数が $1$ の $F(t,\cdot)$ について§E20.39 命題 2.1 (2)の $M$ を取ると $1+M<R$ であるから、 $|x|\ge R$ を満たす実数 $x$ について $F(t,x)\ne0$ であり、 $F(t,\cdot)$ の実根は $[-R,R]$ に属する。

$|t-a_0|<\delta$ を満たす任意の $t$ について $F(t,\cdot)$ の実根がすべて $O_1\cup\cdots\cup O_m$ に属するような $\delta\in(0,\delta_0]$ が存在しないと仮定する。各正の整数 $\nu$ に対して、 $|t_\nu-a_0|<\min\{\delta_0,1/\nu\}$ 、 $F(t_\nu,x_\nu)=0$ 、 $x_\nu\notin O_1\cup\cdots\cup O_m$ を満たす $t_\nu,x_\nu\in\R$ を取る。前段により $x_\nu\in[-R,R]$ である。§E2.9 定理 4.3により $[-R,R]$ はコンパクトであり、§E2.9 定理 3.1により点列コンパクトであるから、ある部分列 $(x_{\nu_l})_l$ がある $x_*\in[-R,R]$ に収束する。 $t_{\nu_l}\to a_0$ であり $F$ は連続であるから、 $F(a_0,x_*)=\lim_lF(t_{\nu_l},x_{\nu_l})=0$ である。したがって $m\ge1$ であり、ある $k$ で $x_*=\xi_k$ である。 $O_k$ は $\xi_k$ を含む開区間であるから、十分大きい $l$ について $x_{\nu_l}\in O_k$ である。一方、 $x_\nu$ の選び方により $x_{\nu_l}\notin O_k$ である。この二つは両立しないので、求める $\delta\in(0,\delta_0]$ が存在する。

$|t-a_0|<\delta$ とする。各 $g_k(t)$ は $O_k$ に属する $F(t,\cdot)$ の実根である。 $F(t,\cdot)$ の実根 $x$ はある $O_k$ に属するので、 $x=g_k(t)$ である。 $O_1,\ldots,O_m$ の順序により $g_1(t)<\cdots<g_m(t)$ である。▨

$a\in I$ に対して $F(a,\cdot)$ の実根の個数を $N(a)$ と書く。主張 4.1.1により、 $N$ は各点のある近傍で一定であるから、 $I$ 上で連続である。 $a<a'$ を満たす $a,a'\in I$ で $N(a)\ne N(a')$ となるものが存在すると仮定する。 $y:=\min\{N(a),N(a')\}+1/2$ は $N(a)$ と $N(a')$ の間にあるから、§D1.12 系 1.2により $N(c)=y$ を満たす $c\in[a,a']$ が存在する。 $N(c)$ は整数であり、 $y$ は整数でないので、この等式は成り立たない。したがって $N$ は $I$ 上で一定であり、その値を $N$ と書く。 $1\le k\le N$ と $a\in I$ に対して、 $F(a,\cdot)$ の実根のうち小さい方から $k$ 番目のものを $\theta_k(a)$ とする。 $a_0\in I$ に対して主張 4.1.1の $\delta$ 、 $m$ 、 $g_k$ を取ると $m=N$ であり、 $|t-a_0|<\delta$ ならば $\theta_k(t)=g_k(t)$ であるから、 $\theta_k$ は $a_0$ のある近傍で $C^1$ 級である。したがって $\theta_k$ は $I$ 上で $C^1$ 級であり、 $\theta_1(a)<\cdots<\theta_N(a)$ と根の集合の等式は $\theta_k$ の定め方による。▨

定理 4.2. $r\in\N$ 、 $p_1,\ldots,p_r\in\Q[t][x]$ とし、 $\Delta$ を $(p_1,\ldots,p_r)$ の射影族、 $I\subset\R$ を $I\cap Z(\Delta)=\emptyset$ を満たす開区間とする。 $S(a)$ は族 $(p_1,\ldots,p_r)$ について定義 1.1 (3)で定める。

$N\in\N$ と $C^1$ 級関数 $\theta_1,\ldots,\theta_N\colon I\to\R$ が存在して、任意の $a\in I$ に対して $\theta_1(a)<\cdots<\theta_N(a)$ かつ $\bigcup_{j\in J_+}\{b\in\R\mid p_j(a,b)=0\}=\{\theta_1(a),\ldots,\theta_N(a)\}$ である。 $J_+=\emptyset$ ならば $N=0$ である。
各 $j$ と $1\le k\le N$ について、 $\operatorname{sgn}p_j(a,\theta_k(a))$ は $a\in I$ によらない。
$a\in I$ に対して $\theta_0(a):=-\infty$ 、 $\theta_{N+1}(a):=+\infty$ と置く。各 $j$ と $0\le k\le N$ について、 $a\in I$ と $\theta_k(a)<b<\theta_{k+1}(a)$ を満たす組 $(a,b)$ の全体の上で $\operatorname{sgn}p_j(a,b)$ は一定である。
任意の $a,a'\in I$ に対して $S(a)=S(a')$ である。

証明. $j\in J_0$ ならば、任意の $(a,b)$ で $p_j(a,b)=0$ である。 $j\in J_t$ ならば、 $p_j(a,b)=p_j(a)$ は $b$ によらず、命題 3.5により $a\mapsto p_j(a)$ は $I$ 上で零にならない連続関数であるから、§E20.39 補題 1.4により $\operatorname{sgn}p_j(a,b)$ は $(a,b)\in I\times\R$ によらない。

(1)を示す。 $J_+=\emptyset$ ならば左辺の和集合は空であり、 $N=0$ として主張が成り立つ。 $J_+\ne\emptyset$ とし、 $H=x^d+\sum_{i<d}\varphi_ix^i$ と書く。各 $\varphi_i$ は分母が $\Delta$ に属する分数表示をもち、その分母は $I$ 上で零にならないので、補題 2.2 (3)により $a\mapsto\ev_a(\varphi_i)$ は $I$ 上で $C^1$ 級である。 $(t,x)\in I\times\R$ に対して $F(t,x):=H_t(x)=x^d+\sum_{i<d}\ev_t(\varphi_i)x^i$ と置くと、 $\frac{\partial F}{\partial x}(a,\theta)=H_a'(\theta)$ であるから、命題 3.5 (2)により補題 4.1の仮定が満たされる。補題 4.1の $N$ と $\theta_k$ について $\{\theta_1(a),\ldots,\theta_N(a)\}$ は $H_a$ の実根の全体であり、命題 3.5 (3)により主張が成り立つ。

(2)を示す。 $j\in J_0\cup J_t$ の場合は前段で示した。 $j\in J_+$ 、 $1\le k\le N$ とし、 $a\in I$ に対して $f(a):=G_{j,a}(\theta_k(a))$ 、 $g(a):=B_{j,a}(\theta_k(a))$ と置く。 $G_j$ と $B_j$ の係数は分母が $\Delta$ に属する分数表示をもつので、補題 2.2 (3)と $\theta_k$ の連続性により、 $f$ と $g$ は $I$ 上で連続である。命題 3.5 (4)により各 $a$ で $f(a)$ と $g(a)$ のちょうど一方が零であるから、 $\lambda(a):=f(a)^2/\bigl(f(a)^2+g(a)^2\bigr)$ は $I$ 上の連続関数であり、 $f(a)=0$ ならば $\lambda(a)=0$ 、 $f(a)\ne0$ ならば $\lambda(a)=1$ である。 $\lambda(a)\ne\lambda(a')$ を満たす $a<a'$ が $I$ に存在すると仮定すると、§D1.12 系 1.2により $\lambda(c)=1/2$ を満たす $c\in[a,a']$ が存在し、 $\lambda(c)\in\{0,1\}$ と両立しない。したがって $\lambda$ は $I$ 上で一定である。 $\lambda$ が恒等的に $0$ ならば、命題 3.5 (4)により任意の $a\in I$ で $p_j(a,\theta_k(a))=0$ である。 $\lambda$ が恒等的に $1$ ならば、任意の $a\in I$ で $f(a)\ne0$ であり、命題 3.5 (4)により $p_j(a,\theta_k(a))\ne0$ である。 $a\mapsto p_j(a,\theta_k(a))$ は連続であるから、§E20.39 補題 1.4によりその符号は $I$ 上で一定である。

(3)を示す。 $j\in J_0\cup J_t$ の場合は前段で示した。 $j\in J_+$ 、 $0\le k\le N$ とする。 $a\in I$ に対して、 $N=0$ ならば $s(a):=0$ 、 $k=0<N$ ならば $s(a):=\theta_1(a)-1$ 、 $k=N\ge1$ ならば $s(a):=\theta_N(a)+1$ 、 $1\le k<N$ ならば $s(a):=(\theta_k(a)+\theta_{k+1}(a))/2$ と置く。 $s$ は $I$ 上で連続であり、 $\theta_k(a)<s(a)<\theta_{k+1}(a)$ である。(1)により、各 $a\in I$ について関数 $p_j(a,\cdot)$ は区間 $(\theta_k(a),\theta_{k+1}(a))$ 上で零にならないので、§E20.39 補題 1.4により、この区間に属する任意の $b$ について $p_j(a,b)p_j(a,s(a))>0$ である。 $a\mapsto p_j(a,s(a))$ は $I$ 上で零にならない連続関数であるから、§E20.39 補題 1.4によりその符号は一定である。したがって $\operatorname{sgn}p_j(a,b)=\operatorname{sgn}p_j(a,s(a))$ は組 $(a,b)$ によらない。

(4)を示す。 $a\in I$ とする。任意の $b\in\R$ は、ある $1\le k\le N$ で $b=\theta_k(a)$ を満たすか、ある $0\le k\le N$ で $\theta_k(a)<b<\theta_{k+1}(a)$ を満たし、後者の各区間は空でない。したがって $S(a)$ は、 $1\le k\le N$ に対する $\sigma(a,\theta_k(a))$ と、 $0\le k\le N$ に対する区間 $(\theta_k(a),\theta_{k+1}(a))$ 上での $\sigma(a,b)$ の値とからなる。(2)と(3)によりこれらの値は $a$ によらないので、 $S(a)$ は $a\in I$ によらない。▨

例 4.3. $r=1$ 、 $p_1:=x^3-3x+t$ とする。 $J_+=\{1\}$ 、 $P=p_1$ 、 $n=3$ 、 $P'=3x^2-3$ であり、

S_{3,2}(P,P')=\begin{pmatrix}1&0&3&0&0\\0&1&0&3&0\\-3&0&-3&0&3\\t&-3&0&-3&0\\0&t&0&0&-3\end{pmatrix}

である。第 $3$ 列から第 $1$ 列の $3$ 倍を引き、第 $4$ 列から第 $2$ 列の $3$ 倍を引くと、§E20.40 補題 4.2 (3)により行列式は変わらず、第 $1$ 行と第 $2$ 行は $(1,0,0,0,0)$ と $(0,1,0,0,0)$ になり、第 $3$ 行から第 $5$ 行の第 $3$ 列から第 $5$ 列の成分は $(6,0,3)$ 、 $(-3t,6,0)$ 、 $(0,-3t,-3)$ になる。§E20.40 定義 4.1の和で $\sigma(1)=1$ かつ $\sigma(2)=2$ を満たす項だけが残るので、

\operatorname{Res}(P,P')=\det\begin{pmatrix}6&0&3\\-3t&6&0\\0&-3t&-3\end{pmatrix}=27t^2-108

である。これは $\Q(t)$ の零でない元であるから、§E20.40 定理 4.5により $D=1$ であり、 $H=P$ 、 $d=3$ 、 $A=1$ 、 $B=P^2$ 、 $G_1=H$ 、 $B_1=C_1=1$ である。 $U_1:=0$ 、 $V_1:=1$ と取り、すべての係数を分母 $1$ の分数表示で、 $(u_R,v_R):=(27t^2-108,1)$ と取ると、 $\Delta=\{1,\ 27t^2-108\}$ 、 $Z(\Delta)=\{-2,2\}$ である。

定理 4.2 (1)により、 $(-\infty,-2)$ 、 $(-2,2)$ 、 $(2,\infty)$ のそれぞれの上で $p_1(a,\cdot)$ の実根の個数 $N$ は一定である。 $p_1(0,x)=x(x^2-3)$ の実根は $0,\pm\sqrt3$ であるから、 $(-2,2)$ 上で $N=3$ である。 $p_1(3,x)=(x-1)^2(x+2)+1$ であるから、 $p_1(3,b)=0$ を満たす実数 $b$ は $(b-1)^2(b+2)=-1$ を満たし、 $b<-2$ である。 $b<b'\le-2$ ならば $b^2,\ bb',\ b'^2\ge4$ から $p_1(3,b')-p_1(3,b)=(b'-b)(b'^2+b'b+b^2-3)>0$ であり、 $p_1(3,-3)=-15<0<1=p_1(3,-2)$ であるから、§D1.12 定理 1.1により $p_1(3,\cdot)$ の実根はちょうど一つである。 $p_1(-t,-x)=-p_1(t,x)$ であるから $p_1(-3,\cdot)$ の実根もちょうど一つであり、 $(-\infty,-2)$ と $(2,\infty)$ 上で $N=1$ である。 $t=\pm2$ では $p_1(2,x)=(x-1)^2(x+2)$ 、 $p_1(-2,x)=(x+1)^2(x-2)$ は相異なる実根を二つもち、その一方は重根であって、補題 4.1の仮定は成り立たない。

命題 5.1. $r\in\N$ 、 $p_1,\ldots,p_r\in\Q[t][x]$ とし、 $S(a)$ を族 $(p_1,\ldots,p_r)$ について定義 1.1 (3)で定める。実数 $a$ は有理数として、または§E20.40 定義 1.1 (2)の表示によって与えられているとし、 $K:=\Q(a)$ と置く。 $p_j=\sum_iu_{ji}x^i$ （ $u_{ji}\in\Q[t]$ ）と書き、 $g_j:=\sum_iu_{ji}(a)x^i\in K[x]$ と置く。

各 $u_{ji}(a)$ は、 $a$ が有理数ならば有理数の四則演算の有限回で得られ、 $a$ が表示で与えられているならばその表示が§E20.40 定理 5.3の有限回の適用で得られる。任意の $b\in\R$ に対して $g_j(b)=p_j(a,b)$ である。
$r=0$ ならば $S(a)=\{()\}$ である。 $r\ge1$ とし、 $g_1,\ldots,g_r$ に§E20.40 定理 7.3を適用して得る区画のうち一点集合でないものの標本点の全体を $E$ 、一点集合である区画の点の全体を $E'$ とすると、 $S(a)=\bigl\{(\operatorname{sgn}g_1(s),\ldots,\operatorname{sgn}g_r(s))\bigm| s\in E\cup E'\bigr\}$ であり、右辺は§E20.40 定理 7.3の計算の有限回で得られる。

証明.(1)を示す。 $a$ が有理数ならば、 $u_{ji}(a)$ は有理数の四則演算で得られる。 $a$ が表示で与えられているとする。有理数 $c$ について $x-c$ は平方自由であり、 $(c-1,c+1)$ はその分離区間であるから、 $(x-c,c-1,c+1)$ は $c$ の表示である。 $u_{ji}=\sum_{l=0}^Lc_lt^l$ に対して、 $c_L$ から始めて $a$ を掛けて次の係数 $c_{l}$ を加える操作を $L$ 回行うと $u_{ji}(a)$ が得られ、各操作は§E20.40 定理 5.3の積と和である。 $g_j(b)=\sum_iu_{ji}(a)b^i=p_j(a,b)$ は定義 1.1の値の定め方による。

(2)を示す。 $r=0$ ならば $\{-1,0,1\}^0$ は空列 $()$ だけからなるので、 $S(a)=\{()\}$ である。 $r\ge1$ とする。 $K$ は、 $a$ が有理数ならば $s=0$ 、そうでなければ $s=1$ 、 $\gamma_1=a$ とした§E20.40 命題 6.1の体であり、(1)により $g_j$ の係数は有理数または表示として与えられる。 $b\in\R$ とすると、§E20.40 定理 7.3 (1)により $b$ はただ一つの区画に属する。その区画が一点集合ならば $b\in E'$ である。そうでなければ、その区画の標本点を $s$ とすると、§E20.40 定理 7.3 (2)により各 $j$ で $\operatorname{sgn}g_j(b)=\operatorname{sgn}g_j(s)$ である。(1)により $\sigma(a,b)=(\operatorname{sgn}g_j(b))_j$ であるから、 $\sigma(a,b)$ は右辺に属する。逆に $E\cup E'$ の各元 $s$ は実数であり、 $(\operatorname{sgn}g_j(s))_j=\sigma(a,s)\in S(a)$ である。右辺が有限回の計算で得られることは、§E20.40 定理 7.3の最後の主張による。▨

命題 5.2. $\Delta$ を $\Q[t]$ の零でない元からなる有限集合とする。 $\Delta$ が次数 $1$ 以上の元をもつならば、 $\Delta$ の元を並べた族に変数を $t$ として§E20.40 定理 7.3を $K=\Q$ で適用し、次数 $1$ 以上の元の積から同定理で得る平方自由な多項式を $W\in\Q[t]$ 、その根の個数を $m$ とし、有理数 $c_\ell<d_\ell$ （ $1\le\ell\le m$ ）を同定理の条件を満たすように取り（§E20.40 定理 6.4 (4)の出力を並べ替えたものはこれを満たす）、 $(c_\ell,d_\ell)$ に属する $W$ の実根を $\alpha_\ell$ とする。 $\Delta$ が次数 $1$ 以上の元をもたないならば（ $\Delta=\emptyset$ の場合を含む）、 $W$ を定めず、 $m:=0$ とする。 $m=0$ ならば、 $\R$ を唯一の区画とし、その標本点を $\tau_\R:=0$ 、 $\chi_\R:=\top$ とし、 $\Xi$ を空の族とする。 $m\ge1$ ならば、 $I_0:=(-\infty,\alpha_1)$ 、 $I_\ell:=(\alpha_\ell,\alpha_{\ell+1})$ （ $1\le\ell<m$ ）、 $I_m:=(\alpha_m,\infty)$ と一点集合 $\{\alpha_\ell\}$ （ $1\le\ell\le m$ ）を区画とし、標本点を $\tau_{I_0}:=c_1$ 、 $\tau_{I_\ell}:=d_\ell$ （ $1\le\ell\le m$ ）、 $\tau_{\{\alpha_\ell\}}:=\alpha_\ell$ とする。 $\Xi$ を $t-c_\ell$ 、 $t-d_\ell$ 、 $W(c_\ell)W$ （ $1\le\ell\le m$ ）と $W$ からなる $\Q[t]$ の有限族とし、 $\Xi$ 上の符号条件式

\begin{aligned} \chi_{=\ell}&:=(t-c_\ell>0)\wedge(t-d_\ell<0)\wedge(W=0),\\ \chi_{<\ell}&:=(t-c_\ell\le0)\vee\bigl((t-c_\ell>0)\wedge(t-d_\ell<0)\wedge(W(c_\ell)W>0)\bigr),\\ \chi_{>\ell}&:=\neg\chi_{=\ell}\wedge\neg\chi_{<\ell} \end{aligned}

を定め、 $\chi_{I_0}:=\chi_{<1}$ 、 $\chi_{\{\alpha_\ell\}}:=\chi_{=\ell}$ 、 $\chi_{I_\ell}:=\chi_{>\ell}\wedge\chi_{<\ell+1}$ （ $1\le\ell<m$ ）、 $\chi_{I_m}:=\chi_{>m}$ と置く。

区画は $\R$ の分割をなし、各区画はその標本点を含む。一点集合でない区画は $Z(\Delta)$ と交わらない開区間である。 $m\ge1$ ならば、各 $\ell$ について $(W,c_\ell,d_\ell)$ の変数を $x$ に替えた三つ組は $\alpha_\ell$ の表示である。
任意の区画 $C$ と $a\in\R$ に対して、 $\chi_C(a)$ が成り立つことは $a\in C$ と同値である。

$\Delta$ が次数 $1$ 以上の元をもつかどうかは係数の比較で判定され、 $m$ 、 $\Xi$ 、各 $\chi_C$ と、定める場合の $W$ 、 $c_\ell$ 、 $d_\ell$ は、有理数の四則演算と比較の有限回で得られる。

証明. $\Delta$ の元は零でないので、零でない定数である $\Delta$ の元は実根をもたない。 $\Delta$ が次数 $1$ 以上の元をもたないならば、 $Z(\Delta)=\emptyset$ であり、 $m=0$ である。 $\Delta$ が次数 $1$ 以上の元をもつならば、§E20.40 定理 7.3の $J_0$ は空であり、§E20.40 定理 7.3 (1)により次数が $1$ 以上の $\Delta$ の元の実根の全体は $\{\alpha_1,\ldots,\alpha_m\}$ である。したがって、いずれの場合も $Z(\Delta)=\{\alpha_1,\ldots,\alpha_m\}$ である。

(1)を示す。 $m=0$ ならば、区画は $\R$ だけであり、標本点 $0$ を含み、 $Z(\Delta)=\emptyset$ である。 $m\ge1$ ならば、§E20.40 定理 7.3 (1)により区画は $\R$ の分割をなして各標本点はその区画に属し、一点集合でない区画はどの $\alpha_\ell$ も含まない開区間であるから $Z(\Delta)$ と交わらない。§E20.40 定理 7.3 (3)により $(W,c_\ell,d_\ell)$ は $\alpha_\ell$ の $\Q$ 上の表示であるから、 $W$ は平方自由であり、 $(c_\ell,d_\ell)$ は $W$ の分離区間である。したがって変数を $x$ に替えた三つ組は $\alpha_\ell$ の表示である。

(2)を示す。 $m=0$ ならば、 $[\top]$ は $\{-1,0,1\}^0$ 全体であるから、任意の $a$ で $\chi_\R(a)$ が成り立つ。 $m\ge1$ とし、 $1\le\ell\le m$ とする。§E20.40 命題 7.5を $W$ と分離区間 $(c_\ell,d_\ell)$ に適用すると、任意の実数 $a$ について、 $a=\alpha_\ell$ であることは $c_\ell<a<d_\ell$ かつ $W(a)=0$ であることと同値であり、 $a<\alpha_\ell$ であることは、 $a\le c_\ell$ であるか、 $c_\ell<a<d_\ell$ かつ $W(a)W(c_\ell)>0$ であることと同値である。定義 1.1 (2)により、これらの右辺はそれぞれ $\chi_{=\ell}(a)$ と $\chi_{<\ell}(a)$ と同値であり、 $\chi_{>\ell}(a)$ は $a=\alpha_\ell$ でも $a<\alpha_\ell$ でもないこと、すなわち $a>\alpha_\ell$ と同値である。 $I_0$ 、 $\{\alpha_\ell\}$ 、 $I_\ell$ （ $1\le\ell<m$ ）、 $I_m$ はそれぞれ $a<\alpha_1$ 、 $a=\alpha_\ell$ 、 $\alpha_\ell<a<\alpha_{\ell+1}$ 、 $a>\alpha_m$ を満たす実数 $a$ の全体であるから、主張が成り立つ。

最後の主張は、§E20.40 定理 7.3の最後の主張と、 $W(c_\ell)$ が有理数の四則演算で得られることによる。▨

定理 5.3. $r\in\N$ 、 $p_1,\ldots,p_r\in\Q[t][x]$ とし、 $\Phi$ を族 $(p_1,\ldots,p_r)$ 上の符号条件式とする。次の手続きを考える。

$J_0$ 、 $J_t$ 、 $J_+$ を求め、 $(p_1,\ldots,p_r)$ の射影族 $\Delta$ を、 $J_+\ne\emptyset$ ならば命題 3.4 (3)の計算で求める。
$\Delta$ に命題 5.2を適用し、区画、標本点 $\tau_C$ 、族 $\Xi$ と符号条件式 $\chi_C$ を求める。
各区画 $C$ について、 $\tau_C$ に命題 5.1を適用して $S(\tau_C)$ を求める。
$[\Phi]$ を定義 1.1 (2)の規則で求め、 $S(\tau_C)\cap[\Phi]\ne\emptyset$ を満たす区画 $C$ の全体を $\mathcal T_\exists$ 、 $S(\tau_C)\subset[\Phi]$ を満たす区画 $C$ の全体を $\mathcal T_\forall$ とする。
$\Psi_\exists:=\bigvee_{C\in\mathcal T_\exists}\chi_C$ 、 $\Psi_\forall:=\bigvee_{C\in\mathcal T_\forall}\chi_C$ と置く。

この手続きは有理数の四則演算と比較の有限回で停止する。 $\Psi_\exists$ と $\Psi_\forall$ は $\Q[t]$ の元からなる有限族 $\Xi$ 上の符号条件式であり、任意の $a\in\R$ に対して

\bigl(\exists b\in\R\ \ \Phi(a,b)\bigr)\iff\Psi_\exists(a),\qquad\bigl(\forall b\in\R\ \ \Phi(a,b)\bigr)\iff\Psi_\forall(a)

が成り立つ。

証明. $J_0$ 、 $J_t$ 、 $J_+$ は $p_j$ の係数を $0$ と比較して得られ、 $\Delta$ は、 $J_+\ne\emptyset$ ならば命題 3.4 (3)により、 $J_+=\emptyset$ ならば $J_t$ の $p_j$ を集めて得られる。命題 3.4 (2)により $\Delta$ は $\Q[t]$ の零でない元からなる有限集合であり、命題 5.2により区画、標本点、 $\Xi$ 、 $\chi_C$ は有限回の計算で得られ、区画は有限個である。命題 5.2 (1)により一点集合の区画の標本点は表示で与えられるので、命題 5.1 (2)により各 $S(\tau_C)$ は有限回の計算で得られる。 $[\Phi]$ は有限集合 $\{-1,0,1\}^r$ の部分集合として $\Phi$ の構成に沿って補集合・共通部分・和集合を有限回取って得られ、 $\mathcal T_\exists$ と $\mathcal T_\forall$ は有限集合の比較で得られる。したがって手続きは有限回で停止する。各 $\chi_C$ は $\Xi$ 上の符号条件式であるから、 $\Psi_\exists$ と $\Psi_\forall$ も $\Xi$ 上の符号条件式である。

$a\in\R$ とする。命題 5.2 (1)により、 $a$ を含む区画 $C$ がただ一つ存在する。 $C$ が一点集合ならば $a=\tau_C$ である。 $C$ が一点集合でなければ、 $C$ は $Z(\Delta)$ と交わらず $\tau_C$ を含む開区間であるから、定理 4.2 (4)により $S(a)=S(\tau_C)$ である。いずれの場合も $S(a)=S(\tau_C)$ である。定義 1.1 (3)により、 $\Phi(a,b)$ を満たす $b\in\R$ が存在することは $S(a)\cap[\Phi]\ne\emptyset$ と同値であり、任意の $b\in\R$ で $\Phi(a,b)$ が成り立つことは $S(a)\subset[\Phi]$ と同値である。したがって、左辺の $\exists$ の式は $C\in\mathcal T_\exists$ と同値であり、 $\forall$ の式は $C\in\mathcal T_\forall$ と同値である。

$\mathcal T$ を $\mathcal T_\exists$ と $\mathcal T_\forall$ のいずれかとし、 $\Psi:=\bigvee_{C'\in\mathcal T}\chi_{C'}$ とする。定義 1.1 (2)により、 $\Psi(a)$ が成り立つことは $\chi_{C'}(a)$ を満たす $C'\in\mathcal T$ が存在することと同値である。命題 5.2 (2)により $\chi_{C'}(a)$ は $a\in C'$ と同値であり、区画は互いに交わらないので、 $\Psi(a)$ が成り立つことは $C\in\mathcal T$ と同値である。前段と合わせて、二つの同値が成り立つ。▨

例 5.4. $r=2$ 、 $p_1:=tx-1$ 、 $p_2:=tx$ とする。 $J_+=\{1,2\}$ であり、 $\Q(t)[x]$ において $p_1=t(x-1/t)$ 、 $p_2=tx$ である。 $x-1/t$ と $x$ は相異なるモニックな一次式であるから既約であり、 $P=t^2x(x-1/t)$ 、 $n=2$ である。補題 3.2 (1)により $D=1$ 、 $H=x(x-1/t)=x^2-x/t$ 、 $d=2$ であり、 $A=t^2$ 、 $B=H/t^2=x^2/t^2-x/t^3$ である。§E20.39 補題 3.3 (4)により $G_1=x-1/t$ 、 $G_2=x$ であり、 $B_1=x$ 、 $C_1=t$ 、 $B_2=x-1/t$ 、 $C_2=t$ である。 $U_1=U_2:=0$ 、 $V_1=V_2:=1/t$ と取ると $U_jH+V_jp_j=G_j$ が成り立つ。§E20.40 例 4.8 (3)により $\operatorname{Res}(H,H')=4\cdot0-(1/t)^2=-1/t^2$ である。係数を既約な分数で表し、 $(u_R,v_R):=(-1,t^2)$ と取ると、 $\Delta=\{-1,\ 1,\ t,\ t^2,\ t^3\}$ 、 $Z(\Delta)=\{0\}$ である。命題 5.2では $W=t$ 、 $m=1$ 、 $(c_1,d_1)=(-1,1)$ 、 $\alpha_1=0$ と取ることができ、区画は $(-\infty,0)$ 、 $\{0\}$ 、 $(0,\infty)$ 、標本点は $-1$ 、 $0$ 、 $1$ である。

$H$ の係数 $-1/t$ の任意の分数表示 $(u,v)$ は $ut=-v$ を満たすので $v(0)=0$ であり、 $H$ は $\mathcal O_0[x]$ に属さない。 $t=0$ では $p_1(0,x)=-1$ は次数が下がって零でない定数になり、 $p_2(0,x)=0$ は零多項式になる。命題 5.1 (2)により

\begin{aligned} S(-1)&=\{(1,1),(0,1),(-1,1),(-1,0),(-1,-1)\},\\ S(1)&=\{(-1,-1),(-1,0),(-1,1),(0,1),(1,1)\},\\ S(0)&=\{(-1,0)\} \end{aligned}

である。 $\Phi_1:=(p_1=0)$ について $\mathcal T_\exists=\{(-\infty,0),(0,\infty)\}$ であるから、 $\exists b\ \Phi_1(a,b)$ は $\Psi_\exists=\chi_{<1}\vee\chi_{>1}$ と同値であり、 $a\ne0$ と同値である。 $\Phi_2:=(p_2=0)$ について $\mathcal T_\forall=\{\{0\}\}$ であるから、 $\forall b\ \Phi_2(a,b)$ は $\Psi_\forall=\chi_{=1}=(t+1>0)\wedge(t-1<0)\wedge(t=0)$ と同値である。 $\Delta$ から $p_j$ の最高次係数と分母を除いた $\{-1\}$ は零点をもたないので、それによる区画は $\R$ だけになり、その標本点 $0$ で $S(0)\cap[\Phi_1]=\emptyset$ であるから、この区画から作る式は $\bot$ になる。一方、 $a=1$ 、 $b=1$ は $\Phi_1(a,b)$ を満たす。

例 5.5. $r=2$ 、 $p_1:=(x^2-t)^2$ 、 $p_2:=x$ とし、 $\Phi_1:=(p_1=0)\wedge(p_2>0)$ 、 $\Phi_2:=(p_1=0)\wedge(p_2\ge0)$ とする。 $u,v\in\Q[t]$ 、 $v\ne0$ が $(u/v)^2=t$ を満たすならば $u^2=tv^2$ かつ $u\ne0$ であり、§E6.28 命題 1.2により $2\deg u=1+2\deg v$ となって偶奇が合わない。したがって $x^2-t$ は $\Q(t)$ に根をもたず、§E6.28 定理 4.3により $\Q(t)[x]$ で既約である。 $\pi_1:=x^2-t$ と $\pi_2:=x$ は相異なるモニック既約多項式であり、 $P=\pi_1^2\pi_2$ 、 $n=5$ である。補題 3.2 (1)により $D=x^2-t$ 、 $H=\pi_1\pi_2=x^3-tx$ 、 $d=3$ であり、 $A=x^2-t$ 、 $B=(x^2-t)^3x^4$ である。 $D\ne1$ であるから§E20.40 定理 4.5により $\operatorname{Res}(P,P')=0$ であり、 $P$ の終結式は $\Delta$ に零でない元を与えない。§E20.39 補題 3.3 (4)により $G_1=x^2-t$ 、 $B_1=x$ 、 $C_1=x^2-t$ 、 $G_2=x$ 、 $B_2=x^2-t$ 、 $C_2=1$ である。 $U_1:=x/t$ 、 $V_1:=-1/t$ 、 $U_2:=0$ 、 $V_2:=1$ と取ると、

U_1H+V_1p_1=\frac{(x^2-t)\bigl(x^2-(x^2-t)\bigr)}t=x^2-t=G_1

であり、 $U_2H+V_2p_2=G_2$ である。 $H'=3x^2-t$ であり、 $S_{3,2}(H,H')$ の第 $1$ 列から第 $5$ 列は $xH$ 、 $H$ 、 $x^2H'$ 、 $xH'$ 、 $H'$ の係数ベクトル $(1,0,-t,0,0)$ 、 $(0,1,0,-t,0)$ 、 $(3,0,-t,0,0)$ 、 $(0,3,0,-t,0)$ 、 $(0,0,3,0,-t)$ である。第 $3$ 列から第 $1$ 列の $3$ 倍を、第 $4$ 列から第 $2$ 列の $3$ 倍を引くと、例 4.3と同じく第 $1$ 行と第 $2$ 行は $(1,0,0,0,0)$ と $(0,1,0,0,0)$ になり、第 $3$ 行から第 $5$ 行の第 $3$ 列から第 $5$ 列の成分は $(2t,0,3)$ 、 $(0,2t,0)$ 、 $(0,0,-t)$ になる。この $3$ 次の行列は上三角行列であるから、§E20.40 補題 4.2 (4)により $\operatorname{Res}(H,H')=2t\cdot2t\cdot(-t)=-4t^3$ である。 $U_1,V_1$ の零でない係数の分数表示の分母を $t$ 、その他の係数の分数表示の分母を $1$ とし、 $(u_R,v_R):=(-4t^3,1)$ と取ると、 $\Delta=\{1,\ t,\ -4t^3\}$ 、 $Z(\Delta)=\{0\}$ である。命題 5.2では $W=t$ 、 $m=1$ 、 $(c_1,d_1)=(-1,1)$ 、 $\alpha_1=0$ と取ることができ、区画は $(-\infty,0)$ 、 $\{0\}$ 、 $(0,\infty)$ 、標本点は $-1$ 、 $0$ 、 $1$ である。

$p_1(-1,x)=(x^2+1)^2$ は正であり、 $p_1(1,x)=(x^2-1)^2$ の実根は $\pm1$ 、 $p_1(0,x)=x^4$ の実根は重根 $0$ であって、 $0$ は $p_2(0,x)=x$ の根でもある。命題 5.1 (2)により

\begin{aligned} S(-1)&=\{(1,-1),(1,0),(1,1)\},\\ S(1)&=\{(1,-1),(0,-1),(1,0),(1,1),(0,1)\},\\ S(0)&=\{(1,-1),(0,0),(1,1)\} \end{aligned}

である。 $[\Phi_1]=\{(0,1)\}$ 、 $[\Phi_2]=\{(0,0),(0,1)\}$ である。したがって $\Phi_1$ については $\mathcal T_\exists=\{(0,\infty)\}$ 、 $\Psi_\exists=\chi_{>1}$ であり、 $\exists b\ \Phi_1(a,b)$ は $a>0$ と同値である。 $\Phi_2$ については $\mathcal T_\exists=\{\{0\},(0,\infty)\}$ 、 $\Psi_\exists=\chi_{=1}\vee\chi_{>1}$ であり、 $\exists b\ \Phi_2(a,b)$ は $a\ge0$ と同値である。二つの $\mathcal T_\exists$ は一点集合でない区画では一致し、点区画 $\{0\}$ だけで異なる。

§E20.41パラメータ付き多項式と量化子消去

1 符号条件式

2 有理関数の特殊化

3 平方自由部分と射影族

4 根の枝と符号の不変性

5 量化子の消去

前提記事