On Comparing Sums of Square Roots of Small Integers

Let k and n be positive integers, nk. Define r(n,k) to be the minimum positive value of $ |\sqrt{a_1} + \cdots + \sqrt{a_k} -- \sqrt{b_1} -- \cdots -\sqrt{b_k} | $ where a1, a2, ⋯, ak, b1, b2, ⋯, bk are positive integers no larger than n. It is an important problem in computational geometry to determine a good upper bound of –logr(n,k). In this paper we prove an upper bound of 2$^{O({\it n}/log{\it n})}$, which is better than the best known result O(22k logn) whenever n ≤ck logk for some constant c. In particular, our result implies an algorithm subexponential in k (i.e. with time complexity 2$^{o({\it k})}$(logn)O(1) ) to compare two sums of square roots of integers of value o(k logk).