| Title: |
An Improved Bound on Sums of Square Roots via the Subspace Theorem |
| Authors: |
Eisenbrand, Friedrich; Haeberle, Matthieu; Singer, Neta |
| Contributors: |
Friedrich Eisenbrand and Matthieu Haeberle and Neta Singer |
| Publisher Information: |
Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
| Publication Year: |
2024 |
| Collection: |
DROPS - Dagstuhl Research Online Publication Server (Schloss Dagstuhl - Leibniz Center for Informatics ) |
| Subject Terms: |
Exact computing; Separation Bounds; Computational Geometry; Geometry of Numbers |
| Description: |
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. |
| Document Type: |
article in journal/newspaper; conference object |
| File Description: |
application/pdf |
| Language: |
English |
| Relation: |
Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024); https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.54 |
| DOI: |
10.4230/LIPIcs.SoCG.2024.54 |
| Availability: |
https://doi.org/10.4230/LIPIcs.SoCG.2024.54; https://nbn-resolving.org/urn:nbn:de:0030-drops-199993; https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.54 |
| Rights: |
https://creativecommons.org/licenses/by/4.0/legalcode |
| Accession Number: |
edsbas.84C5BB44 |
| Database: |
BASE |