Nonnegativity certificates for finite semi-algebraic sets

<div> We introduce new certificates for nonnegativity of multivariate polynomials with rational coefficients over zero-dimensional semi-algebraic sets. They are perfectly complete, certifying every nonnegative polynomial, and perfectly sound, correctly identifying negativity. We rely on resultants computations and Rational Univariate Representations (RUR) and make no assumptions on the input. For the univariate case, we introduce a perturbation technique that avoids root approximation and does not alter the (bit)size of the input. For multivariate polynomials, we make a reduction to the univariate case using RUR. For the dense case, we compute a certificate in OB(d 4n+3 (d + τ )) bit operations; it involves numbers of bitsize O(d 3n+2 (d + τ )), where n is the number of variables, d the degree, and τ the maximum coefficient bitsize of the polynomials. For the sparse case, we provide the first sparse certificate based on the Newton polytope Q of the input polynomials. We compute in OB(vol(Q) 8 (n!) 8 2 5n+3 (n + τ )), For semi-algebraic sets with s inequalities, we present two approaches. The first performs a reduction to the algebraic case and has complexity OB(2 (3ω+3)s d 5n τ ); it is purely algebraic approach and does not require root approximation. The second exploits approximate Lagrange interpolation and matches the O(sd 4n τ ) bitsize bounds of recent work by Baldi, Krick, and Mourrain [2] while improving complexity by orders of magnitude and removing all structural assumptions on the input. Additionally, we provide a witness of negativity, ensuring that we either obtain a certificate or it does not exist. </div>