ALCOMFT-TR-02-122

Albert Atserias
Improved Bounds for the Weak Pigeonhole Principle and Infinitely Many Primes from Weaker Axioms
Barcelona. Work package 4. May 2002.

Abstract: We show that the known bounded-depth proofs of the Weak Pigeonhole Principle PHP²ⁿ_n in size n^O(log(n)) are not optimal in terms of size. More precisely, we give a size-depth trade-off upper bound: there are proofs of size n^{O(d(log(n))2/d)} and depth O(d). This solves an open problem of Maciel, Pitassi and Woods (2000). Our technique requires formalizing the ideas underlying Nepomnja\vs\vcij's Theorem which might be of independent interest. Moreover, our result implies a proof of the unboundedness of primes in I\Delta₀ with a provably weaker `large number assumption' than previously needed.

Postscript file: ALCOMFT-TR-02-122.ps.gz (62 kb).