Datensatz

Zusammenfassung

The sum of square roots problem over integers is the task of deciding the sign of a \emphnon-zero} sum, S = \sum_{i=1}^{n}{δ_i ⋅ \sqrt{a_i}}, where δ_i \in { +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 \abs{S} ≥q 1/2^{(n ⋅ \log N)^{O(1)}} when S \neq 0. We study a formulation of this problem over polynomials: Given an expression S = \sum_{i=1}^{n}{c_i ⋅ \sqrt{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) \neq 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 a_i is of the form, a_i = X^{d_i} + b_{i 1} X^{d_i - 1} + \ldots + b_{i d_i}, \hspace{0.1in} d_i > 0, where X is a positive real number and b_{i j}'s are integers. Let B = \max ({\abs{b_{i j}}}_{i, j}, 1) and d = \max_i{d_i}. If X > (B+1)^{(n ⋅ d)^{O(1)}} then a \emph{non-zero} S = \sum_{i=1}^{n}{δ_i ⋅ \sqrt{a_i}} is lower bounded as \abs{S} ≥q 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(\vecx) and integer d, is the degree of f(\vecx) less than or equal to d? We give a \mathsf{coRP}^{\mathsf{PP}-algorithm for this problem, improving previous results of Allender, Bürgisser, Kjeldgaard-Pedersen and Miltersen (2009), and Koiran and Perifel (2007).