algorithm for finding radical expressions of all conjugates of an arbitrary algebraic number expressed in radicals

Question

By an algebraic number expressed in radicals, I mean one that is an element of a set $S$ characterized as follows:

1. $\mathbb{Z}\subset S$.
2. For any $a,b\in S$, $a+b,a·b\in S$.
3. For $a,b\in S$ with $b\neq0$, $a/b\in S$.
4. For $a\in S$ and $b\in \mathbb{Q}$ with $a$ and $b$ not both $0$, $a^b\in S$.

For example, given an expression like $\sqrt{\sqrt[3]{2}+\sqrt[5]{3}}+1$, what is an algorithm that can be used to find similar expressions for all of its conjugates? Since its conjugates are by definition the roots of its minimal polynomial, the obvious approach is to find the minimal polynomial, then split it. Is that the way to do it? If so, I have more questions about both parts of the process, which I'll add in edits.

Answer 1

I hadn't noticed this question initially, so I'm a bit late for the battle, but I think your whole question is essentially answered by the fact that there are known algorithms for doing exact computations on algebraic numbers. This means performing additions, subtractions, multiplications, inverses, $n$-th roots, solving arbitrary algebraic equations (with coefficients themselves algebraic numbers), testing exact equality and inequalities, and computing real and imaginary parts.

This also includes computing the minimal polynomial, but, in fact, this datum is part of the representation of the algebraic numbers in the first place: a real algebraic number is represented by its minimal polynomial together with a rational interval in which it is the only root (something which can be tested by Sturm-Liouville). Most operations can be performed by using algebraic elimination (e.g., to compute a polynomial vanishing on $x+y$ knowing minimal polynomials $f$ and $g$ for $x$ and $y$, construct the zero-dimensional algebraic set with equations $f(X)=0$, $g(Y)=0$ and $Z=X+Y$ and perform elimination of the $X$ and $Y$ variables) or some variation thereof; by performing approximate computations with guaranteed precision, one can narrow the interval down so that there is a single root, and using the fact that factorization in $\mathbb{Q}[T]$ is decidable, one can keep the polynomial minimal.

Details can be found in Henri Cohen's Course in Computational Algebraic Number Theory (GTM 138 (1993)), esp. §4.2.

(Variations are possible where, instead of representing an algebraic number by its minimal polynomial and an interval, i.e., approximation at the place at infinity, we use a $p$-adic approximation.)

Furthermore, these algorithms are not just theoretical, they have been implemented in, say, Sage. (In practice, though, the degrees of the polynomials become very rapidly huge when you start doing any kind of non-trivial computations, so it is not terribly usable.)

Computing Galois groups is also algorithmic, so you can decide not just the full set of conjugates but also what permutations between them are possible. This is sort-of-implemented, at least up to a certain degree (but in theory, Galois groups are computable at any degree).

