What are the limits of the Erdős-Rankin method for covering intervals by arithmetic progressions? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T04:06:57Z http://mathoverflow.net/feeds/question/105477 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/105477/what-are-the-limits-of-the-erds-rankin-method-for-covering-intervals-by-arithmet What are the limits of the Erdős-Rankin method for covering intervals by arithmetic progressions? Douglas Zare 2012-08-25T19:51:06Z 2013-03-24T02:52:33Z <p>To construct <a href="http://en.wikipedia.org/wiki/Prime_gap" rel="nofollow">gaps between primes</a> 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 <a href="http://www.dms.umontreal.ca/~andrew/Courses/Chapter16.pdf" rel="nofollow">here</a>, but I'll summarize.</p> <hr> <p>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.</p> <p>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.</p> <p>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].$</p> <p>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 <a href="http://en.wikipedia.org/wiki/Mertens%27_theorems" rel="nofollow">Mertens' Theorem,</a> that </p> <p>$$\prod_{p\lt z_1}(1-\frac1p) \sim \frac{e^{-\gamma}}{\log z_1}.$$</p> <p>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. </p> <p>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).$</p> <hr> <p>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.</p> <h2>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)$?</h2> <p>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)$.</p>