On the minimum gap between sums of square roots of small integers

Let kk and nn be positive integers, n>kn>k. Define r(n,k)r(n,k) to be the minimum positive value of |a1+⋯+ak−b1−⋯−bk| where a1,a2,…,ak,b1,b2,…,bka1,a2,…,ak,b1,b2,…,bk are positive integers no larger than nn. Define R(n,k)R(n,k) to be −logr(n,k)−logr(n,k). It is important to find tight bounds for r(n,k)r(n,k) and R(n,k)R(n,k), in connection to the sum-of-square-roots problem, a famous open problem in computational geometry. The current best lower bound and upper bound are far apart. In this paper, we prove an upper bound of 2O(n/logn)2O(n/logn) for R(n,k)R(n,k), which is better than the best known result O(22klogn)O(22klogn) whenever n≤cklogkn≤cklogk for some constant cc. In particular, our result implies an algorithm subexponential   in kk (i.e. with time complexity 2o(k)(logn)O(1)2o(k)(logn)O(1)) to compare two sums of kk square roots of integers of value o(klogk)o(klogk). We then present an algorithm to find r(n,k)r(n,k)exactly   in nk+o(k)nk+o(k) time and in n⌈k/2⌉+o(k)n⌈k/2⌉+o(k) space. As an example, we are able to compute r(100,7)r(100,7) exactly in a few hours on a single PC. The numerical data indicate that the root separation bound is very far away from the true value of r(n,k)r(n,k).