Let $n$ be a positive integer. Determine the smallest possible value of $|p(1)|^2+|p(2)|^2 +...+ |p(n+3)|^2$ over all monic polynomials $p$ of degree $n$.
This question was proposed (problem A.611)
some time ago at KoMaL.
The minimal values for $n=0,1,2,3$ are $3,5,14,324/5$.
It was also discussed at math.se, where the polynomial minimising such sum was found using Gram-Schmidt algorithm.
However the minimum value was not determined.
Any suggestion is welcome.
[edited to explain a few steps and connect with the Hahn polynomials]
The answer is $$ \frac{(2n+1)(2n+3) n!^4}{(2n)!} $$ assuming that I did the algebra right, which seems likely because this formula agrees with the previously computed values $3,5,14,324/5$ for $n=0,1,2,3$.
Consider first the minimum of $\sum_{i=1}^{n+1} p(i)^2$ over monic $p$ of degree $n$. Any vector $v = (a_1,a_2,\ldots,a_{n+1})$ is the list of values at $1,2,\ldots,n+1$ of some polynomial of degree at most $n$; the leading coefficient of this polynomial is $(u,v) / n!$ where $u$ is the vector whose $(n+1-i)$-th coordinate is $(-1)^i {n \choose i}$ (each $i$ in $0 \leq i \leq n$).$\color{red}{\bf[1]}$ We thus seek the minimum of $(v,v)$ subject to $(u,v) = n!$, and by Cauchy-Schwarz the answer is $n!^2 / (u,u)$, attained iff $v = n! u / (u,u)$. The denominator $(u,u)$ is $\sum_{i=0}^n {n \choose i}^2$, which is well-known to equal $2n \choose n$.$\color{red}{\bf[2]}$ Hence the answer is $n!^2 / {2n \choose n} = n!^4 / (2n)!$.
With a bit more work we can find for each $k$ the minimum of $\sum_{i=1}^{n+k+1} p(i)^2$ over monic $p$ of degree $n$. Here's how it goes for $k=2$. There are now three linear conditions on $v = (a_1,a_2,\ldots,a_{n+3})$ to be the list of values at $1,2,\ldots,n+3$ of a monic polynomial of degree at most $n$. We can write them as $(u_0,v)=n!$, $(u_1,v)=0$, $(u_2,v)=0$, where $u_j$ is the vector whose $(n+3-i)$-th coordinate is $(-1)^i {n+j \choose i}$ for each $i$ in $0 \leq i \leq n+2$.$\color{red}{\bf[1a]}$ As was the case for $k=0$, the minimum of $(v,v)$ over all such $v$ is attained by a linear combination of $u_0,u_1,u_2$. So we need only calculate the $3 \times 3$ Gram matrix of inner products $(u_j,u_{j'})$ $(j,j'=0,1,2)$, and invert it to find the linear combination $v$ such that $(u_j,v) = n! \delta_j$. Each $(u_j,u_{j'})$ is $\sum_{i \geq 0} {n+j \choose i} {n+j' \choose i} = {2n+j+j' \choose n+j}$.$\color{red}{\bf[2a]}$ So write each of these entries of the Gram matrix as $2n \choose n$ times some rational function of $n$, solve the resulting linear equations for the coefficients of $v$ in $u_0,u_1,u_2$, and recover $(v,v)$. This calculation yields the formula $(2n+1)(2n+3) n!^2 / {2n \choose n}$ displayed (in equivalent form) at the start of this answer.
For general $k$ the minimum seems to be $$ \frac{n!^4}{(2n)!} {2n+1+k \, \choose k}, $$ which presumably can be proved from the above analysis and known identities.$\color{red}{\bf[3]}$
$\color{red}{\bf[1],[1a]}$ Taking the inner product with $u$ amounts to evaluating an $n$-th finite difference. Likewise, taking the inner product with $u_i$ amounts to evaluating an $(n+i)$-th finite difference.
$\color{red}{\bf[2],[2a]}$ The formula $\sum_{i \geq 0} {m \choose i} {m' \choose i} = {m+m' \choose m}$ has at least two well-known proofs, one bijective and one generatingfunctionological. For the former, write ${m+m' \choose m}$ as the number of $(m+m')$-tuples of $m$ 0's and $m'$ 1's, and let $i$ be the number of 1's among the first $m$ coordinates. For the latter, compute the $X^m$ coefficient of $(1+X)^m \, (1+X)^{m'} = (1+X)^{m+m'}$ in two ways.
$\color{red}{\bf[3]}$ Further corroboration is that this is also consistent with the extreme cases $n=0$ and (with a bit more work) $n=1$. I later obtained a proof by transforming the relevant determinants into Vandermonde determinants. The existence of such a formula for all $n,k$ suggested that the $p$'s (which are orthogonal polynomials for a discrete measure) must be known already, and after some Googling found that indeed they are the special case $\alpha=\beta=0$ of the Hahn polynomials $Q_n$ evaluated at $x-1$ (with $N = n+k+1$). The orthogonality relation, together with the formula for the leading coefficient of $Q_n$, soon yields the evaluation for all $n,k$ of the minimum of $\sum_{i=1}^{n+k+1} p(i)^2$ over monic polynomials $p$ of degree $n$.
