Séminaire Marelle : Root isolation for one variable polynomials with rational coefficients

On Friday 04/06/2010, at 11h, in room Byron Beige.

Speaker: Yves Bertot.

Title: Root isolation for one variable polynomials with rational coefficients.

Given a one variable polynomial with rational coefficients, we want to isolate its roots. In other words, we want to find a finite list of intervals such that each interval contains exactly one root of the polynomial and each root is in one of the intervals.

The approach we study is based on Bernstein coefficients. These coefficients give a discrete approximation of the behavior of a polynomial in a given closed interval. We rely on a sufficient condition concerning these coefficients (let’s call this condition C1): if the Bernstein coefficients, taken in order, have only one alternation, then the polynomial is guaranteed to have exactly one root in the corresponding interval.

The bulk of our work is to prove condition C1.

We study the relations between the coefficients and roots of a given polynomial on a given bounded interval and the coefficients and roots of the image of this polynomial after some transformations. These transformations relate the coefficients of a polynomial in the standard monomial basis to the coefficients of another polynomial in Bernstein bases. They also relate the positive roots of a polynomial to roots of the other polynomial in some bounded interval. In fact, this establishes a relation between condition C1 and Descartes’ law of sign.