Skip to main content
1 of 3
Ofir Gorodetsky
  • 14.6k
  • 1
  • 66
  • 79

I'll show your prediction is off by a factor of $\phi(q)$; some technical details are left to you.

H. Halberstam studied related problems in "On the distribution of additive number-theoretic functions. III.", J. Lond. Math. Soc. 31, 14-27 (1956). Given an irreducible polynomial $f$, he proved that $$\sum_{p \le n}\omega(f(p)) \sim \frac{n}{\log n} \log \log n$$ as $n \to \infty$. It is not hard to adapt this result to $\Omega$, which counts prime factors with multiplicities.

This relates to your problem because $$\Omega(Q_n) =\sum_{p\le p_n} \Omega( f_q(p))$$ where $f_q(n) = n^q-1$. While $f_q$ is not irreducible, it factors into $\phi(q)$ (irreducible) cyclotomic polynomials: $f_q(n) = \prod_{d \mid q} \phi_d(n)$. Thus Halberstam's work essentially shows $$\Omega(Q_n) \sim \phi(q) \frac{p_n}{\log p_n}\log \log p_n,$$ while $$\log \log Q_n \sim \frac{p_n}{\log p_n} \log \log p_n.$$ Since $\Omega(Q_n)-\omega(Q_n)$ can be shown to be small, this shows that your conjecture is off by a factor of $\phi(q)$.

Informally, you are missing the facts that $\omega(\prod_{k=1}^{n} \phi_d(p_k))$ behave `independently' for the different $d \mid q$, and each contributes $\log \log \prod_{k=1}^{n} \phi_d(p_k) \sim \log \log Q_n$.

Ofir Gorodetsky
  • 14.6k
  • 1
  • 66
  • 79