Evaluating the sum of $\omega(n)$ in an arithmetic progression

866 Views Asked by At

Let $\omega(k)$ count how many distinct prime factors k has,

Then I can prove that for any coprime integers $a,b$ $$\lim_{n\to\infty}\frac{\sum_{k=2}^n\omega(ak+b)}{\sum_{k=2}^n\omega(k)}=1$$

Does anyone think this is a deep result?

Its essentially saying on average all linear polynomials with co prime coefficients

Have around the same number of prime factors

1

There are 1 best solutions below

4
On BEST ANSWER

This type of result, and the tools needed to prove it, would usually be discussed in a graduate level Analytic Number Theory text. My personal preference is Montgomery and Vaughn's "Multiplicative Number Theory I. Classical Theory."

Here is another way to see why this result is true. Lets examine the sum $$\sum_{\begin{array}{c} n\leq x\\ n\equiv a\ (q) \end{array}}\omega(n).$$ Since $\omega(n)=\sum_{p|n}1,$ the above becomes $$\sum_{\begin{array}{c} n\leq x\\ n\equiv a\ (q) \end{array}}\sum_{p|n}1=\sum_{p\leq x}\sum_{\begin{array}{c} n\leq x,\ p|n\\ n\equiv a\ (q) \end{array}}1.$$ This equals

$$\sum_{\begin{array}{c} p\leq x\\ p\nmid q \end{array}}\sum_{\begin{array}{c} n\leq\frac{x}{p}\\ n\equiv p^{-1}a\ (q) \end{array}}1=\sum_{\begin{array}{c} p\leq x\\ p\nmid q \end{array}}\left(\frac{x}{pq}+O(1)\right) $$

$$=\frac{x}{q}\log\log x+\frac{B_{1}x}{q}+O\left(\frac{x}{\log x}\right),$$ where $B_1$ is Mertens constant. From here, we can recover your asymptotic since $\log \log \left(\frac{x}{q}\right)\sim \log \log x$, and so $$\sum_{n\leq x }\omega(nq+a)\sim\sum_{n\leq x }\omega(n)\sim x \log \log x.$$