Skip to main content
2 of 4
corrected typos, and added the definition of the Buchstab function.
Lucia
  • 43.7k
  • 6
  • 193
  • 218

This is the type of problem that is solved by the ``fundamental lemma of sieve theory." Put $z=y^{1/u}$. Then from the fundamental lemma it follows that the number of integers in $[x,x+y]$ that are coprime to all primes below $z$ is $$ \sim y \prod_{p\le z} \Big(1-\frac 1p \Big) (1+O(u^{-u})). $$ So as $u$ goes to infinity, one has the asymptotic that you wanted. That is, the criterion is $(\log y)/(\log z) \to \infty$. See any book on sieves e.g. Friedlander and Iwaniec's Opera de Cribro.

Such a result is best possible. For example if you consider the initial interval $[0,y]$ and count integers free of primes below $z=y^{1/u}$, then this is $$ \sim \frac{y}{\log z} \omega(u), $$ where $\omega(u)$ is known as the Buchstab function (it satisfies $u\omega(u)=1$ for $1\le u\le 2$, and for $u>2$ is given by the differential-difference equation $(u\omega(u))^{\prime}= \omega(u-1)$). The function $\omega(u)$ tends to $e^{-\gamma}$ as $u$ goes to infinity (and in fact at the rate $O(u^{-u})$ as in the fundamental lemma). But for any finite $u$, $\omega(u)$ is not usually $e^{-\gamma}$. For example if $u=2$, then we are counting the primes up to $y$ and so $\omega(2)= 1/2$ instead of $e^{-\gamma}$. This problem is discussed (for example) in III.6 of Tenenbaum's book on analytic and probabilistic number theory (or see Montgomery and Vaughan's book).

Lucia
  • 43.7k
  • 6
  • 193
  • 218