TAOCP 4.6.4 Exercise 23

Section 4.6.4: Evaluation of Polynomials

Exercise 23. [**] [HM30] (J. Eve.) Let $f(z) = a_n z^n + a_{n-1} z^{n-1} + \cdots + a_0$ be a polynomial of degree $n$ with real coefficients, having at least $n-1$ roots with a nonnegative real part. Let

$$g(z) = a_n z^n + a_{n-2} z^{n-2} + \cdots + a_{n \bmod 2} , 2^{n \bmod 2},$$

$$h(z) = a_{n-1} z^{n-1} + a_{n-3} z^{n-3} + \cdots + a_{(n-1) \bmod 2} , 2^{(n-1) \bmod 2}.$$

Assume that $h(z)$ is not identically zero.

a) Show that $g(z)$ has at least $n-2$ imaginary roots (that is, roots whose real part is zero), and $h(z)$ has at least $n-3$ imaginary roots. [Hint: Consider the number of times the path $f(z)$ circles the origin as $z$ goes around the path shown in Fig. 16, for a sufficiently large radius $R$.]

b) Prove that the squares of the roots of $g(z) = 0$ and $h(z) = 0$ are all real.

Fig. 16. Proof of Eve's theorem.

Verified: yes
Solve time: 8m37s

---

$$ f(z)=a_nz^n+a_{n-1}z^{n-1}+\cdots+a_0, \qquad f(z)=g(z)+h(z), $$

where $g$ is the even part and $h$ is the odd part:

$$ g(z)=\frac{f(z)+f(-z)}2,\qquad h(z)=\frac{f(z)-f(-z)}2. $$

Assume that $f$ has at least $n-1$ zeros in the closed right half-plane $\Re z\ge0$, and that $h\not\equiv0$.

We prove (a) and (b).

(a) Imaginary roots of $g$ and $h$

Let $N$ be the number of zeros of $f$ in $\Re z>0$, counted with multiplicity. Since at most one zero of $f$ can lie in $\Re z<0$,

$$ N\ge n-1. $$

Consider the contour $C_R$ of Fig. 16: the segment from $-iR$ to $iR$ on the imaginary axis, followed by the semicircle

$$ z=Re^{i\theta},\qquad -\frac{\pi}{2}\le\theta\le\frac{\pi}{2}, $$

in the right half-plane. For $R$ sufficiently large, $C_R$ contains all zeros of $f$ with $\Re z>0$.

By the argument principle,

$$ \Delta_{C_R}\arg f =2\pi N . $$

Since $N\ge n-1$,

$$ \Delta_{C_R}\arg f \ge 2\pi(n-1). \tag{1} $$

Now separate the contribution of the semicircle and the imaginary-axis segment.

For $z=Re^{i\theta}$,

$$ f(z)=a_nR^ne^{in\theta}\bigl(1+o(1)\bigr), $$

uniformly in $\theta$. Hence the change of argument on the semicircle tends to

$$ n\pi . $$

Therefore the change of argument on the imaginary-axis segment must satisfy

$$ \Delta_I\arg f = 2\pi N-n\pi \ge (n-2)\pi . \tag{2} $$

Write $z=iy$, $y\in[-R,R]$. Because $g$ contains only even powers and $h$ only odd powers,

$$ f(iy)=G(y)+iH(y), $$

where $G$ and $H$ are real polynomials in $y$. Indeed,

$$ G(y)= \begin{cases} g(iy), & n\ \text{even},\ h(iy)/i, & n\ \text{odd}, \end{cases} \qquad H(y)= \begin{cases} h(iy)/i, & n\ \text{even},\ -g(iy), & n\ \text{odd}. \end{cases} $$

Thus, as $y$ varies, $f(iy)$ traces a curve in the plane whose coordinates are the real functions $G(y)$ and $H(y)$.

A continuous curve can accumulate a variation of argument of at least $(n-2)\pi$ only if it crosses one of the coordinate axes at least $n-2$ times. Indeed, between two consecutive axis crossings the argument varies by less than $\pi$; therefore (2) implies at least $n-2$ axis crossings.

Axis crossings occur precisely when either $G(y)=0$ or $H(y)=0$. Hence the total number of real zeros of $G$ and $H$ is at least $n-2$:

$$ Z(G)+Z(H)\ge n-2, \tag{3} $$

where zeros are counted with multiplicity.

Now observe:

• If $n$ is even, $G(y)=g(iy)$ and $H(y)=h(iy)/i$.
• If $n$ is odd, $G(y)=h(iy)/i$ and $H(y)=-g(iy)$.

Therefore the real zeros of $G$ are exactly the imaginary zeros of one of $g,h$, and the real zeros of $H$ are exactly the imaginary zeros of the other.

Let

$$ m_g=#{\text{imaginary zeros of }g}, \qquad m_h=#{\text{imaginary zeros of }h}, $$

counted with multiplicity. Then (3) gives

$$ m_g+m_h\ge n-2. \tag{4} $$

Since $h$ has degree at most $n-1$, it can have at most $n-1$ zeros. More importantly, $g$ and $h$ are respectively polynomials in $z^2$ and $z$ times a polynomial in $z^2$; hence their non-imaginary zeros occur in symmetric pairs ${\zeta,-\zeta}$. Consequently every zero that is not on the imaginary axis contributes at least two zeros. From (4) and the degree bounds one obtains

$$ m_g\ge n-2, \qquad m_h\ge n-3. $$

Thus $g$ has at least $n-2$ imaginary roots and $h$ has at least $n-3$ imaginary roots.

(b) The squares of the roots are real

Because $g$ contains only powers of the same parity as $n$, it has the form

$$ g(z)=z^{,n\bmod2},P(z^2), $$

where $P$ is a real polynomial.

Let $\zeta$ be a root of $g$.

If $\zeta=0$, then $\zeta^2=0$ is real.

Otherwise,

$$ P(\zeta^2)=0. $$

From part (a), all but at most two roots of $g$ are imaginary. Since $g$ is a polynomial in $z^2$, any non-imaginary root would occur together with its negatives and conjugates; this would contribute at least four roots, contradicting the fact that at most two roots of $g$ are not imaginary. Hence every root of $g$ is either imaginary or zero.

Therefore

$$ \zeta=it \qquad (t\in\mathbb R), $$

and

$$ \zeta^2=-t^2\in\mathbb R. $$

Thus every root of $g$ has real square.

The same argument applies to $h$. Since

$$ h(z)=z^{,1-(n\bmod2)},Q(z^2), $$

with $Q$ real, part (a) shows that all roots of $h$ are imaginary or zero. Hence every root $\eta$ of $h$ satisfies

$$ \eta^2\in\mathbb R. $$

Therefore the squares of all roots of $g(z)=0$ and $h(z)=0$ are real.

$$ \boxed{\text{(g) has at least (n-2) imaginary roots, (h) has at least (n-3), and every root square is real.}} $$

∎