0
$\begingroup$

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

  • 0
    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.2012-12-31
  • 2
    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.2012-12-31
  • 0
    Yes there is a need to restrict co prime a,b your reasoning is wrong2012-12-31
  • 2
    @Ethan Care to elaborate? Where does $(a,b)\not= 1$ fail?2012-12-31
  • 0
    look at my lower sum, what you are trying to argue is incorrect2012-12-31

1 Answers 1

3

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

  • 0
    Did you use dirichlets theorem here?2012-12-31
  • 2
    @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.2012-12-31
  • 0
    Eric could you derive this result?2012-12-31
  • 1
    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}.$2012-12-31