Induction, the infinitude of the primes, and workaday number theory - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T06:33:32Z http://mathoverflow.net/feeds/question/59262 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/59262/induction-the-infinitude-of-the-primes-and-workaday-number-theory Induction, the infinitude of the primes, and workaday number theory David Feldman 2011-03-23T04:38:29Z 2011-03-24T01:35:06Z <p>There are various open problems in the subject of logical number theory concerning the possibility of proving this or that well-known standard results over this or that weak theory of arithmetic, usually weakened by restricting the quantifier complexity of the formulas for which one has an induction axiom. It particular, the question of proving the infinitude of the primes in Bounded Arithmetic has received attention.</p> <p>Does this question make known contact with "workaday number theory" - number theory not informed by concepts from logic and model theory? I understand that proof of the infinitude of the primes in bounded arithmetic could not use any functions that grow exponentially (since the theory doesn't have the power to prove the totality of any such function). So especially I mean to ask:</p> <p>1) If one had such a proof, would it have consequences about the primes or anything else in the standard model of arithmetic? 2) If one proves that no such proof exists, would that have consequences... 3) Do any purely number theoretic conjectures if settled in the right way, settle this question of its kin? </p> <hr> <p>As a side question, I'd be interested to know the history of this question. I first heard about it from Angus Macintyre and that must have been 25 years ago.</p> http://mathoverflow.net/questions/59262/induction-the-infinitude-of-the-primes-and-workaday-number-theory/59286#59286 Answer by François G. Dorais for Induction, the infinitude of the primes, and workaday number theory François G. Dorais 2011-03-23T11:16:00Z 2011-03-24T01:35:06Z <p>First, let me discuss the precise open question and why it is interesting to logicians. Then I will discuss potential ramifications outside of pure logic.</p> <p>The main open question is whether the theory I&Delta;<sub>0</sub> can prove the existence of arbitrarily large primes. The theory I&Delta;<sub>0</sub> is the theory over the language of basic arithmetic ($0,1,+,\times,{\leq}$, together with their usual defining axioms) where induction is limited to bounded formulas (&Delta;<sub>0</sub> formulas): formulas wherein all quantifiers are of the bounded form $\forall x(x \leq t \rightarrow \cdots)$ and $\exists x(x \leq t \land \cdots)$ where $t$ is a term of the language possibly involving variables other than $x$. While this theory has been around for quite some time, one of the earliest papers studying this system in detail is Paris &amp; Wilkie <em>On the scheme of induction for bounded arithmetic formulas</em> [Ann. Pure Appl. Logic 35 (1987), no. 3, 261–302, <a href="http://www.ams.org/mathscinet-getitem?mr=904326" rel="nofollow">MR904326</a>]. The currently open question regarding the unboundedness of primes occurs there, probably for the first time in print.</p> <p>Why is this question interesting to logicians? There is a standard fact about the proof theory of &forall;&exist;-formulas which explains the interest. Over I&Delta;<sub>0</sub>, this fact takes the following form due to Parikh:</p> <p><strong>Fact.</strong> If I&Delta;<sub>0</sub> proves $\forall x \exists y \phi(x,y)$, where $\phi(x,y)$ is a bounded formula, then I&Delta;<sub>0</sub> proves $\forall x \exists y(y \leq t(x) \land \phi(x,y))$ where $t(x)$ is a term of the language (i.e. a polynomial in $x$).</p> <p>Thus, I&Delta;<sub>0</sub> cannot prove certain statements such as $\forall x \exists y (2^x = y)$ since $2^x$ grows faster than any polynomial. (Here, $2^x = y$ is an abbreviation for a bounded formula that expresses the properties of the exponential function $2^x$. That formula is rather complex, so I will not explain it here.) In fact, any proof that involves functions of exponential growth at intermediate stages cannot be formalized in I&Delta;<sub>0</sub> because of this. This applies in particular to Euclid's proof which takes a rather large product of primes relative to the input $x$ in order to prove that there is a prime larger than $x$. However, by Bertrand's Postulate, the formula $\forall x \exists y(\mathrm{prime}(y) \land y \geq x)$ does not by itself impose exponential growth. Thus, the fact leaves open the question whether some other proof of the infinitude of primes can be formalized in I&Delta;<sub>0</sub>.</p> <p>What are potential ramifications outside of logic? A natural question to ask about primes is whether there is some kind of efficient formula for producing large primes. (Cf. the <a href="http://michaelnielsen.org/polymath1/index.php?title=Finding_primes" rel="nofollow">Polymath 4 Project</a>.) One can ask further about the growth rate and the computational complexity of such a function. <a href="http://en.wikipedia.org/wiki/Proof_mining" rel="nofollow">Proof mining</a> techniques show that if I&Delta;<sub>0</sub> proves the infinitude of primes, then there must be a relatively simple function of moderate growth rate to produce large primes. In fact, there must be such a function that produces primes provably in I&Delta;<sub>0</sub>.</p> <p>The existence of such a function should not be a surprise. Indeed, the simple function $p(x)$ that returns the first prime greater than $x$ has very moderate growth rate by Bertrand's Postulate. However, the function produced by a proof of the unboundedness of primes in I&Delta;<sub>0</sub> will have other important characteristics. In particular, it will have rather low computational complexity. The precise relationship between I&Delta;<sub>0</sub> and computational complexity is a little subtle and I don't want to make this statement more precise here. (Some details were added below.) However, there are good reasons to believe that such a proof could yield a polynomial time computable function of moderate growth that produces large primes, which would be a major breakthrough.</p> <p>What can we say if there is no I&Delta;<sub>0</sub> proof of the existence of arbitrarily large primes? Well, for one thing, a model of I&Delta;<sub>0</sub> where primes are bounded would be a rather interesting object with potential applications to the structure theory of integral domains. However, it turns out that there is not much one can say here about the standard model, but the reason is subtle. </p> <p>The key problem is the definition of prime number. In the discussion above, I implicitly assumed the standard definition $\mathrm{prime}(x)$ iff $$x > 1 \land (\forall y, z \leq x)(x = yz \rightarrow y = 1 \lor z = 1).$$ However, there are other potential definition of primes. For example, one could define prime numbers as those which pass the <a href="http://en.wikipedia.org/wiki/AKS_primality_test" rel="nofollow">AKS primality test</a>. These various equivalent definitions are not necessarily equivalent over I&Delta;<sub>0</sub>. Therefore, it is possible that I&Delta;<sub>0</sub> fails to prove the existence of arbitrarily large "traditional primes" but that I&Delta;<sub>0</sub> does prove the existence of arbitrarily large "AKS primes." Since the standard model can't tell the difference between these two notions of primality, this could still give an efficient way to produce large primes as discussed above.</p> <hr> <p>Let me clarify the relationship between proofs in I&Delta;<sub>0</sub> and computational complexity. The polynomial hierarchy is closely tied to slightly different systems of bounded arithmetic, namely the systems $S^n_2$, $T^n_2$ pioneered by Sam Buss. Note that these are somewhat orthogonal to I&Delta;<sub>0</sub>. On the one hand, these systems include the smash function <code>$x \# y = 2^{|x||y|}$</code> which is not provably total in I&Delta;<sub>0</sub>. On the other hand, the amount of induction in these systems is even more restricted than in I&Delta;<sub>0</sub>. </p> <p>It is hard to give a precise relationship between time complexity and proofs in I&Delta;<sub>0</sub>. The claims I made above are rather based on the (admittedly optimistic) expected success of proof mining on a hypothetical proof the unboundedness of primes in I&Delta;<sub>0</sub>.</p> <p>In any case, there is an inherent weakness to this approach. Complexity theorists do not impose limits on the amount of induction they use in their proofs. For example, complexity theorists will freely use the equivalence of "traditional primes" and "AKS primes" in their arguments. Therefore, the existence of a simple way to generate large primes is not at all equivalent to the existence of a proof of the existence of arbitrarily large primes in I&Delta;<sub>0</sub> or other systems of bounded arithmetic.</p> http://mathoverflow.net/questions/59262/induction-the-infinitude-of-the-primes-and-workaday-number-theory/59308#59308 Answer by Dave Marker for Induction, the infinitude of the primes, and workaday number theory Dave Marker 2011-03-23T14:55:05Z 2011-03-23T14:55:05Z <p>Two comments:</p> <ul> <li><p>Work of Paris, Wilkie and Woods shows that we can prove the existence of infinitely primes, and indeed that there is always a prime between $n$ and $2n$, assuming $I\Delta_0+\forall x \exists y\ y=x^{|x|}$, where $|x|$ is the length of a binary expansion of $x$. So we know functions of exponential growth aren't necessary, but we are still using a function of super-polynomial growth. Actually, they proved that this theory implies a weak Pigeon-hole Principle which Woods had shown earlier implied the infinitude of primes.</p></li> <li><p>Another question in this spirit is whether $I\Delta_0$ proves that for any prime $p$ there is a non-square mod $p$. </p></li> </ul> <p>It is known that neither of these number theoretic results can be proved if the base theory is weakened to allow induction only for quantifier free formulas.</p>