REVIEW 1 minor 1 cited by
If a sparse multivariate polynomial with bounded total degree is an exact power, its base has bounded sparsity, enabling a deterministic polynomial-time root algorithm.
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
T0 review · grok-4.3
2026-07-03 03:41 UTC pith:LLCAAACQ
load-bearing objection The paper gives a deterministic poly-time algorithm for exact e-th roots of sparse multivariate polys when total degree D is bounded, via a new sparsity bound on the root that improves the dependence on sparsity from quasi-poly to poly.
Deterministic Polynomial-time Exact-root Computation for Sparse Polynomials with Bounded Total Degree
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
If f in F[x1 to xn] is nonzero, s-sparse, with individual degree at most d and total degree D, and f equals g^e, then the base satisfies ||g||_0 at most s to the power D(2d+2)/e +1, and there is a deterministic algorithm computing g with complexity poly(s to the O(Dd), n, d, D) plus s times R(e), where R(e) is the cost of a scalar e-th root or Frobenius root.
What carries the argument
The sparsity bound ||g||_0 ≤ s^{D(2d+2)/e +1} on the base polynomial, which limits the search space so that g can be recovered deterministically from the support and coefficients of f.
Load-bearing premise
The input polynomial must be exactly an e-th power of some base polynomial.
What would settle it
An explicit s-sparse f of total degree D and individual degree d that equals some g^e yet has ||g||_0 strictly larger than s^{D(2d+2)/e +1} would falsify the bound.
If this is right
- Exact roots can be computed deterministically in time polynomial in the input parameters whenever total degree D is treated as a constant.
- The algorithm applies over any field in which a single scalar e-th root (or Frobenius root) can be extracted at cost R(e).
- Within the bounded-total-degree regime the method improves on the quasi-polynomial time of general deterministic factorization algorithms.
Where Pith is reading between the lines
- The sparsity bound could be used to design deterministic algorithms for related structured problems such as computing e-th roots of sparse polynomials that are close to exact powers.
- One could attempt to tighten or saturate the exponent D(2d+2)/e +1 by constructing families of examples.
- The technique might extend to computing exact roots over rings or to deciding whether a given sparse polynomial is an exact power.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims a sparsity bound ||g||_0 ≤ s^{D(2d+2)/e + 1} for the base g of an s-sparse exact e-th power f = g^e with individual degree ≤ d and total degree D. It develops a deterministic algorithm to compute g with complexity poly(s^{O(Dd)}, n, d, D) + s·R(e), which is polynomial-time for constant D.
Significance. If the bound and algorithm hold, this yields a deterministic polynomial-time exact-root algorithm for sparse polynomials in the bounded-total-degree regime, improving on the quasi-polynomial dependence in Bhargava-Saraf-Volkovich. The explicit sparsity bound and the field-dependent R(e) term (absorbed into polynomial time for standard fields) are strengths. The paper ships a concrete, derived sparsity bound and an explicit complexity expression.
minor comments (1)
- [Abstract] Abstract: the displayed sparsity bound and complexity expressions are not cross-referenced to the sections containing their proofs or derivations; adding such pointers would improve navigation.
Simulated Author's Rebuttal
We thank the referee for the positive summary, recognition of the explicit sparsity bound, and recommendation for minor revision. The report correctly identifies the improvement over the quasi-polynomial dependence in prior work when total degree D is bounded.
Circularity Check
No significant circularity detected
full rationale
The paper states the input premise that f is exactly an e-th power (f = g^e) with given sparsity s, individual degree bound d, and total degree D, then proves an independent sparsity bound ||g||_0 ≤ s^{D(2d+2)/e + 1} on the base polynomial. This bound is used to construct a deterministic algorithm whose running time is expressed in terms of the bound. No load-bearing step reduces by construction to a fitted parameter renamed as a prediction, a self-definitional loop, or a self-citation chain; the central sparsity result and complexity claim are derived from the explicit problem assumptions without circular reduction to the target quantities. The derivation is therefore self-contained.
Axiom & Free-Parameter Ledger
read the original abstract
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 is an exact $e$-th power, say $f = g^e$. Suppose $f$ is $s$-sparse, has an individual degree of at most $d$, and a total degree of $D = \tdeg(f)$. We prove a sparsity bound on the base polynomial $g$: \[ \|g\|_0 \le s^{D(2d+2)/e + 1}. \] Based on this bound, we develop a deterministic algorithm that computes the base $g$. % In contrast to the general deterministic factorization algorithm of Bhargava, Saraf, and Volkovich \cite{BhargavaSarafVolkovich2020}, which achieves only a quasi-polynomial dependence on the input parameters, our algorithm is \emph{polynomial-time} in the setting where the total degree $D$ is bounded. Specifically, the overall complexity is \[ \mathrm{poly}\left(s^{O(Dd)}, n, d, D\right) + s\cdot R(e), \] % where $R(e)$ denotes the cost of constructing a single $e$-th root of a scalar in the base field $\F$, and, when $\operatorname{char}(\F)\mid e$, the cost of computing a single Frobenius root of a scalar. % This term is field-dependent, and over finite fields, $\mathbb{Q}$, or number fields with a suitable representation, it is absorbed into the polynomial complexity bound. % Within the bounded total-degree regime, this yields a deterministic polynomial-time algorithm for exact-root computation.
Forward citations
Cited by 1 Pith paper
-
MechMath Agent Team: LLM Driven Agents for Mathematical Research
A decoupled multi-agent LLM system (Harness + KB/NL/FL provers) co-piloted solutions to 11 open math problems, some with Lean formalization.
Reference graph
Works this paper leans on
- [1]
-
[2]
Computational Complexity , volume =
Bisht, Pranav and Volkovich, Ilya , title =. Computational Complexity , volume =. 2025 , doi =
work page 2025
-
[3]
Bhargava, Vishwas and Saraf, Shubhangi and Volkovich, Ilya , title =. Journal of the ACM , volume =. 2020 , doi =
work page 2020
-
[4]
Some Results on Sparse Exact-Root Questions , year =
-
[5]
A Constant-Free Exact-Root Sparsity Bound , year =
-
[6]
Vishwas Bhargava and Shubhangi Saraf and Ilya Volkovich , title =. Journal of the ACM , volume =. 2020 , doi =
work page 2020
-
[7]
Mark Giesbrecht and Daniel S. Roche , title =. Journal of Symbolic Computation , volume =
- [8]
-
[9]
Eric Bach and Jonathan Sorenson , title =. Algorithmica , volume =
- [10]
- [11]
- [12]
-
[13]
David Y. Y. Yun , title =. Proceedings of the
-
[14]
Rendiconti Lincei -- Matematica e Applicazioni , volume =
Andrzej Schinzel and Umberto Zannier , title =. Rendiconti Lincei -- Matematica e Applicazioni , volume =
-
[15]
Mathematics of Computation , volume =
John Abbott , title =. Mathematics of Computation , volume =
-
[16]
P. Erd. On the number of terms of the square of a polynomial , journal =
-
[17]
Inventiones Mathematicae , volume =
Umberto Zannier , title =. Inventiones Mathematicae , volume =
- [18]
-
[19]
Journal of Symbolic Computation , volume =
Felipe Cucker and Pascal Koiran and Steve Smale , title =. Journal of Symbolic Computation , volume =
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.