Boris Bukh proved an amazing upper bound for E(n). He showed that E(n) < 1/e^{2√n+o(√n)}. Here is his argument: We know that square roots of square-free numbers are linearly independent over Z. Let b_i be the i^th square-free number. It is well known that b_i = π²i/6+ o(√i). To count the number of solutions of ∑ a_i b_i ≤ n, where the a_i are non-negative integers, we substitute the above formula for b_i to get ∑ i a_i + o(∑ √i a_i) ≤ 6n/π². Since ∑ i a_i is a partition of some number less than 6n/π², and asymptotically there are 1/(4t√3) e^π√(2t/3) partitions of t, there are no more than π²/(24n√3) e^2√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 (24n²√3)/π² 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/8n^5/2, he showed that E(n) eventually grows smaller than any power of n.

Ulrich Schimke, Claudio Baiocchi, and Philippe Fondanaiche 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 exhaustive searches! Here are the best approximations known for small n:

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.