32
$\begingroup$

$p_0(x)=a_mx^m+a_{m-1}x^{m-1}+\dotsb+a_1x+a_0(a_m,\dotsc,a_1,a_0\in\Bbb R)$ is a polynomial, and

$$p_n(x)=p_{n-1}(x)+p_{n-1}^{\prime}(x),\qquad n=1,2,\dotsc$$

then, there exist $N\in\Bbb N$, such that $\forall n \geq N$, all the roots of $p_n(x)$ are real


I think, let $f_n(x)=e^xp_n(x)$, then

$$f_n(x)=\frac {d(f_{n-1}(x))}{dx} $$

we get that

$$f_n(x)=\frac{d^n\left( e^xp_0(x)\right)}{dx^n}$$

so, If there exists a $p_N(x)$ such that $p_N(x)$ has $m$ real roots, then $\forall n\geq N$, $p_n(x)$ has $m$ real roots.

I'd be grateful for any help

$\endgroup$
  • $\begingroup$ One point of interest, either $p_n(x)$ or $p_n'(x)$ has at least one real root for all $n$. You can use this to guarantee one real root for some $n$ in $p_n(x)$. $\endgroup$ – abiessu Jun 3 '14 at 19:47
  • 4
    $\begingroup$ @user90041 Why? If it's constant, $p_n$ is also constant and has no zeros (or identically zero) and the claim still true (all zeroes real), right? $\endgroup$ – ploosu2 Jun 3 '14 at 20:13
  • 3
    $\begingroup$ Another way to look at this is to notice that $p_n(x)=\sum_{i=0}^n{n\choose i}p_0^{(i)}(x)$ for $p^{(k)}(x)$ the $k$th derivative of $p$ at $x$. $\endgroup$ – abiessu Jun 3 '14 at 20:53
  • 2
    $\begingroup$ @Edwin I believe $p_0(x)$ is just some arbitrary polynomial, and is taken here to be of degree $m$. $\endgroup$ – Bob Pego Jun 6 '14 at 21:17
  • 1
    $\begingroup$ If $p(x)=\prod_i(x+d_i)$ with $d_1<d_2<d_3<\cdots$, and $q(x)=p(x)+p'(x)$, then we easily see that $q(-d_1)>0$, $q(-d_2)<0$, $q(-d_3)>0$ and so on (the signs alternate). Furthermore, as $x\to-\infty$, then $q(x)$ and $p(x)$ have opposite signs. Therefore $q(x)$ has a zero between any pair of consecutive zeros of $p(x)$ (and one extra zero to the left). Thus if we get the zeros to be distinct real numbers after some iteration, then the same will hold from that point on. The OP also had this - using the neat trick with the functions $f_n$. $\endgroup$ – Jyrki Lahtonen Jun 8 '14 at 14:08
15
+50
$\begingroup$

It is true that, for $n$ large enough, $p_n(x)$ will have distinct real roots, which I will prove by induction on $m$.

Before proceding with the proof, let me first state what it shows about the behaviour of $p_n$ as $n$ increases. Assuming the leading coefficient is positive, $p_n^{(m-2)}$ are quadratics with a unique minimum. As $n$ increases, the minimum decreases monotonically until it becomes negative, at which point $p_n^{(m-2)}$ has distinct real roots. Then, $p_n^{(m-3)}$ is a cubic with a local maximum and a local minimum. As $n$ increases further, the local maximum increases until it is positive and the local minimum decreases until it is negative, at which point $p_n^{(m-3)}$ has distinct real roots. More generally, for each $k=0,1,2,\ldots,m-2$, once $p_n^{(k+1)}$ has distinct real roots then $p_n^{(k)}$ has $m-k-1$ local extrema. Further increasing $n$, the local maxima increase monotonically until they are positive and the local minima decrease until they are negative, at which point $p_n^{(k)}$ has distinct real roots. By induction then, $p_n$ eventually has distinct real roots.

Now, to continue with the proof.

For $m=1$, $p_n(x)$ is of first order so always has a real root.

For $m > 1$, we now suppose that the statement holds for polynomials of degree $m-1$. Then, setting $q_n(x)=p_n^\prime(x)$, we have $q_n(x)=q_{n-1}(x)+q_{n-1}^\prime(x)$. By the induction hypothesis, $q_n(x)$ has $m-1$ distinct real roots for all large enough $n$. I'll denote these by $a_{n,1} > a_{n,2} > \cdots > a_{n,m-1}$. These are the turning points of $p_n(x)$. I'll show that the for large $n$, the signs of $p_n(a_{n,1}),p_n(a_{n,2}),p_n(a_{n,3}),\ldots$ are alternating, from which it follows that $p_n$ has $m$ distinct roots.

