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

mailaddress



Copyright © 2023 scruta

Chapter5

    The Terror of Factorization "Trager Algorithm"

\(\qquad \qquad \qquad f(x)=x^3-3x+1 \qquad Galois \ Group:A_3 \quad GCD \)

\( \quad \)

▶ Page    1,   2,   3,   4,   5           ▶ Sample Program

\(\quad \)
home \(\quad \)

\(\nextSection\)
\(\nextSection\)

[5-4] Another viewpoint on \(Res(f(x+v),g(v),v)\) (2)

\(\nextSection\)
We restate the result of the transformations for \(Res(f(x+v),g(v),v)\) from the previous section in (4.1). In this section we examine the constituents of (4.1) in finer detail.

\begin{align} Res(f(x+v),g(v),v)&=\prod_{i=1}^{3}\prod_{j=1}^{3}(\alpha_i-\beta_j) \notag \\ &\Downarrow \notag \\ \end{align} \begin{align} Res(f(x+v),g(v),v)=(-1)&\bbox[#FFFF00]{(x+v_1-\alpha)}\bbox[#7FFF00]{(x+v_1-\beta)}\bbox[#00FFFF]{(x+v_1-\gamma)} \notag \\ &(x+v_4-\alpha)(x+v_4-\beta)(x+v_4-\gamma) \notag \\ &(x+v_5-\alpha)(x+v_5-\beta)(x+v_5-\gamma) \\ \end{align}

Here, to avoid confusion, we color the three linear factors in the first line of (4.1) differently and observe them.

\begin{align} Y_1 \equiv \bbox[#FFFF00]{(x+v_1-\alpha)}\quad Y_2 &\equiv \bbox[#7FFF00]{(x+v_1-\beta)} \quad Y_3 \equiv \bbox[#00FFFF]{(x+v_1-\gamma) } \\ \end{align}

From this point on, our goal is to find expressions that remain invariant under the action of the Galois group \(A_3=\{\rho_1,\rho_4,\rho_5\}\) of \(f(x)\).

First, consider how the elements \(\rho_i\) of \(A_3\) act on \(\{ \ Y_1,Y_2,Y_3 \ \}\). Using [Table5-1] and [Table5-2] below, it is easy to see that the images of each \(Y_i\) under the action of the group \(A_3\) are as listed in [Table5-3].
[Table5-1]
Transformation table for \(\rho_i(v_j)\) in \(A_3\)
\( i \backslash j \)\(\rho_i(v_1)\)\(\rho_i(v_4)\)\(\rho_i(v_5)\)
\(\rho_1\)\(v_1\)\(v_4\)\(v_5\)
\(\rho_4\)\(v_4\)\(v_5\)\(v_1\)
\(\rho_5\)\(v_5\)\(v_1\)\(v_4\)
[Table5-2]
Transformation table for \(\rho_i(\alpha,\beta,\gamma)\) in \(A_3\)
\( i \backslash j \)\(\rho_i(\alpha)\)\(\rho_i(\beta)\)\(\rho_i(\gamma)\)
\(\rho_1\)\(\alpha\)\(\beta\)\(\gamma\)
\(\rho_4\)\(\beta\)\(\gamma \)\(\alpha\)
\(\rho_5\)\(\gamma\)\(\alpha\)\(\beta\)
[Table5-3]
Transformation table for \(\rho_i(Y_i)\) in \(A_3\)
\( i \backslash j \)\(\rho_i(Y_1)\)\(\rho_i(Y_2)\)\(\rho_i(Y_3)\)
\(\rho_1\)\(x+v_1-\alpha\)\(x+v_1-\beta\)\(x+v_1-\gamma\)
\(\rho_4\)\(x+v_4-\beta\)\(x+v_4-\gamma\)\(x+v_4-\alpha\)
\(\rho_5\)\(x+v_5-\gamma\)\(x+v_5-\alpha\)\(x+v_5-\beta\)

In [Table5-3], we color the group of linear factors \(\{\rho_i(Y_1),\rho_i(Y_2),\rho_i(Y_3)\}\) according to the subsets formed under the action of \(A_3\). Then the coloring of the nine linear factors in (4.1) becomes (4.3).
Next, we collect the linear factors of the same color and define their products to be the polynomials \(\{ \ H_1,H_2,H_3 \ \}\) as in (4.4).

\begin{align} Res(f(x+v),g(v),v)=(-1)& \left\{\bbox[#FFFF00]{ (x+v_1-\alpha) }\bbox[#7FFF00]{(x+v_1-\beta)}\bbox[#00FFFF]{(x+v_1-\gamma)} \right \} \notag \\ \times &\left\{\bbox[#00FFFF]{ (x+v_4-\alpha)}\bbox[#FFFF00]{ (x+v_4-\beta)}\bbox[#7FFF00]{(x+v_4-\gamma)} \right \} \notag \\ \times &\left\{\bbox[#7FFF00]{(x+v_5-\alpha)}\bbox[#00FFFF]{(x+v_5-\beta)}\bbox[#FFFF00]{ (x+v_5-\gamma)} \right \} \\ \notag \\ &\Downarrow \notag \\ \end{align} \begin{align} H_1=\prod_{i \ \in A_3} \rho_i \bigl(Y_1\bigr) &= \bbox[#FFFF00]{(x+ v_1-\alpha)(x+ v_4-\beta)(x+ v_5-\gamma)} \notag \\ H_2=\prod_ {i \ \in A_3}\rho_i \bigl(Y_2\bigr) &=\bbox[#7FFF00]{(x+ v_1-\beta)(x+ v_4-\gamma)(x+ v_5-\alpha)} \\ H_3=\prod_{i \ \in A_3} \rho_i \bigl(Y_3\bigr) &=\bbox[#00FFFF]{(x+ v_1-\gamma)(x+ v_4-\alpha)(x+ v_5-\beta)} \notag \\ &\quad \Downarrow \notag \\ \notag \\ Res( \ f(x + v), \ &g(v), \ v)=(-1) \cdot H_1 \cdot H_2 \cdot H_3 \\ \notag \\ \rho_i\bigl(H_j\bigr)=H_j \quad [ \ &\rho_i \in A_3 \ ],\ [j=1,2,3] \quad \Rightarrow \quad \therefore \ \{H_1,H_2,H_3\} \ \in \ F_0[x] \\ \end{align}


As in (4.4), the three polynomials \(\{H_j\}\) obtained by grouping identical colors are invariant under the action of the Galois group \(Gal(F_0(v)/F_0)=A_3\). Moreover, as the computations below (4.7) show, \(\{H_j\}\) are polynomials in \(F_0[x]\). Therefore the resultant in (4.1) factors as the product of three polynomials \(\{H_1,H_2,H_3\}\) over \(F_0[x]\), as in (4.5). This answers the question raised in [5-2].


Since \(\{H_j\}\) are not invariant under the full symmetric group \(S_3\), one cannot in general assert that they are polynomials over \(F_0\). However, because we reduce modulo the minimal polynomial \(g(v)\) generating the extension field \(F_0(v)\), it can be verified that they do lie in \(F_0[x]\).
Note that the following discussion assumes we already know the expressions of \(\{\alpha,\beta,\gamma\}\) and \(\{v_1,v_4,v_5\}\) as polynomials in \(v\). We will shamelessly borrow the results of Chapter 4 to carry out the computation.

\begin{align} &\left[ \quad \alpha =\frac{6-{{v}^{2}}}{3}, \quad \beta =\frac{2 {{v}^{2}}-3 v-12}{3}, \quad \gamma=\frac{-{{v}^{2}}+3 v+6}{3} \quad \right]\\ \notag \\ &[ \quad {v_1}=v, \quad {v_4}=-{{v}^{2}}+v+6, \quad {v_5}={{v}^{2}}-2 \quad ] \\ \notag \\ &\qquad \qquad \Downarrow \notag \\ \end{align}

\begin{align} \notag \\ \bbox[#FFFF00]{ H_1 }&=(x+v_1-\alpha)(x+v_4-\beta)(x+v_5-\gamma) \notag \\ &=\biggl(x+v-\frac{6-{{v}^{2}}}{3}\biggr)\biggl(x+(-v^2+v+6)-\frac{2 {{v}^{2}}-3 v-12}{3} \biggr)\biggl(x+(v^2-2v-6)-\frac{-{{v}^{2}}+3 v+6}{3}\biggr) \notag \\ & =x^3-21x+37 \quad (mod \ g(v)) \notag \\ \notag \\ \bbox[#7FFF00]{ H_2 }&=(x+v_1-\beta)(x+v_4-\gamma)(x+v_5-\alpha) \notag \\ &=\biggl(x+v-\frac{2 {{v}^{2}}-3 v-12}{3} \biggr)\biggl(x+(-v^2+v+6)-\frac{-{{v}^{2}}+3 v+6}{3}\biggr)\biggl(x+(v^2-2v-6)-\frac{6-{{v}^{2}}}{3}\biggr) \notag \\ &=x^3-12x-8 \quad (mod \ g(v)) \notag \\ \notag \\ \bbox[#00FFFF]{ H_3 }&=(x+v_1-\gamma)(x+v_4-\alpha)(x+v_5-\beta) \notag \\ &=\biggl(x+v-\frac{-{{v}^{2}}+3 v+6}{3}\biggr)\biggl(x+(-v^2+v+6)-\frac{6-{{v}^{2}}}{3}\biggr)\biggl(x+(v^2-2v-6)-\frac{2 {{v}^{2}}-3 v-12}{3} \biggr) \notag \\ &=x^3-3x+1 \quad (mod \ g(v)) \notag \\ \end{align}

\begin{align} \notag \\ \therefore \ Res(f(x+v),g(v),v) &=(-1)(x^3-21x+37)(x^3-12x-8)(x^3-3x+1) \notag \\ &=(-1) \cdot H_1 \cdot H_2 \cdot H_3 \notag \\ \end{align}


In this way we have confirmed that \(\{H_j\}\) are polynomials over \(F_0\).
One cautionary remark: in the computation above we happened to have \(\{R_i(x)=H_i\}\)! This is purely accidental. When factoring the degree-9 polynomial in (2.5) into three factors, the order in which the factors are listed is arbitrary. Hence the ordering of \(\{R_i(x)\}\) in (2.7) and that of \(\{H_i\}\) merely coincided by chance.

\(\quad \)
home \(\quad \)