Real roots and interlacing
by HroK, Jul 22, 2012, 6:44 AM
The intermediate value theorem and Rolle's theorem are ubiquitous principles in the analysis of real roots of continuous and differentiable functions, respectively.
As the reader is likely familiar with the most standard uses of these theorems, we briefly discuss the phenomenon of interlacing functions
with alternating real roots. (For a much more unified coverage, see Steve Fisk's paper "Polynomials, roots, and interlacing".) In particular, we look at polynomial recurrences, which provide some of the most natural examples of interlacing.
Example: The
Hermite polynomial
has all real roots (by induction one easily verifies that
is a polynomial of degree
).
Solution: We induct to show that for every
,
has exactly
roots, where the base case is obvious. But if for some
we assume that
has
real roots
, then noting that
are also roots and
, we're done by Rolle's theorem. Obseve that
interlace, i.e. the roots of
lie in between those of
.
Of course, there are several variations on the same idea. For example, if we have a recurrence like
and we know that
interlace, then under some mild conditions we can show via the IVT that
and
also interlace (of course, we need
to have degrees within one of each other). This is in essence the idea behind, for instance, Sturm's theorem.
Now for some problems, (very) roughly arranged in difficulty order!
1. (Steve Fisk) Suppose
are sequences of reals where all
are positive and the
are unrestricted. Define a sequence of polynomials recursively by
,
, and
for
. Show that
has all real roots for every positive integer
.
2. Prove Sturm's theorem.
3. (ELMO Shortlist 2012) Prove that any polynomial of the form
(
) has at least
non-real roots (counting multiplicity), where the
(
) are real and
.
4. Prove Newton's inequalities.
Hint
5. (Descartes' rule of signs) For a polynomial
, let
denote the number of positive zeros and
the number of sign changes.
a) Show that
.
b) Prove that
by writing
for some positive real root
of
and inducting on
.
c) Prove that
by considering the derivative
(assuming WLOG that
) and inducting on
.
6. (Classical) Show that out of all monic polynomials of a fixed degree
,
attains the smallest maximum absolute value on the interval
, where
denotes the
Chebyshev polynomial of the first kind.
7. (MOP 1999) Given
points on the unit circle such that the product of the distances from any point on the circle to the given points does not exceed 2, prove that the points must be vertices of a regular
-gon.
8. (MOP 2001) Let
be a real-valued polynomial with
. Show that there exist at least
distinct (unordered) pairs of distinct real numbers
such that
and
. Does this necessarily hold if we allow
to be any continuous function?
9. (USAMO 2002) Prove that any monic polynomial of degree
with real coefficients is the average of two monic polynomials of degree
with
real roots.
10. (MOP 2007) Let
be a real number. Prove that every nonreal root of
lies on the unit circle and
has at most 2 real roots.
11. (ELMO Shortlist 2011) If
for some positive integer
and complex
, show that two of
have the same magnitude.
Hint
12. ("Enzo", MathOverflow) For
, let
Prove that
is a polynomial of degree
with every root real and strictly greater than 2.
Hint
As the reader is likely familiar with the most standard uses of these theorems, we briefly discuss the phenomenon of interlacing functions

Example: The

![\[H_n(x)=(-1)^n e^{x^2}\frac{d^n}{dx^n}e^{-x^2}\]](http://latex.artofproblemsolving.com/5/6/2/562ce7f533dabec9fbdb9c94c7f13e18e88faf9c.png)


Solution: We induct to show that for every













Of course, there are several variations on the same idea. For example, if we have a recurrence like





Now for some problems, (very) roughly arranged in difficulty order!
1. (Steve Fisk) Suppose









2. Prove Sturm's theorem.
3. (ELMO Shortlist 2012) Prove that any polynomial of the form






4. Prove Newton's inequalities.
Hint
Reduce the problem to the case
.

5. (Descartes' rule of signs) For a polynomial
![$p\in\mathbb{R}[x]$](http://latex.artofproblemsolving.com/2/f/e/2fe31a8d27bf49ac7e1b43285e29e406e2e4f5d3.png)


a) Show that

b) Prove that





c) Prove that




6. (Classical) Show that out of all monic polynomials of a fixed degree


![$[-1,1]$](http://latex.artofproblemsolving.com/3/9/f/39f506ebeeeb72f62147990614a67f4e30b7c751.png)


7. (MOP 1999) Given


8. (MOP 2001) Let







9. (USAMO 2002) Prove that any monic polynomial of degree



10. (MOP 2007) Let



11. (ELMO Shortlist 2011) If




Hint
Scale so that
, and let
...


12. ("Enzo", MathOverflow) For

![\[P_n(x)=x^{n+1}\left[\frac{\partial^{2n+1}}{\partial z^{2n+1}}\frac{\sinh(z)}{\cosh(z)-1+x}\right]_{z=0}.\]](http://latex.artofproblemsolving.com/7/b/9/7b94300cbf8ca7f439bf7de25e90d3daf29f7862.png)


Hint
Let
, and find a recursion involving the
.


This post has been edited 11 times. Last edited by HroK, Jun 2, 2014, 8:52 AM