Since$$\prod_{p \leq n} \left(1-\frac{1}{p}\right) =\frac{ e^{-\gamma}+o(1)}{ \log n},$$ by Mertens theorem, the density of integers in $$(X^{\theta},X],$$ which aren't divisible by primes $$p \leq X^{\theta}$$ is $$\rho(X)\sim \frac{ e^{-\gamma}}{\theta \log X}.$$

How small a subinterval in this interval can inherit this density?


Actually, the density you indicate is false, because $X^\theta$ is too large for the primes $p\leq X^\theta$ to behave sufficiently independently. For example, for $\theta=1/2$ the sifted set consists precisely of the primes in $(X^{1/2},X]$ whose density is $1/\log X$ (instead of $2e^{-\gamma}/\log X$) by the Prime Number Theorem.

Let $\Phi(x,y)$ denote the number of integers up to $x$ which are not divisible by any prime up to $y$. Let $u:=\log x/\log y$. Then Theorem 3 in Section of III.6.2 of Tenenbaum: Introduction to analytic and probabilistic number theory (Cambridge University Press, 1995) gives the asymptotic formula $$ \Phi(x,y)=\frac{x\omega(u)-y}{\log y}+O\left(\frac{x}{(\log y)^2}\right),\qquad x\geq y\geq 2,$$ where $\omega:[1,\infty)\to[1/2,1]$ is the Buchstab function satisfying (cf. Corollary 3.1 after the theorem) $$ \omega(u)=e^{-\gamma}+O(u^{-u/2}),\qquad u\geq 1.$$ Better bounds and various refinements are also available: see Chapter III.6 of the book in more detail.


It may be helpful to provide a combinatoric perspective for contrast. It will raise some interesting questions.

Given $n$ equal to the $k$th prime represent the left hand side as a reduced fraction I call $Pk$. For $k=1$ to $4$ we have the fractions 1/2, 1/3, 4/15, and 8/35. Thus I would expect an interval containing numbers coprime to $210$ to have this density be 8/35 only if the length of the interval is a multiple of 35. This quickly leads to the question: how fast does the denominator of $Pk$ grow?

A related statistic is the ratio $\omega(\prod (p-1))$, the number of distinct prime factors of the (unreduced) numerator of $Pk$; for $k\lt 46$ this quantity is lower bounded by $k/3$. I do not know the asymptotic of this quantity, but to discuss the previous paragraph further let me conjecture that it stays above $k/3$.

If it does stay above $k/3$, this means that the reduced denominator of $Pk$ is (very roughly) at most $P^{2/3}$, where $P$ is the product of the first $k$ primes. So for such $P$ (and thus for $X$ not far from $P$), I would expect an interval of length about $P^{2/3}$ to exactly match the density of coprimes to P in the interval $(\log P, P) \approx (p_k,P)$. If you are willing to accept some error, I would expect much smaller intervals to exist (of almost any length greater than say $2\log P$) to come close to the desired density. ( Of course, I am interested in how much the density can vary at that scale, which I believe can go from 0 to almost twice the average.) As remarked in another answer, if you fix $\theta \gt 0$ and ask ( as $X$ goes to infinity ) about density of numbers less than $X$ with no prime factor less than $X^\theta$, that density drops considerably.

Gerhard "It's A Matter Of Scale" Paseman, 2016.12.06.

  • $\begingroup$ In mathoverflow.net/a/219119 , I note that Lehmer considered some intervals which had the same density as the large interval. Again, if one accepts some error, it is not hard to show the existence of a small interval with density near the target density. If one knows the target density for the interval $(X^\theta, X)$, one should be able to get within epsilon of it using an interval of something like $X^\theta$/epsilon. Gerhard "Mind Your Epsilons And Deltas" Paseman, 2016.12.06. $\endgroup$ – Gerhard Paseman Dec 6 '16 at 20:50
  • $\begingroup$ Oh, and for $k=1$ one has $\omega(1)=0$, so the $k/3$ lower bound applies only for sufficiently large $k \lt 46$. Gerhard "One Is A Lonely Number" Paseman, 2016.12.06. $\endgroup$ – Gerhard Paseman Dec 6 '16 at 20:57
  • $\begingroup$ A055768 at oeis.org has terms computed to $k=10000$, showing that $k/6$ is a better lower bound than $k/3$. Likely the number of distinct prime factors over k tends to 0 with large k, but it may do so slowly enough that considering subintervals of length $P^{1-\delta(k)}$ may still be useful/interesting . Gerhard "Maybe It Doesn't Approach Zero" Paseman, 2016.12.06. $\endgroup$ – Gerhard Paseman Dec 6 '16 at 21:34
  • $\begingroup$ Also, there is the issue of sub intervals of non integral length. In this case, I conjecture that small intervals exist of the required density which contain any small positive number of coprimes. That should be an easy consequence of the nature of the density function, having discontinuities only on a discrete set of points. Gerhard "Not Doing Topological Number Theory" Paseman, 2016.12.06. $\endgroup$ – Gerhard Paseman Dec 6 '16 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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