How accurate is $\prod_{p < y} \left(1-\frac{1}{p}\right)$ for the number of $y$-rough integers?

Question

Call a positive integer $y$-rough if it has no factors below $y$. I am interested in accurate ways to estimate the number of positive integers less than or equal to $x$ that are $y$-rough. Assuming that $x > y^2$, one option is first to compute:

$$P=\prod_{p < y} \left(1-\frac{1}{p}\right)$$

where the $p$ are primes.

We can then give $xP$ as the estimate.

What can be said about how accurate this estimate is?

Answer 1

I don't know how much analytic number theory you know, so if this is way past your pay grade then let me know and perhaps there's an elementary method I can find. This is just the general method that almost always works with this sort of problem.

Suppose we want to count the amount of $y$-rough numbers. Let $i_n$ be the indicator function for $y$-rough numbers, i.e,

$$i_n= \begin{cases} 1 & n \text{ is }y\text{-rough}\\ 0 & \text{otherwise}. \end{cases}$$

We construct the Dirichlet series

$$f(s)=\sum_{n=1}^{\infty}\frac{i_n}{n^s}.$$

It is clear that $nm$ is $y$-rough if and only if both $n$ and $m$ are $y$-rough, and hence $i_{nm}=i_{n}i_{m}$. Thus, we have an Euler product expansion

\begin{align*} f(s)&=\prod_{p}\left(1+\frac{i_p}{p^s}+\frac{i_{p^2}}{p^{2s}}...\right)\\ &=\prod_{p\geq y}\left(1+\frac{1}{p^s}+\frac{1}{p^{2s}}...\right)\\ &=\prod_{p\geq y}\frac{1}{1-p^{-s}}\\ &=\zeta(s)\prod_{p<y}(1-p^{-s}). \end{align*}

In particular, since $\lim_{s\to 1}(s-1)\zeta(s)=1$, we have

$$\lim_{s\to 1}(s-1)f(s)=\prod_{p<y}\left(1-\frac{1}{p}\right).$$

The Hardy-Littlewood Tauberian Theore gives us thus that

$$\lim_{x\to\infty}\frac{1}{x}\sum_{n<x}i_{n}=\prod_{p<y}\left(1-\frac{1}{p}\right).$$

This is exactly the statement that your approximation is correct, i.e, the proportion of $y$-rough numbers tends to $\prod_{p<y}\left(1-\frac{1}{p}\right)$. To get uniform error bounds, you could use stronger analytic number theory results. For instance, Perron's formula says that

$$\sum_{n<x}i_n=\frac{1}{2\pi i}\int_{c-i\infty}^{c+i\infty}f(z)\frac{x^z}{z}dz$$

for any $c>1$. Now, $f(s)$ has no poles apart from the one at $s=1$ and hence using Cauchy's integral formula we can push $c$ as close as we want to 0. Hence, we get that

$$\left(\text{proportion of }y\text{-rough numbers less than }x \right)=\prod_{p<y}\left(1-\frac{1}{p}\right)+O(1/(x^{1-\epsilon}))$$

for every $\epsilon>0$. The constant in the big-Oh depends on $\epsilon$ and $y$.

Answer 2

Carl Pomerance gave a talk, "The sieve of Eratosthenes and rough numbers," at the recent Number Theory meeting in Monterey. He lets $\Phi(x,y)$ be the number of integers $n\le x$ with no prime factors $\le y$. His graduate student, Steve Fan, proved $$ \Phi(x,y)\le{x\over\log y},\quad x\ge y\ge2 $$ Fan and Pomerance together proved, for $3\le y\le\sqrt x$, we have $$ \Phi(x,y)<0.6x/\log y $$ I don't know whether these results are published yet, but Carl is good at posting his work to his website, you could have a look there.

Answer 3

I see that the question now has a bounty, so I guess my previous answer wasn't satisfactory. I'll make the upper bound explicit. Fix $T\geq 1$, and $1/2\geq\delta>0$. Explicit versions of Perron's formula tell us that

\begin{equation} \left| \sum_{n<x}i_n\right|=\left|\frac{1}{2\pi i}\int_{2-iT}^{2+iT}f(z)\frac{x^z}{z}dz\right|+O\left(\frac{x\log(x)}{T}\right). \end{equation}

The constant in the $O$ is uniform with respect to everything, i.e, an error bound of $10x\log(x)/T$ might hold. I have a gripe with people who treat Perron's formula with rarely making constants of this sort explicit. If I could find a reference with a number instead of a $O$ that would be great.

Now, we have by Cauchy's integral formula that

