Question: Let $\omega_k$ be the number of distinct prime divisors of k. What is the asymptotic growth of $C_n := \sum_{k=1}^n 2^{\omega_k}$?

Thank you for considering this elementary question. Below I give some motivation for this problem and some of my progress.

Motivation: There are a couple. The first is purely number theoretic. Note that because $2^{\omega_k} = \sum_{d | k} |\mu(d)|$, we have $C_n = \sum_{k=1}^n \sum_{d|k} |\mu(d)|,$ and thus $C_n$ is the asymptotic growth of absolute values of the Möbius function (in other contexts this relates to the Prime Number Theorem, see here).

The second motivation comes from geometric group theory. The commensurability index of $A, B \leq G$ (all groups) is $[A : A \cap B][B: A \cap B]$. The full commensurability growth function assigned to a pair $A \leq B$ is defined to be $$ C_n(A,B) = \# \{ \Delta \leq B : c(\Delta, A) \leq n \}. $$ This is a generalization of the subgroup growth function to pairs and it can be infinite in natural settings. The question above is the case $G(\mathbb{Z}) = \mathbb{Z} \leq \mathbb{R} = G(\mathbb{R})$ of the following

Problem: Compute the full commensurability growth function for the pairs $G(\mathbb{Z}) \leq G(\mathbb{R})$ where $G$ is a unipotent linear algebraic group.

Some progress: Write $f \preceq g$ if there exists $C > 0$ such that $f(n) \leq C g(C n)$. In Proposition .3, it is shown that $n (\log(n))^{\log(2)} \leq C_n \preceq n(\log(n))$.


As you observe, $$C_n=\sum_{k=1}^n\sum_{d\mid k}|\mu(d)|=\sum_{k=1}^n\sum_{d\mid k\text{ squarefree}}1.$$ Exchanging the order of summation, $$C_n=\sum_{d\leq n\text{ squarefree}}\sum_{d\mid k\leq n}1=\sum_{d\leq n\text{ squarefree}}\left\lfloor\frac{n}{d}\right\rfloor=n\sum_{d\leq n\text{ squarefree}}\frac{1}{d}+O(n).$$ Now, the squarefree numbers have density $\frac{1}{\zeta(2)}=\frac{6}{\pi^2}$, so by summation by parts it's easy to find $\sum_{d\leq n\text{ squarefree}}\frac{1}{d}\sim\frac{1}{\zeta(2)}\log n$, hence giving $C_n\sim\frac{1}{\zeta(2)}n\log n$. You should be able to get an $O(n)$ bound on the error this way, and using the hyperbola method you should get some more precise estimates.

  • 5
    $\begingroup$ OEIS also mentions Merten's theorem (1874): $\frac n{\zeta(2)}\left(\log n + 2\gamma - 1 - 2\frac{\zeta'(2)}{\zeta(2)}\right) + O(\sqrt n\log n)$ $\endgroup$ – მამუკა ჯიბლაძე Sep 28 '18 at 14:21
  • $\begingroup$ Thank you very much for your answer! I was so close ... $\endgroup$ – Khalid Bou-Rabee Sep 28 '18 at 14:52
  • 1
    $\begingroup$ Alternatively, break the sum up into k subsums and count the numbers less than n with k distinct prime factors. Landau did this, with a logarithmically shrinking numerator and (k-1)! in the denominator, so one can get a good approximation with about k=loglog n many terms. Gerhard "Go Where The Mass Is" Paseman, 2018.09.28. $\endgroup$ – Gerhard Paseman Sep 28 '18 at 15:53
  • 2
    $\begingroup$ @GerhardPaseman: one needs to be careful with heuristics here, because $2^x$ grows so fast that the relatively few integers with substantially more than $\log\log n$ prime factors contribute more to the sum of $2^{\omega(n)}$ than the density-1 set of integers with around $\log\log n$ prime factors. (Note that the contribution of the latter is about $x\cdot 2^{\log\log x} = x(\log x)^{\log 2}$, which is less than the main term for the sum.) The same thing happens with the divisor function: most of the mass in the sum comes from integers with about $\frac1{\log2}\log\log x$ prime factors. $\endgroup$ – Greg Martin Sep 28 '18 at 17:16
  • $\begingroup$ @Greg, what do you think would be a good cutoff for this sum then? (k=(loglog x)^2), maybe? Gerhard "Is Willing To Add More" Paseman, 2018.09.28. $\endgroup$ – Gerhard Paseman Sep 28 '18 at 17:20

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.