Is it possible, for an arbitrary polynomial in one variable with integer coefficients, to determine the roots of the polynomial in the Complex Field to arbitrary accuracy? When I was looking into this, I found some papers on homotopy continuation that seem to solve this problem (for the Real solutions at least), is that correct? Or are there restrictions on whether homotopy continuation will work? Does the solution region need to be bounded?



Finding all roots of a polynomial
This argument is problematic; see Andrej Bauer's comment below.




---


Sure. I have no idea what an efficient algorithm looks like, but since you only asked whether it's possible I'll offer a terrible one. 


**Lemma:** Let $f(z) = z^n + a\_{n-1} z^{n-1} + \cdots + a\_0$ be a complex polynomial and let $R = \max(1, |a\_{n-1}| + \cdots + |a\_0|)$. Then all the roots of $f$ lie in the circle of radius $R$ centered at the origin.


*Proof.* If $|z| > R$, then $|z|^n > R |z|^{n-1} \ge |a\_{n-1} z^{n-1}| + \cdots + |a\_0|$, so by the triangle inequality no such $z$ is a root.


Now subdivide the disk of radius $R$ into, say, a mesh of squares of side length $\varepsilon > 0$ and evaluate the polynomial at all the lattice points of the mesh. As the mesh size tends to zero you'll find points that approximate the zeroes to arbitrary accuracy.


There are also lots of specialized algorithms for finding roots of polynomials [at the Wikipedia article](http://en.wikipedia.org/wiki/Root-finding_algorithm#Finding_roots_of_polynomials).


