### A Whirlwind Tour of Galois Theory

*translated*,

*for a. and j.*

A few years ago I found an abstract algebra book at a used book sale. Although I knew I'd probably never read it I bought it anyway, 'cause it costed just one buck and I can't never say no to cheap books! Said book stayed quietly on my bookshelf for many months, and I'd totally forget about its existence if one day I didn't suddenly found myself wanting to solve a pretty cool problem, which is proving that 26 is the only natural number preceded by a square (25) and succeeded by a cube (27). People on Yahoo! Answers told me that it's a theorem by Fermat, and if I wanted to prove it I needed to know more about Unique Factorization Domain, but this is exactly the title of one of the chapters in that \$1 book!

I started reading it, and immediately got hooked to its chatty tone, and soon spent many evenings solving the exercises or searching for solutions. Eventually I got to prove that unique property of 26 (yay!), but the book offers more than that -- its second half is devoted to Galois and the theory named after him. I first heard about Galois when I was a kid, and always been inspired by his life story ever since. I was so excited having a chance getting to understand Galois's ideas, but the chapters became, however, more and more confusing. Perhaps the informal style, which has worked well for elementary stuff, backfires somewhat when it comes to an advanced theory that has many layers of abstraction. Perhaps it's just me not smart enough.

I kept pushing anyway, even doubling down after learning that Galois theory is also used in the theory of elliptic curves, another topic that I really want to master. Eventually things became clearer. I guess it's true that one can make oneself smarter by working harder. I got to understand the individual theorems, but didn't see the big picture until I tried to do this simple looking exercise:

**: find the minimal polynomial $f(x) \in \mathbb{Q}[x]$ (i.e., its coefficients are rational) that accepts $\epsilon= 1 + \sqrt[3]{2} + \sqrt[3]{4}$ as a root.**

__Exercise__An elementary solution is to set $f(x) = x^3 + ax^2 +bx + c$, and turn the equation $f(\epsilon) = 0$ into a system of equations in $a$, $b$, and $c$. That's actually my first attempt, but the calculation was so laborious that I abandoned it after a few minutes. I'm going to show you a more elegant elegant solution, which should also demonstrate some of the ideas behind Galois theory.

Galois discovered that if one knows a root of $f(x)$ one can easily calculate the other roots. Let $\delta$ và $\omega$ be the other two roots, we have

\[

\begin{equation}

f(x) = (x - \epsilon) (x - \delta) (x - \omega)

\end{equation}

\label{eq:f(x)}

\]

thus, the coefficients can be computed

$$

\begin{align*}

- a &= \epsilon+ \delta+ \omega \\

b &= \epsilon\delta+ \epsilon\omega + \omega\delta\\

-c & = \epsilon\delta\omega

\end{align*}

$$

Because $\epsilon \notin \mathbb{Q}$ in order to reduce $f(x)$ into linear polynomials as in $\eqref{eq:f(x)}$, we have to extend $\mathbb{Q}$. If you're not familiar with field extension, the following example might help.

**: Consider $g(x) = x^2 - 2$. We can prove that $g(x)$ is an irreducible polynomial in $\mathbb{Q}$. In other words, it's impossible to reduce $g(x)$ into multiplicity of linear polynomials with rational coefficients. If we, however, extend $\mathbb{Q}$ by adjoining $\sqrt{2}$ to create $\mathbb{Q}(\sqrt{2})$, $g(x)$ is no long irreducible**

__Example 1__$$

\begin{equation*}

g(x) = (x - \sqrt{2})(x + \sqrt{2})

\end{equation*}

$$

$\mathbb{Q}$ is a field, and

$$

\mathbb{Q}(\sqrt{2}) = \{a + b\sqrt{2}\ |\ a,\ b \in \mathbb{Q}\}

$$

