9 papers
Sparse Polynomial GCD Algorithms Asymptotically Linear in All Fundamental Parameters
Qiao-Long Huang, Xiao-Shan Gao
Let be multivariate polynomials with integer coefficients and let . We present an algorithm for computing whose expected…
MechMath Agent Team: LLM Driven Agents for Mathematical Research
Yichuan Cao, Ruichen Qiu, Junqi Liu +5
AI reasoning has become a central focus in contemporary artificial intelligence, largely driven by the success of large language models. However, mathematical research, which is ch…
Deterministic Polynomial-time Exact-root Computation for Sparse Polynomials with Bounded Total Degree
Qiao-Long Huang, Yichuan Cao, Ruichen Qiu +1
We study the problem of deterministically computing the exact root of a sparse polynomial in the multivariate setting. Let $f \in \F[x_1,\ldots,x_n]$ be a nonzero polynomial that i…
Every Nonnegative Integer Is a Sum of a Triangular, a Pentagonal, and a Heptagonal Number
Yichuan Cao, Dakai Guo, Ruichen Qiu +2
In this paper, it is proved that any nonnegative integer can be written in the following form This settles the…
A Greatest Common Divisor Criterion of Certain Binomial Coefficients
Dakai Guo, Ruichen Qiu, Yichuan Cao +2
The binomial greatest common divisor (gcd) criterion recorded as OEIS A080170 is proven. The criterion also appears as conjecture (17) in Ralf Stephan's list of OEIS conjectures. F…
Output-sensitive Sparse Polynomial GCD over Finite Fields is NP-hard
Ruichen Qiu, Yichuan Cao, Qiao-Long Huang +2
In this paper, we prove that output-sensitive sparse polynomial GCD computation over finite fields is NP-hard under BPP many-one reduction. More precisely, for two sparse univariat…