As an example, consider the polynomial $f(x) = x^3 + x - 2 = (x - 1)(x^2 + x + 2)$ which clearly has a root $x = 1$. But we can also find the roots using Cardano's method, which leads to

$$x = \sqrt[3]{\sqrt{28/27} + 1} - \sqrt[3]{\sqrt{28/27} - 1}$$

and two other roots.

It's easy to check numerically that this expression is really equal to $1$, but is there a way to derive it algebraically which isn't equivalent to showing that this expression satisfies $f(x) = 0$?


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.

  • $\begingroup$ thanks, that was the kind of thing I was looking for. $\endgroup$ – Chris Card Sep 14 '10 at 21:28
  • 1
    $\begingroup$ Qiaochu, where does the $\pm 1/2$ in your guess come from? $\endgroup$ – Michael Lugo Sep 14 '10 at 21:41
  • 1
    $\begingroup$ It comes from the fact that we know the answer is 1. If we didn't know the answer was 1 we'd have to solve a little Diophantine equation instead. $\endgroup$ – Qiaochu Yuan Sep 14 '10 at 21:47

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} \,$.

  • $\begingroup$ nice answer, thanks Bill. Are the denesting algorithms implemented in any CAS? Maxima didn't seem to be able to do it for example. $\endgroup$ – Chris Card Sep 15 '10 at 7:34
  • $\begingroup$ Macsyma (and more weakly Maxima) have only some less powerful heuristics (mainly due to Gosper). I had hoped to implement some of my work and Bloemer's but, alas, never found the spare time. I don't know the current status for other CAS. $\endgroup$ – Bill Dubuque Sep 15 '10 at 11:59
  • $\begingroup$ I could verify that Maple doesn't automatically equates the example expression to 1, but applying its simplify function to it yields 1 $\endgroup$ – Jean-Denis Muys Sep 16 '12 at 9:01

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.

  • 1
    $\begingroup$ I don't know what's been done since Blömer's work since I haven't kept up on this line of research. His results are described in full detail in his publications. If memory serves correct, there is still much work to be done to obtain efficient algorithms. Note: I found your post only now by accident. This software platform notifies users only if you answer their question, comment on their answer, or write @username in a comment thread they are in. Of course you can always reach me at my first.lastname at gmail. $\endgroup$ – Bill Dubuque Mar 5 '11 at 18:56
  • 6
    $\begingroup$ "breadboarded"? $\endgroup$ – Gerry Myerson Dec 11 '11 at 5:00
  • $\begingroup$ I'm guessing "breadboarded" is in the EE-sense of implementing a prototype. I too have been looking for confirmed implementations of either Landau's or Blömer's algorithm in some CAS... and found nothing! There's 1999 paper by some Maple guys ("Simplifying Square Roots of Square Roots by Denesting" in a CAS volume edited by Michael J. Wester) which says something along the lines that heuristics are more practical. A recent book, A Classical Introduction to Galois Theory by Stephen C. Newman only mentions Zippel denesting. $\endgroup$ – Fizz Mar 7 '15 at 11:24

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.