Olympiad Reminiscence: Abstract Algebra

“Nowadays, every good student at the National Olympiad should know at least some field theory to solve number theory problems…” Pleinfeld, 2015.

I was sitting in a training/selection camp for Germany’s National Olympiad with the brightest minds in Bavaria. I was in 10th grade. 

I was frantically copying the lecturer’s writings. “Just copy, don’t look up… Just copy…” 

“Why the heck does everybody know what this \mathbb{F}_7 is? What the #### is that? OMG. Perhaps I shouldn’t have chosen the advanced class after all…”

“I don’t even know what a field is, oh my god. What are we doing…” Symbols. So many meaningless symbols. I was embarrassed. Ashamed. Ashamed I didn’t know what was apparently trivial to everyone else.

Pleinfeld Mitschrift.jpg
My notes at Pleinfeld 2015. I now understand that we were discussing the existence of an algebraic closure.

Now, 4 years later, I finally understand. At least a little bit. I don’t agree with the lecturer that we should have known field theory (German olympiads are really easy!). However, I do agree that it’s a great asset to mathematical understanding.

This semester, I took an abstract algebra class. It’s amongst my favorites! Especially because it dearly reminds me of the good old competition days.

I’d like to give you an overview of what was reminiscent to me.

Groups and Functional Equations

Almost all abstract algebra classes start with group theory. I’d like to adhere to this tradition.

Groups occasionally reminded me of functional equations. Not surprising! Groups themselves can (in some sense) be identified as functional equations!

More difficult than all IMO problems. Let G = \{g_1, g_2, \dots, g_n \} be a finite set. Find all functions f : G \times G \to G satisfying the following properties:

  1. \forall x,y,z \in G: f(f(x,y),z) = f(x, f(y,z))
  2. \exists e \in G: \forall x \in G: f(x,e) = f(e,x) = x
  3. \forall x \in G: \exists y \in G: f(x,y) = f(y,x) = e

In other words: Find all groups (up to isomorphism) of order n.

I learned this view from Evan Chen.

Certain homework problems also reminded me of functional equations. Oh well. Homomorphisms are simply special functions.

H 11. Prove that the group (\mathbb{Q}, +) cannot be written as the product of 2 non-trivial groups.

The functional equation is merely the proposed fictional isomorphism. An equivalent formulation is the following:

H 11 (equivalent). Prove that there do not exist non-trivial groups G, H with an isomorphism \varphi : G \times H \to \mathbb{Q}.

Group Theory and Number Theory

Fermat’s Little Theorem and Euler-Fermat Theorem are probably known by almost the entire mathlete community. They are easy to use and yet so powerful. Computing large powers in \mathbb{F}_p doesn’t scare us – we’d simply call Fermat and use his little theorem!

For some reason, though, I was never invested in properly studying group theory. A greater gem is Lagrange’s Theorem – a natural generalization of Fermat’s Theorem.

Lagrange’s Theorem. Let G be a finite group and H \subseteq G a subgroup. Then |H| \mid |G|.

With a bit of group theory, most/all results related to Fermat’s Little Theorem follow from Lagrange. One has to understand \mathbb{F}_p^{\times}.

That was not all. Again and again, I would be reminded of elementary number theory. One day, we would experience alternative approaches to familiar results. As an example, Jordan-Hölder gives us the uniqueness of prime factorization. On another day, we would use divisibility arguments all over the place. Results in group actions, the above Lagrange’s Theorem or the mighty Sylow Theorems. All of these eventually required divisibility arguments.

I savored it.

Classical Theorems Revisited: Chinese Remainder Theorem and Euclidean Algorithm

I remember a friend telling me that he knows an easy proof of the Chinese Remainder Theorem with abstract algebra. Of course, I had no idea. I only knew an inductive argument.

Finally, I learned an abstract algebra view. We can prove a more general version with ring theory. The classical Chinese Remainder Theorem is a quick corollary, though also results in Polynomial Interpolation such as Lagrange’s or Hermite’s Interpolation follow.

Chinese Remainder Theorem. Let R be an integral domain and I_1, \dots, I_n \trianglelefteq R be pairwise relatively prime. Then

\displaystyle \pi : R \to R/I_1 \times \dots \times R/I_n, \ x \mapsto (x+I_1, \dots, x+I_n) 

is surjective.

Another classic is the Euclidean Algorithm. As far as I can remember, it’s one of the first proper algorithms that I learned. Sure enough, it would be a technique I would often refer to. Also, which past/current contestant doesn’t remember the legendary

IMO 1959, #1. Prove that \displaystyle \frac{21n+4}{14n+3} is irreducible.

Being the first problem in the first IMO, it’s of course extremely easy. However, one can finally say for the first time to have solved an IMO problem.

Euclid’s algorithm can be generalized in ring theory. In fact, his algorithm is so natural that mathematicians construct rings called Euclidean Rings. These are exactly those rings in which we can perform the Euclidean Algorithm – hurray for Euclid!

Ideals and Primes/Irreducibility Relaunched

One main motivation of ring theory is algebraic number theory. I loved it. I love number theory.

Ideals helped me understand “working modulo x” better. It’s encapsulated in quotient structures. Instead of only modding out numbers (e.g. compute 42 \bmod 5), it makes great sense to mod out ideals!

Bézout’s Theorem is a classical theorem that can be proven quite easily with ideals. It was astonishing to me, as Bézout is important to build prime factorization in elementary number theory.

