Every Finite Division Ring Is A Field

January 12, 2009

The Ring of Quaternions:

Consider the ring of quaternions \mathbb{H}=\{a+bi+cj+dk\bigm| a,b,c,d\in\mathbb{R}\}. We define multiplication with the identities ij=k, jk=i, ki=j, ji=-k,kj=-i,ik=-j.

We have the identity (a+bi+cj+dk)(a-bi-cj-dk) = a^2+b^2+c^2+d^2, so in particular every nonzero element is invertible, making \mathbb{H} “almost” a field. But multiplication is clearly not commutative.

A ring like \mathbb{H}, in which every nonzero element has an inverse, is called a division ring. (or sometimes a division algebra) All fields are division rings.

One interesting observation about \mathbb{H}: its center, or the set Z(\mathbb{H}) = \{x\in\mathbb{H}\bigm| \forall y\in\mathbb{H},  xy=yx\}, is simply \mathbb{R}, and \mathbb{H} is a 4-dimensional real vector space. It is easy to see that the center of any division ring is a field, but a deeper result is that the dimension of a division ring over its center is always either infinite or a perfect square.

Finite Division Rings:

Since the theory of finite fields is so rich, one might expect the same from the theory of finite division rings. But as the title of this post has no doubt suggested to you, there are no unexpected finite division rings. The remainder of this post will prove this surprising and nontrivial fact.


Let D be a finite division ring, and K=Z(D) its center. Say that |K|=q, then |D|=q^n for some n. The statement that D is a field is equivalent to n=1, so assume n>1.

We use some basic facts from group theory, namely the class equation, on the group D^\times = D-\{0\}. First, notice that if x\in D-K, the centralizer C(x)=\{y\bigm| xy=yx\} is a ring containing K, so it is a K-vector space and its order is q^{k_x} for some k_x < n. So the centralizer in D^\times has order q^{k_x} - 1. The class equation gives us:

q^n - 1 = q - 1 + \sum_x \frac{q^n-1}{q^{k_x}-1}

Now we need a little wishful thinking. What if q^n-1 was divisible by some prime that no smaller q^{k_x}-1 was divisible by? Then we’d have a contradiction and could finish the proof. Playing around with examples will show you that this is not true in general. For example, q=2, n=6 is a counterexample, as is q=2^k-1, n=2. But it turns out that these are the only counterexamples, which is a surprising result with a surprising name:

Zsigmondy’s Theorem: If a>b>0 are relatively prime integers, then for any natural number n>1 there is a prime number p that divides a^n-b^n and does not divides a^k-b^k for any positive integer k<n, with two exceptions:

  • a=2, b=1, and n=6.
  • a+b is a power of 2, n=2.

Every finite division ring is a field, assuming Zsigmondy’s Theorem:

I will present a (somewhat technical) proof of Zsigmondy in my next post. In the meantime, we are done with our original problem unless we are in one of the two exceptional cases.

Suppose that q=2 and n=6. Then the class equation reads 64-1 =2 - 1 + \sum_x \frac{2^6-1}{2^{k_x}-1}. But each term of the sum must equal \frac{2^6-1}{2^2-1}=21 or \frac{2^6-1}{2^3-1}=9, so we have 62=21a+9b. But the right side is divisible by 3 while the left is not, contradiction.

Now, suppose that n=2. Since every term in the right-hand sum must be \frac{q^2-1}{q-1}=q+1, we see that the left-hand side is divisible by q+1 but the right-hand side is not, contradiction.

We conclude that every finite division ring is a field.

Summoning Cthulhu: sin^2 + cos^2 with power series

January 6, 2009

I would like to dedicate this post to the Redditor AlanCrowe. When I claimed that working out the formula \mbox{sin}^2 + \mbox{cos}^2 = 1 using power series wouldn’t be that big of a deal, he said that this was “a rash thing to do” and that I would “end up summoning Cthulhu doing weird shit like that.”

How could I resist such a dare? The following manipulations contain no real mysteries; they are all direct applications of the binomial theorem and the distributive law. There is a small but transparent trick using complex numbers, which can be eliminated at the expense of more combinatorial footwork.

Disclaimer: Be careful working with power series. Power series may carry high voltages. Improper handling of power series may result in extreme divergence or serious mental anguish. Power series have no remorse. Do not taunt power series. If the double summations make you queasy, go for a short walk outside. I’ll wait.

Step 1:

\mbox{sin}\ x = x - \frac{x^3}{3!} + \frac{x^5}{5!}\ldots = \sum_n \frac{(i)^n-(-i)^n}{2in!} x^n

\mbox{sin}^2\ x = (\sum_n \frac{(i)^n-(-i)^n}{2in!} x^n)^2

= \sum_n x^n \sum_k (\frac{(i)^k-(-i)^k}{2ik!})(\frac{(i)^{n-k}-(-i)^{n-k}}{2i(n-k)!})

= \sum_n x^n i^n \sum_k \frac{-1 + (-1)^k + (-1)^{n-k} - (-1)^n}{4k!(n-k)!}

Step 2:

\mbox{cos}\ x = 1 - \frac{x^2}{2!} + \frac{x^4}{4!}\ldots = \sum_n \frac{(i)^n+(-i)^n}{2n!} x^n

\mbox{cos}^2\ x = (\sum_n \frac{(i)^n+(-i)^n}{2n!} x^n)^2

=\sum_n x^n \sum_k (\frac{(i)^k+(-i)^k}{2k!})(\frac{(i)^{n-k}+(-i)^{n-k}}{2(n-k)!})

= \sum_n x^n i^n \sum_k \frac{1 + (-1)^k + (-1)^{n-k} + (-1)^n}{4k!(n-k)!}

Step 3:

\mbox{sin}^2\ x + \mbox{cos}^2\ x = \sum_n x^n i^n \sum_k \frac{(-1)^k + (-1)^{n-k}}{2k!(n-k)!}

=\sum_n \frac{x^n i^n (1 + (-1)^n)}{2n!} \sum_k (-1)^k {n\choose k}

=\sum_n \frac{x^n i^n (1+(-1)^n)}{2n!} (1-1)^n = 1 + 0 + 0+\ldots = 1

UPDATE: notfancy has accused me of being a “cheater” for my use of complex numbers, claiming that I am relying on an implicit call to De Moivre’s theorem Euler’s formula. I have seen this view elsewhere as well, that the use of tricks like this is tantamount to pulling a rabbit out of a hat.

I have a somewhat different viewpoint. At the heart of the series for \mbox{sin} and \mbox{cos} is the periodic sequence 0,1,0,-1, 0,1\ldots. And surely the mathematical techniques for manipulating this series can be no simpler than the series itself! In other words, I feel that my observation that we can write this sequence as \frac{i^n + (-i)^n}{2} was just notational convenience and nothing more. My own style is to prefer algebra to case analysis because I tend to make more mistakes in the latter.

To illustrate this, I am presenting the same proof, without an appeal to complex numbers. It requires a little more thought, but is overall a much simpler-looking approach.

First, for the purpose of notation, we need to make an observation about power series. If f(x) = \sum_n \frac{a_n x^n}{n!} and g(x) = \sum_n \frac{b_n x^n}{n!}, then f(x)g(x) = \sum_n x^n \sum_k \frac{a_k b_{n-k}}{k! (n-k)!} = \sum_n \frac{x^n}{n!} \sum_k {n\choose k}a_k b_{n-k}. Nothing special here; just the distributive law. (if you are interested in going deeper into these kinds of manipulations of sequences, I highly recommend Wilf’s generatingfunctionology, available for free online)

In the same notation, if f(x)=\mbox{sin}\ x and g(x)=\mbox{cos}\ x, then a_n and b_n are the sequences 0, 1, 0, -1\ldots and 1,0,-1,0\ldots respectively.

Steps 1 and 2:

\mbox{sin}\ x = \sum_n \frac{a_n x^n}{n!}

\mbox{sin}^2\ x = \sum_n \frac{c_n x^n}{n!}

where c_n = \sum_k {n\choose k} a_k a_{n-k}, and

\mbox{cos}\ x = \sum_n \frac{b_n x^n}{n!}

\mbox{cos}^2\ x = \sum_n \frac{d_n x^n}{n!}

where d_n = \sum_k {n\choose k} b_k b_{n-k}

Step 3:

\mbox{sin}^2\ x + \mbox{cos}^2\ x = \sum_n \frac{x^n}{n!} e_n

where e_n = c_n + d_n.

We have c_0 = 0 and d_0=1, so e_0=1. All that remains to be shown is that e_n=0 for all n>0.

First, suppose that n is odd. Then a_k a_{n-k} = b_k b_{n-k}=0 for all k, so e_n = 0.

Now, suppose that n=2m is even. Then c_n = (-1)^{m+1}( {n\choose 1} + {n\choose 3}+\ldots + {n\choose {n-1}} ) and d_n = (-1)^m ({n\choose 0} + {n\choose 2}\ldots+ {n\choose n}). Hence e_n = c_n + d_n = (-1)^m ({n\choose 0} - {n\choose 1} + {n\choose 2}\ldots + {n\choose n}) = (-1)^m (1-1)^n = 0.

All About (regular) n-gons—session at the Berkeley Math Circle

December 21, 2008

Last Tuesday I gave a talk at the Berkeley Math Circle titled “All About (regular) n-gons”. This was a sort of problem seminar that covered a mixed bag of mathematical tricks, but one focus was the use of complex numbers in geometry.

You can download my handout here. The questions range from fairly basic geometry to research questions—the question “How many intersection points are formed when we draw all the diagonals of a regular n-gon?” is much more difficult than it appears at first; it was first answered in closed form by Poonen and Rubenstein in 1997.

There was a follow-up problem session this morning, which discussed some of the harder questions. (though I have yet to see solutions to either of the Miklós Schweitzer problems) I was impressed to see more than half a dozen students, many of them in junior high, spend two hours on Saturday morning like this.

The last time I talked at Berkeley Math Circle was in 2002, on generating functions.

Here are some of the more fun problems from my session this week:

  • What are all the values of n for which you can tile the plane with regular n-gons of varying size?
  • (Romania 1995) Find the number of ways of coloring the vertices of a regular n-gon with p colors, such that no two adjacent vertices have the same color.
  • Does there exist a regular n-gon such that exactly half of its diagonals are parallel to one of its sides?
  • Show that the sum of the squares of the lengths of all sides and diagonals emanating from a vertex of a regular n-gon inscribed in the unit circle is 2n.
  • (USAMO 1997) To clip a convex n-gon means to choose a pair of consecutive sides AB, BC and to replace them with three segments AM, MN, NC, where M is the midpoint of AB and N is the midpoint of BC. In other words, one cuts off the triangle MBN to obtain a convex (n+1)-gon. A regular hexagon P_6 of area 1 is clipped to obtain a heptagon P_7. Then P_7 is clipped (in one of the seven possible ways) to obtain an octagon P_8 and so on. Prove that no matter how the clippings are done, the area of P_n is greater than 1/3 for all n\geq 6.
  • (USAMO 2008) Let P be a convex polygon with n sides, n\geq 3. Any set of n-3 diagonals that do not intersect in the interior of a polygon determine a triangulation of P into n-2 triangles. If P is regular and there is a triangulation of P consisting only of isoceles triangles, find all possible values of n.

The Group of Units (mod n)

November 24, 2008

The ring \mathbb{Z}/n\mathbb{Z} is more interesting than it is often given credit for.  This post will tell you the isomorphism type of its group of units.

Why care about such a simple thing? Well first, the rings \mathbb{Z}/n\mathbb{Z} are universal, in the following sense. If R is any ring with unity, there exists a unique n\geq 0 and injective homomorphism f: \mathbb{Z}/n\mathbb{Z} \to R. n here is called the characteristic of R. It’s easy to find this homomorphism: there is a natural map \mathbb{Z}\to R, and we factor out its kernel (which is of the form n\mathbb{Z}, \mathbb{Z} being a principal ideal domain).  So we should expect \mathbb{Z}/n\mathbb{Z} to come up anywhere that rings do (though n=1 only applies to a single ring, and n=0 is disproportionately common).

Theorem: If n=2^l \prod_i p_i^{a_i}, where the product is over odd primes, the group of units (\mathbb{Z}/n\mathbb{Z})^\times can be written as a product of cyclic groups \prod_i Z_{p^i - p^{i-1}} when l\leq 1 and Z_2 \times Z_{2^{l-2}} \times \prod_i Z_{p^i - p^{i-1}} when l\geq 2. In particular, the group of units is cyclic exactly when n is a power of an odd prime, twice a power of an odd prime, or 4.

