Prime Factorization in Models of PV$_1$

1. Problem Statement

The paper addresses a fundamental question in bounded arithmetic and computational complexity: Can the theory $PV_1$ (and its extension with the sharply bounded choice scheme, $PV_1 + BB(\Sigma^b_0)$) prove that every integer $x \ge 2$ has a prime divisor?

• Context: The theory $PV_1$ is a first-order extension of Cook's theory $PV$, characterized by induction restricted to polynomial-time predicates. It is known that stronger theories, such as $S^1_2$, can prove the existence of prime divisors (and thus prime factorization) using the principle $\Sigma^b_1$-LMAX (maximization). However, $PV_1$ lacks this principle unless $NP \subseteq P/poly$.
• The Question: Does $PV_1$ (even augmented with $BB(\Sigma^b_0)$) suffice to prove the sentence PrimeFactor:
  $$(\forall x \ge 2)(\exists y \le x)(2 \le y \land y|x \land (\forall z \le y)(z|y \to (z=1 \lor z=y)))$$
  If not, it implies the existence of a model of $PV_1$ containing a "nonstandard" number that has no prime factorization.

2. Methodology

The author employs a proof by contradiction utilizing the KPT Witnessing Theorem (Krajíček, Pudlák, and Takeuti, 1991) and concepts from complexity theory regarding the hardness of integer factorization.

A. The KPT Witnessing Theorem

The core technical tool is the KPT theorem, which states that if a theory like $PV_1$ proves a $\forall\exists\forall$ sentence (like PrimeFactor), then there exists a polynomial-time "student" algorithm $s$ that, in an interactive protocol with a "teacher," can find a witness for the existential quantifier.

• Protocol: The student $s$ proposes candidates $y_i$. The teacher $t$ responds with counterexamples $z_i$ if the candidate is incorrect.
• Guarantee: If the theory proves the statement, the student is guaranteed to find a correct witness after a constant number of rounds $c$, regardless of the teacher's strategy (provided the teacher is "correcting").

B. The Hardness Assumption

The paper assumes a standard cryptographic hypothesis:

Assumption: No family of polynomial-size Boolean circuits can factorize a constant fraction of all products of two $n$-bit primes.

C. The Strategy: Constructing a "Hard" Teacher

To disprove the provability of PrimeFactor, the author constructs a specific teacher $t$ that simulates a hard factorization problem:

1. Input: The teacher receives an input $x = p_1 \cdot p_2 \cdot \dots \cdot p_d$ (product of distinct primes).
2. Interaction: The student proposes divisors $y_i$.
3. Teacher's Logic:
   • If $y_i$ is a prime factor, the teacher confirms it.
   • If $y_i$ is composite, the teacher computes the GCD of $y_i$ with "obvious numbers" (numbers derived from previous interactions via GCD and division).
   • If no obvious divisor is found, the teacher splits $y_i$ roughly in half (e.g., $z_i = p_{i_1} \dots p_{i_{\lfloor l/2 \rfloor}}$).
4. The Contradiction: The author proves that if $PV_1$ could prove PrimeFactor, the polynomial-time student $s$ would be able to interact with this teacher and eventually output a prime factor. However, the structure of the teacher's responses forces the student to effectively factorize the product of primes. Under the hardness assumption, no polynomial-time algorithm (and thus no polynomial-size circuit) can succeed with non-negligible probability.

D. Handling $BB(\Sigma^b_0)$

For the extended theory $PV_1 + BB(\Sigma^b_0)$, the author uses an extension of the KPT theorem (Cook and Thapen, 2006). Here, the student can output a sequence of candidates simultaneously. The author defines a parallel teacher that replies coordinate-wise to these sequences. A key lemma shows that the number of "obvious sets" (atoms in the field of sets generated by the interaction) grows slowly enough that a sequential student can simulate the parallel one, reducing the problem back to the standard factorization hardness.

3. Key Contributions and Results

Main Theorem

Assuming the average-case hardness of factoring products of two $n$-bit primes against non-uniform polynomial-time adversaries:

1. Unprovability in $PV_1$: The theory $PV_1$ does not prove PrimeFactor.
2. Unprovability in $PV_1 + BB(\Sigma^b_0)$: The theory $PV_1 + BB(\Sigma^b_0)$ does not prove PrimeFactor.

Model Existence

By the completeness theorem, the unprovability implies the existence of a model $\mathcal{M}$ of $PV_1$ (or $PV_1 + BB(\Sigma^b_0)$) containing a nonstandard element $m$ such that:

• Every divisor of $m$ in $\mathcal{M}$ has a proper divisor in $\mathcal{M}$.
• $m$ has no irreducible divisors and thus no prime factorization within the model.
• This implies that models of these theories are not necessarily "positive parts of a Furstenberg domain" (a domain where every non-unit has an irreducible divisor).

Hierarchy Separation

The paper establishes a strict separation between three consecutive theories in Buss's hierarchy under a single cryptographic assumption:
$$PV_1 \prec PV_1 + BB(\Sigma^b_0) \prec S^1_2$$

• $PV_1$ cannot prove PrimeFactor.
• $PV_1 + BB(\Sigma^b_0)$ cannot prove PrimeFactor.
• $S^1_2$ can prove PrimeFactor.
• This improves upon previous results (e.g., Cook-Thapen) by separating $PV_1 + BB(\Sigma^b_0)$ from $S^1_2$ using a single, natural assumption about factoring.

4. Significance

1. Connecting Cryptography and Logic: The paper provides a rigorous link between the average-case hardness of integer factorization (a cornerstone of modern cryptography) and the logical strength of bounded arithmetic theories. It demonstrates that the inability to factor numbers efficiently is equivalent to the inability of these weak theories to prove basic number-theoretic facts.
2. Refining the Hierarchy: It clarifies the boundary between $PV_1$, $PV_1 + BB(\Sigma^b_0)$, and $S^1_2$. Specifically, it shows that the sharply bounded choice scheme ($BB(\Sigma^b_0)$), while powerful, is insufficient to recover the full power of $S^1_2$ regarding prime factorization.
3. Model Theory Implications: The result guarantees the existence of "pathological" models of arithmetic where unique factorization fails for nonstandard numbers, providing concrete examples of how computational limitations manifest in logical models.
4. Open Questions: The author raises questions about whether similar assumptions can separate higher levels of the polynomial hierarchy (e.g., $S^1_2$ vs. $T^1_2$) and whether the failure of factorization implies the failure of the injective weak pigeonhole principle ($iWPHP$) in the same models.

Summary

Ondřej Ježil's paper proves that under standard cryptographic assumptions, the theory $PV_1$ (even with the sharply bounded choice scheme) is too weak to prove that every number has a prime divisor. This is achieved by showing that a proof of such a statement would yield a polynomial-time algorithm capable of factoring a constant fraction of semiprimes, contradicting the assumed hardness of the factorization problem. Consequently, there exist models of these theories where nonstandard numbers lack prime factorizations.