Symbolic Computation Group

We study the problem of expressing a polynomial as a function of a given set of algebraically independent generators. Concretely, suppose we are given $n$ such generators and a polynomial built from them. Then this polynomial can always be written uniquely as another polynomial in $n$ new variables, evaluated at the generators.

We present an algorithm that effectively recovers this unique representation. Our method has linear complexity in the size of the input (the polynomial and the generators) and polynomial in the number of variables when the degree of the target polynomial is fixed. While earlier results have mostly focused on the case where the generators are special families of symmetric polynomials, such as elementary, homogeneous, or power sums, our approach applies more generally.