The rest of this post will prove this theorem. First, the Chinese remainder theorem tells us that if n factors into primes as n=\prod_i p_i^{a_i}, then \mathbb{Z}/n\mathbb{Z} \cong \prod_i \mathbb{Z}/p_i^{a_i} \mathbb{Z}. So we only need to address the question when n=p^k is a power of a prime.

What are the invertible elements in \mathbb{Z}/p^k \mathbb{Z}? If p\bigm| a, then p^{k-1} a =0, so a cannot be invertible. Those who are quick on the draw with the number theory will be able to quickly show that if p does not divide a, then a is invertible in \mathbb{Z}/p^k \mathbb{Z}. (the standard technique here is to note that a and p^k are relatively prime, so we can choose integers x and y such that ax + p^k y = 1)

Since there are p^{k-1} elements divisible by p, it follows that \mathbb{Z}/p^k\mathbb{Z} has p^k-p^{k-1} units. (notice that this, along with the Chinese remainder theorem, gives us a nice formula for Euler’s phi function)

Proposition 1: When p is odd, the group of units of \mathbb{Z}/p^k\mathbb{Z} is a cyclic group of order p^k-p^{k-1}.

Proof: The case k=1 is actually the most difficult. It is a special case of a theorem which says that a finite subgroup of the multiplicative group of any field is cyclic. For a proof of this case, see e.g. here. (I will certainly discuss this topic in detail in a future post)

Suppose that \sigma is a generator for the group of units of \mathbb{Z}/p \mathbb{Z}. Then the order of \sigma\ (\rm{mod}\ p^k) is divisible by p-1, so it is of the form p^j (p-1). Then \sigma^{p^j} has order p-1. We claim that 1+p has order p^{k-1}, from which it follows that \tau = \sigma^{p^j} (1+p) has order p^{k-1} (p-1)=p^k -p^{k-1}.

What we really need to show here is that (1+p)^{p^{k-2}} - 1 is divisible by p^{k-1} but not p^k. But this is straightforward induction: if (1+p)^{p^{k-2}} = 1 + a p^{k-1} with a not divisible by p, then taking p-th powers we see that (1+p)^{p^{k-1}} = 1 + ap^k + (\ldots)p^{k+1}.

Proposition 2: If k\geq 3, the group of units of \mathbb{Z}/2^k\mathbb{Z} is the product of two cyclic groups, one of order 2, and one of order 2^{k-2}. If k\leq 2, the group of units of \mathbb{Z}/2^k\mathbb{Z} is cyclic.

Proof In fact, we will show that 5 generates a cyclic group of order 2^{k-2} that does not contain - 1, an element of order 2. (there is nothing special about 5 here—any choice that is 5\ (\rm{mod}\ 8) will work) We first show, by induction on k, that 5^{2^{k-3}} \equiv 1+2^{k-1}\ (\rm{mod}\ 2^k), the case k=3 being clear.

For k\geq 3, the inductive hypothesis now tells us that 5^{2^{k-3}} \equiv 1+2^{k-1}\ (\rm{mod}\ 2^k), so there is some a\in\{0,1\} such that 5^{2^{k-3}} \equiv 1+2^{k-1} + a 2^k\ (\rm{mod}\ 2^{k+1}). Squaring, we get 5^{2^{k-2}} \equiv 1+2^k\ (\rm{mod}\ 2^{k+1}).

Since 1+2^{k-1} is an element of order 2, this shows that 5 generates a cyclic group of order 2^{k-2}. So we just need to make sure that -1\not\in \langle 5\rangle. But a cyclic group can contain at most one element of order 2, and we have already shown 1+2^{k-1}\in\langle 5\rangle.

The second statement in the proposition is easily verified.

Exercise: Prove the second sentence of the theorem! (hint: for one direction, use the Chinese remainder theorem for cyclic groups, and for the other, count elements of order 2)

Fun With Group Actions

November 10, 2008

I had to take a bit of a break to move into my new apartment in the Castro, (which has, incidentally, been a pretty exciting place to live this past week) but now I’m all settled down and ready to tell you about group actions.

