Archives For abstract algebra

A simplified structure diagramMy colleague Nandor Sieben and I recently submitted for publication a paper titled “Impartial achievement and avoidance games for generating finite groups.” The current arXiv version of the article is located here. My typical pure mathematics research interests are in the combinatorics of Coxeter groups and their associated algebras, so while I have a background in group theory and combinatorics, this was my first research experience in combinatorial game theory. In fact, prior to working on this project, I knew next to nothing about the subject. In the year and a half we worked on the project, I learned a tremendous amount of new material, which was a lot of fun. It was exciting to branch out and try something new.

Here is the abstract for the paper:

We study two impartial games introduced by Anderson and Harary and further developed by Barnes. Both games are played by two players who alternately select previously unselected elements of a finite group. The first player who builds a generating set from the jointly selected elements wins the first game. The first player who cannot select an element without building a generating set loses the second game. After the development of some general results, we determine the nim-numbers of these games for abelian and dihedral groups. We also present some conjectures based on computer calculations. Our main computational and theoretical tool is the structure diagram of a game, which is a type of identification digraph of the game digraph that is compatible with the nim-numbers of the positions. Structure diagrams also provide simple yet intuitive visualizations of these games that capture the complexity of the positions.

The fundamental problem in the theory of impartial combinatorial games is the determination of the nim-number of the game. This allows for the calculation of the nim-numbers of game sums and the determination of the outcome of the games. The major aim of this paper is the development of some theoretical tools that allow the calculation of the nim-numbers of the achievement and avoidance games for a variety of familiar groups. In the paper, we introduce the structure diagram of a game, which is an identification digraph of the game digraph that is compatible with the nim-numbers of the positions. Structure diagrams also provide simple but intuitive visualizations of these games that capture the complexity of the positions. By making further identifications, we obtain the simplified structure diagram of a game, which is our main computational and theoretical tool in the paper.

We developed a software package that computes the simplified structure digraph of the achievement and avoidance games. We used GAP to get the maximal subgroups and the rest of the computation is implemented in C++. The software is efficient enough to allow us to compute the nim-numbers for the smallest 100,000 groups, which includes all groups up to size 511. The result is available on our companion web page.

In April of 2013, I gave two talks at the University of Nebraska at Omaha that introduce the two games that this paper is about, but did not elaborate on the nim-number aspect. I summarized those talks in this blog post.

High Five A few weeks ago, Stan Yoshinobu asked me to round up a few student quotes about their experience with inquiry-based learning (IBL). The intention is to use some of the material he gets for pamphlets and flyers for the Academy of Inquiry-Based Learning. I contacted a few of the students from the abstract algebra course that I taught in the fall and here is what they had to say.

“I’m a very shy person. Presenting math problems in front of an audience of math students was at first excruciating, but by the end of the course I realized I had gained an enormous amount of confidence. I truly feel that the IBL process has given me access to internal resources I didn’t realize I had available.”

“IBL created an environment for me where I felt comfortable enough to try proofs without the pressure of needing to be 100% right on the first try. So now in later upper division courses I am more comfortable with trying more complex problems, which ultimately lead me to do undergraduate research. And in all honesty, the classroom culture created by the IBL setup is what sold me on pure mathematics and has made me a better independent learner.”

“IBL helps prepare the student for the real world by teaching them how to create intuition. When you get to the real world or higher level mathematics courses, you will not always have someone there to tell you how to solve the problem.”

“By far, and without a doubt, inquiry-based learning is the best way to learn mathematics. Most methods for teaching math involve an instructor showing how to “do” various problems often involving computations and formulas, and then the students mimic the process for similar problems. IBL, however, asks the students to use what they know (or assume) to be true in order to create their own ways to solve problems or form logical arguments to validate other ideas. And logical arguments, not computations, not formulas, are the basis of all mathematics. Being able to form logical arguments is not something that can be mimicked, it must be discovered on one’s own, which is exactly how IBL works. Hence, when it comes to math, real math, and not just computations, IBL is the way to go.”

It would be a crime if I didn’t mention my all-time favorite student quote about IBL that was written on a course evaluation at the end of my introduction to proof course from the spring 2013 semester.

“Try, fail, understand, win.”

I believe that this last quote perfectly captures the essence of an effective IBL experience for a student. If you want to know about IBL, check out my post, What the Heck is IBL?, over on Math Ed Matters.

Q8The Fall semester of 2013 just ended and one of the classes I taught was abstract algebra. The course is intended to be an introduction to groups and rings, although, I spent a lot more time discussing group theory than the latter. A few weeks into the semester, the students were asked to prove the following theorem.

