An Improved Bound on Sums of Square Roots via the Subspace Theorem
The sum of square roots is as follows: Given x1, . . ., xn ∈ Z and a1, . . ., an ∈ N decide whether E = Pni=1 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.
2-s2.0-85195519626
École Polytechnique Fédérale de Lausanne
École Polytechnique Fédérale de Lausanne
École Polytechnique Fédérale de Lausanne
2024-06-01
9783959773164
293
54
REVIEWED
EPFL
| Event name | Event acronym | Event place | Event date |
Athens, Greece | 2024-06-11 - 2024-06-14 | ||