一句话:在特定密码学困难性假设下,PV₁ 即使加入 BB(Σ^b_0) 也不能证明每个数有素因子,并由此得到非标准模型。
本文研究有界算术理论 PV₁ 能否证明每个自然数都有素因子。作者假设不存在多项式大小的布尔电路族能分解所有两个 n 比特素数乘积中的常数比例,在此假设下证明:即使将 PV₁ 加强为加入 sharply bounded choice scheme BB(Σ^b_0) 的理论,仍不能证明“每个数都有某个素因子”。随后利用完备性定理,得到该假设下存在 PV₁ 的模型 M,其中含有一个非标准数 m,而 m 没有任何素因子分解。该结果将分解困难性假设与有界算术的证明能力及非标准模型的存在性联系起来。
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.