Sparse Polynomial Divisibility Test over Finite Field is CoNP-hard

Qiao-Long Huang; Ruichen Qiu; Ruyong Feng; Xiao-Shan Gao; Yichuan Cao

arxiv: 2606.12130 · v1 · pith:OW4JZK4Wnew · submitted 2026-06-10 · 💻 cs.SC · cs.CC

Sparse Polynomial Divisibility Test over Finite Field is CoNP-hard

Yichuan Cao , Ruichen Qiu , Qiao-Long Huang , Ruyong Feng , Xiao-Shan Gao This is my paper

Pith reviewed 2026-06-27 07:43 UTC · model grok-4.3

classification 💻 cs.SC cs.CC

keywords sparse polynomialsdivisibility testfinite fieldsCoNP-hardNP-hardBPP reductionscomputational complexity

0 comments

The pith

Deciding divisibility between sparse polynomials over finite fields is CoNP-hard.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that determining if one sparse polynomial divides another exactly over finite fields is CoNP-hard. This is achieved by proving that the non-divisibility problem is NP-hard through BPP many-one reductions. A sympathetic reader cares because sparse polynomial arithmetic is fundamental in computer algebra, and hardness results guide what efficient methods can achieve. The finding closes a long-standing open question on the complexity of this test in the finite field case.

Core claim

We show that deciding whether a sparse polynomial does not divide another sparse polynomial exactly over finite fields is NP-hard under BPP many-one reductions. Equivalently, the sparse polynomial divisibility test over finite fields is CoNP-hard. This resolves the long-standing open problem concerning the computational complexity of the divisibility test for sparse polynomials in the setting of finite fields.

What carries the argument

BPP many-one reduction from a known NP-hard problem to instances of sparse polynomial non-divisibility over finite fields.

Load-bearing premise

The BPP many-one reduction from the known NP-hard problem to the sparse polynomial non-divisibility problem over finite fields is valid and maintains the hardness.

What would settle it

Discovery of a polynomial time algorithm for deciding sparse polynomial divisibility over finite fields or an explicit counterexample showing the reduction does not preserve NP-hardness.

read the original abstract

In this paper, we show that deciding whether a sparse polynomial does not divide another sparse polynomial exactly over finite fields is NP-hard under BPP many-one reductions. Equivalently, the sparse polynomial divisibility test over finite fields is CoNP-hard. This resolves the long-standing open problem concerning the computational complexity of the divisibility test for sparse polynomials in the setting of finite fields.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a BPP reduction claiming CoNP-hardness for sparse polynomial divisibility over finite fields, settling an open question if the construction holds up.

read the letter

The central result is a BPP many-one reduction showing that deciding non-divisibility of two sparse polynomials over a finite field is NP-hard. This makes the divisibility test itself CoNP-hard and closes the complexity gap for the finite-field case.

The work is new in its focus on finite fields and the use of randomized reductions to transfer hardness while keeping the polynomials sparse. Prior results apparently covered other domains but left this setting open, so the claim directly targets that gap.

The reduction itself is the part that needs scrutiny. It must map instances so that sparsity stays polynomially bounded, the field characteristic does not create accidental roots or coefficient collapses, and no unintended factorizations produce false answers. The stress-test note flags exactly these points. If the paper's construction addresses them with explicit choices of field size and term encoding, the argument goes through; otherwise the hardness does not transfer cleanly.

The paper is aimed at people working on algebraic algorithms and complexity in computer algebra systems. Anyone who needs to know the hardness status of sparse operations over finite fields will want to see the details. It is worth sending to referees so that experts can check the reduction steps and the field-parameter choices. The claim is strong enough to justify that review even if revisions are needed later.

Referee Report

1 major / 0 minor

Summary. The paper claims to prove that deciding whether one sparse polynomial does not divide another exactly over finite fields is NP-hard under BPP many-one reductions (equivalently, the sparse polynomial divisibility test is CoNP-hard), thereby resolving a long-standing open problem in the complexity of sparse polynomial arithmetic over finite fields.

Significance. If the claimed BPP reduction is correct and verifiable, the result would be significant for computational algebra, establishing CoNP-hardness for a basic operation on sparse polynomials over finite fields and potentially informing the design of algorithms in computer algebra systems. The use of BPP reductions and preservation of sparsity would be notable strengths if demonstrated.

major comments (1)

[Reduction construction (abstract and main body)] The manuscript provides no explicit construction or verification of the BPP many-one reduction from a known NP-hard problem to the sparse non-divisibility instance over F_q. Without details on how the reduction preserves sparsity (poly-bounded terms), chooses field parameters to avoid characteristic issues or unintended roots, and ensures that algebraic identities do not introduce false positives/negatives, the central hardness claim cannot be assessed (see abstract and any sections describing the reduction).

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and for highlighting the need for greater clarity on the reduction. We address the major comment below.

