Positivstellensatz(Krivine–Stengle Positivstellensatz)とは、実閉体 $R$ の上の多項式の連立条件 $f_i\ne0$、$g_j\ge0$、$h_l=0$ が $R^n$ に解をもたないことと、$f_i$ の積 $s$、$g_j$ の生成する前順序の元 $t$、$h_l$ の生成するイデアルの元 $i$ で $s^2+t+i=0$ となることが同値である、という Krivine と Stengle の定理である。Hilbert の零点定理の実数版で、証明は局所化した環の素錐から実閉包の点を作り、移行原理で $R$ に戻す。系として正値・非負の証明書、実の零点定理と実イデアルの特徴づけ、Artin の定理が出る。
前提知識: 実閉体, 実スペクトル, Tarski–Seidenbergの定理, Hilbertの零点定理
Positivstellensatz(ドイツ語で「正値点定理」の意)は、実閉体 $R$ の上の多項式の連立条件
$$
f_1\ne0,\dots,f_r\ne0,\qquad g_1\ge0,\dots,g_m\ge0,\qquad h_1=0,\dots,h_k=0
$$
が解をもたないことと、ある代数的な恒等式 $s^2+t+i=0$ が成り立つことの同値を述べる定理である(thm-ps-main)。$s$ は $f_i$ たちの積、$t$ は $g_j$ たちの積に平方の和を掛けて足したもの、$i$ は $h_l$ たちの生成するイデアルの元である。Krivine(Kri64)が示し、Stengle(Ste74)が再発見して実代数幾何に広めたので、Krivine–Stengle の Positivstellensatz とも呼ばれる。
Hilbertの零点定理 は、代数閉体の上で方程式系 $h_l=0$ が解をもたないことを $1\in(h_1,\dots,h_k)$ という恒等式で言い表す。Positivstellensatz はその実数版で、不等式と「$0$ でない」の条件も扱う。恒等式は解がないことの 証明書 であり、多項式の最適化では、その次数を制限して 半正定値計画 で探す。
| 内容 | 扱い |
|---|---|
| 等式の条件を前順序に吸収する(lem-ps-equalities) | 証明 |
| 真の前順序は素錐に含まれる(lem-ps-prime-cone) | 証明 |
| Positivstellensatz(thm-ps-main) | 証明。移行原理は引用 |
| 正値・非負・零の証明書(cor-ps-forms) | 証明 |
| 実の零点定理と実イデアル(thm-ps-real-null、prop-ps-real-ideal) | 証明 |
| 乗数が要る例、指数が大きくなる例 | 証明(ex-ps-multiplier、ex-ps-power) |
| 次数の評価 | 引用 |
この記事では $R$ を 実閉体 とし、$R[x]:=R[x_1,\dots,x_n]$ とする。$R$ の正の元は平方なので、$R[x]$ の 平方の和 の全体 $\Sigma$ は、正の係数を掛けても足しても閉じる。
$A$ を $\tfrac12$ を含む可換環とする。部分集合 $T\subset A$ が $T+T\subset T$、$TT\subset T$、すべての $a\in A$ について $a^2\in T$ を満たすとき、$T$ を $A$ の 前順序 といい、さらに $-1\notin T$ なら 真の前順序 という。
$R[x]$ の多項式の組 $f=(f_1,\dots,f_r)$、$g=(g_1,\dots,g_m)$、$h=(h_1,\dots,h_k)$ について、次を定める。
$T(g)$ は $g_1,\dots,g_m$ を含む最小の前順序である。Schmüdgenの定理 の定義「2 次加群と前順序」の $T(g)$($R=\mathbb R$)と同じものである。$T(g)$ の元は、$g_1,\dots,g_m$ がすべて $0$ 以上の点で $0$ 以上の値をとる。
等式の条件は、符号を変えた 2 つの不等式 $h\ge0$、$-h\ge0$ と同じである。前順序の側でも、その 2 つを足すとイデアルになる。
$T(g_1,\dots,g_m,h_1,-h_1,\dots,h_k,-h_k)=T(g)+I(h)$ である。
$\subset$:左辺の生成元の積 $g_J\cdot\prod(\pm h_l)$ のうち、$\pm h_l$ を 1 つでも含むものは $I(h)$ に入り、含まないものは $T(g)$ の生成元である。
$\supset$:$T(g)$ は左辺に入る。$u\in R[x]$ について
$$
uh_l=\Bigl(\frac{u+1}2\Bigr)^2h_l+\Bigl(\frac{u-1}2\Bigr)^2(-h_l)
$$
なので $uh_l$ は左辺に入る。左辺は和で閉じるので $I(h)$ も入り、$T(g)+I(h)$ も入る。$\square$
$A$ の部分集合 $P$ が、前順序で、$P\cup(-P)=A$、$-1\notin P$、かつ $\mathfrak p:=P\cap(-P)$ が素イデアルであるとき、$P$ を 素錐 という。実スペクトル の命題「素錐による言い換え」により、素錐 $P$ は $\operatorname{Frac}(A/\mathfrak p)$ の順序で「$a\ge0\iff a\in P$」となるものを定める。
$\tfrac12$ を含む可換環 $A$ の真の前順序 $T$ は、ある素錐 $P$ に含まれる。
要点:極大な真の前順序 $P$ では、$a$ と $-a$ のどちらかを付け加えられる。付け加えられないことを $-1$ の表示で書き、掛け合わせると $-1\in P$ が出る。
真の前順序の増大列の和は真の前順序なので、Zornの補題 により $T$ を含む極大な真の前順序 $P$ がある。$a\in A$ について $P[a]:=\{s+at\mid s,t\in P\}$ は前順序で($a^2\in P$ を使う)、$P$ と $a$ を含む。
主張.$P[a]$ と $P[-a]$ の少なくとも一方は真である。両方が $-1$ を含むとして $-1=s+at=s'-at'$($s,t,s',t'\in P$)と書く。$-at=1+s$ と $at'=1+s'$ を掛けると $-a^2tt'=(1+s)(1+s')$、すなわち $-1=s+s'+ss'+a^2tt'\in P$ となり矛盾する。
全順序性.主張と極大性から、すべての $a$ について $a\in P$ または $-a\in P$ である($P[a]$ が真なら $P[a]=P$)。
台はイデアル.$a\in\mathfrak p$、$c\in A$ とする。$c=\bigl(\tfrac{c+1}2\bigr)^2-\bigl(\tfrac{c-1}2\bigr)^2$ から $ca=\bigl(\tfrac{c+1}2\bigr)^2a+\bigl(\tfrac{c-1}2\bigr)^2(-a)\in P$ で、$a$ を $-a$ に替えて $-ca\in P$ である。$1\notin\mathfrak p$ なので真のイデアルである。
台は素.$ab\in\mathfrak p$、$a,b\notin\mathfrak p$ とする。符号を替えて $-a\notin P$、$-b\notin P$ としてよい。極大性から $P[-a]$、$P[-b]$ は $-1$ を含み、$-1=s-at=s'-bt'$ と書ける。$at=1+s$、$bt'=1+s'$ を掛けて $abtt'=(1+s)(1+s')$ である。$-ab\in P$ なので $-1=(-ab)tt'+s+s'+ss'\in P$ となり矛盾する。$\square$
$R$ を実閉体、$f_1,\dots,f_r$、$g_1,\dots,g_m$、$h_1,\dots,h_k\in R[x]$ とし、
$$
W:=\{x\in R^n\mid f_i(x)\ne0\ (\forall i),\ g_j(x)\ge0\ (\forall j),\ h_l(x)=0\ (\forall l)\}
$$
とおく。次は同値である。
この形は Lau10 Theorem 3.15(p. 36)に、係数を順序体 $K$ に広げ、$K$ の実閉包で解がないことと同値にした形は LPR Theorem 1.2.9(p. 5)にある($>$ の条件は $\ne$ と $\ge$ の組として扱われる。同 p. 3)。
2 ⇒ 1. $x\in W$ なら $s(x)\ne0$ なので $s(x)^2>0$、$t(x)\ge0$、$i(x)=0$ であり、$s^2+t+i$ は $x$ で正である。
1 ⇒ 2. 2 が成り立たないとして、$W$ の点を作る。$f:=f_1\cdots f_r\in S(f)$ とし($r=0$ なら $f=1$)、$I=I(h)$ とおく。
段階 1:環と前順序. もし $f^N\in I$ となる $N$ があれば、$s=f^N$、$t=0$、$i=-f^{2N}\in I$ が 2 を満たす。よって $\bar f$ は $R[x]/I$ で冪零でなく、
$$
B:=(R[x]/I)[\bar f^{-1}]
$$
は $0$ でない環で、$\tfrac12$ を含む。各 $f_i$ は $f$ を割るので、$S(f)$ の元の像は $B$ の単元である。$B$ の部分集合 $T':=\{\bar t/\bar s^2\mid t\in T(g),\ s\in S(f)\}$ を考える。$\bar t_1/\bar s_1^2+\bar t_2/\bar s_2^2=(\overline{t_1s_2^2+t_2s_1^2})/(\overline{s_1s_2})^2$ と積から $T'$ は和と積で閉じ、$B$ の元 $\bar a/\bar f^N$ の平方は $\bar a^2/(\bar f^N)^2\in T'$ である。よって $T'$ は前順序である。
段階 2:$T'$ は真. $-1=\bar t/\bar s^2$ とすると、局所化の定義から、ある $M$ で $f^M(s^2+t)\in I$ である。両辺に $f^M$ を掛けて $(f^Ms)^2+f^{2M}t\in I$ となる。$f^Ms\in S(f)$、$f^{2M}t\in T(g)$ なので 2 が成り立ち、仮定に反する。
段階 3:点を作る. lem-ps-prime-cone により素錐 $P\supset T'$ がある。$\mathfrak p=P\cap(-P)$ とし、$\kappa=\operatorname{Frac}(B/\mathfrak p)$ に $P$ の定める順序を入れ、その実閉包を $R'$ とする(実閉体 の定理「実閉包の存在とArtin–Schreierの定理」)。合成 $R\to B\to\kappa\to R'$ は実閉体の間の準同型なので順序を保つ(実閉体 の命題「準同型は順序を保つ」)。$\xi\in R'^n$ を変数 $x_1,\dots,x_n$ の像とする。
段階 4:$R$ に戻す. $R$ の元を係数とする閉じた論理式
$$
\exists x\ \Bigl(\textstyle\bigwedge_if_i(x)\ne0\wedge\bigwedge_jg_j(x)\ge0\wedge\bigwedge_lh_l(x)=0\Bigr)
$$
は $R'$ で真である。実閉体の拡大 $R\subset R'$ の間では、$R$ を係数とする閉じた論理式の真偽は変わらない(Tarski–Seidenberg の移行原理。BPR16 Theorem 2.98, p. 81)。よって $R$ でも真であり、$W\ne\emptyset$ となって 1 に反する。$\square$
段階 1 の局所化は、条件「$f\ne0$」を「$f$ は単元」に言い換える。条件「$h=0$」は $I$ で割ることで、「$g\ge0$」は前順序 $T'$ で表される。3 種類の条件が環の 3 つの操作に対応している。
条件がすべて 1 次式のとき、乗数を定数に限っても証明書が見つかる。1 次の不等式系 $g_j\ge0$ が解をもたないことは、ある $\lambda_j\ge0$ で $\sum_j\lambda_jg_j=-1$ となることと同値である。これは $s=1$、$t=\sum_j\lambda_jg_j$ の形の証明書で、Farkasの補題 の帰結である(Lau10 p. 36 はこの類似を述べている)。
以下、$K:=\{x\in R^n\mid g_j(x)\ge0\ (\forall j),\ h_l(x)=0\ (\forall l)\}$ とする。
$p\in R[x]$ とする。
$T(g,-p)=T(g)-p\,T(g)$ である(生成元の積に $-p$ は高々 1 回現れる)。thm-ps-main を次の系に当てる。
1 は「$p$ に平方の和の乗数 $b$ を掛ければ、明らかに正な形になる」と読める。乗数 $b$ と 2・3 の指数 $2e$ は一般には省けない(ex-ps-multiplier、ex-ps-power)。$g$ も $h$ もないとき、2 は $pb=p^{2e}+a$($a,b\in\Sigma$)となり、$p\ne0$ なら $b\ne0$ で $p=(p^{2e}+a)b/b^2$ は有理関数の平方の和である。これは Hilbertの第17問題 の定理「Artinの定理」の結論である。
$Z(J):=\{x\in R^n\mid q(x)=0\ (\forall q\in J)\}$、$\mathcal I(Z):=\{q\in R[x]\mid q|_Z=0\}$ と書く。
$R[x]$ のイデアル $J$ について
$$
\sqrt[R]{J}:=\{p\in R[x]\mid p^{2e}+\sigma\in J\text{ となる }e\ge1,\ \sigma\in\Sigma\text{ がある}\}
$$
を $J$ の 実根基 という。$a_1^2+\dots+a_q^2\in J$ なら $a_1,\dots,a_q\in J$ となるとき、$J$ を 実イデアル という。
$R[x]$ のイデアル $J$ について $\mathcal I(Z(J))=\sqrt[R]{J}$ である。
$J=(h_1,\dots,h_k)$ と有限個で生成する(Hilbert の基底定理)。
$\supset$:$x\in Z(J)$ で $p(x)^{2e}+\sigma(x)=0$、$\sigma(x)\ge0$ なので $p(x)=0$ である。
$\subset$:$p$ が $Z(J)$ で $0$ になるとする。cor-ps-forms の 3($g$ なし、$T(g)=\Sigma$)により $p^{2e}+\sigma\in J$($\sigma\in\Sigma$、$e\ge0$)である。$e=0$ なら $p^2$ を掛けて $p^2+p^2\sigma\in J$ とし、$e=1$ の形にする。$\square$
Hilbertの零点定理 で $\mathcal I(Z(J))$ が根基 $\sqrt J$ だったのに対し、実閉体では平方の和 $\sigma$ の分だけ大きい。たとえば $J=(x^2+1)\subset R[x]$ は実の零点をもたないので $\mathcal I(Z(J))=R[x]$ で、$1^2+x^2\in J$ がそれを示す。
$R[x]$ のイデアル $J$ について、$J$ が実イデアルであることと $J=\mathcal I(Z(J))$ は同値である。
$J=\mathcal I(Z(J))$ とし、$a_1^2+\dots+a_q^2\in J$ とする。$Z(J)$ の点で $\sum a_j(x)^2=0$ なので各 $a_j(x)=0$、すなわち $a_j\in\mathcal I(Z(J))=J$ である。
逆に $J$ を実イデアルとし、$p\in\mathcal I(Z(J))$ とする。thm-ps-real-null により $(p^e)^2+\sigma\in J$ で、$\sigma$ は平方の和なので、実イデアルの定義から $p^e\in J$ である。$p^e\in J$、$e\ge2$ とし、$e'=\lceil e/2\rceil$ とおく。$2e'\ge e$ なので $(p^{e'})^2=p^{2e'-e}p^e\in J$ であり、定義から $p^{e'}\in J$ である。$e'< e$ なので、これを繰り返して $p\in J$ を得る。$J\subset\mathcal I(Z(J))$ は明らかである。$\square$
$n=1$、$g_1=x^3$ とすると $K=\{x\ge0\}$ で、$p=x+1$ は $K$ の上で正である。cor-ps-forms の 1 の証明書は
$$
(x+1)\Bigl(\bigl(x-\tfrac12\bigr)^2+\tfrac34\Bigr)=1+x^3
$$
で、$b=x^2-x+1\in\Sigma$、$a=x^3\in T(x^3)$ である。
一方、$p\notin T(x^3)=\Sigma+\Sigma x^3$ である。$x+1=\sigma_0+\sigma_1x^3$($\sigma_0,\sigma_1\in\Sigma$)とする。$0$ でない平方の和は偶数次で最高次の係数が正なので、$\sigma_1\ne0$ なら $\sigma_1x^3$ は 3 次以上の奇数次で、偶数次の $\sigma_0$ と最高次の項が打ち消し合わない。右辺の次数は 3 以上になり、左辺の 1 次と合わない。$\sigma_1=0$ なら $x+1=\sigma_0$ が偶数次になり、これも合わない。$K$ はコンパクトでないので、Schmüdgenの定理 の仮定を満たさない。
$n=1$、$m\ge1$、$g_1=-x^{2m}$ とすると $K=\{0\}$ で、$p=x$ は $K$ の上で $0$ である。$e=m$ なら $p^{2m}+g_1=0$ が cor-ps-forms の 3 の証明書である。
$e< m$ では証明書はない。$x^{2e}+\sigma_0-\sigma_1x^{2m}=0$($\sigma_0,\sigma_1\in\Sigma$)とし、$x=0$ での零の位数(最低次の項の次数)を比べる。$0$ でない平方の和の最低次の項は偶数次で係数が正なので、$x^{2e}+\sigma_0$ の最低次は $2e$ 以下で係数は正である($\sigma_0$ の最低次が $2e$ なら係数は $1$ より大きい)。一方 $\sigma_1x^{2m}$ の最低次は $2m>2e$ 以上である。両辺が等しいことに反する。このように、$p$ を固定しても、必要な指数 $e$ は条件の次数とともにいくらでも大きくなる。
$h$ がないとき、$K$ の上で正な $p$ の証明書を比べる($R=\mathbb R$)。
| 定理 | 仮定 | $K$ の上で $p>0$ のときの表示 |
|---|---|---|
| Positivstellensatz(cor-ps-forms の 1) | なし | $pb=1+a$、$a,b\in T(g)$ |
| Schmüdgen の定理 | $K$ がコンパクト | $p\in T(g)$ |
| Putinar の定理 | 2 次加群 $M(g)$ が Archimedes 性をもつ | $p\in M(g)=\Sigma+\sum_j\Sigma g_j$ |
下の 2 行は Schmüdgenの定理 で証明する。乗数 $b$ がないので、$p$ を固定して表示を探す問題が凸になり、次数を制限すると 半正定値計画 になる。
恒等式の次数の上界は長く問題だった。LPR は、$n$ 変数、次数 $d$ 以下、$s$ 個の多項式の系が解をもたないとき、次数が 5 段の指数の塔で抑えられる証明書があることを示した(Theorem 1.4.2, p. 8)。同じ論文の紹介によれば、それ以前の評価は高さ $n+4$ の指数の塔であり(Theorem 1.3.2, p. 7)、下界としては、$n\ge2$ について、次数 $2$ 以下の $n$ 個の多項式からなる系で、どの証明書も次数 $2^{n-2}$ 以上になる例がある(p. 7)。上界と下界の差は大きい。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| thm-ps-main の $R$ が実閉体 | $R=\mathbb Q$、$h_1=x^2-2$ | 1 ⇒ 2($\mathbb Q$ に解はないが恒等式はない) |
| thm-ps-main の $s^2$ の平方 | $f_1=-1$ で $s+t=0$ を許す | 2 ⇒ 1($s=-1$、$t=1$ で成り立つが $W=R^n$) |
| Schmüdgenの定理 の $K$ のコンパクト性 | $g_1=x^3$、$p=x+1$(ex-ps-multiplier) | $p\in T(g)$ |
| thm-ps-real-null の平方の和 $\sigma$ | $J=(x^2+1)$、$p=1$ | $p\in\mathcal I(Z(J))$ だが $p^{2e}\notin J$ |
| prop-ps-real-ideal の実イデアル性 | $J=(x^2)$ | $J=\mathcal I(Z(J))$(実際は $\mathcal I(Z(J))=(x)$) |
1 行目:$s\in S(\emptyset)=\{1\}$、$t\in T(\emptyset)=\Sigma$ で、$1+t+i(x)$ を $x=\sqrt2\in\mathbb R$ で評価すると $1+t(\sqrt2)\ge1$ なので $0$ でない。
3 行目は ex-ps-multiplier で示した。
4 行目:$J$ の $0$ でない元は $x^2+1$ の倍数で 2 次以上なので、$1\notin J$ である。
5 行目:$Z(J)=\{0\}$ で $\mathcal I(Z(J))=(x)\ni x$ だが、$x\notin(x^2)$ である。$x^2\in J$ なので $J$ は実イデアルでない。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する