14
$\begingroup$

I want to prove that the set of natural numbers n having a prime divisor greater than $\sqrt{n}$ is positive.

I have a heuristic argument that this density should be $\log 2$, which is approximately 0.7, but I am not sure how this could be converted to a formal argument.

For any x, the probability that x is prime is approximately $1/ \log x$ (By the prime number theorem). Further, the probability that n is a multiple of x is approximately $1/x$. These are "independent" so the probability that n is a multiple of x and x is prime is approximately $1/x\log x$.

We know that n can have at most one prime divisor greater than $\sqrt{n}$, so the probability that n has a prime divisor greater than $\sqrt{n}$ can be approximated by the integral:

$$\int_{\sqrt{n}}^n \frac{dx}{x \log x} = [\log (\log x)]_{\sqrt{n}}^n = \log 2$$

Can this be made precise in terms of densities? How would the error terms be handled? Has this or a similar result already been proved?

ADDED LATER: The proofs below resolve this question, and they also seem to show that the density of numbers n with a prime divisor greater than $n^\alpha$ is $-\log \alpha$ for $1 > \alpha \ge 1/2$. My question: is the result also valid for $0 < \alpha < 1/2$? For such $\alpha$, we could have more than one prime divisor, so the simple counting above doesn't work; we need to use a sieve that subtracts the multiple contributions occurring from numbers that have more than one such prime divisor. My guess would be that asymptotically, this wouldn't matter, but I'm not sure how to formally show this.

$\endgroup$

6 Answers 6

9
$\begingroup$

This is actually fairly straightforward, and reduces to the fact that

$ \sum_{p \text{prime}} \frac 1p = \log \log x + C + o(1)$

for some constant $C$. To see how to apply this to the original problem, let $p$ denote the largest prime divisor of $n$, and write $n = pz$. Then $p \ge \sqrt{n}$ if and only if $z \le p$. Thus the number of such $n \le x$ is

$\sum_{p \le x} \sum_{z \le \min(p,x/p)} 1$ which breaks up into a main term

$\sum_{p \ge \sqrt{x}} \lfloor \frac xp \rfloor$ plus a smaller term $\sum_{p \le \sqrt{x}} p \le \sqrt{x} \pi(\sqrt x) = o(x)$, which is therefore negligible compared with the first term. The main term is taken care of by the equation I cited at the beginning, using the fact that $\pi(n) = o(n)$ and finally that

$\log \log x - \log \log \sqrt x = \log 2$.

$\endgroup$
7
  • $\begingroup$ I don't quite understand. What would be the precise statement in density terms? What density are we using? I'd appreciate a little more detail, thanks. $\endgroup$
    – Vipul Naik
    Feb 8, 2010 at 17:31
  • 1
    $\begingroup$ You're correct in that you're implicitly using the prime number theorem which says that the density of primes is $\le x$ is $1/\log x$. However, you don't need anything that strong, as the formula for the sum of the reciprocals of the primes is much easier to prove than the PNT. $\endgroup$ Feb 8, 2010 at 17:34
  • 1
    $\begingroup$ The density of integer $n \le x$ whose largest prime factor is $> \sqrt{n}$ is $\sum_{p > \sqrt{x}} \lfloor \frac xp \rfloor/x$, so that up to lower order terms you can "cancel the $x$". $\endgroup$ Feb 8, 2010 at 17:36
  • $\begingroup$ Victor Miller is right. The weakest bounds you can get away with is his statement about sum 1/p and the bound pi(n) = o(n). You need the latter in order to switch \lfloor n/p \rfloor with n/p + O(1). $\endgroup$ Feb 8, 2010 at 17:37
  • 1
    $\begingroup$ @DS: Thanks. I was concerned that I might be viewed as too cavalier in slightly changing the problem. However the differences between allowing the larges prime factor to be bigger than $\sqrt{x}$ and $\sqrt{n}$ is actually negligible (i.e. only affects the remainder). $\endgroup$ Feb 8, 2010 at 17:44
4
$\begingroup$

If I recall correctly, this was an exercise in Mathematics for the Analysis of Algorithms. I don't have access to a library right now, so I can't check that.

In any case, here is a proof. Fix a positive integer $N$. We will be counting the number of $n$ in $\{ 1,2, \ldots, N \}$ such that the largest prime divisor of $n$ is $\leq \sqrt{n}$.

We can break this count into two parts: (1) Those $n$ which are divisible by $p$ where $p \leq \sqrt{N}$ and $n \leq p^2$ and (2) Those $n$ which are divisible by $p > \sqrt{n}$.

Case (1) is easier. We are looking at $\sum_{p \leq \sqrt{N}} p = \int_{t=0}^{\sqrt{N}} t d \pi(t)$. (This is a Riemann-Stieltjes integral.) Integrating by parts, this is $\int_{0}^{\sqrt{N}} \pi(u) du + O( \sqrt{N} \ \pi(\sqrt{N}))$. Since $\pi(u) = O(u / \log u)$ as $u \to \infty$, this integral is $O \left( \int^{\sqrt{N}} \pi(u) du \right) = O\left(\sqrt{N} \frac{\sqrt{N}}{\log N} \right) = O(N/\log N)$, and the second term is also $O(N/\log N)$. So case 1 contributes density zero.

Case (2) is the same idea — integrate by parts and use the prime number theorem — but the details are messier because we need a better bound.

