An algebraic certificate for Budan's theorem
type: Item
instance of: scholarly article
title: An algebraic certificate for Budan's theorem
zbMATH Open document ID: 1238.12002
author: Daniel Bembé
published in: Journal of Pure and Applied Algebra
publication date: 2011-04-29T00:00:00Z
review text: Budan's Theorem states that if \(a,b\) are two elements of an ordered field \(K\) with \(a<b\), then the number of sign changes in the sequence \(\left( f(a),f'(a),f''(a),\dots\right)\) is not less than the number of sign changes in \(\left(f(b),f'(b),f''(b),\dots\right)\). In this short paper, the author presents 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. The author presents two different algorithms producing an algebraic certificate for Budan's Theorem. The author claims that this is a first step towards reducing the complexity of constructing the real closure of an ordered field.
Mathematics Subject Classification ID: 12D15
Mathematics Subject Classification ID: 12J15
Mathematics Subject Classification ID: 14Q20
zbMATH DE Number: 5882428
zbMATH Keywords: Budan's Theorem
zbMATH Keywords: algebraic certificate
zbMATH Keywords: real closure
zbMATH Keywords: Sturm sequence
reviewed by: Luis David Garcia Puente
MaRDI profile type: Publication
full work available at URL: j.jpaa.2010.08.016
OpenAlex ID: W2004696957
cites work: Q3770650
cites work: Sur la vie et l'oeuvre de François Budan (1761--1840). (On the life and work of F. Budan)
cites work: Algorithms in real algebraic geometry
cites work: Generalized Budan--Fourier theorem and virtual roots
cites work: Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets
cites work: Dynamical method in algebra: Effective Nullstellensätze
cites work: Q5781066
cites work: Anneaux preordonnes
cites work: Q3973341
cites work: Q3358841
cites work: Q2716044
cites work: Q3601991
cites work: The \(K\)-moment problem for compact semi-algebraic sets
cites work: An algorithmic approach to Schmüdgen's Positivstellensatz
cites work: A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
DOI: 10.1016/J.JPAA.2010.08.016
description: scientific article; zbMATH DE number 5882428