I'm new to asking questions on MathOverflow, so forgive me if this question is not the kind of thing to be asked here.

Let $q$ be a positive integer and let $N$ be an integer with $1 \leq N \leq q$. The estimate $$ \sum_{\substack{n= 1\\ (n,q)=1}}^N 1 = N \frac{\phi(q)}{q} + O(2^{\omega(q)}) $$ is a classical and straightforward application of Mobius inversion. The error term can be given explicitly by $$ \sum_{d\mid q} \mu(d) \left\{ \frac{N}{d}\right\}. $$ If $q$ has few distinct prime factors, then the bound $$ \Big|\sum_{d\mid q} \mu(d) \left\{ \frac{N}{d}\right\}\Big| \leq 2^{\omega(q)} $$ is sharp. For instance, if $q=p^k$ for some prime $p$, then $2^{\omega(q)} = O(1)$. Writing $N=Mp+r$, where $0\leq r < p$, gives $$ \sum_{d\mid q} \mu(d) \left\{ \frac{N}{d}\right\} = - \frac{r}{p}, $$ and this can genuinely be size $O(1)$.

On the other hand, I suspect that the bound $2^{\omega(q)}$ is quite wasteful when $q$ has many distinct prime factors. From some numerical calculations ($q \leq 10^6$), I suspect that $$ \tag{1} \Big|\sum_{d\mid q} \mu(d) \left\{ \frac{N}{d}\right\}\Big| \ll \log\log q. $$ If, if for instance, $q$ is the product of the first $k$ primes, then $q \ll (k\log k)^k$, and so $\log\log q \ll \log k$, whereas $2^{\omega(q)} = 2^k$. Thus my actual question:

Does the estimate (1) hold in general? It might be possible to establish this estimate using sieve methods (via upper and lower bounds on the original sum), but I am not familiar enough with sieve theory to pursue this avenue myself. I have not been able to find any results of this kind in the literature, so I would gladly welcome any ideas and/or references on this topic.


2 Answers 2


In fact there are moduli $q$ with arbitrarily many prime factors where the error term can be shown to be as large as $2^{\omega(q)-2}$. The following construction is due to D.H. Lehmer, The distribution of totatives.

Let $q$ be the product of $k$ distinct prime numbers all of which are $ 3 \pmod 4$, and take $N=q/4$. Then $\frac 12 -\{ N/d\} = \pm 1/4$ depending on whether $q/d$ has an even or odd number of prime factors. Therefore $$ \Big| \sum_{d|q} \mu(d) \{N/d\} \Big| = \Big| \sum_{d|q} \mu(d) (1/2- \{N/d\})\Big| = \frac 14 \sum_{d|q} |\mu(d)| = \frac 14 2^{\omega(q)}. $$

One interesting application of this idea (which is how I know it) is Montgomery's work on the error term in the counting function of $\phi(n)$: see Fluctuations in the mean ....


Let $p_1,\dots,p_k$ be the first $k$ primes. Let $q = p_1\dots p_k$. By CRT there's some $m \ge 1$ so that $m+j \equiv 0 \pmod{p_j}$ for $1 \le j \le k$. Then $$\sum_{\substack{n=1 \\ (n,q)=1}}^m 1 = \sum_{\substack{n=1 \\ (n,q) = 1}}^{m+k} 1,$$ while $$\left|(m+k)\frac{\phi(q)}{q}-m\frac{\phi(q)}{q}\right| = k\frac{\phi(q)}{q}.$$ So the error term at $m$ or at $m+k$ is at least $\frac{1}{2}k\frac{\phi(q)}{q}$, which is $\frac{1}{2}k\prod_{j=1}^k (1-\frac{1}{p_j})$, which is at least $ck/\log k$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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