The Fundamental Theorem of Algebra (with Galois Theory)

This post assumes familiarity with some basic concepts in abstract algebra, specifically the terminology of field extensions, and the classical results in Galois theory and group theory.

The fundamental theorem of algebra has quite a few number of proofs (enough to fill a book!). In fact, it seems a new tool in mathematics can prove its worth by being able to prove the fundamental theorem in a different way. This series of proofs of the fundamental theorem also highlights how in mathematics there are many many ways to prove a single theorem, and in re-proving an established theorem we introduce new concepts and strategies. And perhaps most of all, we accentuate the unifying beauty of mathematics.

Problem: Let p(x) \in \mathbb{C}[x] be a non-constant polynomial. Prove p(x) has a root in \mathbb{C}.

Solution: Without loss of generality, we may assume p(x) \in \mathbb{R}[x] has real coefficients, since if p(x) has no roots, then neither does p(x)\overline{p(x)},  where the bar represents complex conjugation. In particular, p(x)\overline{p(x)} is invariant under complex conjugation, and all such quantities are real.

Let F be the splitting field for p(x) over \mathbb{R}, and embed F in some algebraic closure of \mathbb{R}. Consider the extension F(i). We claim F(i) is Galois over \mathbb{R}; indeed, it is the splitting field of the separable polynomial constructed as the square-free part of p(x)(x^2 + 1), i.e., the product of all linear factors of that polynomial.

Let G be the Galois group of this extension over \mathbb{R}, and note that since i \in F(i), we have an intermediate field \mathbb{R} \subset F \subset F(i), so that the degree of the extension F \subset F(i) is 2; so 2 divides the degree of \mathbb{R} \subset F(i), and hence the order of the Galois group G (recall |\textup{Aut}_{k}(F)| = [F : k] for any Galois field extension).

Since 2 \big | |G|, there is a Sylow 2-subgroup H \subset G, which by Sylow’s theorem has odd index in G. By the Galois correspondence, H corresponds to an intermediate field extension \mathbb{R} \subset E \subset F(i) of odd degree (the degree is equal to the index of the subgroup H). Since every real polynomial of odd degree has a root in \mathbb{R} (recall the intermediate value theorem), we see that there are no irreducible polynomials of odd degree d > 1, and hence there can be no separable extensions of degree d (in particular, every such extension is finite and separable, and all such extensions are simple: the minimal polynomial of the singly-adjoined element must be irreducible). Hence, the degree of E over \mathbb{R} must be 1, i.e. E = \mathbb{R} is a trivial extension.

Taking this back to the group, since the index [G:H] = [E:\mathbb{R}] by the Galois correspondence, we have [G:H] = 1, and hence G=H has order 2^n for some n. We note that since \mathbb{C} = \mathbb{R}(i) \subset F(i), F(i) is a Galois extension of \mathbb{C}. In particular the automorphism group G' = \textup{Aut}_{\mathbb{C}}(F(i)) is a subgroup of G, and hence has order 2^k for some k dividing n. We will show that k=0, which occurs precisely when the extension is trivial (again, by virtue of being a Galois extension).

If k > 0, then we recall the corollary of Cauchy’s theorem for p-groups, that G' has a subgroup of order 2^j for any j < k, and in particular a subgroup of index 2. But such a subgroup corresponds to an intermediate field extension of degree 2. As with the case for odd extensions of \mathbb{R}, we note that there are no irreducible polynomials of degree 2 over \mathbb{C}: we have the sing-a-long quadratic formula which constructs the roots in \mathbb{C}. So k=0, and hence F(i) = \mathbb{C} is the splitting field of p(x), and contains all of its roots. \square

Handshake Lemma

Problem: Prove or disprove: at a party of n people, there must be an even number of people who have an odd number of friends at the party.

Solution: Let P be the set of all people, and for any person p \in P, let d(p) be the number of friends that person has. Let f be the total number of friendships between pairs of people at the party. Since each friendship among two friends at the party concerns exactly two people, we see that the following is true:

\displaystyle \sum_{p \in P} d(p) = 2f

In other words, counting up all of the number of friends that each person has will always be twice the number of total friendships. In particular, this number is always even. If there were an odd number of people with an odd number of friends at the party, and everyone else had an even number of friends, then the total number \sum_{p \in P} d(p) would necessarily be odd.

Hence, there can only be an even number of people with an odd number of friends at the party. \square

Discussion: This is a proof by “double-counting,” so to speak. Double counting proves an identity by showing that each side of the equality can be thought of as a different way of counting elements in the same set. In the above proof, we are counting the set of one-sided friendships in two different ways.

This technique comes up all over mathematics (particularly in combinatorics, the field of maths concerned with counting things). We can relate this to graph theory (see our very basic introduction to the topic), by seeing that a party is just a graph where the vertices are people and the edges are friendships. This theorem then says that for any graph, the sum of the degrees of each vertex is twice the number of edges, and hence always even.

Double counting has been used to prove a number of identities, and it can even be used to prove something as interesting as Fermat’s Little Theorem (which has quite a few proofs, and quite a few uses!) and counting the number of trees made from a set of n distinct vertices (it’s quite large: O(n^n) in fact!).

The Fundamental Theorem of Algebra (with the Fundamental Group)

This post assumes familiarity with some basic concepts in algebraic topology, specifically what a group is and the definition of the fundamental group of a topological space.