Theorem. If $G$ is a cyclic group, then all the subgroups of $G$ are cyclic.

As with all conditional theorems, I also encouraged my students to think about whether the converse of this theorem is true. That is, if all the subgroups of a group $G$ are cyclic, does this imply that $G$ is cyclic? Well, since $G$ is always a subgroup of itself, the answer is clearly yes. But this isn’t the interesting question to ask. Instead, we should ask:

If $G$ is a group such that all proper subgroups are cyclic, does this imply that $G$ is cyclic?

The answer is “no” and my students were able to quickly come up with a few counterexamples. In particular, they mentioned the dihedral group $D_3$ (symmetry group for an equilateral triangle), the Klein four-group $V_4$, and the Quarternion group $Q_8$. The groups $D_3$ and $Q_8$ are both non-abelian and hence non-cyclic, but each have 5 subgroups, all of which are cyclic. The group $V_4$ happens to be abelian, but is non-cyclic. Yet it has 4 subgroups, all of which are cyclic.

Following the discussion of these three examples, one of my students asked whether the question above is true for infinite groups. I responded with something like, “Uh…well…no, I don’t think so. Hmmm, let me think about it.” So, I thought about it off and on for a couple hours, but didn’t make much headway. I decided to roam the hallways and recruit some help. I ended up chatting with my colleagues Mike Falk, Jim Swift, and Jeff Rushall. Collectively, we all thought about it a little bit here and a little bit there. I was fairly confident that an internet search would provide some insight, but I was intentionally putting that off in the hopes that I could come up with an example.

A couple days later, I was meeting with one of my undergraduate research students and we chatted briefly about the problem. A few hours after we met, he sent me a link to a discussion on Math Stack Exchange, which contains a response that is precisely about the question above.

Without further ado, here’s an example that confirms that the answer to the question above is “no” even if the group is infinite.

Theorem. The group $G=\{a/2^k\mid a\in\mathbb{Z}, k\in\mathbb{N}\}$ is an infinite non-cyclic group whose proper subgroups are cyclic.

Note that any fixed prime will do for the denominator. Let’s sketch a proof.

First, it is clear that $G$ is an infinite subgroup of $\mathbb{Q}$ since the sum of any two elements from $G$ will be contained in $G$ and the additive inverse of any element from $G$ is also in $G$. To see that $G$ is not cyclic, let $a/2^k\in G$ such that $a$ is odd and consider $\langle a/2^k\rangle$. It’s quickly seen that $\langle a/2^k\rangle$ does not contain any rational numbers having denominators equal to $2^{n}$ for $n>k$, and hence $G$ is not cyclic. Now, suppose that $H$ is a proper subgroup of $G$. If $a/2^k\in H$, then $a/2^{k-1}=a/2^k+a/2^k\in H$, as well. It follows that if there is an element in $H$ with denominator equal $2^k$ (in reduced form), then $H$ also contains elements with denominators equal to $2^n$ (in reduced form) for all $n\leq k$. Since $H$ is a proper subgroup, there exists a smallest $m\in \mathbb{N}$ such that no element of $H$ has a denominator equal to $2^m$. Then it must be the case that $H$ is contained in $\langle 1/2^{m-1}\rangle$, and so $H$ is cyclic (since subgroups of cyclic groups are cyclic).

Cool.

On Tuesday, February 5 (my birthday!), I gave a talk titled “A diagrammatic representation of the Temperley-Lieb algebra” in the NAU Department of Mathematics and Statistics Colloquium. Here is the abstract.

One aspect of my research involves trying to prove that certain associative algebras can be faithfully represented using “diagrams.” These diagrammatic representations are not only nice to look at, but they also help us recognize things about the original algebra that we may not otherwise have noticed. In this talk, we will introduce the diagram calculus for the Temperley-Lieb algebra of type $A$. This algebra, invented by Temperley and Lieb in 1971, is a certain finite dimensional associative algebra that arose in the context of statistical mechanics in physics. We will show that this algebra has dimension equal to the nth Catalan number and discuss its relationship to the symmetric group. If time permits, we will also briefly discuss the diagrammatic representation of the Temperley-Lieb algebra of type affine $C$.

And here are the slides.

Despite the fact that this was a 50-minute talk, it was intended to be an overview of one aspect of a long and complex story. The subject matter is intimately related to my PhD thesis, as well as a series of papers that I have written.

  • Ernst, D. C. (2010). Non-cancellable elements in type affine $C$ Coxeter groups. Int. Electron. J. Algebra, 8, 191–218. [arXiv]
  • Ernst, D. C. (2012). Diagram calculus for a type affine $C$ Temperley-Lieb algebra, I. J. Pure Appl. Alg. (to appear). [arXiv]
  • Ernst, D. C. (2012). Diagram calculus for a type affine $C$ Temperley–Lieb algebra, II. [arXiv]

In addition, there is (at least) a part III that goes with the last two papers that is in progress.

On Friday, September 12, 2012, I gave a 25 minute talk titled “An open problem of the symmetric group” during NAU’s Friday Afternoon Mathematics Undergraduate Seminar (FAMUS). Here is the open problem that I discussed.

How many commutation classes does the longest element in the symmetric group have?

The main goal of the talk was to understand what this question is asking. The secondary goal was to illustrate that mathematics is a lively field with open questions and to provide an example of what research in mathematics looks like. Here’s the abstract.

Many people are often surprised to hear that mathematicians do research. What is mathematical research? Research in mathematics takes many forms, but one common theme is that the research seeks to answer an open question concerning some collection of mathematical objects. The goal of this talk will be to introduce you to one of the many open questions in mathematics: how many commutation classes does the longest element in the symmetric group have? This problem has been nicknamed “Heroin Hero” by my advisor in honor of a game from the TV show “South Park” in which the character Stan obsesses over chasing a dragon. We will review the basics of the symmetric group and introduce all of the necessary terminology, so that we can understand this problem.

Here are the slides.

AIBL summer grant

December 30, 2011 — 4 Comments

In November of 2011, I applied for a Category 2 Small Grant from the Academy of Inquiry-Based Learning (AIBL). I found out today (December 30, 2011) that I have been awarded the grant!

The grant provides summer salary that will fund the development of inquiry-based learning (IBL) course materials for an abstract algebra course that emphasizes visualization and incorporates technology. In case anyone is interested, below is a slightly edited version of the narrative for my grant proposal.

Update (July 7, 2012): I am postponing this work until the summer of 2013. This summer is far too busy with my family’s move from Plymouth, New Hampshire to Flagstaff, Arizona. By next summer, I should be settled in at my new gig at Northern Arizona University and have a lot more time for this project.


Abstract algebra with visualization and technology

Project Summary

I am requesting summer salary in the amount of $2500 via a Category 2 AIBL Small Grant to fund the development of course materials for a junior/senior level IBL abstract algebra course. Course materials will emphasize visualization of groups and incorporate technology.

IBL Experience

I have been teaching college-level mathematics, starting as a graduate student, since the spring of 1997. During this time, I have received several teaching awards, most recently being named the 2009 and the 2011 Plymouth State University Distinguished Mathematics Professor, an honor determined by the mathematics majors at PSU. My classes have always been interactive, but initially they were predominately lecture-based. I was aware of the Moore method and inquiry-based learning (IBL), but I had never had an experience with this paradigm of teaching as a student. Moreover, by most metrics, my approach in the classroom seemed to be working. It was not until I sat through a Project NExT workshop at the 2008 MathFest led by Carol Schumacher that I began to think that perhaps IBL was a way for me to get even more out of my teaching.

In the spring of 2009, despite having no prior experience or formal training, I decided to teach my very first IBL course. The course I chose is called Logic, Proof, and Axiomatic Systems, which is meant to be our introduction to proof course. Having heard positive reviews, and being unfamiliar with the various free IBL resources, I elected to use Schumacher’s book titled Chapter Zero: Fundamental Notions of Abstract Mathematics [7]. Perhaps surprisingly, the course was a huge success and I was immediately sold on the potential impact that IBL can have on a student’s learning and character development. I have loved teaching since the day I started, but nothing compared to the joy of watching students truly learn mathematics, and often completely independent of me. I had taught the same course two semesters in a row using a mostly lecture-based approach, and I had thought that the previous two iterations went very well. However, the IBL version was a vast improvement. I have since had students from all three variations in upper-level proof-based courses and the students from the IBL version are much more independent and, in general, better proof-writers.

Over the past few semesters, I have taught the following courses using IBL:

  1. Logic, Proof, and Axiomatic Systems (twice)
  2. Real Analysis
  3. Abstract Algebra (twice)
  4. Number Theory

My first attempt at using my own theorem-sequence was while teaching Logic, Proof, and Axiomatic Systems using IBL a second time. As a starting point, I was modifying notes written by Stan Yoshinobu (Cal Poly, San Luis Obispo) and Matthew Jones (University of California, Dominguez Hills). Midway through the semester, I was writing my own notes. My experience writing my own theorem-sequence was positive. Yet, I learned quickly that it is very time consuming to produce a quality output.

