壮；（2㌘、㌫）一〜

となり，Bん十1＝助十1も同様に成り立つ。したがって，（4＋1）のときも成り立つ． ロ        一｛Ql

Pとρ丑と共通解をもつ場合，あるρ旭の根であるPの根を減少させるためにQ をt青 と置き換える．

2．1．4 多項式方程式・不等式の解の存在の決定

 上の結果から，Pが定数でないとき，システムP＝O，Q1＞O，＿，Q〉0の解が存在 するか決定することが出来る．このシステムがP1＝O，＿，み＝0と複数の方程式を含 んでいるならば，これを一つの方程式冴十．。。十瑞＝Oと置き換えることが出来る．また，

Q≧0は「Q〉OまたはQ＝O」と置き換えることができる．つまり，Q1＞0，＿，Q垣〉O のみを満たすシステムと考えることが出来る．よってこの場合，

  ．上のシステムが（α，十〇c）の形をした有界でないある区間で満たされるための必要   十分条件は，Q1，…，斬の最高次係数はすべて正であることである．同様に，上の   システムが（＿oo，α）の形をした有界でないある区間で満たされるための必要十分条   件は，Q1（＿X），．．。，Q乏（一X）の最高次係数はすべて正であることである．

       j

  ．α，わが積Q＝n Q｛の実根で，上のシステムが（α，6）上で満たされるための必       ｛：1

  要十分条件は，Q ＝O，Q1＞0，…，軌〉Oが実数解を持つことである．これは   deg（Q）≧2で，導関数Q が定数でないときのみ起こる．

2．2 パラメータを持つ多項式方程式・不等式のシステム

 次の定理を述べる前に，定理で用いる用語を初めに紹介する．

 多項式方程式・不等式のシステム

       81（T，X）〉10        82（T，X）〉20        8（T，x）：

       8疋（T，X）〉40

を考える。ここで8毒はT＝（T1，・．。，η）とXに関する実多項式で，〉全は＝または≠，

〉，＞のいずれかである．Xは変数として，Tは実数パラメータとして考える．この小節 では，パラメータTに依存するシステムの実数解の存在性について議論する方法について

述べる．

2．2．1 タルッキー・ザイデンベルク（Tarski−Seidenberg）の定理  ここで，次の定理を証明する．

定理2．8タルッキー・ザイデンベルクの定理 実係数のT＝（T1，．。．，η）とXを変数と する多項式方程式・不等式8（T，X）のシステム

      81（T，X）〉10       82（T，X）〉20       8（T，X）：

      8疋（T，X）〉40

が与えられたとき，実係数のTに関する多項式方程式・不等式の有限個のシステムC1（T），・、・，

C先（T）で，任意の古∈Rρに対し，rシステム8（士，X）が実数解を持つための必要十分条件が ら（t）の一つが満たされる」ものを作り出すアルゴリズムが存在する．

 言い換えるならば，公式rヨX8（T，X）」が，論理和r C！（X）または…またはCた（X）」

と同値である．タルッキー・ザイデンベルクの定理は，実変数xを消去するアルゴリズ ムが存在することを意味している．実変数を消去する例として，ヨXλX2＋BX＋0＝O

に対し，

    （λ≠0かつB2−4λ0≧O），（λ＝OかっB≠O），（λ＝B＝0＝0）

のいずれかが成り立つことが一般に知られている．この例は，パラメータに依存したシ ステムを議論するために，システム上の多項式のXに関する次数を固定すると都合がい いことを示している．3を（T，X）の二変数実多項式とするとき，これをXの多項式と考 え，3の最高次係数を1C（8）と表すことにする．また，固定された次数を持つシステムを

（8（T，X），の（T））の形式のシステムとよぶとする。ここで，P（T）は8（T，X）上に現れる 全ての多項式に対して，1c（8｛）≠Oを含むものとする、あるシステムが，固定した次数を 持つシステムの有限個の論理和と同値になることを，次の例を用いて観察する．

例2．9不等式TX3＋（ひ一1）X2＋γ〉0は，

         （T≠0かつτX3＋（σ一1）X2＋γ＞O），

         （T＝0かつひ一1≠0かつ（σ一1）X2＋γ＞O），

         （T＝Oかつσ一1＝Oかつγ〉O）

と同値になる．

