On the Sum of Square Roots of Polynomials and Related Problems

The sum of square roots problem over integers is the task of deciding the sign of a non-zero 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·logN)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 which 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 at is of the form, a_i = X^di + 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_i,j{|b_ij|} and d = max_i{d_i}. If X >; (B + 1)^(n·d)O(1) then a non-zero S = Σ_i=1ⁿ δ_i · √(a_i) is lower bounded as |S| ≥ 1/X^(n·d)O(1). The constant in the O(1) notation, 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) les- - s than or equal to d? We give a coRP^PP-algorithm for this problem, improving previous results of and.