Constructing arithmetic progressions

Solution 1:

There is no largest prime that would satisfy the sequence, since there are infinitely many progressions of length $k$. It is reasonable to ask for an upper bound for the smallest $k$-term progression in the primes. Green and Tao indeed obtained such a bound. To say it's astronomically large would be a gross understatement; it's mathematically large. :) $$N_k < c2^{2^{2^{2^{2^{2^{2^{100k}}}}}}}$$ There is a nice overview in the dissertation http://www.maths.bris.ac.uk/~matfb/dissertation.pdf , and reference [6] therein answers your question.

Solution 2:

This records page seems to be a good reference. It's conjectured that there is an AP of length $n$ starting with the smallest prime $\ge n$. The primorial $n\#=\prod_{p\le n}p$ is conjectured to be a tight lower bound on the difference for all $n>7$, although smaller values are possible for $n\le 7$, see A033188.

I'd be surprised if there's a nice analytical way to find small APs, but brute force seems to work pretty well. To find short ones you can start with any prime large enough and inspect APs with differences that are multiples of the primorial $n\#$. I wrote a quick PARI program to do this given a starting prime and it quickly gave me these: for n=5,

47, 13907, 27767, 41627, 55487

229, 108799, 217369, 325939, 434509

541, 25951, 51361, 76771, 102181

where the differences are 6, 47 and 11 times 11#. A bit longer, but in about a minute for n=10:

47, 4350704867, 8701409687, 13052114507, 17402819327, 21753524147, 26104228967, 30454933787, 34805638607, 39156343427

541, 916008361, 1832016181, 2748024001, 3664031821, 4580039641, 5496047461, 6412055281, 7328063101, 8244070921

I had to look farther to find one starting with 229, this took about 7 minutes:

229, 18170841379, 36341682529, 54512523679, 72683364829, 90854205979, 109025047129, 127195888279, 145366729429, 163537570579

To find much longer APs seems to require much more computational effort (e.g. AP26 was a PrimeGrid project).

Edit: I originally wrote the bound given in the question was correct, but realize thanks to @ErickWong I misread and it's not right at the primes.

Solution 3:

Note that the restriction $q<n$ can be strengthened to $q \le n$ unless the first prime $p$ happens to be exactly equal to $n$ (as in your example for $n=5$).

When $n$ is prime, the lower bound $d_0 = \prod\limits_{q<n} q$ given by the result you quote is not achieved unless the numbers $n, n+d_0, \ldots, n+(n-1)d_0$ are all simultaneously prime. This occurs for $n=2, 3, 5$, but not for $n=7,11,13$, and almost certainly not for any larger prime value of $n$ (there is no proof of this, but it seems extremely unlikely to ever occur).

With the above three exceptions aside, the best known lower bound for $d$ is $\prod\limits_{q\le n} q$. This is expected to be tight (according to the prime $k$-tuples conjecture), but no one has been able to prove even the simplest case: when $n=2$ we should be able to take $d=2$, but it is unknown whether there are infinitely many progressions $p,p+2$ (the safe bet is that there are).

Solution 4:

This may not answer the question, but I would like to point out that more recent work of Green and Tao have proven even stronger results.

Specifically, Green and Tao give exact asymptotics for the number of solutions to systems of linear equations in the prime numbers, and their paper Linear Equations in the Primes was published in the Annals in 2010. In particular, this tells us asymptotics for the number of $k$-term arithmetic progressions in the primes up to $N$.

For example, as $N\rightarrow \infty$, we can count the asymptotic number of 4-tuples of primes $p_1<p_2<p_3<p_4\leq N$ which lie in arithmetic progression, and it equals $$(1+o(1))\frac{N^2}{\log^4(N)} \frac{3}{4}\prod_{p\geq 5} \left(1-\frac{3p-1}{(p-1)^3}\right).$$

Do note however, that Green and Tao's paper made two major assumptions. They assumed the Möbius Nilsquence conjecture (MN) and the Gowers Inverse norm conjecture (GI). In a paper published in the Annals in 2012, Green and Tao resolve the MN conjecture, proving that the Möbius Function is strongly orthogonal to nilsequences. Recently, Green, Tao and Ziegler resolved the Gowers inverse conjecture, and their paper is currently on the arxiv. (It has not yet been published) This means that we unconditionally have asymptotics for the number of primes in a $k$ term arithmetic progression.

If you would like to learn more, I suggest reading Julia Wolf's excellent survey article Arithmetic and polynomial progressions in the primes, d'après Gowers, Green, Tao and Ziegler. It is very recent, as it was for the Bourbaki lectures at 2 month ago.