2023/12/04 by Friedrich Eisenbrand, Eisenbrand, Friedrich, Matthieu Haeberle +3 · 1 citation
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Cryptography and Residue Arithmetic #FOS: Computer and information sciences #Numerical Methods and Algorithms
paper · pdf · doi:10.48550/arxiv.2312.02057
openalex publication_date 2023/12/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The sum of square roots is as follows: Given x1,…,xn ∈ ℤ and a1,…,an ∈ ℕ decide whether E=∑i=1n 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.