2026-07-26T00:15:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19999 2024-06-06T06:21:15Z ddc:004 open_access

An Improved Bound on Sums of Square Roots via the Subspace Theorem Eisenbrand, Friedrich Haeberle, Matthieu Singer, Neta Exact computing Separation Bounds Computational Geometry Geometry of Numbers The sum of square roots is as follows: Given x_1,… ,x_n ∈ ℤ and a₁,… ,a_n ∈ ℕ decide whether E = ∑_{i=1}^n x_i √{a_i} ≥ 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 ⋅ max_i (|x_i| ⋅√{a_i})) ^{-2ⁿ}, which is doubly exponentially small. 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_1,… ,a_n. The constant γ is not explicit and stems from the subspace theorem, a deep result in the geometry of numbers. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Friedrich Eisenbrand and Matthieu Haeberle and Neta Singer 2024 Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2024.54 urn:nbn:de:0030-drops-199993 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.54 eng https://creativecommons.org/licenses/by/4.0/legalcode