Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Effectivity Issues and Results for Hilbert's 17th Problem
Speaker:Marie-Francoise Roy
coming from:Universit├ę de Rennes 1
Speakers Bio:
Event Type:Talk
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:MPI Audience
Date, Time and Location
Date:Thursday, 25 February 2016
Duration:60 Minutes
Building:E1 4
If a polynomial is everywhere non negative, it is a sum of squares of rational fractions (which is the positive solution of Hilbert's 17th problem). This is an example of a certificate for positivity (more precisely non-negativity), i.e. an algebraic identify certifying that the polynomial is non-negative.

But how to construct this sum of squares from a proof of the non negativity?

Artin's initial proof of Hilbert's 17th problem in 1927 was very indirect, and did not produce explicitly the sum of squares. Effective methods have been designed since then (starting from Kreisel and his students) but the degree estimate of the corresponding constructions were primitive recursive functions.

In this talk, we recall the initial proof of Artin and present a new constructive proof for Hilbert's 17th problem, and show that following this construction, the degree of the polynomials in the identity is bounded by an elementary recursive function in the number of variables, and the degree of the polynomial (more precisely a tower of five exponentials). We end with a discussion on what could be hoped for.

Based on joint work with Henri Lombardi and Daniel Perrucci.

Name(s):Michael Sagraloff
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Michael Sagraloff, 02/05/2016 12:07 PM
Last modified:
Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Michael Sagraloff, 02/12/2016 10:37 AM
  • Michael Sagraloff, 02/05/2016 12:07 PM -- Created document.