WorksComputer Science
Irreducibility Testing of Sparse Polynomials over Integers is NP-hard and Probabilistic Polynomial Time
Abstract
In this paper, we prove that irreducibility testing for sparse polynomials in is coNP-hard under deterministic polynomial-time many-one reductions. That is, there exists no polynomial-time irreducibility test algorithm unless . We also provide an upper bound for this problem by demonstrating that the same irreducibility testing problem lies in ; in other words, it can be solved in probabilistic polynomial time and, moreover, within polynomial space. The fact that relies on the quasi-Riemann hypothesis result of Cureton–Thorner and on the uniform effective prime-ideal bound by Frei–Sofos–Widmer just posted recently.
Introduction
Polynomial factorization is a central problem in algebraic and symbolic computation, and substantial progress has been made in developing efficient algorithms. This extensive research has produced effective randomized algorithms for polynomial factorization, which have significant applications in complexity theory, coding theory, and cryptography [21].
For dense univariate polynomials, factoring over finite fields admits randomized polynomial-time (Las Vegas) algorithms [3], and irreducibility testing (abbr. irreducibility) follows as a consequence. However, deterministic polynomial-time factorization over finite fields remains open. Over integers, factorization and irreducibility are deterministic in polynomial time via the seminal LLL algorithm [15]. When polynomials are instead given by compact representations such as straight-line programs or sparse (lacunary) sums, the complexity of factorization is surveyed in [11], and a retrospective on the algorithmic progress in polynomial factorization is given in [12].
In practical settings and in mathematical software like Maple, polynomials are typically represented in sparse form—that is, as lists of their exponents and coefficients. Factorization of sparse polynomials is quite different from that of dense ones. The simple example below illustrates that a reducible sparse polynomial can have an irreducible factor with exponentially many nonzero terms compared to the size of the original polynomial. Therefore, there exists no polynomial-time factorization algorithm for sparse polynomials.
Example 1. Let be an odd prime. Then
where each cyclotomic polynomial is irreducible over . The size of is . The polynomial contains nonzero terms, and its size grows exponentially relative to the input size of .
Recently, Mishra [17] proves that for every sufficiently large , there exists an with exactly nonzero coefficients such that every irreducible factor of over has more than nonzero coefficients. Thus, for such , every irreducible factor has a superpolynomial number of terms in .
Therefore, for sparse polynomials, the complexity of testing irreducibility can differ substantially from that of factoring, because a sparse polynomial may have irreducible factors that are dense, making straightforward enumeration of candidate factors infeasible. Based on the seminal work on the complexity of sparse polynomial operations [18], Kaltofen and Koiran [13] proved that irreducibility testing for bi-variate sparse polynomials over integers or sufficiently large finite fields is coNP-hard under randomized polynomial-time many-one reductions. In [4], a similar result is proved for arbitrary fields; precisely, irreducibility for bi-variate sparse polynomials over any field is coNP-hard under deterministic polynomial-time many-one reductions.
In this paper, we consider the following basic problem.
Problem SparseIrred. Given a polynomial in sparse form , of size bits, decide whether is irreducible in .
An instance of the problem is a polynomial given in sparse (supersparse) form, that is, as a list of its nonzero terms
where is the number of nonzero terms of and the degree of . Its size is
Only the logarithms of the exponents are charged, so a polynomial of exponentially large degree may still have an input of polynomial length; consequently, no polynomial-time algorithm may traverse term by term up to its degree. The decision problem is to decide, in time polynomial in , whether such an is irreducible in (equivalently, whether is reducible, i.e. for some nonunits ).
The computational complexity of testing irreducibility for univariate sparse polynomials has remained unresolved for a long time, as noted either explicitly or implicitly in [8, 13, 14, 19]. In [14], it was mentioned that “another interesting related question to which probably can be studied by the method of this paper (Hilbert irreducibility) is deciding irreducibility of sparse polynomials (in ).” In [13], it was mentioned that “the hardness of sparse irreducibility in remains open.” Open problem 7 in [19] implicitly assumed irreducibility over as an open problem. Furthermore, the irreducibility of univariate sparse polynomials cannot be deduced from the CoNP-hardness of testing irreducibility for bivariate sparse polynomials because, in [13], the polynomials studied have the special shape with and , and is irreducible precisely when and are coprime.
Main Result
In this paper, we present lower and upper bounds for the complexity question of deciding the irreducibility of sparse polynomials over the integers. Specifically, we establish the following result (Refer to Theorem 4 and Theorem 10).
Theorem 2. SparseIrred is coNP-hard under deterministic polynomial-time many-one reductions. Equivalently, reducibility in is NP-hard under the same reductions. Furthermore, SparseIrred, that is, SparseIrred can be decided in probabilistic polynomial (PP) time and also in polynomial space (PSPACE).
As a consequence of the CoNP-hardness result, a polynomial-time irreducibility test implies . By Example 1, the PSPACE complexity of testing irreducibility is not immediate because the factors of may have size exponential in that of .
It is worth noting that the proof establishing SparseIrred relies on the recent quasi–Riemann hypothesis result of Cureton–Thorner [7] as well as the uniform effective prime-ideal estimate due to Frei–Sofos–Widmer [10].
Remark 3. Note that PP and BPP are different. BPP (Bounded-error Probabilistic Polynomial time) means that the algorithm answers correctly with probability . PP means that the algorithm answers correctly with probability . It is widely believed that .
It should be noted that whether testing irreducibility for univariate sparse polynomials over finite fields is coNP-hard is still an open question.
Lean Formalization
The accompanying Lean 4 development covers both the hardness results of Theorem 4 and the integer upper bound of Theorem 10, together with their internal mathematical derivations and machine implementations. The source code, build instructions, and theorem correspondence are hosted at https://github.com/MechMath/sparse-irr. The project uses Lean 4.34.0-rc2, mathlib [20], and complexitylib [6].
For the hardness result, the specialized Filaseta–Ford–Konyagin [9] argument, the sparse reduction, its polynomial running time and output length, and the one-query oracle reduction are proven without additional mathematical hypotheses. For the upper bound (Theorem 10), the development proves the discriminant and exceptional-prime estimates, the modular root–prime-ideal correspondence, the average estimate, the cutoff and decision criterion, and the deterministic and strict-majority machine constructions. The effective prime-ideal counting result obtained from [7, 10] and the polynomial-time primality result of [1] remain explicit theorem hypotheses; the paper’s conclusions are derived from them.
All project proofs are free of project-specific axioms and sorry placeholders; the audited dependency closure uses only propext, Classical.choice, and Quot.sound. This audit does not discharge the explicitly stated literature parameters of the upper bound. Appendix A gives the principal declarations, the precise machine specifications, and reproducibility details.
Irreducibility Test of Sparse Polynomials over Integers is CoNP-hard
We will prove the following theorem in this section.
Theorem 4. Irreducibility for sparse polynomials in is coNP-hard under deterministic polynomial-time many-one reductions. Equivalently, reducibility in is NP-hard under the same reductions. Irreducibility is NP-hard under polynomial-time Turing reductions using one irreducibility query. Consequently, a polynomial-time irreducibility test implies P = NP.
The theorem is proved by reducing an exact-3-CNF satisfiability formula to the sparse polynomial , where is built from the literal polynomials and (Refer to Lemma 5) so that the roots of unity of encode exactly the satisfying assignments. A gap theorem obtained by specializing the simultaneous-approximation and polynomial-lifting mechanism of Filaseta–Ford–Konyagin [9] makes irreducible precisely when is unsatisfiable, and every constructed polynomial is presented by a canonical sparse table of polynomial length.
The exact-3-CNF reduction
The reduction uses exact-3-CNF satisfiability, with repeated literals permitted. A polynomial with a positive degree is irreducible in if and only if it is primitive and irreducible in . We specify the full reduction, including malformed source strings and the constant/unit convention.
The first reduction step follows [18 Theorem 5.1]. Note that our construction of polynomial is different from that in [18 Theorem 5.1]. Also, a new conclusion about has been added.
Lemma 5. Let be a nonempty CNF formula with at least one occurring variable. Number those variables , and let be the -st odd prime. Put and . For a positive or negative literal on variable put, respectively,
Let be the product of the literal polynomials in clause and form the Laurent polynomial
Let , , and . Then , , , , where
and
For every integer , the polynomial has a root of unity if and only if is satisfiable.
Proof. All and are odd. Hence and . No vanishes, so . The relation makes its coefficients at equal and nonzero. Consequently, has degree , constant coefficient , and .
Let and . Then . The polynomial vanishes at exactly when . The geometric identity shows that vanishes exactly when : at its value is . Declare variable true when . A clause is true precisely when one of its literal polynomials vanishes, hence when . Because and have real coefficients, and . Thus, exactly when this assignment satisfies . Conversely, a chosen truth assignment is realized by some : by the Chinese remainder theorem choose for true variables and for false ones. Since is invertible modulo , the resulting is exactly in the true case. As and has precisely the -th roots of unity as roots, this proves (2).
If is satisfiable, its witness satisfies , and hence . Conversely, suppose for an arbitrary root of unity. Every conjugate of is again a root of unity and is a root of , because . For each such ,
Here and . The value is an algebraic integer: every Laurent monomial in the root of unity is an algebraic integer. Its field norm is the product of the displayed conjugate values. If , that norm is a nonzero integer, but its absolute value is at most , a contradiction. Thus . The equation now gives , so (2) shows that is satisfiable.
A Criterion for Irreducibility
For a nonzero , put , , and . The star operation is multiplicative on polynomials with nonzero constant coefficient. The coefficient of in is . The polynomial has the same weight and term count as . We use the following criterion to test whether a polynomial is irreducible.
Theorem 6. Let , , and . Assume
Set , , and . If
then, for and every ,
If, in addition, has no complex root of unity, then is irreducible in .
The derivation below specializes the simultaneous-approximation and polynomial-lift mechanism of Filaseta–Ford–Konyagin [9] to this palindromic family.
Lemma 7. Let and have . Under (3), there are integers and such that , and, with , each has a unique integer with
In particular, all residues in (5) are integers strictly between and .
Proof. Put . Partition into half-open boxes of side . Apply the pigeonhole principle to the points
The difference of two indices gives and integers such that for every . Since , one may take . Write , with . Then
The assumption gives
As , (6) yields . For , this is less than . Consequently . Two different multiples of cannot both give a residue in , establishing uniqueness.
Proof of Theorem 6. Put . Inequality (3) gives , so is monic of degree and . Palindromicity gives
The two terms of do not meet the support of . Thus
Suppose . The nonzero constant term of forces . Equality of degrees gives . Comparing coefficients of in the products and using (9) gives
because each nonzero integer coefficient has square at least one. Take . By (9)–(10) and invariance of term count under star,
The support is nonempty and lies in . Apply Lemma 7 to obtain .
For any polynomial with support in , define its shifted lift in by
Here by (5), so . Every -degree is below and
Every product of two such lifts has -degree strictly below . On the -module spanned by monomials with , substitution is injective: distinct pairs give distinct integers . Using (13) and the equality therefore gives
We determine the lift of . The estimate (7), with , also gives , hence and . Thus the two terms of both have -degree zero, and their lift is . The support of lies in the interval of length . All its lifted -degrees lie in by (5). If two of its terms had distinct -degrees, their original exponents would differ by more than , contrary to their difference being at most . Hence they share one -degree . Because , the exponent occurs, so for some integer the high lift is . Also : if , then since ; if , the same inequality follows from . Consequently
Let , , . Then , and (15) equals , where
We prove that is a prime element of . Since and , one has . In the UFD , is prime. It does not divide the leading coefficient of in . It divides every other coefficient: the intermediate coefficients vanish, and the constant coefficient is . Since
does not divide that constant coefficient. The two nonzero coefficients and are coprime in . Indeed, a nonconstant common irreducible factor other than would divide both and , contradicting their coprimality over ; a common factor is excluded by , , and . A common integer prime is excluded by the coefficient of . Thus is primitive as a polynomial in over . Eisenstein’s criterion at , followed by Gauss’s lemma, makes irreducible in . Since is a UFD, is prime.
From (14)–(15), divides . Primality gives
Suppose first that . Substitute in this divisibility. (13) and (15) give
Because , the polynomials and are coprime. Euclid’s lemma applied to (18) gives in . Their degrees are both , so for an integer . By (10), ; hence and . In the second case of (17), the same argument gives with . The star operation is involutive on polynomials with nonzero constant term, so . This proves (4).
Now assume has no root of unity. From (8),
The exponent is positive. If and had a common nonconstant factor over , that factor would have a complex root . Since , . (19) then gives or . In either case is a root of unity, contradicting the assumption. Thus . Both polynomials are primitive because is monic and , so they have no nonunit common divisor in .
Finally suppose in with both factors nonunits. As is monic, are nonconstant. Their constant coefficients are nonzero because . Put . Multiplicativity of star gives . By (4), or . In the first case cancellation of from gives . Then divides both and , contrary to coprimality. In the second case cancellation of from gives , and divides both and , again a contradiction. Hence no factorization into nonunits exists; is irreducible in . □
Proof of Theorem 4
We first present a result about primes.
Lemma 8. Let , with , and let count the primes at most . With ,
If is the zero-indexed -th prime and , then and .
Proof. At the first assertion is . Suppose . Fix and a prime ; set . Unique factorization gives . Counting multiples of in factorials gives . Hence
Each summand is 0 or 1: adding the remainders of and modulo causes at most one carry. Thus . No prime greater than divides , so . The binomial theorem yields . Also and each , which proves .
Fix , put and , and suppose . The first assertion and imply . Since for integers by induction,
The strict inequality follows from . This contradiction gives , hence . All primes after 2 are odd, so . □
The following lemma provides an estimate for the size of .
Lemma 9. For an exact-3-CNF input string of length , the canonical sparse table of , with
can be computed in deterministic time polynomial in . It has total binary length polynomial in , and (20) satisfies (3).
Proof. We use Lemma 8. Its polynomial bound suffices for the construction.
Only occurring variables are numbered, so . Put . Lemma 8 bounds all by . Trial division of integers at most enumerates the first odd primes in polynomial time; primality need not be treated as a unit-cost operation. Each literal polynomial has at most terms. An exact-3 clause expands to at most raw terms, and to at most raw products, where is the number of clauses. Sorting exponents, summing equal coefficients and deleting zeros take polynomial time in the number and bit length of these raw terms. A coefficient of has absolute value at most , and its support has at most elements. Hence
so the numerical value of is polynomial in .
The integer is a product of numbers at most , so its binary length is at most . Every exponent in a clause has magnitude at most , every exponent in has magnitude at most , and . The binary length of is therefore polynomial in . Binary arithmetic computes (20) with bits. The table of has no more than entries, and all exponents have at most bits. No dense array of length or is formed.
For the numerical inequality, the exponent in (3) is , hence its power of is . Since and ,
For instance, and prove the displayed comparison directly. This completes both the algorithmic and threshold assertions.
Proof of Theorem 4. Take a valid nonempty 3-CNF formula with an occurring variable, and construct by Lemmas 5 and 9. If is unsatisfiable, (2) makes and coprime over , hence they have no nonunit common divisor over . Lemma 5 says that has no root of unity, and Lemma 9 supplies (3). Every hypothesis of Theorem 6 is now met, so is irreducible in .
If is satisfiable, (2) supplies an -th root of unity with . Let be the minimal polynomial of over , where is its order. The standard cyclotomic identity says is monic, has positive degree and divides both and in : division by the monic is integral, and a rational remainder vanishing at must be zero by minimality. Therefore . Since , the cyclotomic polynomial divides and has degree at most . The polynomial is monic of degree because ; its quotient by has positive degree. Thus is a product of two nonunits in .
On malformed 3-CNF strings, output the encoding of . For the empty formula or a formula with no occurring variable, evaluate its clauses directly and output in the satisfiable case, otherwise. These branches are polynomial-time. Consequently this total map sends 3-UNSAT instances exactly to irreducible sparse polynomials, and sends 3-SAT instances exactly to reducible sparse polynomials. The first equivalence is a many-one reduction from the coNP-complete language 3-UNSAT; the second is a many-one reduction from the NP-complete language 3-SAT. The coding can use the canonical binary sparse representation: the computed sorted table has nonzero coefficients and distinct exponents, and a polynomial-time parser rejects noncanonical encodings.
For the Turing claim, a deterministic polynomial-time machine computes the same , asks an irreducibility oracle about its encoding once, and negates the answer. This decides 3-SAT. The query is made on a positive degree polynomial (also in the degenerate branches), so reducible is exactly the negation of irreducible there. If irreducibility were in P, the same computation would put 3-SAT in P, and NP-completeness of 3-SAT would give P = NP.
Irreducibility of Sparse Polynomials over Integers is PP
In this section, we will prove
Theorem 10. Sparse univariate irreducibility over integers satisfies
.
Note that both complexities are for deterministic algorithms.
The proof shows that a fixed zero-free half-plane for the Dedekind zeta functions of all number fields implies . Applying the zero-free theorem of Cureton–Thorner [7] and the uniform effective prime-ideal estimate of Frei–Sofos–Widmer [10], gives the asserted inclusion without assuming GRH. The main steps of the proof include: a weighted modular root count detects both distinct factors and repeated factors, an explicit cutoff has bits, and a deterministic streaming algorithm uses polynomial space. A direct majority-machine construction proves the stronger PP bound.
Let be a sparse polynomial given in (1) with bit size , degree , and . Then and are . Natural logarithms are denoted by , binary logarithms by .
We use ring-theoretic irreducibility in . Thus, a nonconstant input of content greater than one is reducible. For primitive nonconstant inputs, Gauss’s lemma identifies irreducibility over and . The zero polynomial and units are not irreducible; if constants are allowed, the irreducible constants are the signed rational primes. These cases are handled separately. In the main argument assume only
In particular, neither squarefreeness nor is assumed.
Quasi-Riemann hypothesis for Dedekind zeta functions
The proof uses the recent result on quasi-Riemann hypothesis for Dedekind zeta functions by Cureton–Thorner [7] and a result of Frei–Sofos–Widmer [10].
Cureton–Thorner [7] prove that, for every number field ,
The public formalization [2] contains the statement for an arbitrary type carrying field and number-field structures, with the analytic continuation agreeing with the usual Dedekind zeta function on .
Thus, the unconditional application in this note explicitly relies on (24) as an external theorem with a published proof and formalization. If that input is omitted, the reduction below remains a theorem conditional on a uniform positive zero-free gap. It must not be described as a proof from only the older references in the original manuscript.
For a number field , let , let be its absolute discriminant, and let count its nonzero prime ideals of absolute norm at most . Frei–Sofos–Widmer [10] prove that, if has no zeros in , then
where is an effectively computable positive absolute constant. Their theorem is stated for a normal extension and a conjugacy class. Apply it to the identity extension . This is normal regardless of whether is normal, and gives (25) directly. No Galois closure is introduced.
Combining (24) and (25), fix once and for all an effectively computable integer such that
for every number field and every . The integer is a fixed machine constant, independent of the input polynomial. No numerical value for it is asserted here; its effective existence is part of the cited analytic estimate and suffices for a uniform complexity-class inclusion.
For , this yields
A modular statistic that also detects repeated factors
For a rational prime , define
Because is primitive, its reduction is never the zero polynomial. Hence
even at primes where the degree drops or the reduction is not squarefree.
Write the rational factorization, used only in the proof, as
with distinct primitive irreducible of positive leading coefficient. Put
Since ,
Most importantly,
For example, a power with irreducible and has , not one. This is why counting only distinct modular roots would not suffice without a squarefreeness test.
Let
The polynomial and the integer will never be computed. They identify a finite exceptional set for the proof. If , the reductions of the are pairwise coprime and separable, with unchanged degrees. At a root of ,
Indeed, when , the derivative at is the product of the nonzero value and the nonzero values of all other factors. When , every derivative term retains a factor . Therefore
No exclusion of primes dividing the multiplicities is needed.
Uniform discriminant and exceptional-prime bounds
Set
In particular, and . We have the following discriminant bounds.
Lemma 11. Let , where is a root of , and let be the absolute discriminant of . Then
Furthermore, if is the number of distinct rational primes dividing , then
Proof. For an integer polynomial , let
be its Mahler measure. Its multiplicativity and the inequality imply
because every nonzero integer polynomial has Mahler measure at least one.
For a separable polynomial of degree , Hadamard’s inequality applied to its Vandermonde determinant gives
In detail, the row corresponding to has Euclidean norm at most ; squaring the determinant bound and multiplying by gives the assertion. For degree one the discriminant is one, consistently with this formula.
To handle nonmonic factors without any implicit integrality assumption, put , , and
This is a monic irreducible polynomial for , and
The field discriminant divides the discriminant of the order , so
using and (40). Multiplying by and using (34) proves
Similarly, and (40) give
A nonzero integer has at most of its absolute value distinct prime divisors; if , there are none. This proves (39). □
Lemma 12 (Degree-one prime ideals). For , the number equals the number of prime ideals of above with residue degree one.
Proof. The prime divides neither nor , and consequently does not divide . It therefore divides neither the field discriminant nor the index of in the full ring of integers. Dedekind’s factorization theorem applies to ; its distinct irreducible factors modulo record the residue degrees. The invertible change of variable identifies the roots of and modulo . See, for example, [16 Chapter 3] for the factorization theorem and its index condition. □
The complete prime-root average estimate
We have the following uniform error estimate.
Proposition 13. For every ,
Proof. Let count prime ideals of with norm at most and residue degree one over . A prime ideal with higher residue degree has norm with , hence . There are at most prime ideals above a fixed rational prime. Therefore
At each , (36) and Lemma 12 identify the contribution to with the corresponding weighted degree-one prime-ideal contribution. At each exceptional prime, both contributions lie in , so their difference in absolute value is at most . Lemma 11 gives
Applying (26) to every and adding with weights gives
By (27) and , the replacement of by costs at most
Combining these estimates with (38) proves the stronger bound with in the bracket. The stated, deliberately looser bound (41) follows.
An explicit cutoff with linearly many bits
The following formulas use only integers of bits:
The integer is computed by a bit-length operation, with the usual adjustment when is a power of two. The algorithm need not evaluate logarithms of real numbers.
Proof. We have and . Since
we get
which proves (44).
For ,
Since , (42) implies
As , (25) yields (43).
Using , the first term in (39) is bounded by
Divide (39) by (43). The resulting error is at most
The first term is at most by (42). For the second, the same inequality implies
so that term is at most . For the third, use
It is at most . Thus (45) is less than .
Finally,
The constant is fixed, so and the bit length of have the claimed bounds.
Corollary 15. For a primitive nonconstant input and the cutoff (41),
Proof. If is irreducible, then and . If is reducible, then and . Apply Lemma 14 and (33). □
The deterministic polynomial-space algorithm and SparseIrred ∈ PSPACE
The main loop is the following. Integers suffice because is a power of two greater than two and hence is not prime.
Normalize the sparse input.
Handle zero, units, constants, and nonprimitive inputs.
Compute n, S, Delta, U, ell, k, and X from the formulas above.
P := 0; A := 0.
For p := 2, ..., X-1:
If p is prime:
P := P + 1.
For a := 0, ..., p-1:
If f(a) = 0 modulo p:
A := A + 1.
If f'(a) = 0 modulo p:
A := A + 1.
Accept exactly when 2*A < 3*P.
Primality in this deterministic implementation can be tested by trial division. Neither a fast primality algorithm nor a factorization oracle is needed for the space bound. For modular evaluation, use
Binary modular exponentiation takes space polynomial in the lengths of , the coefficient, and the exponent. Here each is ; derivative coefficients also have bits. The exponent-zero convention evaluates constant terms correctly, including at .
The integer has bits. Thus the prime counter, trial divisor, field-element counter, and modular arithmetic registers all have bits. By (31),
The two accumulators therefore have bits as well. The input normalization and content calculation are polynomial-time and polynomial-space; their workspace is reused. Every loop is finite, and no vector of length , no prime list, no polynomial factor, and no dense squarefree part is stored.
Corollary 15 proves correctness. This already proves the requested PSPACE inclusion. The core enumeration after normalization, in fact, admits work space with ordinary binary arithmetic; a linear-space preprocessing claim is not needed here.
A stronger bound: SparseIrredZPP
The same decision inequality admits a polynomial-time majority implementation. This section is not needed for the deterministic space algorithm but confirms that the result does not conceal a long witness-consistency problem.
Let , so and . Define polynomial-time predicates on a prime candidate and residue candidate , each encoded in exactly bits, and a bit :
and or .
Their satisfying-assignment counts are respectively and . Primality is decidable in polynomial time by Agrawal–Kayal–Saxena [1]; the sparse modular evaluations are polynomial time in . The other preprocessing steps are also polynomial time.
For completeness, construct a majority machine explicitly. Guess three mode bits, then , then one additional fair bit . For modes 0, 1, 2, accept regardless of when holds; otherwise, accept exactly when . For modes 3, 4, reject regardless of when holds; otherwise, accept exactly when . For modes 5, 6, 7, accept exactly when .
Every branch uses polynomial time and the same number of guesses. In the difference between accepting and rejecting paths, each satisfying assignment for each positive mode contributes 2, each satisfying assignment for each negative mode contributes , and all remaining assignments contribute zero. Consequently,
The machine has a strict accepting majority if and only if (48) holds. Deterministic preprocessing cases can immediately accept or reject, padding with unused fair bits if desired. This proves SparseIrred PP.
Finally, a polynomial-time machine has only exponentially many branches of polynomial description length. A deterministic machine can enumerate them, simulate one at a time, and keep a polynomial-bit count. Hence PP PSPACE, also directly. Theorem 4 is proved.
Remark 16 (Uniform gaps other than ). The reduction only needs some fixed , independent of the number field. Replacing by another fixed gap changes absolute constants and the fixed multiplier in , not the polynomial-space or PP conclusions. Thus the logical statement “uniform QRH implies sparse irreducibility in PP” is independent of the publication status of the particular zero-free theorem; its present unconditional application uses [7]. A gap shrinking with would require a separate cutoff analysis and is not silently sufficient.
Conclusion
We proved that irreducibility testing for sparse polynomials in is coNP-hard under deterministic polynomial-time many-one reductions; equivalently, reducibility in is NP-hard under the same reductions; irreducibility is also NP-hard under polynomial-time Turing reductions that use a single query. Hence, no polynomial-time irreducibility test exists unless P = NP. This settles the univariate integer case left open in [8, 13, 14, 19]; the corresponding questions over finite fields remain open.
Acknowledgment
This paper is supported by the Strategic Priority Research Program of CAS Grants XDA0480502 and XDA0480503, NSFC Grants 12288201 and 92270001.
Declaration of AI Use
The main results presented in this paper are obtained through an interactive collaboration between the authors and an artificial intelligence agent system, MechMath Agent Team (MMAT) [5] and GPT-Astra. The authors assume full responsibility for the paper’s content.
Lean Formalization Details
This appendix describes the formal development at the level of its mathematical structure and its connection to the statements in the paper. It covers the integer hardness proof and the integer PP and PSPACE upper bounds. The complexity statements use complexitylib’s Turing-machine definitions and proved containments; the hardness proof also uses its proved NP-completeness of exact-3-CNF satisfiability. The integer upper bound retains the literature inputs specified below.
Files and Formal Targets
All project declarations below lie in the namespace SparseIrred, unless a further namespace is specified. Subdirectory paths below are relative to SparseIrred/. The module SparseIrred.lean imports the complete development.
Construction/Defs.lean defines the occurring-variable numbering, the odd primes , the literal and clause polynomials, and , , , . The remaining files in Construction/ prove the Laurent-polynomial identities, the satisfying-assignment correspondence, the algebraic-integer norm argument, and the cyclotomic factorization in the satisfiable case.
The files FFK/Dirichlet.lean, FFK/Lift.lean, FFK/Eisenstein.lean, and FFK/Ljunggren.lean formalize the simultaneous approximation, the lift to , Eisenstein’s criterion at , and the Ljunggren argument for Theorem 6. The module FFK/Main.lean applies this criterion to the formula-dependent construction.
Sparse/Canonical.lean defines canonical binary-sparse polynomial codes and the irreducibility and reducibility languages. The files in Reduction/ define the total reduction and prove its correctness on every source string. The files in Machine/ implement the sparse computation and prove its polynomial running time. Oracle/OneQuery.lean adds exact query counting to the oracle Turing-machine model and constructs the one-query reduction.
Theorem8.lean contains the four complexity conclusions; its name reflects the numbering in an earlier set of progress notes. Irreducibility.lean collects the main statements in the namespace SparseIrred.Irreducibility. They include irreducibility_hardness, satisfiability_encoding, ljunggren_gapPoly, irreducible_gapPoly, exists_shifted_residue_modulus, lcm_primeCounting_bounds, prime_index_bounds, and polynomial_time_sparse_reduction.
The integer upper-bound entry module is UpperBounds/Section3Complete.lean. It collects the counting argument, arbitrary real cutoffs, fixed positive zero-free gaps, and the implemented machines in the namespace SparseIrred.UpperBounds.
Algebraic Construction and Gap Criterion
The polynomial denoted by in the paper is Hpoly for an arbitrary gap , and Hfinal for the chosen gap Mval. The statement Irreducibility.satisfiability_encoding collects the nonvanishing, degree, reciprocity, rational-coprimality, and root-of-unity assertions of Lemma 5. The theorem toLaurent_Apoly proves that extracting as an ordinary integer polynomial loses no Laurent terms. The Chinese remainder step is exists_root_realizing; the equivalence between satisfiability and a root of unity of , for every , is exists_rootOfUnity_root_iff. Its converse uses the formalized algebraic-integer norm argument in Construction/Norm.lean.
For Theorem 6, the predicate FFK.FFKThreshold is exactly the numerical inequality (3). The theorem Irreducibility.exists_shifted_residue_modulus gives the multiplier , the modulus , and the unique integer quotient with shifted residue in . The lifting identity is proved by FFK.kLift_mul_eq_of_mul_eq; FFK.irreducible_gapLift supplies the Eisenstein step. The palindromic identity and root-of-unity exclusion yield relative primality of and its reciprocal, and mathlib’s Polynomial.irreducible_of_mirror completes the irreducibility argument.
Internally, this argument uses mathlib’s Polynomial.mirror, which equals Polynomial.reverse when the constant coefficient is nonzero. The theorem Irreducibility.ljunggren_gapPoly uses reverse directly and derives from . Both parts of Theorem 6 accept coprimality in ; `Irreducibility. isRelPrime_of_rational_coprime proves the required relative primality in , also excluding integer nonunit common factors by the constant coefficient of .
Polynomial-Time Reduction and Complexity Conclusions
The function encPoly represents an integer polynomial by its nonzero coefficient–exponent pairs in increasing exponent order. Coefficients have a sign and binary magnitude, and exponents are binary. Theorems encPoly_injective and decodePoly_eq_some_iff establish uniqueness and the exact meaning of a canonical code. The languages IrredLang and RedLang use mathlib’s irreducibility predicate and factorization into two nonunits, respectively. Noncodes belong to neither language; on positive-degree polynomials, reducible_iff_not_irreducible proves the complementary relation used by the reduction.
The function reduce handles malformed and degenerate inputs as in the proof of Theorem 4. Its main branch applies encPoly to Hfinal of the decoded formula . The core theorem Hfinal_irreducible_iff proves, for every nonempty CNF formula, that this polynomial is irreducible exactly when the formula is unsatisfiable. The theorem reduce_correct extends correctness to all binary source strings.
The prime bounds of Lemma 8 are established by two theorems: Machine.nth_prime_le and Machine.oddPrime_le. The two inequalities in (PB1) are combined in Irreducibility.lcm_primeCounting_bounds. The machine implementation computes only sparse term lists and binary integers. Its Cobham-algebra membership and complexitylib’s proved Cobham characterization imply reduce_mem_FP. The theorem Irreducibility.polynomial_time_sparse_reduction exhibits one deterministic machine and one natural-coefficient polynomial bounding both running time and output length, and verifies (3) for Mval.
The four final statements in Theorem8.lean are
irreducibility_coNPHard, reducibility_NPHard, irreducibility_NPHard_oneQuery, P_eq_NP_of_irreducibility_mem_P.
The oracle construction proves that its complete run makes exactly one query. The strengthened statements P_eq_NP_of_irreducibility_test and irreducibility_NPHard_oneQuery_of_codes require correctness only on canonical polynomial codes. No membership in NP or coNP is asserted for the target languages.
Integer Upper Bounds and Verified Machines
The number-field argument is formalized for the actual irreducible factors of the input polynomial. It includes integral normalization of nonmonic factors, discriminant bounds, the exceptional-prime bound, and the correspondence between modular roots and degree-one prime ideals. Thus Lemmas 11 and 12 are internal proofs, not additional hypotheses. In the namespace SparseIrred.UpperBounds, integer_prime_root_average_concrete_real proves the average estimate of Proposition 13 for every real . The cutoff analysis then establishes Corollary 15, including inputs with repeated factors. The encoded decision procedure also handles zero, units, constants, and nonprimitive polynomials.
The external analytic input is recorded by the named proposition EffectivePrimeIdealEstimate, with a real-cutoff version EffectivePrimeIdealEstimateReal. These state the effective counting conclusion after supplying the uniform zero-free input of [7] to the estimate of [10]. They quantify over number fields and cutoffs before the input polynomial is chosen. The development proves the choice of a single integer constant and all subsequent specializations. It does not import the external zero-free project [2] or independently prove the analytic implication from zero-freeness to the effective estimate. The other literature parameter is BinaryPrimalityInFP, the binary-encoding form of the AKS theorem [1].
The final integer theorem is
section3_irreducibility_mem_PP_and_PSPACE_of_external_theorems.
It concludes membership of the actual encoded language SparseIrred.IrredLang in complexitylib’s PP and PSPACE, with only the two literature inputs just described. The string verifier, fair-bit guessing, preprocessing composition, polynomial time bound on every branch, and exact acceptance probability are proved in UpperBounds/Machine/. In particular, the majority-machine argument is connected to a real machine, rather than left as a counting specification or an assumed implementation certificate. The theorem GeneralGap.section3_irreducibility_mem_PP_and_PSPACE_of_positive_gap extends the construction to every fixed positive gap, independent of the input. The acceptance condition is strict majority, as required for PP; no bounded-error BPP claim is made.
The deterministic enumeration is also implemented. The theorem Machine.section3_deterministic_streaming_mem_PSPACE applies to the full encoded input and uses the same analytic and AKS inputs. Separately, Machine.section3_linear_streaming_core proves an affine space bound for every reachable configuration of the trial-division core, without AKS, starting from its specified preprocessed configuration. This latter result does not claim linear-space preprocessing or an end-to-end linear-space machine on arbitrary raw input.
Axiom Boundary and Reproducibility
The development uses no project-specific axioms and contains no sorry or admit placeholders in the project proofs. The repository-wide release audit checks 479 declarations and reports only
propext, Classical.choice, Quot.sound.
These are Lean’s standard propositional-extensionality, classical-choice, and quotient-soundness axioms. A separate traversal of the proof and type dependencies of 463 entry points reaches 84,756 constants and no other axioms. In particular, the source NP-hardness theorem, the machine implementations, and the containment PP ⊆ PSPACE are proved dependencies. These checks certify the proof terms of the conditional integer theorems; they do not prove their explicit literature parameters.
For comparison with the earlier progress notes, the repository also retains an alternative route with the general Sawin–Shusterman–Stoll large-gap statement SSSLargeGap as an explicit hypothesis. That statement is not a declared axiom and is not used by the unconditional results of this paper. The FFK argument needed here is proved directly.
The toolchain is fixed to leanprover/lean4:v4.34.0-rc2. The dependency manifest lake-manifest.json fixes all package revisions, including complexitylib at edd0e9ec and mathlib at e06eff5f. The 38 vendored sparse-arithmetic modules are listed in Vendor/MODULES.txt and checked against the published Vendor/SHA256SUMS; no sibling repository is needed. After cloning https://github.com/MechMath/sparse-irr, the development and audits can be checked from the repository root with
lake exe cache get
scripts/audit.sh
The audit script runs the complete build, the axiom and dependency checks, and the vendored-source check, returning failure on an error. The repository-wide release build completes 9,470 tasks. Audit outputs are recorded in docs/AXIOMS.txt and docs/DEP_AUDIT.txt. The full manuscript correspondence is in docs/PAPER_1021_MAP.md; the section reports give more detailed declaration maps and machine specifications. Historical module names and comments may use earlier manuscript numbering. Background discussion and illustrative examples, including Example 1, are not claimed to have separate Lean declarations.
References
- [1]Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. PRIMES is in P. Annals of Mathematics, 160: 781–793, 2004.DOI
- [2]Axiom Math. DedekindZetaZeroFree, 2026. URL https://github.com/AxiomMath/DedekindZetaZeroFree. Public Lean 4 formalization, Main.lean, Solution/DedekindZetaSolution.lean, accessed 20 October 2026.
- [3]David G. Cantor and Hans Zassenhaus. A new algorithm for factoring polynomials over finite fields. Mathematics of Computation, 36(154):587–592, 1981.DOI
- [4]Yichuan Cao, Ruyong Feng, Xiao-Shan Gao, Qiao-Long Huang, and Ruichen Qiu. Sparse polynomial gcd cannot be computed in fixed-output polynomial time. arXiv:2606.12144v2, 2026. URL https://arxiv.org/abs/2606.12144.
- [5]Yichuan Cao, Ruichen Qiu, Junqi Liu, Jiaqi Wang, Dakai Guo, Ruyong Feng, Lihong Zhi, and Xiao-Shan Gao. Mechmath agent team: Llm driven agents for mathematical research. arXiv:2607.04394, 2026.arxiv.org/abs/2607.04394
- [6]cslib-community. Complexitylib, 2026. URL https://github.com/cslib-community/complexitylib.
- [7]Dean Cureton and Jesse Aaron Thorner. A quasi-Riemann hypothesis for Dedekind zeta functions, 2026. Hexagon preprint 2610.00200v2.
- [8]James Harold Davenport and Jacques Carette. The sparsity challenges. In 2009 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, pp. 3–7, 2009. doi: 10.1109/SYNASC.2009.62.DOI
- [9]Michael Filaseta, Kevin Ford, and Sergei Konyagin. On an irreducibility theorem of a. schinzel associated with coverings of the integers. Illinois Journal of Mathematics, 44:633–643, 2000.
- [10]Christopher Frei, Efthymios Sofos, and Martin Lucien Widmer. Some applications of the quasi-Riemann hypothesis to class groups and small generators of number fields. arXiv preprint 2610.18491v2, 2026.arxiv.org/abs/2610.18491
- [11]Erich Kaltofen. Factorization of polynomials given by straight-line programs. In Silvio Micali (ed.), Randomness and Computation, volume 5 of Advances in Computing Research, pp. 375–412. JAI Press, Greenwich, Connecticut, 1989.
- [12]Erich Kaltofen. Polynomial factorization: A success story. In Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation (ISSAC ’03), pp. 3–4, New York, NY, USA, 2003. ACM Press. ISBN 1-58113-641-2. doi: 10.1145/860854.860857.DOI
- [13]Erich Kaltofen and Pascal Koiran. On the complexity of factoring bivariate supersparse (lacunary) polynomials. In Proceedings of the 2005 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC ’05, pp. 208–215. ACM, 2005. doi: 10.1145/1073884.1073912.
- [14]Marek Karpinski and Igor Shparlinski. On the computational hardness of testing square-freeness of sparse polynomials. In Proc. AAECC-13 (Heidelberg, Germany, 1999), Vol. 1719 of LNCS, pp. 492–497. Springer Verlag, 1999.DOI
- [15]Arjen K. Lenstra, Hendrik W. Lenstra, and László Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515–534, 1982.
- [16]James Milne. Algebraic Number Theory. Available at www.jmilne.org/math/, 2020.
- [17]Bhubaneswar Mishra. Superpolynomially large support in every irreducible factor of lacunary polynomials, 2026. arXiv:2609.22286.arxiv.org/abs/2609.22286
- [18]David A. Plaisted. New np-hard and np-complete polynomial and integer divisibility problems. Theoretical Computer Science, 31(1):125–138, 1984.
- [19]Daniel S. Roche. What can (and can’t) we do with sparse polynomials? In Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC ’18, pp. 25–30, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450355506. doi: 10.1145/3208976.3209027. URL https://doi.org/10.1145/3208976.3209027.
- [20]The mathlib community. The Lean mathematical library. In CPP 2020, pp. 367–381, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450370974. doi: 10.1145/3372885.3373824.DOI
- [21]Joachim von zur Gathen and Jürgen Gerhard. Modern Computer Algebra. Cambridge University Press, 2013.