Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
1  
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
add comment

3 Answers 3

up vote 4 down vote accepted

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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