On comparing sums of square roots of small integers

2006/02/28 by Qi Cheng, Cheng, Qi
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #F.2.1 #FOS: Computer and information sciences #cs.CG

paper · pdf · doi:10.48550/arxiv.cs/0603002

arxiv created 2006/02/28 · openalex publication_date 2006/02/28 · arxiv updated 2009/12/01 · openalex created_date 2016/07/22 · openalex updated_date 2026/07/28

Abstract

Let k and n be positive integers, n>k. Define r(n,k) to be the minimum positive value of |√(a₁) + ... + √(a_k) - √(b₁) - >... -√(b_k) | where a₁, a₂, ..., a_k, b₁, b₂, ..., b_k are positive integers no larger than n. It is an important problem in computational geometry to determine a good upper bound of -log r(n,k). In this paper we prove an upper bound of 2^{O(n/log n)} log n, which is better than the best known result O(2^2k log n) whenever n ≤ cklog k for some constant c. In particular, our result implies a \em subexponential algorithm to compare two sums of square roots of integers of size o(klog k).

Related

• Sums of square roots that are close to an integer
• An improved bound on sums of square roots via the subspace theorem
• USSR is in P/poly
• Distribution of sums of square roots modulo 1
• A Fast Algorithm for Determining the Existence and Value of Integer Roots of N