What is the asymptotic number of square-free numbers less than $x$ with exactly $k$ prime divisors?
$\begingroup$
$\endgroup$
3
-
5$\begingroup$ See Exercise 4 of Section 7.4 of Montgomery and Vaughan's book on Multiplicative number theory. If $k$ is fixed, then the asymptotics are essentially the same as that of just numbers with $k$-prime factors (forgetting squarefree). $\endgroup$– LuciaCommented Mar 20, 2014 at 21:34
-
2$\begingroup$ @Lucia: I think you should make your comment an answer. $\endgroup$– GH from MOCommented Mar 20, 2014 at 21:40
-
$\begingroup$ @IstvánKovács, see the comment of Greg Martin after yours, then mine... $\endgroup$– Will JagyCommented Mar 21, 2014 at 2:07
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
All this is taken from Section 7.4 of Montgomery-Vaughan's Multiplicative Number Theory I. Classical Theory.
Theorem 7.19: The number of integers up to $x$ with exactly $k$ prime divisors counted with multiplicity is $$ \frac{F((k-1)/\log\log x)}{\Gamma(1+(k-1)/\log\log x)} \frac{x(\log\log x)^{k-1}}{(k-1)!\log x} \bigg( 1 + O\bigg( \frac k{(\log\log x)^2} \bigg) \bigg). \tag{$*$} $$ Here $\Gamma$ is the Euler Gamma function, and $$ F(z) = \prod_p \bigg( 1 - \frac zp \bigg)^{-1} \bigg( 1 - \frac1z \bigg)^p. $$ (This is true uniformly for $k\le 1.99\log\log x$, say.) Note that $F(0)=1$, which gives the result Will quoted for fixed $k$. Note also that $F(1)=1$; this is relevant because most integers near $x$ have about $k=\log\log x$ prime factors.
Problem 3: The number of integers with exactly $k$ distinct prime factors is also given by ($*$), except one must change $F$ to $$ F(z) = \prod_p \bigg( 1 + \frac z{p-1} \bigg) \bigg( 1 - \frac1z \bigg)^p. $$ (This is true in a wider range - uniformly for $k\le 1000\log\log x$ or whatever constant you want.) Note that again $F(0)=1$ and $F(1)=1$.
Problem 4: The number of squarefree integers with exactly $k$ distinct prime factors is also given by ($*$), except one must change $F$ to $$ F(z) = \prod_p \bigg( 1 + \frac zp \bigg) \bigg( 1 - \frac1z \bigg)^p. $$ (This is also uniform for $k\le 1000\log\log x$.) Note that again $F(0)=1$, but now $F(1) = 6/\pi^2$.
answered Mar 21, 2014 at 3:36
-
$\begingroup$ Thank you. So, the "most integers near $x$" would be Erdos-Kac. en.wikipedia.org/wiki/Erd%C5%91s-Kac_theorem $\endgroup$ Commented Mar 21, 2014 at 5:39
-
1$\begingroup$ Right, or even the less precise Hardy-Ramanujan theorem. $\endgroup$ Commented Mar 21, 2014 at 7:20
$\begingroup$
$\endgroup$
4
Also Theorem 437, section 22.18 (page 368 in edition 5) of Hardy and Wright. $$ \pi_k(x) \sim \frac{x (\log \log x)^{k-1}}{(k-1)! \log x} $$
answered Mar 20, 2014 at 23:06
-
$\begingroup$ This $\pi_k$ is surely not what we are looking for, since summing up to every $k$ this would yield density one. But the density of square-free integers is just $6/ \pi^2$. $\endgroup$ Commented Mar 21, 2014 at 0:38
-
$\begingroup$ @IstvánKovács, not sure what to tell you; they say the result is the same for $\tau_k(x),$ where $k$ is the exponent sum and there is no longer a restriction to be squarefree. So for that interpretation, a sum of 1 seems correct. Well, I will leave it here, someone will explain the difficulty. I don't have Montgomery and Vaughan. $\endgroup$ Commented Mar 21, 2014 at 1:08
-
2$\begingroup$ The problem with just summing that formula over $k$ is that the error term (hidden in the $\sim$ notation) is not uniform in $k$. In fact, there's a leading function $G(k/\log\log x)$ when $k$ is allowed to vary with $x$; $G(0)=1$, and $G(1)=1$ when counting primes with multiplicity, but $G(1)=\pi^2/6$ when counting distinct primes. It's a bit of a coincidence that the sum works out when counting primes with multiplicity. $\endgroup$ Commented Mar 21, 2014 at 1:14
-
$\begingroup$ @GregMartin, thanks. It seems to me, reading Lucia's comment, that Montgomery and Vaughan are saying exactly the same thing as Hardy and Wright. Maybe you could leave an answer with some detail about the error term, which i guess is the approximate size of H+W's $\tau_k(x) - \pi_k(x).$ $\endgroup$ Commented Mar 21, 2014 at 1:19