New Results in bounds for positiveness of polynomials[HBNI Th148]

Abstract

For a univariate polynomial with real coefficients, a bound on its positiveness is a positive real number B such that the polynomial is non-negative at every value larger than B. One of the best known bounds in literature is due to Hoon Hong. Due to an algorithm of Koprowski-Mehlhorn-Ray, Hong’s bound is linear time computable in the degree of the polynomial. In 2015, Collins showed that an old bound due to Lagrange can be used to improve upon Hong’s bound. Does this improvement over Hong’s bound come at an extra computational cost? We show that Collins’ bound does not admit a linear time algorithm like Hong’s bound. Our result shows that Hong’s bound achieves a near optimal tradeoff between quality and computational complexity. The problem of proving upper bounds on positiveness generalizes naturally for multivariate polynomials. We say that a positive real number B is an upper bound on the positiveness of a multivariate polynomial F(x1, x2,..., xn) ∈ R[x1,..., xn] if F(x1, x2,..., xn) ≥ 0, for all xi ≥ B. Here, we improve upon the best known bound due to Hong. Our improvement is achieved by generalizing a known bound for univariate complex polynomials due to Westerfield. We also give an algorithm to compute a specific version of Westerfield’s bound and the running time of our algorithm matches the running time of the algorithm to compute Hong’s bound. In the second part, we strengthen a known lower bound on orthogonal range querying due to Fredman. Informally, Fredman’s lower bound says that for orthogonal range querying, either the storage space has to be large or the output complexity has to be large. We tighten this trade off by showing that both storage space and the output complexity has to be large for orthogonal range querying.