In their paper, On the distribution of reduced residues, Montgomery and Vaughan state early on that

With a more careful argument from (2) it is easily seen that $$\tag{*} qhP - qhPQ + O(qhP^2) \leq M_2(q; h) \leq qhP $$ where $Q=\prod_{\substack{{p \mid q}\\{p>h}}} (1-1/p)$.

However, the careful argument is omitted, and I haven't been able to lure out the first inequality myself. I hope asking here could help me in that direction. The introduction of Montgomery and Vaughan's paper is included below as background.

Question: How can one derive
$$ qhP - qhPQ + O(qhP^2) \leq M_2(q; h) $$ from (2) below?


Let $q$ be a natural number, let $P = \phi(q)/q$ be the "probability" that a randomly chosen integer is relatively prime to q, and let $$ \tag{1} M_k(q;h) = \sum_{n=1}^{q} \left( \sum_{\substack{{m=1}\\{(m+n,q)=1}}}^{h} 1 - h P \right)^k. $$ This is the $k$-th moment of the number of reduced residues modulo $q$ in an interval of length $h$ about its mean, $hP$. Clearly $M_1(q; h) = 0$. By an elementary calculation (see Hausman and Shapiro [3]) it may be shown that $$\tag{2} 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). $$ This with the simple inequality $\{\alpha\}(1 - \{\alpha\}) \leq \alpha$ gives immediately the estimate $$\tag{3} M_2(q;h)\leq qhP. $$ With a more careful argument from (2) it is easily seen that $$ qhP - qhPQ + O(qhP^2) \leq M_2(q; h) \leq qhP $$ where $Q=\prod_{\substack{{p \mid q}\\{p>h}}} (1-1/p)$.


1 Answer 1


1. First we prove the upper bound in $(\ast)$. Using the original hint, and noting that $P=\phi(q)/q$, it suffices to show the identity $$\sideset_{^\flat}\sum_{r\mid q}\frac{r}{\phi(r)^2} \left(\prod_{\substack{ {p \mid q }\\{p \nmid r} }}\frac{p(p-2)}{(p-1)^2} \right)=\frac{q}{\phi(q)},$$ where $\flat$ indicates that the summation is restricted to square-free values of $r$. The two sides are multiplicative in $q$, hence it suffices to verify the special case when $q$ is the power of a prime $p$. In that case, the identity boils down to $$\frac{p(p-2)}{(p-1)^2}+\frac{p}{(p-1)^2}=\frac{p}{p-1},$$ which is evident.

2. Now we prove the lower bound in $(\ast)$, which can be rewritten as $$\frac{M_2(q;h)}{qhP}\geq 1-Q+O(P).$$ Equivalently, $$\frac{1}{\phi(q)}\sideset_{^\flat}\sum_{r\mid q}\frac{r}{h}\left\{ \frac{h}{r}\right\}\left( 1 - \left\{ \frac{h}{r}\right\}\right)\prod_{\substack{ {p \mid q }\\{p \nmid r} }}(p-2)\geq 1-Q+O(P).$$ It is clear that (cf. previous point) $$\frac{1}{\phi(q)}\sideset_{^\flat}\sum_{r\mid q}\prod_{\substack{ {p \mid q }\\{p \nmid r} }}(p-2)=1,$$ hence the lower bound in $(\ast)$ is equivalent to $$\frac{1}{\phi(q)}\sideset_{^\flat}\sum_{r\mid q}f(h,r)\prod_{\substack{ {p \mid q }\\{p \nmid r} }}(p-2)\leq Q+O(P),$$ where $f(h,r)$ abbreviates $$f(h,r):=1-\frac{r}{h}\left\{ \frac{h}{r}\right\}\left( 1 - \left\{ \frac{h}{r}\right\}\right).$$ It is straightforward that $$f(h,r)\leq\min\left(1,\frac{h}{r}\right)\leq\prod_{\substack{p\mid r\\p>h}}\frac{h}{p},$$ hence hence it suffices that $$\frac{1}{\phi(q)}\left(\prod_{\substack{p\mid q\\p\leq h}}(p-2+1)\right) \left(\prod_{\substack{p\mid q\\p>h}}\left(p-2+\frac{h}{p}\right)\right) \leq Q+O(P).$$ Equivalently, $$\prod_{\substack{p\mid q\\p>h}}\left(1-\frac{1}{p-1}+\frac{h}{p(p-1)}\right)\leq Q+O(P).$$ Now the left hand side equals $$Q\prod_{\substack{p\mid q\\p>h}}e^{O(h/p^2)}=Q\left(1+\frac{O(1)}{\log h}\right)=Q+O\left(\frac{Q}{\log h}\right)=Q+O(P),$$ and we are done. In the last step, we used that $$Q=P\prod_{\substack{p\mid q\\p\leq h}}\left(1-\frac{1}{p}\right)^{-1}=O(P\log h).$$

  • $\begingroup$ Thanks! If I haven't misunderstood anything, you prove the second inequality, $M_2(q;h)\leq qhP$. What I was interested in was the other inequality. Sorry if I caused some confusion. I have altered my question to be clearer. You got any thoughts on the question as it's now phrased? $\endgroup$
    – user45947
    Apr 30, 2020 at 15:50
  • $\begingroup$ @user45947: I included a proof of the lower bound. It was rather nontrivial, it made me think for a while! $\endgroup$
    – GH from MO
    May 1, 2020 at 0:58
  • 1
    $\begingroup$ Thanks for the effort! I've accepted the answer. $\endgroup$
    – user45947
    May 1, 2020 at 8:14

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.