# Bounds for relative totient function for small values

Define $\phi(n,x)= \sum_{m\leq x,\gcd(m,n)=1} 1$, the number of elements in the interval $[1,x]$ that is relatively prime to $n$. $\omega(n)$ is the number of distinct prime factors of $n$.

It's not difficult to show that $\phi(n,x) \geq x \phi(n)/n - 2^{\omega(n)}$ (see this question). This shows for large $x$, say $x\geq n^\frac{1}{\log \log n}$, $\phi(n,x)$ is essentially $x\phi(n)/n$.

Are there better bounds known for smaller values of $x$, say $x=o(2^{\omega(n)})$? The bound is negative for $x$ in those values.

Even the naive bound $\phi(n,x)\geq 1+\pi(x)-\omega(n)$ performs better when $x$ is small.

• Possible duplicate of Bound the error in estimating a relative totient function – Alexey Ustinov Oct 23 '16 at 3:18
• It's not the same, this problem asks for the behavior for very small $x$ compared to $n$. I have made an update to reflect that. – Chao Xu Oct 23 '16 at 3:52
• Maybe it will help if you say why you need such a bound ? – reuns Oct 23 '16 at 4:11
• Did you try to apply inclusion-exclusion principle which gives the error term $2^{\omega(n)}$? – Alexey Ustinov Oct 23 '16 at 4:16

The fundamental lemma of sieve theory will give you good results here. Put $n_0 = \prod_{p|n, p< (\log n)^2} p$, so that $n_0$ is the product of the small prime factors of $n$. The fundamental lemma gives $$\Big| \sum_{\substack{m \le x\\ (m,n_0)=1}} 1 - \frac{\phi(n_0)}{n_0} x \Big| \ll u^{-u(1+o(1))} x \frac{\phi(n_0)}{n_0},$$ with $x= (\log n)^{2u}$ (and $u \ge 2$ say).
Next note that there cannot be too many primes dividing $n$ larger than $(\log n)^2$, and these make a negligible contribution: $$\Big| \sum_{\substack{m\le x \\ (m,n)=1} }1 - \sum_{\substack{m\le x \\ (m,n_0)=1} }1 \Big| \le \sum_{\substack { p|n \\ p>(\log n)^2}} \frac xp = o\Big(\frac{x}{\log n}\Big).$$
Thus it follows that you can get a good asymptotic formula whenever $x$ is larger than $(\log n)^{2u}$ for any slowly growing quantity $u$. Consult any standard text on analytic number theory (for example Montgomery and Vaughan) for the fundamental lemma.