# Improving the error term in a classic sieving problem

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.

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$$.