Covering the primes by arithmetic progressions - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T17:41:32Z http://mathoverflow.net/feeds/question/46769 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/46769/covering-the-primes-by-arithmetic-progressions Covering the primes by arithmetic progressions Joseph O'Rourke 2010-11-20T19:50:14Z 2010-11-21T20:46:06Z <p>Define the <em>length</em> of a set of arithmetic progressions of natural numbers $A=\lbrace A_1, A_2, \ldots \rbrace$ to be $\min_i | A_i |$: the length of the shortest sequence among all the progressions. Say that $A$ <em>exactly covers</em> a set $S$ if $\bigcup_i A_i = S$. Let $P'$ be the primes excluding 2.</p> <blockquote> <p>What is the longest set of arithmetic progressions that exactly covers the primes $P'$?</p> </blockquote> <p>In other words, I want to maximize the length of a set of such arithmetic progressions. Call this maximum $L_{\max}$.</p> <p>$L_{\max} \ge 2$ because $$P' \;=\; \lbrace 3,5 \rbrace \cup \lbrace 7,11 \rbrace \cup \cdots \cup \lbrace 521,523 \rbrace \cup \cdots$$ Perhaps it is possible that $$P' \;=\; \lbrace 3, 11, 19 \rbrace \cup \lbrace 5, 17, 29,41,53 \rbrace \cup \lbrace 7,19,31,43 \rbrace \cup \cdots \;,$$ but I cannot get far with sequences of length $\ge 3$. (I know Green-Tao establishes that there are arbitrarily long arithmetic progressions in $P$, but I don't know if that helps with my question.)</p> <p>I am number-theoretically naïve, and apologize if this question is nonsensical or trivial. In any case, I appreciate the tutoring!</p> <p><b>Addendum</b>. Although my question should be revised (as Idoneal suggests) in light of George Lowther's proof that 3 cannot be in a progression of length 4, George has shown that it is likely that $L_{\max}=3$ but certification requires resolving an open problem. So I've added the <em>open-problem</em> tag. Thanks for everyone's interest!</p> http://mathoverflow.net/questions/46769/covering-the-primes-by-arithmetic-progressions/46784#46784 Answer by George Lowther for Covering the primes by arithmetic progressions George Lowther 2010-11-20T23:31:16Z 2010-11-20T23:57:56Z <p>Despite the comments to the question (including mine), this is a bit easier than it seems at first sight. We can show that $L_{\max}=2$ or $3$. Almost certainly we have $L_\max=3$. However, determining which of these is actually the case seems to be beyond current technology, according to this MO answer "<a href="http://mathoverflow.net/questions/34197/are-all-primes-in-a-pap-3/34298#34298" rel="nofollow">Are all primes in a PAP-3?</a>".</p> <p>Showing that, $L_{\max} &lt; 4$ is easy. That is, not every odd prime is contained in an arithmetic progression of primes of length 4. More specifically, 3 is not contained in an arithmetic progression of length 4. Suppose that $\lbrace x, x+d, x+2d, x+3d \rbrace$ was such a progression for $d > 0$. Then $x\not=2$, otherwise we would have $x=2,d=1$, but $x+2d=4$ is not prime. So, $x=3$. But, then, $x+3d=3(1+d)$ is not prime.</p> <p>Edit: Looking at $\tilde L_\max \equiv \max_A\liminf_i \vert A_i\vert$ might be more interesting. I expect that this is infinite but, again, showing that $\tilde L_\max > 2$ appears to be beyond current means.</p>