Bounding the sum of square roots via lattice reduction
HTML articles powered by AMS MathViewer
- by Qi Cheng, Xianmeng Meng, Celi Sun and Jiazhe Chen PDF
- Math. Comp. 79 (2010), 1109-1122 Request permission
Abstract:
Let $k$ and $n$ be positive integers. Define $R(n,k)$ to be the minimum positive value of \[ \left | e_i \sqrt {s_1} + e_2 \sqrt {s_2} + \cdots + e_k \sqrt {s_k} -t \right |, \] 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
- C. Burnikel, R. Fleischer, K. Mehlhorn, and S. Schirra, A strong and easily computable separation bound for arithmetic expressions involving radicals, Algorithmica 27 (2000), no. 1, 87–99. Implementation of geometric algorithms. MR 1748595, DOI 10.1007/s004530010005
- Qi Cheng, On comparing sums of square roots of small integers, Mathematical foundations of computer science 2006, Lecture Notes in Comput. Sci., vol. 4162, Springer, Berlin, 2006, pp. 250–255. MR 2298182, DOI 10.1007/11821069_{2}2
- Noam D. Elkies, Rational points near curves and small nonzero $|x^3-y^2|$ via lattice reduction, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 33–63. MR 1850598, DOI 10.1007/10722028_{2}
- 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.
- M. R. Garey, R. L. Graham, and D. S. Johnson, Some NP-complete geometric problems, Eighth Annual ACM Symposium on Theory of Computing (Hershey, Pa., 1976), Assoc. Comput. Mach., New York, 1976, pp. 10–22. MR 0468310
- Subhash Khot, Hardness of approximating the shortest vector problem in lattices, J. ACM 52 (2005), no. 5, 789–808. MR 2176563, DOI 10.1145/1089023.1089027
- Daniele Micciancio and Shafi Goldwasser, Complexity of lattice problems, The Kluwer International Series in Engineering and Computer Science, vol. 671, Kluwer Academic Publishers, Boston, MA, 2002. A cryptographic perspective. MR 2042139, DOI 10.1007/978-1-4615-0897-7
- Francesco Pappalardi, A survey on $k$-freeness, Number theory, Ramanujan Math. Soc. Lect. Notes Ser., vol. 1, Ramanujan Math. Soc., Mysore, 2005, pp. 71–88. MR 2131677
- Jianbo Qian and Cao An Wang, How much precision is needed to compare two sums of square roots of integers?, Inform. Process. Lett. 100 (2006), no. 5, 194–198. MR 2253248, DOI 10.1016/j.ipl.2006.05.002
- C.-P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms, Theoret. Comput. Sci. 53 (1987), no. 2-3, 201–224. MR 918090, DOI 10.1016/0304-3975(87)90064-8
- Prasoon Tiwari, A problem that is easier to solve on the unit-cost algebraic RAM, J. Complexity 8 (1992), no. 4, 393–397. MR 1195259, DOI 10.1016/0885-064X(92)90003-T
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
- 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.
- © Copyright 2009
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 79 (2010), 1109-1122
- MSC (2000): Primary 11Y40
- DOI: https://doi.org/10.1090/S0025-5718-09-02304-7
- MathSciNet review: 2600558