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

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

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]**G. E. Collins, "The calculation of multivariate polynomial resultants,"*J. Assoc. Comput. Mach.*, v. 18, 1971, pp. 515-532. MR**45**#7970. MR**0298921 (45:7970)****[3]**L. E. Heindel, "Integer arithmetic algorithms for polynomial real zero determination,"*J. Assoc. Comput. Mach.*, v. 18, 1971, pp. 533-548. MR**45**#9480. MR**0300434 (45:9480)****[4]**D. E. Knuth,*The Art of Computer Programming*. Vol. 2:*Seminumerical Algorithms*, Addison-Wesley, Reading, Mass., 1969. MR**44**#3531. MR**0286318 (44:3531)****[5]**R. G. K. Loos, "A constructive approach to algebraic numbers,"*Math. of Comp.*(submitted.)**[6]**H. Minc & M. Marcus,*Introduction to Linear Algebra*, Macmillan, New York, 1965. MR**32**#5660. MR**0188221 (32:5660)****[7]**M. T. McClellan, "The exact solution of systems of linear equations with polynomial coefficients,"*J. Assoc. Comput. Mach.*, v. 20, 1973, pp. 563-588. MR**0347068 (49:11788)****[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