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!

  • 3
    $\begingroup$ 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. $\endgroup$ Nov 20, 2010 at 20:02
  • $\begingroup$ @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! $\endgroup$ Nov 20, 2010 at 20:15
  • $\begingroup$ it is not a result, but rather widely open conjecture... $\endgroup$ Nov 20, 2010 at 20:49
  • $\begingroup$ 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. $\endgroup$ Nov 20, 2010 at 21:21
  • $\begingroup$ @Fedor, Daniel: Oh, I see, sorry for misunderstanding. $\endgroup$ Nov 20, 2010 at 21:29

1 Answer 1


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.

  • $\begingroup$ 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. $\endgroup$ Nov 20, 2010 at 23:37
  • $\begingroup$ @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). $\endgroup$ Nov 21, 2010 at 0:16
  • $\begingroup$ I can't claim credit for that phrase, as I was just quoting Ben Green's linked answer. $\endgroup$ Nov 21, 2010 at 0:28
  • $\begingroup$ 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. $\endgroup$
    – Idoneal
    Nov 21, 2010 at 6:34
  • $\begingroup$ 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. $\endgroup$ Nov 21, 2010 at 6:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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