An Improved Bound on Sums of Square Roots via the Subspace Theorem

The sum of square roots is as follows: Given x1, . . ., xn ∈ Z and a1, . . ., an ∈ N decide whether E = Pni=1 xi √ai ≥ 0. It is a prominent open problem (Problem 33 of the Open Problems Project), whether this can be decided in polynomial time. The state-of-the-art methods rely on separation bounds, which are lower bounds on the minimum nonzero absolute value of E. The current best bound shows that |E| ≥ (n · maxi(|xi| · √ai))−2n, which is doubly exponentially small. We provide a new bound of the form |E| ≥ γ · (n · maxi |xi|)−2n where γ is a constant depending on a1, . . ., an. This is singly exponential in n for fixed a1, . . ., an. The constant γ is not explicit and stems from the subspace theorem, a deep result in the geometry of numbers.