Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. An Improved Bound on Sums of Square Roots via the Subspace Theorem
 
conference paper

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

Eisenbrand, Friedrich  
•
Haeberle, Matthieu  
•
Singer, Neta  
Mulzer, Wolfgang
•
Phillips, Jeff M.
June 1, 2024
Leibniz International Proceedings in Informatics, LIPIcs
40 International Symposium on Computational Geometry

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.

  • Details
  • Metrics
Type
conference paper
DOI
10.4230/LIPIcs.SoCG.2024.54
Scopus ID

2-s2.0-85195519626

Author(s)
Eisenbrand, Friedrich  

École Polytechnique Fédérale de Lausanne

Haeberle, Matthieu  

École Polytechnique Fédérale de Lausanne

Singer, Neta  

École Polytechnique Fédérale de Lausanne

Editors
Mulzer, Wolfgang
•
Phillips, Jeff M.
Date Issued

2024-06-01

Publisher

Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Published in
Leibniz International Proceedings in Informatics, LIPIcs
ISBN of the book

9783959773164

Book part number

293

Article Number

54

Subjects

Computational Geometry

•

Exact computing

•

Geometry of Numbers

•

Separation Bounds

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DISOPT  
Event nameEvent acronymEvent placeEvent date
40 International Symposium on Computational Geometry

Athens, Greece

2024-06-11 - 2024-06-14

Available on Infoscience
January 26, 2025
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/244609
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés