Below, we summarize some new developments in the area of distribution of roots and signs of real univariate polynomials pioneered by R. Descartes in the middle of the seventeenth century.
- real univariate polynomial
- sign pattern
- admissible pair
- Descartes’ rule of signs
- Rolle’s theorem
2010 Mathematics Subject Classication: Primary 26C10; Secondary 30C15
The classical Descartes’ rule of signs claims that the number of positive roots of a real univariate polynomial is bounded by the number of sign changes in the sequence of its coefficients and it coincides with the latter number modulo . It was published in French (instead of the usual at that time Latin) as a small portion of Sur la construction de problèmes solides ou plus que solide which is the third book of Descartes’ fundamental treatise La Géométrie which, in its turn, is an appendix to his famous Discours de la méthode. It is in the latter chef d’oeuvre that Descartes developed his analytic approach to geometric problems leaving practically all proofs and details to an interested reader. This interested reader turned out to be Frans van Schooten, a professor of mathematics at Leiden who together with his students undertook a tedious work of making Descartes’ writings understandable, translating and publishing them in the proper language, that is, Latin. (For the electronic version of this book, see .) Mathematical achievements of Descartes form a small fraction of his overall scientific and philosophical legacy, and Descartes’ rule of signs is a small but important fraction of his mathematical heritage.
Descartes’ rule of signs has been studied and generalized by many authors over the years; one of the earliest can be found in , see also [4, 11]. (For some recent contributions, see [1, 2, 6, 10, 12, 14], to mention a few.)
In the present survey, we summarize a relatively new development in this area which, to the best of our knowledge, was initiated only in the 1990s (see ).
For simplicity, we consider below only real univariate polynomials with all nonvanishing coefficients. For a polynomial with fixed signs of its coefficients, Descartes’ rule of signs tells us what possible values the number of its real positive roots can have. For as above, we define the sequence of signs of length which we call the sign pattern (SP for short) of , namely, we say that a polynomial with all nonvanishing coefficients defines the sign pattern , , , if . Since the roots of the polynomials and are the same, we can, without loss of generality, assume that the first sign of a SP is always a .
It is true that for a given SP with sign changes (and hence with sign preservations), there always exist polynomials defining this sign pattern and having exactly positive roots, where if is even and if is odd (see, e.g., [1, 3]). (Observe that we do not impose any restriction on the number of negative roots of these polynomials.)
One can apply Descartes’ rule of signs to the polynomial which has sign changes and sign preservations in the sequence of its coefficients and whose leading coefficient is positive. The roots of are obtained from the roots of by changing their sign. Applying the above result of  to , one obtains the existence of polynomials with exactly negative roots, where if is even and if is odd. (Here again we impose no requirement on the number of positive roots.)
A natural question apparently for the first time raised in  is whether one can freely combine these two results about the numbers of positive and negative roots. Namely, given a SP with sign changes and sign preservations, we define its admissible pair (AP for short) as , where , , and the differences and are even. For the SP as above, we call the Descartes’ pair of . The main question under consideration in this paper is as follows.
Problem 1. Given a couple (SP, AP), does there exist a polynomial of degree with this SP and having exactly positive and exactly negative roots (and hence exactly complex conjugate pairs)?
If such a polynomial exists, then we say that it realizes a given couple (SP, AP). The present paper discusses the current status of knowledge in this realization problem.
Example 1. For and for the sign pattern , the following pairs and only them are admissible: , , , and . The first of them is the Descartes’ pair of .
It is clear that if a couple (SP, AP) is realizable, then it can be realized by a polynomial with all simple roots, because the property of having nonvanishing coefficients is preserved under small perturbations of the roots.
In this short survey, we present what is currently known about Problem 1. After the pioneering observations of Grabiner  which started this line of research, important contributions to Problem 1 have been made by Albouy and Fu  who, in particular, described all non-realizable combinations of the numbers of positive and negative roots and respective sign patterns up to degree . Our results on this topic which we summarize below can be found in [5, 8, 9] and [15, 16, 17, 18, 19]. On the other hand, we find it surprising that such a natural classical question has not deserved any attention in the past, and we hope that this survey will help to change the situation. The current status of Problem 1 is not very satisfactory in spite of the complete results in degrees up to as well as several series of non-realizable cases in all degrees. There is still no general conjecture describing all non-realizable cases. It might happen that the answer to Problem 1 in sufficiently high degrees is very complicated.
On the other hand, besides Problem 1 as it is stated, there is a significant number of related basic questions which can be posed in connection to the latter Problem and are still waiting for their researchers. (Very few of them are listed in Section 5.)
One should also add that there is a number of completely different directions in which mathematicians are trying to extend Descartes’ rule of signs. They include, for example, rule of signs for other univariate analytic functions including exponential functions, trigonometric functions and orthogonal polynomials, multivariate Descartes’ rule of signs, tropical rule of signs, rule of signs in the complex domain, etc. (see, e.g., [6, 10, 14]) and references therein. But we think that Problem 1 is the closest one to the original investigations by Descartes himself.
The structure of this chapter is as follows. In Section 2, we provide the information about the solution of Problem 1 in degrees up to 11. In Section 3, we present several infinite series of non-realizable couples (SP, AP). Finally, in Section 4 we discuss two generalizations of Problem 1 and their partial solutions.
2. Solution of the realization problem 1 in small degrees
2.1 Natural -action and degrees , , and
Let us start with the following useful observation.
To shorten the list of cases (SP, AP) under consideration, we can use the following -action whose first generator acts by.
and the second one acts by
Obviously, the first generator exchanges the components of the AP. Concerning the second generator, to obtain the SP defined by the polynomial , one has to read the SP defined by backward. The roots of are the reciprocals of these of which implies that both polynomials have the same numbers of positive and negative roots. Therefore, the SPs which they define have the same AP.
Remark 1. A priori the length of an orbit of any -action could be , , or , but for the above action, orbits of length do not exist since the second components of the SPs defined by the polynomials and are always different. When an orbit of length occurs and is even, then both SPs are symmetric w.r.t. their middle points (hence their last component equal ). Similarly, when is odd, then one of the two SPs is symmetric w.r.t. its middle (with the last component equal to ), and the other one is antisymmetric. Thus, its last components equal .
It is obvious that all pairs or quadruples (SP, AP) constituting a given orbit are simultaneously (non-)realizable.
As a warm-up exercise, let us consider degrees and . In these cases, the answer to Problem 1 is positive. We give the list of SPs, with the respective values and of their APs and examples of polynomials realizing the couples (SP, AP). In order to shorten the list, we consider only SPs beginning with two signs; the cases when these signs are are realized by the respective polynomials . All quadratic factors in the table below have no real roots.
Example 2. For , an example of an orbit of length is given by the couples
Here, both SPs are symmetric w.r.t. its middle.
For , such an example is given by the couples
The first of the SPs is symmetric, and the second one is antisymmetric w.r.t. their middles.
Finally, for , the following four couples (SP, AP)
constitute one orbit for . In this example all admissible pairs are Descartes’ pairs.
It turns out that for , it is no longer true that all couples (SP, AP) are realizable by polynomials of degree . Namely, the following result can be found in :
Theorem 1. The only couples (SP, AP) which are non-realizable by univariate polynomials of degree are
It is clear that these two cases constitute one orbit of the -action of length (the SPs are the same when read the usual way and backward).
Proof. The argument showing non-realizability in Theorem 1 is easy. Namely, if a polynomial
realizes the second of these couples and has two positive roots and no negative roots, then for any , the values of the monomials , , and are the same at and , while the monomials and are positive at and negative at . Hence, . As and , the polynomial has two negative roots as well—a contradiction.
For , realizability of all other couples (SP, AP) can be proven by producing explicit examples.
Remark 2. In  a geometric illustration of the non-realizability of the two cases mentioned in Theorem 1 is proposed. Namely, one considers the family of polynomials and the discriminant set
where Res is the resultant of the polynomials and . The hypersurface partitions into three open domains, in which the polynomial has , , or complex conjugate pairs of roots, respectively. These domains intersect the open orthants of defined by the coordinate system , and in each of these intersections, the polynomial has one and the same number of positive, negative, and complex roots, as well as the same signs of its coefficients. The non-realizability of the couple can be interpreted as the fact that the corresponding intersection is empty. Pictures of discriminant sets allow to construct easily the numerical examples mentioned in the proof of Theorem 1.
It remains to be noticed that for and , the polynomials and have one and the same numbers of positive, negative, and complex roots. Therefore, it suffices to consider the family of polynomials in order to cover all SPs beginning with . The ones beginning with will be covered by the family .
For degrees and , the following result can be found in .
Theorem 2. (1) The only two couples (SP, AP) which are non-realizable by univariate polynomials of degree are:
(2) For degree , up to the above -action, the only non-realizable couples (SP, AP) are:
The two cases of Part (1) of Theorem 2 also form an orbit of the -action of length . Each of the first two cases of Part (2) defines an orbit of length , while each of the last two cases defines an orbit of length .
For , the following theorem is contained in .
Theorem 3. For univariate polynomials of degree , among their 1472 possible couples (SP, AP) (up to the -action), exactly the following are non-realizable:
The lengths of the respective orbits in these cases are , , , , , and .
Theorem 4. For degree , among the 3648 possible couples (SP, AP) (up to the -action), exactly the following are non-realizable:
The lengths of the respective orbits are , , , , , , , , , , , , , , , , , , and .
Remark 3. As we see above, for , , , , and , up to the -action, the numbers of non-realizable cases are , , , , and , respectively. The fact that these numbers increase more when and than when and could be related to the fact that the maximal possible number of complex conjugate pairs of roots of a real univariate degree polynomial is . This number increases w.r.t. when is even and does not increase when is odd.
Observe that for , all examples of couples (SP, AP) which are non-realizable are with APs of the form or and . Initially, we thought that this is always the case. However, recently it was proven that, for higher degrees, this fact is no longer true (see ):
Theorem 5. For , the following couple (SP, AP)
is non-realizable. The Descartes’ pair in this case equals .
There is a strong evidence that for , the similar couple (SP, AP)
is also non-realizable. (Its Descartes’ pair equals .) If this were true, then would be the smallest degree with an example of a non-realizable couple (SP, AP) for which both components of the AP are nonzero. When studying the cases and (see  and ), discriminant sets have been considered (see Remark 2).
Summarizing the above, we have to admit that the information in low degrees available at the moment does not allow us to formulate a consistent conjecture describing all non-realizable couples in an arbitrary degree which we could consider as sufficiently well motivated.
3. Series of examples of (non-)realizable couples (SP, AP)
In this section we present a series of couples (non-)realizable for infinitely many degrees. We decided to include those proofs of the statements formulated below which are short and instructive.
3.1 Some examples of realizability and a concatenation lemma
Our first examples of realizability deal with polynomials with the minimal possible number of real roots:
Proposition 1. For even, any SP whose last component is a (resp. is a ) is realizable with the AP (resp. ). For odd, any SP whose last component is a (resp. is a ) is realizable with the AP (resp. ).
Proof. Indeed, for any given SP, it suffices to choose any polynomial defining this SP and to increase (resp. decrease) its constant term sufficiently much if the latter is positive (resp. negative). The resulting polynomial will have the required number of real roots.□
Our next example deals with hyperbolic polynomials, that is, real polynomials with all real roots. Several topics concerning hyperbolic polynomials are developed in .
Proposition 2. Any SP is realizable with its Descartes’ pair.
Proposition 2 will follow from the following concatenation lemma whose proof can be found in .
Lemma 1. Suppose that monic polynomials and , of degrees and resp., realize the SPs and , where are the SPs defined by in which the first is deleted. Then:
If the last position of is a , then for any small enough, the polynomial realizes the SP and the AP .
If the last position of is a , then for any small enough, the polynomial realizes the SP and the AP (Here is the SP obtained from by changing each by a and vice versa.)
The concatenation lemma allows to deduce the realizability of couples (SP, AP) with higher values of from that of couples with smaller in which cases explicit constructions are usually easier to obtain. On the other hand, non-realizability of special cases cannot be concluded using this lemma.
Example 3. Denote by the last entry of the SP . We consider the cases
When then one has, respectively,
and the SP of equals
When then one has, respectively,
and the SP of equals
Proof of Proposition 2. We will use induction on the degree of the polynomial. For , the SP (resp. ) is realizable with the AP (resp. ) by the polynomial (resp. ).
For , we apply Lemma 1. Set and . Then, for small enough, the polynomials
define the SPs and , respectively, and realize them with the AP . In the same way, one can concatenate (resp. ) with itself to realize the SP with the AP (resp. the SP with the AP ). These are all possible cases of monic hyperbolic degree polynomials with nonvanishing coefficients.
For , in order to realize a SP with its Descartes’ pair , we represent in the form , where and are the last two components of and is the SP obtained from by deleting and . Then, we choose to be a monic polynomial realizing the SP :
With the AP , and we set , if .
With the AP , and we set , if . □
Proposition 3. Consider a sign pattern with sign changes, consisting of consecutive pluses followed by consecutive minuses and then by consecutive pluses, where Then:
For the pair this sign pattern is not realizable ifE3
The sign pattern is realizable with any pair of the form , except in the case when and are even, (hence is even), and .
Certain results about realizability are formulated in terms of the ratios between the quantities , , and . The following proposition is proven in .
Proposition 4. For a given couple (SP, AP), if , then this couple is realizable.
3.2 The even and the odd series
Suppose that the degree is even. Then, the following result holds (see Proposition 4 in ):
Proposition 5. Consider the SPs satisfying the following three conditions:
Their last entry (i.e., the sign of the constant term) is a .
The signs of all odd monomials are .
Among the remaining signs of even monomials, there are exactly signs (at arbitrary positions).
Then, for any such SP, the APs , and only they, are non-realizable.
Suppose now that the degree is odd. For , denote by the SP beginning with two pluses followed by pairs and then by minuses. Its Descartes’ pair of equals . The following proposition is proven in .
Theorem 6. (1) The SP is not realizable with any of the pairs ; (2) The SP is realizable with the pair ; (3) The SP is realizable with any of the APs , , and .
One can observe that Cases (1), (2), and (3) exhaust all possible APs .
4. Similar realization problems
In this section, we consider realization problems similar or motivated by Problem 1. A priori it is hard to tell which of these or similar problems might have a reasonable answer.
Consider a real polynomial of degree and its derivative. By Rolle’s theorem, if has exactly real roots (counted with multiplicity), then the derivative has real roots (counted with multiplicity), where . It is possible that has more real roots than . For example, for and , one gets which has a real root at , while has no real roots at all. For , the polynomial has one negative root and one complex conjugate pair, while its derivative has one positive and one negative root.
Now, for , , and , denote by and the numbers of real roots and complex conjugate pairs of roots of the polynomial (both counted with multiplicity). These numbers satisfy the conditions
Definition 1. A sequence satisfying conditions (4) will be called a -sequence of length . We say that a given -sequence of length is realizable if there exists a real polynomial of degree with this -sequence, where for , all roots of are distinct.
Example 4. One has and . Clearly, one has either , or , . For small values of , one has the following -sequences and respective polynomials realizing them:
The following question where a positive answer to which can be found in  seems very natural.
Problem 2. Is it true that for any , any -sequence is realizable?
4.2 Sequences of admissible pairs
Now, we are going to formulate a problem which is a refinement of both Problems 1 and 2.
Recall that for a real polynomial of degree , the signs of its coefficients define the sign patterns corresponding to and to all its derivatives of order since the SP is obtained from by deleting the last component. We denote by and the Descartes’ and admissible pairs for the SPs . The following restrictions follow from Rolle’s theorem:
It is always true that
Definition 2. Given a sign pattern of length , suppose that for , the pair satisfies the conditions
as well as the inequalities (5)–(6). Then, we say that
is a sequence of admissible pairs (SAPs). In other words, it is a sequence of pairs admissible for the sign pattern in the sense of these conditions. We say that a given couple (SP, SAP) is realizable if there exists a polynomial whose coefficients have signs given by the SP , and such that for , the polynomial has exactly positive and negative roots, all of them being simple. Complex roots are also supposed to be distinct.
Remark 4. If one only knows the SAP , the SP can be restituted by the formula
Nevertheless, in order to make comparisons with Problem 1 more easily, we consider couples (SP, SAP) instead of just SAPs. But for a given SP, there are, in general, several possible SAPs which is illustrated by the following example.
Example 5. Consider the SP of length with all pluses. For and , there are, respectively, two and three possible SAPs:
For , the numbers of SAPs compatible with the SP of length having all pluses are
respectively. One can show that , if is even, and , if is odd (see ).
Example 6. There are two couples (SP, SAP) corresponding to the couple (SP, AP) , ; we also say that the couple can be extended into these couples (SP, SAP). These are
Indeed, by Rolle’s theorem, the derivative of a polynomial realizing the couple has at least one negative root. By conditions (7), this derivative (whose degree equals 3) has an even number of positive roots. This yields just two possibilities for , namely, and . The second derivative is a quadratic polynomial with positive leading coefficient and negative constant term. Hence, it has a positive and a negative root. The realizability of the above two couples (SP, SAP) is proven in .
Our final realization problem is as follows:
Problem 3. For a given degree , which couples (SP, SAP) are realizable?
Remarks 1. (1) This problem is a refinement of Problem 1, because one considers the APs of the derivatives of all orders and not just the one of the polynomial itself (see Remark 4). Therefore, if a given couple (SP, AP) is non-realizable, then all couples (SP, SAP) corresponding to it in the sense of Example 6 are automatically non-realizable.
(2) Obviously, Problem 3 is a refinement of Problem 2—in the latter case, one does not take into account the signs of the real roots of the polynomial and its derivatives.
(3) When we deal with couples (SP, SAP), we can use the -action defined by (1). Therefore, it suffices to consider the cases of SPs beginning with . The generator (2.2) of the -action cannot be used, because when the derivatives of a polynomial are involved, the polynomial loses its last coefficients. Due to this circumstance, the two ends of the SP cannot be treated equally.
The following proposition is proven in :
Proposition 6. For any given SP of length and , there exists a unique SAP such that . This SAP is realizable. For the given SP, this pair is its Descartes’ pair.
Example 7. For even , consider the SP with all pluses. Any hyperbolic polynomial with all negative and distinct roots realizes this SP with SAP
One can choose such a polynomial with all distinct critical values. Hence, in the family of polynomials and , one encounters polynomials realizing this SP with any of the SAPs
In the same way, for odd , the SP is realizable with the SAP
by some hyperbolic polynomial with all distinct roots and critical values. In the family of polynomials and , one encounters polynomials realizing this SP with any of the SAPs
For , the following exhaustive answer to Problem 3 is given in :
A. For , , and , all couples (SP, SAP) are realizable.
B. For , the couple (SP, SAP)
and only it (up to the -action), is non-realizable. Its non-realizability follows from one of the couples (SP, AP) (see Theorem 1).
One can observe that the couple can be uniquely extended into a couple (SP, SAP). Indeed, the first derivative has a positive constant term hence an even number of positive roots. This number is positive by Rolle’s theorem. Hence, the AP of the first derivative is . In the same way, one obtains the APs and for the second and third derivatives, respectively.
C. For , the following couples (SP, SAP), and only they, are non-realizable:
The non-realizability of the first four of them follows from that of the couple . The last one is implied by part (1) of Theorem 2; it is true that the couple (SP, AP) extends in a unique way into a couple (SP, SAP), and this is the fifth of the five such couples cited above.
One of the methods used in the study of couples (SP, AP) or (SP, SAP) is the explicit construction of polynomials with multiple roots which define a given SP. Such constructions are not difficult to carry out because one has to use families of polynomials with fewer parameters. Once a polynomial with multiple roots is constructed, one has to justify the possibility to deform it continuously into a nearby polynomial with all distinct roots. Multiple roots can give rise to complex conjugate pairs of roots. An example of such a construction is the following lemma from .
Lemma 2. Consider the polynomials and and . Their coefficients of are positive if and only if, respectively, and . The coefficients of the polynomial define the SP
The coefficients of define the SP
Our first open question deals with the limit of the ratio between the quantities of all realizable and of all possible cases of couples (SP, AP) as . In principle, one does not have to take into account the -action in order not to face the problem of the two different possible lengths of orbits (and ).
A priori, for , one has . It would be interesting to find out whether this ratio has a limit as and, if “yes,” whether this limit is and or belongs to . In the latter case, it would be interesting to find the exact value.
A less ambitious open problem is to find an interval to which this ratio belongs for any , , or at least for sufficiently large.
A related problem would be to find sufficient conditions for realizability based on the ratios between the quantities , , and . On the one hand, when the ratios and are both large enough, one has realizability (see Proposition 4). On the other hand, in all examples of non-realizability known up to now, one of the quantities and is either or is very small compared to the other one. Thus, it would be interesting to understand the role of these ratios for the (non)-realizability of the couples (SP, AP).
Our third open question is about the realizability of couples (SP, SAP). For , the non-realizability of all non-realizable couples (SP, SAP) results from the non-realizability of the corresponding couples (SP, AP). In principle, one could imagine a situation in which there exists a couple (SP, AP) extending into several couples (SP, SAP) some of which are realizable and the remaining are not. Whether, for , such couples (SP, AP) exist or not is unknown at present.
Our final natural and important question deals with the topology of intersections of the set of real univariant polynomials with a given number of real roots with orthants in the coefficient space (which means fixing the signs of the coefficients). It is well known that the set of monic univariate polynomials of a given degree and with a given number of real roots is contractible. When we cut this set with the union of coordinate hyperplanes (coordinates being the coefficients of polynomials), then it splits into a number of connected components. In each such connected component, the number of positive and negative roots is fixed. But, in principle, it can happen that different connected components correspond to the same pair (pos, neg). Could this really happen? Are all such connected components contractible, or they can have some nontrivial topology?
The authors want to thank the Department of Mathematics of the Université Côte d’Azur and Stockholms Universitet for the hospitality, financial support, and nice working conditions during our several visits to each other.
- To René Descartes, a polymath in philosophy and science.