Deterministic Polynomial-time Exact-root Computation for Sparse Polynomials with Bounded Total Degree

We study the problem of deterministically computing the exact root of a sparse polynomial in the multivariate setting. Let $f\in \text{F}[x_1,\dots ,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=\text{tdeg}(f)$. We prove a sparsity bound on the base polynomial $g$: $$\mathrm{\parallel }g{\mathrm{\parallel }}_0\le s^{D(2d+2)\mathrm{/}e+1}\mathrm{.}$$ 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{p}\mathrm{o}\mathrm{l}\mathrm{y}(s^{O(Dd)},n,d,D)+s\cdot R(e),$$ % where $R(e)$ denotes the cost of constructing a single $e$-th root of a scalar in the base field $\text{F}$, and, when $\mathrm{char}(\text{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.