Applications of Abstract Algebra to elementary mathematics

Question

I'm currently an undergraduate student in mathematics. I am currently taking Algebra. The course is interesting, but I have grown very curious about the usefulness of algebra.

I am NOT asking about "applications of algebra to real-life". I am asking about how algebra can be used to solve math problems. Unfortunately, Googling "applications of algebra" is not all that helpful.

Right now I can only recall seeing two instances of "useful" applications of algebra -- a proof of Fermat's Little Theorem, and determining whether a polynomial is solvable in radicals by looking at its Galois group.

What interests me about both problems is that they are of interest to someone who has not necessarily encountered abstract algebra yet (e.g. what is the remainder when you divide k^p by p? can you write explicitly the roots of some polynomial using only the integers and the specified functions?).

At least from the way my course is currently progressing, it feels as though such applications are few and far in between. We are currently making observations about permutations (e.g. if p and q are permutations, then pq and qp have "similar forms"), which is interesting, but I fail to see how algebra has helped make any interesting deduction -- all interesting results so far about permutations (e.g. the one mentioned above) were all done without any algebraic result.

Only when we ask a question using algebraic terminology was algebra required (e.g. show An is a normal subgroup of Sn). If algebra were only used to answer questions about algebra, there would be no real need to study algebra, right?

What are some other "elementary" applications of algebra? What are some other interesting results I would be able to understand after an introductory course?

I have a suspicion that finding answers to these questions would better my understanding of algebra, but I have had difficulty in finding many good answers.

Answer 1

What is the period of the Fibonacci sequence $F_n$ modulo a prime $p$?

This is the Pisano period. It is difficult to say much about the exact period, but one can write down a number which is guaranteed to be divisible by the period using some facts about finite fields in a manner analogous to Fermat's little theorem, together with quadratic reciprocity. The key result is that Binet's formula

$$F_n = \frac{\phi^n - \varphi^n}{\phi - \varphi}$$

continues to hold $\bmod p$ in a suitable sense for all $p \neq 5$. Here $\phi, \varphi$ are the two roots of the characteristic polynomial $t^2 - t - 1$.

Proposition: If $p \neq 5$, then $F_n$ has period dividing $p - 1$ if $p \equiv 1, 4 \bmod 5$; otherwise, $F_n$ has period dividing $2(p + 1)$. If $p = 5$, then $F_n$ has period $20$.

Proof. By quadratic reciprocity, $p \equiv 1, 4 \bmod 5$ if and only if $t^2 - t - 1$ factors over $\mathbb{F}_p$. By Fermat's little theorem, it follows that $\phi, \varphi$ have multiplicative order dividing $p-1$. If $t^2 - t - 1$ does not factor over $\mathbb{F}_p$, then its roots lie in $\mathbb{F}_{p^2}$, and the Frobenius map interchanges them; that is, $\phi^p \equiv \varphi \bmod p$ and vice versa. Consequently $\phi^{p+1} \equiv -1 \bmod p$, and we conclude that

$$F_p \equiv -1 \bmod p$$ $$F_{p+1} \equiv 0 \bmod p$$ $$F_{p+2} \equiv -1 \bmod p$$ $$F_{p+3} \equiv -1 \bmod p$$

and by induction $F_{p+1+k} \equiv - F_k \bmod p$, hence $F_{2(p+1)+k} \equiv F_k \bmod p$ as desired. The case $p = 5$ is left as an exercise. $\Box$

This proposition describes a pattern which is straightforward to verify by hand, but which without some knowledge of abstract algebra and number theory is very difficult to explain.

Answer 2

One of the most important results you learn in a first course on abstract algebra is Burnside's lemma, which has many applications in combinatorics and number theory. Some time ago I wrote a series of blog posts leading up to a powerful corollary of Burnside's lemma called the Polya enumeration theorem (including several applications, so you should look in those posts for them), which can be used to count many things; it was originally used to count chemical compounds.

The Polya enumeration theorem in turn can be used to prove a powerful result in combinatorics called the exponential formula, which gives you an enormous amount of information about permutations. For example, using the exponential formula you can prove results like

The number of fixed points of a random permutation of $n$ elements is asymptotically Poisson distributed with parameter $\lambda = 1$ as $n \to \infty$

relatively easily.

Answer 3

Persi Diaconis showed that it takes about $7$ shuffles to shuffle a $52$-card deck. I'm not going to explain how he proved this result, but I'm going to explain some relevant ideas.

Given a regular graph $X$, it's interesting to think about random walks on $X$. (In Diaconis' case, the graph is the graph whose vertices are all possible configurations of the deck and whose edges are given by shuffles.) A natural question to ask is approximately how quickly the random walk mixes, which roughly speaking means asking about how many steps need to be taken before a random walker is about equally likely to be at any particular vertex. The mixing time of a random walk on $X$ is controlled by the second largest eigenvalue of the adjacency matrix $A(X)$ of $X$, so what we'd like to do is to compute this eigenvalue.

