On the complexity of invariant polynomials under the action of finite reflection groups

Abstract

Let $\mathbb{K}[x_1,\dots ,x_n]$ be a multivariate polynomial ring over a field $\mathbb{K}$. Let $(u_1,\dots ,u_n)$ be a sequence of $n$ algebraically independent elements in $\mathbb{K}[x_1,\dots ,x_n]$. Given a polynomial $f$ in $\mathbb{K}[u_1,\dots ,u_n]$, a subring of $\mathbb{K}[x_1,\dots ,x_n]$ generated by the $u_i$'s, we are interested infinding the unique polynomial $f_{\mathrm{new}}$ in $\mathbb{K}[e_1,\dots ,e_n]$, where $e_1,\dots ,e_n$ are new variables, such that $f_{\mathrm{new}}(u_1,\dots ,u_n)=f(x_1,\dots ,x_n)$. We provide an algorithm and analyze its arithmetic complexity to compute $f_{\mathrm{new}}$ knowing $f$ and $(u_1,\dots ,u_n)$.