The question asked here is a follow up to this question, which was answered by user GH from MO. [EDIT: The question is edited for clarification after receiving a comment on the original posting.]

As there, let $q$ be a natural number, let $P = \phi(q)/q$ be the "probability" that a randomly chosen integer is relatively prime to q. Then, following Montgomery and Vaughan in On the distribution of reduced residues, the second moment of the number of reduced residues modulo $q$ in an interval of length $h$ about its mean, $hP$, can be stated as $$ M_2(q;h) = qP^2 \sum_{\substack{{r \mid q }\\{r > 1}}} \mu(r)^2 \left( \prod_{\substack{ {p \mid q }\\{p \nmid r} }} \frac{p(p-2)}{(p-1)^2} \right) r^2 \phi(r)^{-2} \left\{ \frac{h}{r}\right\}\left( 1 - \left\{ \frac{h}{r}\right\}\right). $$ Applying the inequality $\{\alpha\}(1 - \{\alpha\}) \leq \alpha$ then gives the upper bound $$\tag{1} M_2(q;h)\leq qhP, $$ while a lower bound is given by $$ M_2(q; h) \geq qhP - qhPQ + O(qhP^2) $$ where $Q=\prod_{\substack{{p \mid q}\\{p>h}}} (1-1/p)$.

Since $\{\alpha\}\leq 1$, we also have that $\{\alpha\}(1 - \{\alpha\}) \leq 0.25$. This allows for a second upper bound, $$\tag{2} M_2(q;h) \leq 0.25 \, qP^2 \sum_{\substack{{r \mid q }\\{r > 1}}} \mu(r)^2 \left( \prod_{\substack{ {p \mid q }\\{p \nmid r} }} \frac{p(p-2)}{(p-1)^2} \right) r^2 \phi(r)^{-2}. $$

As pointed out by user Ofir Gorodetsky in the comment below, the upper bound in (1) is already optimal for those choices of $q$ such that the upper and lower bounds are of same order. For example, taking $q=\prod_{p\leq h^C} p$ for large enough $C$, we have that $M_2(q;h)\asymp qhP$.

Here I'd like to consider the rather opposite situation, when $C$ is small. Specifically, take $q=\prod_{p\leq h^C} p$, where $C<1$. Then we have that $Q=1$ and the lower bound takes the form $$ M_2(q; h) \geq O(qhP^2), $$ which leaves some more wiggle room between the upper and lower bounds, and I'd like to know whether the upper bound in (2) this case provides some improvement on (1).


Given $q=\prod_{p\leq h^C} p$, where $C<1$. Does the upper bound for $M_2(q;h)$ stated in (2) provide a sharper bound compared to (1) in this case? And is it possible to express the upper bound in (2) a bit more simplified or asymptotically?

  • 1
    $\begingroup$ At least for some families of $q$, the upper bound is already optimal in the sense that there is a matching lower bound of the same order magnitude; this follows from the general lower bound given at the end of your linked question. To be concrete, taking $q = \prod_{p \le h^C} p$ for sufficiently large $C$, we have $M_2(q;h) \asymp qhP$. $\endgroup$ May 14, 2020 at 9:27
  • $\begingroup$ Thanks for pointing to an important clarification! I've edited the question to focus on the case when $q=\prod_{p\leq h^C} p$ and $C<1$, as in this case the lower bound should be $M_2(q;h)\geq O(qhP^2)$ (is it a better or more correct way to write this inequality?). $\endgroup$
    – user45947
    May 14, 2020 at 11:28
  • 1
    $\begingroup$ Unfortunately, if you just use the fact that $\{ \alpha\}(1-\{\alpha\})$ is bounded, you do not obtain a superior upper bound. Indeed, assuming $q$ is squarefree (as we may), both $\mu(r)^2$ and $\prod_{p\mid q, \, p \nmid r} p(p-2)/(p-1)^2$ are $\asymp 1$, and your idea leads to an upper bound of order $qP^2 \sum_{r \mid q, \, r> 1} r^2/\phi(r)^2$, which is much larger qualitatively than $qPh$ for $q=\prod_{p \le x} p$ with $x \ge \log^2 h$... $\endgroup$ May 14, 2020 at 12:27
  • 1
    $\begingroup$ A heuristic for using $\{ \alpha \} (1-\{\alpha\}) \le \alpha$ is that $r^2/\phi(r)^2$ being large is correlated with $r$ being large which is correlated with $\{ h/r \}(1-\{h/r \})$ being of order $h/r$. $\endgroup$ May 14, 2020 at 12:29
  • $\begingroup$ Thanks for the effort! I'd be happy to accept that as an answer if you'd want to write it up as such. $\endgroup$
    – user45947
    May 14, 2020 at 13:07


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.