Largest absolute value of a polynomial of degree $n$ on $\{0,1,\ldots,n\}$

Question

Consider a polynomial $P_n(x)\in\mathbb{R}[x]$, of degree $n\geq1$, of the form $$P_n(x)=c_0+c_1x+c_2x^2+\cdots+c_{n-1}x^{n-1}+x^n.$$ To illustrate the question, take $P_1(x)=c_0+x$ so that $P_1(0)=c_0$ and $P_1(1)=c_0+1$. If $\vert c_0\vert<\frac12$ then $\vert c_0+1\vert\geq1-\vert c_0\vert>1-\frac12=\frac12$. That means, $\pmb{\max}\{\vert P_1(0)\vert,\vert P_1(1)\vert\}\geq\frac12$.

In general,

QUESTION. is this true? $$\pmb{\max}\{\vert P_n(0)\vert,\vert P_n(1)\vert,\vert P_n(2)\vert,\dots,\vert P_n(n)\vert\}\geq\frac{n!}{2^n}.$$

Answer 1

You can write your polynomial as $$ P(x) = \sum_{k = 0}^n P(k) L_{n,k}(x) ,$$ where $L_{n,k}$ are the Lagrange interpolation polynomials with nodes at $0, 1, \ldots, n$. Note that $(-1)^{n - k} L_{n,k}$ has positive coefficient at $x^n$. Thus, with the constraint $$\max\{|P(k)| : k = 0, 1, \ldots, n\} \leqslant 1,$$ the largest possible value of the coefficient of $P$ at $x^n$ is attained by $$ \bar P(x) = \sum_{k = 0}^n (-1)^{n - k} L_{n,k}(x) , $$ and the coefficient of $\bar P$ at $x^n$ is equal to $$ \sum_{k = 0}^n \prod_{\substack{0 \leqslant j \leqslant n \\ j \ne k}} \frac{1}{|k - j|} \, .$$ In other words, if the coefficient at $x^n$ is to be equal to $1$, the least possible value of $\max\{|P(k)| : k = 0, 1, \ldots, n\}$ is $$ \biggl(\sum_{k = 0}^n \prod_{\substack{0 \leqslant j \leqslant n \\ j \ne k}} \frac{1}{|k - j|} \biggr)^{-1} .$$ It remains to note that $$ \sum_{k = 0}^n \prod_{\substack{0 \leqslant j \leqslant n \\ j \ne k}} \frac{1}{|k - j|} = \sum_{k = 0}^n \frac{1}{k! (n - k)!} = \frac{1}{n!} \sum_{k = 0}^n \binom{n}{k} = \frac{2^n}{n!} \, .$$

Answer 2

Lagrange interpolation suggested by Mateusz Kwaśnicki is perfectly ok, but in this case it is probably easier to use the finite difference formula $$\sum_{i=0}^{n} (-1)^{i}{n\choose i}P(t+n-i)=\Delta^n P=n!$$ for $t=0$, where $\Delta:f(t)\to f(t+1)-f(t)$ is a finite difference operator.

Also this very statement is well known, in case if you need references.