# Evaluating the sum of $\omega(n)$ in an arithmetic progression [closed]

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

-

## closed as not a real question by Jasper Loy, Asaf Karagila, Austin Mohr, Fabian, Alexander Gruber♦Dec 31 '12 at 8:46

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question.

On MSE, try to avoid wording questions in the form "I can prove this, is it known?" It is generally preferred when people ask either for a reference request, or how to solve the problem. –  Eric Naslund Dec 31 '12 at 6:46
There's no need to restrict to coprime $a,b$, since $\omega(n) \le \omega(nd) \le \omega(n)+\omega(d)$. A common factor of $d$ thus affects each term by at most a constant (depending on $d$), and that's negligible compared to the average value $\log \log n$ in the denominator. –  Erick Wong Dec 31 '12 at 6:53
Yes there is a need to restrict co prime a,b your reasoning is wrong –  Ethan Dec 31 '12 at 7:01
@Ethan Care to elaborate? Where does $(a,b)\not= 1$ fail? –  Alexander Gruber Dec 31 '12 at 8:46
look at my lower sum, what you are trying to argue is incorrect –  Ethan Dec 31 '12 at 9:13

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.$$

-
Did you use dirichlets theorem here? –  Ethan Dec 31 '12 at 7:03
@Ethan: I did not, I used only Merten's estimate, that $$\sum_{p\leq x}\frac{1}{p}=\log \log x+B_1+O\left(\frac{x}{\log x}\right).$$ Note that if you wanted to prove something similar and evaluate the average of $\omega_{q,a}(n)$ which I define to be the number of distinct prime factors $p$ dividing $n$ with $p\equiv a \pmod{q}$, then you would need some kind of result regarding primes in arithmetic progressions, such as a form of Mertens estimate for arithmetic progressions. –  Eric Naslund Dec 31 '12 at 7:09
Eric could you derive this result? –  Ethan Dec 31 '12 at 7:10
For Merten's Theorem in arithmetic progressions, there is a paper by Languasco and Zaccagnini. To derive what I said about $\omega_{q,a}(n)$, it suffices show that $$\sum_{n\leq x}\omega_{q,a}(n)=\sum_{\begin{array}{c} p\leq x\\ p\equiv a\ (q) \end{array}}\left[\frac{x}{p}\right].$$ From here, we find that $$\sum_{n\leq x}\omega_{q,a}(n)=\frac{x}{\phi(q)}\log\log x+C(q,a)x+O\left(\frac{x}{\log x}\right)$$ uniformely for $q\leq\left(\log x\right)^{A}.$ –  Eric Naslund Dec 31 '12 at 7:19