Can someone provide a list of references of papers, books, etc. presenting results on the time and space complexity of the problem of isolating the roots of a univariate polynomial $P(t)$ with integer coefficients (e.g. $P(t) \in \mathbb{Z}[t]$)?

Papers like this one offer informal arguments to provide upper bounds for time, but I wonder whether more precise and systematic surveys into this question have been conducted.

Arguments like the ones in the paper I cite above, as well as many (?) of the state-of-the-art root isolation algorithms, depend on assuming that the polynomial $P$ is square-free, e.g. $gcd(P, P')=1$, but I haven't found (yet) a rationale that motivates this assumption other than an appeal to "simplicity" without further explanation or attempt at being didactical.

Please note that there are some related questions and answers in both compsci and the math stack exchanges, but this one is about isolating rather than finding the roots or $P$.

Thanks in advance!

  • $\begingroup$ Real roots can be deterministically isolated by the method of Sturm sequences combined to a dichotomic process. That dichotomic process will take a recursion depth at worst equal to the cologarithm of the distance between the closest roots (relative to the initial interval size). The whole process only involves rationals. $\endgroup$
    – user16034
    Commented Jun 30, 2022 at 8:03
  • $\begingroup$ If $(P,P') \neq 1$ then you can factor $(P,P')$, remove the relevant roots from $P$, and continue. $\endgroup$ Commented Jun 30, 2022 at 13:57
  • $\begingroup$ Factorization and then "moving on" is not general for subdivision methods as far as I can tell, since you lose information regarding the ordering of the isolating intervals within the "top-level" interval (like $I = (0, 1)$). By factorizing, there is no reason why we cannot potentially get, for each of the factors, overlapping isolating intervals... $\endgroup$ Commented Jul 1, 2022 at 2:05


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.