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

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

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

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

r(20, 3) $$\approx$$ .000005 = $$\sqrt{{5}}$$ + $$\sqrt{{6}}$$ + $$\sqrt{{18}}$$ - $$\sqrt{{4}}$$ - $$\sqrt{{12}}$$ - $$\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(2^2klg 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)  ≥  [4k²n]^1/2-22k-2  .

Cheng et al. [CMSC09] establish an upper bound on -lg r(n, k) of 2^O(n/lg n)lg n, which improves on the above bound O(2^{2k lg n}) whenever n≤ck 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+${\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/n^3/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.