Testing Positiveness of Polynomials.
Many problems in mathematics, logic, computer science, and engineering can be reduced to the problem of testing positiveness of polynomials (over real numbers). Although the problem is decidable (shown by Tarski in 1930), the general decision methods are not always practically applicable because of their high computational time requirements. Thus several partial methods were proposed in the field of term rewriting systems. In this paper, we exactly determine how partial these methods are, and we propose simpler and/or more efficient methods with the same power.
Introduction
Many problems in mathematics, logic, computer science, and
engineering can be reduced to the problem of testing positiveness
of polynomials. In 1930, Tarski [33, 34] showed that the
problem is decidable. In fact, he gave a decision method for
a more general problem than just testing positiveness. Since
many improvements and new methods were proposed
19, 18, 25, 36, 8, 21, 22, 5, 12, 23].
However, these methods are computationally expensive due
to their generality. Naturally one is interested in devising
more efficient methods for the sub-problem: testing posi-
tiveness. But then, this sub-problem turns out to be still
difficult. Thus, several authors (mainly from the field of
rewriting systems, for proving termination) proposed
some partial methods, partial in the sense that these method
might not be able to decide the positiveness of some polynomials
[24, 4, 10, 10, 31, 32, 11].
In this paper, we determine how much partial these methods
are. In other words, we find proper subsets of the set
of all positive polynomials that are decided by those meth-
ods. Equivalently, we determine restrictions on the positiveness
that are decided by them. Further, we propose simpler
and/or more efficient methods for the same sets of polynomials

