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

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?

• I am only aware of asymptotic results. The estimate should be quite accurate if $x$ is much larger than $y$ (say $\ln(x)>3\ln(y)$ holds). Note that $P$ is asymptotically $$\frac{e^{-\gamma}}{\ln(y)}$$ where $\gamma$ is the Euler-Mascheroni constant. Commented Dec 22, 2022 at 11:08
• @Peter I would really like a non-asymptotic result. Where does $\ln(x) > 3\ln(y)$ come from and can "quite accurate" be quantified?
– Simd
Commented Dec 22, 2022 at 11:10
• I wondered this a long time ago as well and I only found the Buchstab function, but nowhere a good estimate of the error we make. Commented Dec 22, 2022 at 11:11
• @Peter It is not me speaking against something. See meta and other places, where it is recommended not to crosspost: "Ask the question on the site you think is most applicable. Each site is focused on a specific topic area and it's important to respect the community." Commented Dec 22, 2022 at 15:10
• @GerryMyerson I have learned that my question isn't easy to answer.
– Simd
Commented Dec 26, 2022 at 17:13

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

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

$$\lim_{s\to 1}(s-1)f(s)=\prod_{p

The Hardy-Littlewood Tauberian Theore gives us thus that

$$\lim_{x\to\infty}\frac{1}{x}\sum_{n

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

$$\sum_{n

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

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

• Thank you for this! You switched to y-smooth at the end. Did you mean to?
– Simd
Commented Dec 22, 2022 at 19:44
• I think your references are missing too.
– Simd
Commented Dec 22, 2022 at 19:45
• @Simd Oops, that was a mistake. Thanks for the correction! Commented Dec 22, 2022 at 19:46
• @Simd Oh, yes. This was copy pasted from yesterday's version of your question, and the references didn't carry through: It's fixed now. Commented Dec 22, 2022 at 19:48
• If we fix x and y can this method give an error bound? Say $x=2^{20}$ and $y=2^9$.
– Simd
Commented Dec 22, 2022 at 19:49

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.

• math.dartmouth.edu/~carlp/rough.pdf
– Simd
Commented Dec 24, 2022 at 22:13
• I read their paper but sadly they say numerical bounds will come in a later paper. I also implemented their expanded version of Buchstab's function but it is almost identical numerically to the non-expanded version and still approx 3% off for simple cases.
– Simd
Commented Dec 26, 2022 at 17:14

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

$$$$\left| \sum_{n

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

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}.$$

$$\left|\prod_{p

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

$$$$\left| \sum_{n

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

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

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

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.

• How small does y have to be for this method?
– Simd
Commented Dec 26, 2022 at 19:08
• y<log(x), more or less Commented Dec 26, 2022 at 19:46
• Ah ok. I am sorry my question just turns out to have been much harder than I expected.
– Simd
Commented Dec 26, 2022 at 19:52