The sum of square roots problem

How close can two sums of $k$ square roots of integers up to $n$ come without being equal? If the gap is never extremely small, such sums can be compared in polynomial time. That would remove a basic obstacle in geometric computing, where even simple problems about Euclidean lengths are not known to lie in NP.

Problem

For positive integers $n$ and $k$, let $r(n,k)$ be the smallest positive value of

$$\Big|\sum_{i=1}^{k}\sqrt{a_i}-\sum_{i=1}^{k}\sqrt{b_i}\Big|$$

over integers $1\le a_i,b_i\le n$. For example, $r(20,2)\approx 0.0002$, attained by $\sqrt{10}+\sqrt{11}-\sqrt{5}-\sqrt{18}$.

Question. Find tight upper and lower bounds on $r(n,k)$ as a function of $n$ and $k$. In particular, is $\log\big(1/r(n,k)\big)$ bounded by a polynomial in $k$ and $\log n$? If it is, the sign of a difference of two such sums can be found in polynomial time by evaluating it to polynomially many bits.

Background

O'Rourke posed the question in 1981 as an Advanced Problem in the American Mathematical Monthly, and it is Problem 33 of The Open Problems Project. It matters because geometric algorithms are analysed on a real-number machine while complexity classes are defined for Turing machines. Without a way to compare sums of distances quickly, even the decision versions of easy problems such as the Euclidean minimum spanning tree are not known to be in NP, as David Eppstein put it in a remark quoted by the source.

What is known

• Upper bounds on the precision needed. Root separation bounds give $\log(1/r(n,k))=O(2^{2k}\log n)$ (Burnikel, Fleischer, Mehlhorn and Schirra, 2000) [1], so the gap is at worst doubly exponentially small in $k$. Cheng, Meng, Sun and Chen (2010) related the problem to short vectors in lattices and showed $\log(1/r(n,k))\le 2^{O(n/\log n)}\log n$, which is better when $n$ is at most a constant times $k\log k$; they also conjectured a lattice property that would make comparing sums of square roots of small integers polynomial [3].
• Lower bounds. Qian and Wang (2006) showed $r(n,k)=O(n^{-2k+3/2})$, so about $2k\log n$ bits are sometimes necessary [2].
• Fixed radicands. For $E=\sum_{i=1}^m x_i\sqrt{a_i}\neq 0$ with integer $x_i$, Eisenbrand, Haeberle and Singer (2024) proved $|E|\ge\gamma\,(m\max_i|x_i|)^{-2m}$, where $\gamma$ depends only on the $a_i$ and comes from the subspace theorem, so it is not explicit [4].
• Complexity. Comparing sums of square roots lies in the counting hierarchy, through a reduction to the problem PosSLP (Allender, Bürgisser, Kjeldgaard-Pedersen and Miltersen, 2009) [5]; it is not known to be in NP. When the integers are written in unary, deciding the sign of $\sum_i \pm\sqrt{a_i}$ is in P/poly (Balaji and Datta, 2024) [6].

What would count as progress

• A proof that $\log(1/r(n,k))\le \mathrm{poly}(k,\log n)$, or a family of examples showing that it grows faster.
• Exact values of $r(n,k)$ for small $n$ and $k$, or new near-ties, found by search; each candidate can be checked with high-precision interval arithmetic.
• A polynomial-time algorithm for the sign of $\sum_i x_i\sqrt{a_i}$, or for comparing two sums of square roots. The formal-conjectures project states this polynomial-time question in Lean, in a one-sum and a two-sum version: SquareRootSum.lean.

References

1. C. Burnikel, R. Fleischer, K. Mehlhorn and S. Schirra, A strong and easily computable separation bound for arithmetic expressions involving radicals, Algorithmica 27 (2000), 87–99. doi:10.1007/s004530010005
2. J. Qian and C. A. Wang, How much precision is needed to compare two sums of square roots of integers?, Inform. Process. Lett. 100 (2006), 194–198. doi:10.1016/j.ipl.2006.05.002
3. Q. Cheng, X. Meng, C. Sun and J. Chen, Bounding the sum of square roots via lattice reduction, Math. Comp. 79 (2010), 1109–1122. doi:10.1090/S0025-5718-09-02304-7, arXiv:0905.4487
4. F. Eisenbrand, M. Haeberle and N. Singer, An improved bound on sums of square roots via the subspace theorem, Proc. SoCG 2024, LIPIcs 293, 54:1–54:8. doi:10.4230/LIPIcs.SoCG.2024.54, arXiv:2312.02057
5. E. Allender, P. Bürgisser, J. Kjeldgaard-Pedersen and P. B. Miltersen, On the complexity of numerical analysis, SIAM J. Comput. 38 (2009), 1987–2006. doi:10.1137/070697926
6. N. Balaji and S. Datta, USSR is in P/poly, Proc. SOSA 2024, 151–159. doi:10.1137/1.9781611977936.15, arXiv:2310.19335

Source

Imported from The Open Problems Project, Problem 33, curated by Erik D. Demaine, Joseph S. B. Mitchell and Joseph O'Rourke. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.