# Implication of Polignac's conjecture on prime distribution in models of PA

Polignac's conjecture (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.

($\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: 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).

My question concerns the other models of PA:

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?

-
Could you clarify: are you asking the question still under the assumption of $\neg PC$, but interested in the nonstandard models of PA that may have additional $\Sigma^0_1$ facts? – Joel David Hamkins Jan 7 '11 at 12:54
For an answer to a dual version of your question, see Francois' answer to this question: mathoverflow.net/questions/30064/… – Joel David Hamkins Jan 7 '11 at 13:03
I was wondering if anyone had produced a model of PA where there were at least two primes in a $\mathbb{Z}$-block given the state of Polignac's conjecture. Of course, if Polignac's conjecture is true, then such a model is easy to produce by a standard compactness argument so I was working under the assumption of $\lnot PC$. – Jason Jan 7 '11 at 23:07

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

For all (fixed, standard) primes $p$ the sentence $$\phi_p:\forall x>p,\,\,\, x \textrm{ is not prime or } x+2 \textrm{ is not prime }$$ is not provable in PA.

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.

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.

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.

In the same vein, there is a frontspiece to a book, I think by Mahler, that says:

     If you want to make sausage you have to put some pork in the grinder.


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."

-
In a spirit similar to your comment on Tennenbaum's theorem, in Dales-Woodin "Super-real fields", models of arithmetic are coded into superreal fields. This is taken to mean that there is no hope of a reasonable classification of these fields, not that this gives a new way to establish facts about PA. (Def: A super-real field is the field of fractions of C(X)/P for some Tychonoff space X and some prime ideal P in C(X). This generalizes constructions of Gillman-Jerison, "Rings of Continuous Functions".) – Andrés E. Caicedo Jan 7 '11 at 21:22
+1: Wow, so this question really does remain wide open. – Jason Jan 7 '11 at 23:11
@SJR: The Tennenbaum result you mention needs the model of $PA$ to satisfy the $\Pi_1$ theory of $\BBb{N}$. A proof can be found in the following paper: J. Kennedy and S. Shelah, On embedding models of arithmetic of cardinality ℵ_1 into reduced powers. Fund. Math. 176 (2003), no. 1, 17–24. You can find a preprint at: math.helsinki.fi/logic/people/juliette.kennedy/KennShe728.pdf – Ali Enayat Jun 9 '11 at 3:55
@Ali Enayat: The paper you mention concerns embeddings of models of PA into $\mathbb{N}^\omega$ mod the cofinite filter. If you use $\mathbb{R}$ in place of ℕ then the situation changes, and in fact the result I mentioned is proved in Kennedy's Thesis. – SJR Jun 9 '11 at 4:32
@Ali: (....Continued) The main idea of the proof is that if $S$ is any finite set of quantifier-free formulas in the variables $\bar{x}$ that can be simultaneously satisfied in some model $M$ of PA, then $S$ can be satisfied in the real closure of $M$, and therefore in the reals, by the completeness of the theory of real closed fields. You can use this fact, and the diagram of $M$, to construct the embedding I mentioned. – SJR Jun 9 '11 at 4:58