Polynomial minimum root separation. (English) Zbl 1008.12001
The problem considered in this paper is the important following one: given an univariate integer polynomial \(P\) study the minimum distance between distinct roots of \(P\), say \(\text{sep} (P)\), in terms of the (naïve) height of \(P\), i.e. the maximum of the absolute values of the coefficients of this polynomial.
This problem has been studied in several directions: lower bounds on \(\text{sep}(P)\) (obtained by suitable Liouville estimates), explicit examples for which \(\text{sep}(P)\) is small (such as \((aX-1)(X^n-aX+1)\) and \(X^n-2(aX-1)^2\) for large \(a\) and \(n\geq 3\)).
The main contribution of this paper is a massive experimental study. According to this work, the author considers that this leads to conjecture that the “worst” case should be approximatively the square root of the best theoretical lower bound presently known. In my opinion, the difficulty with extensive computational studies is that interesting special examples may be too far or to rare to be found. In any case, the problem remains open and these experiences bring interesting information.
This problem has been studied in several directions: lower bounds on \(\text{sep}(P)\) (obtained by suitable Liouville estimates), explicit examples for which \(\text{sep}(P)\) is small (such as \((aX-1)(X^n-aX+1)\) and \(X^n-2(aX-1)^2\) for large \(a\) and \(n\geq 3\)).
The main contribution of this paper is a massive experimental study. According to this work, the author considers that this leads to conjecture that the “worst” case should be approximatively the square root of the best theoretical lower bound presently known. In my opinion, the difficulty with extensive computational studies is that interesting special examples may be too far or to rare to be found. In any case, the problem remains open and these experiences bring interesting information.
Reviewer: Maurice Mignotte (Strasbourg)
MSC:
| 12D10 | Polynomials in real and complex fields: location of zeros (algebraic theorems) |
| 26C05 | Real polynomials: analytic properties, etc. |
| 30C20 | Conformal mappings of special domains |
References:
| [1] | Collins, G. E.; Akritas, A. G., Polynomial real root isolation using Descartes’ rule of signs, (Jenks, R. D., Proc. 1976 ACM Symposium on Symbolic and Algebraic Computation (SYMSAC ’76) (1976), ACM Press), 272-275 |
| [2] | Collins, G. E.; Johnson, J. R.; Krandick, W., Interval arithmetic in CAD computation, J. Symb. Comput., submitted (2001) |
| [3] | Collins, G. E.; Horowitz, E., The minimum root separation of a polynomial, Math. Comp., 28, 589-597 (1974) · Zbl 0278.65049 |
| [4] | Mahler, K., An inequality for the discriminant of a polynomial, Michigan Math. J., 11, 257-262 (1964) · Zbl 0135.01702 |
| [5] | Mignotte, M., Some useful bounds, (Buchberger, B.; Collins, G. E.; Loos, R., Computer Algebra (1982), Springer-Verlag), 259-263 · Zbl 0498.12019 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