The structure of the paper is as follows. In Section 2, we
list three different restrictions on the property of positiveness
(eventual, absolute, eventual absolute). In the subsequent
sections, we show that each of the existing methods is a decision
procedure for one of the above restricted positiveness
properties. We also give several new methods.
Several Types of Positiveness
let P be a non-zero polynomial in
R[x], and let - 2 R.
Definition 2.1 (Types of Positiveness) We say that P is
ffl positive from - iff 8x
eventually positive 1 iff there exists a - such that P is
positive from -.
absolutely positive from - iff P is positive from - and
every partial derivative P   is non-negative from -, that
eventually absolutely positive iff exists a - such that P
is absolutely positive from -. 2
Example 2.1 Let polynomial. The polynomial
P is positive from 0. In fact one sees easily that it
is positive from all - ? \Gamma1. Therefore it is also eventually
positive. However, it is absolutely positive only from - 0
because its second derivative (6x) is non-negative only for
non-negative values of x. As it is absolutely positive from
some - it is also eventually absolutely positive. 2
Example 2.2 Let 1. It is easy to see that
the polynomial P is positive from every - and therefore it
is eventually positive. On the contrary, it is not absolutely
positive from any -, because the derivative
always negative. Consequently it is not eventually absolutely
positive. 2
1 The notion of eventual positiveness was first introduced by Lankford
[24].
Naturally, we are interested in the relations among the
properties. Let P - , EP, AP - , EAP respectively stand for
positiveness from -, eventual positiveness, absolute positiveness
from - and eventual absolute positiveness. The following
proposition shows the relations among them.
Proposition 2.1 The following diagram describes the implication
relation among the different kinds of positiveness prop-
erty. An arrow goes from A to B if A implies B.
@
@
@
@R
\Gamma\Psi
@
@
@
@R
\Gamma\Psi
Proof.
The proofs of all indicated implications follow easily from the
definition. It is equally easy to see that the indicated implications
are the only implications valid for the given properties.
We can use polynomials from Examples 2.1 and 2.2 as counter
examples to other implications. 2
3 Methods for Absolute Positive-
ness
We start with presenting a necessary and sufficient condition
for absolute positiveness of a polynomial. The theorem will
be used in several following subsections and will form a base
for the new method we present later.
From now on, let oe - stand for "shifting" by -. Precisely,
oe - (P ) is the polynomial obtained from P by replacing each x i
with polynomial P can be rewritten
as
e c e x e where the exponent vectors (e) are distinct and
(distributed representation). We will call those c e 's
coefficients of P .
Theorem 3.1 Let P be a non-zero polynomial. Then P is
absolutely positive from - iff every coefficient of the polynomial
oe positive and the constant term is non-zero. 2
Proof.
First note that since P is a non-zero polynomial, oe - (P ) is
also a non-zero polynomial.
Assume that every coefficient of oe - (P ) is positive and the
constant term is non-zero. Then obviously oe - (P ) is positive
from 0. Note that the graph of P is obtained by shifting that
of oe - (P ) by - to the positive direction. Thus the polynomial
P is positive from -.
Let @ be an arbitrary but fixed partial differentiation operator
as @ e 1 +\Delta\Delta\Delta+e n
. Since the polynomial oe - (P ) has all co-efficients
positive, the polynomial @(oe - (P )) also has all coefficients
positive. Therefore @(oe - (P )) is non-negative from 0.
Observing that differentiation and shifting commutes, that is,
we see that oe - (@(P )) is non-negative
from 0. Note again that the graph of @(P ) is obtained by
shifting that of oe - (@(P )) by - to the positive direction. Thus
@(P ) is non-negative from -. Therefore P is absolutely positive
from -.
We can use the same arguments as in the first part of the
proof. The assumption of the polynomial P being absolutely
positive from - is then equivalent to the fact of polynomial
oe being absolutely positive from 0. Therefore we want to
prove that if the polynomial oe - (P ) is absolutely positive from
then it has all coefficients positive and non-zero constant
term. The proof will be done by contradiction.
Assume the constant term of oe - (P ) is zero. Then the value
of oe - (P ) at 0 is 0, contradicting the fact that oe - (P ) is absolutely
positive from 0. Assume there exists a term with
negative coefficient in oe - (P ). Then there exists a derivative 2
of oe - (P ) with a negative constant term (it is the derivative
eliminating all variables of the term with the negative coef-
ficient). The derivative is negative at 0, contradicting the
absolute positiveness of oe - (P ). 2
3.1 Partial Derivative Method
Giesl [11] gave a partial method for testing the positiveness,
by extending the idea of Lankford [24]. The method is based
on the following implications (called differentiation rules):
It might be the 0-th order derivative, that is, the polynomial oe - (P )
itself.
The method, starting from the sentence
repeatedly applies the implications (backward) until it results
in a conjunction of inequalities among numbers. If all those
numeric inequalities are satisfied, then the method outputs
'yes' (P is positive from -). If not, it outputs `don't know'.
Since it is a partial method, a question naturally arises:
How much partial is the method? In other words, we want
to know the proper subset of the set of all positive polynomials
that are decided by the method. As the reader might
have guessed (from the fact we put the method into the section
about absolute positiveness), the method is a decision
procedure for absolute positiveness (Theorem 3.2).
The rest of the subsection is devoted to the proving the
theorem. For this we start with a lemma which will simplify
the proof of the theorem.
Lemma 3.1 The partial derivative method outputs 'yes' on
an input P and - iff it outputs 'yes' on the input oe - (P ) and 0.Proof.
Suppose that by applying Rule-1 on an inequality Q
we generate two new inequalities Q
is easy to see, from the commutativity of shifting and differ-
entiation/evaluation, that by applying the same rule on the
inequality oe - (Q) ? 0, we will generate two new inequalities
The same holds for applying
Rule-2 on Q - 0.
The computation of the partial derivative method on input
ends in a set A of numerical inequalities. Following
the observation above, we easily see that applying the
same computation path on oe - (P ) and 0 results in the set A 0
of numerical inequalities, which are obtained by shifting the
inequalities in A. But then shifting a numerical inequality results
in the same inequality. Thus we conclude that
and so their truths are the same. 2
Now we can prove the exact power of the partial derivative
method.
Theorem 3.2 (Power of Partial Derivative Method)
The partial derivative method outputs 'yes' for an input P
and - iff the polynomial P is absolutely positive from -.
Proof.
Assume the partial derivative method outputs 'yes' on P
and -, it means P is positive from -. From Lemma 3.1 we
know it also outputs 'yes' on oe - (P ) and 0, and oe - (P ) is positive
from 0.
Now we will show, by contradiction, that oe - (P ) has all co-efficients
positive and non-zero constant term. Assume that
the polynomial oe - (P ) has either a negative monomial or constant
term equal to zero.
We start with the case when the constant term is zero.
Then we know oe - (P ) is not positive at 0 and it contradicts
the positiveness of oe - (P ) from 0.
Next we assume that a monomial in oe - (P ) has a negative
coefficient. We would like to show that the partial derivative
method does not prove the positiveness of oe - (P ) from 0. For
this, let us first observe the following. Let Q be a polynomial
in an inequality and let M be a monomial in Q with negative
coefficient. We claim that after applying a rule (Rule-1
or Rule-2) one of the resulting polynomials still contains a
monomial with negative coefficient. To see this, let x i be the
variable on which the rule is applied. Let Q 1 be the polynomial
resulting from substituting 0 into x i in Q and let Q 2
be the polynomial resulting from differentiating Q in x i . Assume
that x i occurs in M . Then the monomial @M
occurs in
since it cannot be canceled by other monomials. Further,
the monomial obviously has a negative coefficient. Assume
that x i does not occur in M . Then M occurs in Q 1 because
there cannot be any cancelation among different monomials
after substituting 0 into x i .
Repeated applications of the rules results in a set of numerical
inequalities. From the observation above we know that
at least one of the inequalities must be of the form a - 0 or
a ? 0 where a ! 0. Thus the partial derivation method does
not output 'yes' for oe - (P ) and 0. Contradiction.
Thus, we showed that oe - (P ) has all coefficients positive
and the constant term is non-zero. From Theorem 3.1 we
conclude that P is absolutely positive from -.
Assume P is absolutely positive from -. From Theorem
3.1 we know that oe - (P ) has all coefficients positive and non-zero
constant term. We will show that the method proves the
positiveness of oe - (P ) from 0.
In the final set of numerical inequalities there is only one
strict inequality (resulting from the application of the first
part of Rule-1). Note that the left hand side of the strict
numerical inequality is the constant term of oe - (P ). Because
the constant term is positive, the strict inequality is true.
All other numerical inequalities are non-strict. Note that the
applications of the rules cannot create a negative term. Thus
all the numbers in the non-strict numerical inequalities are
non-negative. Hence, all non-strict inequalities are true,
We showed that the initial inequality is transformed into a
valid set of numerical inequalities. Thus the partial derivative
method outputs 'yes' for the input oe - (P ) and 0. From Lemma
3.1 we conclude that the method outputs 'yes' also on the
input P and -. 2
3.2 Merging Method
The method was first described by Ben Cherifa and Lescanne
[4]. Steinbach [31, 32] increased the power of the method and
removed some restriction imposed by the original version.
The main idea of this method is deciding the positiveness of
polynomial P by finding a sequence of polynomials
such that
The positiveness of polynomial Pn is checked with the "all
coefficients are positive" rule. Of course this rule decides the
positiveness of a polynomial only from positive -.
The transformation of P i into P i+1 is done in two main
steps. Firstly, a pair of monomials, one having negative
and one positive coefficient are chosen. Secondly, the two
monomials are merged into a new monomial. The procedures
CHOOSE and CHANGE are the essential part of the method
and for a detailed discussion on them we refer to Section 5.3
of [32].
We are again interested in the relation between the method
and the positiveness properties we have defined. Giesl in [11]
proved the following facts regarding the comparison of his
method with the merging methods of Steinbach [32] and Ben
Cherifa and Lescanne [4].
Theorem 3.3 (Power of Merging Method (Giesl 95))
ffl If the merging method can prove a polynomial P to be
positive from -, then the partial derivative method can
do so as well.
ffl If partial derivative method can prove P to be positive
from -, then there exists a - 0 - such that the merging
method can prove P to be positive from - 0 . 2
Giesl also gives an example for the second observation,
where the merging method cannot prove positiveness of P
from - though the partial derivative method does. Therefore
the partial derivative method is stronger than the merging
method.
We see that the merging method besides being a partial
method for deciding positiveness of polynomial also only partially
decides absolute positiveness of polynomial. Naturally
one can be again interested in an exact characterization of
the power of the method. We do not know a simple characterization
for the polynomials positiveness of which is decided
by the merging method and leave it as an open problem.
3.3 Shifting Method (New)
We present a new and simple method for checking absolute
positiveness of polynomial. The method is based on Theorem
3.1 which gives the necessary and sufficient condition
for absolute positiveness. From the theorem the method is
obvious.
1. Shift P by -, that is, compute the polynomial P 0 such
that
2. If all the coefficients of P 0 are positive and the constant
term is non-zero then output 'yes', else output `no'.
Example 3.1 Check if the following polynomial 3 P is absolutely
positive from 2:
We apply the shifting method. For this, we first shift P
by 2,
Next, we find that all the coefficients are positive and the
constant term is non-zero (8), thus we conclude that P is
absolutely positive from 2. 2.
3.4 Comparing the Complexity of the Method

