20
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ why $n+3$ values? $\endgroup$ – Will Sawin Jul 4 '15 at 17:38
  • 3
    $\begingroup$ Well $n$ or fewer is trivial :-) and I guess you're expected to see how to do $n+1$ before figuring out how to deal with a few more values. $\endgroup$ – Noam D. Elkies Jul 4 '15 at 19:00
33
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.