王蒙, 陈玉福
中国科学院大学数学科学学院, 北京 100049
2015年03月18日 收稿; 2015年04月14日 收修改稿
基金项目: 国家自然科学基金(11271363)资助
通信作者: E-mail:kami518@126.com

摘要: 给出判断有理系数多元多项式方程组是否存在实数解的初等方法,从而证明多元多项式方程组的实解存在性可在有限步内自动判定.基于此,给出判定有理系数多元多项式方程组是否存在实数解的算法.
关键词: 判别式矩阵判别式序列数学归纳法
An elementary method for verifying the existence of real roots of rational polynomial equations
WANG Meng, CHEN Yufu
School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China


Abstract: In this paper we present an elementary method to decide whether a system of multivariate polynomials with rational coefficients has a real solution. Based on our discussion of the method, an algorithm is shown, which implies that verifying a system of multivariate polynomials with rational coefficients has a real solution can be completed in finite steps.
Key words: discriminant matrixdiscriminant sequencemathematical induction
判断多项式方程和多项式方程组在代数闭域上是否有解的问题已经解决^[1-5]，特别是在复数域上是否有解的问题已经解决.但是判断有理系数多项式方程和有理系数多项式方程组在实数域上是否有解的问题，很长时间内都没有解决.Tarski^[6]在1948年指出,所有初等代数的判定问题都可以解决，并建立了实闭域上的一阶命题理论.有理系数多项式方程组是否存在实数解属于初等代数判定问题，因而，理论上可以解决.但是他们没有给出具体的判定方法. 文献^[7]给出如何判断单变元半代数问题是否存在实数解的算法，并指出该算法可以扩展为判定多元半代数问题^[8-11]的实解存在性的算法.主要思路是把n变元半代数问题归约为有限个n-1 元半代数问题.但是，如何将n变元的半代数问题归约为n-1元半代数问题，以及如何判断是否存在实数使得一组多项式都大于零这些关键问题，文献^[7]都没有给出具体的步骤.本文给出判断有理系数多元多项式组实解存在性的初等方法.该方法基于杨路等人提出的单变元多项式的判别式理论^[12]，通过分类和归纳判断实数解是否存在.在解决单变元半代数问题时，这是归纳的基础，本文的方法不需将多项式组化成互素的，因此，本文的算法与文献^[7]给出算法有实质性的差别.
1 单变元多项式判别式单变元多项式的判别式理论^[5]由杨路提出，根据多项式的判别式，可以得出多项式方程的不同的实数解的个数.
定义1.1 给定单变元多项式

$f\left( x \right)={{a}_{n}}\cdot {{x}^{n}}+{{a}_{n-1}}\cdot {{x}^{n-1}}+\ldots +{{a}_{1}}\cdot x+{{a}_{0}};{{a}_{n}}\ne 0,$

(1)

其系数构成的2n阶方阵

$Discm\left( f \right):=\text{ }\left[ \begin{matrix} {{a}_{n}} & {{a}_{n-1}} & {{a}_{n-2}} & \ldots & {{a}_{0}} & {} & {} & {} \\ 0 & n\cdot {{a}_{n}} & \left( n-1 \right)\cdot {{a}_{n-1}} & \ldots & {{a}_{1}} & {} & {} & {} \\ {} & {{a}_{n}} & \left( n-1 \right)\cdot {{a}_{n-1}} & \ldots & {{a}_{1}} & {{a}_{0}} & {} & {} \\ {} & 0 & n\cdot {{a}_{n}} & \ldots & 2\cdot {{a}_{2}} & {{a}_{1}} & {} & {} \\ {} & {} & {} & {} & \vdots & \vdots & {} & {} \\ {} & {} & {} & {{a}_{n}} & {{a}_{n-1}} & {{a}_{n-2}} & \ldots & {{a}_{0}} \\ {} & {} & {} & 0 & n\cdot {{a}_{n}} & \left( n-1 \right)\cdot {{a}_{n-1}} & \ldots & {{a}_{1}} \\\end{matrix} \right]$

称为f(x)的判别矩阵.用D_k表示判别矩阵的2k 阶顺序主子式.约定D₀=1，称

$Discl\left( f \right):=[{{D}_{0}},{{D}_{1}},\ldots ,{{D}_{n}}]$

(2)

为多项式f(x)的判别式序列.
定义1.2 对于实数序列

$\bar{c}:=[{{c}_{0}},{{c}_{1}},{{c}_{2}},\ldots ,{{c}_{n}}]$

(3)

称

$\overline{sgn(c):}=[sgn({{c}_{0}}),sgn({{c}_{1}}),sgn({{c}_{2}}),\ldots ,sgn({{c}_{n}})]$

为实数序列c的符号表.
定义1.3 给定一个符号表[s₀,s₁,s₂,…s_n]，符号表的首项s₀不为零.依据以下规则构造一个新的符号表[ψ₀,ψ₁,ψ₂,…,ψ_n].构造规则如下：如果[s_i,s_i+1,…,s_i+j]是给定符号表的一部分，满足

${{s}_{i}}\ne 0;{{s}_{i+1}}={{s}_{i+2}}=\ldots ={{s}_{i+j-1}}=0;{{s}_{i+j}}\ne 0;$

(4)

那么就将

$[{{s}_{i+1}},{{s}_{i+2}},\ldots ,{{s}_{i+j-1}}]$

(5)

