An extension of the Hermite-Biehler theorem with application to polynomials with one positive root
Richard Ellard Helena Šmigoc




An extension of the Hermite-Biehler theorem]An extension of the Hermite-Biehler theorem with application to polynomials with one positive root








	Richard Ellard,
	School of Mathematics and Statistics,
	University College Dublin,
	Belfield, Dublin 4, Ireland

richardellard@gmail.com
The authors' work was supported by Science Foundation Ireland under Grant 11/RFP.1/MTH/3157.




	Helena Šmigoc,
	School of Mathematics and Statistics,
	University College Dublin,
	Belfield, Dublin 4, Ireland

helena.smigoc@ucd.ie


[2010]26C10, 93D20, 15A29







	If a real polynomial f(x)=p(x^2)+xq(x^2) is Hurwitz stable (every root if f lies in the open left half-plane), then the Hermite-Biehler Theorem says that the polynomials p(-x^2) and q(-x^2) have interlacing real roots. We extend this result to general polynomials by giving a lower bound on the number of real roots of p(-x^2) and q(-x^2) and showing that these real roots interlace. This bound depends on the number of roots of f which lie in the left half plane. Another classical result in the theory of polynomials is Descartes' Rule of Signs, which bounds the number of positive roots of a polynomial in terms of the number of sign changes in its coefficients. We use our extension of the Hermite-Biehler Theorem to give an inverse rule of signs for polynomials with one positive root.


