Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Define the length 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$ exactly covers a set $S$ if $\bigcup_i A_i = S$. Let $P'$ be the primes excluding 2.

What is the longest set of arithmetic progressions that exactly covers the primes $P'$?

In other words, I want to maximize the length of a set of such arithmetic progressions. Call this maximum $L_{\max}$.

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

I am number-theoretically naïve, and apologize if this question is nonsensical or trivial. In any case, I appreciate the tutoring!

Addendum. 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 open-problem tag. Thanks for everyone's interest!

share|improve this question
3  
some general heuristics and explicit hard conjectures suggest that you may cover primes by (even disjoint) arithmetic progressions of arbitrary length $n$. Indeed, if you have already covered all primes up to $p$ (but not $p$), then there must exist an arithmetic progression $\{\p,p+d,p+2d,\dots,p+(n-1)d}$ for infinitely many $d$'s. So cover $p$ and proceed. –  Fedor Petrov Nov 20 '10 at 20:02
    
@Fedor: Your comment seems to definitively answer my question: $L_{\max}$ has no upper bound! I did not know the existence result you use. Thanks! –  Joseph O'Rourke Nov 20 '10 at 20:15
    
it is not a result, but rather widely open conjecture... –  Fedor Petrov Nov 20 '10 at 20:49
    
As Fedor suggests, the question "does every prime belong to an arithmetic progression of primes of length $d$," to which this question is equivalent, is very, very open for large $d$. So this question should probably be re-tagged "open-question"; that said this statistic is probably an interesting one for many other subsets of the integers. –  Daniel Litt Nov 20 '10 at 21:21
    
@Fedor, Daniel: Oh, I see, sorry for misunderstanding. –  Joseph O'Rourke Nov 20 '10 at 21:29
show 5 more comments

1 Answer

up vote 10 down vote accepted

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 "Are all primes in a PAP-3?".

Showing that, $L_{\max} < 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.

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.

share|improve this answer
    
I think maybe, in his comment, Fedor was suggesting that it can be done using arithmetic progressions with arbitrarily large step size, rather than arbitrarily large length. –  George Lowther Nov 20 '10 at 23:37
    
@George: Clever proof that 3 is not in a progression of length 4! Similarly 5 is not in a progression of length 6. So the question could be modified to ask for coverage of all but the beginning of the sequence. But I won't attempt to reformulate the question in light of your recognizing that deciding between 2 and 3 is already "beyond the current technology" (a useful [and optimistic!] phrase). –  Joseph O'Rourke Nov 21 '10 at 0:16
    
I can't claim credit for that phrase, as I was just quoting Ben Green's linked answer. –  George Lowther Nov 21 '10 at 0:28
    
In such problems, it is interesting to ignore the small primes and ask what happens for all sufficiently large primes. Perhaps that is what Fedor had meant. –  Idoneal Nov 21 '10 at 6:34
    
No no, I meant what I said, but I've been mistaken, sorry. The natural conjecture is that $p$ lies in arithmetic progression of length $p$, but of course not more, by trivial reasons (modulo $p$). So, most probably we may cover all primes but finite number of them by arithmetic progressiond of arbitrary length. –  Fedor Petrov Nov 21 '10 at 6:58
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.