Let f be a square-free polynomial. The root separation of f is the minimum of the pair-wise distance between the complex roots of f. 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 in mathematics, science and engineering. Due to its importance, there has been extensive research on this problem, resulting in various celebrated bounds.
However, the previous bounds are still very pessimistically small. Furthermore, surprisingly, they are not compatible with the geometry roots: for instance, when the roots are doubled, the bounds do not double. Worse yet, the bounds even become smaller.
In this talk, we present another bound, which is "nicer" than the previous bounds in that
(1) It is siginificanly bigger (hence better) than the previous bounds.
(2) It is compatible with the geometry of the roots.
2.Connectivity in Semialgebraic SetsIf time allows, we will also describe a generalization to multivariate polynomials systems.
This is a joint work with Aaron Herman and Elias Tsigaridas.
A semialgebraic set is a subset of real space defined by polynomial equations and inequalities. A semialgebraic set is a union of finitely many maximally connected components.
In this talk, we consider the problem of deciding whether two given points in a semialgebraic set are connected, that is, whether the two points lie in a same connected component. In particular, we consider the semialgebraic set defined by f not equal 0 where f is a given bivariate polynomial.
The motivation comes from the observation that many important/non-trivial problems in science and engineering can be often reduced to that of connectivity. Due to it importance, there has been intense research effort on the problem.
This is a joint work with James Rohal, Mohab Safey Eldin and Erich Schost. We will describe a method based on gradient fields and provide a sketch of the proof of correctness based Morse complex. The method seems to be more efficient than the previous methods in practice.
We will also provide a bound on the length of the curves connecting the points.
3.Algorithm for Computing mu-bases of univariate polynomials
We present a new algorithm for computing a mu-basis of the syzygy module of n polynomials in one variable. The algorithm is conceptually different from the previously-developed algorithms by Cox, Sederberg, Chen, Zheng, and Wang for n=3, and by Song and Goldman for an arbitrary n. The algorithm involves computing a ``partial'' reduced row-echelon form of a certain matrix. The proof of the algorithm is based on standard linear algebra and is completely self-contained. Comparison with Song-Goldman algorithm will be given.
This is a joint work with Irian Kogan, Zachary Hough.