On comparing sums of square roots of small integers
<|reference_start|>On comparing sums of square roots of small integers: Let $k$ and $n$ be positive integers, $n>k$. Define $r(n,k)$ to be the minimum positive value of $$ |\sqrt{a_1} + ... + \sqrt{a_k} - \sqrt{b_1} - >... -\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 an important problem in computational geometry to determine a good upper bound of $-\log r(n,k)$. In this paper we prove an upper bound of $ 2^{O(n/\log n)} \log n$, which is better than the best known result $O(2^{2k} \log n)$ whenever $ n \leq ck\log k$ for some constant $c$. In particular, our result implies a {\em subexponential} algorithm to compare two sums of square roots of integers of size $o(k\log k)$.<|reference_end|>
@article{cheng2006on,
    title={On comparing sums of square roots of small integers},
    author={Qi Cheng},
    journal={arXiv preprint arXiv:cs/0603002},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0603002},
    primaryClass={cs.CG}
}