Puzzles, Groups, and Groupoids

Over at Good Math, Bad Math, MarkCC has a nice post introducing groupoids which uses the fifteen puzzle as an example. I like this example a lot, and I thought it would be interesting to expand on it a bit. So I’m going to tell you:

1. Why the Rubik’s Cube is a finite group,
2. Why the fifteen puzzle is a finite groupoid, and
3. How to solve the fifteen puzzle.

I’m not going to assume any knowledge of groups or groupoids, but if you don’t know much group theory, you’ll have to skip over certain parts of the second half.

Convergence of Infinite Products

There is a simple convergence test for infinite products that I think deserves to be better known.

Theorem. Let be a sequence of positive numbers. Then the infinite product

converges if and only if the series

converges.

Periodic Functions Problem

Here’s a neat little problem that I learned about during a party in my first year of graduate school. I don’t know where it’s from originally, but I got it from Joe Miller:

Show that there exist two periodic functions whose sum is the identity function:

for all .

Hello World!

Wow,

Between teaching, research, paper–writing, and job applications, last semester was extremely busy for me. Obviously my blogging suffered (my last post was in July!), though I’m glad to see that Greg has been carrying the torch. With less to do this semester, I’m intending to start blogging again regularly. Hopefully my return will inspire Matt to come out of retirement!

Contributing to Wikipedia

Well, I decided to write my first Wikipedia article, which is on the Lie group . I look up mathematics on Wikipedia a lot, and I’ve also been linking to Wikipedia articles in my blog entries, so I thought I should start giving back.

I’m not a particular expert on , and I wrote the article mainly because I wanted to include the classification of elements into elliptic, parabolic, and hyperbolic, as groundwork for writing articles on isometries of the hyperbolic plane and on the classification of self-homeomorphisms of the torus.

Please let me know if you have any comments or suggestions. If anyone would be willing to help, it could use a better summary of the representation theory (although there is also a whole article on that subject), and could also probably use a section entitled “algebraic structure”. In addition, I wasn’t really confident enough with my algebraic geometry to write anything about the relationship with moduli space.

Combinatorial Julia Sets (1)

I have been reading recently about complex dynamics, in particular the Mandelbrot set and the associated Julia sets. Mathematicians seem to be in awe of these fractals, in particular of the intricate beauty of the Mandelbrot set, and introductions to the subject tend to focus on the stunning complexity of the (computer-generated) pictures.

Though I agree that the pictures are compelling, I think it does a disservice to the subject to focus on the complexity. In some sense, Julia sets are quite straightforward, not really much more complicated than the Sierpinski gasket or the Koch curve. The structure is just a little bit harder to see, primarily because a Julia set is something like a “co-fractal”.

Euler’s Nonstandard Nonsense

Matt’s post on the harmonic series has inspired me to share with you some nonsense due to Euler, leading to a beautiful non-proof of the following identity:

In my opinion, this is one of the few non-proofs that every mathematician should know.

Graph Minor Theory, Part 4

< See Part 3

Before starting this post, I have to warn you that it will be getting somewhat technical. I should also say that I’m not an expert in this area. I learned much of what I’m talking about by reading Graphs on Surfaces by Bojan Mohar and Carsten Thomassen.

Last time I promised that I would try to explain the six forbidden trivalent minors for the projective plane. To start, let me present some new drawings of these minors:

Graph Minor Theory, Part 3

< See Part 2

Okay, after two very expository posts I’m ready to get at something less elementary: forbidden minors for embeddings on surfaces. I’m going to need to assume some additional background, including the classification of closed surfaces:

Orientable: Sphere, Torus, 2-Holed Torus, etc.

Non-Orientable: Projective Plane, Klein Bottle, etc.

Topologists generally prefer to talk about embeddings of graphs in closed surfaces. For example, we draw graphs on the sphere instead of on the plane (a sphere is just a plane with an extra point an infinity), and we similarly prefer the projective plane to the Möbius strip.

Graph Minor Theory, Part 2

< See Part 1

Recall that a graph is planar if it can be drawn on the plane without edge crossings. In the last post, I mentioned Kuratowski’s characterization of planar graphs:

Kuratowski’s Theorem. A graph is planar if and only if it has neither nor as a minor:

(Here refers to the complete graph on 5 vertices, and is the complete bipartite graph on two sets of three vertices.)

I don’t know a really elegant proof of this theorem, but I do have some sense of why these two graphs are the right forbidden minors.