17
$\begingroup$

Let $P_n$ be the set of degree $n$ polynomials that pass through $(0,1)$ and $(1,1)$ and are non-negative on the interval $[0,1]$ (but may be negative elsewhere).

Let $a_n = \min_{p\in P_n} \int_0^1 p(x)\,\mathrm{d}x$ and let $p_n$ be the polynomial that attains this minimum.

Are $a_n$ or $p_n$ known sequences? Is there some clever way to rephrase this question in terms of linear algebra and a known basis of polynomials?

$\endgroup$
20
$\begingroup$

Following Robert Israel's answer, we also scale everything to $[-1,1]$ (thus multiplying the result by 2). As he mentions, the optimal polynomial is always a square of some other polynomial, $p_{2n}=p_{2n+1}=q_n^2$, and $q_n$ is either even or odd (see Lemma below). So we are left to find the minimal $L_2[-1,1]$-norm of an odd/even polynomial $q_n$ such that $\deg q_n\leq n$ and $q_n(\pm1)=(\pm1)^n$. In other words (recall the division by 2 in the first line!), $a_{2n}=a_{2n+1}=d_n^2/2$, where $d_n$ is the distance from $0$ to the hyperplane defined by $q(1)=1$ in the space of all odd/even polynomials of degree at most $n$ with $L_2[-1,1]$-norm.

Now, this hyperplane is the affine hull of the Legendre polynomials $ P_i(x)=\frac1{2^ii!}\frac{d^i}{dx^i}(x^2-1)^i$, where $i$ has the same parity as $n$ (since we know that $ P_i(1)=1$ and $P_i(-1)=(-1)^i$). Next, by $\| P_i\|^2=\frac{2}{2i+1}$, our distance is $$ \left(\sum_{j\leq n/2}\| P_{n-2j}\|^{-2}\right)^{-1/2} =\left(\sum_{j\leq n/2}\frac{2(n-2j)+1}{2}\right)^{-1/2}=\sqrt{\frac4{(n+1)(n+2)}}, $$ attained at $$ q_n(x)=\left(\sum_{i\leq n/2}\frac{2}{2(n-2i)+1}\right)^{-1} \sum_{i\leq n/2}\frac{2P_{n-2i}(x)}{2(n-2i)+1}. $$ Thus the answer for the initial question is $a_{2n}=a_{2n+1}=\frac2{(n+1)(n+2)}$ and $p_{2n}=p_{2n+1}=q_n^2$.

Lemma. For every $n$, one of optimal polynomials on $[-1,1]$ is a square of an odd or even polynomial.

Proof. Let $r(x)$ be any polynomial.which is nonnegative on $[-1,1]$ with $r(\pm 1)=1$. We will replace it by some other polynomial which has the required form, has the same (or less) degree and the same values at $\pm 1$, is also nonnegative on $[-1,1]$, and is not worse in the integral sense. Due to the compactness argument, this yields the required result.

Firstly, replacing $r(x)$ by $\frac12(r(x)+r(-x))$, we may assume that $r$ is even (and thus has an even degree $2n$). Let $\pm c_1,\dots,\pm c_{n}$ be all complex roots of $r$ (regarding multiplicities); then $$ r(x)=\prod_{j=1}^n\frac{x^2-c_j^2}{1-c_j^2}, $$ due to $r(\pm 1)=1$.

Now, for all $c_j\notin[-1,1]$ we simultaneously perform the following procedure.

(a) If $c_j$ is real, then we replace $\pm c_j$ by $\pm x_j=0$. Notice that $$ \frac{|x^2-c_j^2|}{|1-c_j^2|}\geq 1\geq \frac{|x^2-0^2|}{|1-0^2|}. $$ for all $x\in[-1,1]$.

(b) If $c_j$ is non-real, then we choose $x_j\in[-1,1]$ such that $\frac{|c_j-1|}{|c_j+1|}=\frac{|x_j-1|}{|x_j+1|}$. Notice that all complex $z$ with $\frac{|c_j-z|}{|x_j-z|}=\frac{|c_j-1|}{|x_j-1|}$ form a circle passing through $-1$ and $1$, and the segment $[-1,1]$ is inside this circle. Therefore, for every $x\in[-1,1]$ we have $$ \frac{|c_j-x|}{|x_j-x|}\geq\frac{|c_j-1|}{|x_j-1|}, $$ thus $$ \frac{|x^2-c_j^2|}{|1-c_j^2|} =\frac{|c_j-x|}{|c_j-1|}\cdot\frac{|c_j+x|}{|c_j+1|} \geq \frac{|x_j-x|}{|x_j-1|}\cdot\frac{|x_j+x|}{|x_j+1|} =\frac{|x^2-x_j^2|}{|1-x_j^2|}. $$ So, we replace $\pm c_j$ and $\pm\bar c_j$ by $\pm x_j$ and $\pm x_j$ (or simply $\pm c_j$ by $\pm x_j$ if $c_j$ is purely imaginary).

