5
$\begingroup$

For each prime $p$, we can consider the set of arithmetic progression made of primes that include $p$: $A_p=\{\{a_i\}_{i=1}^k \mid \text{$\{a_i\}_{i=1}^k$ is an arithmetic progression, each $a_i$ is a prime, and $p=a_j$ for some $j$}\}$. Since there is no infinite arithmetic progression of primes (since for $a+nb$, $a \mid (a+na)$) we have a particular sequence in $A_p$ that is the longest among sequences in $A_p$. We may call its length $\alpha(p)$. Has this function been studied? Or does it have trivial explicit values?

2 Answers 2

2

I'll assume you are considering only positive primes. If a prime progression (of length $>1$) contains $p$, then the common difference cannot be divisible by $p$. This gives an a priori upper bound of $2p-1$ on the length of the progression.

One can sharpen this to an upper bound of $p$ by balancing the fact that the common difference can't be large (else there is no room before $p$) against the fact that it must be divisible by many small primes (else it cannot go much further than $p$).

So there is an upper bound of $\alpha(p)\le p$. This is generally believed to be best possible since the standard conjectures (e.g. Schinzel's Hypothesis H) would imply that $\alpha(p)=p$. On the other hand, lower bounds are very hard to come by. We do not even know, for instance, that $\alpha(p) > 2$ for all odd primes $p$ (however it is known to be true for the vast majority of primes by Montgomery and Vaughan's work on the exceptional set of Goldbach's conjecture).

  • 0
    I may be slightly confused, but why does there need to be room 'before' $p$? What if $p$ is the first member of the progression?2012-12-10
  • 0
    @StevenStadnicki Perhaps that was poorly worded. I simply meant that the larger you make the common difference, the less room there is to place terms before $p$. The tradeoff indeed heavily favours $p$ being the first member of the progression.2012-12-10
  • 0
    Ahhh, now I understand - I'd misunderstood the argument in the first paragraph and not caught on to the residue-classes. It makes much more sense now.2012-12-10
1

Here are a few thoughts on your problem, going to the intent of the question rather than the content.

For example, any prime arithmetic progression containing $2$ will have length at most $2$... and so is boring.

There are arbitrarily long arithmetic progressions consisting only of primes. This is the topic of the Green Tao Theorem. Their proof is not at all constructive, and it seems that a construction would be radically more difficult. What you are asking for is strictly harder than this result, and is likely beyond current methods.

  • 0
    I must be missing something pretty elementary here: you wrote "There are arbitrarily long arithmetic progressions consisting only of primes". Could you give 1-2 examples of these or, at least, of the first few elements of some of these? I must be understanding something different somewhere and it's driving me nuts. Thanks2012-12-06
  • 2
    @DonAntonio The longest explicitly-known progression of primes is $43142746595714191 + 23681770·23\#\cdot n$ with length $26$. This was found by PrimeGrid (the lucky machine was a Sony PlayStation 3!)2012-12-06
  • 0
    @DonAntonio: No, I can't, since the Green Tao Theorem is not constructive. None are known.2012-12-06
  • 0
    @mixedmath I'm curious what you'd expect an example to look like...2012-12-06
  • 0
    @Erick: That's a very good question. If we wanted a progression of $n$ primes, we'd need the common difference to be divisible by approximately the first $n$ primes. But one would anticipate that it would have to be larger to account for the growing expected difference between primes. As for the starting prime... since the difference is at least the approximate size of the product of the first $n$ primes, it would likely have to be much larger than the $n$th prime. How large? I have no idea.2012-12-07
  • 0
    @Erick: In fact, this lets us get some small progressions quickly. Starting with $2,3$, we might find $11,17,23,29$. Starting with $2,3,5$, we might find $7,37,67,97,127,157$. For $2,35,7$, we might find $13,223, 433,643,853,1063$. But it breaks down later.2012-12-07