If $X$ is a Cayley graph of a finite group $G$, then the eigenspaces of $A(X)$ become representations of $G$, and this is a huge help in figuring out what the second largest eigenvalue is. If $G$ is in addition abelian, then the irreducible representations of $G$ are $1$-dimensional, and this tells you explicitly what all of the eigenvectors of $A(X)$ are, from which their eigenvalues are straightforward to compute. (In Diaconis' case, $G = S_{52}$ is far from abelian, but nevertheless representation theory is still, as I understand it, quite relevant.)

Example. If $G = C_n$, then a natural Cayley graph for $G$ is an $n$-gon. The second largest eigenvalue of the adjacency matrix can be computed using the representation theory of $C_n$ (essentially the discrete Fourier transform) to be

$$2 \cos \frac{2 \pi}{n} \approx 2 - \frac{4 \pi}{n^2}$$

(the largest eigenvalue is $2$.) I believe this implies that the mixing time is $O(n^2)$.

Example. If $G = C_2^n$, then a natural Cayley graph for $G$ is a hypercube. The second largest eigenvalue of the adjacency matrix can be computed again using the discrete Fourier transform to be $n-2$ (the largest eigenvalue is $n$). I believe this implies that the mixing time is $O(n)$.

Answer 4

Lagrange's Theorem has some applications to elementary number theory:

1) Wilson's Theorem says that for a prime $p$ we have $(p-1)! \equiv -1 \pmod p$. Proof: By Lagrange's Theorem applied to $\mathbb{F}_p^*$ we have $X^{p-1}-1 = \prod_{a \in \mathbb{F}_p^*} (X+a)$ in $\mathbb{F}_p[X]$. Now let $X \mapsto 0$.

2) The algebraic definition of binomial coefficients relies on the fact that for $n,m \in \mathbb{N}$ we have that $n! m!$ divides $(n+m)!$. Here is a proof: There is a canonical monomorphism

$Sym(\{1,\dotsc,n\}) \times Sym(\{n+1,\dotsc,n+m\}) \hookrightarrow Sym(\{1,\dotsc,n+m\})$.

Now apply Lagrange's Theorem.

Answer 5

Disclaimer: This is a long post and I am not originally a Mathematician. I just wanted to offer my viewpoint as someone who is not just in the process of learning it, but also had prior experience in its application.

What you might be able to appreciate from an introductory course
Personally, I think the Rubik's Cube is a good object to make use of your group theory knowledge.
It can be fully described as products of permutation groups and it is fun!

In fact, it probably fits what you mentioned in the first part:

of interest to someone who has not necessarily encountered abstract algebra yet

So if you like puzzles, consider it as a learning tool!
Try to solve it using the theory you learned in class.
If the typical cube is too mundane for you, there are also exotic choices. :)
There are even Algebra courses conducted using it. (I cannot remember where)

And while staying in just group theory, a lot of application will come from combinatorics.
There is a good reason for this: every group is isomorphic to a subgroup of a permutation group.
And permutation happens very frequently in combinatorics topics.
For example, it can be shown that enumerating all permutations of $\lbrace 1,\dots,n\rbrace$ can be done using only 2 generators.

Going 1 step further in this direction, some areas of Graph theory is closely related to group theory too. For example, the Graph Isomorphsim problem is known to be a non-abelian hidden subgroup problem. Very difficult in general cases!
But if the graph involved is a permutation graph, then it can be solved efficiently.

If we consider an abelian hidden subgroup problem instead, then this includes 2 very important classes of problems: Integer factorization and Discrete Logarithm.
Although to be precise, study of these problems goes beyond group theory.

While talking about number theory, there are some nice algorithms that you can understand with just group theory.
Many important results are derived from just Fermat's little theorem:
Miller-Rabin primality test: A probabilistic test for primes (I think still most efficient)
Pollard's p-1 algorithm: An algorithm to find small prime factors

If your introductory course covers rings, more specifically polynomials in rings, then factorization of polynomial rings is a great area to look at.
Note: The question of whether polynomials have solutions is equivalent to its factorization into linear factors. There are some nice results stating when this is possible.
An example: If GCD$(f(x),x^p-x)\neq 1$, then it has solutions in $\mathbb{F}_p$.

I don't think I have enough experience to explain it better... this is the best I can offer at the moment. Hope it will be useful!

P.S. Algebra is also an important gateway to many other areas. Algebraic Geometry/Algebraic Topology/Algebraic Combinatorics etc
Perhaps if you also looked a bit into that direction you may find more things that interests you.

Answer 6