替换为

$[-{{s}_{i}},-{{s}_{i}},{{s}_{i}},{{s}_{i}},-{{s}_{i}},-{{s}_{i}},{{s}_{i}},{{s}_{i}},-{{s}_{i}},\ldots ],$

(6)

变换前后项数不变，而且变换后序列不再含有0 项.符号表[ψ₀,ψ₁,ψ₂,…,ψ_n]称为符号表[s₀,s₁,s₂,…,s_n]的符号修订表.
定理1.1 ^[1] 如果实系数多项式f(x)的判别式序列的符号修订表的变号数为v，那么f(x)的互异共轭虚根对的数目就是v; 如果该修订表中非零元的个数是l，则f(x) 的互异实根数目是l-1-2v.
定义1.4 对于实系数多项式

$f\left( x \right)={{a}_{n}}\cdot {{x}^{n}}+{{a}_{n-1}}\cdot {{x}^{n-1}}+\ldots +{{a}_{1}}\cdot x+{{a}_{0}}$

(7)

和另一个实系数多项式g(x)，设

$r\left( x \right)=rem\left( f\prime g,f \right)={{b}_{n-1}}\cdot {{x}^{n-1}}+{{b}_{n-2}}\cdot {{x}^{n-2}}+\ldots +{{b}_{1}}\cdot x+{{b}_{0}},$

(8)

称2n阶方阵

$Discm\left( f,g \right):=\left[ \begin{matrix} {{a}_{n}} & {{a}_{n-1}} & {{a}_{n-2}} & \ldots & {{a}_{0}} & {} & {} & {} \\ 0 & {{b}_{n-1}} & {{b}_{n-2}} & \ldots & {{b}_{0}} & {} & {} & {} \\ {} & {{a}_{n}} & {{a}_{n-1}} & \ldots & {{a}_{1}} & {{a}_{0}} & {} & {} \\ {} & {} & 0 & {{b}_{n-1}} & \ldots & {{b}_{2}} & {{b}_{0}} & {} \\ {} & {} & {} & {} & {} & \vdots & {} & {} \\ {} & {} & {} & {{a}_{n}} & {{a}_{n-1}} & {{a}_{n-2}} & \ldots & {{a}_{0}} \\ {} & {} & {} & 0 & {{b}_{n-1}} & {{b}_{n-2}} & \ldots & {{b}_{0}} \\\end{matrix} \right]$

为f(x)关于g(x)的广义判别式矩阵^[2]，令D₀=1，D_k(f,g)为矩阵Discm(f,g)的2k 阶顺序主子式，则

$Discl\left( f,g \right):=[{{D}_{0}},{{D}_{1}}\left( f,g \right),\ldots ,{{D}_{n}}\left( f,g \right)]$

(9)

称为f(x)关于g(x)的广义判别式序列.
定理1.2 给定实系数多项式f(x)，g(x)，如果Discl(f,g) 的符号修订表的变号数是v，而非零元素的个数是l，则

$l-1-2\cdot v={{f}_{g}}_{^{+}}-{{f}_{g}}_{^{-}},$

(10)

其中

${{f}_{g}}_{^{+}}=\left| \{x\in R \right|f\left( x \right)=0,g\left( x \right)＞0\}|,{{f}_{g}}_{^{-}}=\left| \{x\in R \right|f\left( x \right)=0,g\left( x \right)＜0\}|.$

(11)

定义1.5 问题P(n):

$\bar{g}=[{{g}_{1}}({{x}_{1}},{{x}_{2}},\ldots ,{{x}_{n}}),{{g}_{2}}({{x}_{1}},{{x}_{2}},\ldots ,{{x}_{n}}),\ldots ,{{g}_{m}}({{x}_{1}},{{x}_{2}},\ldots ,{{x}_{n}})],$

(12)

?i,g_i(x₁,x₂,…,x_n)是关于未定元(x₁,x₂,…,x_n)的有理系数多项式.

$\bar{c}=[{{c}_{1}},{{c}_{2}},\ldots ,{{c}_{m}}],$

(13)

?i,c_i是一个实数.
是否存在实数(x₁⁰,x₂⁰,…,x_n⁰),使得

$\forall i,({{c}_{i}}\ne 0\Rightarrow {{g}_{i}}({{x}^{0}}_{1},{{x}^{0}}_{2},\ldots ,{{x}^{0}}_{n})\cdot {{c}_{i}}>0)\wedge ({{c}_{i}}=0\Rightarrow {{g}_{i}}({{x}^{0}}_{1},{{x}^{0}}_{2},\ldots ,{{x}^{0}}_{n})=0).$

(14)

