On Descartes' rule of signs

A sequence of $d+1$ signs $+$ and $-$ beginning with a $+$ is called a {\em sign pattern (SP)}. We say that the real polynomial $P:=x^d+\sum _{j=0}^{d-1}a_jx^j$, $a_j\neq 0$, defines the SP $\sigma :=(+$,sgn$(a_{d-1})$, $\ldots$, sgn$(a_0))$. By Descartes' rule of signs, for the quantity $pos$ of positive (resp. $neg$ of negative) roots of $P$, one has $pos\leq c$ (resp. $neg\leq p=d-c$), where $c$ and $p$ are the numbers of sign changes and sign preservations in $\sigma$; the numbers $c-pos$ and $p-neg$ are even. We say that $P$ realizes the SP $\sigma$ with the pair $(pos, neg)$. For SPs with $c=2$, we give some sufficient conditions for the (non)realizability of pairs $(pos, neg)$ of the form $(0,d-2k)$, $k=1$, $\ldots$, $[(d-2)/2]$.


Introduction
In the present paper we consider a problem which is a natural continuation of Descartes' rule of signs. The latter states that the number of positive roots of a real univariate polynomial (counted with multiplicity) is majorized by the number of sign changes in the sequence of its coefficients. We focus on polynomials without zero coefficients. Such a polynomial (say, of degree d) is representable in the form P := x d + a d−1 x d−1 + · · · + a 1 x + a 0 , a j ∈ R * . Denoting by c and p the numbers of sign changes and sign preservations in the sequence 1, a d−1 , . . ., a 1 , a 0 and by pos and neg the number of positive and negative roots of P (hence c+p = pos+neg = d) one obtains the conditions (1.1) pos ≤ c , neg ≤ p , c + p = d , c − pos ∈ 2N ∪ 0 , p − neg ∈ 2N ∪ 0 , (−1) pos = sgn (a 0 ) (the condition neg ≤ p results from Descartes' rule applied to the polynomial P (−x)). We call sign pattern (SP) a sequence of + or − signs of length d + 1 beginning with a +. We say that the polynomial P defines the SP (+, sgn(a d−1 ), . . ., sgn(a 1 ), sgn(a 0 )). A pair (pos, neg) satisfying conditions (1.1) is called admissible. An admissible pair (AP) is called realizable if there exists a polynomial P with exactly pos positive distinct and exactly neg negative distinct roots.
Example 1. For c = 0, the all-pluses SP is realizable with any AP (which is of the form (0, d − 2k), k = 0, 1, . . ., [d/2], where [α] denotes the integer part of α ∈ R). Indeed, one can construct a polynomial P with d distinct negative roots and d − 1 distinct critical levels. Then in the family of polynomials P + t, t > 0, one 1 encounters polynomials with exactly d − 2, d − 4, . . ., d − 2[d/2] negative distinct roots and with no positive roots (as t increases, the polynomial P + t loses twoby-two its real roots; each time two coalescing real roots give birth to a complex conjugate pair).

Proposition 1.
(1) Any SP with c = 1 is realizable with any AP of the form (2) Any SP is realizable with the AP (c, p).
Proposition 1 is proved in Section 2. Part (1) of it shows that in terms of the value of c, the first truly nontrivial case is c = 2. Its study is the object of the present paper. We should point out that due to the possibility to consider instead of the polynomial P (x) the polynomial P (−x) (this change exchanges the quantities c and p and the quantities pos and neg), it suffices to consider (for a given degree d) the cases with c ≤ [d/2]. Notation 1. We denote by Σ m,n,q the SP consisting of m ≥ 1 pluses followed by n ≥ 1 minuses followed by q ≥ 1 pluses, where m + n + q = d + 1. For a given polynomial P , we denote by P R the corresponding reverted polynomial, i.e. P R := x d P (1/x). If the polynomial P defines the SP Σ m,n,q , then P R defines the SP Σ q,n,m . The roots of P R are the reciprocals of the roots of P .
For small values of m or n, we have the following result: (2) For n = 3 and d ≥ 5, any SP Σ m,3,q is realizable with the AP (0, d − 2). For d = 4, the SP Σ 1,3,1 is not realizable with the AP (0, 2).
Theorem 1 is proved in Section 3.

