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

I've been driven up a wall by the following question: let p be a complex polynomial of degree d. Suppose that |p(z)|≤1 for all z such that |z|=1 and |z-1|≥δ (for some small δ>0). Then what's the best upper bound one can prove on |p(1)|? (I only care about the asymptotic dependence on d and δ, not the constants.)

For the analogous question where p is a degree-d real polynomial such that |p(x)|≤1 for all 0≤x≤1-δ, I know that the right upper bound on |p(1)| is |p(1)|≤exp(d√δ). The extremal example here is p(x)=Td((1+δ)x), where Td is the dth Chebyshev polynomial.

Indeed, by using the Chebyshev polynomial, it's not hard to construct a polynomial p in z as well as its complex conjugate z*, such that

(i) |p(z)|≤1 for all z such that |z|=1 and |z-1|≥δ, and

(ii) p(1) ~ exp(dδ).

One can also show that this is optimal, for polynomials in both z and its complex conjugate.

The question is whether one can get a better upper bound on |p(1)| by exploiting the fact that p is really a polynomial in z. The fastest-growing example I could find has the form p(z)=Cd,δ(1+z)d. Here, if we choose the constant Cd,δ so that |p(z)|≤1 whenever |z|=1 and |z-1|≥δ, we find that

p(1) ~ exp(dδ2)

For my application, the difference between exp(dδ) and exp(dδ2) is all the difference in the world!

I searched about 6 approximation theory books---and as often the case, they answer every conceivable question except the one I want. If anyone versed in approximation theory can give me a pointer, I'd be incredibly grateful.

Thanks so much! --Scott Aaronson

PS. The question is answered below by David Speyer. For anyone who wants to see explicitly the polynomial implied by David's argument, here it is:

pd,δ(z) = zd Td((z+z-1)(1+δ)/2+δ),

where Td is the dth Chebyshev polynomial.

share|improve this question
8  
Scott: Good question, but please register with MO. Join the club! –  Greg Kuperberg Dec 14 '09 at 21:49
add comment

1 Answer 1

up vote 23 down vote accepted

I may be missing something obvious here. Let $f(z, z^{\*})$ be the polynomial in $z$ and $z^{\*}$ of degree $d$ which achieves $\exp(d \delta)$. Let $g(z)$ be the Laurent polynomial obtained from $f$ by replacing $z^{\*}$ by $z^{-1}$. On the unit circle, we have $f=g$.

Now, let $h$ be the polynomial $z^d g$. This is an honest polynomial, because we multiplied by a high enough power of $z$ to clear out all the denominators and, for $z$ on the unit circle, we have $|h|=|f|$.

Doesn't this mean that $h$ is a polynomial of degree $2d$, obeying your conditions, with $|h(1)| \sim \exp(d \delta)$?

share|improve this answer
2  
In fact, it's a way to convert between the two questions in both directions. –  Greg Kuperberg Dec 14 '09 at 21:54
1  
Duhhhhhh ... thanks so much David! And Greg, yes, I registered! I'll see if I can return the karma by mentally unsticking someone else now. –  Scott Aaronson Dec 15 '09 at 2:30
1  
To follow through with the ritual, remember to accept David's answer. –  Greg Kuperberg Dec 15 '09 at 5:27
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.