5
$\begingroup$

The following is a well-known theorem (see e.g. The Chebyshev Polynomial by Rivlin):

If $p(x) = x^n + a_{n_1} x^{n-1} + \ldots + a_0$, then $\max_{-1\leq x \leq 1} |p(x)| \geq 2^{1-n}$ for $n \geq 1$ with equality being attained only if $p$ is the $n$th Chebyshev polynomial normalized so that the leading coefficient is $1$.

In my work I came across a question that can be seen as a refined version of the question answered by the above theorem:

Let $p$ be a polynomial as above and let $0 \leq \epsilon \leq 2^{1-n}$. Suppose that $x$ is a uniformly distributed random variable on $[-1, 1]$. What is $\sup_p \Pr[|p(x)|\leq \epsilon]$ as a function of $\epsilon$ and $n$ (sup is over all possible choices of the deg-$n$ monic polynomial $p$)? A good upper bound on this quantity will also be useful. Note that for $\epsilon=2^{1-n}$ this quantity is equal to $1$ by the theorem above.

Improve this question
$\endgroup$
5
  • $\begingroup$ I do not understand your very last sentence: How does it follow by the theorem above that the probability is 1 ? $\endgroup$
    – Alexandre Eremenko
    Mar 9, 2013 at 23:45
  • $\begingroup$ @Alexandre: I realize that I forgot to state the theorem with $p$ under the absolute values. I have modified the statement accordingly. Now I think my last statement is immediate:: for $\epsilon=2^{1-n}$ the normalized degree-$n$ Chebyshev polynomial is always in $[-2^{1-n}, 2^{1-n}]$ by the theorem. Does this answer your question? $\endgroup$
    – Navin Goyal
    Mar 10, 2013 at 5:09
  • $\begingroup$ So for small $\epsilon$ the supremum should be attained by $p(x):=x^n$, giving $|\{|p|\le\epsilon\}|=2\epsilon^{1/n}$. $\endgroup$
    – Pietro Majer
    Mar 10, 2013 at 13:20
  • $\begingroup$ Actually $p(x)=x^n$ can't be optimal (once $n>1$), though it probably comes within a constant factor. For example, if $n$ is even then $x^n-\epsilon$ already does better by a factor $2^{1/n}$. Likewise for $n\geq 3$ odd you can subtract some multiple of $x^{n-2}$ to extend the interval $|p(x)| \leq \epsilon$ beyond $|x| \leq \epsilon^{1/n}$. Better yet: if $p_0$ is the Chebyshev polynomial that works for $2^{1-n}$, and $\delta = 2^{n-1} \epsilon$, then $p(x) = \delta p_0(\delta^{-1/n} x)$ yields an interval of length $2\delta^{1/n} = 2^{2-1/n} \epsilon^{1/n}$. $\endgroup$
    – Noam D. Elkies
    Mar 10, 2013 at 15:54
  • $\begingroup$ Come to think of it, it might be natural to conjecture that the Chebyshev polynomial $p_0$ of each degree $n$ maximizes the size of $\lbrace x \in {\bf R} : |p(x)| \leq 1 \rbrace$ among all polynomials $p$ of the same degree and leading coefficient (is this a known theorem?), which would imply that the desired sup is $\min(2, 2^{2-1/n} \epsilon^{1/n})$ for all $\epsilon$, attained by $p_0(x)$ or $\delta p_0(\delta^{-1/n} x)$. $\endgroup$
    – Noam D. Elkies
    Mar 10, 2013 at 18:35

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.