Bounding the sum of square roots via lattice reduction
Qi Jin Cheng, Xianmeng Meng, Celi Sun, Jiazhe Chen · Mathematics of Computation · 2009
Let k k and n n be positive integers. Define R ( n , k ) R(n,k) to be the minimum positive value of \[ | e i s 1 + e 2 s 2 + ⋯ + e k s k − t | , \left | e_i \sqrt {s_1} + e_2 \sqrt {s_2} + \cdots + e_k \sqrt {s_k} -t \right |, \] where s 1 , s 2 , ⋯ , s k s_1, s_2, \cdots , s_k are positive integers no larger than n n , t t is an integer and e i ∈ { 1 , 0 , − 1 } e_i\in \{1,0, -1\} for all 1 ≤ i ≤ k 1\leq i\leq k . It is important in computational geometry to determine a good lower and upper bound of