7

Let $p:\mathbb{R}\rightarrow\mathbb{R}$ be a polynomial function with real coefficients satisfying \begin{align} p(x_1)<0, p(x_2)>0, p(x_3)<0,\ldots \text{(sign flips in alternating manner)} \end{align} for $x_1<x_2<\ldots<x_n$. Even without polynomial assumption, by virtue of intermediate value theorem (IVT), it is apparent that there are at least $n-1$ distinct real roots—precisely, at least one root in each interval $(x_k,x_{k+1}), k=1,\ldots,n-1$.

Replacing all strict inequalities with non-strict counterparts, that is, \begin{align} p(x_1)\leq0, p(x_2)\geq0, p(x_3)\leq0,\ldots \text{(sign flips in alternating manner)}, \end{align} we can again guarantee that there are at least $n-1$ real roots in $[x_1,x_n]$ when taking multiplicity into account. Let us commence (somehow dirty) derivation with strong induction on $n$.

Base case: The base case $n=2$ is trivial: if either $p(x_1)$ and $p(x_2)$ is zero, we are done; otherwise, applying IVT works out.

Induction step: Assume that the claim holds for $n<m$ and consider the case $n=m$. Let us divide and conquer the problem.
i) $p(x_1)=0$: $x_1$ is a root, and there are at least $m-2$ roots in $[x_2,x_m]$ from induction hypothesis.
ii) $p(x_1)<0$, $p(x_2)>0$: There is at least one root in $(x_1,x_2)$ by IVT, and there are at least $m-2$ roots in $[x_2,x_m]$ from induction hypothesis.
iii) $p(x_1)<0$, $p(x_2)=0$: We further divide into three cases:
iii-a) $p'(x_2)=0$: $x_2$ is a root with multiplicity 2, and there are at least $m-3$ roots in $[x_3,x_m]$ from induction hypothesis.
iii-b) $p'(x_2)>0$: We can find $x_2'\in(x_2,x_3)$ such that $p(x_2')>0$. Applying the inductive hypothesis to $x_2',x_3,\ldots,x_m$, there are at least $m-2$ roots in $[x_2',x_m]$. Together with $x_2$, there are at least $m-1$ roots in $[x_2,x_m]$.
iii-c) $p'(x_2)<0$: We can find $x_2'\in(x_1,x_2)$ such that $p(x_2')>0$. Therefore, there is at least one root in $(x_1,x_2')$ by IVT. Together with $m-2$ roots in $[x_2,x_m]$ where the existence is guaranteed by induction hypothesis, we have $m-1$ roots in $[x_1,x_m]$.

I reckon that the statement of the claim is intuitive whereas my proof described above is unnecessarily complicated. Hence, my question is twofold:

  1. Is there any simple and elegant proof of this claim?
  2. Is there any name referring to this claim?

Any comments would be much appreciated.

Heedong Do
  • 339

2 Answers2

2

Here's a somewhat simpler proof, although I'm still not completely happy with it. We still use induction, with the base cases of $n=1$ (vacuous) and $n=2$ (easy). Now:

  1. If the polynomial is the zero polynomial, the claim is (somewhat vacuously) true.

  2. If the polynomial has a double root at $x_i$ for some $i$, then $p(x)/(x-x_i)^2$ satisfies the same alternating properties with respect to $[x_1,\dots,x_{i-2},x_{i\pm 1},x_{i+2},\dots,x_n]$, where the $\pm$ is chosen arbitrarily so that $1\leq i\pm 1\leq n$ (i.e. if $i=1$, we choose $+$, and if $i=n$ we choose $-$). So, we may proceed by an inductive hypothesis with $n$ replaced by $n-2$.

  3. If none of the $x_i$ are double roots, define $x_i'=x_i$ if $p(x_i)\neq 0$ or if $i\in\{1,n\}$. For $1<i<n$ with $p(x_i)=0$, select $x_i'=x_i+\epsilon$ or $x_i'=x_i-\epsilon$ (with the $\pm$ depending on the sign of $p'(x_i)$) for some small $\epsilon$, so that the sign of $p(x_i')$ is as desired, (as there are only finitely many roots, a small enough $\epsilon$ guarantees that the signs of $p(x_i\pm \epsilon)$ is the sign of $\pm p'(x_i)$). Now, apply the intermediate value theorem, possibly selecting $x_1$ or $x_n$ as the "intermediate" values.

Carl Schildkraut
  • 32,931
1

Please treat this as comments.

  1. Classically there is the Sturm's Theorem that completely determines the number of real roots of a polynomial over the reals. But this does not seem to be directly relevant to your formulation.

  2. The following is a generalization of the result and simplification of your argument.

Proposition. Let $f(x)$ be a continuous function on $[x_1,x_n].$ Assume that $f'(x)$ exists at $x_i$'s with $i=2,\cdots,n-1,$ where $$x_1<x_2<\cdots<x_{n-1}<x_n,$$ and furthermore the signs of $a_i:=f(x_i)$'s exhibit alternating pattern as follows: $$(-1)^ia_i\geq 0~{\rm or~}(-1)^ia_i\leq 0,i=1,\cdots,n.$$ Then $f(x)$ has at least $n-1$ roots on the interval $[x_1,x_n],$ counting multiplicity.

Proof. One proves this by induction on $n$ with respect to the set $\{x_1,\cdots,x_n\}$. Without loss of generality, one starts with the sign pattern $f(x_1)\leq 0$. The cases when $n=1,2$ are clear. Now for $n\geq 3,$ one considers the mutually exclusive cases:

$A_1.$ If there exists $x_1'\in [x_1,x_2)$ such that $f(x_1')=0,$ then the case is reduced to $\{x_2,\cdots,x_n\}$ for $f$ on $[x_2,x_n],$ for one gets a root $x_1'$ and at least $n-2$ roots from the induction hypothesis.

$A_2.$ If $f(x)<0$ on $[x_1,x_2),$ then by continuity of $f$, one has $f(x_2)=0.$ (Note that if $A_1$ is not true, one would necessarily have $A_2$ because of IVT.) One considers the following mutually exclusive subcases:

$\qquad b_1.$ There exists $x_2'\in (x_2,x_3)$ such that $f(x_2')\geq 0.$ Then similar to $A_1,$ this is reduced to $\{x_2',x_3,\cdots,x_n\}$ for $f$ on $[x_2',x_n]$.

$\qquad b_2.$ $f(x)<0$ on $(x_2,x_3)$ hence on $(x_1,x_3)$ except at $x_2$, where $f(x_2)=f'(x_2)=0,$ since $f(x_2)=0$ is a local maximum on $(x_1,x_3).$ Then this is reduced to $\{x_3,\cdots,x_n\}$ for $f$ on $[x_3,x_n],$ for one gets at least a double root $x_2$ and at least $n-3$ roots for $f$ on $[x_3,x_n]$ from the induction hypothesis. QED

Pythagoras
  • 7,079