Quality of positive root bounds. (May 2016) - Herman, Aaron; Hong, Hoon
Abstract: In this paper, we study the quality of positive root bounds. A positive root bound of a polynomial is an upper bound on the largest positive root. Higher quality means that the relative over-estimation (the ratio of the bound and the largest positive root) is smaller. We report three findings. (1) Most known positive root bounds can be arbitrarily bad ; that is, the relative over-estimation can approach infinity, even when the degree and the coefficient size are fixed. (2) When the number of sign variations is the same as the number of positive roots, the relative over-estimation of a positive root bound due to Hong ( B H ) is at most linear in the degree, no matter what the coefficient size is. (3) When the number of sign variations is one, the relative over-estimation of B H is at most constant, in particular 4, no matter what the degree and the coefficient size are.