11 papers
On the Turing Completeness of Transformers and Agents
Yimu Qiao, Lijia Yu, Ruichen Qiu +1
Transformers have emerged as the dominant architecture in sequence modeling, achieving remarkable success in natural language processing and reasoning tasks. While existing literat…
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…
Sparse Polynomial GCD Cannot Be Computed in Fixed-output Polynomial Time
Ruichen Qiu, Yichuan Cao, Qiao-Long Huang +2
This paper shows that, assuming , sparse univariate polynomial GCD cannot be computed in fixed-output polynomial time over any fixed computable field. Pre…
Sparse Polynomial Divisibility Test over Finite Field is CoNP-hard
Yichuan Cao, Ruichen Qiu, Qiao-Long Huang +2
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. Equi…
Quasi-linear Time Multiplication of Sparse Polynomials with Integer Coefficients
Qiao-Long Huang, Yichuan Cao, Ruichen Qiu +1
Sparse polynomial multiplication is a fundamental problem in computer algebra and the theory of computation, and the development of a quasi-linear time output-sensitive multiplicat…
MechMath: Sorrifier-Driven Formal Decomposition Workflow for Automated Theorem Proving
Ruichen Qiu, Yichuan Cao, Junqi Liu +4
Recent advances in large language models (LLMs) and LLM-based agents have substantially improved the capabilities of automated theorem proving. However, for problems that require c…
Deterministic Interpolation of Sparse Black-box Multivariate Polynomials using Kronecker Type Substitutions
Qiao-Long Huang, Xiao-Shan Gao
In this paper, we propose two new deterministic interpolation algorithms for a sparse multivariate polynomial given as a standard black-box by introducing new Kronecker type substi…