Improving the error term in a classic sieving problem

Question

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.

Answer 1

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

Answer 2

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