<p>Here is a rather sloppy proof sketch. Let <span class="math-container">$S = \sum_{i=1}^n \delta_i \sqrt{a_i}$</span> where <span class="math-container">$\delta_i \in \{\pm 1\}$</span>. This is an algebraic number of degree at most <span class="math-container">$2^n$</span> and height at most <span class="math-container">$H = (max(a_i))^{n}$</span>. Now it is easy to check if <span class="math-container">$S = 0$</span> (can be done even in <span class="math-container">$TC^0$</span> -- see <a href="https://people.mpi-sws.org/~joel/publications/fsttcs10abs.html" rel="noreferrer">this</a>).If <span class="math-container">$S \neq 0$</span> then it is bounded away from <span class="math-container">$0$</span> 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 <span class="math-container">$S$</span>. Unfortunately, the dependence on the degree is exponential in the number of square roots (and if the <span class="math-container">$a_i$</span>'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 <span class="math-container">$2^n$</span>-bits for <span class="math-container">$S$</span>. It now suffices to truncate each of the <span class="math-container">$\sqrt{a_i}$</span> to say <span class="math-container">$2^{10n}$</span> 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 <span class="math-container">$S$</span> 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 <a href="https://core.ac.uk/download/pdf/82781772.pdf" rel="noreferrer">Tiwari's paper</a>. </p>

CC BY-SA 4.0
2019-08-01T20:58:24.673Z
Downvoted because the only part of this long answer that actually addresses the question is the last line, and it's a reference from 1992 not the 1970s or earlier.
David Eppstein
CC BY-SA 4.0
2019-08-01T21:10:53.153Z
@david I was just trying to provide a proof sketch for why we need 2^n- bit precision for evaluating the square roots (@mhum asked for it at some point). I'm not familiar with how such a bound was derived earlier before the paper I cited (though I suspect it should use similar techniques).
Nikhil
CC BY-SA 4.0
2019-08-01T23:04:28.913Z
Maybe it's just me, but when a question says "I know how to prove this but can someone give me a reference" I find answers showing how to prove it irritating. It's like when students on an exam give an answer to something different than what was asked, hoping (in vain) that they'll get partial credit for knowing something even though they didn't know what you wanted them to.
David Eppstein
CC BY-SA 4.0
2019-08-02T04:12:06.890Z
Don't know where you're quoting from but there's a "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." Somewhere in the question
Nikhil
CC BY-SA 4.0
2019-08-02T21:39:31.517Z
This seems to me plausibly close enough to what could have been in the personal communication. Thanks. (I suppose I could have tried to contact Odlyzko directly to find out)
mhum
CC BY-SA 4.0
2019-07-31T20:32:28.263Z
2019-07-31T23:01:33.953Z
2019-07-31T23:01:33.953Z
Nikhil
<p>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.</p>

<blockquote>
  <p>Given integers <span class="math-container">$a_1, a_2, \ldots, a_n$</span> and <span class="math-container">$L$</span>, determine if <span class="math-container">$\sqrt{a_1} + \sqrt{a_2} + \cdots + \sqrt{a_n} &lt; L$</span></p>
</blockquote>

<p>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 <span class="math-container">$L$</span>. However, they do cite a best known upper bound of <span class="math-container">$O(m2^n)$</span> where <span class="math-container">$m$</span> 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. </p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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. </p>

<ol>
<li><p>Garey, Michael R., Ronald L. Graham, and David S. Johnson. "<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.308.8190&amp;rep=rep1&amp;type=pdf" rel="noreferrer">Some NP-complete geometric problems</a>." Proceedings of the eighth annual ACM symposium on Theory of computing. ACM, 1976.</p></li>
<li><p>Burnikel, Christoph, et al. "<a href="https://www.researchgate.net/profile/Kurt_Mehlhorn/publication/47842038_A_Strong_and_Easily_Computable_Separation_Bound_for_Arithmetic_Expressions_Involving_Radicals/links/00463536e6da4ba768000000/A-Strong-and-Easily-Computable-Separation-Bound-for-Arithmetic-Expressions-Involving-Radicals.pdf" rel="noreferrer">A strong and easily computable separation bound for arithmetic expressions involving radicals</a>." Algorithmica 27.1 (2000): 87-99.</p></li>
</ol>

CC BY-SA 4.0
2019-08-02T22:59:52.430Z
See also the answer to [this cstheory.stackexchange question](https://cstheory.stackexchange.com/questions/44324/is-convex-optimisation-in-p), which says "The most remarkable progress towards this problem is by Eric Allender and his co-authors, in 2003, they showed this problem lies in the 4th level of the Counting Hierarchy. http://ftp.cs.rutgers.edu/pub/allender/slp.pdf"
Neal Young
<reference-request><cg.comp-geom><na.numerical-analysis>
Proof for Upper Bound of Sum of Square Roots Problem
mhum
# Proof for Upper Bound of Sum of Square Roots Problem

(Asked by: username_0 on 2019-07-31)

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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.308.8190&rep=rep1&type=pdf)." 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](https://www.researchgate.net/profile/Kurt_Mehlhorn/publication/47842038_A_Strong_and_Easily_Computable_Separation_Bound_for_Arithmetic_Expressions_Involving_Radicals/links/00463536e6da4ba768000000/A-Strong-and-Easily-Computable-Separation-Bound-for-Arithmetic-Expressions-Involving-Radicals.pdf)." Algorithmica 27.1 (2000): 87-99.

**Tags:** reference-request, cg.comp-geom, na.numerical-analysis

> **Comments:**
> **username_1**: See also the answer to [this cstheory.stackexchange question](https://cstheory.stackexchange.com/questions/44324/is-convex-optimisation-in-p), which says "The most remarkable progress towards this problem is by Eric Allender and his co-authors, in 2003, they showed this problem lies in the 4th level of the Counting Hierarchy. http://ftp.cs.rutgers.edu/pub/allender/slp.pdf"  

---

## 1 answers

### Answer by username_2 on 2019-07-31. Score: 7 | Accepted answer

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](https://people.mpi-sws.org/~joel/publications/fsttcs10abs.html)).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](https://core.ac.uk/download/pdf/82781772.pdf).

> **Comments:**
> **username_3**: Downvoted because the only part of this long answer that actually addresses the question is the last line, and it's a reference from 1992 not the 1970s or earlier.  
> **username_2**: @david I was just trying to provide a proof sketch for why we need 2^n- bit precision for evaluating the square roots (@username_0 asked for it at some point). I'm not familiar with how such a bound was derived earlier before the paper I cited (though I suspect it should use similar techniques).  
> **username_3**: Maybe it's just me, but when a question says "I know how to prove this but can someone give me a reference" I find answers showing how to prove it irritating. It's like when students on an exam give an answer to something different than what was asked, hoping (in vain) that they'll get partial credit for knowing something even though they didn't know what you wanted them to.  
> **username_2**: Don't know where you're quoting from but there's a "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." Somewhere in the question  
> **username_0**: This seems to me plausibly close enough to what could have been in the personal communication. Thanks. (I suppose I could have tried to contact Odlyzko directly to find out)  

---

