The minimum root separation of a polynomial

Authors:
George E. Collins and Ellis Horowitz

Journal:
Math. Comp. **28** (1974), 589-597

MSC:
Primary 12D10; Secondary 30A08

MathSciNet review:
0345940

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The minimum root separation of a complex polynomial *A* is defined as the minimum of the distances between distinct roots of *A*. For polynomials with Gaussian integer coefficients and no multiple roots, three lower bounds are derived for the root separation. In each case, the bound is a function of the degree *n* of *A* and the sum *d* of the absolute values of the coefficients of *A*. The notion of a seminorm for a commutative ring is defined, and it is shown how any seminorm can be extended to polynomial rings and matrix rings, obtaining a very general analogue of Hadamard's determinant theorem.

**[1]**G. E. Collins, "Computing time analyses for some arithmetic and algebraic algorithms,"*Proc. 1968 Summer Institute on Symbolic Mathematical Computation*, IBM Corp., Cambridge, Mass., 1961, pp. 197-231.**[2]**George E. Collins,*The calculation of multivariate polynomial resultants*, J. Assoc. Comput. Mach.**18**(1971), 515–532. MR**0298921****[3]**Lee E. Heindel,*Integer arithmetic algorithms for polynomial real zero determination*, J. Assoc. Comput. Mach.**18**(1971), 533–548. MR**0300434****[4]**Donald E. Knuth,*The art of computer programming. Vol. 2: Seminumerical algorithms*, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont, 1969. MR**0286318****[5]**R. G. K. Loos, "A constructive approach to algebraic numbers,"*Math. of Comp.*(submitted.)**[6]**Henryk Minc and Marvin Marcus,*Introduction to linear algebra*, The Macmillan Co., New York; Collier-Macmillan Ltd., London, 1965. MR**0188221****[7]**Michael T. McClellan,*The exact solution of systems of linear equations with polynomial coefficients*, J. Assoc. Comput. Mach.**20**(1973), 563–588. MR**0347068****[8]**D. R. Musser,*Algorithms for Polynomial Factorization*, Univ. of Wisconsin Comp. Sci. Dept. Technical Report No. 134 (Ph.D Thesis), Sept. 1971, 174 pp.**[9]**J. R. Pinkert,*Algebraic Algorithms for Computing the Complex Zeros of Gaussian Polynomials*, Univ. of Wisconsin Comp. Sci. Dept. Ph.D. Thesis, May 1973, Technical Report No. 188, July 1973.**[10]**B. L. van der Waerden,*Moderne Algebra*. Vol. I, Springer, Berlin, 1930; English transl., Ungar, New York, 1949. MR**10**, 587.

Retrieve articles in *Mathematics of Computation*
with MSC:
12D10,
30A08

Retrieve articles in all journals with MSC: 12D10, 30A08

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1974-0345940-X

Keywords:
Polynomial zeros,
root separation,
Hadamard's theorem,
seminorms

Article copyright:
© Copyright 1974
American Mathematical Society