Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Assume an arbitrary $x$ and let $z$ be smaller than $y$, where $y$ is the length of the interval $[x,x+y]$. What I would like to know is:

Let $W(z)=\prod_{p\leq z}\left(1-\frac{1}{p}\right)$. For what values of $z=z(y)$ is $$ y W(z) \sim \textrm{e}^{-\gamma} \frac{y}{\log z} $$ an accurate estimate of the number of integers coprime to all primes $p\leq z$ in the interval $[x,x+y]$?

A trivial answer—since the set of coprimes to $p\leq z$ is periodic with period $P(z)=\prod_{p\leq z} p$—is to choose $z$ so that $y/P(z) p \rightarrow \infty$. From numerical experiments, however, it seems that the far more moderate constraint $z/y\rightarrow 0$ is sufficient. So when can we indeed assume that Merten's product theorem correctly estimates the number of coprimes in an interval?

EDIT 1: To be specific, the observation I make numerically is that if we look at the interval $[x,x+y]$ in regions where $x$ is much larger than $y$, but still much smaller than $P(z)$, Merten's product theorem seems to accurately describe the density of coprimes to $p<z$ in $[x,x+y]$, even when $(\log y) /(\log z)=u$ is constant. Take for example $y=10^5$, $z=y^{1/2}$, and $x=n\cdot10^8$, where $n=1,\dots,512$. Then the mean density of coprimes to $p<z$ in $[x,x+y]$ ($\pm$ standard deviation) takes the value $$ (0.9998(5) \pm 0.0026(1))\cdot W(z). $$ Larger values of $u$ produce even more precise values, so e.g. $z=y^{1/3}$ for the same $x$ and $y$ results in mean density $$ (0.99999(9)\pm 0.00050(6)) \cdot W(z), $$ and likewise for $z=y^{1/4}$, $$ (0.99999(7)\pm 0.00011(6)) \cdot W(z). $$

From these numerical experiments the conjectured behavior is that if $z=y^{1/u}$, where $u>1$ is a constant, and we let $y\rightarrow \infty$, the density of coprimes to $p<z$ in $[x,x+y]$ is accurately approximated by $\textrm{e}^{-\gamma}/\log z$, given that $x$ is much larger than $y$ and much smaller than $P(z)$.

I'm interested in learning whether anyone has good heuristic arguments as to why and when these observations hold, and if possible, some more rigorous footing.

(Note that in order to emphasize the accuracy of the measurements, I have expressed the density values in terms of W(z) rather than $\textrm{e}^{-\gamma}/\log z$, as this would include a hidden error term.)

EDIT 2: While the numerical standard deviations above appear small, we could perhaps expect a larger standard deviation if we consider the number of coprimes to $P(z)$ in a random interval of length $y$. This poses a couple of questions (where we no longer consider $z$ to relate to $y$):

Q1: Is there a known upper bound on the variance of the number of coprimes to $P(z)$ for a randomly selected interval of length $y$?

Q2: Is the variance of the binomial distribution $B(y,W(z))$, given by $y W(z)(1-W(z))$, an upper bound of the variance of the number of coprimes to $P(z)$ in a random interval of length $y$?

The last question is motivated by the fact that in the extreme case when $y=1$, the probability of finding a coprime reduces to that of a Bernoulli trial with variance $W(z)(1-W(z))$. But for $y>1$, the probabilities of finding coprimes along $y$ are no longer independent. Furthermore, the variance is necessarily periodic with period $P(z)$. It therefore seems plausible that the binomial distribution $B(y,W(z))$ has a variance that is always greater than that of counting coprimes to $P(z)$ in a random interval of any length $y$.

share|improve this question
1  
Check out mathoverflow.net/questions/88777/… (not mathoverflow.net/questions/88877/…, quite different). You will get a different perspective on this problem. –  The Masked Avenger Mar 13 at 3:56
    
@TheMaskedAvenger: The discussion there only gives the obvious sieve of Eratosthenes result that if $y$ is substantially larger than $2^{\pi(z)}$ then the asymptotic holds. The fundamental lemma does much better than this, needing only $y$ to be a large power of $z$ rather than essentially exponential. –  Lucia Mar 13 at 4:40
    
Your last questions are addressed in the paper of Montgomery and Vaughan that I referenced (see the first page there; equations (2) and (3)). In particular, the variance is bounded above by $yW(z)$ in your notation. This is an elementary calculation, due first to Hausman and Shapiro. –  Lucia Mar 13 at 22:45
add comment

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer
    
Thanks a lot for a clear and informative answer. As you will see from my edit of the question, my numerical observations seem in fact to be in want for something that beats the best possible as long as we allow for some restrictions on $x$. Do you have any ideas of what direction to take? –  user45947 Mar 12 at 22:19
    
Your answer triggered a few more questions that I added above. Have me excused if they are already answered in the articles you referenced. While I get the gist of them, I am not fluent in reading analytical number theory, so it's a bit hard for me to penetrate the information rapidly. I'm grateful if you have any insights or clarifications on what I'm asking. –  user45947 Mar 13 at 22:36
    
Your range of answers was very insightful, so I consider the question as resolved. Thanks! –  user45947 Mar 14 at 13:19
    
For my own curiosity I'm working my way through the derivation of Hausman's and Shapiro's variance estimate. At the point, however, where they state "...and a simple calculation shows that this in turn equals...", I cannot understand how the calculation comes about. It might be obvious, but right now cannot see through it. Would you possibly know how that step is done? –  user45947 Mar 15 at 22:48
    
I don't have access to this from home. If I look at it at work next week (and find time), I'll let you know. –  Lucia Mar 15 at 22:59
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.