nt.number theory - Density of numbers having large prime divisors (formalizing heuristic probability argument)

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) = Oleft(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 dpi(t) = int_{sqrt{N}}^N left( frac{N}{t} + O(1) right) dpi(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 + Oleft( 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.

• Next matrices - Linear Algebra Problems?
• Previous st.statistics - How would you compute that "average" ?