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.

  • $\begingroup$ Possible duplicate of Bound the error in estimating a relative totient function $\endgroup$ – Alexey Ustinov Oct 23 '16 at 3:18
  • $\begingroup$ 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. $\endgroup$ – Chao Xu Oct 23 '16 at 3:52
  • $\begingroup$ Maybe it will help if you say why you need such a bound ? $\endgroup$ – reuns Oct 23 '16 at 4:11
  • $\begingroup$ Did you try to apply inclusion-exclusion principle which gives the error term $2^{\omega(n)}$? $\endgroup$ – 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.


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.