Certificates of positivity in the Bernstein basis

Let P ∈ ℤ [Script X] be a polynomial of degree p with coefficients in the monomial basis of bit-size bounded by τ. If P is positive on [-1,1], we obtain a certificate of positivity (i.e., a description of P making obvious that it is positive) of bit-size O(p4(τ +log2 p)). Previous comparable results had a bit-size complexity exponential in p and τ (Powers and Reznick in Trans. Am. Math. Soc. 352(10):4677-4692, 2000; Powers and Reznick in J. Pure Appl. Algebra 164:221-229, 2001). © 2007 Springer Science+Business Media, LLC.