为了表述方便,下文要用到一些记号，下面指明这些记号的含义.
符号表是一个由0，1，-1组成的有限长的序列.对于任何一个符号表c，如果c 的符号修订表的非零元个数为l，变号数为v，那么记号number(c) 定义为 number(c):=l-2·v-1. degree(f(x₁,x₂,…,x_n),x_i)记为多项式f(x₁,x₂,…,x_n) 关于未定元x_i 的次数. coeff(f(x₁,x₂，…，x_n),x_i,k)记为多项式f(x₁,x₂,…,x_n)关于未定元x_i的k 次系数，一般是个关于未定元x₁,x₂,…,${\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\frown$}} \over x} _i}$,…,x_n的多项式. DiscriminantSequence(f(x₁,x₂,…,x_n),x_i) 记为多项式f(x₁,x₂,…,x_n) 关于未定元x_i的判别式序列. Discriminant Sequence(f(x₁,x₂,…,x_n),g(x₁,x₂,…,x_n),x_i) 记为根据定义4 以x_i 为主变元，求得的判别式序列. trunc(f,x_i,k) 记为将f 中所有关于未定元x_i 的次数大于k 的项截掉之后剩下的项组成的多项式.
2 P(1)可以在有限步内解决定义2.1 Q(n)是这样一个问题： 存在多少个不同的实数,使得
f(x)=0,g₁(x)>0,g₂(x)>0,…,g_n(x) ＞0,
f(x)不是零次多项式.
定理2.1 用记号number([f(x),g₁(x),g₂(x),…,g_n(x)])表示问题Q(n) 的解，也就是说存在number([f(x),g₁(x),g₂(x),…,g_n(x)]) 个不同的实数使得

$f\left( x \right)=0,{{g}_{1}}\left( x \right)＞0,{{g}_{2}}\left( x \right)＞0,\ldots ,{{g}_{n}}\left( x \right)＞0,$