read point-by-point responses

Referee: [Reduction construction (abstract and main body)] The manuscript provides no explicit construction or verification of the BPP many-one reduction from a known NP-hard problem to the sparse non-divisibility instance over F_q. Without details on how the reduction preserves sparsity (poly-bounded terms), chooses field parameters to avoid characteristic issues or unintended roots, and ensures that algebraic identities do not introduce false positives/negatives, the central hardness claim cannot be assessed (see abstract and any sections describing the reduction).

Authors: We agree that the current presentation of the BPP reduction would benefit from additional explicit details to facilitate verification. The manuscript (Section 3) sketches the reduction from 3-SAT, but does not supply the full expanded construction, field-size arguments, or a separate lemma verifying absence of false positives/negatives. In the revised version we will add an explicit, self-contained description of the reduction, including the precise mapping that keeps the number of terms polynomial, the choice of prime q larger than all degrees involved, and a short proof that the algebraic identities preserve the yes/no instances exactly. revision: yes

Circularity Check

0 steps flagged

No significant circularity in hardness reduction

full rationale

The paper establishes CoNP-hardness of sparse polynomial divisibility testing over finite fields by constructing a BPP many-one reduction from an external known NP-hard problem. No self-definitional steps, fitted inputs renamed as predictions, load-bearing self-citations, uniqueness theorems imported from the authors' prior work, ansatzes smuggled via citation, or renamings of known results appear in the provided abstract or description. The derivation is a standard complexity reduction from independent source problems and is therefore self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard complexity-theoretic assumptions about BPP reductions and the existence of suitable NP-hard source problems; no free parameters or invented entities are introduced in the abstract.

axioms (1)

standard math BPP many-one reductions preserve NP-hardness for the target decision problem
The proof technique relies on this standard notion from complexity theory to establish the hardness result.

pith-pipeline@v0.9.1-grok · 5592 in / 1160 out tokens · 18080 ms · 2026-06-27T07:43:37.669347+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

17 extracted references · 10 canonical work pages

[1]

Maurice Rojas

Jingguo Bi, Qi Cheng, and J. Maurice Rojas. Sub-linear root detection, and new hardness results, for sparse polynomials over finite fields. InProceedings of the 38th International Symposium on Symbolic and Algebraic Computation, ISSAC ’13, pp. 61–68, New York, NY, USA, 2013. Association for Computing Machinery. ISBN 9781450320597. doi: 10.1145/2465506.246...

work page doi:10.1145/2465506.2465514 2013
[2]

The sparsity challenges

James Harold Davenport and Jacques Carette. The sparsity challenges. In2009 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, pp. 3–7, 2009. doi: 10.1109/ SYNASC.2009.62

2009
[3]

Sumsets, 3sum, subset sum: Now for real! InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp

Nick Fischer. Sumsets, 3sum, subset sum: Now for real! InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 4520–4546, 2025. doi: 10.1137/1.9781611978322.155. URLhttps://epubs.siam.org/doi/abs/10.1137/1.9781611978322.155

work page doi:10.1137/1.9781611978322.155 2025
[4]

On exact division and divisibility testing for sparse polynomials

Pascal Giorgi, Bruno Grenet, and Armelle Perret du Cray. On exact division and divisibility testing for sparse polynomials. InProceedings of the 2021 International Symposium on Symbolic and Algebraic Compu- tation, ISSAC ’21, pp. 163–170, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450383820. doi: 10.1145/3452143.3465539. URLhtt...

work page doi:10.1145/3452143.3465539 2021
[5]

Pascal Giorgi, Bruno Grenet, Armelle Perret du Cray, and Daniel S. Roche. Sparse polynomial in- terpolation and division in soft-linear time. InProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation, ISSAC ’22, pp. 459–468, New York, NY, USA, 2022. Associa- tion for Computing Machinery. ISBN 9781450386883. doi: 10.1145/34764...

work page doi:10.1145/3476446.3536173 2022
[6]

Fast polynomial computations with space constraints, 2026

Bruno Grenet. Fast polynomial computations with space constraints, 2026. URLhttps://arxiv.org/ abs/2511.11267

arXiv 2026
[7]

Grigoriev, Marek Karpinski, and Andrew M

Dima Yu. Grigoriev, Marek Karpinski, and Andrew M. Odlyzko. Existence of short proofs for non- divisibility of sparse polynomials under the extended riemann hypothesis. InPapers from the Interna- tional Symposium on Symbolic and Algebraic Computation, ISSAC ’92, pp. 117–122, New York, NY, USA,
[8]

ISBN 0897914899

Association for Computing Machinery. ISBN 0897914899. doi: 10.1145/143242.143287. URL https://doi.org/10.1145/143242.143287

work page doi:10.1145/143242.143287
[9]

