Induction, the infinitude of the primes, and workaday number theory

2011-03-23T04:38:29Z

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.

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:

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?

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.

Answer by François G. Dorais for Induction, the infinitude of the primes, and workaday number theory

2011-03-23T11:16:00Z

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.

The main open question is whether the theory IΔ₀ can prove the existence of arbitrarily large primes. The theory IΔ₀ 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 (Δ₀ 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 & Wilkie On the scheme of induction for bounded arithmetic formulas [Ann. Pure Appl. Logic 35 (1987), no. 3, 261–302, MR904326]. The currently open question regarding the unboundedness of primes occurs there, probably for the first time in print.

Why is this question interesting to logicians? There is a standard fact about the proof theory of ∀∃-formulas which explains the interest. Over IΔ₀, this fact takes the following form due to Parikh:

Fact. If IΔ₀ proves $\forall x \exists y \phi(x,y)$, where $\phi(x,y)$ is a bounded formula, then IΔ₀ 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$).

Thus, IΔ₀ 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Δ₀ 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Δ₀.

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 Polymath 4 Project.) One can ask further about the growth rate and the computational complexity of such a function. Proof mining techniques show that if IΔ₀ 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Δ₀.

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Δ₀ will have other important characteristics. In particular, it will have rather low computational complexity. The precise relationship between IΔ₀ 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.

What can we say if there is no IΔ₀ proof of the existence of arbitrarily large primes? Well, for one thing, a model of IΔ₀ 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.

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 AKS primality test. These various equivalent definitions are not necessarily equivalent over IΔ₀. Therefore, it is possible that IΔ₀ fails to prove the existence of arbitrarily large "traditional primes" but that IΔ₀ 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.

Let me clarify the relationship between proofs in IΔ₀ 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Δ₀. On the one hand, these systems include the smash function $x \# y = 2^{|x||y|}$ which is not provably total in IΔ₀. On the other hand, the amount of induction in these systems is even more restricted than in IΔ₀.

It is hard to give a precise relationship between time complexity and proofs in IΔ₀. 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Δ₀.

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Δ₀ or other systems of bounded arithmetic.

Answer by Dave Marker for Induction, the infinitude of the primes, and workaday number theory

2011-03-23T14:55:05Z

Two comments:

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.
Another question in this spirit is whether $I\Delta_0$ proves that for any prime $p$ there is a non-square mod $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.

Induction, the infinitude of the primes, and workaday number theory - MathOverflow

Induction, the infinitude of the primes, and workaday number theory

Answer by François G. Dorais for Induction, the infinitude of the primes, and workaday number theory

Answer by Dave Marker for Induction, the infinitude of the primes, and workaday number theory