# Asymptotics of products of primes

Let $P(n)=\{p \leq n: p\text{ is prime} \}$. For given $N$ and $n$, what's a good approximation for $|S(N,n)|$, where $S(N,n)=\{x<N: \forall p\text{ prime, s.t. }p|x \to p \in P(n) \}$. In other words, how to approximate how many numbers $<N$ have only primes from $P(n)$ in their factorization?

-
See math.stackexchange.com/q/122692/1778 which is very similar. –  Charles Mar 22 '12 at 12:37

My previous answer was to a misreading of the question. Here is a similar aswer to the correct question. Once again, let $N=n^u$. The number of integers $<N$ with all prime factors $<n$ is approximately $\rho(u) N$, where $\rho(u)$ is Dickman's function.

For $0 \leq u \leq 1$, we clearly have $\rho(u)=1$.

For $1 \leq u \leq 2$, the number of integers which do NOT have the desired property is $\sum_{n \leq p \leq N} \lfloor N/p \rfloor$, where the variable $p$ runs over primes in the indicated range. One can justify turning the sum into an integral and discarding the greatest integer function: $$\int_{p=n}^N \frac{N}{p} \frac{dp}{\log p} = \int_{x=1/u}^1 \frac{N}{N^x} \frac{(\log N) N^x dx}{x \log N} = N \int_{x=1/u}^1 \frac{dx}{x} = N \log u.$$ In the first equality, we set $p =N^x$.

So the number of integers which do have the desired property is roughly $N - N \log u$, and $\rho(u) = 1-\log u$.

For $u$ in higher ranges, one has to worry about double counting, plus the integrals very quickly become undoable. The Wikipedia page is pretty good, so I'll stop here.

-

ADDED Oops! I thought you wanted all prime divisors of $N$ to be $>n$, not $<n$, and that is what the answer below addresses. For your question, there is a similar answer involving Dickman's function, which I have now added as a separate answer.

Fix a constant $u >1$ and let $N = n^u$. As $n \to \infty$, we have $$|S(N,n)| \sim \omega(u) \frac{N}{\log n}.$$ where $\omega$ is Buchstab's function. Buchstab's function is piecewise smooth, with singularities at the integers. I'll work out some special values of $u$ below:

If $1< u < 2$, then $|S(N,n)|$ is the number of primes between $N$ and $n$, so $\pi(N) - \pi(n)$. The first term is much larger than the second, so $$|S(N,n)| \sim \pi(N) \sim \frac{N}{\log N} = \frac{1}{u} \frac{N}{\log n}.$$ So $\omega(u)=1/u$ for $1 < u <2$.

If $2 < u < 3$, then $S(N,n)$ has two kinds of elements in it: Primes between $N$ and $n$, and products $pq$ of two primes with $p<q$, $p$ and $q > n$ and $pq<N$. Note that $p$ is necessarily $\leq N^{1/2}$. So $$|S(N,n)| =\pi(N)- \pi(n) + \sum_{p \ \mathrm{prime}, n < p < N^{1/2}} \left( \pi(N/p) - \pi(p) \right).$$ Again, the second $\pi$ term in each expression is negligible. Using the prime number theorem and being non-rigorous, we expect $$|S(N,n)| \approx \frac{N}{\log N} + \int_{p=n}^{N^{1/2}} \frac{N/p}{\log (N/p)} \frac{dp}{\log p}.$$ Put $p = N^x$, the integral is $$\int_{1/u}^{1/2} \frac{N^{1-x}}{(1-x) \log N} \frac{\log N \cdot N^x dx}{x \log N} = \int_{1/u}^{1/2} \frac{N dx}{x (1-x) \log N}$$ $$=\frac{N}{\log N} \log(u-1) = \frac{\log(u-1)}{u} \frac{N}{\log n}.$$ So $\omega(u) = 1/u + \log(u-1)/u$ for $2 < u <3$ (if I didn't screw up the integral).

For $3< u < 4$, a similar analysis gives an integral which can't be done in closed form, and for $u>4$, you wind up with integrals of those integrals which can't be done in closed form. But this should give you the idea.

When $u$ is very large, we have $$|S(N,n)| \approx N \prod_{p < n} (1-1/p) \sim N \cdot e^{- \gamma}/\log n$$ by Merten's theorem. So $\omega(u) \to e^{- \gamma}$ as $u \to \infty$.

-
Maybe I'm misreading, but didn't the original question ask about numbers with only small prime factors (so Dickman's $\rho$-function), as opposed to only large prime factors (where Buchstab's $\omega$-function appears)? –  Greg Martin Mar 22 '12 at 17:15
You are right. I misread. Would you like to write up the Dickman's function explanation? –  David Speyer Mar 22 '12 at 17:17
Maybe I can convince you to edit yours instead :) Thanks! –  Greg Martin Mar 22 '12 at 17:18