Let f be a polynomial (or polynomial system) with all simple roots. The root separation of f is the minimum of the pair-wise distances between the complex roots. A root separation bound is a lower bound on the root separation. Finding a root separation bound is a fundamental problem, arising in numerous disciplines. We present two new root separation bounds: one univariate bound, and one multivariate bound. The new bounds improve on the old bounds in two ways:
- (1)
The new bounds are usually significantly bigger (hence better) than the previous bounds.
- (2)
The new bounds scale correctly, unlike the previous bounds.
Crucially, the new bounds are not harder to compute than the previous bounds.