17
$\begingroup$

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!

Improve this question
$\endgroup$
10
  • 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$
    – Fedor Petrov
    Commented 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$
    – Joseph O'Rourke
    Commented Nov 20, 2010 at 20:15
  • $\begingroup$ it is not a result, but rather widely open conjecture... $\endgroup$
    – Fedor Petrov
    Commented 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$
    – Daniel Litt
    Commented Nov 20, 2010 at 21:21
  • $\begingroup$ @Fedor, Daniel: Oh, I see, sorry for misunderstanding. $\endgroup$
    – Joseph O'Rourke
    Commented Nov 20, 2010 at 21:29

1 Answer 1

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\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$
    – George Lowther
    Commented 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$
    – Joseph O'Rourke
    Commented 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$
    – George Lowther
    Commented 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
    Commented 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$
    – Fedor Petrov
    Commented Nov 21, 2010 at 6:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .