featured – Page 22 – neverendingbooks

The 15-puzzle groupoid (2)

Published June 19, 2007 by lieven

In the 15-puzzle groupoid 1 we have seen that the legal positions of the classical 15-puzzle are the objects of a category in which every morphism is an isomorphism (a groupoid ). Today, we will show that there are exactly 10461394944000 objects (legal positions) in this groupoid. The crucial fact is that positions with the hole in a fixed place can be identified with the elements of the alternating group $A_{15} $, a fact first proved by William Edward Story in 1879 in a note published in the American Journal of Mathematics.

Recall from last time that the positions reachable from the initial position can be encoded as $\boxed{\tau} $ where $\tau $ is the permutation on 16 elements (the 15 numbered squares and 16 for the hole) such that $\tau(i) $ tells what number in the position lies on square $i $ of the initial position. The set of all reachable positions are the objects of our category. A morphism $\boxed{\tau} \rightarrow \boxed{\sigma} $ is a legal sequence of slide-moves starting from position $\boxed{\tau} $ and ending at position $\boxed{\sigma} $. That is,

$\boxed{\sigma} = (16,i_k)(16,i_{k-1}) \cdots (16,i_2)(16,i_1) \boxed{\tau} $

Hexagonal Moonshine (1)

Published June 18, 2007 by lieven

Over at the Arcadian Functor, Kea is continuing her series of blog posts on M-theory (the M is supposed to mean either Monad or Motif). A recurrent motif in them is the hexagon and now I notice hexagons popping up everywhere. I will explain some of these observations here in detail, hoping that someone, more in tune with recent technology, may have a use for them.

The three string braid group $B_3 $ is expected to play a crucial role in understanding monstrous moonshine so we should know more about it, for example about its finite dimensional representations. Now, _M geometry_ is pretty good at classifying finite dimensional representations provided the algebra is “smooth” which imples that for every natural number n the variety $\mathbf{rep}_n~A $ of n-dimensional representations of A is a manifold. Unfortunately, the group algebra $A=\mathbb{C} B_3 $ of the three string braid group is singular as we will see in a moment and the hunt for singularities in low dimensional representation varieties will reveal hexagons.

The 15-puzzle groupoid (1)

Published June 17, 2007 by lieven

Before we go deeper into Conway’s M(13) puzzle, let us consider a more commonly known sliding puzzle: the 15-puzzle. A heated discussion went on a couple of years ago at sci-physics-research, starting with this message. Lubos Motl argued that group-theory is sufficient to analyze the problem and that there is no reason to resort to groupoids (‘The human(oids) who like groupoids…’ and other goodies, in pre-blog but vintage Motl-speak) whereas ‘Jason’ defended his viewpoint that a groupoid is the natural symmetry for this puzzle.

I’m mostly with Lubos on this. All relevant calculations are done in the symmetric group $S_{16} $ and (easy) grouptheoretic results such as the distinction between even and odd permutations or the generation of the alternating groups really crack the puzzle. At the same time, if one wants to present this example in class, one has to be pretty careful to avoid confusion between permutations encoding positions and those corresponding to slide-moves. In making such a careful analysis, one is bound to come up with a structure which isn’t a group, but is precisely what some people prefer to call a groupoid (if not a 2-group…).

Category: featured

The 15-puzzle groupoid (2)

Hexagonal Moonshine (1)

The 15-puzzle groupoid (1)