Error Term Estimates for Sets of Remainders

Abstract

For a positive integer $n$, let $$S_1(n)=\{n\mathrm{mod}k:1\le k\le \lfloor n/2\rfloor \},s_1(n)=|S_1(n)|.$$ Baraskar and Vukusic proved $s_1(n)=\Xi n+O(n/(\log n\log \log n))$ for an explicit positive constant $\Xi$, and asked for a sharper error term. Their computations suggested that an $O(n^{1/3})$ bound might hold. We prove that, for every $\alpha >\sqrt{2}$, $$\underset{n\to \infty }{\mathrm{limsup}}\frac{s_1(n)-\Xi n}{n\exp \{-\alpha \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)=\Xi n+O\left(n\exp \{-\alpha \sqrt{\log n\log \log n}\}\right)$$ for every fixed $\alpha \in (0,\sqrt{2})$, sharpening the previous $O(n/(\log n\log \log n))$ bound. Thus, the constant $\sqrt{2}$ is the threshold for bounds of the form $n\exp \{-\alpha \sqrt{\log n\log \log n}\}$.