hide
Free keywords:
-
Abstract:
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).
