A characterization of polynomials whose high powers have non-negative coefficients

A characterization of polynomials whose high powers have non-negative coefficients, Discrete Analysis 2020:20, 16 pp.

Polynomials with non-negative coefficients are an important class of polynomials that appear in many contexts. This paper characterizes polynomials $P$ with the property that $P^m$ has non-negative coefficients for all sufficiently large $m$, which the authors call eventually non-negative. If $a=(a_0,a_1,a_2,\dots)$ is the sequence of coefficients of $P$, then the sequence of coefficients of $P^m$ is the $m$-fold convolution $a*a*\dots*a$, so the result of the paper is equivalent to characterizing finitely supported sequences for which all sufficiently large convolution powers are non-negative sequences. The characterization consists in showing that two clearly necessary conditions are also sufficient.

A few simple observations help to make sense of these conditions. First, note that any result must be invariant under translation and dilation of the sequence of coefficients. In terms of polynomials, this states that if $P$ is a polynomial and $Q$ is a polynomial given by the formula $Q(x)=x^rP(x^s)$ for some integer $r$ and positive integer $s$, then $P$ is eventually non-negative if and only if $Q$ is eventually non-negative.

Similarly, the result must be invariant under passing from a polynomial $P(x)=\sum_{k=0}^na_kx^k$ to the “reverse” polynomial $Q(x)=\sum_{k=0}^na_kx^{n-k}$, since the corresponding statement about convolutions is clearly invariant in this way.

Note also that it is easy to find examples of polynomials that are not eventually non-negative. For example, the constant coefficient of $P^m$ is $a_0^m$, so if $a_0$ is negative, $P^m$ will have a negative coefficient for every odd $m$.

A more general and more interesting class of examples is given as follows. Let $A\subset\mathbb N$ be the set of $k$ such that $a_k>0$ and let $B\subset\mathbb N$ be the set of $k$ such that $a_k<0$. Now suppose that the minimal element $j$ of $B$ cannot be written as a sum of elements of $A$. Then the coefficient of $x^j$ in $P^m$ is easily seen to be $a_j^m$, so if $a_j<0$, then again $P$ is not eventually non-negative.

A slightly more complicated argument (see Lemma 17 of the paper) shows that the minimality was not needed above: if there exists any element of $B$ that cannot be written as a sum of elements of $A$, then $P$ is not eventually non-negative.

The authors say that $P$ has the positive covering property if every element of $B$ can be written as a sum of elements of $A$, and if the same holds for the reverse polynomial.

A further condition enters the picture, called strong positivity. A polynomial $P$ is said to be strongly positive if $P(|z|)>|P(z)|$ for every complex number $z$ that is not a non-negative real. Note that if $P$ has non-negative coefficients but fails to be strongly positive, then the arguments of $a_kz^k$ must be the same for every $k$ such that $a_k\ne 0$, which implies that the arguments of the corresponding powers $z^k$ are the same. This can happen only if $z$ has argument $2\pi/r$ for some integer $r\geq 2$ and all the $k$ for which $a_k\ne 0$ lie in an arithmetic progression with common difference $r$.

From these observations it is a short step to formulating the main result of the paper, which states that $P$ is eventually non-negative if and only if it is of the form $P(x)=x^kQ(x^\ell)$, where $Q$ is strongly positive and has the positive covering property. This proves a conjecture of Bergweiler, Eremenko and Sokal.

An earlier result of De Angelis characterizes eventually positive polynomials: that is, polynomials $P$ of degree $d$ such that for all sufficiently large $m$ the coefficients of $P^m$ up to the coefficient of $x^{md}$ are strictly positive. The conditions turn out to be that $P$ should be strongly positive and that $a_0,a_1,a_{d-1}$ and $a_d$ should be positive. These conditions imply that $P$ and its reverse satisfy the positive covering property, and it turns out to be possible to deduce De Angelis’s theorem from the result of this paper. The main reason that understanding eventually non-negative polynomials turned out to be harder is the extra symmetry mentioned earlier: the fact that the problem is invariant under dilations and not just translations and reflections.

The proof of the main result divides into two parts: one part is purely combinatorial and the other part estimates coefficients by expressing them as contour integrals and using the saddle-point method.