Return to Answer

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

Edit: The numerics you have are quite interesting. Put $P(z)=\prod_{p\le z}p$. My answer above addresses what is known in general, but if the initial point $x$ is chosen randomly, then we do expect $y\prod_{p\le z}(1-1/p)$ to be a good approximation with high probability. One famous result in this direction is the work of Montgomery and Vaughan (On the distribution of reduced residues, Annals of Math. 1986) which shows that if $x$ is chosen uniformly from $[0,P(z)]$ then the distribution of numbers coprime to $P(z)$ in intervals $[x,x+y]$ is roughly Gaussian with mean $y\phi(P(z))/P(z)$ and variance also on that order. See also work of Montgomery and Soundararajan (Comm. Math. Phys. 2004; http://arxiv.org/pdf/math/0409258.pdf ). It is conceivable that if say $x=z^{10}$ and $y=z^2$ then the asymptotic holds always, but I don't know of any proven result of this kind (and would find such a result extremely interesting).

However one should be a bit careful about what ranges of $x$ might have such a result. For example if $x=\prod_{p\le z/100} p$ then I would expect that the interval $[x,x+z^2]$ does not contain the right number of integers coprime to $P(z)$. Yet here $x$ is much smaller than $P(z)$ (about its $100$-th root) and much larger than $y$.

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

Edit: The numerics you have are quite interesting. Put $P(z)=\prod_{p\le z}p$. My answer above addresses what is known in general, but if the initial point $x$ is chosen randomly, then we do expect $y\prod_{p\le z}(1-1/p)$ to be a good approximation with high probability. One famous result in this direction is the work of Montgomery and Vaughan (On the distribution of reduced residues, Annals of Math. 1986) which shows that if $x$ is chosen uniformly from $[0,P(z)]$ then the distribution of numbers coprime to $P(z)$ in intervals $[x,x+y]$ is roughly Gaussian with mean $y\phi(P(z))/P(z)$ and variance also on that order. See also work of Montgomery and Soundararajan (Comm. Math. Phys. 2004; http://arxiv.org/pdf/math/0409258.pdf ).

However one should be a bit careful about what ranges of $x$ might have such a result. For example if $x=\prod_{p\le z/100} p$ then I would expect that the interval $[x,x+z^2]$ does not contain the right number of integers coprime to $P(z)$. Yet here $x$ is much smaller than $P(z)$ (about its $100$-th root) and much larger than $y$. Also there will exist intervals with $x$ of size any fixed power of $z$ having significant fluctuations from the expected asymptotic.

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

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

Edit: The numerics you have are quite interesting. Put $P(z)=\prod_{p\le z}p$. My answer above addresses what is known in general, but if the initial point $x$ is chosen randomly, then we do expect $y\prod_{p\le z}(1-1/p)$ to be a good approximation with high probability. One famous result in this direction is the work of Montgomery and Vaughan (On the distribution of reduced residues, Annals of Math. 1986) which shows that if $x$ is chosen uniformly from $[0,P(z)]$ then the distribution of numbers coprime to $P(z)$ in intervals $[x,x+y]$ is roughly Gaussian with mean $y\phi(P(z))/P(z)$ and variance also on that order. See also work of Montgomery and Soundararajan (Comm. Math. Phys. 2004; http://arxiv.org/pdf/math/0409258.pdf ). It is conceivable that if say $x=z^{10}$ and $y=z^2$ then the asymptotic holds always, but I don't know of any proven result of this kind (and would find such a result extremely interesting).

However one should be a bit careful about what ranges of $x$ might have such a result. For example if $x=\prod_{p\le z/100} p$ then I would expect that the interval $[x,x+z^2]$ does not contain the right number of integers coprime to $P(z)$. Yet here $x$ is much smaller than $P(z)$ (about its $100$-th root) and much larger than $y$.

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 x} \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 a nice function that tends to $e^{-\gamma}$ as $u$ goes to infinity (and in fact at the rate $O(u^{-u})$ as in the fundamental lemma). 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 Tenenbaum's book on analytic and probabilistic number theory (or see Montgomery and Vaughan's book); my notation may be slightly different ... .

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