An Optimal Bound for Sum of Square Roots of Special Type of Integers

Abstract The sum of square roots of integers problem is to find the minimum nonzero difference between two sums of square roots of integers. Let r(n,k) denote the minimum nonzero positive value: | ∑ k √ i=1 ai − ∑ k √ i=1 bi|, where ai and bi are positive integers not larger than integer n. We prove by an explicit construction that r(n,k) = O(n−2k+ 3 2) for fixed k and any n. Our result implies that in order to compare two sums of k square roots of integers with at most d digits per integer, one might need precision of as many as (2k − 3)d digits. We also prove that this bound is optimal 2 for a wide range of integers, i.e., r(n,k) = Θ(n−2k+ 3 2) for fixed k and for those integers in the form of n = � �2 � �2 2k−1