An algebraic certificate for Budan’s theorem

The existing algorithms to construct the real closure of an ordered field involve very high complexities. These algorithms are based on Sturm’s theorem which we suspect to be one reason for the complexities since all known proofs of Sturm’s theorem use Rolle’s theorem which is problematic in a constructive context.Therefore we propose to replace the use of Sturm’s theorem by Budan’s theorem. In this paper we present as a first step in this direction an algebraic certificate for Budan’s theorem. An algebraic certificate is a certain kind of proof of a statement. In particular, it is an algorithm which produces, from an arbitrary data in the premise of the statement, explicit (in)equalities which express the conclusion.