From: orourke@server.cs.jhu.edu (Joseph O'Rourke)
Newsgroups: sci.math
Subject: Radical difference
Date: 25 Dec 90 19:50:44 GMT
Reply-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.math
Subject: Re: Radical difference
Date: 25 Dec 90 22:10:54 GMT
Organization: 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.edu
Newsgroups: sci.math
Subject: Radical difference: clarification
Date: 26 Dec 90 03:42:35 GMT
Reply-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.edu
Newsgroups: sci.math
Subject: Radical difference: summary of responses
Date: 28 Dec 90 15:08:34 GMT
Reply-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.edu
To: jmchen@pub.jiangmen.gd.cn
Subject: Re: Welcome to my site on Equal sums of like powers
Date: 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/