# Solving a Solvable Polynomial by Radicals (Effectively)

I'm trying to actually write some code (in sage) to take a polynomial $$f$$ with solvable galois group and compute its roots as nested radicals. Right now I'm just trying to get cyclic extensions to work, as the solvable case should follow by iterating this process, but it seems the approach I'm taking (from Gaal's Classical Galois Theory with Examples) is ineffective in practice (I tried it on $$x^5 + x^4 - 4x^3 - 3x^2 + 3x + 1$$, and it took $$30$$ hours on my desktop, and ended up running out of memory before it could finish).

The current algorithm is:

1. Let $$\alpha_0, \ldots, \alpha_{n-1}$$ be the roots of $$f$$.
2. Let $$\sigma$$ generate $$\text{gal}(f / \mathbb{Q})$$
3. Look at the vectors $$v_i = \alpha_0 + \zeta^i \alpha_1 + \zeta^{2i} \alpha_2 + \ldots + \zeta^{(n-1)i} \alpha_{n-1}$$. There are $$n$$ of these ($$i = 0, \ldots, n-1$$), and each is an eigenvector of $$\sigma$$ with eigenvalue $$\zeta^i$$ (where $$\zeta$$ is an $$n$$th root of unity).
4. That means $$v_i^n$$ is fixed by $$\sigma$$ for each $$i$$, and thus lies in $$\mathbb{Q}$$.
5. Now the coefficients of the polynomial $$\psi = (Y - v_0^n)(Y-v_1^n) \cdots (Y-v_{n-1}^n)$$ are symmetric in the $$\alpha_i$$, and so we can write them in terms of the elementary symmetric polynomials in the $$\alpha_i$$. That is, we can write the coefficients of $$\psi$$ in terms of the coefficients of $$f$$.
6. Factor $$\psi$$ over $$\mathbb{Q}$$ as $$(Y - c_0)(Y - c_1) \cdots (Y - c_{n-1})$$. This tells us each $$v_i = \sqrt[n]{c_i}$$.
7. Recover the $$\alpha_i$$ as weighted averages of the $$v_i$$. For instance, $$\alpha_0 = \frac{1}{n} \left ( v_0 + v_1 + \ldots + v_{n-1} \right )$$.

This is all quite effective, but step $$5$$ is not in practice. In particular, for the above polynomial of degree $$5$$, I cannot actually compute the coefficients of $$\psi$$.

Does anybody know if this is how people solve this problem in practice? Are there any implementations that people know of which might be more efficient? I've also checked some textbooks on computational number theory, but none that I've seen have included an algorithm for this.

Edit: If you want to see the exact code I'm running (be warned, it's kind of brittle right now) you can find it here: https://pastebin.com/8qeduT5m

• Are you seeking solutions in terms of real radicals? If your irreducible, raducal-solvable quintic (or any odd-prime-degree) equation has multiple roots, the radicals will be complex and you have what is called the casus irreducibilis for cubic equations. Commented Jul 22, 2021 at 2:15
• I would try the program on $x^5-5x^3+5x-4=0$, and then $x^5-5x^3+5x-1=0$. Commented Jul 22, 2021 at 2:16
• The question has come up here before. Some users found the references in math.stackexchange.com/questions/1388/… to be helpful. Commented Jul 22, 2021 at 4:19
• @OscarLanzi -- I'm allowing complex numbers as well, by taking square roots of negative numbers. I'll also be sure to try my code on those polynomials tomorrow. Is there a reason you chose them? I took the minimal polynomial of $\zeta + \zeta^{-1}$ for $\zeta$ an $11$th root of unity. I'm curious what made you choose your suggestions. Commented Jul 22, 2021 at 7:09
• Equations with the form $x^5-5x^3+5x-a=0$ are solved by rendering $x=r+(1/r)$, then $x^5-5x^3+5x=(r^5)+[1/(r^5)]$ from which $(r^5)^2-a(r^5)+1=0$. Thus $r^5$ solves a quadratic equation and $r$ is obtained directly as a fifth root. By putting in $|a|\ge2$ and then $|a|<2$ we can test with real radicals and complex radicals respectively. Commented Jul 22, 2021 at 8:14

So it looks like I was doing the right thing, and the intensive part of the problem really was in calculating $$\psi$$, which I later learned is called the galois resolvent. I found a paper (Lehobey’s Resolvent Computations By Resultants Without Extraneous Powers) which describes an algorithm for effectively computing the resolvent (though it's still quite slow for polynomials of degree $$5$$, and is borderline unusably slow for polynomials of degree $$7$$). It works, though, and you can find a fully coded up version on my blog.
At time of writing, there's still an issue in that code, regarding the choice of $$n$$th root for each root of $$\psi$$. You can read more about that problem at my followup question here, and I'm currently just trying every possible root for each term... This is inefficient, but gets the job done. I'll probably spend some time later thinking about a smarter way to do this, but if anyone happens to know one, I would love to hear about it.