Error Term Estimates for Sets of Remainders

Source abstract

For a positive integer $n$, let $$S_1(n)=\{n\bmod k:1\leq k\leq\lfloor n/2\rfloor\}, \qquad s_1(n)=|S_1(n)|.$$ Baraskar and Vukusic proved $s_1(n)=Ξn+O(n/(\log n\log\log n))$ for an explicit positive constant $Ξ$, and asked for a sharper error term. Their computations suggested that an $O(n^{1/3})$ bound might hold. We prove that, for every $α>\sqrt2$, $$\limsup_{n\to\infty} \frac{s_1(n)-Ξn}{n\exp\{-α\sqrt{\log n\log\log n}\}} =\infty,$$ and the corresponding limit inferior is $-\infty$. In particular, no fixed power saving is possible. We also prove the complementary upper estimate $$s_1(n)=Ξn+O\left( n\exp\{-α\sqrt{\log n\log\log n}\} \right)$$ for every fixed $α\in (0,\sqrt{2})$, sharpening the previous $O(n/(\log n\log\log n))$ bound. Thus, the constant $\sqrt2$ is the threshold for bounds of the form $n\exp\{-α\sqrt{\log n\log\log n}\}$.