Computing Polynomial Representation in Subrings of Multivariate Polynomial Rings

2025/04/30 by Thi Xuan Vu, Vu, Thi Xuan · 1 voice
Computer Science · Mathematics · #Algebraic Geometry (math.AG) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Symbolic Computation (cs.SC) #cs.CC #cs.SC #math.AG

paper · pdf · doi:10.48550/arxiv.2504.21708

Abstract

Let R = \mathbbK[x₁, …, x_n] be a multivariate polynomial ring over a field \mathbbK of characteristic 0. Consider n algebraically independent elements g₁, …, g_n in R. Let S denote the subring of R generated by g₁, …, g_n, and let h be an element of S. Then, there exists a unique element f ∈ \mathbbK[u₁, …, u_n] such that h = f(g₁, …, g_n). In this paper, we provide an algorithm for computing f, given h and g₁, …, g_n. The complexity of our algorithm is linear in the size of the input, h and g₁, …, g_n, and polynomial in n when the degree of f is fixed. Previous works are mostly known when f is a symmetric polynomial and g₁, …, g_n are elementary symmetric, homogeneous symmetric, or power symmetric polynomials.

Citations

• Computing critical points for algebraic systems defined by hyperoctahedral invariant polynomials
• Computing critical points for invariant algebraic systems
• Homotopy techniques for solving sparse column support determinantal polynomial systems
• CLUE: Exact maximal reduction of kinetic models by constrained lumping of differential equations
• Schur Polynomials do not have small formulas if the Determinant doesn't!
• On the complexity of partial derivatives
• A nearly optimal algorithm for deciding connectivity queries in smooth\n and bounded real algebraic sets
• Algebraic Independence and Blackbox Identity Testing
• Lumpability Abstractions of Rule-based Systems
• An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography
• Straight--Line Programs in Geometric Elimination Theory
• Straight-line programs in geometric elimination theory
• On computing the determinant in small parallel time using a small number of processors

Discussions

• Previous works are mostly known when $f$ is a symmetric polynomial and $g_1, \dots, g_n$ are elementary symmetric, homogeneous symmetric, or power symmetric polynomials. [4/4 of https://arxiv.org/abs/ [bsky, 2 points, 0 comments]

Related

• On the complexity of invariant polynomials under the action of finite reflection groups
• Computing critical points for algebraic systems defined by hyperoctahedral invariant polynomials
• Solving Polynomial Systems via a Stabilized Representation of Quotient Algebras
• Classification of multivariate skew polynomial rings over finite fields\n via affine transformations of variables
• Evaluation and interpolation over multivariate skew polynomial rings