Next: Problem 34: Extending Pseudosegment Arrangements by Subdivision
Previous: Problem 32: Bar-Magnet Polyhedra
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| \sum_{i=1}^k \sqrt{a_i} - \sum_{i=1}^k \sqrt{b_i} \right| 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}
Posed in [O'R81]. Perhaps older in other formulations.
Open, although some weak bounds are known.
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 : “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.”
Exponential upper bounds are known through root-separation bounds [BFMS00], [MS00]. Specifically, [MS00], [BFMS00] proves that -\lg r(n,k) \leq O(2^{2 k} \lg 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 and for exact geometric computation.)
John A. Anderson (johnaa333@netzero.net) has an unpublished proof (Aug 2003) of a similar bound: r(n,k) \; \ge \; [4 k^2 n]^{1/2 - 2^{2k-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 \le c k \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 \Theta(1/n^{3/2}) on this integrality gap.
Related, [Blö91] gives a polynomial-time Monte Carlo algorithm to decide whether a sum of radicals is zero.
[O'R81]; Usenet newsgroup 25 Dec 90.
numerical computations
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.
Dana Angluin and Sarah Eisenstat. . Technical Report YALEU/DCS/TR-1279, Yale University, March 2004.
J. Blömer. Computing sums of radicals in polynomial time. In Proc. 32nd Annu. IEEE Sympos. Found. Comput. Sci., pages 670–677, 1991.
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.
Qi Cheng, Xianmeng Meng, Celi Sun, and Jiazhe Chen. Bounding the sum of square roots via lattice reduction. arXiv:0905.4487v1 [cs.CG], 2009.
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.
Joseph O’Rourke. Advanced problem 6369. Amer. Math. Monthly, 88(10):769, 1981.
Jianbo Qian and Cao An Wang. New upper bound on difference between two sums of square roots of integers. Technical report, Memorial University of Newfoundland, October 2004.
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.