Is it possible that for any integer $y \ge 2$, there exists an integer $x$ such that if an integer $n \ge x$, then for all integers $z \le n^y$, there exists a prime $p$ such that $z \le p < z+n$

I am especially interested in a counter example, an argument that it is not possible, or a explanation of what the Prime Number Theorem or some other deep mathematical theorem states about this possibility.

Thanks very much,


  • 1
    $\begingroup$ I have removed the "elementary number theory" tag. $\endgroup$ – user 170039 Dec 11 '14 at 6:14
  • $\begingroup$ Thanks. I never know how elementary my questions are. :-) $\endgroup$ – Larry Freeman Dec 11 '14 at 6:20

We can show (using the PNT and using more or less standard notation here) that for sufficiently large $n$ there is an arbitrarily large $k$ such that $$n< p < (n+1/k)n$$

We can prove it in general--the trick is to find a specific $N$ so that if $n>N$ this will work for given k. Nagura proves it for $k = 5$ and other authors have found much higher $k$ and $N.$

Changing the notation of the OP a little we could try to incorporate the claim into the PNT assertion as

$$n \leq (n/k)^{y}. $$

Then $n^{(1/y-1)} =\frac{1}{n^{(1-1/y)}}\leq 1/k$ or $k \leq n^{1-1/y}.$ For concreteness if $y = 2$ initially we have $k \leq \sqrt{n}.$ As $n$ grows larger we would see $k \leq n^{2/3}$ and so on. So even though $k$ can grow it cannot grow too fast.

As an aside, if we look at $(n,n+n^{1/k})$ there is a theorem that for sufficiently large $n$ there is a prime on $(n,n+n^{0.525})$ due to Baker and a 1996 result of Ch. Jia that there there is a prime on $(n,n+n^{1/20+\epsilon})$ in which $\epsilon$ goes to zero as n gets large. These used analytic and sieve methods.

Taking the second theorem above, this is equivalent to saying that if $n$ is large enough we could take $k \leq n^{19/20}$ and find a prime in the interval.

So I think this is not a simple consequence of the PNT if it is true. I can't prove or disprove it.

  • $\begingroup$ Thanks very much for your comment. What interests me about the exponent is a pattern I saw when I looked at each integer $n$, for the first number $x$ where $x, x+1,$ ... $, x+n-1$ that did not have any primes. I noticed that at first, the bound was around $n^2$ but as $n$ got larger, it grew to $n^3$. I wondered if this trend continued. $\endgroup$ – Larry Freeman Dec 11 '14 at 6:01
  • $\begingroup$ That would be great! That's exactly the point that I am trying to understand. $\endgroup$ – Larry Freeman Dec 11 '14 at 6:16

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.