DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2024.54

An Improved Bound on Sums of Square Roots via the Subspace Theorem

Authors: Friedrich Eisenbrand, Matthieu Haeberle, and Neta Singer

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract

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.

Cite as

Friedrich Eisenbrand, Matthieu Haeberle, and Neta Singer. An Improved Bound on Sums of Square Roots via the Subspace Theorem. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 54:1-54:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{eisenbrand_et_al:LIPIcs.SoCG.2024.54,
  author =	{Eisenbrand, Friedrich and Haeberle, Matthieu and Singer, Neta},
  title =	{{An Improved Bound on Sums of Square Roots via the Subspace Theorem}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{54:1--54:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.54},
  URN =		{urn:nbn:de:0030-drops-199993},
  doi =		{10.4230/LIPIcs.SoCG.2024.54},
  annote =	{Keywords: Exact computing, Separation Bounds, Computational Geometry, Geometry of Numbers}
}

Search Results

Documents authored by Haeberle, Matthieu

An Improved Bound on Sums of Square Roots via the Subspace Theorem

Abstract

Cite as

Thanks for your feedback!

Could not send message