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 lower 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) $\leq$ 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.)

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 proved [AE04] a bound of $\Theta$(1/n^3/2) on this integrality gap.

Erik Demaine asks (Nov. 2001) whether the number of bits required to distinguish the difference from 0 ever exceeds the number of bits in the input. More precisely, are there integers a₁,..., a_j, b₁,..., b_k for which

-lg$$\left(\vphantom{\sum_{i=1}^j \sqrt{a_i} - \sum_{i=1}^k \sqrt{b_i}}\right.$$$$\sum_{{i=1}}^{j}$$$$\sqrt{{a_i}}$$ - $$\sum_{{i=1}}^{k}$$$$\sqrt{{b_i}}$$$$\left.\vphantom{\sum_{i=1}^j \sqrt{a_i} - \sum_{i=1}^k \sqrt{b_i}}\right)$$ > $$\sum_{{i=1}}^{j}$$lg a_i + $$\sum_{{i=1}}^{k}$$lg b_i + O(k)

where the O(k) term allows for roundoff error for small values?

John A. Anderson (johnaa333@netzero.net) has an unpublished proof (Aug 2003) that a lower bound is

r(n, k)  $$\ge$$  [4k²n]^1/2-22k-2  .

Qian and Wang [QW04,QW05] show a bound of r(n, k) = O(n^{-2k+${\frac{{3}}{{2}}}$}). Cheng established an upper bound on -lg r(n, k) of 2^O(n/lg n)lg n [], which improves on the bound O(2^{2k lg n}) (mentioned above) whenever n$\le$ck lg k for some c. 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.

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.

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?, October 2005.