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

Abstract

The sum of square roots is as follows: Given $x_1,\dots ,x_n\in \mathbb{Z}$ and $a_1,\dots ,a_n\in \mathbb{N}$ decide whether $E={\sum }_{i=1}^n{x}_i\sqrt{a_i}\ge 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|\ge {\left(n\cdot {\max }_i(|x_i|\cdot \sqrt{a_i})\right)}^{-2^n}$, which is doubly exponentially small. We provide a new bound of the form $|E|\ge \gamma \cdot (n\cdot {\max }_i|x_i|{)}^{-2n}$ where $\gamma$ is a constant depending on $a_1,\dots ,a_n$. This is singly exponential in $n$ for fixed $a_1,\dots ,a_n$. The constant $\gamma$ is not explicit and stems from the subspace theorem, a deep result in the geometry of numbers.