The D-plus Discriminant and Complexity of Root Clustering
share
Let p(x) be an integer polynomial with m≥ 2 distinct roots ρ_1,…,ρ_m whose multiplicities are μ=(μ_1,…,μ_m). We define the D-plus discriminant of p(x) to be D^+(p):= ∏_1≤ i<j≤ m(ρ_i-ρ_j)^μ_i+μ_j. We first prove a conjecture that D^+(p) is a μ-symmetric function of its roots ρ_1,…,ρ_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.
READ FULL TEXT