4
$\begingroup$

What is the asymptotic number of square-free numbers less than $x$ with exactly $k$ prime divisors?

$\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$
    – Lucia
    Mar 20, 2014 at 21:34
  • 2
    $\begingroup$ @Lucia: I think you should make your comment an answer. $\endgroup$
    – GH from MO
    Mar 20, 2014 at 21:40
  • $\begingroup$ @IstvánKovács, see the comment of Greg Martin after yours, then mine... $\endgroup$
    – Will Jagy
    Mar 21, 2014 at 2:07

2 Answers 2

5
$\begingroup$

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

$\endgroup$
2
2
$\begingroup$

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

$\endgroup$
4
  • $\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$ 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$
    – Will Jagy
    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$ 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$
    – Will Jagy
    Mar 21, 2014 at 1:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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