Problem of the Month (May 2002)

This month we investigate square root approximations, such as √164 + √126 ≈ √153 + √136. The error above is only .000000031. How small is the smallest non-zero error between sums of square roots of integers that add to no more than n? We allow any number of terms on both sides.


ANSWERS

Let E(n) be the smallest non-zero error in an approximation involving square roots of integers totalling n.

Boris Bukh proved an amazing upper bound for E(n). He showed that E(n) < 1/e2√n+o(√n). Here is his argument: We know that square roots of square-free numbers are linearly independent over Z. Let bi be the ith square-free number. It is well known that bi = π2i/6+ o(√i). To count the number of solutions of ∑ ai bi ≤ n, where the ai are non-negative integers, we substitute the above formula for bi to get ∑ i ai + o(∑ √i ai) ≤ 6n/π2. Since ∑ i ai is a partition of some number less than 6n/π2, and asymptotically there are 1/(4t√3) eπ√(2t/3) partitions of t, there are no more than π2/(24n√3) e2√n solutions of the above inequality. At most n linear combinations have the same value modulo 1. So, by Dirichlet's principle there are two of them which differ by less than (24n2√3)/π2 e-2√n. Subtract these two, and add enough 1's, and we get the result. There is some slight fudging of the error terms in the proof, but it is likely true.

Ulrich Schimke noted that 2√a ≈ √(a-1) + √(a+1) with error approximately 1/4a√a. Another approximation he gave was if ab=cd and (a+b)-(c+d)=1, then √a + √b ≈ √c + √d, with error approximately 1/(2√c + 2√d). He thinks continued fractions mights be useful, but he hasn't figured out how.

Claudio Baiocchi pointed out that if you put all the terms of an approximation on one side and square both sides, the approximation gets much better. Generalizing approximations like | √n - 3√(n+1) + 3√(n+2) - √(n+3) | ≤ 3/8n5/2, he showed that E(n) eventually grows smaller than any power of n.

Ulrich Schimke, Claudio Baiocchi, and Philippe Fondanaiche (to whom i still can't reply for some reason) sent me some good approximations for small n. Claudio Baiocchi claims these results up to n=100 are optimal. He wrote a computer program to do exhautive searches! Here are the best approximations known for small n:

Best Approximations

nBest ApproximationSmallest ErrorAuthor
3√2 ≈ √1.414EF
5√3 ≈ 2√1.267EF
72√2 ≈ 3√1.171EF
8√3 + √1 ≈ 2√2.0963EF
9√6 ≈ √2 + √1.0352EF
12√5 + √3 ≈ 4√1.0318EF
13√5 + 2√1 ≈ 3√2.00657EF
15√7 + √1 ≈ √5 + √2.00453EF
19√11 + √2 ≈ √3 + 3√1.00121EF
24√7 + √6 + √3 ≈ 2√2 + 4√1.00113US
252√7 + √1 ≈ 2√2 + 2√3.00102US
27√7 + 5√1 ≈ √6 + 3√3 .000109EF
31√6 + √5 + 3√2 ≈ 4√3 + 2√1.00000482EF
48√15 + 2√6 + 2√3 ≈ √5 + 10√1.00000353US
54√17 + √13 + √6 + √5 ≈ √2 + 11√1.00000105US
58√19 + √10 + √7 + √3 ≈ 2√6 + 7√1.000000763US
64√15 + √7 + 3√5 ≈ √14 + 6√2 + √1.000000171US
81√10 + 6√5 ≈ √11 + 4√6 + 2√3.000000148CB
82√14 + √11 + √10 + √7 + √2 ≈ √19 + √6 + 2√5 + 1√1.0000000694CB
83√17 + 3√5 + √2 + 4√1 ≈ √13 + 2√7 + 3√6.00000000545CB

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 5/18/02.