Overview
- Why can sparse input have a factor too large to print efficiently?
- How are factors of bounded degree found?
- What improves when each variable has bounded degree?
Input and output
A sparse polynomial is stored by listing its nonzero coefficients and exponent vectors. Exponents may be written in binary. Thus has input length of order , apart from coefficient encoding. When is prime, its factor has terms. An algorithm that prints every factor densely cannot always run in time polynomial in sparse input length.
In several variables, individual degree at most means for every variable. This differs from allowing one variable an arbitrarily large binary exponent.
References 2
- Lenstra1999Lacunary · §1, pp. 267–268Source
- ChuyoonShpilka2026 · Definition 6, published CCC 2026 versionSource
Factors of bounded degree
Lenstra gives a deterministic algorithm which, for a number field , a nonzero sparse , and , finds all monic irreducible factors of degree at most , with multiplicities. Its running time is polynomial in the encoded lengths of and in , not in .
Cyclotomic factors are treated separately. For other factors, a lower bound for the height of a root shows that a sufficiently large gap splits a vanishing sum into two vanishing blocks. Factoring shorter blocks then finds the required factors.
References 1
- Lenstra1999Lacunary · Main theorem, p. 268; Corollary 2.3, p. 271Source
Complexity of irreducibility
For univariate integer polynomials with binary exponents, a 2026 preprint of Cao–Gao–Huang–Nie claims that irreducibility is coNP-hard under deterministic polynomial-time many-one reductions. Their construction gives monic polynomials. Equivalently, reducibility is NP-hard under these reductions. The title’s NP-hardness assertion for irreducibility uses a different notion: a polynomial-time Turing reduction with one oracle query.
The preprint also claims membership in . Here allows an arbitrarily small advantage over probability ; it does not give a bounded-error randomized polynomial-time algorithm. The upper bound assumes a fixed positive zero-free gap for Dedekind zeta functions of all number fields, together with a uniform effective prime-ideal estimate. The authors invoke recent preprints for these analytic inputs; Appendix A.4–A.5 retains them as hypotheses of the formalized theorem. Both complexity results are recorded as unpublished claims. They concern unbounded binary exponents, so they do not settle the bounded-individual-degree question below.
References 1
- CaoGaoHuangNie2026SparseIrreducibility · Version 1, Theorems 4 and 10; Remark 3; §3.1; Appendix A.4–A.5Source
How many terms can a factor have?
Let , where is a field, have at most terms and individual degree at most . Then Bhargava–Saraf–Volkovich prove that every factor has at most terms. Their proof uses Newton polytopes. It yields deterministic quasipolynomial factorization when is fixed.
This bounds the number of terms in factors, not just their degrees. The cost of univariate factorization over the coefficient field must also be included.
References 1
- BhargavaSarafVolkovich2020 · Theorems 1 and 2 of the arXiv manuscriptThe equivalent log(n+1) bound avoids a convention at n=1; add a dummy variable to treat that case.Source
Sparse divisors
Chuyoon–Shpilka’s CCC 2026 paper lists all -sparse divisors not divisible by a nonconstant monomial in time , up to nonzero scalar multiples. It also gives full factorization in time . These bounds suppress univariate-factorization and field-arithmetic costs.
Finding sparse divisors does not settle irreducibility: a proper factor may have more terms than the input.
References 1
- ChuyoonShpilka2026 · Theorems 9 and 12; Remark 7, published CCC 2026 versionThe input is the nonzero polynomial defined above; log(n+1) gives a bound valid also for n=1.Source
Lists of candidate factors
The June 2026 preprint of Bhattacharjee–Kothary–Rai–Saraf gives a different output. In characteristic zero or greater than , it constructs at most constant-depth circuits containing every factor not divisible by a nonconstant monomial, up to scalar multiples, in time . The maximal monomial divisor is returned separately.
Some circuits may represent polynomials which do not divide . Small coefficient fields may require an extension, and univariate-factorization costs are suppressed. Thus the list alone is not a factorization certificate. Interpolation and divisibility tests give complete factorization with the known quasipolynomial bound.
References 1
- BhattacharjeeKotharyRaiSaraf2026 · Theorem 1.1; Remarks 1.2–1.4; Corollary 4.5Source
Questions
Can bounded individual degree give a faster irreducibility test?
Scope. An n-variable, s-sparse polynomial of individual degree at most d; field costs stated separately
Chuyoon–Shpilka ask for a deterministic irreducibility test in time . Their full manuscript states this question in §10; the published conference paper gives the sparse-divisor and full-factorization algorithms discussed above. A proper factor may be denser than the input, and a list of circuits containing all factors can also contain polynomials that do not divide the input.
References 2
- ChuyoonShpilka2026 · §10, irreducibility-testing questionSource
- BhattacharjeeKotharyRaiSaraf2026 · Theorem 1.1; §1.1, spurious candidatesSource
Related topics
Connected diagrams
Browse all diagrams →References
- Finding small degree factors of lacunary polynomials
Lenstra, Jr., Hendrik W. In Györy, Kálmán and Iwaniec, Henryk and Urbanowicz, Jerzy (editors), Number Theory in Progress, Vol. 1, De Gruyter, 267–276, 1999.
Read the source - On Factorization of Sparse Polynomials of Bounded Individual Degree
Chuyoon, Aminadav and Shpilka, Amir. 41st Computational Complexity Conference (CCC 2026), LIPIcs 383, 20:1–20:20, 2026.
Read the source - Irreducibility Testing of Sparse Polynomials over Integers is NP-hard and Probabilistic Polynomial Time
Cao, Yichuan and Gao, Xiao-Shan and Huang, Qiao-Long and Nie, Jiawei. arXiv:2610.37179v1 [cs.CC], 2026.
Read the source - Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree
Bhargava, Vishwas and Saraf, Shubhangi and Volkovich, Ilya. Journal of the ACM, 67(2), Article 8, 1–28, 2020.
Read the source - Deterministic Algorithms for Low Individual Degree Factors of Sparse Polynomials
Bhattacharjee, Somnath and Kothary, Rishabh and Rai, Shanthanu S. and Saraf, Shubhangi. Electronic Colloquium on Computational Complexity, Report TR26-105, 2026.
Read the source
Comments
Any comments are welcome. Comments appear after the site owner approves them. Privacy policy.