is, too. Note that $\mathbb{Q}(\sqrt{2})$ is a 2-dimensional vector space over $\mathbb{Q}$. Because $\mathbb{Q} \subset \mathbb{Q}(\sqrt{2})$, we say that $\mathbb{Q}(\sqrt{2})$ is an extension of degree 2 over $\mathbb{Q}$. Because $-\sqrt{2} \in \mathbb{Q}(\sqrt{2})$, $\mathbb{Q}(\sqrt{2})$ contains all the roots of $g(x)$, and thus is the splitting field of $g(x)$. The name comes from the fact that $g(x)$ splits completely into linear polynomials over $\mathbb{Q}(\sqrt{2})$. In other words, the splitting field of a polynomial contains all its roots.

Galois discovered that the group of automorphisms of the splitting field of a polynomial permutes its roots. Let $G = \{\sigma_0, \sigma_1,...,\sigma_n\}$, where $\sigma_i$ is an automorphism of the splitting field of $f(x)$ (we're going to define it in the next paragraph.) If we know $G$ and a root $\epsilon$, we can compute all other roots by computing $\sigma_i(\epsilon)$.

Let's go back to example 1. $\mathbb{Q}(\sqrt{2})$ is the splitting field of $g(x)$. Let $\sigma$ là be an automorphism of $\mathbb{Q}(\sqrt{2})$. By definition, $\sigma$ is a bijective $\sigma:\ \mathbb{Q}(\sqrt{2}) \rightarrow \mathbb{Q}(\sqrt{2})$ satisfying

$$

\begin{align*}

&\sigma(\alpha + \beta) = \sigma(\alpha) + \sigma(\beta) \\

&\sigma(\alpha\beta) = \sigma(\alpha)\sigma(\beta)

\end{align*}

$$

for all $\alpha,\ \beta \in \mathbb{Q}(\sqrt{2})$. Thus, $\sigma$ is an isomorphism from $\mathbb{Q}(\sqrt{2})$ to itself.

It's trivial to prove that $\sigma(0) = 0$ and $\sigma(1) = 1$, thus $\sigma(a) = a$ với mọi $a \in \mathbb{Q}$. We say that $\sigma$ fixes $\mathbb{Q}$. Consider $\sigma(a + b\sqrt{2})$, for $a,\ b \in \mathbb{Q}$

It's trivial to prove that $\sigma(0) = 0$ and $\sigma(1) = 1$, thus $\sigma(a) = a$ với mọi $a \in \mathbb{Q}$. We say that $\sigma$ fixes $\mathbb{Q}$. Consider $\sigma(a + b\sqrt{2})$, for $a,\ b \in \mathbb{Q}$

$$

\begin{align*}

\sigma(a + b\sqrt{2}) &= \sigma(a) + \sigma(b\sqrt{2}) \\

&= a + \sigma(b)\sigma(\sqrt{2}) \\

&= a + b\sigma(\sqrt{2})

\end{align*}

$$

Hence, the action of $\sigma$ on $\mathbb{Q}(\sqrt{2})$ completely depends on its action on $\sqrt{2}$.

$$

\begin{align*}

\sigma(g(\sqrt{2})) &= \sigma(0) \\

\rightarrow \sigma(\sqrt{2})^2 - 2) &= 0 \\

\rightarrow \sigma(\sqrt{2})^2) - \sigma(2) &= 0 \\

\rightarrow (\sigma(\sqrt{2}))^2 - 2 &= 0

\end{align*}

$$

Because $g(x)$ has two roots $\pm\sqrt{2}$, thus $\sigma(\sqrt{2}) = \pm\sqrt{2}$. That means the set of automorphisms of $\mathbb{Q}(\sqrt{2})$, denote as $AUT(\mathbb{Q}(\sqrt{2}))$, consists of two elements

$$

\begin{align*}

\sigma_0(a + b\sqrt{2}) &= a + b\sqrt{2} \\

\sigma_1(a + b\sqrt{2}) &= a - b\sqrt{2}

\end{align*}

$$

$\sigma_0$ is the identity automorphism, because $\sigma_0(\alpha) = \alpha$ for all $\alpha \in \mathbb{Q}(\sqrt{2})$. Thus $AUT(\mathbb{Q}(\sqrt{2}))$ is isomorphic to $\mathbb{Z}/2\mathbb{Z}$.

I hope that the last example has demonstrated somewhat the beauty of Galois theory. Our original problem can be solved in the same way. Let me restate it here so that you don't have to scroll up:

