The D-plus Discriminant and Complexity of Root Clustering

Abstract

Let $p(x)$ be an integer polynomial with $m\ge 2$ distinct roots ${\rho }_1,\dots ,{\rho }_m$ whose multiplicities are $\mathbf{\mu }=({\mu }_1,\dots ,{\mu }_m)$. We define the D-plus discriminant of $p(x)$ to be $D^{+}(p):={\prod }_{1\le i<j\le m}({\rho }_i-{\rho }_j{)}^{{\mu }_i+{\mu }_j}$. We first prove a conjecture that $D^{+}(p)$ is a $\mathbf{\mu }$-symmetric function of its roots ${\rho }_1,\dots ,{\rho }_m$. Our main result gives an explicit formula for $D^{+}(p)$, as a rational function of its coefficients. Our proof is ideal-theoretic, based on re-casting the classic Poisson resultant as the "symbolic Poisson formula". The D-plus discriminant first arose in the complexity analysis of a root clustering algorithm from Becker et al. (ISSAC 2016). The bit-complexity of this algorithm is proportional to a quantity $\log (|D^{+}(p){|}^{-1})$. As an application of our main result, we give an explicit upper bound on this quantity in terms of the degree of $p$ and its leading coefficient.

Cited by in corpus (1)

• On mu-Symmetric Polynomials