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

Consider the following statement $S_a$, with some parameter $a > 1$ :

"If $P(X)$ is a real polynomial such that for every $i\in \{0;1;\ldots;N\}$, $|P(a^i)|< 1$ and $|P(a^0)-P(a^1)|>1$, then the degree of $P$ is $\Omega(N)$."

It happens to be true for all $a>1$, and the lower bound on the degree of $P$ can be more or less made uniform in $a$, but my question is the following: if you know $S_a$ to be true for some given $a>1$, is there a direct way to deduce that it is true for all of them? Intuitively, it is blatantly obvious that it should be the case, but I fail to find a correct argument.

share|improve this question
    
I don't understand the statement of the question. It says "for every i" but then never mentions i again. On the other hand, it mentions $a^0$ and $a^1$ with no indication of what they range over. –  Andreas Blass Feb 16 '11 at 14:35
    
Woops, you're right. Corrected. –  Vincent Nesme Feb 16 '11 at 14:44
    
The condition you describe seems a bit odd, could you explain a bit why the statement is true? –  J.C. Ottem Feb 17 '11 at 0:15
    
Can do. It's part of the polynomial approximation theory, and more precisely to a set of theorems having the following pattern. $P(X)$ is a real polynomial, and its value is bounded at a given set of so-called "control points", in this case the first N+1 powers of a, where $P(X)$ must be in $]-1;1[$. In order to make things a little more difficult for $P$, it is also required that $P(1)$ and $P(a)$ differ quite a bit. Then, I think it is quite intuitive that this implies a nontrivial lower bound on the degree of $P$. –  Vincent Nesme Feb 17 '11 at 14:17
    
$P$ cannot be constant, affine won't get you through many control points, so you will have to add some degree $2$, but then it will eventually dive in the other direction, so you'll have to add a correction of order $3$, and so on... Now, I don't think I can convey an intuition as to why the lower bound grows linearly in $N$, but I can point you to Lemma 3 in arXiv:quant-ph/0501060v1 which the case a=2. (of course the proof is essentially the same for a different a) ... and btw, I just realized $a$ must be larger than $1$, not just $0$ as I first wrote. That was unnecessarily confusing. –  Vincent Nesme Feb 17 '11 at 14:28
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.