Sharedwww / primes.texOpen in CoCalc
Author: William A. Stein
1\documentclass[11pt]{article}
2%\textwidth=1.1\textwidth
3%\hoffset=-.3in
4%\textheight=1.1\textheight
5%\voffset=-.5in
6%
7% The pari code I used:
8%
9% prog(p, a,  i=0) = while(isprime(p+a*i),i++);return(i);
10%
11% f(a, l, j=200000, i=0) = for(i=1,j,\
12%    if(prog(prime(i),a)>=l,print1(prime(i),"  ");i+=l-2));
13
14\include{macros}
15\title{Arithmetic Progressions of Primes}
16\author{W. Stein\footnote{UC Berkeley, Department of Mathematics, {\tt was@math.berkeley.edu}}}
17\begin{document}
18\maketitle
19\begin{abstract}
20Let $2n$ be an even integer.
21What is the longest arithmetic progression
22$p,\,p+2n,\,\ldots,\,p+2na$
23with $p$ prime?  In this paper we guess some answers.
24\end{abstract}
25{\bf Warning:} The following is just for fun!  There could be
26a well-known conjecture which supercedes all of this.
27
28\section{Introduction}
29It is easy to show (see Proposition~\ref{prop}) that if
30   $$p,\, p+2,\, p+4$$
31are all prime, then $p=3$.
32Similarly, if
33   $$p,\, p+6,\, p+12,\, p+18,\, p+24$$
34are all prime, then $p=5$ and the progression is thus
35   $5, \,11,\, 17, \, 23,\, 29.$
36There are probably infinitely many examples where
37   $$p,\, p+6,\, p+12, \, p+18,$$
38are all prime, but one would not dare think of proving this
39here as it is probably more difficult than the twin primes conjecture.
40
41For each even integer $2n$, let $M(2n)$ to be
42the maximal length of an arithmetic progression
43of primes with gap $2n$.  Thus $M(2)=3$, $M(6)=5$.
44Let $M_{\infty}(2n)$ be the maximum length of arithmetic
45progressions of gap $2n$ which occur
46infinitely often.  Thus one conjectures that
47$M_{\infty}(2)=2$, $M_{\infty}(6)=4$.
48
49Is there an example in which
50                  $M_{\infty}(2n)< M(2n)-1?$
51Is there an upper bound on the possible
52values $M(2n)$?
53
54\section{Table}
55The $M_?$ column was computed by searching the first
56100000 or so primes for an arithmetic progression of
57primes, having gap $2n$.
58The $M_{\infty?}$ column was computed by doing the same search,
59but requiring that at least {\em two} distinct progressions were found
60(usually there were many more). By Proposition~\ref{prop},
61the computed values of $M_?$ are the actual value of
62$M$, except possibly for the last four rows in the table.
63
64\begin{center}
65\begin{tabular}{|c|c|c|c|l|}\hline
66$2n$& $2n$ & $M_?$ & $M_{\infty?}$& Examples\\\hline\hline
67  $2$& $2$  &    3&   2 & 3\\
68  $4$& $2^2$  &    3&   2 & 3\\
69  $6$& $2\cdot 3$  &    5&   4 & 5\\
70  $8$& $2^3$  &    3&   2 & 3\\
7110& $2\cdot 5$  &    3&   2 & 3\\\hline
7212& $2^2\cdot 3$ &    5&   4 & 5\\
7314& $2\cdot 7$  &    3&   2 & 3\\
7416& $2^4$  &    2&   2 & 3\\
7518& $2\cdot 3^2$  &    4&   4 & 5\\
7620& $2^2\cdot 5$  &    3&   2 & 3\\\hline
7722& $2\cdot 11$  &    2&   2 & 7\\
7824& $2^3\cdot 3$  &    4&   4 & 59\\
7926& $2\cdot 13$  &    2&   2 & 3\\
8028& $2^2\cdot 7$  &    2&   2  & 3\\
81 30 &$2\cdot 3\cdot 5$ &    6&  6  & 7, 107 \\\hline
82 32 &$2^5$ &    2&  2  & 5\\
83 34 &$2\cdot 17$&    3&  2  & 3\\
84 36 &$2^2\cdot 3^2$&    4&  4  & 31\\
85 38 &$2\cdot 19$&    3&  2  & 3\\
86 40 &$2^3\cdot 5$ &   3&  2  & 3\\\hline
87 42 &$2\cdot 3\cdot 7$&    5&  4  & 5\\
88 44 &$2^2\cdot 11$&    2&  2  & 3\\
89 46 & $2\cdot 23$  &    2&  2  & 7\\
90 48&$2^4\cdot 3$&    5&  4  & 5\\
91 50&$2\cdot 5^2$&    3&  2  & 3\\\hline
92 210 & $2\cdot 3\cdot 5\cdot 7$  &   10&  9  & 199\\
93 2310 & $2\cdot 3\cdot 5\cdot 7\cdot 11$&  9  & 9 & 3823\\
9430030 & $2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13$&  12  & 12 & 23143,\,1498141\\
95510510 & $2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17$&  13  & ? & 766439\\
96\hline
97\end{tabular}
98\end{center}
99
100\section{Conclusions}
101\begin{proposition}\label{prop}
102Let $q$ be a prime.
103If $q\nmid 2n$ then
104$M(2n)\leq q$ and  $M_{\infty}(2n)\leq q-1$.
105Furthermore, $M(2n)=q$ iff $q$ is involved in arithmetic
106progression of length $q$ with gap $2n$.
107\end{proposition}
108\begin{proof}
109Reduce the arithmetic progression
110$$p,\,p+2n,\,\ldots,\,p+2na$$
111modulo $q$.  Since $2n$ is a unit
112modulo $q$, if the length of the arithmetic progression
113is $\geq q$ then one of
114the terms in the arithmetic progression is divisible
115by $q$, hence equal to $q$.
116\end{proof}
117
118In the table above, there is not a single example in which $q\nmid 2n$,
119$M(2n)=q$ and $q$ is not the first prime in the arithmetic.
120This suggests
121\begin{question}
122Let $q\nmid 2n$ be a prime and suppose
123$M(2n)=q$.  Then must
124 $$q,\, q+2n,\,\ldots, \, q+2n(q-1)$$
125all be prime?
126\end{question}
127
128The data also suggests the following
129\begin{conjecture}
130Both $M(2n)$ and $M_{\infty}(2n)$ are $\geq 2$ for all $n$.
131\end{conjecture}
132The conjecture that $M(2n)\geq 2$ is similar to Golbach's
133conjecture. It asserts that any even integer is
134the difference of two primes; the conjecture that
135$M_{\infty}(2n)\geq 2$ asserts that this can be done in
136infinitely many ways.
137
138It seems conceivable that $M(2n!)$ is unbounded as
139a function of $n$.
140
141\end{document}