User dima - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T03:50:02Z http://mathoverflow.net/feeds/user/23862 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/125900/constructing-a-linear-ode-for-a-product-of-two-holonomic-functions-without-introd Constructing a linear ODE for a product of two holonomic functions without introducing additional singularities dima 2013-03-29T10:45:18Z 2013-04-03T11:56:58Z <p>A function $f$ is called <em>holonomic</em> if it satisfies some linear differential equation with polynomial coefficients $$p_n(x) f^{(n)}(x)+\dots+p_1(x)f'(x)+p_0(x)f(x)=0.$$ Now if $f,g$ are holonomic then so are their sum and product. To obtain a differential equation for $h=fg$, first observe that $$h^{(k)} = \sum_{i=0}^k {k\choose i} f^{(i)} g^{(k-i)}.$$ Since each $f^{(i)}$ is a linear combintation of $f,f',\dots,f^{(n-1)}$ with rational coefficients (where $n$ is the order of the ODE satisfied by $f$), and analogously each $g^{(i)}$ is a linear combination of $g,g',\dots,g^{(m-1)}$, then $h,h',h'',\dots$ span a finite-dimensional vector space of dimension at most $d=mn$, and hence there exists a nontrivial relation of the form $$r_d(x)h^{(d)}+\dots+r_1(x)h'+r_0(x)h=0$$with $r_i(x)$ rational functions.</p> <p>Now suppose that the ODE which $f$ satisfies had singular points $u_1,\dots,u_n$, while the equation of $g$ had singular points $w_1,\dots,w_m$. The ODE for $h$ might have additional singular points besides $u_1,\dots,u_n,w_1,\dots,w_m$. For example, if $$(x-a)f''(x)+cf(x)=0\\ (x-b)g''(x)+dg(x)=0$$ then $h=fg$ satisfies an ODE of order 4 with leading coefficient $$(x-a)^3 (x-b)^3 \biggl((c-d)x-(bc-ad)\biggr)h^{(4)}+\dots$$ (I calculated this using C.Mallinger's <em>GeneratingFunctions</em> Mathematica package).</p> <p>Is it possible to construct a holonomic ODE for $h$ (in the above example and in general) without introducing additional singular points?</p> http://mathoverflow.net/questions/115458/smallest-lipschitz-constant-on-non-convex-domains Smallest Lipschitz constant on non-convex domains dima 2012-12-05T01:27:07Z 2012-12-05T01:44:49Z <p>It is well known that if a function $f:U\to \mathbb C^n$, $U\subset \mathbb C^m$ satisfies $\sup_{x\in U}\|Df(x)\|_{\infty} = C &lt; \infty$ uniformly on $U$ and $U$ is compact and convex, then $f$ is Lipschitz with smallest possible constant $C$.</p> <p>What if $U$ is non-convex, but still compact and connected? Is there any reasonable "measure of non-convexity" which can be used to bound the Lipschitz constant of such $f$?</p> http://mathoverflow.net/questions/115268/approximation-power-of-wavelets Approximation power of wavelets dima 2012-12-03T10:43:45Z 2012-12-03T13:34:51Z <p>The <a href="http://en.wikipedia.org/wiki/Wavelet_series#Wavelet_compression" rel="nofollow">Wikipedia article on Wavelet Transform</a> states that:</p> <blockquote> <p>Wavelet compression is not good for all kinds of data: transient signal characteristics mean good wavelet compression, while smooth, periodic signals are better compressed by other methods, particularly traditional harmonic compression (frequency domain, as by Fourier transforms and related).</p> </blockquote> <p>What is the precise quantification of this statement? For the smooth periodic signals we have for example: if the signal is of class $C^d$ of $d$-times continuously differentiable periodic functions, then the partial Fourier sum of order $N$ gives uniform approximation error at most $N^{-d-1}$. What would be the corresponding characterization for wavelet series?</p> <p>To make the question more concrete: if the signal is piecewise $C^d$-periodic, with, say, one discontinuity, what approximation error do I get with $N$ wavelet coefficients (the Fourier approximation gives only $N^{-1}$ away from the discontinuity)? Conversely, how many coefficients do I need to get an accuracy $\epsilon$?</p> http://mathoverflow.net/questions/114972/norm-of-inverse-confluent-vandermonde-matrix Norm of inverse confluent Vandermonde matrix dima 2012-11-30T12:25:07Z 2012-12-03T11:56:02Z <p>Let $\{x_1,\dots,x_n\}$ be pairwise distinct complex numbers and $l_1+l_2+\dots+l_n=N$. The $N\times N$ confluent Vandermonde matrix is defined as $$V= \begin{bmatrix} v_{1,0}&amp;v_{2,0}&amp;\dots&amp;v_{n,0}\\ v_{1,1}&amp;v_{2,1}&amp;\dots&amp;v_{n,1}\\ \vdots\\ v_{1,N-1}&amp;v_{2,N-1}&amp;\dots&amp;v_{n,N-1} \end{bmatrix}$$ where $v_{j,k}=\begin{bmatrix}x_j^k,&amp;kx_j^{k-1},&amp;\dots&amp;k(k-1)\times\dots\times (k-l_j+1) x_j^{k-l_j+1}\end{bmatrix}$. Let $\|\cdot\|$ denote the row sum matrix norm. In some applications (e.g. interpolation, signal processing) one would like to estimate the quantity $\|V^{-1}\|$.</p> <p>Gautschi [1] has shown that for $l_1=\dots=l_n=2$ one has $$\|V^{-1}\| \leq \max_{1\leq \lambda\leq n} \beta_{\lambda} \prod_{\nu=1,\nu\neq\lambda}^n \biggl(\frac{1+|x_{\lambda}|}{|x_{\nu}-x_{\lambda}|}\biggr)^2$$ where $\beta_{\lambda}=\max\biggl(1+|x_{\lambda}|,1+2(1+|x_{\lambda}|)\sum_{\nu\neq\lambda}{1\over |x_\nu-x_\lambda|}\biggr)$.</p> <p>I am interested in a somewhat cruder estimates, as follows: if $|x_j|\leq 1$ and $|x_i-x_j|\geq \delta$, then for the above case we have $$\|V^{-1}\| \leq C n 2^N\delta^{-N+1}\qquad (*)$$ for some absolute constant $C$.</p> <p><strong>Is it true that something like $(*)$ holds for the general configuration $\{l_1,\dots,l_n\}$?</strong></p> <p>EDIT: using [2], this seems to boil down to the following. Let $$h_j(x)=\prod_{i \neq j}(x-x_i)^{-l_i}.$$ <strong>For $t=0,1,\dots,l_j$ evaluate $h_j^{(t)}(x_j).$</strong></p> <p>[1] W.Gautschi, "On Inverses of Vandermonde and Confluent Vandermonde matrices II", Numerische Mathematik 5, 425-430, 1963.</p> <p>[2] R.Schapelle, "The Inverse of the Confluent Vandermonde Matrix", IEEE Trans. on Automatic Control, October 1972, pp.724-725.</p> http://mathoverflow.net/questions/114972/norm-of-inverse-confluent-vandermonde-matrix/115094#115094 Answer by dima for Norm of inverse confluent Vandermonde matrix dima 2012-12-01T17:55:31Z 2012-12-01T17:55:31Z <p>For $j=1,\dots,n$ and $k=0,1,\dots,l_j-1$ denote by $u_{j,k}$ the row with index $l_1+\dots +l_{j-1}+k$ of the matrix $V^{-1}$. By using a generalization of the Hermite interpolation formula (see [3]), in [2] it is shown that the elements of $u_{j,k}$ are the coefficients of the polynomial $${1\over k!} \sum_{t=0}^{l_j-1-k} {1\over t!} h_j^{(t)}(x_j) (x-x_j)^{k+t} \prod_{i\neq j} (x-x_i)^{l_i}$$</p> <p>Now thanks to the answer to <a href="http://math.stackexchange.com/q/248537/32051" rel="nofollow">this MSE question</a>, one has $$|h_j^{(t)}(x_j)|\leq N(N+1)\cdots (N+t-1)\delta^{-N-t}.$$</p> <p>The sum of absolute values of the coefficients of the polynomials $(x-x_j)^{k+t} \prod_{i\neq j} (x-x_i)^{l_i}$ is at most (see [4, Lemma]) $$(1+|x_j|)^{k+t} \prod_{i\neq j}(1+|x_i|)^{l_i} \leq 2^{N-(l_j-k-t)}.$$</p> <p>So now $$\|u_{j,k}\| \leq {1\over k!}\sum_{t=0}^{l_j-1-k} {1\over t!} {N(N+1)\cdots (N+t-1) \over {\delta^{N+t}}}2^{N-l_j+k+t}\\ \leq \biggl({2\over \delta}\biggr)^N {1\over {2^{l_j-k}k!}}\sum_{t=0}^{l_j-1-k} {l_j-1-k \choose t} {N(N+1)\cdots(N+t-1)\over (l_j-k-t)\cdots(l_j-k-2)(l_j-k-1)} \biggl({2\over \delta}\biggr)^t\\ \leq \biggl({2\over \delta}\biggr)^N {1\over {2^{l_j-k}k!}} \biggl(1+{2N\over \delta}\biggr)^{l_j-1-k}\\ =\biggl({2\over \delta}\biggr)^N {2\over k!} \biggl({1\over 2}+{N\over\delta}\biggr)^{l_j-1-k}.$$</p> <p>[3] A.Spitzbart, "A Generalization of Hermite's Interpolation Formula", The American Mathematical Monthly, Vol.67 No.1, p.42-46, 1960.</p> <p>[4] W.Gautschi, "On Inverses of Vandermonde and Confluent Vandermonde matrices", Numerische Mathematik 4, p.117-123, 1962.</p> http://mathoverflow.net/questions/114868/perturbations-of-zero-dimensional-algebraic-varieties Perturbations of zero-dimensional algebraic varieties dima 2012-11-29T10:00:51Z 2012-11-29T14:02:36Z <p>Let $P(z,w):\mathbb C^2\to\mathbb C$ be a certain polynomial, and consider $p(s,t)=P(e^{is},e^{it}):\mathbb T^2\to \mathbb C$ its restriction to the real torus. Assume generic situation, so by counting dimensions, the set $Z=\{(s,t): p(s,t)=0\}\subset \mathbb T^2$ is discrete.</p> <p>Now assume that the original polynomial is perturbed slightly, $Q(z,w)=P(z,w)+R(z,w)$ where coefficients of $R(z,w)$ are small (in a controllable manner) w.r.t those of $P$.</p> <p>Can I in principle estimate the magnitude of the corresponding perturbation of the set Z? (In the one-dimensional case, without the restriction on the circle, this would be just Rouche's theorem.)</p> <p>I would like something like this: if the norm of the coefficients of $R$ is at most $\epsilon\ll 1$, then the distances of the elements of the new zero set $Z'=\{(s,t): Q(e^{is},e^{it})=0\}$ from their counterparts in $Z$ are bounded by some function of $\epsilon$.</p> <p>I'm thinking about passing from $p$ to a meromorphic function by defining a suitable complex structure on $\mathbb T^2$ and then applying Rouche's theorem, but I don't quite understand how to do this properly.</p> http://mathoverflow.net/questions/112758/a-g-vitushkins-easily-representable-families-of-functions-can-it-be-general A.G. Vitushkin's "Easily representable families of functions" - can it be generalized? dima 2012-11-18T12:59:02Z 2012-11-18T12:59:02Z <h1>Background</h1> <p>In his monograph <em>"Estimation of the complexity of the tabulation problem"</em> (translated into English as <em>"Theory of the Transmission and Processing of Information"</em>) Vitushkin studies efficient representation of (compact) function classes $F$ defined on some compact set $G$ (continuous, smooth, analytic) by "tables". Let's say that we would like to approximate an element $f\in F$ up to accuracy $\epsilon$. A "table" can be thought of as a mapping $\Gamma:\omega^p \to N_{\epsilon}(F)$ where $N_{\epsilon}(F)$ is an $\epsilon$-net of $F$ and $\omega$ is a finite set of numbers (everything is considered in the uniform norm). The quantity $|\omega|^p$ is called the "table volume", and clearly it cannot be smaller than the minimal size of an $\epsilon$-net of $F$. Therefore $$p\log_2 |\omega| \geq H_{\epsilon}(F)\qquad (1)$$ where $H_{\epsilon}(F)=\log N_{\epsilon}(F)$ is the Kolmogorov's $\epsilon$-entropy.</p> <p>Obviously, nothing more concrete can be said without restricting the nature of the reconstruction/approximation algorithms $\Gamma$. Vitushkin takes $$\Gamma = \{ P_x(\omega_1,\dots,\omega_p); \deg P\leq k \}$$ where $P$ is a poloynomial in $p$ variables of degree $k$ in each one, whose coefficients depend somehow on the coordinates $x\in G$. Then he shows that</p> <ol> <li>For subspaces $F$ of $d$-times continuously differentiable functions $$p\log(k+1)\geq H_{\epsilon}(F)$$</li> <li>For subspaces $F$ of analytic functions $$p\log({k+1\over \epsilon}) \geq H_{\epsilon}(F) \qquad (2)$$</li> </ol> <p>Assume for the rest of the discussion that $k$ is fixed. Then the above suggests that "the complexity of representation" of analytic functions (the number of parameters $p$ in the table) can be made much smaller (by a factor of $\log {1\over \epsilon}$) than by using only considerations of metric entropy (compare $(2)$ with $(1)$).</p> <h1>Easily representable families</h1> <p>In proving $(2)$ Vitushkin uses the fact that the analytic functions are "easily representable", in the following sense.</p> <p><strong>Definition 1</strong> For any finite subset $S=\{s_1,\dots,s_n\} \subset G$ of cardinality $n$, let $f(S)$ denote the set $$f(S) = \{ \left(\Re f(s_1),\Re f(s_2),\dots,\Re f(s_n), \Im f(s_1),\Im f(s_2),\dots,\Im f(s_n) \right) : \; f\in F\} \subset \mathbf R^{2n}.$$</p> <p><strong>Definition 2:</strong> For given $\delta\geq \epsilon$, let $\nu_\epsilon^\delta(F)$ denote the minimal size of a subset $\alpha_\epsilon^\delta \subset G$ for which $$H_\epsilon(f(\alpha_\epsilon^\delta)) \geq H_\delta(F).$$</p> <p><strong>Definition 3</strong> A subspace $F$ is called "easily representable" if there exists a function $\delta=\delta(\epsilon)\geq 2\epsilon$, decreasing monotonically to zero as $\epsilon\to 0$, such that for any $B>0$ and for sufficiently small $\epsilon$ we have $\nu_{B\epsilon}^{\delta(\epsilon)} &lt; +\infty$, and $$\lim_{\epsilon\to 0} {\nu_{B\epsilon}^{\delta(\epsilon)} \over H_{\delta(\epsilon)}(F)}=0.$$</p> <h1>My question</h1> <p>Are there any known generalizations of the above ideas? For instance, the construction of the set $f(S)$ can be considered as a transformation of the space $F$ by the collection of linear functionals $$\{\delta_{s_1},\dots,\delta_{s_n} \}$$ (here $\delta$ is the delta-function).</p> <p>Can one replace this collection by another set of linear functionals (i.e. changing Definition 1 to some other Definition 1'), and still get meaningful results, i.e. a non-empty set of "easily representable functions" in this new sense? What if one takes the first $n$ Fourier coefficients? (in this case one should also probably change the metric to $L^2$). Or even an arbitrary/random collection of $n$ linear functionals?</p> http://mathoverflow.net/questions/32588/n-widths-and-kolmogorovs-entropy/111818#111818 Answer by dima for n-widths and Kolmogorov's entropy dima 2012-11-08T14:58:48Z 2012-11-08T14:58:48Z <p>I would also recommend "Nonlinear Methods of Approximation" by V.N.Temlyakov.</p> http://mathoverflow.net/questions/111562/worst-case-error-and-cramer-rao-lower-bound-is-there-any-mathematical-relation Worst-case error and Cramer-Rao Lower Bound - is there any mathematical relation between them? dima 2012-11-05T14:44:49Z 2012-11-05T14:44:49Z <p>I would like to understand the relation (if any) between the Cramer-Rao Lower Bound of estimation theory and the following simple definition of "reconstruction accuracy" which doesn't use any statistical framework.</p> <p>Let $\theta\in\Theta\subset \mathbb{R}^n$ be an unknown parameter vector and let $x=f(\theta)\subset\mathbb{R}^m$ be a set of measurements, from which $\theta$ is to be reconstructed. Assume that the absolute error in each measurement is bounded from above by $\epsilon>0$, and otherwise nothing is known about the measurement error. Let $T_{\theta,\epsilon}=f^{-1}(x+B(0,\epsilon))$ (the full preimage, always well-defined). Obviously, $\theta\in T_{\theta,\epsilon}$. The "best possible" reconstruction accuracy is defined as $\delta_{\theta,\epsilon}=\sup_{t\in T_{\theta,\epsilon}} \|t-\theta\|$.</p> <p>(Informal justification for the definition: if the measurement error is bounded by $\epsilon$, the original parameter vector $\theta$ can only be recovered up to accuracy $\delta_{\theta,\epsilon}$ because any parameter vector $\hat\theta\in T_{\theta,\epsilon}$ could have produced a measurement vector $\hat x \in B(x,\epsilon)$.)</p> <p>In contrast, Cramer-Rao lower bound depends on some distribution $p(x;\theta)$ of the measurements, and gives a bound on the variance of any unbiased estimator $\hat \theta$ of $\theta$ satisfying some regularity conditions.</p> <p>Apparently, the two notions are different and in general not comparable.</p> <p>Still, are there cases in which the Cramer-Rao bound can be thought of as the $\delta_{\theta,\epsilon}$ defined above?</p> <h2>Example</h2> <p>Consider the simple case of a single parameter. Assuming $f'(\theta)\neq 0$, first-order approximation of the reconstruction accuracy as defined above is $$\delta_{\theta,\epsilon}\approx \frac{\epsilon}{f'(\theta)}. \qquad (1)$$ On the other hand, assuming that the measurements are modeled as $$x = f(\theta) + w$$ where $w$ is Gaussian with zero mean and variance $\sigma^2$, we have (see e.g. Kay's book, section 3.5) $$CRB{\theta} = \frac{\sigma^2}{\biggl(\frac{\partial f}{\partial \theta}\biggr)^2} \qquad (2)$$</p> <p>Comparing $(1)$ and $(2)$ seems to suggest that in this case the notions are very closely related.</p> http://mathoverflow.net/questions/109904/prove-that-a-particular-polynomial-sequence-is-a-sturm-sequence Prove that a particular polynomial sequence is a Sturm sequence dima 2012-10-17T12:45:41Z 2012-10-18T18:02:55Z <p>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}.$$ <strong>Conjecture:</strong> <em>The sequence</em> ${s_d^d(w),s_d^{d-1}(w),\dots,s_d^0(w)}$ <em>is a Sturm sequence.</em></p> <p>An easy corollary of this conjecture is that:</p> <p><strong>Corollary:</strong> <em>For $i\geq d$, the roots of the polynomial</em> $s_i^d(w)$ <em>are all real, simple (and positive).</em></p> <p>Any idea how to prove either the <strong>Conjecture</strong> or (directly) the <strong>Corollary</strong>? Or, in the worst case, the Corollary for the special case $i=d$?</p> <p>Note that:</p> <ol> <li>$s_0^d(w)=(w-1)^{d+1}$</li> <li>$s_i^0(w)=w-2^i$</li> <li>${d\over dw} s_i^d(w)=(d+1)s_i^{d-1}(w)$.</li> </ol> http://mathoverflow.net/questions/109906/lower-asymptotic-bounds-for-the-derivative-of-laguerre-polynomials Lower asymptotic bounds for the derivative of Laguerre polynomials dima 2012-10-17T13:00:57Z 2012-10-17T13:00:57Z <p>Let $L_{d}^{(1)}(x)$ denote the generalized Laguerre polynomial of degree $d$ and order $\alpha=1$. Clearly, since all the roots $r_1,\dots,r_d$ of $L_{d}^{(1)}$ are simple, there exists a strictly positive function $C=C(d)$ for which $$\min_{i=1,\dots,d} |L'^{(1)}_{d} (r_i)| \geq C(d) > 0.$$</p> <p>I would like to have a lower asymptotic bound for $C(d)$ (i.e. as rapidly increasing/slowly decreasing as possible).</p> http://mathoverflow.net/questions/125900/constructing-a-linear-ode-for-a-product-of-two-holonomic-functions-without-introd/126373#126373 Comment by dima dima 2013-04-04T11:19:34Z 2013-04-04T11:19:34Z Thanks Manuel! That kind of things is exactly what I needed. http://mathoverflow.net/questions/125900/constructing-a-linear-ode-for-a-product-of-two-holonomic-functions-without-introd/125910#125910 Comment by dima dima 2013-03-31T12:48:41Z 2013-03-31T12:48:41Z Since my German is nonexistent, could you please pinpoint the location in the paper where they talk about the case of one singular point? Also, I couldn't figure out if they always assume that the solutions of the ODEs are entire functions... http://mathoverflow.net/questions/115458/smallest-lipschitz-constant-on-non-convex-domains/115459#115459 Comment by dima dima 2012-12-05T10:18:28Z 2012-12-05T10:18:28Z Of course, should have figured this out myself. Thanks! http://mathoverflow.net/questions/115435/global-stability-bounds-for-inverting-a-diffeomorphism Comment by dima dima 2012-12-05T00:18:55Z 2012-12-05T00:18:55Z @Alexandre: a Jordan block with zero eigenvalue would not correspond to an invertible map, I think http://mathoverflow.net/questions/115435/global-stability-bounds-for-inverting-a-diffeomorphism Comment by dima dima 2012-12-05T00:13:14Z 2012-12-05T00:13:14Z I now realize that this is just a question about smallest Lipschitz constant. http://mathoverflow.net/questions/115435/global-stability-bounds-for-inverting-a-diffeomorphism Comment by dima dima 2012-12-04T23:44:53Z 2012-12-04T23:44:53Z @Deane: you are right, I probably complicated things by going to the inverse. So the question is just this: if $C=\max_{x\in D} \|J_{f}(x)\|_2$, is it true that for every $\delta x$ one has $\|f(x+\delta x)-f(x)\|_2 \leq C \|\delta x\|_2$? I guess I will rewrite the question. http://mathoverflow.net/questions/115435/global-stability-bounds-for-inverting-a-diffeomorphism Comment by dima dima 2012-12-04T21:59:17Z 2012-12-04T21:59:17Z The spectral norm is the largest singular value. http://mathoverflow.net/questions/115435/global-stability-bounds-for-inverting-a-diffeomorphism Comment by dima dima 2012-12-04T21:58:33Z 2012-12-04T21:58:33Z @Alexandre of course this should be $\max$ and not $\min$. I also want the inequality to hold for all appropriate $\delta y$ (and not just locally), that's why I assume $f$ to be 1-1 and onto. http://mathoverflow.net/questions/115268/approximation-power-of-wavelets/115283#115283 Comment by dima dima 2012-12-03T16:02:08Z 2012-12-03T16:02:08Z OK, this is nice, thanks. I would really like to know, though, what happens for $d\geqslant 2$... http://mathoverflow.net/questions/115268/approximation-power-of-wavelets/115283#115283 Comment by dima dima 2012-12-03T13:32:56Z 2012-12-03T13:32:56Z +1 for the link. Still, this is for me very confusing. What if I want to approximate the function with accuracy $\epsilon$, how large should I take $k$ to be? Consequently, how many wavelet coefficients are needed? http://mathoverflow.net/questions/109904/prove-that-a-particular-polynomial-sequence-is-a-sturm-sequence/109946#109946 Comment by dima dima 2012-10-18T20:27:58Z 2012-10-18T20:27:58Z Now this is perfect. http://mathoverflow.net/questions/109904/prove-that-a-particular-polynomial-sequence-is-a-sturm-sequence/109946#109946 Comment by dima dima 2012-10-18T16:23:24Z 2012-10-18T16:23:24Z Indeed the proof of the recurrence is straightforward. However this last step (proving that $s^d_d$ is square-free) is right now elusive. http://mathoverflow.net/questions/109904/prove-that-a-particular-polynomial-sequence-is-a-sturm-sequence Comment by dima dima 2012-10-18T15:26:15Z 2012-10-18T15:26:15Z These polynomials appear as first-order approximations in some nonlinear reconstruction problems, see e.g. <a href="http://arxiv.org/abs/1005.1884" rel="nofollow">arxiv.org/abs/1005.1884</a>. 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. http://mathoverflow.net/questions/109904/prove-that-a-particular-polynomial-sequence-is-a-sturm-sequence/109946#109946 Comment by dima dima 2012-10-18T12:58:43Z 2012-10-18T12:58:43Z Rewrite the recurrence as $$s_{i+1}^d(w)=(d+2)s_i^d(w)-ws'_i^d(w)$$ Now by [Polya &amp; 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. http://mathoverflow.net/questions/109904/prove-that-a-particular-polynomial-sequence-is-a-sturm-sequence/109946#109946 Comment by dima dima 2012-10-18T11:50:15Z 2012-10-18T11:50:15Z 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&gt;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$).