An effective Positivstellensatz over the rational numbers for finite semialgebraic sets

We study the problem of representing multivariate polynomials with rational coefficients, which are nonnegative and strictly positive on finite semialgebraic sets, using rational sums of squares. We focus on the case of finite semialgebraic sets <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S"> <mml:semantics> <mml:mi>S</mml:mi> <mml:annotation encoding="application/x-tex">S</mml:annotation> </mml:semantics> </mml:math> </inline-formula> defined by equality constraints, generating a zero-dimensional ideal <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper I"> <mml:semantics> <mml:mi>I</mml:mi> <mml:annotation encoding="application/x-tex">I</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , and by nonnegative sign constraints. First, we obtain existential results. We prove that a strictly positive polynomial <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="f"> <mml:semantics> <mml:mi>f</mml:mi> <mml:annotation encoding="application/x-tex">f</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with coefficients in a subfield <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K"> <mml:semantics> <mml:mi>K</mml:mi> <mml:annotation encoding="application/x-tex">K</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper R"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">R</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathbb {R}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> has a representation in terms of weighted Sums-of-Squares with coefficients in this field, even if the ideal <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper I"> <mml:semantics> <mml:mi>I</mml:mi> <mml:annotation encoding="application/x-tex">I</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is not radical. We generalize this result to the case where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="f"> <mml:semantics> <mml:mi>f</mml:mi> <mml:annotation encoding="application/x-tex">f</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is nonnegative on <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S"> <mml:semantics> <mml:mi>S</mml:mi> <mml:annotation encoding="application/x-tex">S</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis f right-parenthesis plus left-parenthesis upper I colon f right-parenthesis equals 1"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>f</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>+</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mi>I</mml:mi> <mml:mo>:</mml:mo> <mml:mi>f</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">(f) + (I:f)=1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . We deduce that nonnegative polynomials with coefficients in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K"> <mml:semantics> <mml:mi>K</mml:mi> <mml:annotation encoding="application/x-tex">K</mml:annotation> </mml:semantics> </mml:math> </inline-formula> can be represented in terms of Sum-of-Squares of polynomials with coefficients in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K"> <mml:semantics> <mml:mi>K</mml:mi> <mml:annotation encoding="application/x-tex">K</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , when the ideal is radical. Second, we obtain degree bounds for such Sums-of-Squares representations, which depend linearly on the regularity of the ideal and the degree of the defining equations, when they form a graded basis. Finally, we analyze the bit complexity of the Sums-of-Squares representations for polynomials with coefficients in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper Q"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">Q</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathbb {Q}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , in the case the ideal is radical. The bitsize bounds are linear in the bitsize of the input polynomials, quadratic or cubic in the Bezout bound, and linear in the regularity, generalizing and improving previous results obtained for special zero dimensional ideals. As an application in the context of polynomial optimization, we retrieve and improve results on the finite convergence and exactness of the moment/Sums-of-Squares hierarchy.