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

Abstract

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