Archives For group theory

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.

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 April 23, 2013, I gave two talks at the University of Nebraska at Omaha. The first talk was part of the Cool Math Talk Series and was titled “Impartial games for generating groups.” Here is the abstract.

Loosely speaking, a group is a set together with an associative binary operation that satisfies a few modest conditions: the “product” of any two elements from the set is an element of the set (closure), there exists a “do nothing” element (identity), and for every element in the set, there exists another element in the set that “undoes” the original (inverses). Let $G$ be a finite group. Given a single element from $G$, we can create new elements of the group by raising the element to various powers. Given two elements, we have even more options for creating new elements by combining powers of the two elements. Since $G$ is finite, some finite number of elements will “generate” all of $G$. In the game DO GENERATE, two players alternately select elements from $G$. At each stage, a group is generated by the previously selected elements. The winner is the player that generates all of $G$. There is an alternate version of the game called DO NOT GENERATE in which the loser is the player that generates all of $G$. In this talk, we will explore both games and discuss winning strategies. Time permitting, we may also relay some current research related to both games.

The content of the talk falls into the category of combinatorial game theory, which is a topic that is fairly new to me. The idea of the talk is inspired by a research project that I recently started working on with Nandor Sieben who is a colleague of mine at NAU. In particular, Nandor are working on computing the nimbers for GENERATE and DO NOT GENERATE for various families of groups. If all goes according to plan, we’ll have all the details sorted out and a paper written by the end of the summer.

After a brief introduction to combinatorial game theory and impartial games, I discussed both normal and misère play for three impartial games: Nim, X-Only Tic-Tac-Toe, and GENERATE. You might think that X-Only Tic-Tac-Toe is rather boring, but the misère version, called Notakto (clever name, right?) is really interesting. In fact, there is a free iPad game that you can download if you want to try it out. Also, if you want to know more about the mathematics behind Notakto, check out The Secrets of Notakto: Winning at X-only Tic-Tac-Toe by Thane Plambeck and Greg Whitehead.

Here are the slides for my talk.

Immediately after giving the Cool Math Talk, I facilitated a 2-hour Math Teachers’ Circle as part of the Omaha Area MTC. The audience for the MTC mostly consisted of middle and high school mathematics teachers. The theme for the circle was the same as the Cool Math Talk, but instead of me talking the whole time, the teachers played the games and attempted to develop winning strategies.

This was my second time running a MTC at UNO. In February of 2012, I ran a circle whose general topic was permutation puzzles. You can find the slides from last year’s circle here.

Both talks were a lot of fun (especially the MTC). Thanks to Angie Hodge for inviting me out to give the talks.

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.

On December 7, 2011, I gave my second talk about the Futurama Theorem during a Plymouth State University Mathematics Seminar. The Futurama Theorem is a theorem about the symmetric group that was developed for and proved in the episode “The Prisoner of Benda” for the TV show Futurama. The theorem was proved by show writer Ken Keeler, who has a PhD in applied mathematics from Harvard.

Image taken from http://theinfosphere.org/

The first time I gave a talk about this theorem was during the Mathematics Forum at Gordon College just few weeks earlier. You can find my blog post about my first talk by going here.

During the episode, Professor Farnsworth and Amy invent a mind swapping machine and after they swap minds, they realize that the machine cannot be used on the same pair of bodies again. After several characters swap minds, they are confronted with the problem of putting everyone’s mind back where it belongs. The Futurama Theorem proves that regardless of how many mind swaps have been made, all minds can be restored to their original bodies using only two extra people. If you want to know more, check out the slides.

The slides for the second talk are very similar to the first set, but there are a few differences:

  • The second talk is shorter. I trimmed a few things from the first talk that were not completely necessary.
  • I’ve improved the wording in a few spots.
  • In the second talk, multiplication of permutations is right to left.

As with the first talk, I used deck.js to create the slides. This allows you to view the slides directly in your web browser. To advance the slides, just use your arrow keys. Also, note that I used MathJax to typeset all of mathematical notation.

On November 3, 2011, I gave a talk in the Mathematics Forum at Gordon College about the Futurama Theorem. The Futurama Theorem is a theorem about the symmetric group that was developed for and proved in the episode “The Prisoner of Benda” for the TV show Futurama. The theorem was proved by show writer Ken Keeler, who has a PhD in applied mathematics from Harvard. During the episode, Professor Farnsworth and Amy invent a mind swapping machine and after they swap minds, they realize that the machine cannot be used on the same pair of bodies again. After several characters swap minds, they are confronted with the problem of putting everyone’s mind back where it belongs. The Futurama Theorem proves that regardless of how many mind swaps have been made, all minds can be restored to their original bodies using only two extra people. If you want to know more, check out the slides. As a side note, this is the first talk that I have given using deck.js, which allows you to view the slides directly in your web browser. To advance the slides, just use your arrow keys. Also, note that I used MathJax to typeset all of mathematical notation and I was able to embed a single-cell instance of Sage to do some live computations.

I really enjoy this short video introduction to group theory by James Grime (aka Singing Banana), especially since it mentions Coxeter groups (one of research interestes).