Shaving logs via large sieve inequality: Faster algorithms for sparse convolu- tion and more

Ce Jin and Yinzhan Xu. Shaving logs via large sieve inequality: Faster algorithms for sparse convolu- tion and more. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pp. 1573–1584, New York, NY, USA, 2024. Association for Computing Machinery. ISBN 9798400703836. doi: 10.1145/3618260.3649605. URLhttps://doi.org/10.1145/3618...

work page doi:10.1145/3618260.3649605 2024
[10]

On the computational hardness of testing square-freeness of sparse polynomials

Marek Karpinski and Igor Shparlinski. On the computational hardness of testing square-freeness of sparse polynomials. InProc. AAECC-13 (Heidelberg, Germany, 1999), Vol. 1719 of LNCS, pp. 492–497. Springer Verlag, 1999

1999
[11]

Mechmath agent team

MechMath Team. Mechmath agent team. Academy of Mathematics and Systems Science, Chinese Academy of Sciences, 2026. URLhttps://eonmath.github.io/mechmath

2026
[12]

A new bound on cofactors of sparse polynomials.Forum of Mathemat- ics, Sigma, 14, 2026

Ido Nahshon and Amir Shpilka. A new bound on cofactors of sparse polynomials.Forum of Mathemat- ics, Sigma, 14, 2026. ISSN 2050-5094. doi: 10.1017/fms.2026.10202. URLhttp://dx.doi.org/10.1017/ fms.2026.10202

work page doi:10.1017/fms.2026.10202 2026
[13]

Plaisted

David A. Plaisted. Some polynomial and integer divisibility problems are np-hard. In17th Annual Symposium on Foundations of Computer Science (sfcs 1976), volume 7, pp. 264–267, 1976. doi: 10.1109/ SFCS.1976.29

1976
[14]

Plaisted

David A. Plaisted. New np-hard and np-complete polynomial and integer divisibility prob- lems.Theoretical Computer Science, 31(1):125–138, 1984. ISSN 0304-3975. doi: https://doi. org/10.1016/0304-3975(84)90130-0. URLhttps://www.sciencedirect.com/science/article/pii/ 0304397584901300

work page doi:10.1016/0304-3975(84)90130-0 1984
[15]

Sparse complex polynomials and polynomial reducibility.Journal of Computer and System Sciences, 14(2):210–221, 1977

David Alan Plaisted. Sparse complex polynomials and polynomial reducibility.Journal of Computer and System Sciences, 14(2):210–221, 1977. ISSN 0022-0000. doi: https://doi.org/10.1016/S0022-0000(77) 80013-5. URLhttps://www.sciencedirect.com/science/article/pii/S0022000077800135