By scaling, we assume wlog that $p_n(x)$ has leading coefficient $1$ (i.e., it is monic). Then, $q_n$ is positive on $(a_{n,1},\infty)$, negative on $(a_{n,2},a_{n,1})$, positive on $(a_{n,3},a_{n,2}))$, etc. Note that $a_{n,i}$ is a local maximum of $(-1)^ip_n(x)$ (for each $i=1,2,\ldots,m-1$). This means that $$ (-1)^ip_n(a_{n,i}+h)=(-1)^ip_n(a_{n,i})-ch^{2r}+O(h^{2r+1}) $$ for some positive $c$ and positive integer $r$. So, $$ (-1)^ip_{n+1}^\prime(a_{n,i}+h)=-c(2r)(2r-1)h^{2(r-1)}+O(h^{2r-1}). $$ This shows that $(-1)^ip_{n+1}(x)$ is decreasing in a neighbourhood of $a_{n,i}$.

Now, for $i=1,2,\ldots,m-2$, we see that $(-1)^ip_{n+1}(x)$ is increasing at $a_{n,i+1}$ and decreasing at $a_{n,i}$. Hence, it has a local maximum in $(a_{n,i+1},a_{n,i})$, which we will denote by $b_{i}$, so $a_{n,i+1} < b_i < a_{n,i}$ and $(-1)^ip_{n+1}(b_i) > (-1)^ip_{n+1}(a_{n-i})$. Similarly, $(-1)^{m-1}p_{n+1}(x)$ is decreasing at $a_{n,m-1}$ and (as $p_{n+1}$ is monic of degree $m$), it tends to $-\infty$ as $x\to-\infty$. Hence, it has a local maximum, $b_{m-1}$ in the range $(-\infty,a_{n,m-1})$. So, $b_{m-1} < a_{n,m-1}$ and $(-1)^ip_{n+1}(b_{m-1}) > (-1)^ip_{n+1}(a_{n,m-1})$. As $b_1 > b_2 > \cdots > b_{m-1}$ are roots of $p_{n+1}^\prime(x)$, we have $a_{n+1,i}=b_i$.

So far, we have shown that $$ a_{n,1} > a_{n+1,1} > a_{n,2} > a_{n+1,2} > a_{n,3} > \cdots > a_{n,m-1} > a_{n+1,m-1} $$ and, for each $i$, $(-1)^ip(a_{n,i})$ is strictly increasing in $n$. If, for each fixed $i$, it can be shown that there is an $\epsilon > 0$ with $(-1)^ip_{n+1}(a_{n+1,i})\ge(-1)^ip_n(a_{n,i})+\epsilon$ for all large $n$ then, for $n$ large enough, $(-1)^ip_n(a_{n,i})$ will be positive. So, the signs of $p_n(a_{n,1}),p_n(a_{n,2}),\ldots$ will be alternating in sign and we are done. Let us proceed by contradiction and assume to the contrary that $(-1)^ip_{n+1}(a_{n+1,i})< (-1)^ip_n(a_{n,i})+\epsilon$ (for small enough $\epsilon$ this will give a contradiction regardless of $n$).

If $i < m-1$ then $(-1)^ip_{n+1}(x)\le(-1)^ip_{n+1}(a_{n+1,i})$ on $(a_{n,i+1},a_{n,i})$. Setting $a_{n,m}=-\infty$ then this also holds for $i=m-1$. By the assumption, $(-1)^ip_{n+1}(x)\le(-1)^ip_{n}(a_{n,i})+\epsilon$ in this range so, setting $f(x)=(-1)^i(p_n(a_{n,i})-p_{n}(x))\ge0$, $$ f(x)+f^\prime(x)=(-1)^i(p_n(a_{n,i})-p_{n+1}(x))\ge-\epsilon. $$ Therefore, $$ f(x)=-\int_x^{a_{n,i}}\frac{d}{dy}(e^{y-x}f(y))dy =-\int_x^{a_{n,i}}e^{y-x}(f(y)+f^\prime(y))dy\le\epsilon\int_x^{a_{n,i}}e^{y-x}dy=\epsilon(e^{a_{n,i}-x}-1). $$ This shows that in the range $(a_{n,i+1},a_{n,i})$, \begin{align} \lvert p_{n}(x)-p_n(a_{n,i})\rvert\le\epsilon(e^{a_{n,i}-x}-1).&&{\rm(1)} \end{align} So, $p_n$ is almost constant here for $\epsilon$ small. I'll need the following lemma, which I'll prove in a moment.

