We present tight bounds for distances from differences of roots of the polynomial f(x)∈R[x] over a discrete normed commutative ring R without zero divisors to the nearest element of R. In the case most interesting for applications, R=Z, an algorithm for the determination of the existence of nonzero integers among these differences in time (n4log(H(f)+1))1+ε is given. This problem arises when constructing algorithms for solving some systems of ODE.
- computational complexity
- polynomials with integer coefficients
- systems of differential equations