Finally, when the Galois group is solvable (which, again, is decidable), Galois theory tells you how to express roots by radicals (even if you're not starting from something which is already an expression in radicals). I don't know of a systematic implementation, but just to give an idea of what can be done with Sage in specific cases, I once computed expressions for $\cos(2\pi/n)$ for $n\in\{7,11,13,17\}$ in a systematic way using principal determinations of complex roots: see here (the text is in French and the formulae require a MathML-supporting browser like Firefox, but it should at least give some idea).

So, to summarize, everything you ask for is possible, and is somewhat doable in practice. It would be a bit long to describe every algorithm in detail, though, but the literature definitely exists (and Cohen's book is a mine of information).

Answer 2

If we can find the minimal polynomial of any radical expression, we can identify the true conjugates of an expression from among the conjugate candidates as described in the comments on the original question by finding the minimal polynomial of each one and seeing if it matches that of the original expression. To that end, I outline a solution to the minimal polynomial problem:

The minimal polynomial of any $r\in\mathbb{Q}$ is $x-r$. Let $R$ and $S$ be expressions whose monic minimal polynomials $P(x),Q(x)\in\mathbb{Q}[x]$ are known. Then if we can find the minimal polynomials of $\sqrt[n]{R}$, $RS$, $R+S$ and $R/S$ we can find the minimal polynomial of any expression.

$P(x^n)$ is an annulling polynomial of $\sqrt[n]{R}$, and the minimal polynomial of $\sqrt[n]{R}$ is one of the irreducible factors of $P(x^n)$. To determine which one, numerically approximate each distinct factor evaluated at $\sqrt[n]{R}$, incrementally refining the accuracy until $0$ is within the margin or error of only one of them; this is the desired polynomial.

Distribute all products of sums, so that all remaining products take the form of a product of a rational number $r$ and some number of surds.

Case A: Suppose $R$ is rational and $S=\sqrt[n]{s}$. Then $RS=\sqrt[n]{R^ns}$.

Case B: Suppose $R=\sqrt[m]{r}$ and $S=\sqrt[n]{s}$. Following the convention that the complex arguments of all expressions are in $[0,\tau)$ and $\sqrt[m]{r}$ refers to the $m$th root of $r$ whose complex argument is that of $r$ divided by $m$, then we have that

Case a: The sum of the arguments of $r^n$ and $s^m$ is less than $\tau$, and $\sqrt[m]{r}\sqrt[n]{s}=\sqrt[mn]{r^ns^m}$, else

Case b: $\sqrt[m]{r}\sqrt[n]{s}=e^{\frac{\tau i}{mn}}\sqrt[mn]{r^ns^m}$

The argument of $\sqrt[mn]{r^ns^m}$ and the sum of the arguments of $\sqrt[m]{r}$ and $\sqrt[n]{s}$ will be equal in case a, and differ by $\tau$ in case b, so if we estimate both values to within an interval of length $\frac{\tau}{2}$, then if the intervals overlap, we have case a, else case b. In case b, a radical expression for the root of unity can be found using this method.

This estimation has a complication that's worth mentioning: in the case that the expression $E$ whose argument is being estimated is a sum, it's necessary to estimate the real and imaginary parts of $E$, $a$ and $b$, and then estimate $\arctan(\frac{b}{a})$. In order to do this, it's necessary to establish whether $a=0$ first. $E$ might be something complicated that has a real part of $0$ in a nontrivial way, which can never be confirmed directly through approximation. To deal with this, find the conjugates of $E\sqrt{-1}$, incrementally refining the accuracy until the real part estimate of $E\sqrt{-1}$ overlaps with that of either none or exactly one of the other conjugates. In the former case, $E\sqrt{-1}$ has no complex conjugate among its conjugate elements, so it is real, $E$ is imaginary, and $a=0$. In the latter, $E\sqrt{-1}$ is part of a conjugate pair, so it has a nonzero imaginary part, and $E$, a nonzero real part.

Relying on being able to find the conjugates of $E\sqrt{-1}$ may seem circular, but the consolidation of surds that motivated the need for it can be propagated down through all layers of nesting in the expression for $E\sqrt{-1}$, ultimately reaching instances of either case A were $s$ is rational, or case B where $r$ and $s$ are both rational. Either way, the $E$ in the expression $E\sqrt{-1}$ then takes the form of a rational number, so we know what the conjugates of $E\sqrt{-1}$ are, and we can assume by induction that we know how to find all the necessary conjugates.

The subfield problem algorithm on page 178 of this book gives a way to find a $A(x)\in\mathbb{Q}[x]$ such that $R=A(S)$ if one exists. Then we have $R+S=A(S)+S$. Let $n$ be the degree of $Q(x)$. For $B(x)=A(x)+x$, take the first $n$ powers, $B_1(x),...,B_n(x)$, of $B(x)$, replacing any factors of $x^n$ with $x^n-Q(x)$. Thus $B_k(S)=(A(S)+S)^k$, and the degree of $B_k(x)$ is less than $n$. The $B_k(x)$ will be linearly independent over $\mathbb{Q}$. Use their coefficients as the rows of an $n\times n$ matrix, and triangularize to find a linear combination of them that equals a rational number. Subtract the rational number from the linear combination to get an annulling polynomial for $A(S)+S$. Factor this, and for each distinct factor, substitute $B_k(x)$ for $x^k$ for each $k$. The terms of the resulting expression will all cancel iff the factor is the minimal polynomial of $A(S)+S$.

If, on the other hand, no $A(x)$ such that $R=A(S)$ is found, do all of the above with $R$ and $S$ switched. If still none is found, look for $A_R(x)$ such that $R=A_R(cR+S)$ for successive integers $c$ until one is found. Then we have that for $A_S(x)=x-cA_R(x)$, $S=A_S(cR+S)$, and $R+S=A_R(cR+S)+A_S(cR+S)$. Take $B(x,y)$ such that $B(R,S)=A_R(cR+S)+A_S(cR+S)$. Take successive powers of $B(x,y)$, constraining the degrees of each power as in the single-variable case, but with respect to both variables, using the minimal polynomials of both $R$ and $S$. Stop when the number of powers of $B(x,y)$, $m$, equals the number of unique kinds of term that appear across all the $B(x,y)_k$, so that their coefficients can be formed into an $m\times m$ matrix. Triangularize to find an annulling polynomial and test the factors to find the minimal polynomial as before. Since $R$ is not a rational polynomial in $S$ and vice versa, it's still the case that the expression produced by substituting $B(x,y)_k$ for $x^k$ will reduce to $0$ iff the factor is the minimal polynomial.

Finally, having the minimal polynomial of $S$ implies that we can rationalize $R/S$, so to find the minimal polynomial of $R/S$, find the minimal polynomial of its rationalized form.