305 – Projects

May 9, 2012

As mentioned before, I asked my 305 students to write a short paper as a final project. I am posting them here, with their permission; it is my hope that people will find them useful. There are some very nice papers here.

  1. The 17 plane symmetry groups. By Samantha Burns, Courtney Fletcher, and Aubray Zell.
  2. The Banach-Tarski paradox. By Josh Giudicelli, Chantel Kelly, and James Kunz.
  3. The quaternions & octonions. By Kyle McAllister.
  4. The pocket cube. By Mike Mesenbrink, and Nicole Stevenson.
  5. 17 plane symmetry groups. By Anna Nelson, Holly Newman, and Molly Shipley.
  6. The Banach-Tarski paradox and amenability. By Kameryn Williams.

305 – A brief update on n(3)

April 12, 2012

This continues the previous post on A lower bound for n(3).

Only recently I was made aware of a note dated November 22, 2001, posted on Harvey Friedman‘s page, “Lecture notes on enormous integers”. In section 8, Friedman recalls the definition of the function n(k), the length of the longest possible sequence x_1,x_2,\dots,x_n from \{1,2,\dots,k\} with the property that for no i<j\le n/2, the sequence x_i,x_{i+1},\dots,x_{2i} is a subsequence of x_j,x_{j+1},\dots,x_{2j}.

Friedman says that “A good upper bound for n(3) is work in progress”, and states (without proof):

Theorem. n(3)\le A_k(k), where k=A_5(5).

Here, A_1,A_2,\dots are the functions of the Ackermann hierarchy (as defined in the previous post).

He also indicates a much larger lower bound for n(4). We need some notation first: Let A(m)=A_m(m). Use exponential notation to denote composition, so A^3(n)=A(A(A(n))).

Theorem. Let m=A(187196). Then n(4)>A^m(1).

He also states a result relating the rate of growth of the function n(\cdot) to what logicians call subsystems of first-order arithmetic. A good reference for this topic is the book Metamathematics of First-order Arithmetic, by Hájek and Pudlák, available through Project Euclid.

There is a recent question on MathOverflow on this general topic.


305 – Derived subgroups of symmetric groups

April 11, 2012

One of the problems in the last homework set is to study the derived group of the symmetric group S_n.

Recall that if G is a group and a,b\in G, then their commutator is defined as

{}[a,b]=aba^{-1}b^{-1}.

The derived group G' is the subgroup of G generated by the commutators.

Note that, since any permutation has the same parity as its inverse, any commutator in S_n is even. This means that G'\le A_n.

The following short program is Sage allows us to verify that, for 3\le i\le 6, every element of (S_i)' is actually a commutator. The program generates a list of the commutators of S_i, then verifies that this list is closed under products and inverses (so it is a group). It also lists the size of this group. Note that the size is precisely {}|A_i|, so (S_i)'=A_i in these 4 cases:

Read the rest of this entry »


305 – Cube moves

April 11, 2012

Here is a small catalogue of moves of the Rubik’s cube. Appropriately combining them and their natural analogues under rotations or reflections, allow us to solve Rubik’s cube starting from any (legal) position. I show the effect the moves have when applied to the solved cube.

But, first, some relevant links:

Read the rest of this entry »


305 – Homework V

April 9, 2012

This is the last homework set of the term. It is due Friday, April 27, 2012, at the beginning of lecture, but I am fine collecting it during dead week, if that works better.

Read the rest of this entry »


305 – Homework IV

March 7, 2012

This homework set is due Wednesday, March 21, at the beginning of lecture.

Read the rest of this entry »


305 – A potpurri of groups

February 27, 2012

Here are a few examples of groups and links illustrating some of them. I will be adding to this list; if you find additional links that may be useful or interesting, please let me know. A nice general place to look at is the page for the book “Visual group theory.”

  • S_n, A_n, the symmetric and alternating groups in n letters.
  • Abelian groups, such as ({\mathbb Z}/n{\mathbb Z},+), (({\mathbb Z}/n{\mathbb Z})^*,\cdot),{\mathbb Z},{\mathbb Q}.
  • Dihedral groups. Here is a page by Erin Carmody illustrating the symmetries of the square. The Wikipedia page on dihedral groups has additional illustrations and interesting examples.
  • Braid groups. Patrick Dehornoy has done extensive research on braid groups, and his page has many useful surveys and papers on the topic. Again, the Wikipedia page is a useful introduction. The applet we saw in class is here.
  • Matrix groups. For example, GL_n({\mathbb R}), the group of all invertible n\times n matrices with real entries, or SL_n({\mathbb R}), the group of all n\times n matrices with real entries and determinant 1.
  • The plane symmetry (or Wallpaper) groups.
  • Coxeter groups.
  • Crystallographic groups.
  • Any group is (isomorphic to) a group of permutations, but the groups corresponding to permutation puzzles are naturally described this way. For example, Dana Ernst recently gave a talk on this topic.

305 – The Futurama theorem

February 24, 2012

Here is a link to Dana Ernst talk on the Futurama theorem of Ken Keeler. In this version, products are just as we treat them (left to right). Also, in this version, there is the “try it yourself” exercise we did not do, but you may want to practice a few examples on your own anyway to make sure you understand the argument.

Finally, the questions mentioned at the end of Ernst’s talk (see here) are all interesting, and if you figure one or several of them out, please turn them in for extra credit.

(By the way, the same applies to all problems we have been discussing. For example, if through the term you figure a way of producing a really long sequence giving us a better bound for n(3) than what you obtained when the homework was due, please turn it in as well.)


305 – Campanology

February 24, 2012

Campanology, or bell ringing, is an English tradition, where a round of cathedral bells is rung by permuting their order. The book discusses some examples of the possible patterns used in practice (the Plain Lead on four bells, and the Plain Bob Minimus). Additional examples can be found in the Wikipedia link, and links are provided there to a few additional sites, such as bellringing.org.

I strongly recommend that you read Section 3.5 in the book dealing with this topic. It introduces through an example the useful notion of cosets, and also it is quite interesting. For example, it shows how several ideas from group theory were used in practice since the seventeenth century, predating the introduction of the concepts by Galois and his contemporaries, and in a completely different setting.

I did not know about this until I read the book, and of course now I see mentions of bell-ringing everywhere.

The quote above, for example, is from the book Combinatorial Set Theory by Lorenz Halbeisen.

A nice article on the topic (in French) can be found here; coincidentally, the article also talks at the end about juggling. The video of the talk on the mathematics of juggling by Allen Knutson that we saw an excerpt of today is here. A few technical and expository articles on this topic, by renown mathematician (and juggler) Ronald Graham, and his coauthors, can be found in Graham’s page. See for example here, here, here, and here.


305 – Homework III

February 17, 2012

This homework set is due Wednesday, February 29th, at the beginning of lecture, but feel free to turn it in earlier if possible. Recall that “show” means “prove”.

Read the rest of this entry »