Skip to main content
7 of 8
deleted 1518 characters in body
Will Sawin
  • 148.4k
  • 9
  • 324
  • 563

The answer to both questions is negative.

Let $\omega(n)$ be the number of prime factors of $n$, let $$a_n = \begin{cases} 1 & \omega(n) < \log \log N \\ -1 & \omega(n) > \log \log N \end{cases}. $$

By Erdős–Kac, $\frac{1}{N} \sum_{n \leq N} a_n = o(1) $.

On the other hand, by Erdős–Kac applied to $n/q$, $$ \frac{1}{N/q} \sum_{n \leq N \colon q\mid n} a_n = o(1) + 2 \int_0^{ \frac{\omega(q)}{\sqrt{\log \log N}}} \frac{1}{\sqrt{2\pi}}e^{ -x^2/2} dx $$

So the difference $\frac{1}{N/q} \sum_{n \leq N \colon q\mid n} a_n - \frac{1}{N} \sum_{n\leq N }a_n $ is at least $\epsilon $ as long as $$\frac{\omega(q)}{\sqrt{\log \log N}} > \sqrt{2} \operatorname{erf}^{-1} (\epsilon) = \sqrt{\frac{\pi}{2}} \epsilon + O(\epsilon^2)$$

So it is possible for the discrepancy to be larger than $\epsilon$ for all $q\leq N$ with more than $(1+o(1) )\sqrt{\frac{\pi}{2}} \epsilon \sqrt{\log \log N}$ prime factors.

The number of $q\leq N$ where the discrepancy is small is apparently $ e^{ (1+o(1) )\frac{1}{2} \sqrt{\frac{\pi}{2}} \epsilon \sqrt{\log \log N } \log \log \log N}$.

Will Sawin
  • 148.4k
  • 9
  • 324
  • 563