Elementary recursive degree bounds for Positivstellensatz, Hilbert 17th problem and Real Nullstellensatz (part I)

HENRI LOMBARDI; DANIEL PERRUCCI; MARIE-FRANCOISE ROY

Montevideo

Workshop; Real Number Complexity - Foundations of Computational Mathematics; 2014

Foundations of Computational Mathematics

Hilbert 17th problem is to express a non-negative polynomial as a sum of squares of rational functions. The original proof by Artin is non-constructive and gives no information on the degree bounds. A more general problem is to give an identity which certifies the unrealizability of a system of polynomial equations and inequalities. The existence of such an identity is guaranteed by the Positivstellensatz. Hilbert 17th problem, as well as Real Nullstellensatz follow easily from such identities. In these two talks, we explain our new constructive proof which provides elementary recursive bounds for the Positivstellensatz and Hilbert 17 problem, namely a tower of five levels of exponentials. Joint work with Henri Lombardi (Université de Franche-Comté, France) and Marie-Françoise Roy (Université de Rennes 1, France).