most recent 30 from http://mathoverflow.net 2013-05-23T21:39:44Z http://mathoverflow.net/feeds/question/3347 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/3347/is-the-set-of-primes-translation-finite Yemon Choi 2009-10-29T21:52:50Z 2009-11-19T06:22:41Z

<p>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.</p> <p>Apologies if the question is too technical/localized/unappealing/bereft of schemes.</p> <p>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}$}.</p> <p>We say that $X$ is <i>translation-finite</i> if it has the following property: for every strictly increasing sequence n₁ &lt; n₂ &lt; in $N$, there exists k (possibly depending on the sequence) such that</p> <p>$(X-n_1) \cap (X-n_2) \cap \dots\cap (X-n_k)$</p> <p>is finite or empty.</p> <p>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 <em>and</em> we can always take k=2. Moreover:</p> <ul> <li><p>if $X$ contains an infinite arithmetic progression, or if it has positive (upper) Banach density, then it is NOT translation finite;</p></li> <li><p>there exist translation-finite sets which, when enumerated as strictly increasing sequences, grow more slowly than any faster-than-liner function.</p></li> <li><p>there exist translation-finite sets containing arbitrarily long arithmetic progressions.</p></li> </ul> <p>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.</p> <p><b>EDIT (2nd Nov)</b> 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.</p>

http://mathoverflow.net/questions/3347/is-the-set-of-primes-translation-finite/3715#3715 aorq 2009-11-01T23:22:30Z 2009-11-01T23:22:30Z

<p>As you mention, this is related to the Hardy-Littlewood <a href="http://mathworld.wolfram.com/k-TupleConjecture.html" rel="nofollow">k-tuple conjecture</a>. In particular, if their conjecture is true, then the primes are not translation-finite. Indeed, it is possible to find an increasing sequence n₁ &lt; n₂ &lt; n₃ &lt; ⋯ so that for every k, the first k n_is form an <a href="http://en.wikipedia.org/wiki/Prime%5Fk-tuple" rel="nofollow">admissible k-tuple</a>. (For example, I think n_i = (i+1)! works.) Then, by the k-tuple conjecture, infinitely many such prime constellations exist and so for all k, (X-n₁) ∩ (X-n₂) ∩ ⋯ ∩ (X-n_k) is infinite. (Here and below, X is the set of primes.)</p> <p>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 n₁ &lt; n₂ such that (X-n₁) ∩ (X-n₂) is infinite. In particular, this implies that the gap n₂-n₁ occurs infinitely often in primes, and so p_n+1-p_n is constant infinitely often. (The standard notation p_n indicates the n^th prime.)</p> <p>The best known upper bound for the size of small gaps in primes is that lim&thinsp;inf_n→∞ (p_n+1-p_n)/log p_n = 0. This was established by Goldston and Yildirim around 2003 and <a href="http://arxiv.org/abs/math.NT/0505300/" rel="nofollow">the proof was later simplified</a>. To the best of my knowledge, the best conditional result is by the same authors; they show that given the <a href="http://en.wikipedia.org/wiki/Elliott%E2%80%93Halberstam%5Fconjecture" rel="nofollow">Elliott-Halberstam conjecture</a>, the prime gap is infinitely often at most 20 or so.</p>