Sum of square roots

This is the open problem number 33.

Given 2k integers a1, ... ak and b1, ... bk, all smaller than a given integer n, how close can sqrt(a1)+...+sqrt(ak)-sqrt(b1)-...-sqrt(bk) be to 0? An exemple showing that this can be small is given by the discrete derivative of the square root function, which for k=2 would be sqrt(m+3)-3sqrt(m+2)+3sqrt(m+1)-sqrt(m). A bound on how small a difference can be is obtained by repeatedly squaring until no square root remains. However, there is a huge gap between the two. If we call f(n,k) the minimum of the difference of square roots, and study g(n,k)=-log(f(n,k))/log(n) as a function of n for a fixed k, we have a linear lower bound and an exponential upper bound. For k=2, the lower bound is 2.5 and the upper bound is 3.5. In order to know which bound should be improved, I computed f(n,2) for all values of n up to 312563. The following table shows the values of n for which f(n)<f(n-1) and the corresponding values of f(n), -g(n-1) and -g(n). It seems clear from these results that the right answer is 3.5, and the discrete derivative of the square root function does not provide a good enough bound.