work page doi:10.1016/s0022-0000(77 1977
[16]

Daniel S. Roche. What can (and can’t) we do with sparse polynomials? InProceedings 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. URLhttps://doi.org/10.1145/3208976.3209027. 6 Key Laboratory...

work page doi:10.1145/3208976 2018
[17]

Cambridge University Press, 2013

Joachim von zur Gathen and Jürgen Gerhard.Modern Computer Algebra. Cambridge University Press, 2013. A A Randomized Polynomial Reduction from Integer Non-Divisibility to Finite Field Non-Divisibility In this section, we present an alternative proof of Theorem 3 by constructing a randomized polynomial- time reduction that transforms integer non-divisibilit...

2013

[1] [1]

Maurice Rojas

Jingguo Bi, Qi Cheng, and J. Maurice Rojas. Sub-linear root detection, and new hardness results, for sparse polynomials over finite fields. InProceedings of the 38th International Symposium on Symbolic and Algebraic Computation, ISSAC ’13, pp. 61–68, New York, NY, USA, 2013. Association for Computing Machinery. ISBN 9781450320597. doi: 10.1145/2465506.246...

work page doi:10.1145/2465506.2465514 2013

[2] [2]

The sparsity challenges

James Harold Davenport and Jacques Carette. The sparsity challenges. In2009 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, pp. 3–7, 2009. doi: 10.1109/ SYNASC.2009.62

2009

[3] [3]

Sumsets, 3sum, subset sum: Now for real! InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp

Nick Fischer. Sumsets, 3sum, subset sum: Now for real! InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 4520–4546, 2025. doi: 10.1137/1.9781611978322.155. URLhttps://epubs.siam.org/doi/abs/10.1137/1.9781611978322.155

work page doi:10.1137/1.9781611978322.155 2025

[4] [4]

On exact division and divisibility testing for sparse polynomials

Pascal Giorgi, Bruno Grenet, and Armelle Perret du Cray. On exact division and divisibility testing for sparse polynomials. InProceedings of the 2021 International Symposium on Symbolic and Algebraic Compu- tation, ISSAC ’21, pp. 163–170, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450383820. doi: 10.1145/3452143.3465539. URLhtt...

work page doi:10.1145/3452143.3465539 2021

[5] [5]

Pascal Giorgi, Bruno Grenet, Armelle Perret du Cray, and Daniel S. Roche. Sparse polynomial in- terpolation and division in soft-linear time. InProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation, ISSAC ’22, pp. 459–468, New York, NY, USA, 2022. Associa- tion for Computing Machinery. ISBN 9781450386883. doi: 10.1145/34764...

work page doi:10.1145/3476446.3536173 2022

[6] [6]

Fast polynomial computations with space constraints, 2026

Bruno Grenet. Fast polynomial computations with space constraints, 2026. URLhttps://arxiv.org/ abs/2511.11267

arXiv 2026

[7] [7]

Grigoriev, Marek Karpinski, and Andrew M

Dima Yu. Grigoriev, Marek Karpinski, and Andrew M. Odlyzko. Existence of short proofs for non- divisibility of sparse polynomials under the extended riemann hypothesis. InPapers from the Interna- tional Symposium on Symbolic and Algebraic Computation, ISSAC ’92, pp. 117–122, New York, NY, USA,

[8] [8]

ISBN 0897914899

Association for Computing Machinery. ISBN 0897914899. doi: 10.1145/143242.143287. URL https://doi.org/10.1145/143242.143287

work page doi:10.1145/143242.143287

[9] [9]

Shaving logs via large sieve inequality: Faster algorithms for sparse convolu- tion and more

Ce Jin and Yinzhan Xu. Shaving logs via large sieve inequality: Faster algorithms for sparse convolu- tion and more. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pp. 1573–1584, New York, NY, USA, 2024. Association for Computing Machinery. ISBN 9798400703836. doi: 10.1145/3618260.3649605. URLhttps://doi.org/10.1145/3618...

work page doi:10.1145/3618260.3649605 2024

[10] [10]

On the computational hardness of testing square-freeness of sparse polynomials

Marek Karpinski and Igor Shparlinski. On the computational hardness of testing square-freeness of sparse polynomials. InProc. AAECC-13 (Heidelberg, Germany, 1999), Vol. 1719 of LNCS, pp. 492–497. Springer Verlag, 1999

1999

[11] [11]

Mechmath agent team

MechMath Team. Mechmath agent team. Academy of Mathematics and Systems Science, Chinese Academy of Sciences, 2026. URLhttps://eonmath.github.io/mechmath

2026

[12] [12]

A new bound on cofactors of sparse polynomials.Forum of Mathemat- ics, Sigma, 14, 2026

Ido Nahshon and Amir Shpilka. A new bound on cofactors of sparse polynomials.Forum of Mathemat- ics, Sigma, 14, 2026. ISSN 2050-5094. doi: 10.1017/fms.2026.10202. URLhttp://dx.doi.org/10.1017/ fms.2026.10202

work page doi:10.1017/fms.2026.10202 2026

[13] [13]

Plaisted

David A. Plaisted. Some polynomial and integer divisibility problems are np-hard. In17th Annual Symposium on Foundations of Computer Science (sfcs 1976), volume 7, pp. 264–267, 1976. doi: 10.1109/ SFCS.1976.29

1976

[14] [14]

Plaisted

David A. Plaisted. New np-hard and np-complete polynomial and integer divisibility prob- lems.Theoretical Computer Science, 31(1):125–138, 1984. ISSN 0304-3975. doi: https://doi. org/10.1016/0304-3975(84)90130-0. URLhttps://www.sciencedirect.com/science/article/pii/ 0304397584901300

work page doi:10.1016/0304-3975(84)90130-0 1984

[15] [15]

Sparse complex polynomials and polynomial reducibility.Journal of Computer and System Sciences, 14(2):210–221, 1977

David Alan Plaisted. Sparse complex polynomials and polynomial reducibility.Journal of Computer and System Sciences, 14(2):210–221, 1977. ISSN 0022-0000. doi: https://doi.org/10.1016/S0022-0000(77) 80013-5. URLhttps://www.sciencedirect.com/science/article/pii/S0022000077800135

work page doi:10.1016/s0022-0000(77 1977

[16] [16]

Daniel S. Roche. What can (and can’t) we do with sparse polynomials? InProceedings 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. URLhttps://doi.org/10.1145/3208976.3209027. 6 Key Laboratory...

work page doi:10.1145/3208976 2018

[17] [17]

Cambridge University Press, 2013

Joachim von zur Gathen and Jürgen Gerhard.Modern Computer Algebra. Cambridge University Press, 2013. A A Randomized Polynomial Reduction from Integer Non-Divisibility to Finite Field Non-Divisibility In this section, we present an alternative proof of Theorem 3 by constructing a randomized polynomial- time reduction that transforms integer non-divisibilit...

2013