Given two radical expressions, $a$ and $b$, I have an algorithm that finds a polynomial $P(x)\in\mathbb{Q}[x]$ such that $a=P(b)$, if one exists. If not, I can also find a radical expression $c$ such that $a$ and $b$ can both be written as polynomials in $c$. Is it possible to use these algorithms to determine whether, given radical expressions $a$ and $b_1,...,b_n$, there is a polynomial $P(x_1,...,x_n)\in\mathbb{Q}[x_1,...,x_n]$ such that $a=P(b_1,...,b_n)$?
The algorithms I refer to are both applications of algorithm 4.5.4 in this book. The first is the field membership problem, as described on page 179, and the second, the primitive element problem, as described on page 181. My ultimate goal is, given any radical expression, to find an equivalent expression that is a polynomial in terms of some expression $a$ where, if $a$ has multiple terms, none of the terms are polynomials in terms of any of the others.
By "radical expressions" I mean elements of the smallest set $S\subset\mathbb{C}$ such that
- $\mathbb{Q}\subset S$
- If $a,b\in S$ then $a+b,a-b,a*b\in S$
- If $a,b\in S$ and $b\neq 0$ then $a/b\in S$
- If $a\in S$, $b\in\mathbb{Q}$, and $a,b$ are not both $0$ then $a^b\in S$
This is, I believe, the subset of algebraic numbers that are roots of polynomials that are said to be "solvable."
Suppose there is $P(x_1,...,x_n)\in\mathbb{Q[x_1,...,x_n]}$ such that $a=P(b_1,...,b_n)$. Let $c_1=b_1$, let $R_1(x)=x$, let $c_i$ be the result of applying the second algorithm to $c_{i-1}$ and $b_i$, and let $Q_{i-1}(x)$ and $R_i(x)$ be the polynomials such that $c_{i-1}=Q_{i-1}(c_i)$ and $b_i=R_i(c_i)$. Let $\Phi_0(x)=x$ and $\Phi_i(x)=Q_{n-i}(\Phi_{i-1}(x))$ so that $\Phi_{n-i}(c_n)=c_i$, and let $$\Psi(x)=P(R_1(\Phi_{n-1}(x)),...,R_n(\Phi_0(x)))$$ Then $$\Psi(c_n)=P(R_1(\Phi_{n-1}(c_n)),...,R_n(\Phi_0(c_n)))=P(R_1(c_1),...,R_n(c_n))=P(b_1,...,b_n)=a$$ Thus there is a polynomial in $c_n$ that equals $a$, and the first algorithm applied to $a$ and $c_n$ will find some such polynomial.
For the other direction, I have to be less concrete: suppose the first algorithm applied to $a$ and $c_n$ finds a $\Psi(x)$ such that $\Psi(c_n)=a$. The discussion of the second algorithm in the book implies that $\mathbb{Q}(c_i)=\mathbb{Q}(c_{i-1},b_i)$, which in turn implies that $\mathbb{Q}(c_n)=\mathbb{Q}(b_1,...,b_n)$, so every element of $\mathbb{Q}(c_n)$, including $c_n$, is a polynomial in $b_1,...,b_n$. Thus there is some $\Omega(x_1,...,x_n)$ such that $\Omega(b_1,...,b_n)=c_n$, $\Psi(\Omega(b_1,...,b_n))=a$, and we have that $a$ is a polynomial in $b_1,...,b_n$ iff the first algorithm finds that it is also a polynomial in $c_n$.