Is there a nice closed-form expression for, or asymptotic formula for the number of numbers below $n$ with a square number of distinct prime factors?


As a student who studies mathematics in my spare time, I encountered some questions asking about the number of numbers below certain limits that adhere to certain elementary factor properties and later was thinking about it, when it occurred to me that there were many, seemingly simple or natural, questions to ask about "counting functions" that nothing I know can help with...

So, more generally, on top of an answer to the above, are there nice toolkits or pieces of machinery that can, with some property, tell me the number of numbers below $n$ with that property? (even if this toolkit only works for a specific subset of properties, I would be interested)

  • 2
    $\begingroup$ 1 is a square number, right? For now let's notate your function, which operates on positive real numbers, as $\chi_{\omega^2}(n)$ (someone will think of something better later). Then $\chi_{\omega^2}(n) > \pi(n)$, where $\pi(n)$ is the prime counting function. Since 1 has zero distinct prime factors and $0 = 0^2$, then $\chi_{\omega^2}(1) = 1$. $\endgroup$ May 20 '18 at 18:18
  • $\begingroup$ Have you looked in the OEIS? oeis.org/A065515 might be what you're looking for. $\endgroup$ May 20 '18 at 18:50
  • $\begingroup$ @RobertSoupe: Sorry for not replying till now. A065515 officially says that it is the number of prime powers below $n$, which seems quite different from $\chi_{\omega^2}(n)$... $\endgroup$ May 24 '18 at 13:32
  • $\begingroup$ That's what I thought and that could still be the case. But most of the time, when an OEIS search gives me a result that matches this much, it turns out to be the right result after all. Try to find the smallest $n$ for which the OEIS entry and your function differ. $\endgroup$ May 24 '18 at 15:01
  • 5
    $\begingroup$ @RobertSoupe: This is because under 210(=$2\times3\times5\times7$), all numbers which have a square number of factors are prime powers (i.e. have 1 prime factor). 210 is the smallest number with a square number of distinct primes factors that is not 1, and after it these two sequences cease to be equivalent. $\endgroup$ May 24 '18 at 15:41

