Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Polynomial minimum root separation
HTML articles powered by AMS MathViewer

by Siegfried M. Rump PDF
Math. Comp. 33 (1979), 327-336 Request permission

Abstract:

The minimum root separation of an arbitrary polynomial P is defined as the minimum of the distances between distinct (real or complex) roots of P. Some asymptotically good lower bounds for the root separation of P are given, where P may have multiple zeros. There are applications in the analysis of complexity of algorithms and in the theory of algebraic and transcendental numbers.
References
    A. CAUCHY, "Analyse algébrique," in Oeuvres Complètes, II série, tome III, p. 398, formula (48), Paris, 1847.
  • George E. Collins and Ellis Horowitz, The minimum root separation of a polynomial, Math. Comp. 28 (1974), 589–597. MR 345940, DOI 10.1090/S0025-5718-1974-0345940-X
  • G. E. COLLINS & R. G. K. LOOS, "Polynomial real root isolation by differentiation," Proc. 1976 ACM Symposium on Symbolic and Algebraic Computation, August 1976, pp. 15-25.
  • A. O. Gel′fond, Transcendental and algebraic numbers, Dover Publications, Inc., New York, 1960. Translated from the first Russian edition by Leo F. Boron. MR 0111736
  • R. Güting, Approximation of algebraic numbers by algebraic numbers, Michigan Math. J. 8 (1961), 149–159. MR 132722
  • R. Güting, Polynomials with multiple zeros, Mathematika 14 (1967), 181–196. MR 223544, DOI 10.1112/S002557930000379X
  • Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms. MR 0378456
  • E. Landau, Sur quelques théorèmes de M. Petrovitch relatifs aux zéros des fonctions analytiques, Bull. Soc. Math. France 33 (1905), 251–261 (French). MR 1504527
  • R. G. K. LOOS, A Constructive Approach to Algebraic Numbers, Stanford University, 27 pages, April 1973. K. MAHLER, "Zur Approximation der Exponentialfunktion und des Logarithmus, I," J. Reine Angew. Math., v. 166, 1932, pp. 118-136.
  • K. Mahler, An application of Jensen’s formula to polynomials, Mathematika 7 (1960), 98–100. MR 124467, DOI 10.1112/S0025579300001637
  • K. Mahler, An inequality for the discriminant of a polynomial, Michigan Math. J. 11 (1964), 257–262. MR 166188
  • M. Mignotte, An inequality about factors of polynomials, Math. Comp. 28 (1974), 1153–1157. MR 354624, DOI 10.1090/S0025-5718-1974-0354624-3
  • M. MIGNOTTE, "Some problems about polynomials," Proc. 1976 ACM Symposium on Symbolic and Algebraic Computation, August 1976, pp. 227-228.
  • Morris Marden, The Geometry of the Zeros of a Polynomial in a Complex Variable, Mathematical Surveys, No. 3, American Mathematical Society, New York, N. Y., 1949. MR 0031114
  • Nikola Obreschkoff, Verteilung und Berechnung der Nullstellen reeller Polynome, VEB Deutscher Verlag der Wissenschaften, Berlin, 1963 (German). MR 0164003
  • S. M. RUMP, "Isolierung der reellen Nullstellen algebraischer Polynome," Bericht der Arbeitsgruppe Computer Algebra, Universität Kaiserslautern, v. 10, 1976, 121 pp.
  • Wolfgang M. Schmidt, Approximation to algebraic numbers, Série des Conférences de l’Union Mathématique Internationale, No. 2, Université de Genève, Secrétariat de l’Enseignement Mathématique, Geneva, 1972. MR 0344203
  • Theodor Schneider, Einführung in die transzendenten Zahlen, Springer-Verlag, Berlin-Göttingen-Heidelberg, 1957 (German). MR 0086842
  • B. L. van der WAERDEN, Algebra, Springer-Verlag, New York, 1966.
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC: 12D10
  • Retrieve articles in all journals with MSC: 12D10
Additional Information
  • © Copyright 1979 American Mathematical Society
  • Journal: Math. Comp. 33 (1979), 327-336
  • MSC: Primary 12D10
  • DOI: https://doi.org/10.1090/S0025-5718-1979-0514828-8
  • MathSciNet review: 514828