MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

Your Answer


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

Browse other questions tagged or ask your own question.