On nonnegative cosine polynomials with nonnegative integral coefficients

We show that there exist ${p_0} > 0$ and ${p_1}, \ldots ,{p_N}$ nonnegative integers, such that

$$0 \leqslant p(x) = {p_0} + {p_1}\cos x + \cdots + {p_N}\cos Nx$$

and ${p_0} \ll {s^{1/3}}$ for $s = \sum\nolimits_{j = 0}^N {{p_j}}$, improving on a result of Odlyzko who showed the existence of such a polynomial $p$ that satisfies ${p_0} \ll {(s\log s)^{1/3}}$. Our result implies an improvement of the best known estimate for a problem of Erdős and Szekeres. As our method is nonconstructive, we also give a method for constructing an infinite family of such polynomials, given one good "seed" polynomial.