Thursday, November 5, 2015

A Whirlwind Tour of Galois Theory

translatedfor 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:

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.

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.

Example 1: 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

$$
\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}$

$$
\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}$.

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

$$
\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}$.

Example 2: 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.

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:

Exercise: 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.

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}$.

Theorem: all irreducible $p(x) \in \mathbb{Q}[x]$ having a root in $\mathbb{E}$ has all its roots in $\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.

4 comments:

Thuong said...

I just want to clarify some implicit ideas. We can think that things can be obtained by the criterion of extension of field homomorphism. Let F_1, F_2 be fields, and F_1 is subfield of F_2; a is an element in F_2, that is algebraic over F_1, and f is its minimum polynomial. Let F be another field, then any isomorphism s from F_1 into F can be extended to an isomorphism from F_1(a) into F iff a is sent to b in F, such that f^s (it is the polynomial in F[x], whose coefficients are obtained by the action from s to all coefficients of f) is the minimum polynomial of b. From this, one can realize that the all extensions of isomorphism via splitting fields are obtained by permuting roots.

In characteristic 0, all polynomials is separable (that means, all polynomials is product of irreducible polynomials, whose have distinct roots in their splitting fields). And hence, any splitting field P of a polynomial f(x) over Q is Galois extension, and we have this fact, the only subfield of P fixed under the action from the group Gal(P/Q) is Q, the field of rational numbers.

To find the minimum polynomial over Q of an element p in P, we can compute the Galois group first. Assume that Gal(P/Q) = {s_1,...,s_n}, and set of all actions from Gal(P/Q) to p is {p^{s_1},...,p^{s_r}} where r is equal or less than n. We obtain the minimum polynomial of p is f_p(x) = (x - p^{s_1})...(x - p^{s_r}). It is obvious, because f_p(x) is invariant under the action from Gal(P/Q), and it implies all of its coefficients are in Q.

Things become much more interesting in the case of characteristic p, because there exists non-separable polynomials.

For the connections between Galois groups and elliptic curves, we can see in the book of L. C. Washington, or Silverman. In characteristic different from 2, 3; the Galois group acts on the curves (defined in a field k), and hence, it also acts on the n-torsion subgroups E[n]. We will consider here the case of finite fields. When gcd(n, char(k)) = 1, then the properties of Weil pairing allow us to obtain the matrix representation of elements in the Galois group, especially the Frobenius endomorphism. Interpret this into the language of linear algebra, we obtain the famous theorem of Hasse-Weil.

Thai Duong said...

Whoa. This is one of the best comments I've seen on my blog. Thanks, Thuong!

Thai Duong said...

BTW you can write Latex equations by putting them between \$ and \$.

Thuong said...

Thanks, I didn't know about this, and it seems I cannot edit my comment :-(. Hope to read your posts about Math and Crypto.