4
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ How can an algorithm know $(49+20\sqrt{6})^{1/4} + (49 - 20 \sqrt{6})^{1/4} = 2\sqrt{3}$ and so not create incorrect Galois conjugates? Finding the minimal polynomial seems hopeless in general (finding irreducible factors of an explicit monic in $\mathbf{Q}[x]$). Also, it seems a nightmare to keep track of specific $n$th roots: cf. the error in the 1st "proof" of the Grunwald-Wang theorem, the apparent 9 solutions to Cardano's cubic formula, and $\cos(2\pi/n)$ is expressible in radicals but rarely in real radicals (Thm. 3.1 in math.stanford.edu/~conrad/210BPage/handouts/radreal.pdf). $\endgroup$ – nfdc23 Feb 17 '18 at 2:35
  • $\begingroup$ @nfdc23 The first question seems like it would be addressed by the fact that a failproof algorithm for denesting radicals apparently exists: computer.org/csdl/proceedings/focs/1989/1982/00/063496.pdf I don't understand the implementation details well enough to know whether there are actually insurmountable roadblocks in it, and I also don't know if you could raise a similar objection that involves only expressions of minimal nesting depth, which denesting wouldn't help. $\endgroup$ – Alex Kindel Feb 17 '18 at 2:47
  • $\begingroup$ @nfdc23 As for finding the minimal polynomial in general, I think I can always find an annulling polynomial, and can certainly always factor that over the integers, though being able to detect which factor is also annulling seems to depend on detecting whether a set of algebraic numbers is linearly independent. I don't know how hard that is. $\endgroup$ – Alex Kindel Feb 17 '18 at 2:47
  • 2
    $\begingroup$ I think you're giving Wikipedia more credit than it deserves. For the goal of denominator rationalization, it doesn't matter if we "overdo" the multiplication by multiplying through by some Galois-stable collections of numbers which includes the original denominator (so we thereby get a rational denominator, even if not "minimal" such). In this sense, the Wikipedia statement doesn't suggest that there's an algorithm of the type you are wondering about. Using the result in the link you give requires "knowing" the splitting field, which feels close to a circular approach to your question. $\endgroup$ – nfdc23 Feb 17 '18 at 3:48
  • 2
    $\begingroup$ To illustrate, consider the expression in your question. Vary the cube root through all 3 options and the 5th root through all 5 options, and form the square roots of all 15 such sums. This is a collection of 30 numbers (I don't claim all are distinct, but we don't care), and Galois-stable (but no reason to be the Galois-orbit of the given quantity, though in this case maybe it is). Their product is rational, and we can compute it explicitly by (i) numerical approximation and (ii) control of its denominator (e.g., in your case it's an integer!). A snag: maybe this product is 0? Hmm. $\endgroup$ – nfdc23 Feb 17 '18 at 4:37
3
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ "real algebraic number is represented by its minimal polynomial together with a rational interval..." The rub for me has been that the program I'm working on takes a representation in terms of integers and arithmetic operations as input, and I need to find the minimal polynomial of the input expression in order to translate it into such a representation. Unless I've made a mistake I don't yet realize, I think I've finally covered all my bases in doing that though, as sketched in my answer. I have indeed made extensive use of Cohen's book. $\endgroup$ – Alex Kindel Jun 7 '18 at 13:59
  • $\begingroup$ @AlexKindel To convert a surd expression into an algebraic number represented as minpoly+interval, one simply uses the fact that every operation (sums, products, roots, etc.) can be computed on the minpoly+interval representation of algebraic numbers, so one can evaluate all the subexpressions in order of increasing complexity. This is what you seem to have rediscovered (although I have a hard time reading your self-answer), my point was mainly to point out that it is well known and actually implemented in Sage. (contd.) $\endgroup$ – Gro-Tsen Jun 7 '18 at 14:16
  • $\begingroup$ (contd.) The difficult part would be the other way around: converting an algebraic number in its minpoly+interval representation to a surd expression (assuming one exists, i.e., the Galois group is solvable). This can also be done but it would be much more troublesome and I don't know of an actual implementation in the most general case. (Of course, this raises the question of whyever you would want to do that, when surd expressions are less general and more troublesome... try to express the real root of $x^5-5x+12$ using surds: it can be done but it's not pretty.) $\endgroup$ – Gro-Tsen Jun 7 '18 at 14:24
  • $\begingroup$ I have no compelling practical reason to want to do this: I chose it as an exercise in writing a nontrivial program. "This is what you seem to have rediscovered" Yes, what you describe is exactly the idea. $\endgroup$ – Alex Kindel Jun 7 '18 at 14:37
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.