我们研究了在多变量设置下确定性计算稀疏多项式的精确根的问题。设 $f \in \F[x_1,\ldots,x_n]$ 是一个非零多项式，且为精确的 $e$ 次幂，即 $f = g^e$。假设 $f$ 是 $s$-稀疏的，且每个变量的度数至多为 $d$，总度数为 $D = \tdeg(f)$。我们证明了基多项式 $g$ 的稀疏性界限： $$ \|g\|_0 \le s^{D(2d+2)/e + 1}. $$ 基于这个界限，我们开发了一个确定性算法来计算基多项式 $g$。与 Bhargava、Saraf 和 Volkovich 提出的通用确定性因式分解算法相比，该算法在总度数 $D$ 有界的情况下实现了多项式时间复杂度，整体复杂度为： $$ \mathrm{poly}\left(s^{O(Dd)}, n, d, D\right) + s \cdot R(e), $$ 其中 $R(e)$ 表示在基础域 $\F$ 中构造一个 $e$ 次根的成本，当 $\operatorname{char}(\F)\mid e$ 时，还包括计算一个标量的 Frobenius 根的成本。这个项依赖于域，在有限域、$\mathbb{Q}$ 或具有适当表示的数域中，它被吸收进多项式复杂度界限内。在有界总度数的情况下，这为精确根计算提供了一个确定性的多项式时间算法。
博主点评： 本文提出了一种高效的算法，解决了多变量稀疏多项式根的计算问题，尤其在总度数有界的情况下，展现了其优越的多项式时间复杂度，具有重要的理论意义和实际应用潜力。算法的复杂度分析清晰，且提供了对基多项式稀疏性的深入理解，值得深入研究与应用。