Fun fact: Professors love asking for Bézout in the final round of Bundeswettbewerb Mathematik. A friend of mine took part in 2 consecutive years. In both years he was asked that question!

Just as primes serve as an atomic building stone of the integers, wishful thinking leads us to similar goals for rings. We strive to generalize notions of irreducibility and being prime to rings. That opens a myriad of possibilities.

The greatest hope is a unique factorization domain (UFD). We have known – since the ancient Greeks – that natural numbers have unique prime factorizations (Fundamental Theorem of Arithmetics). However, that’s not an obvious property for arbitrary rings. In fact, it’s not true for many rings.

Let us look at \mathbb{Z}[\sqrt{-5}] := \{a+i \sqrt 5 b \mid a,b \in \mathbb{R} \}. One can check that 2, 3, 1- \sqrt5, 1 + \sqrt5 are irreducible. However,

6 = 2 \cdot 3 = (1+ \sqrt5 i)(1- \sqrt5 i).

It’s also quite fascinating that 2 isn’t even prime but it is irreducible. So we also discover that primes and irreducible factors can be very much different in rings.

Irreducibility surely is motivated by polynomials. We are interested in irreducible polynomials, as reducing them helps us understand them. One tool is Eisenstein’s Criterion – another reminiscence of olympiad math. In these competitions, one would sometimes be interested in proving irreducibility and use Eisenstein.

It regains importance in abstract algebra where irreducibility is the real deal!  It’ll provide crucial results!

University Competition – Determinants

Let us make a side-stop to university competitions. A well known problem is to compute the Vandermonde Determinant.

\displaystyle V(x_1, x_2, \dots, x_n) = \det \begin{pmatrix} 1 & x_1 & x_1^2 & \dots & x_1^{n-1} \\ 1 & x_2 & x_2^2 & \dots & x_2^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & x_n^2 & \dots & x_n^{n-1} \end{pmatrix} = \prod_{1 \leq i < j \leq n} (x_j-x_i)

You can compute V with induction and row/column combinations. There is a much nicer approach, though.

Key idea: The determinant V(x_1, x_2, \dots, x_n) – by its very definition (e.g. Leibniz formula) – is simply a multivariate polynomial! Hence, we have a clear goal. Find ways to force V(x_1, x_2, \dots, x_n) = 0. It’s equivalent to finding factors of the polynomial.

Remember that a determinant is 0 if two rows are identical. Seeing the symmetry of the Vandermonde determinant, that isn’t too difficult to force. Suppose e.g. that x_1 = x_2. Then

\displaystyle V(x_1, x_1, \dots, x_n) = \det \begin{pmatrix} 1 & x_1 & x_1^2 & \dots & x_1^{n-1} \\ 1 & x_1 & x_1^2 & \dots & x_1^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & x_n^2 & \dots & x_n^{n-1} \end{pmatrix} = 0

Consequence: For some multivariate polynomial P we have

(x_1-x_2) \mid V(x_1,x_2, \dots, x_n) \iff V(x_1,x_2,\dots,x_n) = (x_1-x_2) \cdot P(x_1,x_2,\dots,x_n).

This can be done for all pairs (x_i, x_j) with i \neq j.

With that, we are almost done computing the determinant. It only remains to do some verification work.

I found this solution a year ago (the execution was uglier, though). So I was happy to see it in our lecture. It helped me understand the solution even better – why can we factor x_1 - x_2 algebraically?

Answer: The ring of multivariate polynomials R[X_1, X_2, \dots, X_n] is an UFD if R is an UFD and the linear factors X_i - X_j are irreducible!

Symmetric Polynomials and finally… Fields

Back in high school, I learned about “weird” relationships for polynomials. The coefficients of polynomials can be depicted as so-called symmetric polynomials. One can notice that by applying Vieta’s Theorem. Let us look at a cubic polynomial. Suppose we have a monic polynomial P with roots a, b, c. Then,

P = (X-a)(X-b)(X-c) = X^3 + (-a-b-c)X^2 + (ab+bc+ca)X -abc.

We immediately notice that the coefficients are quite symmetric.

I can now guess (I haven’t learnt it yet!) that there are greater matters at hand. Mathematicians would once try to find solution formulas for polynomial equations.

For example, in high school, we are taught to solve quadratic equations:

\displaystyle ax^2 + bx + c = 0 \implies x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}.

It’s natural to look for formulas for arbitrary degrees.

However, nobody succeeded for polynomials with degree > 4. The ingenious Évariste Galois (1811 – 1832) would later prove that such formulas actually don’t exist. He set the foundation for Galois theory and modern group theory.

The underlying idea is related to the symmetric groups. One would see symmetries of the roots and somewhat look at permutations which eventually would lay the groundwork for that proof. 

(Funnily, up until this semester, I never expected the symmetric groups S_n to be this special. Sure, they were fun to play with. Sure, they were natural structures. But never would I have thought that they are involved in Galois’ ideas. In specific, I’d like to advocate: As a lecturer/teacher, you should at least mention the importance of S_n.)

As symmetries are involved here, I can firmly guess that symmetric polynomials from high school were “just” a by-product of this deep fact.

We’re not quite there in our lecture yet. However, in the last lecture, we finally covered what was depicted in the beginning picture of this blog post.

4 years later after Pleinfeld 2015, I finally learned about the existence of an algebraic closer properly. I finally learned a serious proof.

And just as back then, I was extremely confused!


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s