Finding the Smallest Gap between Sums of Square Roots | SpringerLink
Skip to main content
Springer Nature Link
Log in

Finding the Smallest Gap between Sums of Square Roots

  • Conference paper
LATIN 2010: Theoretical Informatics (LATIN 2010)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 6034))

Included in the following conference series:

  • 1060 Accesses

Abstract

Let k and n be positive integers, n > k. Define r(n,k) to be the minimum positive value of

$$ |\sqrt{a_1} + \cdots + \sqrt{a_k} - \sqrt{b_1} - \cdots -\sqrt{b_k} | $$

where a 1, a 2, ⋯ , a k , b 1, b 2, ⋯ , b k are positive integers no larger than n. It is important to find a tight bound for r(n,k), in connection to the sum-of-square-roots problem, a famous open problem in computational geometry. The current best lower bound and upper bound are far apart. In this paper, we present an algorithm to find r(n,k) exactly in n k + o(k) time and in n ⌈k/2 ⌉ + o(k) space. As an example, we are able to compute r(100,7) exactly in a few hours on one PC. The numerical data indicate that the known upper bound seems closer to the truth value of r(n,k).

This research is partially supported by NSF grant CCF-0830522 and CCF-0830524.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11439
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14299
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Bernstein, D.: Enumerating solutions to p(a) + q(b) = r(c) + s(d). Math. of Comp. 70, 389–394 (2001)

    Article  MATH  Google Scholar 

  2. Borwein, P.: Computational Excursions in Analysis and Number Theory. Springer, Heidelberg (2002)

    MATH  Google Scholar 

  3. Burnikel, C., Fleischer, R., Mehlhorn, K., Schirra, S.: A strong and easily computable separation bound for arithmetic expressions involving radicals. Algorithmica 27(1), 87–99 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  4. Demaine, E.D., Mitchell, J.S.B., O’Rourke, J.: The open problems project: Problem 33, http://maven.smith.edu/~orourke/TOPP/

  5. Elkies, N.: On a 4 + b 4 + c 4 = d 4. Math. of Comp. 51, 825–835 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  6. Knuth, D.: The Art of Computer Programming, vol. 3. Addison-Wesley, Reading (1973)

    Google Scholar 

  7. Pappalardi, F.: A survey on k-power freeness. In: Proceeding of the Conference in Analytic Number Theory in Honor of Prof. Subbarao. Ramanujan Math. Soc. Lect. Notes Ser., vol. 1, pp. 71–88 (2002)

    Google Scholar 

  8. Qian, J., Wang, C.A.: How much precision is needed to compare two sums of square roots of integers? Inf. Process. Lett. 100(5), 194–198 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  9. Schönhage, A.: On the power of random access machines. In: Maurer, H.A. (ed.) ICALP 1979. LNCS, vol. 71, pp. 520–529. Springer, Heidelberg (1979)

    Google Scholar 

  10. Schroeppel, R., Shamir, A.: A T = o(2n/2), S = o(2n/4) algorithm for certain NP-complete problems. SIAM journal on Computing 10(3), 456–464 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  11. Shamir, A.: Factoring numbers in O(log n) arithmetic steps. Information Processing Letters 1, 28–31 (1979)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computer Science, The University of Oklahoma, Norman, OK, 73019, USA

    Qi Cheng & Yu-Hsin Li

Authors
  1. Qi Cheng
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yu-Hsin Li
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Faculty of Mathematics, Department of Computer Science, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada

    Alejandro López-Ortiz

Rights and permissions

Reprints and permissions

Copyright information

© 2010 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Cheng, Q., Li, YH. (2010). Finding the Smallest Gap between Sums of Square Roots. In: López-Ortiz, A. (eds) LATIN 2010: Theoretical Informatics. LATIN 2010. Lecture Notes in Computer Science, vol 6034. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12200-2_39

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-12200-2_39

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-12199-9

  • Online ISBN: 978-3-642-12200-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation