9
$\begingroup$

Recall that the Chebyshev polynomial $T_n(x)$ for a positive integer $n$ is, in a formal sense, the polynomial of degree $n$ that "varies the least" over an interval. Specifically, (a suitable scaling of) $T_n(x)$ is the monic polynomial $p$ of degree $n$ that minimizes

$$\sup_{x \in [-1,1]} |p(x)| \; .$$

I am interested in finding a polynomial of degree $n$ that varies the least over an interval, subject to the constraint that the polynomial must have a root at some fixed point. I.e., I would like to find a polynomial $p$ of degree $n$ such that $$p(0) = 0$$ and satisfying $$1 \leq p(x) \leq \alpha_p$$ for all $x \in [1,N]$ with $\alpha_p$ as small as possible. (I'm not sure how important the parameter $N$ is.)

So, that's the question. For those who are interesting, I'll write down my motivation below.


Motivation

My motivation comes from another very natural question. Suppose that I have some random variable $X$ over, say, the integers $0,\ldots, N$, and suppose I know the first $n$ moments of $X$, $M_1,\ldots, M_n$ with $N \gg n$. Given this information, how accurately can we estimate $\Pr[X \neq 0]$ (in the worst case)?

The first observation to make here is that knowing $M_1,\ldots, M_n$ is equivalent to knowing the expectation $\mathbb{E}[p(X)]$ for any polynomial $p$ whose degree is at most $n$. Suppose for simplicity that we just want to use one such expectation to answer this question. What polynomial $p$ do we pick, and how well can we do?

It's clear that $p$ is useless for this purpose if there exist non-zero $k_1,k_2$ with $p(k_1) \leq p(0) \leq p(k_2)$, since then there exist values of $\mathbb{E}[p(X)]$ that do not constrain $p(0)$ at all. So, after shifting and rescaling, we may assume that $p(0) = 0$ and $1 \leq p(k) \leq \alpha_p$ for $k \in \{1,\ldots, N\}$. Such a polynomial yields a multiplicative approximation factor of $\alpha_p$, so our goal is to find the polynomial minimizing $\alpha_p$. The above question is identical, except that I removed the restriction that $k$ must be an integer (which seems reasonable for large $N$).

$\endgroup$
2
  • 1
    $\begingroup$ With this motivation, doesn’t it make more sense to look for a $p$ such that $p(0)=1$ and $\lvert p(x) \rvert$ is as small as possible over $[1,N]$? Then $\mathbb{E}[p(x)]$ is directly “close to” $\operatorname{Pr}[x=0]$. $\endgroup$ – WimC Jul 11 '19 at 19:59
  • $\begingroup$ Yes, but only because I wrote the wrong thing :). I'm looking to approximate $\Pr[X\neq 0]$, not $\Pr[X = 0]$. Fixed now. I suppose the other question is interesting as well. (Of course, it's not the same thing because the approximation factor is multiplicative.) $\endgroup$ – Noah Stephens-Davidowitz Jul 11 '19 at 20:19
3
$\begingroup$

Note that $$P_n(x)=T_n\left(\frac{2x-2}{N-1}-1\right)$$ oscillates between $-1$ and $1$ on $[1, N]$. And since $P_n(1)=T_n(-1)=(-1)^n$ the polynomial that you are looking for is $$\frac{P_n(0)-P_n(x)}{P_n(0)-(-1)^n}.$$ Its maximum over $[1,N]$ is $$\frac{P_n(0)+1}{P_n(0)-1}$$ if $n$ is even and $$\frac{P_n(0)-1}{P_n(0)+1}$$ if $n$ is odd.

$\endgroup$
3
  • $\begingroup$ I see. It seems natural to expect a construction like this to be optimal, but I'm too dumb to see why it is. It seems that the properties $T_n(-1) = (-1)^n$ and $|T_n(x)| \leq 1$ for $|x| \leq 1$ cannot be sufficient on their own, since then we could have started with something silly like the constant polynomial $p_n(x) = (-1)^n$. In particular, it seems that you're also using some property about $T_n(-\frac{N+1}{N-1})$, which corresponds to $P_n(0)$. Specifically, that it's far from $(-1)^n$. $\endgroup$ – Noah Stephens-Davidowitz Jul 11 '19 at 19:16
  • 1
    $\begingroup$ Any other possible polynomial of degree $n$ that stays within the same band on $[1,N]$ intersects the given one in at least $n$ points on $[1,N]$ (since it oscillates between its extrema there). Together with the common root at $0$ this gives $n+1$ points where both polynomials are equal and so they are equal everywhere. And yes, $\lvert T_n(x) \rvert > 1$ if $\lvert x \rvert > 1$. $\endgroup$ – WimC Jul 11 '19 at 19:35
  • $\begingroup$ I see. Thanks!! $\endgroup$ – Noah Stephens-Davidowitz Jul 11 '19 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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