number([f,g₁,g₂,…,g_n]) 可以写成有限多个形如c·number(DiscrimiantSequence(h(f,g₁,g₂,…,g_n),x))(c是有理数,h是关于f,g₁,…,g_k的多项式)的项及有限多个形如
d·number(DiscriminantSequence(h₁(f,g₁,g₂,…,g_n),h₂(f,g₁,g₂,…,g_n),x),
(d是有理数,h₁,h₂是关于f,g₁,…,g_n的多项式)的项的和.
证明：要求解存在多少个不同的实数,使得f(x)=0,g₁(x) ＞0. 根据定理1.1，可以求出f(x)=0有多少个不同的实数解，计f(x)=0一共有a 个不同的实数解. 根据定理1.1，可以求出f(x)²+g₁(x)²=0有多少个不同的实数解，设f(x)²+g₁(x)²=0一共有b个不同的实数解. 根据定理1.2，可以求出f_g⁺₁-f_g^-₁记为c. 那么一共有(a+c-b)/2个不同的实数,使得f(x)=0,g₁(x)＞0.所以求解的公式为

$\begin{array}{l}(number(DiscriminantSequence\left( {f,x} \right)) - \\number(DiscriminantSequence({f^2} + {g^2}_1,x)) + \\number(DiscriminantSequence(f,{g_1},x)))/2\end{array}$

(15)

假设对于Q(k)，number([f,g₁,g₂,…,g_k])可以表示成有限多个形如
c·number(Discrimiant(h(f,g₁,g₂,…,g_k),x)),
(c是有理数,h是关于f,g₁,…,g_k的多项式)的项及有限多个形如
d·number(DiscriminantSequence(h₁(f,g₁,g₂,…,g_k),h₂(f,g₁,g₂,…,g_k),x),
(d是有理数,h₁,h₂是关于f,g₁,…,g_k的多项式)的项的和.根据假设，可以求出以下5个系统的不同的实数解的个数(分别用记号a,b,c,d,e表示)，

$\left\{ \begin{matrix} f\left( x \right)=0 \\ {{g}_{1}}\left( x \right)＞0 \\ \vdots \\ {{g}_{k}}\left( x \right)＞0 \\\end{matrix} \right.$

(16)

$\begin{align} & \\ & \left\{ \begin{matrix} f\left( x \right)=0 \\ {{g}_{k+1}}\left( x \right)＞0 \\ {{g}_{2}}\left( x \right)＞0 \\ \vdots \\ {{g}_{k}}\left( x \right)＞0 \\\end{matrix} \right. \\ \end{align}$

(17)

$\left\{ \begin{matrix} f{{\left( x \right)}^{2}}+{{g}_{1}}{{\left( x \right)}^{2}}=0 \\ {{g}_{k+1}}\left( x \right)＞0 \\ {{g}_{2}}\left( x \right)＞0 \\ \vdots \\ {{g}_{k}}\left( x \right)＞0 \\\end{matrix} \right.$

(18)

$\left\{ \begin{matrix} f{{\left( x \right)}^{2}}+{{g}_{k+1}}{{\left( x \right)}^{2}}=0 \\ {{g}_{1}}\left( x \right)＞0 \\ \vdots \\ {{g}_{k}}\left( x \right)＞0 \\\end{matrix} \right.$

(19)

$\left\{ \begin{matrix} f\left( x \right)=0 \\ -{{g}_{1}}\left( x \right)\cdot {{g}_{k+1}}\left( x \right)＞0 \\ \vdots \\ {{g}_{k}}\left( x \right)＞0 \\\end{matrix} \right.$

(20)

$\left\{ \begin{matrix} f\left( x \right)=0 \\ {{g}_{1}}\left( x \right)＞0 \\ \vdots \\ {{g}_{k+1}}\left( x \right)＞0 \\\end{matrix} \right.$

(21)

那么满足(21)式的不同的实数的个数为(a+b-c-d-e)/2.根据假设a,b,c,d,e可以写成有限多个形如
c·number(DiscrimiantSequence(h(f,g₁,g₂,…,g_k+1),x)),
(c是有理数,h是关于f,g₁,…,g_k的多项式)的项及有限多个形如
d·number(DiscriminantSequence(h₁(f,g₁,g₂,…,g_k+1),h₂(f,g₁,g₂,…,g_k+1),x),
(d是有理数,h₁,h₂是关于f,g₁,…,g_k+1的多项式)的项的和.
所以满足式(21)的不同的实数的个数可以表示成有限多个形如
c·number(DiscrimiantSequence(h(f,g₁,g₂,…,g_k+1),x))，
(c是有理数,h是关于f,g₁,…,g_k的多项式)的项及有限多个形如
d·number(DiscriminantSequence(h₁(f,g₁,g₂,…,g_k+1),h₂(f,g₁,g₂,…,g_k+1),x)，
(d是有理数,h₁,h₂是关于f,g₁,…,g_k+1的多项式)的项的和.
综上所述，number([f,g₁,g₂,…,g_n])可以写成有限多个形如
c·number(DiscrimiantSequence(h(f,g₁,g₂,…,g_n),x))，
(c是有理数,h是关于f,g₁,…,g_k的多项式)的项及有限多个形如
d·number(DiscriminantSequence(h₁(f,g₁,g₂,…,g_n),h₂(f,g₁,g₂,…,g_n),x)，
(d是有理数,h₁,h₂是关于f,g₁,…,g_n的多项式)的项的和.
定理2.2 P(1)是可以通过有限步运算解决的.
证明：沿用定义问题P(n)时用到的记号，如果序列c的任意一项都为0.令F(x)=∑g_i(x)²，那么存在实数x⁰，使得?i,g_i(x⁰)=0，当且仅当存在实数x¹ 使得F(x¹)=0，下面证明这个结论.
如果存在实数(计为x⁰)使得i,g_i(x⁰)=0，那么∑g_i(x⁰)²=0，也就是说F(x⁰)=0；另一方面，因为?i,x?g_i(x)²≥0，所以如果存在实数(计为x⁰) 使得F(x⁰)=0，那么?i,g_i(x⁰)=0.综上所述，存在实数x⁰使得?i,g_i(x⁰)=0， 当且仅当存在实数x¹ 使得F(x¹)=0.
如果F(x)是个零次多项式，可直接判断F(0)是否为零.为零，有实数解;否则没有实数解.如果F(x)的次数大于零，如果 number(DiscriminantSequence(F(x),x)) ＞0,那么P(1)存在实数解，否则不存在.
如果c中存在等于0的项,也存在不等于0的项(令F(x)=∑_ci=0g_i(x)²)，而且F(x)不是零多项式，那么,归纳起来,如果F(x)是一个次数大于零的多项式，那么可以根据问题Q(n)的求解公式，判断是否存在实数解.如果F(x)的次数为零次，那么F(x)是一个不为零的常数，此P(1)问题无解.
所以P(1)在条件?ic_i=0∧?ic_i≠0∧∑_ci=0g_i(x)²≠0下，可以在有限步内判断是否存在实数解.
如果?i,c_i≠0，那么问题等价于求解是否存在实数x⁰使得，

$\forall i,{{c}_{i}}\cdot {{g}_{i}}({{x}^{0}})＞0,$

(22)

设c_i·g_i(x)的无平方分部分为h_i(x)，则方程

$\underset{i}{\mathop{\prod }}\,{{h}_{i}}\left( x \right)=0$

可能存在实数根，也可能不存在，分情况讨论.
存在实数根时，设

${{\alpha }_{1}},\ldots ,{{\alpha }_{k}}$

为方程的不同的实根(按从小到大排列).添加记号α₀=-∞,α_k+1=∞,那么?i∈N∧i≥0∧i≤k?j,g_j(x)在区间(α_i,α_i+1)上正负号保持不变.所以如果存在位于(α_i,α_i+1) 的实数x⁰ 满足式(22)要求.那么

$\forall a\in ({{\alpha }_{i}},{{\alpha }_{i+1}}),$

a满足式(22)要求.

$\forall i,j$

如果h_j(α_i) ＞0,那么在α_i 的足够小的邻域内有g_j(x)＞0恒成立;如果h_j(α_i) ＜0,那么在α_i的足够小的邻域内有g_j(x)＜0恒成立;如果h_j(α_i)=0因为h_j(x) 是无平方的，所以$\frac{d{{h}_{j}}\left( x \right)}{dx}\ne 0$.如果$\frac{d{{h}_{j}}\left( x \right)}{dx}>0,$表示h(x)在α_i的右边大于零;如果$\frac{d{{h}_{j}}\left( x \right)}{dx}＜0,$表示h(x)在α_i的左边大于零.
存在满足式(22)要求的实数x⁰，那么x⁰一定位于某个(α_i,α_i+1)之间.当然可能会发生这样的情况α_i=-∞ 或者α_i+1=∞.但是α_i,α_i+1 中至少有一个为实数，设α_i 是实数(另一种情况，可以类似地讨论).所有的g_j(x) 要在实数α_i右边的足够小的邻域内都大于零，根据之前的分析，h_j(α_i) ＞0或者${{h}_{j}}({{\alpha }_{i}})=0\wedge \frac{d{{h}_{i}}({{\alpha }_{i}})}{dx}＞0.$.
如果∏h_i(x)=0在实数域上无解，那么存在实数满足(22)的条件，当且仅当?i,h_i(0) ＞0.
综上所述.存在实数满足(22)要求，当且仅当

$(\forall x\in R\Rightarrow \prod {{h}_{i}}\left( x \right)\ne 0)\wedge (\forall i,{{h}_{i}}\left( 0 \right)＞0),$

(23)

或者 存在一个由大于等于1小于等于m的某些自然数构成的集合A,满足下面要求：

$\exists x\in R\Rightarrow (\forall j\in A\Rightarrow {{g}_{j}}\left( x \right)＞0)\wedge (\forall j\in A\Rightarrow {{g}_{j}}\left( x \right)=0)\wedge (\forall j\in A,k\in A\Rightarrow \frac{d{{g}_{j}}\left( x \right)}{dx}\cdot \frac{d{{g}_{k}}\left( x \right)}{dx}＞0),$

(24)

式(24)可以根据求解问题Q(n)的公式求解，而(23)式可以根据定理1.1判断∏h_i(x)=0有没有解，直接代入判断?i,h_i(0)＞0是否成立即可，所以在?i,c_i≠0 条件下，P(1) 是可以在有限步内解决的.
最后一种情况是

$\exists i,{{c}_{i}}=0\wedge \exists j,{{c}_{j}}\ne 0\wedge \underset{{{c}_{i}}=0}{\mathop{\sum }}\,{{g}_{i}}{{\left( x \right)}^{2}}\equiv 0,$

(25)

这种情况下问题可以转换为P(1)在?i,c_i≠0的条件下的问题，所以也是可以在有限步内解决的.
综上所述，P(1)可以在有限步内得到解决.
3 P(n)可以在有限步内解决定理3.1 假设P(k)是可以在有限步内解决的，那么P(k+1)是可以在有限步内解决的.
证明： P(n)问题的c可能只有等于零的项，可能只有不为零的项，可能既有等于零的项，又有不为零的项.分类讨论.
如果

$\forall i,{{c}_{i}}=0,$

(26)

令

$F({{x}_{1}},{{x}_{2}},\ldots ,{{x}_{k+1}})=\sum {{g}_{i}}{{({{x}_{1}},{{x}_{2}},\ldots ,{{x}_{k+1}})}^{2}},$

那么当且仅当?(x₁⁰,x₂⁰,…,x_k+1⁰)使得F(x₁⁰,x₂⁰,…,x_k+1⁰)=0时，原问题有解.
选择x₁为主变元，如果?(x₁⁰,x₂⁰,…,x_k+1⁰)使得F(x₁⁰,x₂⁰,…,x_k+1⁰)=0,那么对于关于x₁的多项式F(x₁,x₂⁰,…,x_k+1⁰)=0有实数解.要使得关于x₁的多项式F(x₁,x₂⁰,…,x_k+1⁰)=0有实数解，需要满足以下情况中的一种：
如果F(x₁,x₂,…,x_k+1)|_{x2=x2⁰,x3=x3⁰,…,xk+1=xk+1⁰}关于变元x₁的次数为0，那么,

$\forall i\ge 0\Rightarrow coeff(F({{x}_{1}},{{x}_{2}},\ldots ,{{x}_{k+1}}),{{x}_{1}},i)\text{ }{{|}_{x}}_{2}={{x}^{0}}_{2},\ldots ,{{x}_{k+1}}={{x}^{0}}_{k+1}=0$

(27)

coeff(F(x₁,x₂,…,x_k+1),x₁,i) 是关于未定元x₂,x₃,·,x_k+1 的多项式，根据假设，P(k)是可以在有限步内解决的.
计 F(x₁,x₂,…,x_k+1)|_{x2=x2⁰,x3=x3⁰,…,xk+1=x⁰k+1} 关于 x₁ 的次数为d，那么，

$\begin{align} & (\forall i\in N\wedge italic>d\wedge i\le degree(F({{x}_{1}},{{x}_{2}},\ldots ,{{x}_{k+1}}), \\ & {{x}_{1}}))\Rightarrow coeff(F({{x}_{1}},{{x}_{2}},\ldots ,{{x}_{k+1}}),{{x}_{1}},i){{|}_{{{_{x}}_{2}}}}_{={{x}^{0}}_{2},\ldots ,{{x}_{k+1}}={{x}^{0}}_{k+1}}=0) \\ & \wedge (coeff(F({{x}_{1}},{{x}_{2}},{{x}_{3}},\ldots ,{{x}_{k+1}}),{{x}_{1}},d){{|}_{{{_{x}}_{2}}}}_{={{x}^{0}}_{2},\ldots ,{{x}_{k+1}}={{x}^{0}}_{k+1}}\ne \\ & 0)\wedge (number(DiscriminantSequence(trunc(F({{x}_{1}},{{x}_{2}}, \\ & \ldots ,{{x}_{k+1}}),{{x}_{1}},d),{{x}_{1}}){{|}_{x}}_{2}={{x}^{0}}_{2},\ldots ,{{x}_{k+1}}={{x}^{0}}_{k+1})＞0). \\ \end{align}$

(28)

这样就将P(k+1)归约为有限多个P(k)问题.根据假设，P(k)是可以在有限步内解决的.所以P(k+1)在条件(26)的情况下是可以在有限步内解决的.
如果

$\exists i,{{c}_{i}}=0\wedge \exists i,{{c}_{i}}\ne 0\wedge (f\left( x \right):=\underset{{{c}_{i}}=0}{\mathop{\sum }}\,{{g}_{i}}{{\left( x \right)}^{2}}\Rightarrow f\left( x \right)\equiv 0),$

(29)

那么P(k)有解，当且仅当存在实数向量(x₁⁰,x₂⁰,…,x_k+1⁰) 使得

$f({{x}^{0}}_{1},{{x}^{0}}_{2},\ldots ,{{x}^{0}}_{k+1})=0\forall i,{{c}_{i}}\ne 0\Rightarrow {{c}_{i}}\cdot {{g}_{i}}({{x}^{0}}_{1},{{x}^{0}}_{2},\ldots ,{{x}^{0}}_{k+1})>0;$

(30)

如果式(30)存在实数解，当且仅当满足下面情况中的一种：
(x₂⁰,…,x⁰_k+1)使得
f(x₁,x₂,…,x_k+1)|_{x2=x2⁰,…,xk+1=xk=1⁰}是个次数为d的多项式，且d大于等于1.
那么要使得(30)式存在实数解，要求
设

$\begin{align} & number([f({{x}_{1}},{{x}_{2}}\ldots ,{{x}_{n}}),{{g}_{i}}_{1}({{x}_{1}},{{x}_{2}},\ldots ,{{x}_{n}}),\ldots , \\ & {{g}_{i}}_{m}({{x}_{1}},{{x}_{2}},\ldots ,{{x}_{n}})])= \\ & \underset{i=1}{\overset{i={{l}_{q}}_{1}}{\mathop{\sum }}}\,{{a}_{i}}\cdot number(DiscriminantSequence({{h}_{i}}({{x}_{1}},{{x}_{2}},\ldots ,{{x}_{k+1}}),{{h}_{1i}}({{x}_{1}},{{x}_{2}},\ldots ,{{x}_{k+1}}),{{x}_{1}}))+ \\ & \underset{i={{l}_{q}}_{1}+1}{\overset{i={{l}_{q}}_{2}+{{l}_{q1}}}{\mathop{\sum }}}\,{{b}_{i}}\cdot number(DiscriminantSequence({{h}_{i}}({{x}_{1}},{{x}_{2}},\ldots ,{{x}_{k+1}}),{{x}_{1}})), \\ \end{align}$

(31)

c_i中不等于0的项一共有m个，依次计为i₁,i₂,…,i_m. 多项式h_i(x₁,x₂,…,x_k+1),h_1i(x₁,x₂,…,x_k+1)是根据f(x₁,x₂,…,x_k+1)和g_i(x₁,x₂,…,x_k+1)计算出来的多项式.而且只要f(x₁,x₂,…,x_k+1)关于x₁的次数大于等于1，那么所有h_i(x₁,x₂,…,x_k+1) 关于x₁的次数都大于等于1.
为了求解出DiscriminantSequence()，需要对

${{h}_{i}}({{x}_{1}},{{x}_{2}},\ldots ,{{x}_{k+1}})$

的次数分类讨论.
(30)式存在实数解，当且仅当
?i,1≤i≤l_q1+l_q2
?l_i,(l_i∈N)∧(l_i≥1),长度为l_i+1的实数序列cⁱ满足.
存在(x₂⁰,x₃⁰,…,x_k+1⁰)∈N^k使得

$\begin{align} & (\forall j,j>{{l}_{i}},\Rightarrow \\ & coeff({{h}_{i}}({{x}_{1}},{{x}_{2}},\ldots ,{{x}_{k+1}}),{{x}_{1}},j){{|}_{^{{{_{x}}_{2}}}}}_{={{x}^{0}}_{2},\ldots ,{{x}_{k+1}}={{x}^{0}}_{k+1}}= \\ & 0)\wedge (coeff({{h}_{i}}({{x}_{1}},{{x}_{2}},\ldots ,{{x}_{k+1}}),{{x}_{1}},{{l}_{i}}){{|}_{x}}_{2}={{x}^{0}}_{2},\ldots ,{{x}_{k+1}}={{x}^{0}}_{k+1}\ne 0)\wedge \\ & (\underset{i=1}{\overset{i={{l}_{q}}_{1}}{\mathop{\sum }}}\,{{a}_{i}}\cdot number({{{\bar{c}}}^{i}})+\underset{i={{l}_{q}}_{1}+1}{\overset{i={{l}_{q}}_{1}+{{l}_{q}}_{2}}{\mathop{\sum }}}\,number({{{\bar{c}}}^{i}})>0)\wedge \\ & DiscriminantSequence(trunc({{h}_{i}}({{x}_{1}},{{x}_{2}},\ldots ,{{x}_{k+1}}),{{x}_{1}},{{l}_{i}}), \\ & {{x}_{1}}){{|}_{x}}_{2}={{x}^{0}}_{2},{{x}_{3}}={{x}^{0}}_{3},\ldots ,{{x}_{k+1}}={{x}^{0}}_{k+1}的符号表为{{{\bar{c}}}^{i}}. \\ \end{align}$

(32)

求解是否存在(x₂⁰,x₃⁰,…,x_k+1⁰)使得(32)成立的问题，是个P(k) 问题.P(k+1) 可以规约为至多有限个P(k)问题，根据假设，P(k)是可以在有限步内解决的，所以P(k+1)是可以在有限步内解决的.
另一种可能是f(x₁,x₂,…,x_k+1)|_{x2=x2⁰,…,xk+1=xk+1⁰}为一个关于x₁的零次多项式,即要求

$\sum coeff{{(f({{x}_{1}},{{x}_{2}},\ldots ,{{x}_{k+1}}),{{x}_{1}},i)}^{2}}{{|}_{x}}_{2}={{x}^{0}}_{2},\ldots ,{{x}_{k+1}}={{x}^{0}}_{k+1}=0.$

令

${{f}^{1}}({{x}_{2}},\ldots ,{{x}_{k+1}}):=\sum coeff{{(f({{x}_{1}},{{x}_{2}},\ldots ,{{x}_{k+1}}),{{x}_{1}},i)}^{2}},$

由于f(x₁,x₂,…,x_k+1)≠0,所以f¹(x₂,…,x_k+1)≠0. 如果f¹(x₂,…,x_k+1)为常数，那么一定是一个非零的常数.
判断P(k+1)在约束(30)的情况下是否存在实数解的问题，转化为判断

${{f}^{1}}\left( {{x}_{2}},\ldots ,{{x}_{k+1}} \right)=0;\forall i,{{c}_{i}}\ne 0\Rightarrow {{c}_{i}}\cdot {{g}_{i}}({{x}_{1}},{{x}_{2}},\ldots ,{{x}_{k+1}})＞0$

(33)

是否有解.
假设原问题在式(30)条件下不能在有限步内判断，那么f(x₁,x₂,…,x_k+1)|_{x2=x2⁰,…,xk+1=xk+1⁰}关于x₁是零次的.经过转化之后的f¹(x₂,…,x_k+1)|_{x3⁰,…,xk+1=xk+1⁰}关于x₂的次数也为零(否则根据第1种情况下的讨论，可以在有限步内判断是否存在实数解)，经过k+1次转换之后原问题转换成问题

${{f}^{k+1}}=0;\forall i,{{c}_{i}}\ne 0\Rightarrow {{c}_{i}}\cdot {{g}_{i}}({{x}_{1}},{{x}_{2}},\ldots ,{{x}_{k+1}})>0;{{f}^{k+1}}是不为零的常数$

到了这一步可以判断无解.
所以与问题不能在有限步内解决矛盾.
综上所述，P(k+1)在式(30)条件下可以归约为有限多个P(k)问题，所以可以在有限步内解决.

$\forall i,{{c}_{i}}\ne 0,$

(34)

在之前讨论P(1)可在有限步内解决的解法中说到了这种情况，不过在一元多项式的情况下，我采取了简化的解法，这里给出一种复杂却普遍有效的方法：
在实数域上存在实数x₀使得

$\forall i,{{c}_{i}}\cdot {{g}_{i}}({{x}_{0}})＞0;$

(35)

当且仅当存在实数满足：

$\begin{align} & (\forall i,(\exists {{l}_{i}}s.t.(\forall l,{{l}_{i}}\Rightarrow \left( \frac{{{d}^{l}}{{c}_{i}}\cdot {{g}_{i}}\left( x \right)}{d{{x}^{l}}}=0) \right)\wedge (\frac{{{d}^{l}}_{i}{{c}_{i}}\cdot {{g}_{i}}\left( x \right)}{d{{x}^{l}}_{i}\ne 0}))\wedge ({{l}_{i}}\equiv 0(mod2)\Rightarrow \\ & \frac{{{d}^{l}}_{i}{{c}_{i}}\cdot {{g}_{i}}\left( x \right)}{d{{x}^{l}}_{i}}>0)))\wedge (\forall i,j({{l}_{i}}\equiv 1(mod2)\wedge {{l}_{j}}\equiv 1(mod2))\Rightarrow (\frac{{{d}^{l}}_{i}{{c}_{i}}\cdot {{g}_{i}}\left( x \right)}{d{{x}^{{{l}_{i}}}}}\cdot \frac{{{d}^{l}}_{j}{{c}_{j}}\cdot {{g}_{j}}\left( x \right)}{d{{x}^{l}}_{j}}＞0)). \\ \end{align}$

(36)

对于多元多项式的情况，首先要选定主元，然后要讨论多项式对于主元可能的次数.如果(x₁⁰,x₂⁰,…,x_k+1⁰)是原问题的一个解，(x₁,x₂⁰,…,x_k+1⁰) 使得 c_i·g_i(x₁,x₂,…,x_k+1) 关于 x₁ 的次数为 l_i ，那么

$({{x}^{0}}_{1},{{x}^{0}}_{2},\ldots ,{{x}^{0}}_{k+1})$

满足：

$\begin{align} & f\left( {{x}_{1}},{{x}_{2}},\ldots ,{{x}_{k+1}} \right):=\underset{i}{\mathop{\sum }}\,\underset{k>{{l}_{i}}}{\mathop{\sum }}\,coeff{{({{g}_{i}}({{x}_{1}},{{x}_{2}},\ldots ,{{x}_{k+1}}),{{x}_{1}},k)}^{2}}, \\ & coeff({{g}_{i}}({{x}_{1}},{{x}_{2}},\ldots ,{{x}_{k+1}}),{{x}_{1}},{{l}_{i}})\ne 0,trunc({{c}_{i}}\cdot {{g}_{i}}({{x}_{1}},{{x}_{2}},\ldots ,{{x}_{k+1}}),{{x}_{1}},{{l}_{i}})>0, \\ \end{align}$

(37)

如果f(x₁,x₂,…,x_k+1)≠0，那么这就是刚才讨论的P(k+1)在条件(30)时的情况.可以在有限步内解决.
如果f(x₁,x₂,…,x_k+1)≡0那么问题转换为

$coeff({{g}_{i}}({{x}_{1}},{{x}_{2}},\ldots ,{{x}_{k+1}}),{{x}_{1}},degree({{g}_{i}}({{x}_{1}},{{x}_{2}},\ldots ,{{x}_{k+1}}),{{x}_{1}}))\ne 0,{{c}_{i}}\cdot {{g}_{i}}({{x}_{1}},{{x}_{2}},\ldots ,{{x}_{k+1}})＞0.$

(38)

根据公式(36)问题归约为：
是否存在(x₁,x₂,…,x_k+1)使得

$\begin{array}{l}(\forall i,coeff({g_i}({x_1},{x_2}, \ldots ,{x_{k + 1}}),{x_1},\\degree({g_i}({x_1},{x_2}, \ldots ,{x_{k + 1}}),{x_1})) \ne 0) \wedge \\((\forall i,(\exists {l_i}s.t.(\forall l,li \Rightarrow \\\left. {\left( {\frac{{{\partial ^l}{c_i} \cdot {g_i}\left( {{x_1},{x_2}, \ldots ,{x_{k + 1}}} \right)}}{{\partial {x^l}_1}} = 0} \right)} \right)\\\left. { \wedge \left( {\frac{{{\partial ^{{l_i}}}{c_i} \cdot {g_i}\left( {{x_1},{x_2}, \ldots ,{x_{k + 1}}} \right)}}{{\partial {x^{{l_i}}}_1}} \ne 0} \right)} \right) \wedge \\\left( {{l_i} \equiv 0\left( {mod2} \right) \Rightarrow } \right.\\\left. {\left. {\left. {\frac{{{\partial ^{{l_i}}}{c_i} \cdot {g_i}\left( {{x_1},{x_2}, \ldots ,{x_{k + 1}}} \right)}}{{\partial {x^{{l_i}}}_1}} > 0} \right)} \right)} \right) \wedge \\\forall i,j\left( {{l_i} \equiv 1\left( {mod2} \right) \wedge {l_j} \equiv 1\left( {mod2} \right)} \right) \Rightarrow \\\left( {\frac{{{\partial ^{{l_i}}}{c_i} \cdot {g_i}\left( {{x_1},{x_2}, \ldots ,{x_{k + 1}}} \right)}}{{\partial {x^{{l_i}}}_1}}} \right..\\\left. {\left. {\frac{{{\partial ^{{l_j}}}{c_j} \cdot {g_j}\left( {{x_1},{x_2}, \ldots ,{x_{k + 1}}} \right)}}{{\partial {x^{{l_j}}}_1}} > 0} \right)} \right),\end{array}$

(39)

(39)式是个在条件(29)下的问题P(k+1)，可以在有限步内解决.综上所述，如果P(k) 可以在有限步内解决，那么P(k+1) 可以在有限步内解决.
根据数学归纳法，P(n)问题都可以在有限步内解决.
4 结语本文给出算法判定有理系数多项式方程是否存在实数解.与文献^[7]不同，本文根据杨路等人的多项式判别式的方法，不需要将多项式组化成互素的就可以判断多项式方程有没有实数解，而且本文详细介绍了如何将 n变元半代数问题归约为 n-1 变元的半代数问题.综上所述，本文给出了判断有理系数多项式方程是否存在实数解的新的算法.
参考文献

[1]	Cox D A, Little J, O'Shea D. Ideals,varieties,and algorithms[M].NewYork: Springer, 2007.
[2]	陈玉福. 计算机代数讲义[M].北京: 高等教育出版社, 2009.
[3]	王东明, 夏壁灿, 李子明. 计算机代数[M].北京: 清华大学出版社, 2007.
[4]	Yang L. Recent advances on determining the number of real roots of parametric polynomials[J].Journal of Symbolic Computation, 1999, 28(1):225–242.
[5]	Dubé T W. The structure of polynomial ideals and Grobner bases[J].SIAM Journal on Computing, 1990, 19(4):750–773.DOI:10.1137/0219053
[6]	Tarski A. A decision method for elementary algebra and geometry[M].Berkeley: Univ of Calif Press Berkeley, 1951.
[7]	Ben-Or M, Kozen D, Reif J. The complexity of elementary algebra and geometry[J].Journal of Computer and System Sciences, 1984, 32(2):251–264.
[8]	Yang L, Hou X, Xia B. A complete algorithm for automated discovering of a class of inequality-type theorems[J].Science in China Series F Information Sciences, 2001, 44(1):33–49.DOI:10.1007/BF02713938
[9]	Mehlhorn K, Sagraloff M. A deterministic algorithm for isolating real roots of a real polynomial[J].Journal of Symbolic Computation, 2011, 46(1):70–90.DOI:10.1016/j.jsc.2010.09.004
[10]	Cheng J S, Gao X S, Guo L. Root isolation of zero-dimensional polynomial systems with linear univariate representation[J].Journal of Symbolic Computation, 2012, 47(7):843–858.DOI:10.1016/j.jsc.2011.12.011
[11]	Wang D. Automated deduction in geometry[M].Berlin: Springer-Verlag, 1998.
[12]	Yang L, Hou X R, Zeng Z B. A complete discrimination system for polynomials[J].中国科学 E 辑 (英文版), 1996, 6:8.