# Polynomials with minimal variation and a fixed root---looking for a variant of Chebyshev polynomials (motivated by probability)

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$$).

• 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]$. – WimC Jul 11 '19 at 19:59
• 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.) – Noah Stephens-Davidowitz Jul 11 '19 at 20:19

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.
• 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$. – Noah Stephens-Davidowitz Jul 11 '19 at 19:16
• 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$. – WimC Jul 11 '19 at 19:35