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

Jul 16, 2026

Study the deterministic computation of exact roots of multivariate sparse polynomials. For a nonzero polynomial f in F[x1,…,xn] that is an exact e-th power f=ge, with s-sparse support, individual degree bounded by d, and total degree D=tdeg(f), a sparsity bound for the base polynomial g is proved: ||g||0 ≤ s·D(2d+2)/e+1. Based on this bound, a deterministic algorithm computes g in polynomial time when D is bounded, contrasting quasi-polynomial dependence in general sparse factorization.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages23

Reading Time58 min

Abstract

Introduction

Sparse polynomials and representation

Exact powers as a subproblem

Prior work and existing limitations

Main contributions

Sparsity bound for the base polynomial

Deterministic exact-root algorithm

arXiv :2607 .02364v 1 [ cs .DS] 2 Jul 2026 Deterministic Polynomial-time Exact-root Computation for Sparse Polynomials with Bounded Total Degree Qiao-Long Huang1, Yichuan Cao2, Ruichen Qiu2, Xiao-Shan Gao2 July 3, 2026 Abstract We study the problem of deterministically computing the exact root of a sparse polynomial in the multivariate setting. Let f ∈ F [x1, . . . , xn] be a nonzero polynomial that is an exact e-th power, say f = ge . 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 ≤ sD (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 [2], which achieves only a quasi-polynomial dependence on the input parameters, our algorithm is polynomial-time in the setting where the total degree D is bounded. Specifically, the overall complexity is poly 􀀐sO(Dd), n, d, D􀀑 + s · 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 char (F) | e, the cost of computing a single Frobenius root of a scalar. This term is field-dependent, and over finite fields, 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. 1 Introduction A polynomial is called s-sparse if it has at most s nonzero monomials. The sparse (or lacunary) representation of a multivariate polynomial can be exponentially more compact than the dense representation: a polynomial such as xN − 1 requires only O (log N) bits to specify, while its dense representation has a length of O (N) . This extreme compression makes sparse polynomials attractive in algebraic complexity theory, coding theory, and symbolic computation, but it also poses fundamental challenges for deterministic algorithm design. In particular, algorithms whose complexity depends polynomially on the total degree D become exponential in the input size when the polynomial is given sparsely, since D can be exponential in the representation length. One of the central problems in this area is sparse polynomial factorization: given a sparse polynomial f , compute its irreducible factors in a representation that is also concise. Bhargava, Saraf, and Volkovich [1] gave a deterministic factorization algorithm for sparse polynomials with bounded individual degree. Their framework establishes a general factor-sparsity bound: if an s-sparse polynomial has an individual degree of at most d, then every factor has sparsity bounded by a function of s and d, enabling deterministic reconstruction. However, their algorithm achieves only quasi-polynomial dependence on the sparse parameters, leaving room for improvement in special but important cases. A particularly fundamental special case is the computation of exact powers: given a polynomial f, determine whether f = ge for some polynomial g and integer e ≥ 2, and if so, compute g. This problem arises 1Shandong University, School of Mathematics, Jinan, China 2State Key Laboratory of Mathematical Sciences, Academy of Mathematics and Systems Science, Chinese Academy of Sciences; University of Chinese Academy of Sciences, Beijing China as a subroutine in complete factorization algorithms, in square-free decomposition, and in detecting prime powers prior to integer factorization. For dense polynomials, exact-power testing and root extraction are classical problems solved efficiently via square-free decomposition or Newton iteration. In the sparse setting, however, these methods break down because they depend polynomially on the degree D, which maybe exponential in the input size. Bisht and Volkovich [3] made significant progress on the structural side, proving a sparsity bound

FAQs

What problem does the paper address?

It studies how to deterministically compute the exact root g in an equation f=ge for sparse multivariate polynomials.

Under what conditions is the polynomial-time guarantee achieved?

The guarantee holds in the bounded total-degree regime, where the total degree D is bounded.

What is the key sparsity bound proved for the base polynomial g?

If f is s-sparse with individual degree ≤ d and total degree D, then for f=ge the base satisfies ||g||0 ≤ s·D(2d+2)/e+1.

Jul 16, 2026

Upload by Emma Wilson