Upper Bound for Polynomial Using Evenly Spaced Points

Question

Suppose that $x \in [0,1]$ and the points $x_1, x_2,\ldots x_n$ are evenly spaced in the interval $[0,1]$. I am trying to find a tight bound for the maximum of:

$$(x - x_1)(x-x_2)\cdots(x-x_n) $$

I realize that the above expression will be smaller in absolute value than the absolute value of the smallest term $(x-x_i)$ for $ 1\le i \le n$ since each term will is less than $1$. Thus, if there are $n$ equally spaced points, each distanced $\frac{1}{n-1}$ apart, then smallest term will be bounded above by $\frac{1}{2(n-1)}$.

I am wondering if there is a way to get a tighter bound than the one I have found above.

Answer 1

One finds that the factors, excluding those for the points directly around $x$, are largest in the first and last interval. As the maxima of third degree polynomials are still accessible, for an $x\in[x_1,x_2]$ we get the first bound $$ |(x-x_1)\cdots(x-x_n)|\le|(x-x_1)(x-x_2)(x-x_3)|\cdot |(x_4-x_1)\cdots(x_n-x_1)| $$ Now set $s=x-x_2$ and $x_2-x_1=h=x_3-x_2$, more generally $x_k-x_1=(k-1)h$, so that $s\in[-h,0]$. The cubic factor reads as $(s+h)s(s-h)=s^3-sh^2$ which has its extrema at $s=\pm\frac{h}{\sqrt3}$ with value $\mp\frac{2\sqrt3h^3}{9}$.

The upper bound of this method is thus $$ |(x-x_1)\cdots(x-x_n)|\le\frac{2\sqrt3h^3}{9}\cdot 3h\cdot 4h\cdots(n-1)h\le\frac{\sqrt3}{9}\frac{(n-1)!}{(n-1)^{n}}\sim \frac{\sqrt{6\pi}}{9\sqrt{n-1}}e^{1-n}. $$

Answer 2

Let $n\geq3$ and let $x_i:=\frac{i}{n-1}$ so that we want to determine the maximum of the polynomial $$f_n(x):=\prod_{i=1}^n(x-x_i)=\prod_{i=1}^n\left(x-\frac{1-i}{n-1}\right),$$ on the interval $[0,1]$. If $n$ is odd then for all $x\in(x_1,x_2)$ and $i>2$ we have $$\frac{1-i}{n-1}<x-x_i<\frac{2-i}{n-1}<0,$$ from which it follows that $$(x-x_1)(x-x_2)\prod_{i=3}^n\frac{2-i}{n-1} <f_n(x) <(x-x_1)(x-x_2)\prod_{i=3}^n\frac{1-i}{n-1}.$$ The maximum of $(x-x_1)(x-x_2)$ on the interval $(x_1,x_2)$ is at the midpoint $\frac{x_1+x_2}{2}=\frac{1}{2(n-1)}$, yielding the following bounds for the maximum $M_n$ of $f_n$ on the interval $(x_1,x_2)$: $$M_n >\left(\tfrac{1}{2(n-1)}-x_1\right)\left(\tfrac{1}{2(n-1)}-x_2\right)\prod_{i=3}^n\frac{2-i}{n-1} =\frac14\frac{(n-2)!}{(n-1)^n}. $$ $$M_n <\left(\tfrac{1}{2(n-1)}-x_1\right)\left(\tfrac{1}{2(n-1)}-x_2\right)\prod_{i=3}^n\frac{1-i}{n-1} =\frac14\frac{(n-1)!}{(n-1)^n},$$ Similarly, if $n$ is even then for all $x\in(x_2,x_3)$ and $i>3$ we have $$(x-x_1)(x-x_2)(x-x_3)\prod_{i=4}^n\frac{3-i}{n-1} <f_n(x) <(x-x_1)(x-x_2)(x-x_3)\prod_{i=4}^n\frac{2-i}{n-1},$$ and some basic algebra shows that the maximum of $(x-x_1)(x-x_2)(x-x_3)$ is at $x=\frac{1+\sqrt{3}}{3(n-1)}$, so $$M_n>\left(\tfrac{1+\sqrt{3}}{3(n-1)}-x_1\right) \left(\tfrac{1+\sqrt{3}}{3(n-1)}-x_2\right) \left(\tfrac{1+\sqrt{3}}{3(n-1)}-x_3\right)\prod_{i=4}^n\frac{3-i}{n-1} =2\frac{\sqrt{3}}{9}\frac{(n-3)!}{(n-1)^n},$$ $$M_n<\left(\tfrac{1+\sqrt{3}}{3(n-1)}-x_1\right) \left(\tfrac{1+\sqrt{3}}{3(n-1)}-x_2\right) \left(\tfrac{1+\sqrt{3}}{3(n-1)}-x_3\right)\prod_{i=4}^n\frac{2-i}{n-1} =2\frac{\sqrt{3}}{9}\frac{(n-2)!}{(n-1)^n}.$$

---

Proof that the maximum is in $(x_1,x_2)$ if $n$ is odd, and in $(x_2,x_3)$ if $n$ is even:

(A bit messy, might clean up later)

It it not hard to see that for $x\in(x_k,x_{k+1})$ we have $\operatorname{sgn}f(x)=(-1)^{n-k}$. So the maximum is in some interval $(x_k,x_{k+1})$ with $k\equiv n\pmod{2}$.

The symmetry in the product shows that for all $x\in(0,1]$ we have $$f\left(x-\frac{1}{n-1}\right) =\frac{x-x_n}{x-x_1}f\left(x\right) =(1-x^{-1})f(x),$$ and of course for $x\in[\tfrac12,1]$ we have $|1-x^{-1}|\leq1$, so the maximum value of $f$ on the interval $[\tfrac12,1]$ is assumed on the interval $(x_{n-2},x_{n-1})$. It is clear that $$f(1-x)=(-1)^nf(x),$$ for all $x\in[0,1]$, from which it follows that the maximum value of $f$ on the interval $[0,1]$ is assumed on $(x_1,x_2)$ if $n$ is odd, and on $(x_2,x_3)$ if $n$ is even.

The polynomial $f$ of degree $n$ has precisely $n$ distinct roots in the interval $[0,1]$. It follows that the polynomial $f'$ has precisely one root in each interval $(x_k,x_{k+1})$ for $k\in\{1,\ldots,n-1\}$. The maximum of $f$ is then assumed at the unique root of $f'$ in the interval $(x_k,x_{k+1})$, where $k=1$ if $n$ is odd and $k=2$ if $n$ is even.