# Characterizing convex polynomials

Let $p=\sum_{i=0}^{n}a_ix^i$. Under what conditions on the coefficients $a_i$ is $p$ convex? Strictly convex?

-
This is about the sign of the second derivative. –  Charles Matthews Jun 21 '10 at 19:54

p is convex iff p'' is non-negative. And a polynomial is non-negative iff it is the modulus of the square of a polynomial with complex coefficients. So p must be of even degree (or of degree 0 or 1).

If we write $p''=|q|^2$, then we see that p is convex iff there exist complex coefficients $q_0...q_l$, $l \leq n/2$, such that, for all $k$, $$k(k-1)\ a_k=\ \ \Sigma_{i,j \ \ s.t.\atop i+j=k-2} \quad q_i \bar{q}_j$$

This is not very explicit, but at least this may be used to generate convex polynomials.

-

To add some more stuff to @coudy's answer. We need to check whether $p''$ is nonnegative. To that end let us recall some basic results (copied from another MO answer of mine), discussed in these lecture notes; these results are helpful for checking if a univariate polynomial is nonnegative.

Theorem A univariate polynomial is nonnegative if and only if it is a sum of squares.

Theorem Let $\mathbf{x}=[1,x,x^2,\ldots,x^m]^T$, and let $P(x)$ have degree $2m$. Then, $P(x)$ is nonnegative if and only if there exists a $m+1 \times m+1$ positive semidefinite matrix $Q$ such that $P(x) = \mathbf{x}^TQ\mathbf{x}$.

Let $P(x)=\sum_{i=0}^{2m} p_ix^i$. It can be further shown that the matrix $Q$ must satisfy \begin{equation*} p_i = \sum_{j+k=i} Q_{jk},\qquad i=0,1,\ldots,2m. \end{equation*}

Theorem If we can find a positive semidefinite matrix $Q$ that satisfies the above linear constraints (this can be done using regular semidefinite programming software), then the polynomial $P(x)=\sum_{i=0}^{2m} p_ix^i$ is nonnegative or SOS, otherwise not.

-

@coudy -

If $p''(x) = \sum_{k=2}^{n}k(k-1)a_{k}x^{k-2}$ and $q(x) = \sum_{l=0}^{(n-2)/2}q_{l}x^{l}$, shouldn't we have for $2 \leq k \leq n$ $$k(k-1)a_{k} = \sum_{i,j \text{ s.t. } i+j=(k-2)} q_{i}\bar{q}_{j}?$$

-
indeed, there was a typo in my answer. This is now corrected, thanks. –  coudy Sep 22 '12 at 18:53

To add to @coudy's answer: a polynomial is nonnegative if and only if it is a sum of squares, which gives a slightly different set of equations to be satisfied by the second derivative.

-

p must be of even order, and its leading coefficient must be positive. Moreover, p is strictly convex (convex) if p'' has no real zeros (no real zeros of odd multiplicity). The number of real zeros of a polynomial is characterized by Sturm's theorem (http://en.wikipedia.org/wiki/Sturm's_theorem#Number_of_real_roots).

-