Prime Factorization in Models of PV 1

Ondřej Ježil · 2025

Read Prime Factorization in Models of PV 1 by Ondřej Ježil (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-14516.txt.

Introduction

Ondřej Ježil connects prime factoring hardness to the limits of a weak arithmetic theory, in this 2025 paper. The theory, called PV1, formalizes reasoning about fast computations. The question is whether it can prove that every number has a prime divisor. Ježil assumes no small circuit family can factor a constant share of products of two large primes.

Under that assumption, even PV1 boosted with a sharply bounded choice scheme cannot prove the divisor claim. By a classic logic theorem, some model of the theory then holds a nonstandard number with no prime factorization at all. The result ties a concrete cryptographic hardness guess to a sharp boundary in proof strength. It also gives a test case for what bounded arithmetic can and cannot certify.

Catalog record

CREATOROndřej Ježil
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE38 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-14516

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Prime Factorization in Models of PV 1 \text{PV}_{1} Thanks: This work has been supported by Charles University Research Center program No. UNCE/24/SCI/022, the project SVV-2025-260837 and by the GA UK project No. 246223. Ondřej Ježil Abstract . Assuming that no family of polynomial-size Boolean circuits can factorize a constant fraction of all products of two n n -bit primes, we show that the bounded arithmetic theory PV 1 \text{PV}_{1} , even when augmented by the sharply bounded choice scheme B ​ B ​ ( Σ 0 b ) BB(\Sigma^{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 M of PV 1 \text{PV}_{1} that contains a nonstandard number m m which has no prime factorization. Jul. 01, 2025Apr. 07, 2026 † † lmcs-doi: Volume 22, Issue 2, Paper 1 1. Introduction Bounded arithmetic is a collective name for a family of first-order theories, which are weak fragments of Peano arithmetic, with strong connections to complexity theory. Their axiomatization usually consists of some basic universal theory describing the recursive properties of the function and relation symbols in the language of the theory, which usually extends the language of Peano arithmetic L_{PA}=\{0,1,+,\cdot,\leq\} , and an induction or some other scheme for a class of formulas whose expressivity corresponds to some computational complexity class. For more details about the motivation behind the study of these theories, we refer the interested reader to [ 15 ] and [ 2 ] which are monographs treating bounded arithmetic in depth. In this work, we are concerned with provability in the theory \text{PV}_{1} , introduced in [ 12 ] as a first-order extension of Cook’s theory PV [ 4 ] , which can be understood in a well-defined sense as a theory of arithmetic with induction accepted only for polynomial-time predicates. Its language contains a function symbol for each polynomial-time algorithm. It is known that the theory \text{PV}_{1} and its extensions prove many fundamental results of algebra, complexity theory and number theory [ 8 , 16 , 11 , 7 , 9 , 5 , 17 ] . In [ 9 ] it was first observed that the theory S^{1}_{2} proves that every number has a prime divisor: taking the maximal k such that x can be written as a product of k numbers greater than 1 yields the prime factorization of x . The logical principle underlying this argument \Sigma^{b}_{1}\text{-LMAX} gives the axiomatization of S^{1}_{2} over the base theory \text{PV}_{1} , and is not available in \text{PV}_{1} itself unless \text{NP}\subseteq\text{P}/poly [ 12 ] . In this work we show, assuming the hypothesis that non-uniform polynomial-time algorithms cannot factor a constant fraction of all multiples of two n -bit primes, for any n\in\mathbb{N} , that \text{PV}_{1} does not prove that every number has a prime divisor. That is, the PV -sentence PrimeFactor : (\forall x\geq 2)(\exists y\leq x)(2\leq y\land y\mid z\land(\forall z\leq y)(z\mid y\to(z=1\lor z=y))) cannot be proved in the theory \text{PV}_{1} even when extended by the sharply bounded choice scheme BB(\Sigma^{b}_{0}) , which is also known by the name sharply bounded collection. Regarding the plausibility of the assumption, the average-case hardness of factorization against non-uniform polynomial-time adversaries is a well established cryptographic assumption (see [ 6 , Section 2.2.4] ). Moreover, our argument allows for uniform sampling from any finite set of primes (see Theorem 7 ). In theory, this allows us to instead assume the average-case hardness of factoring where the inputs are taken as products of some subset of primes which are expected to be hard to factorize. Our main technical tool is the KPT witnessing theorem of [ 12 ] which extracts from the provability of \forall\exists\forall -sentences in \text{PV}_{1} a polynomial-time algorithm which outputs candidates for a witness of the existential quantifier, and each time the algorithm fails it obtains a counterexample to the correctness of the candidate. Such an algorithm is guaranteed to find a correct witness after obtaining a constant number of counterexamples. For the theory \text{PV}_{1}+BB(\Sigma^{b}_{0}) , we use an extension of the KPT witnessing theorem due to [ 3 ] , where the algorithm is allowed to output up to polynomially many candidates at once, but is still guaranteed to output a correct one in constantly many steps. To analyze the interactive computations which arise in the witnessing theorems we also use several observations about fields of sets, which are classes of subsets of a given set closed under finite intersections, finite unions and complements. The work is organized as follows, in Section 2 we briefly recall basic facts about bounded arithmetic and complexity theory, in Section 3 (Corollary 8 ) we prove the unprovability result for \text{PV}_{1} and finally in Section 4 we extend this result to unprovability in \text{PV}_{1}+BB(\Sigma^{b}_{0}) (Theorem 11 ). 2. Preliminaries We assume that the reader is acquainted with basic notions of complexity theory and first-order logic. We use the notation \lfloor-\rfloor for the floor function and the notation \lvert-\rvert for the binary length of a number. We will refrain from giving a formal definition of the theory \text{PV}_{1} which can be found in [ 12 , 15 ] , instead we will define the true universal theory T_{\text{PV}} , which is a proper extension of \text{PV}_{1} . All of our results hold even if we replace \text{PV}_{1} by T_{\text{PV}} , because the presence of true universal sentences does not affect the witnessing theorems. A function computed by a Turing machine is usually understood as a function on binary strings, but in bounded arithmetic we usually understand it as a function on numbers. {defi} Let PV be a language containing a function symbol f_{M} for every polynomial-time clocked machine M , the intended interpretation of each symbol in PV is then the function computed by the corresponding machine. The theory T_{\text{PV}} is then axiomatized by the set \{\varphi\text{ is a universal $\text{PV}$-sentence};\>\mathbb{N}\models\varphi\}. The language of the theory \text{PV}_{1} indeed satisfies the condition in the previous definition, the readers not familiar with the definition of \text{PV}_{1} can simply assume the language of T_{\text{PV}} is the minimal language satisfying the condition. We will from now on use PV to denote the language of \text{PV}_{1} and we will use the term PV -symbol to either mean a function symbol in PV or the predicate g(x_{1},\dots,x_{k})=1 , where g is a function symbol in PV . 2.1. Student-teacher protocols In this section, we will recall a formal definition of student-teacher protocols, which are sometimes called counterexample computations [ 13 ] . This notion is usually left undefined and is simply used as a figure of speech, but we will manipulate these protocols in a non-trivial way and having a formal definition helps the clarity of the arguments. {defi} A student-teacher protocol (or just a protocol ) is a triple (s,t,c) , where c\geq 1 and s,t:\mathbb{N}\to\mathbb{N} . Given a protocol (s,t,c) and a number x we define the computation of the protocol (s,t,c) on the input x as the (2c-1) -tuple: (y_{1},z_{1},y_{2},z_{2},\dots,y_{c-2},z_{c-2},y_{c-1},z_{c-1},y_{c}) where \displaystyle y_{1} \displaystyle=s(x), \displaystyle z_{1} \displaystyle=t(x,y_{1}), \displaystyle y_{i} \displaystyle=s(x,z_{1},\dots,z_{i-1}),\text{ for }1<i\leq c, \displaystyle z_{i} \displaystyle=t(x,y_{1},\dots,y_{i}),\text{ for }1<i<c. We shall sometimes call the function s the student , the

Read the complete text