Prime Factorization in Models of PV$_1$
This addresses a foundational issue in computational complexity and mathematical logic, specifically for researchers in bounded arithmetic and cryptography, by linking cryptographic assumptions to limitations in formal proof systems.
The paper tackles the problem of proving the existence of prime factorizations within the bounded arithmetic theory PV$_1$, showing that under a cryptographic hardness assumption, PV$_1$ cannot prove that every number has a prime divisor, leading to a model with a nonstandard number lacking prime factorization.
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.