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