Let $\pi_k(n)$ be the number of integers $\le n$ with exactly $k$ distinct prime factors. You are looking for $\sum_{m=1}^{\infty}\pi_{m^2}(n)=\pi(n)+\pi_4(n)+\pi_9(n)+\ldots$. Hardy and Ramanujan proved the upper bound $$ \pi_k(n) < c(n/\log n) \cdot (\log\log n + d)^{k-1}/(k-1)!$$ for some constants $c$ and $d$, and Erdös and Pillai (independently) proved the lower bound $$ \pi_k(n) > c'(n/\log n) \cdot (\log\log n)^{k-1}/(k-1)! $$ for some constant $c'$. So, putting things together, you have $$ \frac{c'(\log\log n)^{k-1}}{(k-1)!}<\frac{\pi_{k}(n)}{n/\log n}<\frac{c(\log\log n+d)^{k-1}}{(k-1)!}. $$ Taking $g(z)=\sum_{m=1}^{\infty}\frac{z^{m^2-1}}{(m^2-1)!}$, you have $$ c'g(\log \log n)<\frac{\sum_{m=1}^{\infty}\pi_{m^2}(n)}{n/\log n}<cg(\log\log n + d). $$ Update:

After spending some time looking into the asymptotic growth of functions like $g(z)$, analytic with every derivative at the origin equalling zero or one... which seems interesting and may be worth its own question... I think that $g(z)$ is $\Theta(e^z / \sqrt{z})$ for large $z$. If that's correct, then in fact $$ \sum_{m=1}^{\infty}\pi_{m^2}(n)\in\Theta\left(\frac{n}{\sqrt{\log\log n}}\right). $$

  • $\begingroup$ The last inequalities with constants $c'$ and $c$? $\endgroup$ May 25 '18 at 1:06
  • 1
    $\begingroup$ Also, summed over $k$. $\endgroup$ May 25 '18 at 1:07
  • $\begingroup$ Thanks, fixed it... $\endgroup$
    – mjqxxxx
    May 25 '18 at 14:20
  • 1
    $\begingroup$ You should be a bit careful with how you state the lower bound: for very large $k$ it certainly fails (the LHS is $0$) $\endgroup$
    – fedja
    May 27 '18 at 4:04
  • 1
    $\begingroup$ Heuristically one might guess at the asymptotic $n/\sqrt{\log \log n}$ from the fact that $\omega(n)$ is "normally distributed" around $\log \log n$, and a "random integer" of the same size as $\log \log n$ is square with "probability" $\sqrt{\log \log n}$. $\endgroup$
    – Erick Wong
    May 31 '18 at 17:27

Let $\omega(n)$ be the number of distinct prime factors of $n$. Distribution of the numbers satisfying $\omega(n)=k$ is well-known. The method is discussed in Montgomery & Vaughan 'Multiplicative Number Theory' volume 1, chapter 7, exercise 3. Denote by $$ F(s,z)=\prod_p \left(1+\frac z{p^s-1}\right)\left(1-\frac1{p^s}\right)^z. $$ The product is taken over prime numbers. This product converges for $\Re(s)=\sigma>1/2$, uniformly for $|z|\leq R<\infty$.

Let $\rho_k(x)$ be the number of $n\leq x$ for which $\omega(n)=k$. Then $$ \rho_k(x)=G\left(\frac{k-1}{\log\log x}\right)\frac{x(\log\log x)^{k-1}}{(k-1)!\log x}\left(1+O_R\left(\frac k{(\log\log x)^2}\right)\right) $$ uniformly for $1\le k\le R\log\log x$. Here, $G(z)=F(1,z)/\Gamma(z+1)$, and $G(0)=G(1)=1$. Also, $G(z)\asymp 1$ on $0\leq z\leq R$.

It is okay to have $R=e+1$ since we have the number $B(x,R)$ for which $\omega(n)\geq R\log\log x$ is $$ B(x,R)=O\left( x(\log x)^{R-1-R\log R} \right) $$ and $R-1-R\log R<-1$.

Then it remains summing over the ones with $k=l^2$. Let $y=\log\log x$.

First, note by Stirling's formula that $$ \frac{y^{l^2-1}}{(l^2-1)!} \sim \frac1{\sqrt{2\pi(l^2-1)}}\left( \frac{ey}{l^2-1}\right)^{l^2-1}\sim \frac1{l\sqrt{2\pi} }\left( \frac{ey}{l^2-1}\right)^{l^2-1}. $$ Let $n=l^2-1$. We have $$ \left( \frac{ey}{l^2-1}\right)^{l^2-1}=\exp\left(n\log\left(\frac{ey}n \right) \right) =\exp\left( n \left(1+\log(\frac yn -1 +1) \right)\right). $$ We sum over $\sqrt{1+0.6y}\leq l \leq \sqrt{1+Ry}$, so that $-1<\frac1R -1 \leq \frac yn-1\leq \frac1{0.6}-1<1$. Over $\frac1R-1\leq x\leq \frac1{0.6}-1$, we have $$ \log(1+x)\leq x - \frac16 x^2. $$ This gives $$ \exp\left( n \left(1+\log(\frac yn -1 +1) \right)\right)\leq \exp\left(n(1+\frac yn -1 - \frac16 (\frac yn -1)^2)\right) $$ $$ =e^y\exp\left(-\frac16 n(\frac yn -1)^2 \right)=e^y \exp\left(-\frac16 (\frac y{\sqrt n} - \sqrt n)^2 \right). $$ Thus, $$ \sum_{\substack{{\sqrt{1+0.6y}\leq l \leq \sqrt{1+Ry}}\\{n=l^2-1}}}\exp\left(-\frac16 (\frac y{\sqrt n} - \sqrt n)^2 \right)\asymp 1. \ \ \ \ (*) $$ Then $$ \sum_{\sqrt{1+0.6y}\leq l \leq \sqrt{1+Ry}} \frac1{l\sqrt{2\pi} }\left( \frac{ey}{l^2-1}\right)^{l^2-1}\asymp \frac{e^y}{\sqrt y}. $$ Hence $$ \sum_{\sqrt{1+0.6y}\leq l \leq \sqrt{1+Ry}} \frac{y^{l^2-1}}{(l^2-1)!} \asymp \frac{e^y}{\sqrt y}.$$

We sum over the remaining $l$ with $\asymp \log y$ intervals of the type $[\sqrt{1+\alpha^{t+1} y},\sqrt{1+\alpha^t y}]$ with $0<\alpha<1$ and varying $t$.

By the same method above, we have $$\sum_{\sqrt{1+\alpha^{t+1}y}\leq l \leq \sqrt{1+\alpha^t y}}\frac{y^{l^2-1}}{(l^2-1)!}\ll \frac{e^{\alpha^t y}}{\sqrt{\alpha^t y}}\left(\frac1{\alpha^t}\right)^{\alpha^t y}\ll \exp\left((\alpha - \alpha\log \alpha)y\right). $$ Since $0<\alpha - \alpha\log \alpha <1$, the sum over whole remaining range contribute to $$ \ll (\log y)\exp\left((\alpha - \alpha\log \alpha)y\right) \ll \frac{e^y}{\sqrt y}. $$ Therefore, by combining all estimates, we have $$ \sum_{l\leq \sqrt{1+Ry}} \frac{y^{l^2-1}}{(l^2-1)!}\asymp \frac{e^y}{\sqrt y}. $$ This proves that the conjectured answer by @mjqxxxx is true.

  • $\begingroup$ What does $\asymp$ mean? Sorry if I am amateur at this. $\endgroup$
    – Mr Pie
    Jun 15 '18 at 9:26
  • $\begingroup$ $f(x)\asymp g(x)$ means that there are positive constants $c$ and $C$ such that $c f(x) \leq g(x) \leq Cf(x)$. $\endgroup$ Jun 15 '18 at 10:19
  • $\begingroup$ Ahhh -- much clearer. Thank you :) ..... well, by much clearer, I mean I can read it, but I don't entirely know what any of it means. Looks pretty, though :)) $\endgroup$
    – Mr Pie
    Jun 15 '18 at 10:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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