Approximation theory reference for a bounded polynomial having bounded coefficients - MathOverflow

Approximation theory reference for a bounded polynomial having bounded coefficients

2012-05-23T15:29:34Z

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$.

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:

http://eccc.hpi-web.de/report/2012/037/download

Sherstov obtains $C = 4e$; I don't think either of particularly cares about getting the sharpest constant.

In any case, Sherstov and I agree that this must have appeared somewhere long ago. Could anyone provide a reference? Thanks!

Answer by fedja for Approximation theory reference for a bounded polynomial having bounded coefficients

2012-05-29T23:01:53Z

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$.

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...

Answer by Heinz-Joachim Rack for Approximation theory reference for a bounded polynomial having bounded coefficients

2012-09-19T18:15:13Z

Dear Ryan, I hope the following references will be useful for you:

V.A. Markov has solved your posed problem back in 1892, see pages 80-81 in

http://www.math.technion.ac.il/hat/fpapers/vmar.pdf

Compare also the book

I.P. Natanson: Constructive Function Theory, Vol. I. Uniform Approximation, F. Ungar Publishing, New York, 1964, page 56.

You will find more detailed information in the papers

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

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.

Answer by Matthew Badger for Approximation theory reference for a bounded polynomial having bounded coefficients

2012-09-19T20:04:33Z

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:

R.P. Boas, Extremal problems for polynomials, Amer. Math. Monthly 85 (1978), No. 6, 473--475.

You can also find Markov's theorem written up (including generalizations to polynomials of several variables) in the following textbooks:

P.B. Borwein and T. Erdelyi, Polynomials and Polynomial Inequalities, GTM 161, Springer, 1995.
P. Borwein, Computational Excursions in Analysis and Number Theory, CMS Books in Mathematics, Springer, 2007.