$$\left|\frac{1}{2\pi i}\int_{2-iT}^{2+iT}f(z)\frac{x^z}{z}dz\right|=x\prod_{p<y}(1-1/p)+\left|\frac{1}{2\pi i}\int_{\delta-iT}^{\delta+iT}f(z)\frac{x^z}{z}dz\right|+2\left|\frac{1}{2\pi i}\int_{\delta+iT}^{2+iT}f(z)\frac{x^z}{z} \right|.$$

To bound these, we need upper bounds on $f(z)$. It is well known (see for example page 97 of these notes) that for $\sigma\geq\delta$, and $t \geq 1$, there is an upper bound

$$|\zeta(\sigma+it)|\leq \left(\frac{1}{1-\delta}+1+\frac{3}{\delta}\right)t^{1-\delta}.$$

Additionally, we have that

$$\left|\prod_{p<y}\left(1-p^{-s}\right)\right|\leq \prod_{p<y}\left(1+p^{-\Re(s)}\right)\leq 2^{\pi(y)}.$$

Thus,

$$f(\delta+it)\leq 2^{\pi(y)}\left(\frac{1}{1-\delta}+1+\frac{3}{\delta}\right)t^{1-\delta}\leq 2^{\pi(y)+3} \cdot \delta^{-1} \cdot t^{1-\delta}.$$

Hence,

$$\left|\frac{1}{2\pi i}\int_{\delta+iT}^{2+iT}f(z)\frac{x^z}{z} \right|\leq 2^{\pi(y)+2}\cdot \delta^{-1}\cdot T^{-\delta}\cdot x^{\delta}.$$

Collecting, we get that

\begin{equation} \left| \sum_{n<x}i_n\right|=x\prod_{p<y}(1-1/p)+\left|\frac{1}{2\pi i}\int_{\delta-iT}^{\delta+iT}f(z)\frac{x^z}{z}dz\right|+O\left(\frac{x\log(x)}{T}+2^{\pi(y)}\cdot \delta^{-1}\cdot T^{-\delta}\cdot x^{\delta}\right). \end{equation}

Splitting up the integral one last time, we have

\begin{align*} \left|\frac{1}{2\pi i}\int_{\delta-iT}^{\delta+iT}f(z)\frac{x^z}{z}dz\right|&\leq 2\left|\frac{1}{2\pi i}\int_{\delta+i}^{\delta+iT}f(z)\frac{x^z}{z}dz\right|+\left|\frac{1}{2\pi i}\int_{\delta-i}^{\delta+i}f(z)\frac{x^z}{z}dz\right|. \\ \end{align*}

For the first integral, we use the previous bounds:

\begin{align*} 2\left|\frac{1}{2\pi i}\int_{\delta+i}^{\delta+iT}f(z)\frac{x^z}{z}dz\right|&\leq O\left(\int_{1}^{T}\frac{x^{\delta}\cdot 2^{\pi(y)}\cdot \delta^{-1}}{t^{\delta}}\right)\\ &\leq O\left(x^{\delta}\cdot 2^{\pi(y)}\cdot \delta^{-1}\cdot T^{1-\delta}\right).\\ \end{align*}

For the second, we use that $\zeta(z)$ is bounded in a fixed neighborhood of $0$. Hence, we get that

\begin{align*} \left|\frac{1}{2\pi i}\int_{\delta-i}^{\delta+i}f(z)\frac{x^z}{z}dz\right| &=O\left(2^{\pi(y)}\cdot x^{\delta}\cdot \delta^{-1}\right) \end{align*}

We thus have the big integral-free estimate

\begin{align*} \left| \sum_{n<x}i_n\right|&=x\prod_{p<y}(1-1/p)+2^{\pi(y)}\cdot\delta^{-1}\cdot O\left(x^{\delta}\cdot T^{1-\delta}+\frac{x\log(x)}{T}\right). \end{align*}

The trick is now to find the correct value of $T$. If the estimate had been done better, a good choice of $\delta$ would have given an approximation of the form $x^{\delta}\log(x)$. Seeing as it was done poorly, we can only get down to about $x^{1/2}$. For the sake of concreteness we fix $\delta$ away from $0$, and get the estimate

\begin{align*} \left| \sum_{n<x}i_n\right|&=x\prod_{p<y}(1-1/p)+O\left(2^{\pi(y)}\cdot x^{3/4}\right). \end{align*}

Even if we got down to $x^{\epsilon}$ for small $\epsilon$, this wouldn't work out. Namely, $x>y^2$ is not enough using this method. The error is almost exponential in $y$ but polynomial in $x$. If you wanted to try to get improvements, you would need to find a way to bound

$$\prod_{p<y}\left(1-\frac{1}{p^z}\right)$$

as $z$ ranges over the complex plane, and the real part of $z$ approaches $0$. In particular, you need to prove that not all of the $1/p^z$ can approximate $-1$ simultaneously.