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.

Categories: cs.SC cs.CC math.AG

Computing Polynomial Representation in Subrings of Multivariate Polynomial Rings