Number of smooth numbers less than x

Question

A $p$-smooth number is defined as an integer whose prime factors are all less than or equal to $p$

In the wiki article about smooth numbers it states:

Let $\displaystyle \Psi (x,y)$ denote the number of $y$-smooth integers less than or equal to $x$ (the de Bruijn function). If the smoothness bound $B$ is fixed and small, there is a good estimate for $\displaystyle \Psi (x,B)$: $$\displaystyle \Psi (x,B)\sim \frac {1}{\pi (B)!}\prod _{p\leq B}{\frac {\log x}{\log p}}$$ where $\displaystyle \pi (B)$ denotes the number of primes less than or equal to $B$.

How was this derived? Are there any other good bounds on $\Psi(x,y)$?

Answer 1

Let $S(x, B) $ be the set of $B$ smooth numbers less than or equal than $x$. You notice that $n \in S(x, B) $ iff $\log(n) \le \log(x) $. Writing

$$n = \prod_{p_i \le B} p_i^{\alpha_i} $$

For $p_i$ primes and $\alpha_i$ the exponent with which appears (possibly zero), $n\in S(x, B) $ iff

$$\sum_i \alpha_i \log p_i \le \log(x) $$

This is like asking how many integer coordinates points $(\alpha_1, \ldots, \alpha_m) $ are contained in the region

$$ A(x, B) = \{ (t_1, \ldots, t_m) \in \mathbb{R}^m : \sum (\log p_i) t_i \le \log(x), \ \ \ t_i \ge 0\} $$

Here $m =\pi(B) $ is the number of free parameters we have. It turns out this is closely related to the volume of this region: up to small problems on the boundary, a integer coordinate point contribute with a cube of volume 1, so that

$$\# \{\text{integer coordinate points in } A(x, B) \} \sim \text{volume}(A(x, B)) $$

Since the boundary has one dimension less, the approximation gets better and the better as $x$ gets larger with respect to $B$.

Let's wrap our head around how to calculate this volume. We could do the integral but it's boring. Geometrically, it is a little pyramid of dimension $m+1$, with a nice angle at zero and then some edges departing from it. The edges are long $\log(x) /\log(p_i) $: you get this by taking the maximum possible $t_i$ while all the other parameters are zero, because we are going along an axis.

The volume is linear in the length of each of its edges, so that we can factor out a

$$ \prod_{p\le B} \frac{\log(x) }{\log(p) }$$

And we are left with computing the volume of

$$D =\{(t_1, \ldots, t_m) : \sum t_i \le 1, \ \ t_i \ge 0\}$$

For $m=2$, this is $1/2$. Let's show by induction that the volume of such a pyramid in dimension $k$ is $1/k! $. If we know this for $k$, we also know that a tiny piramid with edges $=s$ has volume $s^k/k! $, by the same scaling argument as above. For $k+1$, we can section along a coordinate and we get pyramids of size $s$ for all $0\le s \le 1$. Integrating we get

$$ \int_{s=0}^1 \frac{s^k}{k! } = \frac{1}{(k+1)! }$$

As desired. Getting back to our original problem, we had $m=\pi(B) $ dimensions, so that

$$ \Psi(x, B) \sim \frac{1}{\pi(B)! } \prod_{p \le B} \frac{\log x}{\log p} $$

As desired. Note also that you have estimates of both parts in term of $x, B$, so that you get a neat estimate in the end!

Answer 2

If we let $y=5$, for example, each $5-$smooth number $N$ can be written as $N=2^a3^b5^c$. We then have $\log N=a\log 2 + b\log 3 +c\log 5$. You can think of a lattice, three dimensional because we have three primes, with each $5-$smooth number identified with the point $(a,b,c)$ in the lattice. The lattice spacing is $\log 2, \log 3, \log 5$ in the three dimensions. $\Psi(x,5)$ is then the number of lattice points nearer the origin than a plane that goes through the point $\log N$ on each axis. There are $\frac {\log N} {\log 2}$ points along the $2$ axis and similarly along the other axes. This means the volume of a lattice cell is $\prod_{p \le 5} \log p$, which gets us the product in your expression. The fact that we have a tetrahedron instead of a rectangular block give a factor $\frac 16$, which corresponds to the $\frac 1{\pi(B)!}$ in your expression.