# Proof for Upper Bound of Sum of Square Roots Problem

In [1], Garey et al. identify what would later be known as the Sum of Square Roots Problem in the course of working out the NP-completeness of Euclidean TSP.

Given integers $$a_1, a_2, \ldots, a_n$$ and $$L$$, determine if $$\sqrt{a_1} + \sqrt{a_2} + \cdots + \sqrt{a_n} < L$$

They observe that it is not even apparent that this problem is in NP since it is not clear what the minimum digits of precision are required in the computation of the square roots to sufficiently compare the sum to $$L$$. However, they do cite a best known upper bound of $$O(m2^n)$$ where $$m$$ is "the number of digits in the original symbolic expression". Unfortunately, this upper bound is attributed merely to a personal communication from A. M. Odlyzko.

Does anyone have a proper reference to this upper bound? Or, in the absence of a published reference, a proof or proof sketch would also be helpful.

Note: I believe that this bound might be inferred as a consequence of more general results by Bernikel et. al. [2] from around 2000 on separation bounds for a larger class of arithmetic expressions. I'm mostly interested in more contemporaneous references (i.e.: what was known circa 1976) and/or proofs specialized to just the case of the sum of square roots.

1. Garey, Michael R., Ronald L. Graham, and David S. Johnson. "Some NP-complete geometric problems." Proceedings of the eighth annual ACM symposium on Theory of computing. ACM, 1976.

2. Burnikel, Christoph, et al. "A strong and easily computable separation bound for arithmetic expressions involving radicals." Algorithmica 27.1 (2000): 87-99.

Here is a rather sloppy proof sketch. Let $$S = \sum_{i=1}^n \delta_i \sqrt{a_i}$$ where $$\delta_i \in \{\pm 1\}$$. This is an algebraic number of degree at most $$2^n$$ and height at most $$H = (max(a_i))^{n}$$. Now it is easy to check if $$S = 0$$ (can be done even in $$TC^0$$ -- see this).If $$S \neq 0$$ then it is bounded away from $$0$$ by a quantity (because it is an algebraic number and hence is a non-zero root of a univariate polynomial) that is a function of the degree and height of the minimal polynomial of $$S$$. Unfortunately, the dependence on the degree is exponential in the number of square roots (and if the $$a_i$$'s are distinct primes, this degree bound is even tight, though that case of sign evaluation is easy to handle). The precision needed is hence exponential in the number of square roots, which is $$2^n$$-bits for $$S$$. It now suffices to truncate each of the $$\sqrt{a_i}$$ to say $$2^{10n}$$ bits to ensure the sign is guaranteed to be correct. This is easily done via polynomially many steps of Newton iteration). Now it is down to checking if the sum is positive, which is just addition and hence linear in the number of bits in the summands. Notice that this computation is in Polynomial time on a BSS machine. Also notice that we are not doing any computation directly with the minimal polynomial of $$S$$ itself, which could have huge coefficients and look ugly, we just use it to reason about the precision to which we need to truncate the square roots. For more details, check Tiwari's paper.