Let $\mathbb{K}$ be the splitting field of $f(x)$. $\mathbb{K}$ is a finite extension of $\mathbb{Q}$ by adjoining roots of $f(x)$. In other to find the other roots, we need to know $AUT(\mathbb{K})$, but in order to compute $AUT(\mathbb{K})$, we need to know $\mathbb{K}$. How do we obtain $\mathbb{K}$ without knowing roots of $f(x)$?

Galois showed that because $\epsilon \in \mathbb{Q}(\sqrt[3]{2})$, $f(x)$ will split completely in the splitting field $\mathbb{E}$ of $r(x) = x^3 - 2$. In other words, $\mathbb{K}$ is a subfield of $\mathbb{E}$.

Let $\alpha$ be a root of $f(x)$ in $\mathbb{E}$. Consider the series $\alpha_0, \alpha_1,...,\alpha_n$ in which $\alpha_i = \sigma_i(\alpha)$ and $AUT(\mathbb{E}) = \{\sigma_i\}$. $\alpha_i$ are the result of the group of automorphisms of E acting on $\alpha$. Let $A = \{\alpha_0, \alpha_1,...,\alpha_r\}$ be the set of the unique elements amongst $\alpha_i$. We can prove that

$$

\begin{equation*}

p(x) = (x - \alpha_0)(x - \alpha_1)...(x - \alpha_r)

\end{equation*}

$$

This is the result that we use in Example 2. This trick is so important that I'm going to repeat it one more time: for a polynomial, if we know one of its roots and the group of automorphisms of its splitting field, we can compute all other roots. We already know $\epsilon$, we just need to obtain $AUT(\mathbb{E})$.

Note that $\mathbb{E} \neq \mathbb{Q}(\sqrt[3]{2})$. In fact $\mathbb{Q}(\sqrt[3]{2})$ is a proper subset of $\mathbb{E}$. According to the fundamental theorem of algebra $r(x)$ has 3 roots in the field of complex numbers, but $\mathbb{Q}(\sqrt[3]{2})$ contains only one real root, which is $\sqrt[3]{2}$, but not the other two complex roots:

$$

\begin{align*}

\zeta_0 &= \sqrt[3]{2}\mu \\

\zeta_1 &= \sqrt[3]{2}\mu^2

\end{align*}

$$

in which $\mu = \frac{-1 + 3i}{2}$ is the 3rd primitive root of unity. Because $\zeta_0$ and $\sqrt[3]{2}$ are in $\mathbb{E}$, its quotient which is $\mu$ is also in $\mathbb{E}$. Thus, $\mathbb{E} = \mathbb{Q}(\sqrt[3]{2}, \mu)$, in other words $\mathbb{E}$ is an extension of $\mathbb{Q}$ by adjoining $\sqrt[3]{2}$ và $\mu$.

Now we can compute $AUT(\mathbb{E})$, as we did in Example 1. With that we can compute the other roots of $f(x)$ by computing the result of the automorphisms acting on $\epsilon$. But there is a shortcut!

Observe that because $\epsilon \in \mathbb{Q}(\sqrt[3]{2})$, $f(x)$ is at most degree 3. $f(x)$ can't have degree 1 because $\epsilon \not\in \mathbb{Q}$. It can't have degree 2 because its degree must divide 3. Thus, $f(x)$ has degree 3 and, thus has 3 roots.

Because $\epsilon= 1 + \sqrt[3]{2} + \sqrt[3]{4}$, the results of $AUT(\mathbb{E})$ acting on $\epsilon$ are completely determined by the actions of the automorphisms on $\sqrt[3]{2}$. But $AUT(\mathbb{E})$ acting on $\sqrt[3]{2}$ permutes the roots of $x^3 - 2 = 0$, thus we can immediately compute the other two roots of $f(x)$:

$$

\begin{align*}

\delta&= 1 + \zeta_0 + \zeta_0^2 \\

\omega &= 1 + \zeta_1 + \zeta_1^2

\end{align*}

$$

Using the facts that $\mu^3 = 1$, and $\mu$ and $\mu^2$ are roots of $\phi(x) = x^2 + x + 1$, we can see that $f(x) = x^3 - 3x^2 - 3x - 1$. Wolfram Alpha seems to agree with us, fortunately!

