Assessing non-negativity of multivariate polynomials over the reals, through the computation of { \em certificates of non-negativity}, is a topical issue in polynomial optimization. This is usually tackled through the computation of { \em sums-of-squares decompositions} which rely on efficient numerical solvers for semi-definite programming. This method faces two difficulties. The first one is that the certificates obtained this way are { \em approximate} and then non-exact. The second one is due to the fact that not all non-negative polynomials are sums-of-squares. In this paper, we build on previous works by Parrilo, Nie, Demmel and Sturmfels who introduced certificates of non-negativity modulo { \em gradient ideals}. We prove that, actually, such certificates can be obtained { \em exactly}, over the rationals if the polynomial under consideration has rational coefficients and we provide { \em exact} algorithms to compute them. We analyze the bit complexity of these algorithms and deduce bit size bounds of such certificates.
Categories: cs.SC math.OC