7
$\begingroup$

Let us define the following sequence of polynomials for every two non-negative integers $i,d$: $$s_i^d(w)=\sum_{j=0}^{d+1} (-1)^j {d+1\choose j} (j+1)^i w^{d+1-j}.$$ Conjecture: The sequence $\{s_d^d(w),s_d^{d-1}(w),\dots,s_d^0(w)\}$ is a Sturm sequence.

An easy corollary of this conjecture is that:

Corollary: For $i\geq d$, the roots of the polynomial $s_i^d(w)$ are all real, simple (and positive).

Any idea how to prove either the Conjecture or (directly) the Corollary? Or, in the worst case, the Corollary for the special case $i=d$?

Note that:

  1. $s_0^d(w)=(w-1)^{d+1}$
  2. $s_i^0(w)=w-2^i$
  3. ${d\over dw} s_i^d(w)=(d+1)s_i^{d-1}(w)$.
$\endgroup$
5
  • $\begingroup$ In what context do these polynomials appear? If you remove the (-1)^j part, it should still be a Sturm sequence, but with non-negative coefficients. Do these coefficients count something? $\endgroup$ Oct 17, 2012 at 19:25
  • $\begingroup$ Shouldn't property 3 have just the factor $(d+1)$, without factorial? $\endgroup$ Oct 17, 2012 at 22:46
  • $\begingroup$ @Pietro Majer: yes absolutely, corrected. Thanks! $\endgroup$
    – dima
    Oct 18, 2012 at 10:02
  • $\begingroup$ @Peter: of course, just corrected. $\endgroup$
    – dima
    Oct 18, 2012 at 10:12
  • $\begingroup$ These polynomials appear as first-order approximations in some nonlinear reconstruction problems, see e.g. arxiv.org/abs/1005.1884. If we substitute $t=-w$ we get a polynomial with positive coefficients and preserving the multiplicities of the roots. So, if positive-coefficient sequence is Sturm, it should be sufficient for our purposes. $\endgroup$
    – dima
    Oct 18, 2012 at 15:26

1 Answer 1

7
$\begingroup$

This is just a partial answer, but anyway: ( I use $s[n,k]$ for $s^n_k$ since I just copy-pasted from Mathematica:

I do not know if this helps, or if you already know, but you have the recurrence $$s[n- 1,k + 1] = s'[n, k] - x \cdot s'[n - 1, k]$$

Note, by induction, we assume $s[n,k]$ and $s[n-1,k]$ to have interlacing roots. By thm 1.47 in http://arxiv.org/abs/math/0612833 (look into this work), we know that the derivatives have interlacing roots as well.

Now, the recursion is quite similar to many other that appear in the link above, so it might not be too hard to prove stability.

EDIT: I show/sketch below that the operator $f \mapsto A f - x f'$ always produce roots interlaced (and to the right) of the roots of $f$, provided $A>\deg f$ and that all roots of $f$ are positive. (We may assume leading term of $f$ has positive coefficient).

Clearly if f has a root of multiplicity m, then the result will have the same root with multiplicity m-1, so the problem is essentially to ensure that no new multiple roots may appear.

Assume now we have two consecutive roots $0\le a \le b$ of $f$ and that $f$ is positive between these. The derivative of $f$ this first positive, and then negative in $[a,b]$, thus $-x f'$ is first negative and then positive. Hence, $A f - x f'$ is negative in $a$, and positive in $b.$ Thus, we have a root of $A f - x f'$ in the interval $[a,b]$. (Mutatis mutandis for the case when f is negative between $a$ and $b$).

Now, if the degree of $f$ is even, $f$ is positive to the right of its largest root. The derivative is also positive here (since even degree poly), so $x f'$ is positive. Hence, $A f - x f'$ is negative in this point. However, notice this is a polynomial with even degree, and with a leading coefficient! Hence, it must eventually cross the real line and grow to infinity. (Mutatis mutandis for the case when f is odd).

This proves that $f \mapsto A f - x f'$ produces interlacing roots, and eventual multiplicities are decreased, no new multiple roots can be introduced.

$\endgroup$
7
  • $\begingroup$ @Per: did you just guess the recurrence? $\endgroup$
    – dima
    Oct 18, 2012 at 11:48
  • $\begingroup$ what is the induction basis? If it's $\{n=0,1; k=0\}$, then the inductive argument doesn't help to prove the interlacing for $n>0$ (one cannot take the basis to be $\{n=0,1,…,d;k=0\}$ since $s^d_0=(x−1)^{d+1}$ and therefore no interlacing between $s^{d−1}_0$ and $s^d_0$). $\endgroup$
    – dima
    Oct 18, 2012 at 11:50
  • 2
    $\begingroup$ Rewrite the recurrence as $$s_{i+1}^d(w)=(d+2)s_i^d(w)-ws'_i^d(w)$$ Now by [Polya & Szego, Vol. 2, Part 5, Problem 66] we have that $s_{i+1}^d$ has no more imaginary roots than $s_i^d$. But $s_0^d=(w-1)^{d+1}$, therefore $s_i^d$ has only real roots for all $i\geq 0$. The only thing left is to show that $s_d^d$ has no multiple roots. $\endgroup$
    – dima
    Oct 18, 2012 at 12:58
  • 1
    $\begingroup$ Yes, I just guessed; I have no proof of it, but since you have an explicit formula, I guess it is straightforward to prove. Seems like you are almost there now. $\endgroup$ Oct 18, 2012 at 16:00
  • $\begingroup$ Indeed the proof of the recurrence is straightforward. However this last step (proving that $s^d_d$ is square-free) is right now elusive. $\endgroup$
    – dima
    Oct 18, 2012 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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