Based on these ideas and with some calculations one can come up with the scary-looking formulas of general solutions of polynomials of degree three and four, and also prove that there are no general solutions for polynomials of degree five or higher. If you want to learn how to do that yourself, I recommend reading A First Course In Abstract Algebra, the book that I bought for one buck. I also found Abstract Algebra of Dummit and Foote easy to understand.

---

Last September marked four years the day I joined Google. I thought I was hot shit when I started, but the longer I work there the more I see how crappy was I. I've probably learned more in the past four years than all previous combined. In my weirdest dreams, I wouldn't think that one day I'd understand Galois theory, let alone using it to do something useful, like crypto!

Happy times.

\begin{align*}

\sigma(a + b\sqrt{2}) &= \sigma(a) + \sigma(b\sqrt{2}) \\

&= a + \sigma(b)\sigma(\sqrt{2}) \\

&= a + b\sigma(\sqrt{2})

\end{align*}

$$

Hence, the action of $\sigma$ on $\mathbb{Q}(\sqrt{2})$ completely depends on its action on $\sqrt{2}$.

**: $\sigma(\sqrt{2})$ is a root of $g(x)$. Indeed, we have $g(\sqrt{2}) = 0$, applying $\sigma$ against two sides of the equation**__Observation__$$

\begin{align*}

\sigma(g(\sqrt{2})) &= \sigma(0) \\

\rightarrow \sigma(\sqrt{2})^2 - 2) &= 0 \\

\rightarrow \sigma(\sqrt{2})^2) - \sigma(2) &= 0 \\

\rightarrow (\sigma(\sqrt{2}))^2 - 2 &= 0

\end{align*}

$$

Because $g(x)$ has two roots $\pm\sqrt{2}$, thus $\sigma(\sqrt{2}) = \pm\sqrt{2}$. That means the set of automorphisms of $\mathbb{Q}(\sqrt{2})$, denote as $AUT(\mathbb{Q}(\sqrt{2}))$, consists of two elements

$$

\begin{align*}

\sigma_0(a + b\sqrt{2}) &= a + b\sqrt{2} \\

\sigma_1(a + b\sqrt{2}) &= a - b\sqrt{2}

\end{align*}

$$

$\sigma_0$ is the identity automorphism, because $\sigma_0(\alpha) = \alpha$ for all $\alpha \in \mathbb{Q}(\sqrt{2})$. Thus $AUT(\mathbb{Q}(\sqrt{2}))$ is isomorphic to $\mathbb{Z}/2\mathbb{Z}$.

**: find the minimal polynomial with integer coefficients that takes $\alpha_0 = 1 + \sqrt{2}$ as a root. As we've identified that $AUT(\mathbb{Q}(\sqrt{2})) = \{\sigma_0, \sigma_1\}$ and a root, we can immediately compute the other root which is $\alpha_1 = \sigma_1(1 + \sqrt{2}) = 1 - \sqrt{2}$, so $h(x) = x^2 - (\alpha_0 + \alpha_1)x + \alpha_0\alpha_1 = x^2 - 2x + 2$ is the answer.**__Example 2__I hope that the last example has demonstrated somewhat the beauty of Galois theory. Our original problem can be solved in the same way. Let me restate it here so that you don't have to scroll up:

**: find the minimal polynomial $f(x) \in \mathbb{Q}[x]$ (thus, its coefficients are rational) that takes $\epsilon= 1 + \sqrt[3]{2} + \sqrt[3]{4}$ as a root.**__Exercise__Galois showed that because $\epsilon \in \mathbb{Q}(\sqrt[3]{2})$, $f(x)$ will split completely in the splitting field $\mathbb{E}$ of $r(x) = x^3 - 2$. In other words, $\mathbb{K}$ is a subfield of $\mathbb{E}$.

