From:orourke@server.cs.jhu.edu (Joseph O'Rourke)Newsgroups:sci.mathSubject:Radical differenceDate:25 Dec 90 19:50:44 GMTReply-To:orourke@cs.jhu.edu (Joseph O'Rourke)Organization:Johns Hopkins University CS Dept.

What is the minimum nonzero difference between two sums of square roots of integers? In particular, find a lower bound 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$. 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}$$ This question arose in (and stymied) an attempt to prove a particular problem NP-complete. --Joseph O'Rourke, Smith College jorourke@smith.bitnet,orourke%sophia@cs.umass.edu

From:ilan@Gang-of-Four.Stanford.EDU (Ilan Vardi)Newsgroups:sci.mathSubject:Re: Radical differenceDate:25 Dec 90 22:10:54 GMTOrganization:Computer Science Department, Stanford University

In article <10070@cs.jhu.edu> orourke@cs.jhu.edu (Joseph O'Rourke) writes: >What is the minimum nonzero difference between two sums of square >roots of integers? In particular, find a lower bound 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$. >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}$$ >This question arose in (and stymied) an attempt to prove a particular >problem NP-complete. >--Joseph O'Rourke, Smith College >jorourke@smith.bitnet,orourke%sophia@cs.umass.edu This is a tough one. Let a_1 = n, b_1 = n-1, then r(n, 1) is, by the mean value theorem sqrt{n} - sqrt{n-1} = 1/(2 sqrt{xi}), n-1 < xi < n < 1/(2 sqrt{n-1}) so I would conjecture that liminf r(n,k) = 0. Do I get to be co-author or what? (This is one of the dangers of posting your technical lemmas as problems to the net.) -Ilan Vardi

From:orourke@whatever.cs.jhu.eduNewsgroups:sci.mathSubject:Radical difference: clarificationDate:26 Dec 90 03:42:35 GMTReply-To:orourke@cs.jhu.edu ()Organization:Smith College

I should have made it clear in my earlier posting that I am seeking a lower bound on r(n,k) as a function of n and k, not a lower bound on r(n,k) over all n and k. --Joseph O'Rourke

From:orourke@whatever.cs.jhu.eduNewsgroups:sci.mathSubject:Radical difference: summary of responsesDate:28 Dec 90 15:08:34 GMTReply-To:orourke@cs.jhu.edu ()Organization:Smith College

Thanks to all who responded to the problem I posted. The problem is: >Find a lower bound on r(n,k), the minimum positive value of > > | sum_{i=1}^k sqrt{a_i} - sum_{i=1}^k sqrt{b_i} | > >where a_i and b_i$ are integers no larger than n. Andrew Odlyzko and Michael Ben-Or both informed me that this is a known difficult problem. Its decade-old origins are not clear (to me), but at the least Ron Graham has discussed it in public lectures. The consensus seems to be that the only bounds known are something like n^{-2^k}, or perhaps (n*k)^{-2^k}, or perhaps (4*n*k)^{-4^k}, but in any case n^{-p} with p exponential in k. On the other hand, Odlyzko feels that the true bound is more like n^{-k}, or perhaps n^{-2*k}: n^{-p} with p linear in k. The gap between what can be proved and what seems to be true, is rather wide, but closing it seems difficult. --Joseph O'Rourke, Smith College

From:eppstein@ics.uci.eduTo:jmchen@pub.jiangmen.gd.cnSubject:Re: Welcome to my site on Equal sums of like powersDate:Mon, 28 Jul 1997 15:10:21 -0700

Thanks for the pointer to your page on equal sums of like powers, http://www.jiangmen.gd.cn/person/chen/chenhome.htm You know, by the way, of the following application of such sums? It is an important open problem in computational geometry how much precision is needed to compute lengths of polygonal paths, in order to determine which of two paths is longer. If the path vertices have integer coordinates, each length is a sum of square roots of integers, so the problem can be expressed in number-theoretic terms: how small can be a nonzero number that is the sum of k terms +-sqrt(a_i) where each a_i is an integer smaller than some bound N. The known lower bounds are something like N^{-2^k}, but the best known upper bound (i.e. explicit construction) is much larger, something like N^{-k}. This upper bound is based on sums like the ones you treat. (I think this may be due to Ron Graham but unfortunately I can't find the reference offhand -- Marshall Bern showed it to me and Graham may have showed it to him.) Here's how it works: Suppose we have two sets of numbers a_i and b_i, such that sum(a_i^j - b_i^j)=0 for all j from 0 to k. (You have a page http://www.jiangmen.gd.cn/person/chen/TarryPrb.htm on this case.) For instance, your home page has a_i={1,19,20,51,57,80,82}, b_i={2,12,31,40,69,71,85}, k=6. Then, consider the number x = sum(sqrt(N - a_i) - sqrt(N - b_i)). Each of the summands sqrt(N - a_i) can be expressed as a Taylor series sqrt(N)*(1-y^2-y^2/8-y^3/16-5y^4/128-7y^5/256-...) where y=a_i/N. The fact that all the sums of powers of ai and bi are equal means that the initial terms in these Taylor series cancel and x = O(sqrt(n) y^{k+1}) = O(N^{-k-1/2}). Numerically, with the a_i above and N=1000, we have x ~= 2.5 * 10^{-11}. With N=10000 we have x ~= 6 * 10^{-18}, and in general multiplying N by 10 is going to lead to a reduction by around 3*10^6 in x. With more of the sums of powers being equal, x would go down even more quickly as a function of N. So, solutions to the Prouhet-Tarry-Escott problem lead to quite small sums of square roots. -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/