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(Σ^b_0)$, 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.
Fields of Study & Subjects
Advanced Mathematical Theories
Matrix Theory and Algorithms
Advanced Differential Equations and Dynamical Systems
Publication details
- Journal / source
- Logical Methods in Computer Science
- Publisher
- Centre pour la Communication Scientifique Directe (CCSD)
- Volume
- Volume 22, Issue 2
- Publication date
- 7 April 2026
- Language
- EN