Solving a Solvable Polynomial by Radicals (Effectively)

Question

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

Thanks in advance ^_^

Answer 1

Ok.

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.

Even though my question is technically answered, I'm going to leave this open in case somebody has something else to say. In particular, I'm still interested in more efficient ways of tackling this problem.

Thank you to everyone who left such helpful comments! Hopefully this answer is helpful for pointing future mathematicians in the right direction ^_^.