# What is the asymptotic growth of $\sum_{k=1}^n 2^{\omega_k}$?

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.
• 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)$ – მამუკა ჯიბლაძე Sep 28 '18 at 14:21
• @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. – Greg Martin Sep 28 '18 at 17:16