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 and be positive integers. Define to be the minimum positive value of

**1.**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**, https://doi.org/10.1007/s004530010005**2.**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**, https://doi.org/10.1007/11821069_22**3.**Noam D. Elkies,*Rational points near curves and small nonzero |𝑥³-𝑦²| via lattice reduction*, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 33–63. MR**1850598**, https://doi.org/10.1007/10722028_2**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. 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****6.**Subhash Khot,*Hardness of approximating the shortest vector problem in lattices*, J. ACM**52**(2005), no. 5, 789–808. MR**2176563**, https://doi.org/10.1145/1089023.1089027**7.**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****8.**Francesco Pappalardi,*A survey on 𝑘-freeness*, Number theory, Ramanujan Math. Soc. Lect. Notes Ser., vol. 1, Ramanujan Math. Soc., Mysore, 2005, pp. 71–88. MR**2131677****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**(2006), no. 5, 194–198. MR**2253248**, https://doi.org/10.1016/j.ipl.2006.05.002**10.**C.-P. Schnorr,*A hierarchy of polynomial time lattice basis reduction algorithms*, Theoret. Comput. Sci.**53**(1987), no. 2-3, 201–224. MR**918090**, https://doi.org/10.1016/0304-3975(87)90064-8**11.**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**, https://doi.org/10.1016/0885-064X(92)90003-T

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.