Since all the above methods are of equal testing power, we are
interested in complexity differences. In the following theorem,
we recall the analysis of the merging method by Steinbach [31]
and the analysis of the partial derivate method by Giesl [11].
Then we give the analysis of the shifting method. Below we
assume that every arithmetic operation takes a constant time.
Theorem 3.4 (Computing Times) The computing times
for worst cases are bounded from above as follows:
ffl Partial Derivative Method O(d n ')
ffl Merging Method O(' ' )
Shifting Method O(d n ')
where
n the number of variables,
' the number of monomials,
d the maximum of the degrees in each variable. 2
Proof.
Partial Derivative Method: In [11], Giesl gave the following
derivation: Let T (n; d; ') be the computing time for
an input characterized by n, d and '. First we compute
store the results for the later use. This
3 This polynomial arises from a certain polynomial interpretation of
the term rewrite system for associativity and endomorphism [11].
takes O(d). Let S(n; d; ') be the computing time for the re-
maing part (successive elimination of variables). The elimination
of one variable involves the following: d partial differen-
tiations, where each differentiation takes O('), d evaluations,
where each evaluation takes O('), using the stored values of
the powers of -. Further this process produces (d
polynomials in variables to work on. Thus, we get the
following recurrence formula:
By solving the recurrence formula, we see that S(n; d;
O(d n '): Thus, T (n; d;
Merging Method: Steinbach [31] proved the following bound
where s is the number of the positive monomials and t is
the number of the negative monomials. He then, using the
formula of Stirling(s! aproximates to ( s
2-s), simplified it
to
t, it can be rewritten in terms of ' as
Shifting Method: First, we need to shift each monomial. 4 For
this, we need to shift the power of each variable, that takes
O(d 2 ) for each variable. Then we need to multiply out the
shifted powers, that takes O(d n ). Thus, shifting each monomial
takes O(d shifting all the
monomials takes O(d n '). Next, we need to sum all the shifted
monomials, which takes O(d n '). Thus, all together, the shifting
method takes O(d
These are asymptotic results (with the big O's), and thus
one should be careful not to draw any too definitive conclusion
about their performances on small/moderate size inputs,
which often arise in application domains.
4 Methods for Eventual Absolute
Positiveness
Now we shift our focus to the (known and new) methods for
testing eventual absolute positiveness.
4.1 Partial Derivative Method (eventual
positiveness version)
We have already mentioned the Lankford's method [24] which
was suggested as a partial decision method for eventual pos-
itiveness. Let P be a non-constant polynomial. Then the
4 Actually, there are practically better ways, such as Honer evaluation
or synthetic division, etc. But they do not seem to give a better bound,
thus we will stick to the brute-force way since it easier to analyze.
method is based on a simple fact that if every non-vanishing
first order partial derivative of P is eventually positive then
P is eventually positive. We can apply the same reasoning
on the partial derivatives repeatedly until all polynomials are
numbers. If all of them are positive then the input polynomial
is eventually positive. Otherwise, we don't know.
Since it is a partial method, a question again naturally
arises: How much partial is the method? We will answer this
question by following the similar approach that we already
used in studying the power of the partial methods for testing
positiveness (Section 3).
Lemma 4.1 The partial derivative method (Lankford) outputs
'yes' on an input P iff it outputs `yes' on the input
Proof.
Suppose that by applying differentiation on an inequality
another inequality Q   ? 0 . It is easy to
see, from the commutativity of shifting and differentiation,
that by differentiation in the same variable on the inequality
oe 0, we will generate a new inequality oe - (Q
The computation of the partial derivative method (Lank-
ford) on input P ends in a set A of numerical inequalities.
Following the observation above, we easily see that applying
the same computation path on oe - (P ) results in the set A 0
of numerical inequalities, which are obtained by shifting the
inequalities in A. But then shifting a numerical inequality results
in the same inequality. Thus we conclude that
and so their truths are the same. 2
Now we can prove the exact power of the partial derivative
method (Lankford).
Theorem 4.1 (Power of Partial Derivative Method)
The partial derivative method (Lankford) outputs 'yes' on input
P iff the polynomial P is eventually absolutely positive.
Proof.
Assume that the partial derivative method outputs 'yes' on
an input P. We need to show that P is eventually absolutely
positive. From the assumption, we know that P is eventually
positive. Therefore there exists a - 0 such that P is positive
from - 0 . Further from the details of the execution of
the partial derivative method, we observe that every partial
derivative of P is either a zero polynomial or eventually posi-
tive. Thus for every non-zero partial derivative P   of P , there
exists a -   such that P   is positive (thus non-negative) from
-   . Now let - be the maximum of - 0 and all -   's. Then, P is
absolutely positive from -. Thus, P is eventually absolutely
positive.
Assume that the polynomialP is eventually absolutely pos-
itive. We need to show that the partial derivative method
outputs 'yes' on this input. Since P is eventually absolutely
positive, there exists - such that P is absolutely positive
from -. Then, oe - (P ) is absolutely positive from 0: By Theorem
3.1, we see that all coefficients of oe - (P ) are positive and
the constant term is non-zero. Note that the partial derivative
method does not introduce negative terms during the
execution on the input oe - (P ). Thus, the method will output
'yes' on the input oe - (P ). By Lemma 4.1, we conclude that
the method will also output 'yes' on the input P . 2
4.2 Dominating Monomials Method (New)
Now we propose a new and more efficient method for testing
eventual absolute positiveness of polynomial. First note that
the eventual (absolute) positiveness of a univariate polynomial
can be trivially decided by checking whether its leading
coefficient is positive. We generalize the observation to multivariate
case. For this, the notion of leading monomial must
be generalized. The new method is essentially based on one
such generalization (which we call dominating monomial).
Definition 4.1 (Dominating monomial) We say that a
monomial s dominates a monomial m. iff m divides s and m
is different from s. We say that s is a dominating monomial
of P iff there is no monomial in P dominating s. 2
Example 4.1 Let us consider polynomials
There are three dominating
monomials in P there are two in Q
univariate polynomials there is only one dominating
monomial - the leading monomial. 2
Now we are ready to describe the new method:
1. Collect all the dominating monomials of P .
2. If their coefficients are all positive, then output 'yes', else
output 'no'.
The proof of the correctness of the method will be given later
(Theorem 4.2). Let us first get familiar with the method by
working on several small examples.
Example 4.2 Check if the following polynomial is eventually
absolutely positive:
One sees immediately that the only dominating monomial is
xyz. Since its coefficient is positive, the polynomial is eventually
absolutely positive.
Let us try another:
One sees that the dominating monomials are x 4 , 2xy 3 and
y. Since their coefficients are positive, the polynomial is
eventually absolutely positive.
Let us try still another (obtained by changing signs in the
previous example),
Again, the dominating monomials are x 4 , \Gamma2xy 3 and 3x 2 y.
Since one coefficient is negative, the polynomial is not eventually
absolutely positive. 2
Remark: Note that one can use the dominating monomial
method as a quick pre-pruning method while testing absolute
positiveness: Suppose that we would like to check whether a
polynomialP is absolutely positive from -. We first apply the
(very cheap) dominating monomial method. If it turns out
that P is not eventually absolutely positive, then we do not
need to carry out the more expensive absolute positiveness
check, since we already know that the answer is 'no'. 2
The remaining of this section is devoted to proving the correctness
of the dominating monomial method (Theorem 4.2).
We begin with a lemma which "justifies" the notion of dominating
monomial.
Lemma 4.2 The set of dominating monomials of P and that
of oe - (P ) are the same. 2
Proof.
Let m be a dominating monomial of P . We need to show
that m is a dominating monomial of oe - (P ). We prove it by
contradiction. Assume that m is not a dominating monomial
of oe - (P ). There are two cases:
ffl m is not a monomial of oe - (P )
ffl m is a monomial of oe - (P ), but not dominating.
Case 1: m is not a monomial of oe - (P ).
Note that m is a monomial of oe - (m). Since m is not a monomial
in the oe - (P ), there must be a monomial q (different
from m) in P such that there is a monomial q 0 of oe - (q), that
has the same degree vector as m. Every monomial of oe - (q)
divides q, in particular, q 0 divides q. Since m and q 0 have the
same degree vector, m divides q. Recall that m is different
from q, thus q dominates m. Therefore m is not a dominating
monomial of P . Contradiction.
Case 2: m is a monomial of oe - (P ), but not dominating.
Thus there is a monomial q 0 in oe - (P ) that dominates m.
Hence there is a monomial q of P such that there is a monomial
q   of oe - (q), that has the same degree vector as q 0 . Every
monomial of oe - (q) divides q, in particular, q   divides q. Since
q 0 and q   have the same degree vector, q 0 divides q. Recall
that q 0 dominates m. Thus m divides q 0 and they are differ-
ent. Since q 0 divides q, we see that m divides q and they are
different. Thus q dominates m, and m is not a dominating
monomial of P . Contradiction.
Thus m must be a dominating monomial of oe - (P ).
Let m be a dominating monomial of oe - (P ). We need to show
that m is a dominating monomial of P . This can be done in
the exactly same way as before, since
The following theorem relates the notions of eventual absolute
positiveness and dominating monomials, proving the
correctness of the dominating monomial method.
Theorem 4.2 A polynomial P is eventually absolutely positive
iff the coefficients of all dominating monomials of P are
positive. 2
Proof.
Assume that P is eventually absolutely positive. We show
that the coefficients of all dominating monomials are positive.
From eventual absolute positiveness of P we know that
there exists a - such that P is absolutely positive from -.
From Theorem 3.1 we know that oe - (P ) must have all coefficients
positive and non-zero constant term. Therefore also all
coefficients of the dominating monomials of oe - (P ) are posi-
tive. By Lemma 4.2, the set of all dominating monomials of P
is the same as that of oe - (P ). Thus all dominating monomials
of P have positive coefficients.
Assume that the coefficients of all dominating monomials
of P are positive. We need to prove that P is eventually
absolutely positive.
We begin by taking care of a trivial case where all other
(non-dominating) monomials of the polynomial P also have
positive coefficients. It is easily seen, that such a polynomial
is absolutely positive from any - ? 0 and therefore eventually
absolutely positive.
Therefore assume that there exists at least one monomial
with negative coefficient (negative monomial) in P . We partition
the polynomial P into a sum of several sub-polynomials
such that one of the sub-polynomials consists of all positive
non-dominating monomials of P and that each of the remaining
sub-polynomials consists of exactly one dominatingmono-
mial of P (which we will call the leading monomial) and some
(possible none) monomials dominated by the leading monomial
(thus, these monomials are all negative.)
Obviously, if each sub-polynomial is eventually absolutely
positive, so is P . Thus, from now on, we will show that each
sub-polynomial is eventually absolutely positive. Let Q be
one of sub-polynomials.
If Q consists of only positive monomials, it is absolutely
positive from any - ? 0 and therefore eventually absolutely
positive. Thus, from now on assume that Q has at least one
negative monomial.
First we will prove that Q is eventually positive. Let
We claim that Q is positive
from - 5 . To see this, first recall that x m dominates x e i for
every i. Hence, we see immediately that for every i and for
every x -,
a
ab
a
Thus, we see that for every x -, Q
Q is eventually positive.
It remains to show that for every partial derivative Q   of
there exists a -   such that Q   is non-negative from -   .
It is obvious that every vanishing derivative is non-negative
from any -. Thus from now on let Q   be a non-vanishing
partial derivative of the polynomial Q. Note that Q   again
consists of a positive leading monomial (a derivative of the
leading monomial of Q) and some (possibly none) negative
monomials dominated by the leading monomial. Thus, by
applying the idea used for showing the eventual positiveness
of Q, we see that there exists a -   such that Q   is positive
from -   and therefore it is also non-negative from -   . As
there are only finitely many derivatives, we can take -m the
maximum of the bound for positiveness of the polynomial Q
and the bounds for non-negativeness of its derivatives. Then
the polynomial Q is absolutely positive from -m . Thus Q
is eventually absolutely positive. We showed that every sub-
polynomial of P is eventually absolutely positive. Therefore
P is also eventually absolutely positive. 2
4.3 Comparing the Complexity of the Method

We know that the partial derivative method (Lankford) and
the dominating monomial method have the same power.
The following theorem compares their asymptotic complexity
bounds.
Theorem 4.3 (Computing Times) The computing times
for worst cases are bounded from above as follows:
ffl Partial Derivative Method (Lankford) O(d n ')
Dominating Monomial Method O(n' log ')
where
n the number of variables,
' the number of monomials,
d the maximum of the degrees in each variable. 2
Proof.
5 Actually, one can find a much smaller value for - than the one
given here. But here we are only interested in proving the existence of
a bound, and thus any bound suffices.
The bound for the partial derivative method is immediate
from the fact that the method performs up to d n differentiations
of polynomials, where each differentiation takes O(').
The bound for the dominating monomial method is immediate
from the number of comparisons needed for sorting the
monomials according to the partial order defined by the domination
property, where each comparison takes O(n). 2
Conclusions
Several results were presented in the paper. We determined
how much partial the several known methods are for testing
positiveness of polynomials. After that we proposed simpler
and/or more efficient methods with equal power.
There are several directions for the future work. Regarding
the shifting method, one can use more sophisticated methods
for the shifting. For example, the number of monomials
necessary to be shifted can be significantly reduced by exploiting
the structure of the polynomial (not all monomials
have to be shifted, the shifting can be stopped after no negative
monomials can be generated, summing new monomials
need not be done for only positive monomials etc). Also, it
will be interesting/important to find out experimentally how
the new methods (shifting, dominating monomial) behave on
small/moderate size inputs.



--R

Algorithms for the Geometry of Semi-Algebraic Sets
Cylindrical algebraic decomposition II: An adjacency algorithm for the plane.
An adjacency algorithm for cylindrical algebraic decompositions of three-dimensional space
Termination of rewriting systems by polynomial interpretations and its implementation.
Simplification of Truth Invariant CAD's and Solution Formula Construction.
Improved algorithms for sign and existential quantifier elimination.
Quantifier elimination for the elementary theory of real closed fields by cylindrical algebraic decomposition.
Quantifier elimination by cylindrical algebraic decomposition - 20 years of progress
Partial cylindrical algebraic decomposition for quantifier elimination.
Termination of rewriting.
Generating polynomial orderings for termination proofs.
A combinatorial algorithm solving some quantiifier elimination problems.
The complexity of deciding Tarski algebra.
On the complexity of semialgebraic sets.
An improvement of the projection operator in cylindrical algebraic decomposition.
Improvements in CAD-based Quantifier Elim- ination
Simple solution formula construction in cylindrical algebraic decomposition based quantifier elimina- tion
Heuristic search and pruning in polynomial constraint satisfaction.
Parallelization of quantifier elimination on a workstation network.
Quantifier elimination for formulas constrained by quadratic equations via slope resultants.
Approximate quantifier elimination.
Generic quantifier elimination.
Approximate Quantifier Elimination.
A finite termination algorithm.
Applying linear quantifier elimination.
An Improved Projection Operator for Cylindrical Algebraic Decomposition.
An improved projection operator for cylindrical algebraic decomposition.
Solving polynomial strict inequalities using cylindrical algebraic decomposition.
On the computational complexity and geometry of the first-order theory of the reals
A parallel implementation of the cylindrical algebraic decomposition algorithm.
Proving Polynomials Positive.
Termination of rewriting.
The completness of elementary algebra and geometry.
A Decision Method for Elementary Algebra and Geometry.
The complexity of linear problems in fields.
Quantifier elimination for real algebra - the cubic case
--TR

--CTR
Salvador Lucas, Practical use of polynomials over the reals in proofs of termination, Proceedings of the 9th ACM SIGPLAN international symposium on Principles and practice of declarative programming, July 14-16, 2007, Wroclaw, Poland
Jrgen Giesl , Aart Middeldorp, Transformation techniques for context-sensitive rewrite systems, Journal of Functional Programming, v.14 n.4, p.379-427, July 2004
Jrgen Giesl , Ren Thiemann , Peter Schneider-Kamp , Stephan Falke, Mechanizing and Improving Dependency Pairs, Journal of Automated Reasoning, v.37 n.3, p.155-203, October   2006
Nao Hirokawa , Aart Middeldorp, Tyrolean termination tool: Techniques and features, Information and Computation, v.205 n.4, p.474-511, April, 2007
termination proofs;positiveness of polynomials;term rewrite systems