Certificates of nonnegativity of multivariate polynomials with zero-dimensional gradient ideal and infimum attained

<div> We study the problem of certifying nonnegativity of multivariate polynomials with rational coefficients, under the assumptions that the polynomial attains its infimum and its gradient ideal is zero-dimensional. We introduce a new certificate, based on Rational Univariate Representations (RUR), that is both perfectly complete, every nonnegative polynomial is always certified, and perfectly sound, any polynomial that is not nonnegative is correctly identified. The certificate reduces the problem to checking whether a univariate polynomial admits a weighted sum-of-squares decomposition modulo an ideal defined by the RUR, thereby avoiding the radicality assumption that limits other existing approaches. We present the algorithm SOS-RUR, which produces such a certificate or returns a rational witness point where the polynomial takes a negative value. For a polynomial in n variables of degree d and maximum coefficient bitsize τ , SOS-RUR runs in bit complexity OB(e ωn+O(lg n) d (ω+2)n (d + τ )), and the polynomials in the certificate have coefficients of bitsize at most O(d 2n+1 (d + nτ )), when we ignore polylogarithmic factors. If the polynomial can take negative values, then the algorithm outputs a rational witness point with coordinates of bitsize O(nd 2n+2 (d + nτ )). In the special case where the gradient ideal is radical, in addition to the improvement in the bit size, our certificate specializes in a representation with improved degree bounds, better by an additive factor of d, and lower bit complexity compared to previous results, together with an explicit validation of the RUR, which had previously been overlooked. We also consider sparse certificates, that their structure, complexity, and (bitsize) bounds depend on the Newton polytope Q of the input polynomial. To compute them, we rely on a Monte Carlo algorithm to obtain a sparse RUR for unmixed systems, which is of independent interest. In particular, we compute the sparse certificate in OB(n 6n vol(Q) 6 τ ) bit operations, where vol(Q) is the volume of Q. The certificate involves sparse polynomials of degree at most 2 n+2 n! 2 vol(Q) 2 and coefficient bitsize O(n 4n vol(Q) 4 τ ). These bounds provide sharper guaranties in the presence of sparsity, as they are input sensitive. This result contributes to the ongoing effort to encode polynomial optimization problems through compact descriptions, in our case by exploiting the sparsity of the input, thereby extending the current frontier of tractability from a computational point of view. Overall, our results extend the scope of certificates modulo the gradient ideal by eliminating the radicality requirement, introduce a variant that exploits the sparsity of the input polynomial, improve existing bitsize complexity bounds by at least a factor of d n , and provide efficient, verifiable algebraic certificates of nonnegativity for polynomial optimization. </div>