The D-plus Discriminant and Complexity of Root Clustering

Let $p(x)$ be an integer polynomial with $mge 2$ distinct roots $rho_1,ldots,rho_m$ whose multiplicities are $boldsymbol{mu}=(mu_1,ldots,mu_m)$. We define the D-plus discriminant of $p(x)$ to be $D^+(p):= prod_{1le i<jle m}(rho_i-rho_j)^{mu_i+mu_j}$. We first prove a conjecture that $D^+(p)$ is a $boldsymbol{mu}$-symmetric function of its roots $rho_1,ldots,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.