Techniques of Solving Equations à la Galois
Profile
Name: scruta \(\quad\)
Daily life: mowing
Revision history
1st upload: 2023/06/17
revision2 : 2023/07/27
revision3 : 2024/12/22
revision4 : 2025/09/14
\(\qquad\)
Contact
Copyright © 2023 scruta
[5-1] Algebraic number fields and factorization?
How would you respond if a problem like the following were given to undergraduates? Try to imagine it.
Let \(f(x)=x^2+x+1 \ \in \mathbb{Q}[x]\).
Problem (1): Factor \(f(x)\) over the field of rational numbers \(\mathbb{Q}\).
Problem (2): Factor \(f(x)\) over the field of complex numbers \(\mathbb{C}\).
Problem (3): Factor \(f(x)\) over the algebraic number field \(\mathbb{Q}(\omega)\) generated by a root \(\omega\) of \(\varOmega(\omega)=\omega^2+\omega+1=0\).
Problem (4): Factor \(f(x)\) over the algebraic number field \(\mathbb{Q}(v)\) generated by a root \(v\) of \(g_1(v)=v^2+v+1=0\).
Problem (5): Factor \(f(x)\) over the algebraic number field \(\mathbb{Q}(v)\) generated by a root \(v\) of \(g_2(v)=v^2+3v+3=0\).
[From Wikipedia] An algebraic number field is a finite-degree algebraic extension of the field of rational numbers.
Problem (1): Factor \(f(x)\) over the field of rational numbers \(\mathbb{Q}\).
\begin{align}
Ans. \quad f(x)=x^2+x+1 \notag \\
\end{align}
Problem (2): Factor \(f(x)\) over the field of complex numbers \(\mathbb{C}\).
\begin{align}
Ans. \quad f(x)=(x-\omega)(x-\omega^2) \notag \\
\end{align}
Problem (3): Factor \(f(x)\) over the algebraic number field \(\mathbb{Q}(\omega)\) generated by a root \(\omega\) of \(\varOmega(\omega)=\omega^2+\omega+1=0\).
\begin{align}
Ans. \quad f(x)=(x-\omega)(x-\omega^2)=\bigl(x-\omega\bigr)\bigl(x-(-\omega-1)\bigr) \notag \\
\end{align}
Problem (4): Factor \(f(x)\) over the algebraic number field \(\mathbb{Q}(v)\) generated by a root \(v\) of \(g_1(v)=v^2+v+1=0\).
\begin{align}
Ans. \quad f(x)=(x-v)(x-v^2)=\bigl(x-v\bigr)\bigl(x-(-v-1)\bigr) \notag \\
\end{align}
Problem (5): Factor \(f(x)\) over the algebraic number field \(\mathbb{Q}(v)\) generated by a root \(v\) of \(g_2(v)=v^2+3v+3=0\).
\begin{align}
Ans. \quad f(x)=\bigl(x-(-v-2)\bigr)\bigl(x-(v+1)\bigr) \notag \\
\end{align}
[From Wikipedia] An algebraic number field is a finite-degree algebraic extension of the field of rational numbers.
Problems (1)(2)
You might think, "Don't insult me! This is trivial!"
Problem (3)
“Algebraic number field? Never heard of it! \(\varOmega(\omega)=0\) is just a defining equation for \(\omega\). Even in high school we did factorizations using \(\omega\). Easy, easy. Well, maybe ‘algebraic number field’ is just some kind of fancy buzzword…”
Problem (4): Suppose you are suddenly given (4) without having seen (1)(2)(3).
“Uh… \(g_1(v)=0\)…? Looks kind of like \(v=\omega\). Okay, fine, I’ll just set \(v=\omega\) and factor it that way!”
Problem (5)
“Wait… \(g_2(v)=0\)…? Algebraic number field? Does this even have anything to do with \(f(x)\)?”
In fact, Problem (5) already appeared back in Chapter 1. Since \(g_1(v)\) is the same polynomial as \(\varOmega(\omega)\), you might be reminded of \(\omega\). But for students outside mathematics departments, it is not obvious to connect \(\omega\) with “algebraic number field.” I was the same. Moreover, the polynomial \(g_2(v)\) is not one we are familiar with.
If Problem (5) were given suddenly, most undergraduates would need some time to arrive at the answer.
And here is an even more difficult problem:
Problem (6): Factor \(f(x)\) over the algebraic number field \(\mathbb{Q}(v)\) generated by a root \(v\) of \(g(v)=0\).
\begin{align}
&f(x)=x^3-3x+1 \\
&g(v)=v^3-9v-9=0 \\
\notag \\
&Ans. \ f(x)= \biggl(x-(-\frac{{{v}^{2}}}{3}+2)\biggr)\biggl(x-(\frac{2 {{v}^{2}}}{3}-v-4)\biggr)\biggl(x-(-\frac{{{v}^{2}}}{3}+v+2)\biggr) \\
\end{align}
The method that formalizes this extremely difficult problem into an algorithm and makes it computable is called the Trager Algorithm. This method is extremely convenient when solving equations by means of Galois theory.
I almost want to call it "the terrifying factorization." And yes, the keyword here is again the resultant.
Look at the factorized form (1.3) of \(f(x)\) above. Exactly: this is \(f(x)\) factorized in the splitting field \(F_0(v)\). When we solve equations in Galois theory, the very first step is to factor \(f(x)\) inside the simple extension \(F_0(v)\) generated by a primitive element \(v\). That is why the Trager Algorithm is so important.
(Note) Simple extension \(F_0(v)\) = algebraic number field \(F_0(v)\) = splitting field \(F_0(v)\).
In Chapter 5 we use Problem (6) above as our example to explain the computational method of the Trager Algorithm.
FYR. Trager, B.M., Algebraic Factoring and Rational Function Integration. Proc. SYMSAC 76, 219-226.
[ Flow of computation ]
The central topic concerning factorization over algebraic number fields is what is known as the Trager Algorithm.
Trager Algorithm
(step.1) Let \(f(x)\) be the polynomial we wish to factor, and let \(g(v)\) be the irreducible polynomial having the primitive element \(v\) as a root. Let \(F_0(v)\) denote the algebraic number field (simple extension) generated by the primitive element \(v\).
Here \(n=deg(f(x)), m=deg(g(x))\). In the example below, \(n=m=3\).
(step.2) Consider \(f(x+s \cdot v)\) together with \(g(v)\), and compute the following resultant with respect to \(v\):
\(Res(f(x+s \cdot v),g(v),v)=R(x)\).
Choose \(s\) so that \(R(x)\) is squarefree.
(step.3) Factor \(R(x)\) over \(F_0\): \(R(x)=(-1)^{nm} \cdot R_1(x) \cdot R_2(x) \cdot R_3(x)\).
(step.4) Define \(GCD(R_i(x),f(x+s \cdot v)) \equiv \tilde{Y}_i(x)\). Using \(\tilde{Y}_i(x)\), \(f(x)\) can then be factorized as follows:
\(f(x)=\tilde{Y}_1(x-s \cdot v) \cdot \tilde{Y}_2(x-s \cdot v) \cdot \tilde{Y}_3(x-s \cdot v)\).
(step.1) Let \(f(x)\) be the polynomial we wish to factor, and let \(g(v)\) be the irreducible polynomial having the primitive element \(v\) as a root. Let \(F_0(v)\) denote the algebraic number field (simple extension) generated by the primitive element \(v\).
Here \(n=deg(f(x)), m=deg(g(x))\). In the example below, \(n=m=3\).
(step.2) Consider \(f(x+s \cdot v)\) together with \(g(v)\), and compute the following resultant with respect to \(v\):
\(Res(f(x+s \cdot v),g(v),v)=R(x)\).
Choose \(s\) so that \(R(x)\) is squarefree.
(step.3) Factor \(R(x)\) over \(F_0\): \(R(x)=(-1)^{nm} \cdot R_1(x) \cdot R_2(x) \cdot R_3(x)\).
(step.4) Define \(GCD(R_i(x),f(x+s \cdot v)) \equiv \tilde{Y}_i(x)\). Using \(\tilde{Y}_i(x)\), \(f(x)\) can then be factorized as follows:
\(f(x)=\tilde{Y}_1(x-s \cdot v) \cdot \tilde{Y}_2(x-s \cdot v) \cdot \tilde{Y}_3(x-s \cdot v)\).
The keywords are "resultant" and "GCD."
The GCD (that is, greatest common divisor of polynomials) does not appear to be closely related to the resultant. One naturally wonders, "Why should these two be connected?" But when you compute a concrete example, the logic becomes very clear.
When solving equations using Galois theory, the Trager Algorithm is hidden behind the algebraic computation command \(factor(p,q)\) in software such as maxima. It may not be visible on the surface, but its role is extremely important.