Approximation theory reference for a bounded polynomial having bounded coefficients - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T05:33:18Z http://mathoverflow.net/feeds/question/97769 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/97769/approximation-theory-reference-for-a-bounded-polynomial-having-bounded-coefficien Approximation theory reference for a bounded polynomial having bounded coefficients Ryan O'Donnell 2012-05-23T15:29:34Z 2012-09-19T20:04:33Z <p>Let $P(x)$ be a real polynomial of degree at most $d$. Assume $|P(x)| \leq 1$ for $|x| \leq 1$. I would like a bound saying that each coefficient of $P(x)$ is at most $C^d$ in magnitude, for some absolute constant $C$.</p> <p>This is surely a well-known, basic fact in approximation theory and I'm looking for a proper reference. I know one very recent paper which writes out a proof using the standard simple idea (Lagrange interpolation) -- Lemma 4.1 from a paper of Sherstov here: </p> <p><a href="http://eccc.hpi-web.de/report/2012/037/download" rel="nofollow">http://eccc.hpi-web.de/report/2012/037/download</a> </p> <p>Sherstov obtains $C = 4e$; I don't think either of particularly cares about getting the sharpest constant.</p> <p>In any case, Sherstov and I agree that this must have appeared somewhere long ago. Could anyone provide a reference? Thanks!</p> http://mathoverflow.net/questions/97769/approximation-theory-reference-for-a-bounded-polynomial-having-bounded-coefficien/98319#98319 Answer by fedja for Approximation theory reference for a bounded polynomial having bounded coefficients fedja 2012-05-29T23:01:53Z 2012-05-29T23:01:53Z <p>This is an answer to Pietro rather than to Ryan. To find the sharp $C$ is easy. Note first that the maximal coefficient and the maximal value on the unit circle are pretty much the same things as far as the exponential rate of growth is concerned: the maximal coefficient is dominated by the maximum on the unit circle by Cauchy and $d+1$ times the maximal coefficient dominates the maximum on the circle by the triangle inequality. Now, the Chebyshev polynomial is defined by $$P(\frac{z+z^{-1}}2)=\frac{z^d+z^{-d}}2$$ Plugging in $z=i(\sqrt 2+1)$, we see that $|P(i)|\approx(\sqrt 2+1)^d$ (up to a constant factor), so $\sqrt 2+1$ is unbeatable. On the other hand, this value is easy to obtain. Take any polynomial $P$ that is bounded by $1$ on $[-1,1]$ and consider the analytic function $$F(z)=z^{-d}P(\frac{z+z^{-1}}2)$$ in the domain $|z|\ge 1$. It is bounded there, so by the maximum principle, it is bounded by its maximum on the unit circle, which is $1$. Thus, $|P(\frac{z+z^{-1}}2)|\le |z|^d$ for every $z$ outside the unit disk. The preimage of the unit circumference under the mapping $z\mapsto \frac{z+z^{-1}}2$ lies in the disk $|z|\le\sqrt 2+1$ (all points outside that disk satisfy $|\frac{z+z^{-1}}2|\ge \frac{|z|-|z|^{-1}}2>1$), so $P(w)|\le(\sqrt 2+1)^d$ for $|w|=1$.</p> <p>Returning to the (much more difficult) Ryan's question "Where is that all written?", I can more or less guarantee that Bernstein knew it well but the earlier history is lost in a dense fog and my eyesight is rather weak, so I prefer to leave it to someone else...</p> http://mathoverflow.net/questions/97769/approximation-theory-reference-for-a-bounded-polynomial-having-bounded-coefficien/107601#107601 Answer by Heinz-Joachim Rack for Approximation theory reference for a bounded polynomial having bounded coefficients Heinz-Joachim Rack 2012-09-19T18:15:13Z 2012-09-19T18:15:13Z <p>Dear Ryan, I hope the following references will be useful for you:</p> <p>V.A. Markov has solved your posed problem back in 1892, see pages 80-81 in</p> <p><a href="http://www.math.technion.ac.il/hat/fpapers/vmar.pdf" rel="nofollow">http://www.math.technion.ac.il/hat/fpapers/vmar.pdf</a></p> <p>Compare also the book</p> <p>I.P. Natanson: Constructive Function Theory, Vol. I. Uniform Approximation, F. Ungar Publishing, New York, 1964, page 56.</p> <p>You will find more detailed information in the papers</p> <p>H.-J. Rack: On V.A. Markov´s and G. Szegö´s inequality for the coefficients of polynomials in one and several variables, East Journal on Approximations 14 (2008), pages 319 - 352</p> <p>H.-J. Rack: On the length and height of Chebyshev polynomials in one and two variables, East Journal on Approximations, 16 (2010), pages 35 - 91.</p> http://mathoverflow.net/questions/97769/approximation-theory-reference-for-a-bounded-polynomial-having-bounded-coefficien/107617#107617 Answer by Matthew Badger for Approximation theory reference for a bounded polynomial having bounded coefficients Matthew Badger 2012-09-19T20:04:33Z 2012-09-19T20:04:33Z <p>I think that an interesting historical point to mention is that this problem was first posed and solved for quadratic polynomials by Medeleev (a chemist). There is a nice little article about the problem, including its origins, in the American Mathematical Monthly:</p> <ul> <li>R.P. Boas, Extremal problems for polynomials, Amer. Math. Monthly 85 (1978), No. 6, 473--475.</li> </ul> <p>You can also find Markov's theorem written up (including generalizations to polynomials of several variables) in the following textbooks:</p> <ul> <li><p>P.B. Borwein and T. Erdelyi, Polynomials and Polynomial Inequalities, GTM 161, Springer, 1995.</p></li> <li><p>P. Borwein, Computational Excursions in Analysis and Number Theory, CMS Books in Mathematics, Springer, 2007.</p></li> </ul>