Sums of square roots that are close to an integer

Abstract

Let $k\in \mathbb{N}$ and suppose we are given $k$ integers $1\le a_1,\dots ,a_k\le n$. If $\sqrt{a_1}+\cdots +\sqrt{a_k}$ is not an integer, how close can it be to one? When $k=1$, the distance to the nearest integer is $\gtrsim n^{-1/2}$. Angluin-Eisenstat observed the bound $\gtrsim n^{-3/2}$ when $k=2$. We prove there is a universal $c>0$ such that, for all $k\ge 2$, there exists a $c_k>0$ and $k$ integers in $\left\{1,2,\dots ,n\right\}$ with $$0<\Vert \sqrt{a_1}+\cdots +\sqrt{a_k}\Vert \le c_k\cdot n^{-c\cdot k^{1/3}},$$ where $\Vert \cdot \Vert$ denotes the distance to the nearest integer. This is a case of the square-root sum problem in numerical analysis where the usual cancellation constructions do not apply: even for $k=3$, constructing explicit examples of integers whose square root sum is nearly an integer appears to be nontrivial.