On the Sum of Square Roots of Polynomials and Related Problems
Neeraj Kayal, Chandan Saha · ACM Transactions on Computation Theory · 2011
The sum of square roots problem over integers is the task of deciding the sign of a non-zero sum, S = Σi=1nδi· √(ai), where δiϵ { +1, -1} and ai'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=1nci· √(fi(x)), where ci's belong to a field of characteristic 0 and fi's are univariate polynomials with degree bounded by d and fi(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, ai= Xdi+ bi1Xdi-1+ ⋯ +bidi, di>; 0, where X is a positive real number and bij's are integers. Let B = maxi,j{|bij|} and d = maxi{di}. If X >; (B + 1)(n·d)O(1)then a non-zero S = Σi=1nδi· √(ai) 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) less than or equal to d? We give a coRPPP-algorithm for this problem, improving previous results of and.