Lemma: Let $p$ be a monic polynominal of degree $m\ge1$. Then, for each $a < b$ we have $$ sup_{x\in(a,b)}\lvert p(x)-p(b)\rvert\ge L(b-a)^m. $$ where $L$ is a constant depending only on $m$.

We can apply this to (1). For the case $i=m-1$ and any $K>0$, apply to the range $[a_{n,m-1}-K,a_{n,m-1}]$ to get $$ \epsilon(e^K-1)\ge L K^{m} $$ which gives a contradiction if $\epsilon$ is small enough. On the other hand, for $i< m-1$, $(-1)^i(p_n(a_{n,i})-p_n(a_{n,i+1})$ is positive and increasing in $n$ for all large enough $n$, so is greater than some fixed $\delta$. Applying (1), $$ \delta\le (-1)^i(p_{n,i}(a_{n,i})-p_{n,i}(a_{n,i+1}))\le\epsilon(e^{a_{n,i}-a_{n,i+1}}-1). $$ Assuming that $\epsilon \le 1$, we choose $K > 0$ such that $\delta\ge e^K-1$. Then, $K\le a_{n,i}-a_{n,i+1}$ and we can apply the lemma to the range $[a_{n,i}-K,a_{n,i}]$ to get $$ \epsilon(e^K-1)\ge LK^m $$ again, giving a contradiction for small $\epsilon$. QED


I'll now prove the lemma. For any $\epsilon\in\mathbb{R}$ define the linear operator $T_\epsilon$ of the functions $f\colon\mathbb{R}\to\mathbb{R}$ by $T_\epsilon f(x)=f(x+\epsilon)$. If $f$ is a polynomial of degree $m$ with leading coefficient $c$, then $T_\epsilon f-f$ is a polynomial of degree $m-1$ with leading coefficient $mc\epsilon$. Hence, $(T_\epsilon-1)^mf(x)=m!c\epsilon^m$. On the other hand $\lVert T_\epsilon\rVert=1$ and $(T_\epsilon-1)^mf(x)$ only depends on the values of $f(y)$ with $y$ in the range $[x,x+m\epsilon]$. So, for a monic polynomial $f$ of degree $m$, $$ m!\epsilon^m=(T_\epsilon-1)^mf(x)\le 2^m\sup_{y\in[x,x+m\epsilon]}\lvert f(y)\rvert $$ If $p$ is a monic polynomial of degree $m$ and $a < b$, then taking $f(y)=p(y)-p(b)$, $x=a$ and $\epsilon=(b-a)/m$ gives the lemma with $L=m!(2m)^{-m}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How do you go from $ P_n (x+h) = A+b h^{2n}(1+o(1))$ to $P_{n+1}^\prime = c -d h^{2r-2}(1+o(1))$ - you just write 'So'? $\endgroup$ – username Jun 11 '14 at 9:56
  • $\begingroup$ I just plugged in the definitions (unless I made a mistake), but I'm going to change this bit anyway when I edit the answer later. $\endgroup$ – George Lowther Jun 12 '14 at 10:40
  • $\begingroup$ Nice proof. More concise and elegant than mine. +1 $\endgroup$ – Krokop Jun 13 '14 at 11:38
  • $\begingroup$ I am really grateful for your help $\endgroup$ – Clin Jun 13 '14 at 19:38
9
$\begingroup$

Not a solution at all, so (down)vote accordingly. Just writing down whatever my toying with Mathematica suggests in the hope that it may inspire somebody else. I think this line of attack should lead to a solution, but it does require careful estimates. Hopefully a more clever method is out there.

The formula in Abiessu's comment shows that the transformation $T_n:p_0\mapsto p_n$ is linear (this could also be proven directly). A more careful look at that formula reveals that for large $n$ the coefficients coming from the leading term, i.e. $T_n(a_mx^m)$, will dominate the other terms. In a way (that needs to be made more precise) this suggests that the zeros of $T_n(p)$ are close to the zeros of $$T_n(x^m)=x^m+m{n\choose 1}x^{m-1}+m(m-1){n\choose 2}x^{m-2}+\cdots$$

So I propose the following attack:

  • Show that for large enough $n$ the polynomial $G_n:=T_n(x^m)$ has $m$ distinct zeros, and that the derivative $G_n'$ has a large enough absolute value at these zeros.
  • Show that the difference $|a_m G_n(x)-p_n(x)|$ is small enough (in comparison to $G_n'(x)$) near the zeros of $G_n$ so that we can conclude $p_n$ to also have a zero in the vicinity.

Testing shows that the zeros of $G_n$ will be "near" $x=-n$ for a suitable definition of "near". This is hardly a surprise as it follows from the definitions that $$ \lim_{n\to\infty}\frac{G_n(nx)}{n^m}=(x+1)^m. $$ I checked what happens with $$ p_0(x)=(x^2+1)(x^2+4)=x^4+5x^2+4. $$ Since I went up to $n=50$ (way overkill, the condition is fulfilled much earlier) I will share a few plots with you. Here are the plots of $p_{50}$ and $G_{50}$. You see that at this resolution they nearly coincide.

enter image description here

Here's a close up of the neighborhood of one of the zeros.

enter image description here


Edit: I think I figured out a useful scaling. Consider the polynomial (changing the notation a bit, as I need double indexing) $$ F_{m,n}=T_n(x^m):=\sum_{i=0}^n\frac{m! n! i!}{(m-i)! (n-i)!}x^{m-i}. $$ Let's do the translation that John Mangual also studied, and scale the variable by $\sqrt n$, and define $$ H_{m,n}:=\frac1{n^{m/2}}F_{m,n}(\sqrt n x-n). $$ I'm well on my way to proving (not there yet, but I have computer justification for $m\le5$, and some useful looking identities) that $$ \lim_{n\to\infty}H_{m,n}(x)=He_m(x), $$ where $He_m(x)$ is the so called probabilist's Hermite polynomial of degree $m$. I would be surprised if this were not either known or easily deduced from known facts.

Anyway, I conjecture that the zeros $z_{i,n}, i=1,2,\ldots,m$, of $p_n(x)$ can be numbered in such a way that the limits $$ z_i=\lim_{n\to\infty}\frac{z_{i,n}+n}{\sqrt n} $$ exist, and are the zeros of $He_m(x)$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This is nice, and I think I have a proof of the conjectured limit. $\endgroup$ – George Lowther Jun 11 '14 at 18:33
  • $\begingroup$ Great, @George! I tried this a bit more, but couldn't make any headway. $\endgroup$ – Jyrki Lahtonen Jun 11 '14 at 18:37
  • $\begingroup$ I'll post a proof later when I log on. One way is to use the central limit theorem, explaining the appearance of the probabilists Hermite polynomial. $\endgroup$ – George Lowther Jun 12 '14 at 10:39
  • $\begingroup$ @GeorgeLowther: I should post that as a separate question, so that you get due credit? It will have to wait for a couple of hours though. $\endgroup$ – Jyrki Lahtonen Jun 12 '14 at 11:47
  • $\begingroup$ You could do, or I can answer here. I'm not going to be able to post an answer until later tonight anyway (in about 10-11 hours time) $\endgroup$ – George Lowther Jun 12 '14 at 11:55
9
+100
$\begingroup$

Another approach.

I will prove the result step by step.

  1. $$\sum_{j=0}^m (-1)^j \binom{m}{j}j(j-1)\cdots(j-k+1)=0$$ if $0\leqslant k\leqslant m-1$, and $m!$ if $k=m$.

Proof.

Use $j\binom{m}{j}=m\binom{m-1}{j-1}$.

2-$$\sum_{j=0}^m (-1)^j \binom{m}{j}j^k=0$$ if $0\leqslant k\leqslant m-1$, and $m!$ if $k=m$.

Proof.

Follows from Step $1$ by linearity.

3-$$\sigma_k(1,2,\ldots,j-1)$$ is polynomial of degree $2k$ on $j$ with leading coefficient $\dfrac{1}{2^k k!}$.

Proof.

This is shown by induction using Newton's identities

4-$$\sum_{j=0}^m (-1)^j\binom{m}{j}\sigma_k(1,2,\ldots,j-1)=0$$ if $2k<m$, and $1\times 3\times\cdots (m-1)$ if $2k=m$.

Follows from Step $2$ and $3$

5 $$\sum_{j=0}^m (-1)^j \binom{m}{j}(1-\frac{1}{n})\cdots (1-\frac{j-1}{n})$$ is equivalent when $n\rightarrow +\infty $ to $(-n)^{-m/2}\times 1\times 3\times\cdots (m-1)$ if $m$ is even and, et is $o(n^{-m/2})$ if $m$ is odd.

Proof.

Just develop the product and use step $4$.

6- For $p_0(x)=x^m$, $p_n(-n)$ is equivalent to $(-n)^{m/2}\times 1 \times 3\times\cdots\times (m-1)$ if $m$ is even, and $p_n(-n)=o(n^{m/2})$ if $m$ is odd.

Proof.

Use $p_n(x)=\sum_{j=0}^m \binom{n}{j}m(m-1)\cdots (m-j+1)x^{m-j}=\binom{m}{j}n(n-1)\cdots (n-j+1)x^{m-j}$ and substitute $x=-n$ to return to step $5$.

7-Denote $q_{m,n}(x)=n^{-m/2}p_{m,n}(-n+x\sqrt{n})$ with $p_0=x^m$ We show by induction on $n$ as $q_ {m, n} $ converges to the Hermite polynomial $H_m $ when $n$ tends to infinity.

For $n=0$ is obvious.

Suppose the assertion true at rank <$ n $. Then she is true for $\frac{1}{m}p'_{m,0}(x)=x^{m-1}=p_{m-1,0}$.

As the derivation commutes with the transformation $p_0\mapsto p_n$, we have $p'_{m,n}=mp_{m-1,n}$.

It comes $q'_{m,n}=mq_{m-1,n}$, thus $q'_{m,n}$ converges to $mH_{m-1}=H'_m$ as $m$ tends to $+\infty$.

Using step $6$ we have $q_{m,n}(0)$ converges to $H_m(0)$.

8- The result of step 7 is true for any monic polynomial of degree $m$ instead of $p_0$.

Finally, We boils down to $p_0$ unitary. By continuity of the roots in the coefficients of a polynomial and the fact that the Hermite polynomials are divided to simple roots over $\mathbb{R}$, $p_n$ is also for $n$ large enough after step $8$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Nice. Another proof of convergence to the Hermite polynomials, which Jyrki posted as a separate question (math.stackexchange.com/q/832186/11619). I posted a probabilistic proof there. $\endgroup$ – George Lowther Jun 13 '14 at 12:34
  • $\begingroup$ Very nice, indeed. You could have kept it there, too. Your call, of course. $\endgroup$ – Jyrki Lahtonen Jun 13 '14 at 19:37
  • $\begingroup$ @JyrkiLahtonen BTW Thank you so much for the bounty. $\endgroup$ – Krokop Jun 16 '14 at 17:46
4
$\begingroup$

Let's recall two observations in this discussion:

  • $\displaystyle f_n(x)=\frac{d^n\left( e^xp_0(x)\right)}{dx^n}$

  • $\displaystyle p_n(x)=\sum_{i=0}^n{n\choose i}p_0^{(i)}(x)$

Notice also, the degree never goes up $\deg p_n = \deg p_0 = m$ for all $n \geq 0$. Then

$$ \sum_{k=0}^n{n\choose k}p_0^{(k)}(x) = \sum_{k=0}^m{n\choose k}p_0^{(k)}(x) \approx \sum_{k=0}^m \frac{n^k}{k!}p_0^{(k)}(x) = p_0(x+n) $$

where $m << n$. In this regime, we estimate the binomial coefficient by: $ \binom{n}{k} \approx \frac{n^k}{k!}$ and then use Taylor formula.


Notice this only holds asymptotically for $n >> 1$ we get $p_n(x) \approx p_0(x+n)$. Then I wasn't agreeing with Clin's conjecture since $p_0(x)$ may not always have real roots, e.g. $p_0(x) = x^2 + 1$. In fact $p_n(x) = (x+n)^2 - n + 1$.


A second-order estimate gives $p_n(x) \approx p_0(x+n) - n \,p''_0(x+n)$...

Does $p_0(x) - n \, p_0''(x)$ have all real roots for $n$ sufficiently large?

Generically we can write $p_0(x) = x^m + ax^{m-2} + \dots$ so that $p_n(x-n) \approx x^m - n \times m(m-1)x^{m-2} + \dots$

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I agree with the observation that we are "approximately moving the plot to the left by one position at each iteration", but IMO you're putting too much faith in the approximation. It is easy to verify the claim for $p_0(x)=x^2+1$, you only need to go to $p_2(x)=x^2+4x+3$ to get one that has two distinct real zeros. I have tested it for several other positive definite choices for $p_0$. $\endgroup$ – Jyrki Lahtonen Jun 8 '14 at 19:18
  • 1
    $\begingroup$ @JyrkiLahtonen $p_n(x) = (x+n)^2 - n + 1$, I guess you are right. $\endgroup$ – cactus314 Jun 8 '14 at 19:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.