Computing Polynomial Representation in Subrings of Multivariate Polynomial Rings

Abstract

Let $\mathcal{R}=\mathbb{K}[x_1,\dots ,x_n]$ be a multivariate polynomial ring over a field $\mathbb{K}$ of characteristic 0. Consider $n$ algebraically independent elements $g_1,\dots ,g_n$ in $\mathcal{R}$. Let $\mathcal{S}$ denote the subring of $\mathcal{R}$ generated by $g_1,\dots ,g_n$, and let $h$ be an element of $\mathcal{S}$. Then, there exists a unique element $f\in \mathbb{K}[u_1,\dots ,u_n]$ such that $h=f(g_1,\dots ,g_n)$. In this paper, we provide an algorithm for computing $f$, given $h$ and $g_1,\dots ,g_n$. The complexity of our algorithm is linear in the size of the input, $h$ and $g_1,\dots ,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_1,\dots ,g_n$ are elementary symmetric, homogeneous symmetric, or power symmetric polynomials.