The basic idea of a group action is to visualize a group as a set of permutations of some set X, giving a homomorphism \phi: G\to S_{|X|}. A basic example would be the cyclic group Z_n acting on an n-gon by rotation. But here are some more interesting and general group actions for a group G:

  • G acts on G by left multiplication.
  • G acts on a normal subgroup of G by conjugation.
  • G acts on the set of subgroups of G of a fixed order, by conjugation.
  • If H\leq G, G acts on the set of left cosets of H by left multiplication.

All of these can provide useful information through the existence of homomorphisms to some symmetric group S_n. For an example of this technique, let’s consider this classic problem:


Problem: Show that any simple group of order 60 is isomorphic to A_5. (recall that a simple group is one with no nontrivial normal subgroups)

We make use of some basic Sylow theory. Let G be a simple group of order 60 and let k be the number of subgroups of G that have order 5. Sylow’s theorems tell us that k is a factor of 12 and is congruent to 1\ (\rm{mod}\ 5), so k\in \{1,6\}. If k=1, then the group of order 5 is normal, (do you see why?) so k=6.

Let G act on the set of subgroups of G of order 5, by conjugation. This gives a homomorphism \phi: G\to S_6. Because none of these subgroups can be normal (or again appealing to Sylow theory) it is easy to see that \phi\neq 1, so \ker{\phi}\neq G. But \ker{\phi} is a normal subgroup of G, so \ker{\phi}=1 and \phi is injective.

So we can imagine G as a subgroup of S_6. In fact, \phi(G)\leq A_6, as the following lemma will tell us:


Lemma: If H\leq S_n is a simple group of order larger than 2, H\leq A_n.

Proof: Let \sigma: S_n\to Z_2 be the sign homomorphism, so A_n = \ker{\sigma}. Then \ker{\sigma_H} is a normal subgroup of H. But \sigma_H cannot be injective, as |H|>|Z_2|, so \ker{\sigma_H} = H, in other words H\leq \ker{\sigma}=A_n.


Returning to our solution, we can now assume that G\leq A_6. Counting orders, we see that G has index 360/60=6. Let A_6 act on the set of left cosets of G by left multiplication, giving a homomorphism \psi: A_6 \to S_6. Pausing for a moment to verify that \psi\neq 1, the fact that A_6 is simple tells us that \psi is injective, and applying the lemma tells us easily that \psi:A_6\to A_6 is an isomorphism.

What is the image of G under this isomorphism? Well, let’s think about the action again. We have some cosets x_1 G, x_2 G, x_3 G, x_4 G, x_5 G, G. Multiplication on the left by elements of G is certainly not guaranteed to fix the first five, but it will always fix the last one. In other words, \psi(G)\leq S_5. So \psi(G)\leq S_5 \cap A_6=A_5.

Since |G|=|A_5|, it follows that \psi is an isomorphism carrying G to A_5, and we are done.


As we can see, group actions provide an excellent if somewhat magical way of reasoning about finite groups that are too big to be easily understood by hand. Make them part of your group theory toolbox.

The “Injectivity Implies Surjectivity” Trick

October 18, 2008

There is a standard proof technique involving the relationship between injectivity and surjectivity on “finite” structures. I rather like it—for the examples provided, it is very difficult to proceed without knowing the trick, even though the solutions are very simple.


Principle A: If S is a finite set and \phi: S\to S is a function, then \phi is injective if and only if \phi is surjective.

Proposition 1: If \mathbb{F} is a finite field and \phi:\mathbb{F}\to\mathbb{F} is a homomorphism of fields, then \phi is an isomorphism.

Proof: \ker{\phi} is an ideal of \mathbb{F}, but it cannot equal \mathbb{F}, (for \phi(1)=1) so \ker{\phi}=0 and \phi is injective. Therefore \phi is surjective.

Proposition 2: If G is a finite simple group and \phi:G\to G is a homomorphism, then \phi is an isomorphism or \phi\equiv e.

Proof: Either \ker{\phi}=G, in which case \phi\equiv e, or \ker{\phi}=\{e\}, in which case \phi is injective, so \phi is surjective.


Principle B: If V is a finite dimensional vector space and \phi:V\to V is a linear transformation, then \phi is injective if and only if \phi is surjective.

Proposition 3: If K is a field and A is an integral domain containing K with finite dimension over K, then A is a field.

Proof: It suffices to show that we can take inverses. Choose any nonzero a\in A, and consider the map \phi: A\to A defined by \phi(x) = ax. Then \phi is a linear transformation. Since A is an integral domain, \phi is injective, therefore \phi is surjective. So there exists some b\in A with \phi(b)=1, so ab=1.


