FoCM 2014 conference
Workshop A6 - Real Number Complexity
December 11, 18:00 ~ 18:30 - Room C11
Elementary recursive degree bounds for Positivstellensatz, Hilbert 17th problem and Real Nullstellensatz (part II)
Marie-Françoise Roy
Université de Rennes 1, France - marie-francoise.roy@univ-rennes1.fr
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 (Universite de Franche-Comté, France) and Daniel Perrucci (Universidad de Buenos Aires, Argentina).