Implication of Polignac's conjecture on prime distribution in models of PA - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T09:58:58Z http://mathoverflow.net/feeds/question/51378 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/51378/implication-of-polignacs-conjecture-on-prime-distribution-in-models-of-pa Implication of Polignac's conjecture on prime distribution in models of PA Jason 2011-01-07T10:07:52Z 2011-01-07T16:12:05Z <p><a href="http://en.wikipedia.org/wiki/Polignac%27s_conjecture" rel="nofollow">Polignac's conjecture</a> (PC) is that there exists infinitely many pairs of consecutive prime numbers that are a distance $d$ apart for some natural number $d$. The twin prime conjecture is the particular instance of this conjecture for $d = 2$. The fact that this conjecture remains open has some interesting implications on nonstandard models of Peano Arithmetic (PA). Specifically, it is a standard exercise to show that every model of PA has order type $\mathbb{N} + \mathbb{Z} \cdot A$ for some dense linear order without endpoints. Thus every nonstandard model has an initial segment of Natural numbers followed by nonstandard numbers all appearing in an unbounded dense linearly ordered collection of what are called integer blocks or $\mathbb{Z}$-blocks. What I realized (someone else must've realized this too so please mention references if you know of any) is that if Polignac's conjecture turned out to be false, then we'd have the following strong limitation on the number of primes appearing in $\mathbb{Z}$-blocks.</p> <p><BLOCKQUOTE> <B>($\mathbb{N} \vDash \lnot PC$) If $M$ is a model of PA and is $\Sigma^0_1$-equivalent to the theory of $\mathbb{N}$, then $M$ can have at most one prime appearing in any $\mathbb{Z}$-block</B>: If not, then for some $d \in \mathbb{N}$, there would be a pair of nonstandard numbers that $M$ would view as two consecutive primes a distance $d$ apart. Since this occurs in a $\mathbb{Z}$-block, for any true Natural number $n$, the model $M$ thinks that there is a pair of consecutive primes greater than $n$ a distance $d$ apart. Then by $\Sigma^0_1$-elementarity, $\mathbb{N}$ would think the same thing so $\mathbb{N}$ would have unboundedly many pairs of consecutive primes a distance $d$ apart, making Polignac's conjecture true (in the standard model). </BLOCKQUOTE></p> <p>My question concerns the other models of PA: <BLOCKQUOTE> Can we prove that there is a nonstandard model of PA having a $\mathbb{Z}$-block with at least two primes? Even better, can we prove that there is a model of PA with unboundedly many $\mathbb{Z}$-blocks having at least two primes? </BLOCKQUOTE></p> http://mathoverflow.net/questions/51378/implication-of-polignacs-conjecture-on-prime-distribution-in-models-of-pa/51409#51409 Answer by SJR for Implication of Polignac's conjecture on prime distribution in models of PA SJR 2011-01-07T16:12:05Z 2011-01-07T16:12:05Z <p>For simplicity, take $d=2$. Then the the existence of a model of PA with at least one non-standard pair of twin primes is equivalent to the assertion </p> <p>For all (fixed, standard) primes $p$ the sentence <code>$$\phi_p:\forall x&gt;p,\,\,\, x \textrm{ is not prime or } x+2 \textrm{ is not prime }$$</code> is not provable in PA.</p> <p>Is it reasonable to spend lots of time hunting for a proof of this before the twin prime conjecture is resolved? My guess is "no" and here is why. </p> <p>All known constructions of non-standard models of PA depend in some way on an oracle who can determine which sentences are consistent with PA, or who can determine which sets are and are not members of some non-principal ultrafiter. I have no objections to such arguments, but it is well to be clear about the awesome powers of such an oracle: Relative to where we are, this is the point of view of eternity. It would be remarkable indeed if any statement of elementry number theory could be derived from such general constructions, and to my knowledge, none ever has.</p> <p>There is an analogy here with a paragraph in Hardy and Wright's number theory text. Let $c$ be the constant $.020300500000007\ldots$. The point is that the definition of $c$ depends on foreknowledge of the sequence of primes. Using $c$ we can give a very simple formula for the $n$th prime, which is, as Hardy remarks, completely useless for proving things about primes. </p> <p>In the same vein, there is a frontspiece to a book, I think by Mahler, that says:</p> <pre><code> If you want to make sausage you have to put some pork in the grinder. </code></pre> <p>It is dangerous to say never, and in spite of Tennenbaum's theorem, there might come a day when some representation of models of PA is discovered that allows one to get information about these models from some source other than the Peano axioms... but as far as I know, that day has not arrived. The closest thing to such a representation theorem I have ever seen is an unpublished theorem of Tennenbaum, proving that every countable model of PA can be embedded in $\mathbb{R}^{\omega}$ modulo the cofinite filter: In other words, you can think of the elements of models of PA as germs at infinity of sequences of real numbers. I once asked Greg Cherlin about the usefulness of this representation. His response was "There is no free lunch."</p>