Problem: Show that any finite integral domain is a field.


EDIT: As Steven points out in the comments, the following is also useful, and the proof is a good exercise:

Principle C: If M is a Notherian module then any surjective homomorphism \phi: M\to M is injective, and if M is an Artinian module, then any injective homomorphism \phi:M\to M is surjective. (hint: in fact, for any \phi:M\to M, if M is Noetherian, then for large enough n we have \ker{\phi^n} \cap \rm{image}\ \phi^n = 0. If M is Artinian, then for large enough n we have \ker{\phi^n} + \rm{image}\ \phi^n = M.)

An Easy Fallacy

October 12, 2008

For a change of pace today, I’ll present an incorrect proof of a simple proposition. The diligent reader can work out the location of the mistake before reading on, where I will present a modified proposition, and correct proof, before discussing the mistake in detail.

Proposition: If k is a field and c is a cardinal less than |k|, then a vector space over k cannot be written as a union of c of its proper subspaces.

Questionable Proof: Suppose that \{V_\alpha\} is a collection of c proper subspaces of V, which cover V. We can assume that no proper subcollection covers V. (we can remove the superfluous elements from our collection if this is not the case) This implies that for each \alpha, there exists some v_\alpha \in V_\alpha such that v_\alpha \not\in V_\beta for \beta\neq\alpha.

Take any \alpha\neq\beta, and consider the set \{v_\alpha + \lambda v_\beta\ |\ \lambda \in k\}. This set has cardinality k, and each element lies in some V_\gamma, so by the pigeonhole principle, two of these elements must lie in the same V_\gamma, say v_\alpha + \lambda_1 v_\beta \in V_\gamma and v_\alpha + \lambda_2 v_\beta \in V_\gamma.

Subtracting, we see that (\lambda_1 - \lambda_2)v_\beta \in V_\gamma, so v_\beta \in V_\gamma. Therefore \beta = \gamma. Similarly, we see that v_\alpha\in V_\gamma, so \alpha=\gamma=\beta, contradiction.


The above proposition is, unfortunately, false. To see this, take V to be a real vector space with countably infinite basis e_1,e_2,\ldots, and for each i, let V_i be the vector space generated by e_j, j\neq i. Then \{V_i\} covers V, even though it is a set of cardinality \aleph_0 < |\mathbb{R}|.


We need to add a condition to the proposition, but this time the proof is correct.

Modified Proposition: If k is a field and c is a cardinal less than |k|, then a finite dimensional vector space over k cannot be written as a union of c of its proper subspaces.

Proof: We proceed by induction on the dimension. If V has dimension 1, then any union of proper subspaces must be the zero space, so the statement is trivial. Now assume that V has dimension d \geq 2 and the proposition has been proved for all vector spaces of dimension d-1.

First, observe that there are at least |k| subspaces of V of dimension d-1. For if e_1,\ldots e_n are a basis for V, then we can take the subspaces generated by \lambda e_1 + e_2, e_3,\ldots e_n for \lambda\in K.

Suppose that we are given a collection \{V_\alpha\} of proper subspaces of V of cardinality c that covers V. Since there are at least |k|> c spaces of dimension d-1, there must be such a space W that is not equal to any V_\alpha. Hence \{V_\alpha \cap W\} is a collection of proper subspaces of W of cardinality c that covers W, contradiction.


So what was the mistake in the original proof? You might question my use of the pigeonhole principle on infinite sets, but that can actually be made quite rigorous. No, the problem is the statement “We can assume that no proper subcollection covers V“. Though an attractive idea, it is not true that we can reduce our collection to no longer be redundant.

Consider our earlier counterexample, a real vector space with a countably infinite basis. The given collection covers V, but there is no non-redundant subcollection that does so. A slightly painful reminder that we must always modify our intuition when dealing with infinite sets.

We can salvage the original proof, however, when the collection is finite. Then, in fact, we can throw out elements of our collection, one at a time, until we have eliminated any redundancy. That gives us the following: (note that this is not strictly weaker than our modified proposition, since it applies to infinite-dimensional spaces as well)

Salvaged Proposition: If k is an infinite field, a vector space over k cannot be written as a union of finitely many proper subspaces.