# "On the distribution of reduced residues" by Montgomery and Vaughan – missing careful argument wanted

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?

### Background

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 ) 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. 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).$$
• 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? Apr 30, 2020 at 15:50