MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

To construct gaps between primes which are marginally larger than average, Erdős and Rankin covered an interval $[1,y]$ with arithmetic progressions with prime differences. A nice short exposition is here, but I'll summarize.

The classic construction $z!+2, z!+3, ...z!+z$ constructs an interval of composite numbers which is embarrassingly short. It is shorter than the average distance between primes of size $z!$, $\log z! \sim z \log z,$ but we only constructed an interval of length $z.$ Slightly better is to replace $z!$ with the product of primes up to $z$, but this only produces a gap of about the average distance between primes. The method of Erdős and Rankin constructs a slightly larger gap, not quite $g \log g$ where $g$ is the size of an average gap.

The point of covering an interval with arithmetic progressions is as follows. If you have a covering of $[1,y]$ by arithmetic progressions $a_p \mod p$ with $p\lt z \lt y$ then by the Chinese Remainder Theorem choose $n$ between $z$ and $z+\prod_{p\lt z} p$ so that $n \equiv -a_p \mod p.$ Then $n+k\in \lbrace n+1, n+2, ... n+y \rbrace$ is divisible by the difference of whichever arithmetic progression covers $k$. If you can cover an interval of length $y$ which is much longer than $z$, then you can construct a gap which is much longer than average.

One ingredient in the construction is to choose $a_p = 0$ for primes between well-chosen $z_1 \lt z_2 \lt z$ with $z_1z_2 \gt y$. The point is that we get no collisions, so the arithmetic progression corresponding to each prime $p \in [z_1,z_2]$ covers a different $\lfloor \frac y p \rfloor$ integers in $[1,y].$

Second, use a greedy algorithm for small primes, choosing $a_p$ for $p \lt z_1$ so that each arithmetic progression covers as many uncovered integers in $[1,y]$ as possible. By the pigeonhole principle, you can reduce the number of uncovered integers by a factor of $(1-\frac 1 p).$ Use Mertens' Theorem, that

$$\prod_{p\lt z_1}(1-\frac1p) \sim \frac{e^{-\gamma}}{\log z_1}.$$

Third, use the larger primes $p \gt z_2$ to eliminate the remaining uncovered integers, using each prime to cover at least one integer until everything is covered.

Optimizing $z_1$ and $z_2$ is a bit messy, but using arithmetic progressions whose differences are primes up to $z$, they covered an interval of length at least $c \frac{z \log z \log\log\log z}{(\log\log z)^2} = o(z \log z).$

My question is what upper bounds are known for the effectiveness of this type of construction. I suspect that Erdős and Rankin couldn't have done much better by this technique.

If you take arithmetic progressions whose differences are the primes up to $z$, must there be an integer smaller than $O(z^2)$ which is not covered by any arithmetic progression? $O(z^{3/2})?$ $O(z \log z)$?

If there must be an uncovered integer smaller than $z^2$ then a different technique, perhaps not a constructive one, would be needed to establish that the existence of gaps of the conjectured size $z^2$ between primes of size about $\exp(z)$.

share|cite|improve this question
I am still working through the literature myself, so I don't know the answer. I take it you know of the further advances on prime gap lower bounds (Pomerance, Maier, Pintz, I think?), and that they bear no resemblance to Rankin's method? Also, have you checked Hagedorn's 2009 paper on computing Jacobsthal's function to make sure there is nothing you want there? Gerhard "Just Checking On The Obvious" Paseman, 2012.08.25 – Gerhard Paseman Aug 25 '12 at 21:46
Also, Westzynthius uses a similar argument to get bounds close to what Rankin and Erdos have. I will review the paper and post something summarizing the differences between W's method and the one you outline above (which may very well be no difference). Gerhard "Ask Me About System Design" Paseman, 2012.08.25 – Gerhard Paseman Aug 25 '12 at 22:18
If I remember correctly, Erdös himself was positive that this construction can't be improved easily (he called it hopeless even), which is the reason he offered a large prize for it. – Woett Aug 25 '12 at 23:58
I wouldn't be shocked if it could be improved by a really clever trick, but I'd still like to know if there is some clear obstruction to improving it all of the way to $z^2$, say. If so, then to prove there are large prime gaps one has to use other techniques than covering intervals by arithmetic progressions, although that still looks like a natural problem on its own. @Gerhard, I'm not very familiar with the recent progress on this problem, and I'll look into the work you mention. Thanks. – Douglas Zare Aug 26 '12 at 0:22
Maier-Pomerance indicate that they expect $z(\log z)^2$ as the limit (see 1.5), if one knew prime $k$-tuples. They basically use an on-average version of that (in AP), in the paper improving the constant. Thus for large primes, they can't show that any of them individually sieves out more than 1 number, but on average they can show at least 1.31, and Pintz 2. When knowing prime $k$-tuples, at least with uniformity enough, the large primes would then be shown to be more optimal, in sieving out. – Junkie Oct 25 '12 at 2:37

Your Answer


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

Browse other questions tagged or ask your own question.