Abstract
Sparse polynomial interpolation is a fundamental problem in computer algebra, focusing on recovering the algebraic form of a "black box" polynomial with few non-zero terms. This paper presents new algorithms for cases where the polynomial's coefficients are known to belong to a finite set, such as bounded integers or rationals. For univariate polynomials, the authors demonstrate recovery from a single evaluation at a sufficiently large value. For multivariate polynomials, a "modified Kronecker substitution" is introduced to reduce the problem to the univariate case without the exponential degree blowup typical of classical methods. Both algorithms achieve polynomial bit-size complexity.
Introduction
In many computational contexts, we encounter polynomials that are "sparse"—meaning they have relatively few terms compared to their total degree—but are only accessible as "black boxes" that return an output for a given input. The challenge of sparse interpolation is to reconstruct the polynomial's coefficients and exponents efficiently.
Classical algorithms often face bottlenecks when dealing with large degrees or many variables, often resulting in exponential complexity. However, in many practical applications, such as rational function interpolation, we possess prior knowledge: the coefficients are not arbitrary but belong to a known finite set (e.g., integers within a specific range). This paper explores how to leverage this constraint to achieve optimal bit-size complexity.
Univariate Interpolation: The Power of a Single Evaluation
The authors' univariate algorithm relies on a "Giant Step" approach. If the coefficients of a polynomial $f(x)$ are known to be within a finite set, $f(x)$ can be recovered using only one evaluation at a carefully chosen, large value $\beta$.
The Base-$\beta$ Analogy
The core insight is to treat the polynomial evaluation $f(\beta)$ as a number represented in base-$\beta$. If $\beta$ is large enough—specifically, larger than the maximum possible coefficient and the minimum difference between distinct coefficients—the terms of the polynomial do not "overlap" in the sum.
- The algorithm evaluates the black box at $\beta$.
- It identifies the highest-degree term because its value dominates the total magnitude.
- It extracts the coefficient, subtracts the term's contribution from the total, and repeats the process until the polynomial is fully reconstructed.
This method achieves a bit complexity of $\tilde{O}(td)$, where $t$ is the number of terms and $d$ is the degree. The authors note that this is likely the optimal bit complexity for any deterministic, exact black-box interpolation algorithm in this setting.
Multivariate Interpolation: Modified Kronecker Substitution
Interpolating multivariate polynomials (those with multiple variables $x_1, \dots, x_n$) is traditionally more complex. A common technique is the Kronecker substitution, which maps a multivariate polynomial to a univariate one by replacing each $x_i$ with $x^{(D+1)^{i-1}}$. While effective at preserving the uniqueness of terms, it causes the degree of the resulting univariate polynomial to grow exponentially with the number of variables.
A Modular Scalpel
The authors introduce a modified Kronecker substitution to circumvent this blowup. Instead of the standard substitution, they take the exponents modulo a prime number $p$. This keeps the degree of the resulting univariate polynomial small and manageable.
The challenge then becomes finding a "good" prime $p$ that avoids "collisions"—instances where two distinct multivariate terms map to the same univariate term. The paper provides two strategies:
- Deterministic: Testing a sequence of primes until a valid one is found.
- Probabilistic: Selecting a random prime from a specific range, which significantly speeds up the process.
The resulting probabilistic multivariate algorithm achieves a bit complexity of $\tilde{O}(n T^3 D \log H \log C)$, where $n$ is the number of variables, $T$ is the number of terms, $D$ is the degree, and $H$ and $C$ are coefficient bounds. This ensures the algorithm remains efficient even as the complexity of the polynomial increases.
Empirical Validation and Limitations
The algorithms were implemented in the Maple computer algebra system and tested on randomly generated polynomials. The results confirmed the theoretical findings: runtime scales linearly with the number of terms and degree, and logarithmically with coefficient bounds.
Constraints
The primary limitation of this approach is the requirement for a priori knowledge. To function, the algorithms require upper bounds on:
- The maximum degree ($D$)
- The maximum number of terms ($T$)
- The magnitude of coefficients and their denominators ($C$ and $H$)
Conclusion
By exploiting the finiteness of coefficient sets, this research provides a highly efficient path for sparse polynomial interpolation. The transition from the "sledgehammer" of classical Kronecker substitution to the "scalpel" of modular substitution allows for polynomial-time recovery in multivariate cases. These techniques are particularly promising for the interpolation of sparse rational functions, a key task in symbolic computation and identity testing.
Summary updated