よって，固定した次数をもつシステムを議論することで十分である．ほかにも方程式〉0 については，方程式 ＝O または不等式 〉O のみを考えればよい、なぜなら，

＊≠0 は ＊〉0または＿＊〉0 と， ＊≧0 は ＊＞Oまたは＊＝O とでき，前の論 理和と同値変形ができるからである．

 注意タルッキー・ザイデンベルクの定理の証明は，次の重要な事実も示している：

 8（T，X）上のすべての多項式が有理係数を持つとき，そのアルゴリズムは，すべての多 項式が有理係数を持っシステムC1（r），… ，C此（T）を作り出す。

 以下の小節の中で，定理2．8の証明を述べる．

2．2．2 一つの等式をもつシステム

 初めに，Xに関して正の次数の一つの等式を含む，固定した次数を持つシステムの場合 を考える．関数sign：R→｛＿1，O，1｝を

剛一

と定義する、P，Qユ，＿，軌を，Xに関して正の次数で，T＝（T1，。。．，η）とXを変数 とする実多項式とする．また，の（T）を，1≦4≦4に対して，1c（P）≠0かつ1c（Q1）≠O のシステムとする．

補題2．10多項式の族（P，Q1，… ，Q4）が与えられたとき，Tに関する多項式のリスト R1，…，私と，関数。：｛一1，O，1｝片→N∪｛0｝で，次の条件を満たすものを作り出すア ルゴリズムが存在する：

 任意のε＝（ε1，…，6κ）∈｛一1，0，1｝此と

       の（士）かっ吻η（R1（士））＝61かっ＿かっ吻η（凧（士））＝ε先

を満たす任意のt∈Rρに対し，システム

       P（亡，X）：0かつQ！（士，X）＞Oかつ… かつQ老（士，X）〉0 がちょうどC（6）個の解を持つ．

 補題2．10の証明の理解を進めやすくするため，先に4次多項式の例を挙げ、そのアルゴ リズムのフローチャートを示す，その後，一般の次数の場合の証明の概要を述べることに

する．

側2．11パラメータα，b，cに対し，等式X4＋αX2＋bX＋c＝0のときを考える．本 来，X4＋ρX3＋gX2＋rX＋5＝Oを考えるべきであるが，チルンハウス変換X＋葦＝

を用いることにより，

       （ 一里）4＋μ3＋（2次以下の項）

      4

      ＝■一μ3＋μ3＋（2次以下の項）

      ＝π4＋（2次以下の項）

と式変形できるからである．したが？て，等式X4＋αX2＋bX＋c＝0のときを考える．

この等式の最高次係数は消えない．また不等式がないため，一つのスツルム列のみを計算 する．スツルム列は以下のようになる．

       2αX2＋3bX＋4c

（X4＋αX2＋6X＋・，4×3＋2αX＋b，     ，

       4

    8・9b2  12b・α2（16α4卜4α3b2−128α2・2＋144α62卜27b4＋256・3）

一（2α一一十丁）X−6一。，

     α α   α      （2α3−8α・十9b2）2

 計算を進める過程で式を簡略にするため，以下の文字を導入することにする：

       r＝2α3−8α・十9b2，

       △＝16α4卜4α3b2−！28α2・2＋144αb2・一27う4＋256・3，

       Σ＝6（α2＋12・），

       A＝＿27b4＋256c3．

上の文字を用いると，スツルム列は

       2αX2＋36X＋4c−rX一Σ1α2△

  （X4＋αX2・lX・・，・X3・・α…， 。 ，、。，ア）

と書き直すことができる．スツルム列に現れるXに関する多項式の最高次係数は，1，4の 零でない定数を除けば，一隻，一具，字余であることに着目しておこう、

 次に，等式X4＋αX2＋bX＋c＝0の解の個数5を求めるフローチャートを表す．

Po＝X＋αX＋わX＋c

pユこ4×3＋2αX＋b

↓

α＝0一一一一一→脆5

・・

^

脆3 b＝0一一一一一

・・

̲

c＝O 一一一一→

w＼

片：X4＋αX2＋δX＋・

p！＝4×3＋2αX＋b 乃＝一2αX≒3bX■4c

8＝1

局＝X4＋わX＋・

p1＝4×3＋b 巧＝一3午4c

γe8

＼6

po＝X＋c

．P1＝4×3

P2＝一C

A＝O

L・

F＝0

十