New bounds for the Descartes method
Werner Krandick, Kurt Mehlhorn · ACM SIGSAM Bulletin · 2005
We give a new bound for the number of recursive subdivisions in the Descartes method for polynomial real root isolation. Our proof uses Ostrowski's theory of normal power series from 1950 which has so far been overlooked in the literature. We combine Ostrowski's results with a theorem of Davenport from 1985 to obtain our bound. We also characterize normality of cubic polynomials by explicit conditions on their roots and derive a generalization of one of Ostrowski's theorems. The poster is based on a paper that is to appear in the Journal of Symbolic Computation [1]. In addition to the results of the paper the poster presents facsimiles of pertinent mathematical works in French, German, and English that span a period of 400 years. We use color-coding to relate the historical results to our theory.