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
    Commented Jul 11, 2019 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$ Commented Jul 11, 2019 at 20:19

1 Answer 1

4
$\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$ Commented Jul 11, 2019 at 19:16
  • 2
    $\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
    Commented Jul 11, 2019 at 19:35
  • $\begingroup$ I see. Thanks!! $\endgroup$ Commented Jul 11, 2019 at 19:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .