Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Bounding the sum of square roots via lattice reduction


Authors: Qi Cheng, Xianmeng Meng, Celi Sun and Jiazhe Chen
Journal: Math. Comp. 79 (2010), 1109-1122
MSC (2000): Primary 11Y40
DOI: https://doi.org/10.1090/S0025-5718-09-02304-7
Published electronically: September 30, 2009
MathSciNet review: 2600558
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ k$ and $ n$ be positive integers. Define $ R(n,k)$ to be the minimum positive value of

$\displaystyle \left\vert e_i \sqrt{s_1} + e_2 \sqrt{s_2} + \cdots + e_k \sqrt{s_k} -t \right\vert, $

where $ s_1, s_2, \cdots, s_k$ are positive integers no larger than $ n$, $ t$ is an integer and $ e_i\in \{1,0, -1\}$ for all $ 1\leq i\leq k$. It is important in computational geometry to determine a good lower and upper bound of $ R(n,k)$. In this paper we show that this problem is closely related to the shortest vector problem in certain integral lattices and present an algorithm to find lower bounds based on lattice reduction algorithms. Although we can only prove an exponential time upper bound for the algorithm, it is efficient for large $ k$ when an exhaustive search for the minimum value is clearly infeasible. It produces lower bounds much better than the root separation technique does. Based on numerical data, we formulate a conjecture on the length of the shortest nonzero vector in the lattice, whose validation implies that our algorithm runs in polynomial time and the problem of comparing two sums of square roots of small integers can be solved in polynomial time. As a side result, we obtain constructive upper bounds for $ R(n,k)$ when $ n$ is much smaller than $ 2^{2k}$.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y40

Retrieve articles in all journals with MSC (2000): 11Y40


Additional Information

Qi Cheng
Affiliation: School of Computer Science, The University of Oklahoma, Norman, Oklahoma 73019
Email: qcheng@cs.ou.edu

Xianmeng Meng
Affiliation: Lab of Cryptographic Technology and Information Security, Shandong University, Jinan 250100, People’s Republic of China

Celi Sun
Affiliation: School of Computer Science, The University of Oklahoma, Norman, Oklahoma 73019
Email: scl@cs.ou.edu

Jiazhe Chen
Affiliation: Lab of Cryptographic Technology and Information Security, Shandong University, Jinan 250100, People’s Republic of China

DOI: https://doi.org/10.1090/S0025-5718-09-02304-7
Received by editor(s): January 5, 2009
Received by editor(s) in revised form: May 1, 2009
Published electronically: September 30, 2009
Additional Notes: This research is partially supported by NSF Career Award CCR-0237845 of USA and by Project 973 (no: 2007CB807903 and no: 2007CB807902) of China.
Article copyright: © Copyright 2009 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society