The sum of square roots over integers problem is the task of deciding the sign of a nonzero sum, S = ∑_i=1ⁿ δ_i · √a_i, where δ_i ∈ {+1, −1} and a_i’s are positive integers that are upper bounded by N (say). A fundamental open question in numerical analysis and computational geometry is whether ∣S∣ ≥ 1/2^{(n ·log N)O(1)} when S ≠ 0. We study a formulation of this problem over polynomials. Given an expression S = ∑_i=1ⁿ c_i · √f_i(x), where c_i’s belong to a field of characteristic 0 and f_i’s are univariate polynomials with degree bounded by d and f_i(0)≠0 for all i, is it true that the minimum exponent of x that has a nonzero coefficient in the power series S is upper bounded by (n · d)^O(1), unless S = 0? We answer this question affirmatively. Further, we show that this result over polynomials can be used to settle (positively) the sum of square roots problem for a special class of integers: Suppose each integer a_i is of the form, a_i = X^d_i + b_i1X^di−1 +...+ b_idi, d_i > 0, where X is a positive real number and b_ij’s are integers. Let B = max ({∣b_ij∣}_{i, j}, 1) and d = max_i{d_i}. If X > (B + 1)^(n·d)O(1) then a nonzero S = ∑_i=1ⁿ δ_i · √a_i is lower bounded as ∣S∣ ≥ 1/X^(n·d)O(1). The constant in O(1), as fixed by our analysis, is roughly 2.

We then consider the following more general problem. Given an arithmetic circuit computing a multivariate polynomial f(X) and integer d, is the degree of f(X) less than or equal to d? We give a coRP^PP-algorithm for this problem, improving previous results of Allender et al. [2009] and Koiran and Perifel [2007].