Simplification of expressions containing radicals

There are very general algorithms known for radical denesting. Below is the structure theorem which lies at the foundation of these algorithms. It widely generalizes the heuristic employed by Qiaochu in his answer. It may be employed heuristically - in a similar manner as Qiaochu - to perform complicated denestings, without requiring much comprehension of the underlying theory.

In Bloemer's FOCS '91, '92 papers you'll find his polynomial-time algorithms for radical denesting. Informally, the Denesting Structure Theorem says that if a radical $\rm\, r^{1/d} \,$ denests in any radical extension $\rm\, F' \,$ of its base field $\rm\, F \,$, then a suitable multiple $\rm\, q b\, r \,$ of the radicand $\rm\, r \,$ must already denest in the field $\rm\, F' \,$ defined by the radicand. More precisely

Denesting Structure Theorem$\,\, \,$ Let $\rm\, F \,$ be a real field and $\rm\, F' = F(q_1^{1/d1},\ldots,q_k^{1/dk}) \,$ be a real radical extension of $\rm\, F \,$ of degree $\rm\, n \,$. Let $\rm\, B = \{b_0,\ldots, b_{n-1}\}$ be the standard basis of $\rm\, F' \,$ over $\rm\, F \,$. If $\rm\, r \,$ is in $\rm\, F' \,$ and $\rm\, d \,$ is a positive integer such that $\rm\, r^{1/d} \,$ denests over $\rm\, F \,$ using only real radicals, that is, $\rm\, r^{1/d} \,$ is in $\rm\, F(a_1^{1/t_1},\ldots,a_m^{1/t_m}) \,$ for some positive integers $\rm\, t_i \,$ and positive $\rm\, a_i \in F \,$, then there exists a nonzero $\rm\, q \in F \,$ and a $\rm\, b \in B \,$ such that $\rm\, (q b r)^{1/d} \in F' \,$.

I.e. multiplying the radicand by a $\rm\, q \,$ in the base field $\rm\, F \,$ and a power product $\rm\, b = q_1^{e_1/d_1}\cdots q_k^{e_k/d_k} \,$ we can normalize any denesting so that it denests in the field defined by the radicand. E.g.

$$ \sqrt{\sqrt[3]5 - \sqrt[3]4} \,\,=\, \frac{1}3 (\sqrt[3]2 + \sqrt[3]{20} - \sqrt[3]{25})$$ normalises to $$ \sqrt{18\ (\sqrt[3]10 - 2)} \,\,=\, 2 + 2\ \sqrt[3]{10} - \sqrt[3]{10}^2 $$

An example with nontrivial $\rm\,b$

$$ \sqrt{12 + 5\ \sqrt 6} \,\,=\, (\sqrt 2 + \sqrt 3)\ 6^{1/4} $$

normalises to

$$ \sqrt{\frac{1}3 \sqrt{6}\, (12 + 5\ \sqrt 6)} \,\,=\, 2 + \sqrt{6} $$

Here $\rm\, F=\mathbb Q,\ F' = \mathbb Q(\sqrt 6),\ n=2,\ B = \{1,\sqrt 6\},\ d=2,\ q=1/3,\ b= \sqrt 6\,$.

The structure theorem also hold for complex fields except that in this case one has to assume that $\rm\, F \,$ contains enough roots of unity (which may be computationally expensive in practice, to wit doubly-exponential complexity).

Note that the complexity of even simpler problems involving radicals is currently unknown. For example, no polynomial time algorithm is known for determining the sign of a sum of real radicals $\rm\, \sum{c_i\, q_i^{1/r_i}} \,$ where $\rm\, c_i,\, q_i \,$ are rational numbers and $\rm\, r_i \,$ is a positive integer. Such sums play an important role in various geometric problems (e.g. Euclidean shortest paths and traveling salesman tours). Even though testing whether such a sum of radicals is zero can be decided in polynomial time, this is of no help in determining the sign, it only shows that if sign testing is in $\rm\, NP \,$ then it is already in $\rm\, NP \cap \text{co-NP} \,$.

Pardon my skepticism, but has anyone so much as breadboarded Blömer '92 or Landau '93 in all these 18 years? For lack of same, people still publish ugly surdballs, e.g., $$\vartheta _3\left(0,e^{-6 \pi }\right)=\frac{\sqrt[3]{-4+3 \sqrt{2}+3 \sqrt[4]{3}+2 \sqrt{3}-3^{3/4}+2 \sqrt{2}\, 3^{3/4}} \sqrt[4]{\pi }}{2\ 3^{3/8} \sqrt[6]{\left(\sqrt{2}-1\right) \left(\sqrt{3}-1\right)} \Gamma \left(\frac{3}{4}\right)}$$ (J. Yi / J. Math. Anal. Appl. 292 (2004) 381–400, Thm 5.5 vi) instead of $$\vartheta _3\left(0,e^{-6 \pi }\right)=\frac{\sqrt{2+\sqrt{2}+\sqrt{2} \sqrt[4]{3}+\sqrt{6}} \,\sqrt[4]{\pi }}{2\ 3^{3/8} \Gamma \left(\frac{3}{4}\right)}\quad .$$ And why do both papers trot out the same old Ramanujan denestings instead of new and interesting ones? E.g., $$\sqrt{2^{6/7}-1}=\frac{2^{8/7}-2^{6/7}+2^{5/7}+2^{3/7}-1}{\sqrt{7}}$$ or $$\sqrt[3]{3^{3/5}-\sqrt[5]{2}}=\frac{2^{2/5}+\sqrt[5]{3}+2^{3/5} 3^{2/5}-\sqrt[5]{2}\, 3^{3/5}}{5^{2/3}}$$ or $$\frac{\sqrt[3]{1+\sqrt{3}+\sqrt{2}\, 3^{3/4}}}{\sqrt[6]{\sqrt{3}-1}}=\frac{\sqrt{1+\sqrt{3}+\sqrt{2} \sqrt[4]{3}}}{\sqrt[6]{2}}\quad ?$$ These results were found by two young students of mine who would very much like to know values of q and b in Bill Dubuque's structure theorem which effect the denesting $$\sqrt[3]{-\frac{106}{25}-\frac{369 \sqrt{3}}{125}+\frac{3 \sqrt{3} \left(388+268 \sqrt{3}\right)}{100 \sqrt[3]{2}\, 5^{2/3}}}=\frac{3}{5^{2/3}}-\frac{1+\sqrt{3}}{\sqrt[3]{10}}+\frac{1}{5} \sqrt[3]{2} \left(3+2 \sqrt{3}\right)\quad.$$ Thanks in advance.

Yes. The first thing to try is to guess that $\sqrt[3]{ \left( \sqrt{ \frac{28}{27} } \pm 1 \right) } = \pm \frac{1}{2} + \sqrt{a}$ for some $a$. Cubing both sides then gives

$$\frac{2}{9} \sqrt{21} \pm 1 = \pm \frac{1}{8} + \frac{3}{4} \sqrt{a} \pm \frac{3}{2} a + a \sqrt{a}.$$

Setting $1 = \frac{1}{8} + \frac{3a}{2}$ gives $a = \frac{7}{12}$, and we can verify that

$$\frac{3}{4} \sqrt{a} + a \sqrt{a} = \frac{1}{8} \sqrt{21} + \frac{7}{72} \sqrt{21} = \frac{2}{9} \sqrt{21}$$

as desired. If this method doesn't work then the problem becomes harder.