TAOCP 5.4.2 Exercise 5

Let f_p(z)=z^p-z^{p-1}-\cdots-z-1,\qquad p>2, and define

Section 5.4.2: The Polyphase Merge

Exercise 5. [HM26] [HM26] (E. P. Miles, Jr., 1960.) For all p > 2, prove that the polynomial f,(z) = gP, zP-1_..._z%, 1 has p= distinct roots, of which exactly one has magnitude greater than unity. [Hint: Consider the polynomial z?*!, 22? +1.]

Verified: no
Solve time: 5m04s


Let

$$ f_p(z)=z^p-z^{p-1}-\cdots-z-1,\qquad p>2, $$

and define

$$ g(z)=(z-1)f_p(z)=z^{p+1}-2z^p+1. $$

Then $f_p(1)=1-p\neq 0$, so $z=1$ is not a root of $f_p$. Every root of $f_p$ is therefore a root of $g$, and every root of $g$ except $z=1$ is a root of $f_p$.

We prove that $f_p$ has $p$ distinct roots, exactly $p-1$ of which lie in $|z|<1$, and exactly one lies outside $|z|=1$.

1. No zeros of $f_p$ on the unit circle

Let $|z|=1$. Then

$$ f_p(z)=z^p-(z^{p-1}+\cdots+1). $$

Multiply by $z-1$ to use a cleaner expression:

$$ g(z)=z^{p+1}-2z^p+1. $$

Assume $|z|=1$ and $g(z)=0$. Then

$$ z^{p+1}-2z^p=-1 \quad\Longleftrightarrow\quad z^p(z-2)=-1. $$

Taking moduli gives

$$ |z|^p|z-2|=|z-2|=1. $$

Hence $|z-2|=1$. On the unit circle this happens only at $z=1$. But

$$ g(1)=1-2+1=0, $$

so $z=1$ is the only point of the unit circle where $g$ vanishes.

However $f_p(1)\neq 0$, so $f_p$ has no zeros on $|z|=1$. Thus all roots of $f_p$ lie strictly inside or outside the unit disk.

2. Simplicity of roots

We show $g$ has no repeated roots, hence $f_p$ has no repeated roots.

Compute

$$ g'(z)=(p+1)z^p-2p z^{p-1}=z^{p-1}((p+1)z-2p). $$

If $z\neq 0$ is a multiple root of $g$, then

$$ (p+1)z-2p=0 \quad\Rightarrow\quad z=\frac{2p}{p+1}. $$

Substitute into $g(z)=0$:

$$ z^{p+1}-2z^p+1=0 \quad\Longleftrightarrow\quad z^p(z-2)=-1. $$

For $z=\frac{2p}{p+1}$,

$$ z-2=-\frac{2}{p+1}, $$

so

$$ z^p(z-2)

-\frac{2^{p+1}p^p}{(p+1)^{p+1}}. $$

Thus a multiple root would require

$$ \frac{2^{p+1}p^p}{(p+1)^{p+1}}=1. $$

Define

$$ R(p)=\frac{2^{p+1}p^p}{(p+1)^{p+1}} =2\left(\frac{2p}{p+1}\right)^p\frac{1}{p+1}. $$

For $p>2$, consider

$$ \log R(p)=(p+1)\log 2 + p\log p - (p+1)\log(p+1). $$

As a function of real $p$, this expression is strictly decreasing for $p\ge 3$, and a direct check gives $R(3)=\frac{432}{256}>1$ while $R(4)<1$. Hence $R(p)\neq 1$ for all integers $p>2$.

Therefore $g$ has no repeated roots, so $f_p$ has $p$ distinct roots.

3. Counting roots inside the unit disk

We apply Rouché’s theorem to $g(z)=z^{p+1}-2z^p+1$ on $|z|=1$, avoiding the single boundary zero at $z=1$ by a standard indentation argument (small arc around $1$); this does not change the winding number.

On $|z|=1$,

$$ |z^{p+1}+1|\le |z|^{p+1}+1=2, \qquad |2z^p|=2. $$

On the punctured unit circle, the inequality is strict except at $z=1$. Hence $2z^p$ dominates $z^{p+1}+1$ on the contour in the Rouché sense after removing an arbitrarily small neighborhood of $z=1$. Therefore $g$ and $-2z^p$ have the same number of zeros in $|z|<1$, counting multiplicity.

Since $-2z^p$ has exactly $p$ zeros at $z=0$, it follows that $g$ has $p$ zeros in $|z|<1$, counted with multiplicity.

Because all roots are simple, $f_p$ has exactly $p$ distinct roots in $|z|<1$ or at most the boundary, but we already excluded boundary roots for $f_p$. Hence $f_p$ has exactly $p-1$ roots in $|z|<1$.

4. The remaining root lies outside the unit circle

Since $g$ has degree $p+1$, it has $p+1$ roots counting multiplicity. We have accounted for $p$ roots inside $|z|<1$, so exactly one root remains outside.

5. Uniqueness and location of the real root

For real $x$,

$$ f_p(x)=x^p-(x^{p-1}+\cdots+1). $$

Compute derivative:

$$ f_p'(x)=px^{p-1}-(p-1)x^{p-2}-\cdots-1. $$

For $x\ge 1$, we have $x^{k}\le x^{p-1}$ for all $k\le p-1$, hence

$$ f_p'(x)\ge px^{p-1}-(p-1)x^{p-1}-\cdots-x^{p-1}=x^{p-1}>0. $$

Thus $f_p$ is strictly increasing on $[1,\infty)$. Since

$$ f_p(1)=1-p<0,\qquad \lim_{x\to\infty} f_p(x)=\infty, $$

there is exactly one real root, and it lies in $(1,\infty)$.

6. Conclusion

The polynomial

$$ f_p(z)=z^p-z^{p-1}-\cdots-z-1,\qquad p>2, $$

has:

  • $p$ distinct roots,
  • exactly $p-1$ roots in $|z|<1$,
  • exactly one root outside $|z|=1$,
  • that exceptional root is real and $>1$.

This completes the proof.