We are trying to compute $$\sum_{\sqrt{N} \leq p \leq N} \lfloor \frac{N}{p} \rfloor = \int_{\sqrt{N}}^N \lfloor \frac{N}{t} \rfloor d\pi(t) = \int_{\sqrt{N}}^N \left( \frac{N}{t} + O(1) \right) d\pi(t).$$

The error term is $O(\pi(N)) = N/\log N$ so, again, it doesn't effect the density. Integrating the main term by parts, we have $$\int_{\sqrt{N}}^N \left( \frac{\partial}{\partial t} \ \frac{N}{t} \right) \pi(t) dt +O(N/\log N).$$ Where the error term is $\left( N/t \pi(t) \right)|^N_{\sqrt{N}}$.

Now, $\pi(t) = Li(t) + O(t/(\log t)^K)$ for any $K$, by the prime number theorem, where $Li(t) = \int^t du/\log u$. So the main term is $$\int_{\sqrt{N}}^N \left( \frac{\partial}{\partial t} \ \frac{N}{t} \right) Li(t) dt + O\left( \int^N \frac{N}{t^2} \frac{t}{(\log t)^K} dt \right).$$ The error term is $O \left( N/(\log N)^{K-1} \right)$.

In the main term, integrate by parts, "reversing" our previous integration by parts. We get $$\int_{\sqrt{N}}^N \frac{N}{t} \frac{dt}{\log t} + O(N/\log N).$$

Focusing on the main term once more, we have $$N \int_{\sqrt{N}}^N \frac{dt}{t \log t} = N \log 2.$$

Putting all of our error terms together, the number of integers with large prime factors is $$N \log 2 + O(N/\log N).$$


In summary, integration by parts, the Prime Number Theorem, and aggressive pruning of error terms.

As I recall, the follow-up exercise in Mathematics of the Analysis of Algorithms is to obtain a formula of the form $$N \log 2 + c N/\log N + O(N/(\log N)^2).$$ That's a hard exercise! If you want to learn a lot about asymptotic technique, I recommend it.

$\endgroup$
4
  • 1
    $\begingroup$ Now that I see Victor Miller's answer, I see that I could have taken a bit of a shorter route, by quoting the asymptotic for sum 1/p rather than rederiving it and using weaker bounds in various places. But I'm going to leave my answer as is, to show how to brute force your way through this sort of thing. $\endgroup$ Feb 8, 2010 at 17:42
  • $\begingroup$ Is there a typo in your second para where you say " ... such that the largest prime divisor of $n$ is $\leq n$"? $\endgroup$
    – Vipul Naik
    Feb 8, 2010 at 17:52
  • $\begingroup$ Yup, that's a typo. Fixed now, thanks. $\endgroup$ Feb 8, 2010 at 18:37
  • 1
    $\begingroup$ This is Problem 2 in "Final Exam I" in Appendix D of my (third, 1990) edition. $\endgroup$ Feb 8, 2010 at 20:25
3
$\begingroup$

As you suspected, when the largest prime factor of $n$ is smaller than $\sqrt{n}$ then things get more complicated. However, there has been a lot done about this. One of the more interesting is in http://www.google.com/url?sa=t&source=web&ct=res&cd=2&ved=0CA0QFjAB&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.108.7037%26rep%3Drep1%26type%3Dpdf&ei=HW1wS5qVKoze8Qbis7H8BQ&usg=AFQjCNGtuzzG1YhO-6m_ySNG3iw1RX-0ig&sig2=OftdPThF1PkbArX_-1cDRw

by Donnelly and Grimmet.

This also leads to the study of "smooth" numbers: an integer is y-smooth, if all of its prime factors are $\le y$. A good survey of that is in http://www.dms.umontreal.ca/~andrew/PDF/msrire.pdf

$\endgroup$
3
$\begingroup$

The expected number of prime divisors greater than $n^{\alpha}$ is, in fact, $-\log \alpha$. For $\alpha \ge 1/2$ this reduces to the probability of having one large divisor, since $n$ can't have two divisors greater than $n^{1/2}$. For $1/3 < \alpha < 1/2$ the situation is more complicated, since one has to consider the probability that there are two "large" (larger than $n^\alpha$) divisors; for $1/4 < \alpha < 1/3$ there could even be three large divisors, and so on.

There's an analogy between the cycle structure of permutations and the prime factorizations of integers; in particular your claim that the expected number of prime divisors of $n$ greater than $n^{\alpha}$ is $-\log \alpha$ is equivalent to the claim that the expected number of cycles of a permutation on $n$ elements which are longer than $\alpha n$ is $-\log \alpha$. See Andrew Granville's preprint The anatomy of integers and permutations.

Keeping this in mind, I've written up some part of the analogous sieving argument for permutations in a preprint, The number of cycles of specified normalized length in permutations (arXiv:0909.2909). I'm not sure if it's been written down for prime factorizations -- the literature is a bit of a blur in my mind -- but there's a good chance it has been.

$\endgroup$
1
$\begingroup$

Your "added later" question can be answered by reading these two Wikipedia articles. The integers you are interested in are commonly called "smooth numbers." Actually you're counting the non-smooth integers but that is a trivial change.

$\endgroup$
0
$\begingroup$

I found (via Wikipedia) this paper by V Ramaswami that address the question. It seems that the function isn't quite log; rather it is the Dickman-de Bruijn function, but there's still a positive density result.

$\endgroup$

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.