# How many distinct translates of a (non-admissible) set $\mathcal{H}$ can consist entirely of primes?

In a recent post, Terence Tao talks about the prime tuples conjecture, and in particular, he asks: "Suppose one is given a ${k_0}$-tuple ${{\mathcal H} = (h_1,\ldots,h_{k_0})}$ of ${k_0}$ distinct integers for some ${k_0 \geq 1}$, arranged in increasing order. When is it possible to find infinitely many translates ${n + {\mathcal H} =(n+h_1,\ldots,n+h_{k_0})}$ of ${{\mathcal H}}$ which consists entirely of primes?" To study this, the concept of an admissible set is introduced: a $k_0$-tuple ${\mathcal H}$ is admissible "if it avoids at least one residue class ${\hbox{ mod } p}$ for each prime ${p}$."

It is pointed out that, since for non-admissible sets ${\mathcal H}$ there exists a prime $p$ such that ${\mathcal H}$ meets every residue class $\hbox{ mod } p$, then every translate of ${\mathcal H}$ must contain a multiple of $p$, and so there can only be a finite number of translates of ${\mathcal H}$ consisting entirely of primes: in particular, each translate consisting of only primes must contain $p$ itself.

This seems incredibly restrictive. Given a non-admissible $k_0$-tuple ${\mathcal H}$, just how many translates are there consisting only of primes, and how does this depend on $k_0$? Can there even be more than 1?

As an example, the non-admissible $3$-tuple $(0,2,4)$ has only a single translate consisting of primes -- $(3,5,7)$ -- since every third odd number greater than 3 is divisible by 3, and hence not prime. There are plenty of prime triplets, i.e. $3$-tuples of the form $(p, p+2, p+6)$ or $(p,p+4,p+6)$, but both $(0,2,6)$ and $(0,4,6)$ are admissible -- and similarly for prime quadruplets, quintuplets, and sextuplets.

I'm thinking about writing up some Mathematica code to go prime-diving, but I wanted to see if there's some simple theory here first that would save time.

Edit: The wiki page on prime k-tuples says that "Some inadmissible k-tuples have more than one all-prime solution" and gives the smallest example, but doesn't explain how it arrived at this or explains any of the theory behind it, let alone gives estimates on how many there are. This of course just makes the curiosity even worse.

• If you have a tuple which is inadmissible because the primes {p, q, ...} have all of their residue classes filled, a necessary condition to having an all-prime translate is that the translate contain {p, q, ...}. This may happen several times. In the Wikipedia example the obstruction is 5 and it can occur in the first or second position of the tuple. – Charles Jun 6 '13 at 20:25

An obvious upper bound is $k_0$ itself. There is some prime $p$ such that $\mathcal{H}$ contains all the residue classes mod $p$ (since the tuple is inadmissible), and $p\in n+\mathcal{H}.$

Another upper bound is $\pi(p)$ since the prime can't appear in after $k$ others unless there are $k$ others before it. Of course this is not sharp: you need not only $k$ primes before $p$, but for them to be arranged in the same pattern.

• @AndrewG: If you use a common difference of $p-1$ then $p$ can occur at most once, in the first position. To occur in the second position there would need to be a prime $p-(p-1)$. – Charles Jun 6 '13 at 20:47
• Derp, of course, I don't know what I was thinking. But in order to actually achieve $k_0$, wouldn't we need a prime arithmetic progression? $p$ would have to start out on the right-hand side and then, as we translate, move to the left: this would turn the distance between the last two elements into the distance between the 2nd and 3rd last, and so-on, so that they all have a common difference. Can prime arithmetic progressions even be inadmissible? I admit I am very ignorant of these ideas and of number theory in general. – AndrewG Jun 6 '13 at 21:14
• @AndrewG: I don't see why you would need an arithmetic progression. The important thing is that all residue classes are filled, not in what order. – Charles Jun 7 '13 at 1:07

It seems very likely that the answer is "arbitrarily many", at least if we are allowed to make $k_0$ arbitrarily large.

I was thinking about this question myself the other day, and I happened upon the exact same tuple mentioned on Wikipedia. My reasoning was as follows. Fix a prime $p$ such that every residue class modulo $p$ is represented in our (hypothetical) tuple $\mathcal H$. Then every translate of $\mathcal H$ consisting of primes must include $p$ itself. Suppose (for example) that $(p, p + h_1, \dots, p + h_{k_0})$ and $(p - h_1, p, p - h_1 + h_2, \dots, p - h_1 + h_{k_0})$ consist entirely of primes. Then $p$ lies in the middle of three-term arithmetic progression of primes with common difference $h_1$. Once we've found such a prime (say $p = 5$, with $h_1 = 2$), we just need to find primes $p + h_2, \dots, p + h_{k_0}$, covering all remaining residue classes modulo $p$, such that each $p + h_i - h_1$ is prime. At least in the given case, this is easy to do: $(3, 5, 11, 17, 29)$ and $(5, 7, 13, 19, 31)$ consist entirely of primes.

The discussion above generalizes pretty easily to give more than two translates. The natural thing to try is to find some $p$ lying in the middle of a five-term arithmetic progression (I chose 17, using the AP 5, 11, 17, 23, 29), and find three-term AP's with the same common difference covering all remaining residue classes modulo $p$. An example is \begin{align} \mathcal H = (0, 2, 6, 12, 26, 42, 56, 91, 96, 146, 222, 252, 582, 642, 1086, 1176, 2702), \end{align} which has three translates consisting of primes: \begin{align} & (5, 7, 11, 17, 31, 47, 61, 97, 101, 151, 227, 257, 587, 647, 1091, 1181, 2707), \\ & (11, 13, 17, 23, 37, 53, 67, 103, 107, 157, 233, 263, 593, 653, 1097, 1187, 2713), \\ & (17, 19, 23, 29, 43, 59, 73, 109, 113, 163, 239, 269, 599, 659, 1103, 1193, 2719). \end{align}

More generally, if you want $n$ prime translates, you could start with a $(2n-1)$-term AP of primes (which exists by Green-Tao), let $p$ be the $n$th of them, and try to fill in the remaining residue classes modulo $p$ with primes in $n$-term APs, as above. I don't know the current state of research well enough to say for sure whether these $n$-term APs with prescribed common difference and residue classes modulo $p$ will necessarily exist, but it seems likely that they will.

As an aside, it isn't necessary to begin with such a long arithmetic progression. For example, if $n = 4$, you could begin with a two-dimensional AP of primes such as \begin{matrix} 5 & 17 & 29 \\ 47 & 59 & 71 \\ 89 & 101 & 113, \end{matrix} take $p = 59$, and construct your four translates so that each one contains one of the four 2x2 corners of the grid above.