Remarks 1.
(1) If a SP Σ m,n,q is realizable with the AP (0, d − 2), then it is realizable with any AP of the form (0, d − 2k), k = 1, . . ., [(d − 2)/2]. Indeed, if a polynomial P with distinct nonzero roots realizes the SP Σ m,n,q , then one can perturb P to make all its critical levels distinct. In the family P + t one encounters (for suitable positive values of t) polynomials with exactly d − 2k distinct negative roots and no positive ones, for k = 1, . . ., [(d − 2)/2]. As t ≥ 0, the constant term of the polynomial P is positive hence P + t defines the SP Σ m,n,q .
Proposition 2 is proved in Section 4. Our next result contains sufficient conditions for realizability of a SP Σ m,n,q with the AP (0, d − 2): Theorem 2 is proved in Section 5.
(2) The condition of realizability (1.2) can be compared with the condition of nonrealizability κ ≥ 4 (see part (3) of Remarks 1). To this end the latter can be given the following equivalent form:
Suppose that for d = d 0 ≥ 2 all SPs with c = 0 or c = 1 are realizable by monic polynomials (denoted by P ). Then to realize for d = d 0 + 1 a SP with c = 0 or c = 1 with the pair (0, d 0 + 1) or (1, d 0 ) it suffices to apply Lemma 1 with P 1 = P and with P 2 = x − 1 (resp. P 2 = x + 1) if c = 0 and the last two signs of the SP defined by P are (+, −) (resp. if c = 1 and these last two signs are (−, −)).
To realize for c = 1 a SP with any AP (1, d − 1 − 2k), k ≤ [(d − 1)/2], it suffices to perturb a polynomial P realizing this SP with the pair (1, d − 1) so that all critical levels become distinct and then choose suitable values of t > 0 in the family of polynomials P − t.
To prove part (2) one has to apply d − 1 times Lemma 1. When it is applied for the first time one sets P 1 := x − 1 (resp. P 1 := x + 1) if the second entry of the SP is − (resp. +). Each time the polynomial P 2 equals x − 1 or x + 1.
Keeping in mind that e j > 0, y > 0 and z > 0, one gets The quadratic polynomial T has a positive discriminant e 2 3 − e 2 e 4 (this follows from Newton's inequalities). Hence it has two real roots, so the last inequality implies and as √ y > z 2 > e 1 2 , one deduces the condition One has e 1 e 2 − 2e 3 > 0. Indeed, every product a i a j a k is encountered exactly two times in 2e 3 and three times in e 1 e 2 (and there are also the products a 2 i a j in e 1 e 2 ). Hence one can take squares of both hand-sides of inequality (3.3) and then divide by e 2 to obtain the condition (3.4) e 2 1 e 2 + 4e 4 < 4e 1 e 3 . We are going to show that for d ≥ 3, (3.5) e 2 1 e 2 + 4e 4 > 4e 1 e 3 which contradiction proves part (4). For d = 3, one has e 1 e 2 ≥ 9e 3 (see Proposition 2 on page 2 of [6]). Suppose that (3.5) holds true up to degree d ≥ 3. We proceed by induction on d. Recall that we denote by (−a j ) the negative roots of P . For degree d + 1, we have to show that where e j are the elementary symmetric functions of the quantities a 1 , . . . , a d−2 , which is simplified to Newton's inequality e 2 1 ≥ 2d d − 1 e 2 implies the following ones: proves (3.6) and hence (3.5) as well.

Proof of Proposition 2
We give in detail the proof of part (1). For part (2), we point out only the differences w.r.t. the proof of part (1). These differences are only technical in character. In order to give easily references to the different parts of the proof, the latter are marked by 1 0 , 2 0 , . . ., 6 0 .
Proof of part (1) of Proposition 2. 1 0 . Suppose that there exists a polynomial P := RQ, where R := (x + u 1 ) · · · (x + u 7 ) , u j > 0 , and Q := x 2 + rx + s , which realizes one of the two SPs Σ 3,4,3 or Σ 2,4,4 with the AP (0, 7). We set P := 9 j=0 p j x j and Q := (x − a) 2 + b, a ∈ R, b ≥ 0. We show that for b = 0, there exists no polynomial satisfying the conditions Hence this holds true also for b > 0 because P = R · Q| b=0 + bR, and the polynomial R has all coefficients positive. This in turn implies that for b ≥ 0, there exists no polynomial P realizing the SP Σ 3,4,3 or Σ 2,4,4 . So from now on we concentrate on the case b = 0. 2 0 . Suppose that a polynomial P with b = 0 and u 1 ≥ u 2 ≥ · · · ≥ u 7 ≥ 0 satisfying the left or right couple of inequalities (4.8) exists. We make the change of variables x → u 1 x and after this we multiply P by (1/u 1 ) 9 (these changes preserve the signs of the coefficients), so now we are in the case u 1 = 1. Denote by ∆ ⊂ R 7 + = {(u 2 , u 3 , . . . , u 7 , a)} the set on which one has conditions (4.8). The closure ∆ of this set is compact. Indeed, one has p 1 ≥ 0 hence The set ∆ can be stratified according to the multiplicity vector of the variables (u 2 , . . . , u 7 ) and the possible equalities u j = 0, u i = 1 and/or a = 0. Suppose that the set ∆ contains a polynomial satisfying the inequalities (4.8).

Remarks 3.
(1) For this polynomial one has a > 0, otherwise all its coefficients are nonnegative. One has also u j > 0, j = 2, . . ., 7. Indeed, in the case of Σ 3,4,3 (resp. Σ 2,4,4 ), if three or more (resp. if four or more) of the variables u j are 0, then the polynomial P has less than two sign changes in the sequence of its coefficients and by the Descartes rule of signs P cannot have two positive roots counted with multiplicity. For Σ 3,4,3 , if exactly one or two of the variables u j equal 0, then the polynomial P is the product of x with a polynomial defining the SP Σ 3,4,2 or of x 2 with a polynomial defining the SP Σ 3,4,1 . However these SPs are not realizable with the APs (0, 6) or (0, 5) respectively, see [4] and [2]. For Σ 2,4,4 , if exactly one, two or three of the variables u j equal 0, then P is the product of x, x 2 or x 3 with a polynomial defining respectively the SP Σ 2,4,3 , Σ 2,4,2 or Σ 2,4,1 which is not realizable with the AP (0, 6), (0, 5) or (0, 4), see [4], [2] and [1].
(3) There exists δ * > 0 such that on the set ∆ • , one has also u j ≥ δ * . This follows from part (1) of the present remarks.
3 0 . We need some technical lemmas: Lemma 2. The minimum of the quantity p 3 + p 6 , resp. p 4 + p 7 , is not attained at a point of the set ∆ • with three or more distinct and distinct from 1 among the quantities u j , 2 ≤ j ≤ 7.
Thus to prove Proposition 2 we have to consider only the case when exactly one or two of the quantities u j are distinct from 1. We use the following result: 4 0 . Further we consider several different cases according to the multiplicity of u j0 , the smallest of the variables u j . In the proofs we use linear changes x → χx, χ > 0, followed by P → χ −9 P . These changes preserve the signs of the coefficients; the condition u 1 = 1 is lost and the condition u j0 = 1, j 0 = 1, is obtained. The aim of this is to have more explicit computations. In all the cases the polynomial R is of the form R = (x + 1) s1 (x + v) s2 (x + w) s3 , s 1 + s 2 + s 3 = 7, and one has v > 1, w > 1, but v and w are not necessarily distinct and we do not suppose that v > w or v < w (which permits us to assume that s 2 ≥ s 3 ). Allowing the equality v = w means treating together cases of exactly two or exactly three distinct quantities u j (counting also u 1 = 1). We list the triples (s 1 , s 2 , s 3 ) defining the cases: and (1, 3, 3) . The cases when there are exactly two different quantities u j one of which is u 1 = 1 can be coded in a similar way. E.g. (5, 2) means that R = (x + 1) 5 (x + u) 2 , u > 1. The nonrealizability of these cases follows automatically from the one of the above 9 ones (when v and w coalesce), with the only exception of R = (x + 1) 6 (x + w) (the case (6, 1)).
Lemma 5. Conditions (4.8) fail in case (6, 1). 5 0 . We consider the SP Σ 2,4,4 first. We compute using MAPLE the resultant Res (p 4 , p 7 , a) as a function of v and w. Then we set v := 1 + V , w := 1 + W , V > 0, W > 0. In all 9 cases this resultant is a polynomial in V and W with all coefficients positive. Hence for no value of V > 0 and W > 0 do the coefficients p 4 and p 7 vanish together.
As in the case of Σ 2,4,4 , we express Res (p 3 , p 6 , a) as a polynomial of v and w, and then of V and W . In cases (5, 1, 1), (4, 2, 1) and (3, 2, 2), this resultant has a single monomial with negative coefficient, this is U V . We give the monomials V W , V 2 and W 2 for these three cases: (3, 2, 2) −37632V W + 47040V 2 + 47040W 2 . The discriminants of these quadratic homogeneous polynomials are negative hence they are nonnegative (and positive for V > 0, W > 0). In the case of (3, 3, 1), there are exactly two monomials with negative coefficients, namely V W and V 2 W . The resultant equals (we skip all other monomials; their coefficients are positive). The two quadratic homogeneous polynomials have negative discriminants, so they are positive for V > 0, W > 0.
The rest of the reasoning goes by exact analogy with the case of Σ 2,4,4 .
We consider first the case of Σ 3,4,3 , i.e (µ, ν) = (3, 6). The 2-vectors of coefficients of x 3 and x 6 of the polynomials P ⋄ , xP ⋄ , x 2 P ⋄ and x 3 P ⋄ equal (B, 0), (C, 1), (D, A) and (E, B) respectively. For B = 0, the first two of them are not collinear. As E = 0 (see parts (2) and (3)  Proof of Lemma 3. For the polynomial (x + 1) 7 (x − a) 2 , we list its coefficients p 3 , p 4 , p 6 and p 7 and their roots: Hence for no value of a ≥ 0 does one have the left or the right two of conditions (4.8) together.
(2) In the proof of part (2) of Proposition 2 we define the set ∆ • ⊂ ∆ as the one on which one has p 5 + p 8 ≤ −δ/2. On this set one has a ≥ 2 −10 δ. Indeed, as P = x 2 R − 2axR + a 2 R, any coefficient of P is not less than −2aσ, where σ is the sum of all coefficients of R (they are all nonnegative); clearly σ ≤ 2 8 (follows from u j ∈ [0, 1]).
The proof is much the same as the one of Lemma 2. One sets (µ, ν) = (5,8). Each of the polynomials P vj and P a is a linear combination of P ⋄ := P v1,v2,v3,a := x 6 + Ax 5 + Bx 4 + Cx 3 + Dx 2 + Ex + F , xP ⋄ , x 2 P ⋄ and x 3 P v,w,a . The 2-vectors of coefficients of x 5 and x 8 of the polynomials P ⋄ , xP ⋄ , x 2 P ⋄ and x 3 P ⋄ equal (A, 0), (B, 0), (C, 1) and (D, A) respectively. If A = 0 or B = 0, there are two noncollinear among the first three of these vectors and the choice of v * j and a * is possible. If A = B = 0, then, as F = 0, either the polynomial P ⋄ or one of its derivatives is not with all roots real which is a contradiction.
One has Res (p 5 , p 8 , a) = 3969(w + 2) 2 (w − 1) 2 . We list the roots of p 5 and p 8 for w = 1/2, w = 1 and w = 2: As in the proof of Lemma 5, we conclude that the conditions p 5 < 0, p 8 < 0 fail for w > 0. 5 0 . We compute Res (p 5 , p 8 , a) as a function of v and w and then set v := 1 + V , w := 1 + W . Our aim is to show that in all 12 cases, the leading coefficients of p 5 and p 8 considered as quadratic polynomials in a are positive. The rest of the reasoning is done by analogy with part 5 0 of the proof of part (1) of Proposition 2.
6 0 . It is in the analog of 6 0 that there is much more technical work to be done. Of the twelve cases listed in 4 0 , in three there is a single monomial with a negative coefficient, and this is U V . We list the coefficients of the monomials U V , U 2 and V 2 of the cases (6, 1, 1), (5, 2, 1) and (4, 2, 2) respectively: Everywhere in 6 0 quadratic and biquadratic polynomials have negative discriminants. There are four cases in which exactly two monomials have negative signs, namely (4, 3, 1), (3,4,1), (3,3,2) and (2,4,2) in which we give only the monomials forming quadratic homogeneous polynomials with negative discriminants (multiplied by 1 or U ); we skip all other monomials (their coefficients are positive): In the cases (2, 5, 1) and (1, 6, 1) there are four and five negative monomials respectively. These cases are treated in a similar way: In the case (2, 3, 3), there are four negative monomials which we include in polynomials as follows: For the third polynomial in brackets its corresponding inhomogeneous polynomial −30618x 2 + 221130x 3 + 221130 − 30618x has one negative and two complex conjugate roots. For a univariate real polynomial with positive leading coefficient and having only negative and complex conjugate roots we say that it is of type P. It is clear that the homogeneous polynomial corresponding to a type P univariate polynomial (we say that it is also of type P) is nonnegative.
In the case (1, 5, 2), there are seven negative monomials: The third and fourth of the polynomials in brackets are of type P hence nonnegative. Finally, in the case (1,4,3) we have also seven negative monomials: The third and the last two polynomials in brackets are of type P.

Proof of Theorem 2
Consider the polynomial P = (x + 1) d−2 (x 2 − zx + y), where the quadratic factor has no real roots, i.e. z 2 < 4y. Hence y > 0 and z > 0 (otherwise all coefficients of P must be positive). If the polynomial P defines the SP Σ m,n,q , then any perturbation of P with d − 2 distinct negative roots close to −1 defines also the SP Σ m,n,q . We expand P in powers of x: where p j = C j d−2 − C j−1 d−2 z + C j−2 d−2 y with C ν µ = 0 if µ < ν. The coefficients of P define the SP Σ m,n,q , so p j > 0 for j = 1, . . . , m − 1 and for j = m + n, . . . , d , and p j < 0 for j = m, m + 1, . . . , m + n − 1 .