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?)

  • 1. C. Burnikel, R. Fleischer, K. Mehlhorn, and S. Schirra.
    A strong and easily computable separation bound for arithmetic expressions involving radicals.
    Algorithmica, 27(1):87-99, 2000. MR 1748595 (2001h:68148)
  • 2. Qi Cheng.
    On comparing sums of square roots of small integers.
    In Proc. of 31st International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 4162 of Lecture Notes in Computer Science, 2006. MR 2298182 (2007m:68256)
  • 3. Noam D. Elkies.
    Rational points near curves and small nonzero $ \vert x^3-y^2\vert$ via lattice reduction.
    In W. Bosma, editor, Proceedings of ANTS-4, volume 1838 of Lecture Notes in Computer Science, pages 33-63, 2000. MR 1850598 (2002g:11035)
  • 4. Kousha Etessami and Mihalis Yannakakis.
    On the complexity of Nash equilibria and other fixed points.
    In Proceedings of the 48th FOCS, pages 113-123, 2007.
  • 5. M. Garey, R.L. Graham, and D.S. Johnson.
    Some NP-complete geometric problems.
    In Proc. ACM Symp. Theory Comp., pages 10-21, 1976. MR 0468310 (57:8146)
  • 6. Subhash Khot.
    Hardness of approximating the shortest vector problem in lattices.
    In Proc. $ 45$th IEEE Symp. on Foundations of Comp. Science, 2004. MR 2176563 (2006h:68051)
  • 7. Daniele Micciancio and Shafi Goldwasser.
    Complexity of Lattice Problems: A Cryptographic Perspective.
    Kluwer Academic Publishers, 2002. MR 2042139 (2004m:94067)
  • 8. Francesco Pappalardi.
    A survey on $ k$ freeness.
    In Proceeding of the Conference in Analytic Number Theory in Honor of Prof. Subbarao, number 1 in Ramanujan Math. Soc. Lect. Notes Ser., pages 71-88, 2002. MR 2131677 (2005k:11194)
  • 9. Jianbo Qian and Cao An Wang.
    How much precision is needed to compare two sums of square roots of integers?
    Inform Process. Lett., 100(5):194-198, 2006. MR 2253248 (2008f:65040)
  • 10. C. P. Schnorr.
    A hierarchy of polynomial time lattice basis reduction algorithms.
    Theoretical Computer Science, 53(2-3):201-224, 1987. MR 918090 (89h:11085)
  • 11. Prasoon Tiwari.
    A problem that is easier to solve on the unit-cost algebraic RAM.
    Journal of Complexity, 8(4):393-397, 1992. MR 1195259 (94a:68056)

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