Irreducibility Testing of Sparse Polynomials over Integers is NP-hard and Probabilistic Polynomial Time
Yichuan Cao, Xiao-Shan Gao, Qiao-Long Huang, Jiawei Nie
cs.CC
Oct 27, 2026 · v1
TL;DR
The coNP-hardness and PP upper-bound results are formalized in Lean 4 with Mathlib and a complexity library, and an appendix documents the formal development.
Abstract
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.
Problem
Determine the computational complexity of testing irreducibility of sparse (lacunary) univariate polynomials over the integers. This question was left open in prior work.
Approach
A reduction from exact-3-CNF satisfiability builds a sparse polynomial F whose roots of unity encode satisfying assignments. A gap theorem specialized from Filaseta–Ford–Konyagin makes F irreducible exactly when the formula is unsatisfiable. For the upper bound, a zero-free half-plane for Dedekind zeta functions (Cureton–Thorner) and a uniform prime-ideal estimate (Frei–Sofos–Widmer) support a weighted modular root count and a majority-machine construction. Both results are formalized in Lean 4 using Mathlib and complexitylib.
Results
Sparse irreducibility over Z is coNP-hard under deterministic polynomial-time many-one reductions, and it lies in PP ⊆ PSPACE without assuming GRH. Both theorems are machine-checked in Lean.
