An improved bound on sums of square roots via the subspace theorem

The sum of square roots is the following problem: Given x₁, ..., x_n ∈ ℤ and a₁, ..., a_n ∈ ℕ decide whether E = x₁ √a₁ + … + x_n √a_n ≥ 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 the expression E. The current best lower bounds shows that doubly exponentially small (in n and the binary encoding lengths of the involved numbers). We provide a new bound of the form |E| ≥ γ ⋅ (n ⋅ max_i |x_i|)^-2n where γ is a constant depending on a₁, ..., a_n. This is singly exponential in n for fixed a₁, ..., a_n. The constant γ is not explicit and stems from the subspace theorem, a deep result in the geometry of numbers. Joint work with Matthieu Haeberle and Neta Singer.