**: all irreducible $p(x) \in \mathbb{Q}[x]$ having a root in $\mathbb{E}$ has all its roots in $\mathbb{E}$.**__Theorem__Let $\alpha$ be a root of $f(x)$ in $\mathbb{E}$. Consider the series $\alpha_0, \alpha_1,...,\alpha_n$ in which $\alpha_i = \sigma_i(\alpha)$ and $AUT(\mathbb{E}) = \{\sigma_i\}$. $\alpha_i$ are the result of the group of automorphisms of E acting on $\alpha$. Let $A = \{\alpha_0, \alpha_1,...,\alpha_r\}$ be the set of the unique elements amongst $\alpha_i$. We can prove that

$$

\begin{equation*}

p(x) = (x - \alpha_0)(x - \alpha_1)...(x - \alpha_r)

\end{equation*}

$$

This is the result that we use in Example 2. This trick is so important that I'm going to repeat it one more time: for a polynomial, if we know one of its roots and the group of automorphisms of its splitting field, we can compute all other roots. We already know $\epsilon$, we just need to obtain $AUT(\mathbb{E})$.

Note that $\mathbb{E} \neq \mathbb{Q}(\sqrt[3]{2})$. In fact $\mathbb{Q}(\sqrt[3]{2})$ is a proper subset of $\mathbb{E}$. According to the fundamental theorem of algebra $r(x)$ has 3 roots in the field of complex numbers, but $\mathbb{Q}(\sqrt[3]{2})$ contains only one real root, which is $\sqrt[3]{2}$, but not the other two complex roots:

$$

\begin{align*}

\zeta_0 &= \sqrt[3]{2}\mu \\

\zeta_1 &= \sqrt[3]{2}\mu^2

\end{align*}

$$

in which $\mu = \frac{-1 + 3i}{2}$ is the 3rd primitive root of unity. Because $\zeta_0$ and $\sqrt[3]{2}$ are in $\mathbb{E}$, its quotient which is $\mu$ is also in $\mathbb{E}$. Thus, $\mathbb{E} = \mathbb{Q}(\sqrt[3]{2}, \mu)$, in other words $\mathbb{E}$ is an extension of $\mathbb{Q}$ by adjoining $\sqrt[3]{2}$ và $\mu$.

Now we can compute $AUT(\mathbb{E})$, as we did in Example 1. With that we can compute the other roots of $f(x)$ by computing the result of the automorphisms acting on $\epsilon$. But there is a shortcut!

Observe that because $\epsilon \in \mathbb{Q}(\sqrt[3]{2})$, $f(x)$ is at most degree 3. $f(x)$ can't have degree 1 because $\epsilon \not\in \mathbb{Q}$. It can't have degree 2 because its degree must divide 3. Thus, $f(x)$ has degree 3 and, thus has 3 roots.

Because $\epsilon= 1 + \sqrt[3]{2} + \sqrt[3]{4}$, the results of $AUT(\mathbb{E})$ acting on $\epsilon$ are completely determined by the actions of the automorphisms on $\sqrt[3]{2}$. But $AUT(\mathbb{E})$ acting on $\sqrt[3]{2}$ permutes the roots of $x^3 - 2 = 0$, thus we can immediately compute the other two roots of $f(x)$:

$$

\begin{align*}

\delta&= 1 + \zeta_0 + \zeta_0^2 \\

\omega &= 1 + \zeta_1 + \zeta_1^2

\end{align*}

$$

Using the facts that $\mu^3 = 1$, and $\mu$ and $\mu^2$ are roots of $\phi(x) = x^2 + x + 1$, we can see that $f(x) = x^3 - 3x^2 - 3x - 1$. Wolfram Alpha seems to agree with us, fortunately!

Based on these ideas and with some calculations one can come up with the scary-looking formulas of general solutions of polynomials of degree three and four, and also prove that there are no general solutions for polynomials of degree five or higher. If you want to learn how to do that yourself, I recommend reading A First Course In Abstract Algebra, the book that I bought for one buck. I also found Abstract Algebra of Dummit and Foote easy to understand.

---

Last September marked four years the day I joined Google. I thought I was hot shit when I started, but the longer I work there the more I see how crappy was I. I've probably learned more in the past four years than all previous combined. In my weirdest dreams, I wouldn't think that one day I'd understand Galois theory, let alone using it to do something useful, like crypto!

Happy times.