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 =Pn i=1 δi ·√ai, where δi ∈ {+1,−1} and ai’s are positive integers that are upperbounded 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 6= 0. We study a formulation of this problem over polynomials: Given an expression S =Pn i=1 ci ·pfi(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)6= 0 forall 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 ai 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 = max({|bij|}i,j,1) and d = maxi{di}. If X > (B +1)(n·d)O(1) then a non-zero S =Pn i=1 δ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 Allender, Bu¨rgisser, Kjeldgaard-Pedersen and Miltersen (2009), and Koiran and Perifel (2007).