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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .