An algebraic certificate for Budan's theorem

DOI10.1016/J.JPAA.2010.08.016MaRDI QIDQ531342zbMATH OpenOpenAlexFDO

Authors Daniel Bembé

Publication date 29 April 2011

Published in Journal of Pure and Applied Algebra (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jpaa.2010.08.016

zbMATH Keywords

algebraic certificateBudan's Theoremreal closureSturm sequence

Mathematics Subject Classification ID

Fields related with sums of squares (formally real fields, Pythagorean fields, etc.) (12D15) Ordered fields (12J15) Effectivity, complexity and computational aspects of algebraic geometry (14Q20)

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.

Recommendations

• Algebraic certificates for Budan's theorem
• The Fundamental Theorem of Algebra Made Effective: An Elementary Real-algebraic Proof via Sturm Chains
• scientific article; zbMATH DE number 29408
• scientific article; zbMATH DE number 1023365
• scientific article; zbMATH DE number 4210287

Cites work

• A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
• Algorithms in real algebraic geometry
• An algorithmic approach to Schmüdgen's Positivstellensatz
• Anneaux preordonnes
• Dynamical method in algebra: Effective Nullstellensätze
• Generalized Budan--Fourier theorem and virtual roots
• scientific article; zbMATH DE number 1601019 (Why is no real title available?)
• scientific article; zbMATH DE number 4210287 (Why is no real title available?)
• scientific article; zbMATH DE number 4029737 (Why is no real title available?)
• scientific article; zbMATH DE number 16655 (Why is no real title available?)
• scientific article; zbMATH DE number 3041741 (Why is no real title available?)
• Positivity and sums of squares: a guide to recent results
• Sur la vie et l'oeuvre de François Budan (1761--1840). (On the life and work of F. Budan)
• The K-moment problem for compact semi-algebraic sets
• Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets

Cited in

(1)

• Algebraic certificates for Budan's theorem

This page was built for publication: An algebraic certificate for Budan's theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q531342)