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 xN−1x^N-1 has input length of order log⁡N\log N, apart from coefficient encoding. When N=ℓN=\ell is prime, its factor Φℓ(x)=1+x+⋯+xℓ−1\Phi_\ell(x)=1+x+\cdots+x^{\ell-1} has ℓ\ell 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 dd means deg⁡xif≤d\deg_{x_i}f\le d for every variable. This differs from allowing one variable an arbitrarily large binary exponent.

References 2

Factors of bounded degree

Lenstra gives a deterministic algorithm which, for a number field KK, a nonzero sparse f∈K[x]f\in K[x], and d≥1d\ge1, finds all monic irreducible factors of degree at most dd, with multiplicities. Its running time is polynomial in the encoded lengths of K,fK,f and in dd, not in log⁡d\log d.

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

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 PP⊆PSPACE\mathsf{PP}\subseteq\mathsf{PSPACE}. Here PP\mathsf{PP} allows an arbitrarily small advantage over probability 1/21/2; 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

How many terms can a factor have?

Let 0≠f∈F[x1,…,xn]0\ne f\in F[x_1,\ldots,x_n], where FF is a field, have at most ss terms and individual degree at most dd. Then Bhargava–Saraf–Volkovich prove that every factor has at most sO(d2log⁡(n+1))s^{O(d^2\log(n+1))} terms. Their proof uses Newton polytopes. It yields deterministic quasipolynomial factorization when dd 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 ss-sparse divisors not divisible by a nonconstant monomial in time poly⁡(n,d!,sd)\operatorname{poly}(n,d!,s^d), up to nonzero scalar multiples. It also gives full factorization in time poly⁡(n,sd2log⁡(n+1))\operatorname{poly}(n,s^{d^2\log(n+1)}). 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 dd, it constructs at most sds^d constant-depth circuits containing every factor not divisible by a nonconstant monomial, up to scalar multiples, in time poly⁡(n,d!,sd)\operatorname{poly}(n,d!,s^d). The maximal monomial divisor is returned separately.

Some circuits may represent polynomials which do not divide ff. 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

Questions

OpenAlgorithms and certificates

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 poly⁡(n,sd)\operatorname{poly}(n,s^d). 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
Discuss this question →

Related topics

References

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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