[
    Helena Šmigoc
    January 2017
=================





§ INTRODUCTION


Recall that a real polynomial f is called (Hurwitz) stable if every root of f lies in the open left half-plane. Determining the stability of real polynomials is of fundamental importance in the study of dynamical systems and as such, several equivalent characterisations have been given. One such characterisation is the Hermite-Biehler Theorem <cit.>, a proof of which can also be found in <cit.>. The Hermite-Biehler Theorem has been instrumental in the study of the “robust parametric stability problem”, that is, the problem of guaranteeing that stability is preserved by real coefficient perturbations (see <cit.>).


	Let
	
    f(x):=a_0x^n+a_1x^n-1+⋯+a_n

	be a real polynomial and write f(x)=p(x^2)+xq(x^2), where p(x^2) and xq(x^2) are the components of f(x) made up by the even and odd powers of x, respectively. Let x_e1,x_e2,… denote the distinct nonnegative real roots of p(-x^2) and let x_o1,x_o2,… denote the distinct nonnegative real roots of q(-x^2), where both sequences are arranged in ascending order. Then f is stable if and only if the following conditions hold:
	
		
   all of the roots of p(-x^2) and q(-x^2) are real and distinct;
		
   a_0 and a_1 have the same sign;
		
   0<x_e1<x_o1<x_e2<x_o2<⋯.
	


The Hermite-Biehler theorem says that, if f(x)=p(x^2)+xq(x^2) is stable, then the polynomials p(-x^2) and q(-x^2) have real, interlacing roots. In Section <ref>, we will extend the Hermite-Biehler Theorem by showing that, even if f is not stable (suppose f has n_- roots in the left half-plane and n_+ roots in the right), then it is still possible to give a lower bound on the number of real roots of p(-x^2) and q(-x^2). This bound is given in terms of the quantity |n_–n_+|. Furthermore, we show that these real roots interlace.

Another classical result in the theory of polynomials is Descartes' Rule of Signs. We say that a real polynomial

    f(x)=a_0x^n+a_1x^n-1+a_2x^n-2+⋯+a_n,  a_0≠0

has k sign changes if k sign changes occur between consecutive nonzero elements of the sequence a_0,a_1,…,a_n. Descartes' Rule of Signs states that the number of positive roots of f is either equal to k, or is less than k by an even number. Descartes' rule gives the exact number of positive roots in only two cases:

	
  * f has no sign changes, in which case, f has no positive roots, or
	
  * f has precisely one sign change, in which case, f has precisely one positive root.


Conversely to (i), if every root of f has real part less than or equal to zero, then f has no sign changes. To see this, we need only observe that, if the roots of f are labeled -η_1,-η_2,…,-η_s,-α_1± iβ_1,-α_2± iβ_2,…,-α_m± iβ_m, where η_j,α_j,β_j≥0 and s+2m=n, then the polynomial

    1/a_0f(x)=∏_j=1^s(x+η_j)∏_j=1^m( (x+α_j)^2+β_j^2 )

has nonnegative coefficients, and consequently, every nonzero coefficient of f has the same sign.

In general, the converse of (ii) is not true; however, in Section <ref>, we will use our extension of the Hermite-Biehler Theorem to prove that, if f has at most one root with positive real part, then the sequences a_0,a_2,a_4,… and a_1,a_3,a_5,… each feature at most one sign change.

Polynomials with one positive root (in particular, inverse rules of signs for such polynomials) are of interest in a number of areas, such as in polynomial real root isolation, i.e. the process of finding a collection of intervals of the real line such that each interval contains precisely one real root and each real root is contained in some interval. Modern real root isolation algorithms typically use a version of Vincent's Theorem <cit.>, the proof of which depends on some kind of inverse rule of sign for polynomials with one positive root. For example, the proof of Vincent's Theorem given by Alesina and Galuzzi <cit.> uses a special case of a theorem of Obreschkoff <cit.>, which we state below:

<cit.>
	If a real polynomial f of degree n has a simple positive root r and all other roots lie in the wedge
	
    S_√(3):={-α+iβ : α>0,  |β|≤√(3)α},

	then f has precisely one sign change.










Polynomials with one positive root also arise in problems that consider the sign patterns of matrices (in particular, companion and related matrices). One such problem is the Nonnegative Inverse Eigenvalue Problem, or NIEP. This is the (still open) problem of characterising those lists of complex numbers which are realisable as the spectrum of some (entrywise) nonnegative matrix. Polynomials with one positive root are of particular importance in the NIEP, and as such, the NIEP has already motivated several results on the coefficients of polynomials of this type. In this context, the polynomial f represents the characteristic polynomial of the realising matrix and its one positive root represents the Perron eigenvalue of the realising matrix.

One of the earliest results in the NIEP was given by Suleǐmanova <cit.> when she proved the following:

<cit.>
	Let σ:=(ρ,λ_2,λ_3,…,λ_n), where ρ≥0 and λ_i≤0: i=2,3,…,n. Then σ is the spectrum of a nonnegative matrix if and only if
	
    ρ+λ_2+λ_3+⋯+λ_n≥0.



Perhaps the most elegant proof of Suleǐmanova's result is due to Perfect <cit.>, who showed that, under the assumptions of the theorem, every coefficient of the polynomial

    f(x)=(x-ρ)∏_i=2^n(x-λ_i),

apart from the leading coefficient, is nonpositive, and hence, the companion matrix of f is nonnegative (note that, since Suleǐmanova's hypotheses guarantee the coefficient of x^n-1 in f is negative, the same result follows immediately from Theorem <ref>).

Later, Laffey and Šmigoc <cit.> generalised Suleǐmanova's theorem to complex lists with one positive element and n-1 elements with real part less than or equal to zero:

<cit.>
  Let ρ≥0 and let λ_2,λ_3,…,λ_n be complex numbers such that
Re λ_i≤0 for all i=2,3,…,n. Then the list
σ:=(ρ,λ_2,λ_3,…,λ_n) is the spectrum of a nonnegative
matrix if and only if the following conditions hold:
  
    
  
    σ is self-conjugate;
    
  
    ρ+λ_2+λ_3+⋯+λ_n≥0;
    
  
    (ρ+λ_2+λ_3+⋯+λ_n)^2≤ n(ρ^2+λ_2^2+λ_3^2+⋯+λ_n^2).
  
  Furthermore, when the above conditions are satisified, σ may be realised by a matrix of the form
C+α I_n, where C is a nonnegative companion matrix with trace zero and α is a
nonnegative scalar.


The crucial ingredient in Laffey and Šmigoc's result was the following lemma (also proved by the authors):


	Let (λ_2,λ_3,…,λ_n) be a self-conjugate list of complex numbers with nonpositive real parts, let ρ≥0 and let
	
    f(x):=(x-ρ)∏_i=2^n(x-λ_i)=x^n+a_1x^n-1+a_2x^n-2+⋯+a_n.

	If a_1,a_2≤0, then a_i≤0: i=3,4,…,n.


Although Lemma <ref> was motivated by matrix theory, it is, fundamentally, a result on the coefficients of real polynomials. We generalise this result in Section <ref>.



§ THE CAUCHY INDEX OF A RATIONAL FUNCTION



	Let f(x) be a real rational function and let θ,ϕ∈ℝ∪{-∞,∞}, with θ<ϕ. The Cauchy index of f(x) between the limits θ and ϕ—written I_θ^ϕ f(x)—is defined as the number of times f(x) jumps from -∞ to ∞, minus the number of times f(x) jumps from ∞ to -∞, as x moves from θ to ϕ.



	If
	
    f(x)=1/(x+1)(x-1),

	then I_-∞^0f(x)=-1, I_0^∞ f(x)=1 and I_-∞^∞ f(x)=0.


We introduce some additional notation: if f(x) is a complex-valued function and C is a contour in the complex plane, let Δ_Cf(x) denote the total increase in arg f(x) as x traverses the contour C. If C is the line segment from θ to ϕ, then we write Δ_θ^ϕ f(x).

The following result (and its proof) essentially appears in <cit.>. The proof is included for completeness.


	Let f(x):=P(x)+iQ(x), where
	
    P(x):=x^n+a_1x^n-1+a_2x^n-2+⋯+a_n

	and
	
    Q(x):=b_1x^n-1+b_2x^n-2+⋯+b_n

	are real polynomials. Suppose f has n_+ roots with positive imaginary part, n_- roots with negative imaginary part and n_0 real roots (n_++n_-+n_0=n). Then
	
    I_-∞^∞Q(x)/P(x)=n_–n_+.



	We first consider the case when n_0=0. Define the closed contour C=C_1+C_2 (shown in Figure <ref>), where C_1 is the line segment from -R to R and C_2 is the semicircle
	
    x(t)=Re^it :  0≤ t≤π.

	Assume R is large enough so that all of the roots of f with positive imaginary part lie within the region enclosed by C.
	
->-/.style=decoration=
  markings,
  mark=at position #1 with >,postaction=decorate


		
	Denote the roots of f by x_1,x_2,…,x_n. For each j=1,2,…,n, if Re(x_j)>0, then Δ_C(x-x_j)=2π. Otherwise, Δ_C(x-x_j)=0. Therefore
	
    Δ_Cf(x)=Δ_C((a_0+ib_0)∏_j=1^n(x-x_j))=∑_j=1^nΔ_C(x-x_j)=2n_+π.

	Similarly,
	
    lim_R→∞Δ_C_2f(x)=nπ.

	Hence
	
    Δ_-∞^∞ f(x)=(2n_+-n)π;

	however, since
	
    arg f(x)=tan^-1Q(x)/P(x)

	and
	
    lim_x→±∞Q(x)/P(x)=0,

	it follows that
	
    1/πΔ_-∞^∞ f(x)=-I_-∞^∞Q(x)/P(x).

	Combining (<ref>) and (<ref>) gives
	
    I_-∞^∞Q(x)/P(x)=n-2n_+=n_–n_+,

	as required.
	
	Now consider the case when n_0>0. Let us label the real roots of f as η_1,η_2,…, η_n_0.
	
	Writing
	
    f(x)   =( ∏_j=1^n_0(x-η_j) )f̃(x),
    f̃(x)   =P̃(x)+iQ̃(x),

	we note that the polynomial f̃ has n_+ roots with positive imaginary part, n_- roots with negative imaginary part and no real roots. Hence, from the above,
	
    I_-∞^∞Q̃(x)/P̃(x)=n_–n_+.

	We note, however, that
	
    P(x)   =( ∏_j=1^n_0(x-η_j) )P̃(x),
    
    		Q(x)   =( ∏_j=1^n_0(x-η_j) )Q̃(x)

	and for all j=1,2,…,n_0,
	
    lim_x→η_jQ(x)/P(x)=lim_x→η_jQ̃(x)/P̃(x).

	Therefore
	
    I_-∞^∞Q(x)/P(x)=I_-∞^∞Q̃(x)/P̃(x).







§ AN EXTENSION OF THE HERMITE-BIEHLER THEOREM


In this section, we consider an arbitrary real polynomial f(x)=p(x^2)+xq(x^2), with n_- roots in the left half-plane and n_+ roots in the right half-plane. We extend the Hermite-Biehler Theorem by giving a lower bound on the number of real roots of p(-x^2) and q(-x^2) in terms of |n_–n_+| and showing that these real roots interlace.


	Let 𝒳 and 𝒵 be sequences of real numbers. We say 𝒳 and 𝒵 interlace if the following two conditions hold:
	
		
  * if x_i and x_j are two distinct elements of 𝒳 with x_i<x_j, then there exists an element z_k of 𝒵 such that x_i≤ z_k≤ x_j (and vice versa);
		
  * if x_i appears in 𝒳 with multiplicity m, then x_i appears in 𝒵 with multiplicity at least m-1 (and vice versa).
	
	We say 𝒳 and 𝒵 strictly interlace if every element of 𝒳 and 𝒵 occurs with multiplicity 1, 𝒳 and 𝒵 have no element in common and whenever x_i and x_j are two distinct elements of 𝒳 with x_i<x_j, there exists an element z_k of 𝒵 such that x_i<z_k<x_j (and vice versa).


Before considering the real polynomial f(x)=p(x^2)+xq(x^2), it is easier (and more general) to first consider the complex polynomial f(x):=P(x)+iQ(x).


	Consider the polynomial
	
    f(x):=P(x)+iQ(x),

	where
	
    P(x)   :=x^n+a_1x^n-1+a_2x^n-2+⋯+a_n, 
    
    		Q(x)   :=b_1x^n-1+b_2x^n-2+⋯+b_n

	and the a_i and b_i are real. Suppose f has n_+ roots with positive imaginary part, n_- roots with negative imaginary part and n_0<n real roots (n_++n_-+n_0=n). If d:=n-2min{n_+,n_-}, then (counting multiplicities) there exist at least d real roots of P (say μ_1,μ_2,…,μ_d) and at least d-1 real roots of Q (say ν_1,ν_2,…,ν_d-1) such that
	
    μ_1≤ν_1≤μ_2≤ν_2≤⋯≤ν_d-1≤μ_d.

	If n_0=0, then the inequalities in (<ref>) may be assumed to be strict.



















	As in the proof of Theorem <ref>, we first consider the case when n_0=0. In this case, P and Q can have no real root in common, since if x_0 were a real root of both P and Q, then x_0 would also be a real root of f. Suppose also that n_->n_+.
	
	Let p_1<p_2<⋯<p_s be the points on the real line at which Q(x)/P(x) jumps from -∞ to ∞ and let q_1<q_2<⋯<q_s' be the points on the real line at which Q(x)/P(x) jumps from ∞ to -∞. Clearly, the p_i and q_i are roots of P. Suppose they are arranged as follows:
	
    ⋯<p_k_j< p_k_j+1<⋯< p_k_j+1-1
    
    		<q_l_j< q_l_j+1<⋯< q_l_j+1-1
    
    		<p_k_j+1< p_k_j+1+1<⋯< p_k_j+2-1<⋯.

	
	Now consider the interval R:=(p_k_j+r-1,p_k_j+r), where 1≤ r≤ k_j+1-k_j-1. By definition of the p_i,
	
    lim_x→ p_r-1+k_j^+Q(x)/P(x)=∞, lim_x→ p_r+k_j^-Q(x)/P(x)=-∞.

	Furthermore, although Q(x)/P(x) may have discontinuities in R (at points where P has a root of even multiplicity), Q(x)/P(x) does not change sign at these discontinuities. Hence Q(x)/P(x) has a root, say w_jr, in R. Obviously, w_jr is also a root of Q.
	
	Let us now consider the sequence
	
    𝒯:=( …,p_k_j,w_j1, p_k_j+1,w_j2,…,p_k_j+1-1,
    
    		p_k_j+1,w_j+1,1, p_k_j+1+1,w_j+1,2,…,p_k_j+2-1,… ).

	This sequence consists of strictly interlacing roots of P and Q, apart from certain pairs of adjacent roots of P of the form (p_k_j+1-1,p_k_j+1). Hence, we form a new sequence 𝒯' from 𝒯 by deleting either p_k_j+1-1 or p_k_j+1 for each j. Since 𝒯' is a strictly interlacing sequence of real roots of P and Q, whose first and last entries are roots of P, it is sufficient to check that 𝒯' is sufficiently long.
	
	Let h be the number of subsequences (q_l_j< q_l_j+1<⋯< q_l_j+1-1) which lie between p_1 and p_s. We note that 𝒯 has length 2s-h-1. Since 𝒯' was formed by deleting h elements from 𝒯, it follows that 𝒯' has length
	
    2(s-h)-1≥2(s-s')-1=2I_-∞^∞Q(x)/P(x)-1.

	By Theorem <ref>, it follows that 𝒯' has at least
	
    2(n_–n_+)-1=2(n-2n_+)-1=2d-1

	elements, as required.
	
	We have yet to consider n_+≥ n_- or n_0>0. If n_0=0 and n_+=n_-, then the statement says nothing; hence we may ignore this case. If n_0=0 and n_+>n_-, then the proof is analogous to the above.
	
	Finally, suppose n_0>0. Let us label the real roots of f as η_1,η_2,…, η_n_0. Writing
	
    f(x)=( ∏_j=1^n_0(x-η_j) )( P̃(x)+iQ̃(x) ),

	we note that the polynomial P̃(x)+iQ̃(x) has n_+ roots with positive imaginary part, n_- roots with negative imaginary part and no real roots. Hence, from the above, there exist d-n_0 real roots of P̃ (say μ_1,μ_2,…,μ_d-n_0) and d-n_0-1 real roots of Q̃ (say ν_1,ν_2, …,ν_d-n_0-1) such that
	
    μ_1<ν_1<μ_2<ν_2<⋯<ν_d-n_0-1<μ_d-n_0.

	All that remains is to note that the sequences
	
    (μ_1,μ_2,…,μ_d-n_0,η_1,η_2,…,η_n_0)

	and
	
    (ν_1,ν_2,…,ν_d-n_0-1,η_1,η_2,…,η_n_0)

	interlace (though not strictly).


As a consequence of Theorem <ref>, we obtain the following extension of the Hermite-Biehler theorem:


	Consider the real polynomial
	
    f(x):=x^n+a_1x^n-1+a_2x^n-2+⋯+a_n.

	Suppose f has n_+ roots with positive real part, n_- roots with negative real part and n_0<n purely imaginary roots (n_++n_-+n_0=n). Let
	
    P(x)   :=x^n-a_2x^n-2+a_4x^n-4-⋯,
    
    		Q(x)   :=a_1x^n-1-a_3x^n-3+a_5x^n-5-⋯

	and d:=n-2min(n_+,n_-). Then (counting multiplicities) there exist at least d real roots of P (say μ_1,μ_2,…,μ_d) and at least d-1 real roots of Q (say ν_1,ν_2,…,ν_d-1) such that
	
    μ_1≤ν_1≤μ_2≤ν_2≤⋯≤ν_d-1≤μ_d.

	If n_0=0, then the inequalities in (<ref>) may be assumed to be strict.


	The real parts of the roots of f correspond to the imaginary parts of the roots of the polynomial
	
    g(x):=i^nf(-ix)=x^n+ia_1x^n-1-a_2x^n-2-ia_3x^n-3+⋯.

	The result follows from Theorem <ref>.


Note that the bounds given for the number of real roots of P and Q in Corollary <ref> may or may not be achieved, as illustrated by the following two examples:










	The polynomial
	
    f(x):=x^5-x^4+3 x^3-4 x+1

	has n_+=4 roots with positive real part and n_-=1 root with negative real part, so that, in the notation of Corollary <ref>, d=3. The polynomial P(x):=x^5-3 x^3-4 x has roots -2,0,2,i,-i and the polynomial Q(x)=-x^4+1 has roots -1,1,i,-i. Hence, in this example, the bounds given in Corollary <ref> on the numbers of real roots of P and Q is achieved.



	Consider the polynomial
	
    f(x):=x^4+2 x^3+23 x^2+94 x+130,

	with roots 1±5i,-2± i. In the notation of Corollary <ref>, n_+=n_-=2 and d=0. Hence, the corollary does not guarantee the existence of any real roots of the polynomials
	
    P(x):=x^4-23 x^2+130

	or
	
    Q(x):=2 x^3-94 x;

	however, P has roots -√(13),-√(10),√(10),√(13) and Q has roots -√(47),0,√(47).


It turns out that, under certain circumstances, we can infer the existence of an additional two real roots of the polynomial Q given in (<ref>). We will use these additional roots in the next section.


	Assume the hypotheses and conclusion of Theorem <ref> (alternatively Corollary <ref>).
	
		
   If n_->n_+ and lim_x→-∞(P(x)/Q(x))=∞, or alternatively if n_-<n_+ and lim_x→-∞(P(x)/Q(x))=-∞, then there exists an additional real root ν_0 of Q such that ν_0≤μ_1.
		
   If n_->n_+ and lim_x→∞(P(x)/Q(x))=-∞, or alternatively if n_-<n_+ and lim_x→∞(P(x)/Q(x))=∞, then there exists an additional real root ν_d of Q such that ν_d≥μ_d.
	
	If n_0=0, then ν_0<μ_1 and ν_d>μ_d.


	Assume the hypotheses and conclusion of Theorem <ref> (those of Corollary <ref> are equivalent). First suppose n_->n_+ and
	
    lim_x→-∞P(x)/Q(x)=∞.

	In the proof of Theorem <ref>, the first element p_1 of 𝒯' was chosen such that
	
    lim_x→ p_1^-Q(x)/P(x)=-∞.

	Hence, in this case, (<ref>) implies the existence of an additional real root w_0 of Q(x)/P(x) such that w_0<p_1. It follows that there exists an additional real root ν_0 of Q such that ν_0≤μ_1.
	
	The remaining cases are dealt with similarly.




§ POLYNOMIALS WITH ONE POSITIVE ROOT


Using our extension of the Hermite-Biehler theorem, it will now be possible give an inverse rule of signs for real polynomials with one positive root. Later (in Theorem <ref>), we will show how this rule can be somewhat simplified, under some minor additional assumptions.


	Consider the real polynomial
	
    f(x):=x^n+a_1x^n-1+a_2x^n-2+⋯+a_n.

	Suppose f has roots r,x_2,x_3,…,x_n, where r is real and Re(x_j)≤0: j=2,3,…,n. Then the sequence a_1,a_2,…,a_n satisfies the following conditions:
	
		
   Let t be the largest integer such that a_2t≠0. Then either a_2j>0 for all j=1,2,…,t, or there exists s∈{1,2,…,t} such that
		
    a_2j   >0  :  j=1,2,…,s-1, 
    
    			a_2s   ≤0, 
    
    			a_2j   <0  :  j=s+1,s+2,…,t.

		
   Let t' be the largest integer such that a_2t'-1≠0. Then either a_2j-1>0 for all j=1,2,…,t', or there exists s'∈{1,2,…,t'} such that
		
    a_2j-1   >0  :  j=1,2,…,s'-1, 
    
    			a_2s'-1   ≤0, 
    
    			a_2j-1   <0  :  j=s'+1,s'+2,…,t'.

	


	First suppose n is even and write n=2m. The polynomial
	
    f(x)=x^2m+a_1x^2m-1+a_2x^2m-2+⋯+a_2m

	has at most one root with positive real part. Therefore, by Corollary <ref>, the polynomial
	
    x^2m-a_2x^2m-2+a_4x^2m-4-⋯+(-1)^ma_2m

	has at least 2m-2 real roots. It follows that the polynomial
	
    y^m-a_2y^m-1+a_4y^m-2-⋯+(-1)^ma_2m

	has at least m-1 nonnegative roots. Let t be the largest integer such that a_2t≠0. Then the polynomial
	
    y^t-a_2y^t-1+a_4y^t-2-⋯+(-1)^ta_2t

	has at least t-1 positive roots. Therefore, by Descartes' rule of signs, the number of sign changes which occur between consecutive nonzero terms of the sequence
	
    𝒯:=(1,-a_2,a_4,-a_6,…,(-1)^ta_2t)

	is at least t-1. In particular, since 𝒯 contains t+1 elements, this implies at most one of the elements in 𝒯 is zero. There are now three cases to consider:
	
	Case 1: If every element in 𝒯 is nonzero and 𝒯 has t sign changes, then a_2j>0 for each j=1,2,…,t.
	
	Case 2: If every element in 𝒯 is nonzero and 𝒯 has t-1 sign changes, then the sequence
	
    (1,a_2,a_4,…,a_2t)

	has precisely one sign change.
	
	Case 3: Suppose there exists s∈{1,2,…,t} such that a_2s=0. Then, removing a_2s from 𝒯, we obtain a sequence
	
    𝒯_0:=(1,-a_2,a_4,…,(-1)^s-1a_2s-2,(-1)^s-1a_2s+2,…,(-1)^ta_2t)

	with t elements (each nonzero) and t-1 sign changes. It follows that 
	
    a_2j   >0  :  j=1,2,…,s-1, 
    
    		a_2j   <0  :  j=s+1,s+2,…,t.

	We have now shown that the sequence a_2,a_4,… satisfies condition (i).
		
	Similarly, by Corollary <ref>, the polynomial
	
    a_1x^2m-1-a_3x^2m-3+a_5x^2m-5-⋯+(-1)^m-1a_2m-1x

	has at least 2m-3 real roots, one of which is zero. It follows that the polynomial
	
    a_1y^m-1-a_3y^m-2+a_5y^m-3-⋯+(-1)^m-1a_2m-1

	has at least m-2 nonnegative roots. Let t' be the largest integer such that a_2t'-1≠0. Then the polynomial
	
    a_1y^t'-1-a_3y^t'-2+a_5y^t'-3-⋯+(-1)^t'-1a_2t'-1

	has at least t'-2 positive roots. Therefore, by Descartes' rule of signs, the number of sign changes which occur between consecutive nonzero terms of the sequence
	
    𝒯':=(a_1,-a_3,a_5,…,(-1)^t-1a_2t'-1)

	is at least t'-2. As above, this implies at most one of the elements in 𝒯' is zero.
	
	If a_1>0, then the sequences 𝒯 and 𝒯' have the same properties. In this case, it follows from the above argument that the sequence a_1,a_3,… satisfies condition (ii).
	
	If a_1<0, then for P(x) and Q(x) defined as in (<ref>), we see that 
    lim_x→-∞(P(x)/Q(x))=∞ and lim_x→∞(P(x)/Q(x))=-∞.
 Hence, by Observation <ref>, every root of (<ref>) is real. It follows that (<ref>) has t'-1 positive roots and 𝒯' has t'-1 sign changes. Therefore a_2j-1<0 for all j=1,2,…,t'.
	
	Finally, if a_1=0, then consider the polynomial
	
    f_ϵ(x)   :=(x-r-ϵ)∏_j=2^n(x-x_j)
       =x^n-ϵ x^n-1+b_2x^n-2+b_3x^n-3+⋯+b_n,

	where ϵ>0. From the above, we see that b_2j-1≤0: j=2,3,…, ⌈ n/2 ⌉. Furthermore, since each b_j depends continuously on ϵ and
	
    lim_ϵ→0f_ϵ(x)=f(x),

	it follows that a_2j-1≤0: j=2,3,…,⌈ n/2 ⌉. Since at most one of the elements in 𝒯' is zero, we conclude that a_2j-1<0 for all j=2,3,…,t'. We have now shown that the sequence a_1,a_3,… satisfies condition (ii).
	
	The proof for odd n is similar.


With Corollary <ref> established, the proof of Theorem <ref> is quite elementary. Furthermore, the proof generalises to polynomials which have more than one root with positive real part: by combining Corollary <ref> with Descartes' Rule of Signs, bounds can be given on the number of sign changes which occur in the even/odd coefficients.

The statement of Theorem <ref> is somewhat complicated by the fact that the multiplicity of zero as a root of

    x^n-a_2x^n-2+a_4x^n-4-⋯

may be different from the multiplicity of zero as a root of

    a_1x^n-1-a_3x^n-3+a_5x^n-5-⋯

The following example illustrates this:


	Let
	
    f(x):=(x-r)g(x)=x^2m+2+a_1x^2m+1+a_2x^2m+⋯+a_2m+2,

	where r>0 and
	
    g(x):=(x+μ)∏_j=1^m(x^2+β_j^2)  : μ,β_1,…,β_m>0.

	The constant term in f is given by
	
    a_2m+2=-rμβ_1^2β_2^2⋯β_m^2<0.

	Hence, by Theorem <ref>, the sequence 𝒯_e:=(1,a_2,a_4,…,a_2m+2) of even coefficients features precisely one sign change and at most one element of 𝒯_e vanishes.
	
	It is not difficult to verify that the odd coefficients of f are given by
	
    a_2k+1=(μ-r)e_k(β_1^2,β_2^2,…,β_m^2)  :  k=0,1,…,m,

	where e_k denotes the k-th elementary symmetric function. Therefore, the sign of every odd coefficient is determined by the sign of r-μ. In particular, if r=μ, then every odd coefficient vanishes.


It turns out that Example <ref> is essentially unique, in that, if f is not of this form and f(0)≠0, then a_k≤0 implies a_k+2,a_k+4,…<0. To establish this fact, we will require some inequalities from <cit.>, which are closely related to Newton's Inequalities:


















	

	

	









	


















<cit.>
	Let
	
    g(x):=∏_j=1^n(x-x_j)=x^n+b_1x^n-1+b_2x^n-2+⋯+b_n

	be a real polynomial, where x_1,x_2,…,x_n are complex numbers with nonpositive real parts. If k and l have different parity, 1≤ k<l≤ n-1, then
	
    b_kb_l≥ b_k-1b_l+1.



The case of equality in (<ref>) is not explicitly considered in <cit.>; however, by examining the proof, it is possible to characterise the equality case:


	Assume the hypotheses of Theorem <ref>. If k is even and l is odd, then equality occurs in (<ref>) if and only if one of the following conditions holds:
	
		
   zero is a root of g of multiplicity at least n-l+1;
		
   Re (x_j)=0 for all j.
	
	If k is odd and l is even, then equality occurs in (<ref>) if and only if (i) or (ii) holds, or g is of the form (<ref>).


We are now able to give a slightly more compact formulation of Theorem <ref>:


	Let
	
    f(x):=(x-r)∏_j=2^n(x-x_j)=x^n+a_1x^n-1+a_2x^n-2+⋯+a_n

	be a real polynomial, where r>0 and x_2,x_3,…,x_n are nonzero complex numbers such that Re (x_j)≤0 for all j∈{2,3,…,n} and Re (x_j)<0 for some j∈{2,3,…,n}. Then, assuming ∏_j=2^n(x-x_j) is not of the form (<ref>), for each k∈{1,2,…,n-2}, a_k≤0 implies a_k+2<0.


	Let us write f(x)=(x-r)g(x), where
	
    g(x):=∏_j=2^n(x-x_j)=x^n-1+b_1x^n-2+b_2x^n-3+⋯+b_n-1

	and let us define b_0:=1. Since a_n=-rb_n-1<0, we need only consider k≤ n-3.
	
	Suppose (to the contrary) that there exists k∈{1,2,…,n-3} such that
	
    a_k=b_k-rb_k-1≤0

	and
	
    a_k+2=b_k+2-rb_k+1≥0.

	Combining (<ref>) and (<ref>) gives
	
    b_kb_k+1≤ b_k-1b_k+2,

	and so, by Theorem <ref>,
	
    b_kb_k+1=b_k-1b_k+2,

	 which, by Observation <ref>, contradicts the hypotheses of the theorem.


We will illustrate Theorems <ref> and <ref> with an example:


	Consider the polynomial
	
    f(x):=(x-r)( (x+1)^2+β^2 )^m=x^2m+1+a_1x^2m+a_2x^2m-1+⋯+a_2m+1,

	where r,β>0. We note that a_2m+1=-r(1+β^2)^m<0 and so f must have an odd number of sign changes. If β≤√(3), then by Theorem <ref>, f must have precisely one sign change. For larger values of β, we will see that f may have many changes, but by Theorem <ref>, the sequences
	
    𝒯_e:=(1,a_2,a_4,…,a_2m)

	and
	
    𝒯_o:=(a_1,a_3,…,a_2m+1)

	must each exhibit at most one sign change.
	
	If β=√(2m+1) and r=1+1/m, it is not difficult to calculate that a_2m-1=a_2m=0, and in this case, Theorem <ref> implies a_k>0: k=1,2,…,2m-2, i.e. f has precisely one sign change. Keeping this value of β fixed, we may vary the location of the sign change by increasing r. In particular, with r=2m, we have a_1=a_2=0. We note that, with this value of β, the complex roots of f lie outside of the wedge (<ref>), illustrating the well-known fact that location in this wedge is sufficient, but not necessary, for the coefficients of the polynomial to exhibit one sign change. The fact that two adjacent coefficients of f can vanish simultaneously as r is varied indicates that this value of β is, in a sense, “critical”: if β were increased slightly beyond √(2m+1), it would be possible to find a value of r such that f has three sign changes.
	
	Finally, let us consider an extreme case: if β=2m and
	
    2m<r<2m+1/2m,

	it is not difficult to check that a_1<0 and a_2m>0 (and hence f has the maximal possible number of sign changes).

























amsplain



