What are the limits of the Erdős-Rankin method for covering intervals by arithmetic progressions?

2012-08-25T19:51:06Z

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

What are the limits of the Erdős-Rankin method for covering intervals by arithmetic progressions? - MathOverflow

What are the limits of the Erdős-Rankin method for covering intervals by arithmetic progressions?

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)$?