The definition in the title probably needs explaining. I should say that the question itself was an idea I had for someone else's undergraduate research project, but we decided early on it would be better for him to try adjacent and less technical questions. So it's not of importance for my own work per se, but I'd be interested to know if it easily reduces to a known conjecture/fact/counterexample in number theory.

Apologies if the question is too technical/localized/unappealing/bereft of schemes.

Given a subset $X$ of the natural numbers $N$, and given $n \in N$, we write $X-n$ for the backward translate of $X$, i.e. the set $\{x-n : x\in X\}$.

We say that $X$ is translation-finite if it has the following property: for every strictly increasing sequence $n_1 < n_2 < \dotsb$ in $N$, there exists $k$ (possibly depending on the sequence) such that

$$(X-n_1) \cap (X-n_2) \cap \dotsb\cap (X-n_k)$$

is finite or empty.

Thus every finite set is trivially translation-finite: and if the elements of $X$ form a sequence in which the difference between successive terms tends to infinity, then $X$ is translation-finite and we can always take $k = 2$. Moreover:

  • if $X$ contains an infinite arithmetic progression, or if it has positive (upper) Banach density, then it is NOT translation finite;

  • there exist translation-finite sets which, when enumerated as strictly increasing sequences, grow more slowly than any faster-than-linear function.

  • there exist translation-finite sets containing arbitrarily long arithmetic progressions.

These resultlets suggest the question in the title, but I don't know enough about number theory to know if it's a reasonable question. Note that if, in the definition, we were to fix $k$ first (i.e. there exists $k$ such that for any sequence $(n_j)$…) then we would get something related to Hardy–Littlewood conjectures; but I was hoping that this might not be necessary to resolve the present question.

EDIT (2nd Nov) It's been pointed out below that the question reduces in some sense to a pair of known, hard, open problems. More precisely: if the answer to the question is yes, then we disprove the Hardy–Littlewood $k$-tuples conjecture; if the answer is no, then there are infinitely many prime gaps bounded by some absolute constant, and this is thought to be beyond current techniques unless one assumes the Eliott–Halberstam conjecture.

Added in 2013: Stefan Kohl points out that the latter is Yitang Zhang's famous recent result. However, as Will Sawin points out in comments, a negative answer to the main question would imply there are 3-tuple configurations occurring infinitely often in the primes, and (see the link in Will's comment) this is thought to be out of reach even if we assume the EH conjecture holds.

  • 1
    $\begingroup$ What do you mean by "the elements of X form a sequence tending to infinity"? Does that imply something other than X being an infinite set? $\endgroup$ Oct 30, 2009 at 0:07
  • 7
    $\begingroup$ Yay for non-scheme questions! $\endgroup$ Oct 30, 2009 at 2:12
  • 1
    $\begingroup$ @Scott: makes sense to me. @Yemon: thanks for nicely summarizing th results in the question body! $\endgroup$ Nov 27, 2009 at 23:52
  • 1
    $\begingroup$ Because the existence of any $3$-tuples which occurs infinitely often in primes is still out of reach, this is still open. See: mathoverflow.net/questions/132731/… $\endgroup$
    – Will Sawin
    Jul 4, 2013 at 16:26
  • 1
    $\begingroup$ @RaphaelJ.F.Berger, re, thank you for editing to improve typos! However, despite the strong initial appearance that "resultlets" is a typo for "result lets", the sentence doesn't make sense with that correction. I think that 'resultlets' here was meant to be a diminutive form of 'results', and have accordingly edited to restore the original. $\endgroup$
    – LSpice
    Feb 1 at 21:42

2 Answers 2


As pointed out to me by the OP, Theorem 1.5 of my recent paper with Tamar Ziegler answers this question in the negative. (The situation has changed since the 2009 and 2013 comments due to the breakthrough work of Zhang on prime gaps in 2014, followed by the stronger results of Maynard in 2015; our own paper relies heavily on the Maynard sieve.)

  • $\begingroup$ Thanks - I thought as much but worried in case I was misreading in haste. $\endgroup$
    – Yemon Choi
    Feb 1 at 19:07

As you mention, this is related to the Hardy-Littlewood k-tuple conjecture. In particular, if their conjecture is true, then the primes are not translation-finite. Indeed, it is possible to find an increasing sequence n1 < n2 < n3 < ⋯ so that for every k, the first k nis form an admissible k-tuple. (For example, I think ni = (i+1)! works.) Then, by the k-tuple conjecture, infinitely many such prime constellations exist and so for all k, (X-n1) ∩ (X-n2) ∩ ⋯ ∩ (X-nk) is infinite. (Here and below, X is the set of primes.)

However, maybe we can prove that the primes are not translation finite by some other means. Unfortunately, the technology is not quite good enough to do that. Proving that the primes are not translation finite would, in particular, prove that there exist n1 < n2 such that (X-n1) ∩ (X-n2) is infinite. In particular, this implies that the gap n2-n1 occurs infinitely often in primes, and so pn+1-pn is constant infinitely often. (The standard notation pn indicates the nth prime.)

The best known upper bound for the size of small gaps in primes is that lim infn→∞ (pn+1-pn)/log pn = 0. This was established by Goldston and Yildirim around 2003 and the proof was later simplified. To the best of my knowledge, the best conditional result is by the same authors; they show that given the Elliott-Halberstam conjecture, the prime gap is infinitely often at most 20 or so.

  • $\begingroup$ Thanks! That's very clear. So, if I understand you correctly: a proof of HL's k-tuple conjecture would imply the primes are not translation finite; while a proof that the primes are not translation finite would imply a bound on prime gaps that is beyond current knowledge. So my question essentially reduces to known open problems I guess. $\endgroup$
    – Yemon Choi
    Nov 1, 2009 at 23:52
  • 1
    $\begingroup$ @Yemon Choi: That's correct. Proving the primes are translation finite would disprove the k-tuples conjecture, while proving the primes aren't translation finite would prove bounds on small prime gaps. $\endgroup$
    – aorq
    Nov 2, 2009 at 3:27
  • 2
    $\begingroup$ Why does the infinitude of $(X-n_1)\cap(X-n_2)$ imply that the gap $n_2-n_1$ occurs infinitely often? Couldn't some smaller gaps occur infinitely often instead? $\endgroup$ Dec 27, 2012 at 4:59
  • 1
    $\begingroup$ Hope you don't mind that I'm switching the "accepted answer" :) $\endgroup$
    – Yemon Choi
    Feb 1 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.