Source-linked AI summary
Irreducibility Testing of Sparse Polynomials over Integers is NP-hard and Probabilistic Polynomial Time
Yichuan Cao, Xiao-Shan Gao, Qiao-Long Huang, Jiawei Nie
TL;DR
Sparse inputs can have exponentially large degree despite polynomial-length representations, making term-by-term traversal up to degree non-polynomial-time for deciding irreducibility in Z[X]. The paper reduces exact-3-CNF satisfiability to sparse integer irreducibility using roots of unity and a gap theorem, and establishes the upper bound using cited analytic estimates. SparseIrredZ is coNP-hard under deterministic polynomial-time many-one reductions and belongs to PP ⊆ PSPACE.
Problem
Sparse inputs can have exponentially large degree despite polynomial-length representations, making term-by-term traversal up to degree non-polynomial-time for deciding irreducibility in Z[X].
Source: §1 · p. 2Method
The paper reduces exact-3-CNF satisfiability to sparse integer irreducibility using roots of unity and a gap theorem, and establishes the upper bound using cited analytic estimates.
Source: §2 · p. 3Results
SparseIrredZ is coNP-hard under deterministic polynomial-time many-one reductions and belongs to PP ⊆ PSPACE.
Source: §1.1 · p. 2Takeaways & Limitations
A polynomial-time irreducibility test for sparse integer polynomials would imply P = NP.
Source: §1.1 · p. 2The unconditional upper-bound argument relies on an external theorem providing a uniform positive zero-free gap; without that input, the reduction is conditional on such a gap.
Source: §3.1 · p. 8
Abstract
from arXiv · showhide
In this paper, we prove that irreducibility testing for sparse polynomials in $\mathbb{Z}[X]$ is coNP-hard under deterministic polynomial-time many-one reductions. That is, there exists no polynomial-time irreducibility test algorithm unless $\mathrm P=\mathrm{NP}$. We also provide an upper bound for this problem by demonstrating that the same irreducibility testing problem lies in $\mathsf{PP}\subseteq\mathsf{PSPACE}$; in other words, it can be solved in probabilistic polynomial time and, moreover, within polynomial space. The fact that $\mathsf{SparseIrred}_{\mathbb{Z}}\in\mathsf{PP}$ 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.
1 Introduction
Sparse polynomial factorization can be difficult to transfer from dense settings because compact inputs may encode very high degrees and factors with many terms. The paper establishes complexity bounds for testing irreducibility over the integers and describes a Lean formalization of its results.
1 Introduction
- A sparse input can have exponentially large degree, making term-by-term traversal infeasible, and a sparse polynomial can have an irreducible factor with exponentially many terms relative to the input.The paper gives a cyclotomic example whose input size is O(log p) while one irreducible factor has p nonzero terms.Source: §1 · pp. 1–2
- Earlier work left univariate sparse irreducibility unresolved; bivariate hardness does not settle it because the studied bivariate form reduces irreducibility to coprimality.The paper also notes that the corresponding finite-field question remains open.Source: §1 · p. 2, §1.1 · p. 2
1.1 Main Result
- SparseIrredZ is coNP-hard under deterministic polynomial-time many-one reductions, and it lies in PP and therefore in PSPACE.The result implies that a polynomial-time irreducibility test would imply P = NP.Source: §1.1 · p. 2
- The PP upper bound relies on the quasi-Riemann hypothesis result of Cureton–Thorner and the uniform effective prime-ideal estimate of Frei–Sofos–Widmer [10].The paper distinguishes PP from BPP; the stated upper bound is PP.Source: §1.1 · p. 2
1.2 Lean Formalization
- The Lean 4 development formalizes the hardness and integer upper-bound results, while the upper bound retains explicit hypotheses for cited analytic and primality results.The project reports no project-specific axioms or sorry placeholders, but its audit does not discharge those literature hypotheses.Source: §1.2 · p. 3
2 Irreducibility Test of Sparse Polynomials over Integers is CoNP-hard
The section proves deterministic coNP-hardness for sparse-polynomial irreducibility testing by reducing exact-3-CNF satisfiability to a sparse polynomial whose roots of unity encode satisfying assignments. A criterion for the constructed family turns this encoding into an irreducibility reduction.
2 Irreducibility Test of Sparse Polynomials over Integers is CoNP-hard
- Irreducibility testing over Z[X] is coNP-hard under deterministic polynomial-time many-one reductions, so a polynomial-time test would imply P = NP.Reducibility is NP-hard under the same reductions.Source: §2 · p. 3
2.1 The exact-3-CNF reduction
- The constructed F has a root of unity exactly when the exact-3-CNF formula is satisfiable, and the gap theorem makes F irreducible precisely when the formula is unsatisfiable.The roots of unity encode satisfying assignments, and the canonical sparse table has polynomial length.Source: §2.1 · p. 3, §2 · p. 3, §2.3 · p. 7
2.2 A Criterion for Irreducibility
- For the constructed palindromic family, the irreducibility criterion applies when its stated hypotheses hold and F has no complex root of unity.The proof specializes simultaneous approximation and polynomial lifting to this family.Source: §2.2 · p. 4
2.3 Proof of Theorem 4
- The polynomial-time construction maps 3-UNSAT instances to irreducible sparse polynomials and 3-SAT instances to reducible ones, establishing the hardness reduction.For unsatisfiable formulas the construction yields an irreducible F; for satisfiable formulas a cyclotomic polynomial divides F, making it reducible.Source: §2.3 · p. 7
3 Irreducibility of Sparse Polynomials over Integers is PP
The section establishes a PP upper bound for sparse-polynomial irreducibility, with a deterministic polynomial-space algorithm; its unconditional analytic input is a uniform zero-free result for Dedekind zeta functions. A weighted modular-root count, explicit cutoff, and majority-machine construction support these bounds.
3.1 Quasi-Riemann hypothesis for Dedekind zeta functions
- The unconditional upper-bound application relies on Cureton–Thorner’s zero-free theorem and Frei–Sofos–Widmer’s uniform effective prime-ideal estimate.Without the cited zero-free input, the argument remains conditional on a uniform positive zero-free gap.Source: §3.1 · p. 8
3.2 A modular statistic that also detects repeated factors
- The weighted modular-root statistic detects repeated factors without excluding primes that divide their multiplicities.The proof handles primes where the reduction drops degree or is not squarefree.Source: §3.2 · p. 9
3.3 Uniform discriminant and exceptional-prime bounds
- For each number field arising from an irreducible factor, the discriminant bound is wi log Di ≤ n log n + n(n −1) log S ≤ n2∆.The argument also bounds the number of exceptional primes through the integer Z.Source: §3.3 · pp. 9–10
3.4 The complete prime-root average estimate
- The complete prime-root average estimate follows by matching modular roots to degree-one prime ideals outside the exceptional primes and bounding their contribution.The proof combines the effective prime-ideal estimate with the discriminant and exceptional-prime bounds.Source: §3.4 · pp. 10–11
3.5 An explicit cutoff with linearly many bits
- The explicit cutoff has O(L) bits and separates irreducible from reducible inputs using the threshold 3/2 for A_f(X)/π(X).The stated error is less than 1/4, while the two cases lie below 5/4 and above 7/4, respectively.Source: §3.5 · pp. 11–12
3.6 The deterministic polynomial-space algorithm and SparseIrredZ ∈PSPACE
- The deterministic streaming algorithm proves the PSPACE inclusion without storing a prime list, factor, or dense squarefree part.The core enumeration uses O(L) work space after normalization; this does not assert linear-space preprocessing.Source: §3.6 · p. 13
3.7 A stronger bound: SparseIrredZ ∈PP
- SparseIrredZ lies in PP and PSPACE, with the PP proof using a polynomial-time majority implementation of the decision inequality.The analytic application uses the cited zero-free result and effective prime-ideal estimate.Source: §3 · p. 8, §3.7 · p. 13
- A fixed positive zero-free gap suffices for the PP and PSPACE conclusions; a gap shrinking with n requires separate cutoff analysis.Changing the fixed gap changes constants, not the stated complexity-class conclusions.Source: §3.7 · p. 13
4 Conclusion
The paper establishes deterministic coNP-hardness for irreducibility testing of sparse polynomials over the integers, settling the univariate integer case left open in prior work. The corresponding questions over finite fields remain open.
4 Conclusion
- Sparse-polynomial irreducibility over Z is coNP-hard under deterministic polynomial-time many-one reductions, while the corresponding finite-field questions remain open.Equivalently, reducibility over Z is NP-hard under the same reductions.Source: §4 · p. 13
Declaration of AI Use
The authors report that the paper’s main results were developed through collaboration with MMAT and GPT-Astra, and state that they assume full responsibility for its content.
Declaration of AI Use
- The authors report collaboration with MMAT and GPT-Astra and assume full responsibility for the paper’s content.The collaboration is identified as interactive.Source: Declaration of AI Use · p. 14
A Lean Formalization Details
The appendix maps the paper’s hardness and upper-bound arguments to a Lean formalization, including its encoded languages, reductions, and machines. It records the analytic literature inputs and the proof-dependency and reproducibility audits.
A.1 Files and Formal Targets
- The formalization organizes the hardness construction, sparse reduction, one-query oracle reduction, and machine implementation across dedicated modules.It also identifies the upper-bound entry module for the integer results.Source: §A.1 · p. 16
A.2 Algebraic Construction and Gap Criterion
- The algebraic construction formalizes the satisfiability encoding and the root-of-unity criterion, while the FFK development proves the gap-lifting and Eisenstein steps used for irreducibility.The formalization connects these ingredients to Theorem 6.Source: §A.2 · p. 16
A.3 Polynomial-Time Reduction and Complexity Conclusions
- The reduction encodes sparse polynomials canonically and proves that its output is irreducible exactly when the source formula is unsatisfiable.The formalized conclusions include coNP-hardness, reducibility NP-hardness, and one-query irreducibility hardness; no NP or coNP membership is asserted.Source: §A.3 · p. 17
A.4 Integer Upper Bounds and Verified Machines
- The upper-bound formalization proves the discriminant, exceptional-prime, modular-root correspondence, average-estimate, cutoff, and decision-procedure steps.The encoded decision procedure also handles zero, units, constants, and nonprimitive polynomials.Source: §A.4 · p. 17
- The formalized PP and PSPACE results use the stated external analytic inputs, and the PP machine’s strict-majority behavior is connected to an implemented machine.The appendix also records the deterministic machine implementation and distinguishes the linear-space core from end-to-end preprocessing.Source: §A.4 · pp. 17–18
A.5 Axiom Boundary and Reproducibility
- The audit reports no project-specific axioms or proof placeholders, while explicitly leaving the upper-bound literature parameters undischarged.The reproducibility record fixes the toolchain and package revisions and describes a script that runs the build and audits.Source: §A.5 · p. 18