A characterization of polynomials whose high powers have non-negative coefficients
- Department of Math. Stats. and Computer Science, University of Illinois at Chicago
- More about Marcus Michelen
- Department of Math. and Math. Stats., University of Cambridge
- More about Julian Sahasrabudhe
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 Pm has non-negative coefficients for all sufficiently large m, which the authors call eventually non-negative. If a=(a0,a1,a2,…) is the sequence of coefficients of P, then the sequence of coefficients of Pm is the m-fold convolution a∗a∗⋯∗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)=xrP(xs) 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)=∑nk=0akxk to the “reverse” polynomial Q(x)=∑nk=0akxn−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 Pm is am0, so if a0 is negative, Pm will have a negative coefficient for every odd m.
A more general and more interesting class of examples is given as follows. Let A⊂N be the set of k such that ak>0 and let B⊂N be the set of k such that ak<0. Now suppose that the minimal element j of B cannot be written as a sum of elements of A. Then the coefficient of xj in Pm is easily seen to be amj, so if aj<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 akzk must be the same for every k such that ak≠0, which implies that the arguments of the corresponding powers zk are the same. This can happen only if z has argument 2π/r for some integer r≥2 and all the k for which ak≠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)=xkQ(xℓ), 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 Pm up to the coefficient of xmd are strictly positive. The conditions turn out to be that P should be strongly positive and that a0,a1,ad−1 and ad 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.