Let $p$ be an odd prime number. $p = x^2 + y^2$ has integer solutions if and only if $p \equiv 1$ (mod $4$). This can be elegantly proved by using the properties of the ring $\mathbb{Z}[i]$.

http://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_theorem_on_sums_of_two_squares

Answer 7

A lucid proof of the quadratic reciprocity law can be obtained by the theory of cyclotomic number fields.

Discriminant of the quadratic subfield of the cyclotomic number field of an odd prime order $l$

Answer 8

To rationalize denominators that are not quadratic is a nice application of linear algebra over fields. For example, if asked to rewrite $$ \frac{1}{1-5\sqrt[3]{2}} $$ with a rational denominator, the best way to approach the problem is to work in the field ${\mathbf Q}(\sqrt[3]{2})$ with ${\mathbf Q}$-basis $1,\sqrt[3]{2},\sqrt[3]{4}$.

Answer 9

Diophantine equations of the type $m = ax^2 + bxy + c^2$ can be solved by using algebraic number theory on quadratic number fields.

As for connections between integral binary quadratic forms and quardratic number fields, here are some examples:

Discriminant of a binary quadratic form and an order of a quadratic number field

A binary quadratic form and an ideal of an order of a quadratic number field

Bijection between an ideal class group and a set of classes of binary quadratic forms.

Answer 10

Here's a nice theorem illustrating how some basic algebraic concepts are useful in seemingly unrelated areas of mathematics. The uniformization theorem for surfaces states that

Every orientable topological surface $S$ admits a Riemannian metric of constant curvature $1$, $0$, or $-1$.

What does algebra have to do with this? It's because we can rephrase this theorem using the fundamental group of $S$, $\pi_1 S$:

For every orientable topological surface, there exists a homomorphism from $\pi_1 S$ into one of $\operatorname{Isom}^+\mathbb{S}^2 = SO(3)$, $\operatorname{Isom}^+\mathbb{E}^2 = \mathbb{R}^2 \rtimes SO(2)$, or $\operatorname{Isom}^+\mathbb{H}^2 = SL(2;\mathbb{R})/\pm I$. The isometric action induced by this homomorphism is free and properly discontinuous and the quotient map is a universal covering map.

There's a lot of background material here, so don't be intimidated if you don't fully understand the statement. Instead, look at how casually these algebraic concepts -- group, homomorphism, action, semidirect product, action -- are invoked in what seemed at first to be a purely geometric statement.

Moreover, in rephrasing the uniformization theorem in terms of algebra, one transforms the problem from differential geometry (computing curvature tensors on surfaces) to algebra (examining homomorphisms from a surface group into these special groups).

Here's another famous example: Mostow-Prasad rigidity:

If two three-manifolds admit finite volume metrics of constant sectional curvature $-1$, then if they are homotopy equivalent, there is a homotopy from the homotopy equivalence to an isometry.

Rephrased algebraically,

If $\Gamma$ and $\Lambda$ are discrete cofinite subgroups of $PSL(2;\mathbb{C})$, and if $\Gamma$ and $\Lambda$ are isomorphic as abstract groups, then $\Gamma$ and $\Lambda$ are conjugate in $PSL(2;\mathbb{C})$.

Again, without getting lost in details, note how this statement, which seems to be purely topological, can be rephrased in a statement that seems to be purely algebraic!

This is often a theme: take a difficult problem in geometry or topology, use a geometric construction to create an algebraic object, use algebra to study the algebraic object, and then deduce geometric or topological conclusions.

The take-home message here is: don't lose hope! To build up your understanding of algebra, and because there's only so much time in a semester, your class has to skimp on all the ways algebra is useful in mathematics and instead focus on building up the abstract edifice of algebra so you can work through the theorems and understand the ideas. But if you continue on in mathematics, you will begin to see these ideas casually invoked in areas that are, at first glance, completely unrelated to the pure structure of number systems.

Answer 11

Group theory is useful in statistics, in experimental design: Look at the book by Box, Hunter & Hunter: "Statistics for Experimenters" (maybe the best book you will ever find about statistics, so you should have a look!) The first chapters is about $2^p$ designs and $2^{n-p}$ fractional designs. Everything they show can be seen as examples of group theory (but they do not do it that way). But if you can see it is group theory, maybe you can learn it faster.

Answer 12

I just found the following book: http://www.amazon.com/Fourier-Analysis-Applications-Mathematical-Society/dp/0521457181/ref=sr_1_1?s=books&ie=UTF8&qid=1350785755&sr=1-1&keywords=audrey+terras

which are written just for people like you wanting to find out about various applications of algebra.

For example, this book have some very interesting applications of groups to error-correcting codes, but also to number theory, and to graph theory ...

Answer 13

The product of all the residue classe modulo a prime $p$ is to -1 (mod p).