Beyond my experience in the classroom, I have attended the last two Legacy of R.L. Moore Conferences and was a participant at the IBL Workshop that took place prior to the 2010 conference in Austin, TX. In addition, I am currently an AIBL Mentor for a small cohort of mathematics instructors in the Northeast that are new to IBL. Lastly, I am in the midst of conducting a couple of small-scale studies with mathematics education specialist Angela Hodge (University of Nebraska at Omaha) about student perception of the effectiveness of IBL.

Project Description

My first experience teaching abstract algebra was during a workshop in the summer of 2009 that was designed for high school mathematics teachers that were pursuing their teaching license in the state of New Hampshire. The purpose of the course was to introduce the concepts of group theory to these working teachers. The course was not intended to be a proof-based course. In fact, with the exception of one student, none of them had ever had a proof-based course before. I decided to use Nathan Carter’s excellent book titled Visual Group Theory (VGT) [4]. The book assumes only a high school mathematics background and covers a typical undergraduate course in group theory from a thoroughly visual perspective. In addition, we made use of the free and open-source software Group Explorer (GE) [1], which is also written by Nathan Carter. In the words of the developer:

“GE is mathematical visualization software for the abstract algebra classroom. It helps the user visualize group theory, builds students’ intuition, and enables experimentation with groups.”

What is remarkable is that by the end of the workshop, the students had more intuition about many concrete groups than many graduate students, despite being exposed to very few proofs. The students had played with groups, like a child with a toy. They were familiar with groups and had a visual way of thinking about various concepts.

My second experience teaching abstract algebra was in the spring of 2010. This was also my second attempt at IBL. Despite the success of using VGT the summer before, I decided that I wanted to teach a more traditional proof-based abstract algebra course. So, I chose to use Tom Judson’s open-source book title Abstract Algebra: Theory and Applications (AATA) [6]. My intention was to incorporate the visualization approach used in VGT with the flow of the content in AATA. However, I found this very difficult to do, and moreover, it required me to lecture more often than I would have liked. One of the issues is that VGT starts off by defining groups in terms of generators and relations, which does not arise in AATA until about half way through the semester. In addition to the students proving theorems, I also assigned exploratory labs, which required the students to make use of Sage [3], which is an open-source mathematics software system meant to be an alternative to Magma, Maple, Mathematica, and Matlab. Using Sage allowed the students to explore large concrete groups and make calculations that I would never ask them to do by hand. This opened up a whole realm of problems for the students to play with. The use of Sage was a success, but making more frequent and regular use would make it go even more smoothly.

This semester I am teaching abstract algebra for a third time. My initial intention was to write my own theorem-sequence that incorporated all of the positive aspects of my previous experiences with teaching the course. However, due to time constraints, I decided to postpone the project and apply for a AIBL Category 2 Small Grant to fund this work over the summer of 2012. I am currently using David Clark’s Group Theory [5] notes from the Journal of Inquiry-Based Learning in Mathematics [2]. Using this theorem-sequence has been a valuable experience and has provided me with further perspective on what I would like my own theorem-sequence to be.

My plan is to write a theorem-sequence in the spirit of Nathan Carter’s VGT, but with the mathematical rigor of Judson’s AATA and Clark’s Group Theory. In particular, the goal is to develop intuition about each new concept by introducing it from a visual perspective, where students are encouraged to play with concrete groups via short exercises. As intuition develops, students will be asked to conjecture and then prove theorems related to the relevant concepts. In addition, exploratory exercises that require the use of GE and Sage will be included. This will require me to write short introductions to the use of both of these software programs. Once the project is completed, my intention is to submit the material to the Journal of Inquiry-Based Learning in Mathematics, so that others can freely benefit from them.

Bibliography

[1] “Group Explorer.” [Online]. Available: http://groupexplorer.sourceforge.net/.

[2] €œ”Journal of Inquiry-Based Learning in Mathematics.” [Online]. Available: http://www.jiblm.org/.

[3] “Sage.”€ [Online]. Available: http://sagemath.org.

[4] N. Carter, Visual Group Theory. Mathematical Association of America, 2009.

[5] D. Clark, “Group Theory”, J. Inquiry-Based Learning in Mathematics, no. 3, 2007.

[6] T. Judson, Abstract Algebra: Theory and Applications, 2011st ed. Open-source textbook, 2011.

[7] C. Schumacher, Chapter Zero: Fundamental Notions of Abstract Mathematics, 2nd ed. Pearson, 2001.