The fundamental theorem of algebra has quite a few number of proofs (enough to fill a book!). In fact, it seems a new tool in mathematics can prove its worth by being able to prove the fundamental theorem in a different way. This series of proofs of the fundamental theorem also highlights how in mathematics there are many many ways to prove a single theorem, and in re-proving an established theorem we introduce new concepts and strategies. And perhaps most of all, we accentuate the unifying beauty of mathematics.

Problem: Let p(z) be a non-constant polynomial with coefficients in \mathbb{C}. Prove p(z) has a root in \mathbb{C}.

Solution: We may assume without loss of generality that p(z) is monic. So let

\displaystyle p(z) = a_0 + a_1z + \dots + a_{n-1}z^{n-1} + z^n.

Supposing p(z) has no roots in \mathbb{C}, we will show p is constant. First, consider for a fixed r \in \mathbb{C} the loop

\displaystyle f_r(s) = \frac{p(re^{2 \pi is})/p(r)}{\left | p(re^{2 \pi is})/p(r) \right |}

Indeed, by assumption the denominators are never zero, so this function is continuous for all s \in [0,1]. Further, each value f_r(s) is on the unit circle in \mathbb{C} by virtue of the scaling denominator (|f_r(s)| = 1 for all s,r). Finally, f_r(0) = (p(r)/p(r)) / |p(r)/p(r)| = 1, and f_r(1) yields the same value, so this is a closed path based at 1.

We note this function is continuous in both s and r (indeed, they are simply rational functions defined for all s,r), so that f_r(s) is a homotopy of loops as r varies. If r=0, then the function is constant for all s, and so for any fixed r, the loop f_r(s) is homotopic to the constant loop.

Now fix a value of r which is larger than both |a_0| + \dots + |a_{n-1}| and 1. For |z| = r, we have

\displaystyle |z^n| = r \cdot r^{n-1} > (|a_0| + \dots + |a_{n-1}|)|z^{n-1}|

And hence |z^n| > |a_0 + a_1z + \dots + a_{n-1}z^{n-1}|. It follows that the polynomial p_t(z) = z^n + t(a_{n-1}z^{n-1} + \dots + a_0) has no roots when both |z| = r and 0 \leq t \leq 1. Fixing this r, and replacing p with p_t(z) in the formula for f_r(s), we have a homotopy from f_r(s) (when t=1, nothing is changed) to the loop which winds around the unit circle n times, where n is the degree of the polynomial. Indeed, plug in t=0 to get f_r(s) = (r^ne^{2 \pi ins}/r^n)/|r^ne^{2 \pi ins}/r^n|, which is the loop \omega_n(s) = e^{2 \pi ins}.

In other words, we have shown that the homotopy classes of f_r and \omega_n are equal, but f_r is homotopic to the constant map. Translating this into fundamental groups, as \pi_1(S^1,1) = \mathbb{Z}, we note that [\omega_n] = [f_r] = 0, but if \omega_n = 0 then it must be the case that n = 0, as \mathbb{Z} is the free group generated by \omega_1. Hence, the degree of p to begin with must have been 0, and so p must be constant. \square

The Fundamental Theorem of Algebra (with Liouville)

This proof assumes knowledge of complex analysis, specifically the notions of analytic functions and Liouville’s Theorem (which we will state below).

The fundamental theorem of algebra has quite a few number of proofs (enough to fill a book!). In fact, it seems a new tool in mathematics can prove its worth by being able to prove the fundamental theorem in a different way. This series of proofs of the fundamental theorem also highlights how in mathematics there are many many ways to prove a single theorem, and in re-proving an established theorem we introduce new concepts and strategies. And perhaps most of all, we accentuate the unifying beauty of mathematics.

Problem: Let p(x) be a non-constant polynomial with coefficients in \mathbb{C}. Prove p(x) has a root in \mathbb{C}.

Solution: First, we note that Liouville’s theorem states that any bounded entire function (has infinitely many derivatives, is analytic/holomorphic) \mathbb{C} \to \mathbb{C} is constant. In other words, if we can find a number M such that |f(z)| < M for all z \in \mathbb{C}, then f(z) = c for some constant c. The proof of this follows from Cauchy’s integral formula, and we take it for granted here.

Suppose to the contrary that p(x) is non-constant and has no roots. Then the function f(z) = \frac{1}{p(z)} is defined everywhere on \mathbb{C} and is analytic (the denominator is never zero by assumption). Now if

\displaystyle p(z) = a_nz^n + a_{n-1}z^{n-1} + \dots + a_0

Then we have

\displaystyle |f(z)| = \left | \frac{1}{p(z)} \right | = \frac{1}{|z|^n} \frac{1}{\left | a_n + \frac{a_{n-1}}{z} + \dots + \frac{a_0}{z^n} \right |}

Now each term in the denominator of the rightmost term, we have \frac{a_i}{z^{n-i}} \to 0 as z \to \infty. Therefore, |f(z)| \to \frac{1}{|a_n||z|^n} \to 0 as z \to \infty.

In particular, we may pick R sufficiently large so that |f(x)| < 1 whenever |z| > R. On the other hand, since f(z) is continuous on the closed, bounded disk centered at 0 of radius R, f(z) is also bounded whenever |z| \leq R. Together these two imply that f(z) is bounded everywhere on \mathbb{C}, and so f = 1/p = c, so p = 1/c is constant as well. This contradicts the assumption that p is non-constant, and hence p has a zero. \square