next up previous
Next: Problem 34: Extending Pseudosegment Up: The Open Problems Project Previous: Problem 32: Bar-Magnet Polyhedra


Problem 33: Sum of Square Roots

Statement
What is the minimum nonzero difference between two sums of square roots of integers? More precisely, find tight upper and lower bounds on r(n, k), the minimum positive value of

$\displaystyle \left\vert\vphantom{ \sum_{i=1}^k \sqrt{a_i} - \sum_{i=1}^k \sqrt{b_i} }\right.$$\displaystyle \sum_{{i=1}}^{k}$$\displaystyle \sqrt{{a_i}}$ - $\displaystyle \sum_{{i=1}}^{k}$$\displaystyle \sqrt{{b_i}}$$\displaystyle \left.\vphantom{ \sum_{i=1}^k \sqrt{a_i} - \sum_{i=1}^k \sqrt{b_i} }\right\vert$

where ai and bi are integers no larger than n. Bounds should be expressed as a function of n and k. Examples:

r(20, 2) $\displaystyle \approx$ .0002 = $\displaystyle \sqrt{{10}}$ + $\displaystyle \sqrt{{11}}$ - $\displaystyle \sqrt{{5}}$ - $\displaystyle \sqrt{{18}}$

r(20, 3) $\displaystyle \approx$ .000005 = $\displaystyle \sqrt{{5}}$ + $\displaystyle \sqrt{{6}}$ + $\displaystyle \sqrt{{18}}$ - $\displaystyle \sqrt{{4}}$ - $\displaystyle \sqrt{{12}}$ - $\displaystyle \sqrt{{12}}$

Origin
Posed in [O'R81]. Perhaps older in other formulations.
Status/Conjectures
Open, although some weak bounds are known.
Motivation
Of particular importance is whether lg 1/r(n, k) is bounded above by a polynomial in k and lg n. If this statement is true, then the sign of a sum of square roots of integers can be computed in polynomial time. If this statement is false, however, there still may be a polynomial-time algorithm to compute the sign.

To quote David Eppstein: ``A major bottleneck in proving NP-completeness for geometric problems is a mismatch between the real-number and Turing machine models of computation: one is good for geometric algorithms but bad for reductions, and the other vice versa. Specifically, it is not known on Turing machines how to quickly compare a sum of distances (square roots of integers) with an integer or other similar sums, so even (decision versions of) easy problems such as the minimum spanning tree are not known to be in NP.''

Partial and Related Results
Exponential upper bounds are known through root-separation bounds [BFMS00,MS00]. Specifically, [MS00,BFMS00] proves that -lg r(n, k)≤O(22klg n). (More generally, [BFMS00,MS00] give finite algorithms to compute the sign of algebraic expressions such as sums of square roots, which are implemented and used in LEDA and CORE for exact geometric computation.)

John A. Anderson (johnaa333@netzero.net) has an unpublished proof (Aug 2003) of a similar bound:

r(n, k)  ≥  [4k2n]1/2-22k-2  .

Cheng et al. [CMSC09] establish an upper bound on -lg r(n, k) of 2O(n/lg n)lg n, which improves on the above bound O(22k lg n) whenever nck lg k for some c.

At the other extreme, Qian and Wang [QW04,QW05] show an upper bound on r(n, k) of O(n-2k+$\scriptstyle {\frac{{3}}{{2}}}$). This upper bound on r(n, k) implies a lower bound on lg 1/r(n, k), that is, on how many bits we need to compute from the square roots to determine the sign of the difference. In particular, it settles (positively) a question posed here by Erik Demaine (Nov. 2001): can the number of bits required to distinguish the difference from zero ever exceed the total number of bits in the input integers?

A slight variation on the problem is to ask (e.g., for k = 2), how close can $ \sqrt{{a}}$ + $ \sqrt{{b}}$ be to an integer; Dana Angluin and Sarah Eisenstat [AE04] proved a bound of Θ(1/n3/2) on this integrality gap.

Also, [Blö91] may be relevant.

Appearances
[O'R81]; Usenet newsgroup sci.math 25 Dec 90.
Categories
numerical computations
Entry Revision History
E. Demaine, J. O'Rourke, 19 Nov. 2001; J. O'Rourke, 3 Dec. 2001; 13 Aug. 2003; 18 Aug. 2003; 30 Aug. 2003; 7 Dec. 2003; E. Demaine, 9 Feb. 2004 (thanks to Raimund Seidel); J. O'Rourke, 10 Mar. 2004; J. Mitchell, 30 Sep. 2004; J. Mitchell, 1 Oct. 2004; J. Mitchell, 27 Oct. 2005; J. O'Rourke, 30 Dec. 2005 (thanks to Marc Glisse); J. O'Rourke, 16 May 2006; E. Demaine, 9 Sep. 2009.

Bibliography

AE04
Dana Angluin and Sarah Eisenstat.
How close can $ \sqrt{{a}}$ + $ \sqrt{{b}}$ be to an integer?, March 2004.

Blö91
J. Blömer.
Computing sums of radicals in polynomial time.
In Proc. 32nd Annu. IEEE Sympos. Found. Comput. Sci., pages 670-677, 1991.

BFMS00
C. Burnikel, R. Fleischer, K. Mehlhorn, and S. Schirra.
A strong and easily computable separation bound for arithmetic expressions involving radicals.
Algorithmica, 27(1):87-99, 2000.

CMSC09
Qi Cheng, Xianmeng Meng, Celi Sun, and Jiazhe Chen.
Bounding the sum of square roots via lattice reduction.
arXiv:0905.4487v1 [cs.CG], 2009.

MS00
Kurt Mehlhorn and Stefan Schirra.
Generalized and improved constructive separation bound for real algebraic expressions.
Research Report MPI-I-2000-1-004, Max-Planck-Institut für Informatik, Saarbrücken, Germany, November 2000.

O'R81
Joseph O'Rourke.
Advanced problem 6369.
Amer. Math. Monthly, 88(10):769, 1981.

QW04
Jianbo Qian and Cao An Wang.
New upper bound on difference between two sums of square roots of integers, October 2004.

QW05
Jianbo Qian and Cao An Wang.
How much precision is needed to compare two sums of square roots of integers?.
Information Processing Letters, 100(5):194-198, December 2005.
Also Technical Report, Memorial University of Newfoundland, Oct. 2005.


next up previous
Next: Problem 34: Extending Pseudosegment Up: The Open Problems Project Previous: Problem 32: Bar-Magnet Polyhedra
The Open Problems Project - December 04, 2015