# Approximation theory reference for a bounded polynomial having bounded coefficients

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:

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!

-
Just out of curiosity, what's a lower bound on the best constant $C$? E.g. it can't be smaller than $2$, because by the Chebyshev approximation theory, the leading coefficient of $P$ satisfies a sharp inequality $|a_d|\le 2^{d-1}\|P\|_{\infty,[-1,1]}$. – Pietro Majer May 24 '12 at 9:22
That's a good question; I also do not know a lower bound higher than $2$. – Ryan O'Donnell May 24 '12 at 15:35

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.

-
Thank you, the top of p. 81 is exactly what I'm looking for. And indeed it jibes with Fedja's response; it's not too hard to show that the bounds Markov gives are maximized when '2i' = 1 - 1/sqrt(2), leading to Fedja's bound. – Ryan O'Donnell Sep 20 '12 at 16:03

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

-
Thanks Fedja! I'm accepting your answer for now since I learned a lot from it. I'd still be happy if someone in the area could suggest a generic citation I could put in the paper I'm working on :) – Ryan O'Donnell Jun 2 '12 at 17:46

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.

-