After this procedure has been applied, we obtain a new polynomial whose roots are in $[-1,1]$ and have even multiplicities, and its values at $\pm1$ are equal to $1$. So it is a square of some polynomial which is even/odd (since the roots are still split into pairs of opposite numbers). On the other hand, its values at every $x\in[-1,1]$ do not exceed the values of $r$ at the same points, as was showed above. So the obtained polynomial is not worse in the integral sense, as required. The lemma is proved.

$\endgroup$
  • 2
    $\begingroup$ Sorry to be dense, but please say why it has to be the square of another polynomial. I can see that any zeros in the critical interval have even multiplicity, but why can't the polynomial be negative elsewhere (as allowed by OP)? $\endgroup$ – Brendan McKay Oct 9 '15 at 22:54
  • $\begingroup$ The last part of the answer (after `finally') is about it; I'll try to expand it. In short: If our polynomial has a non-real root, or if it has real roots outside $[-1,1]$, then we may replace these roots by some root on $[-1,1]$ so as to lower the values of the polynomial at all points in $(-1,1)$(and keep it nonnegative). $\endgroup$ – Ilya Bogdanov Oct 10 '15 at 7:05
  • $\begingroup$ Expanded (or, I would say, rewritten). $\endgroup$ – Ilya Bogdanov Oct 10 '15 at 7:47
17
$\begingroup$

For better symmetry, let me change the boundary points to $(-1,1)$ and $(1,1)$. Then it is clear that we may assume $p_n$ is an even function (and thus you really want $P_n$ to be polynomials of degree at most $n$, otherwise you'll be likely to have an infimum rather than an actual minimum): $p_{2k+1} = p_{2k}$. I get $$ \eqalign{p_0(x) = 1, & a_0 = 2\cr p_2(x) = x^2, & a_2 = \dfrac{2}{3}\cr p_4(x) = \dfrac{(5 x^2 - 1)^2}{16},& a_4 = \dfrac{1}{3}\cr p_6(x) = \dfrac{x^2}{16} (7 x^2 - 3)^2,& a_6 = \dfrac{1}{5}\cr p_8(x) = \dfrac{1}{64} (21 x^4 - 14 x^2 + 1)^2, & a_8 = \dfrac{2}{15}\cr p_{10}(x) = \dfrac{x^2}{64} (33 x^4 - 30 x^2 + 5)^2, & a_{10} = \dfrac{2}{21}\cr p_{12}(x) = \dfrac{1}{4096} (429 x^6 - 495 x^4 + 135 x^2 - 5)^2, & a_{12} = \dfrac{1}{14}}$$ Well, so far it looks like $a_{2n} = \dfrac{4}{(n+1)(n+2)}$

$\endgroup$
  • 4
    $\begingroup$ How were these computed? $\endgroup$ – Nate Eldredge Oct 9 '15 at 0:03
  • $\begingroup$ The leading coefficients look like Catalan numbers when the polynomials are normalized to $\sqrt{2^{2n} p_{2n}(x)}$. $\endgroup$ – Douglas Zare Oct 9 '15 at 1:51
  • 3
    $\begingroup$ The next coefficients match $-{2n \choose n-2}$. The whole triangle looks like oeis.org/A234950 read skewed, with alternating signs. See oeis.org/A062991 for a signed version. $\endgroup$ – Douglas Zare Oct 9 '15 at 3:43
  • 3
    $\begingroup$ For $n$ even, $$p_{2n} = \prod_{i=1}^{n/2} \dfrac{(x^2 -c_i^2)^2}{(1-c_i^2)^2}$$ For $n$ odd, there's also a factor of $x^2$. Differentiate $a_{2n} =\int_{-1}^1 p_{2n}(x)\; dx$ with respect to each $c_i$, solve, check which solution gives the least $a_{2n}$. $\endgroup$ – Robert Israel Oct 9 '15 at 4:49

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.