Prime Factorization in Models of PV${}_1$

Abstract

Assuming that no family of polynomial-size Boolean circuits can factorize a constant fraction of all products of two $n$-bit primes, we show that the bounded arithmetic theory ${\text{PV}}_1$, even when augmented by the sharply bounded choice scheme $BB(\hat{I}{\pounds }_0^b)$, cannot prove that every number has some prime divisor. By the completeness theorem, it follows that under this assumption there is a model $M$ of ${\text{PV}}_1$ that contains a nonstandard number $m$ which has no prime factorization.