a COLgo endgame

COL is a map-colouring game, attibuted to Colin Vout. COLgo is COL played with Go-stones on a go-board.

The two players, bLack (left) and white (right) take turns placing a stone of their colour on the board, but two stones of the same colour may not be next to each other.

The first player unable to make a legal move looses this game.

As is common in combinatorial game theory we do not specify which player has the move. There are $4$ different outcomes, the game is called:

– positive, if there is a winning strategy for Left (bLack),
– negative, if there is a winning strategy for Right (white),
– zero, if there is a winning strategy for the second-player,
– fuzzy, if there is a winning strategy for the first player.

Here’s an endgame problem: who wins this game?

Spoiler alert: solution below.

First we can exclude all spots which are dead, that is, are excluded for both players. Example, F11 is dead because it neighbors a black as well as a white stone, but F10 is alive as it can be played by white (Right).

If we remove all dead spots, we are left with 4 regions (the four extremal corners of the board) as well as 5 spots, 3 for white and 2 for black.

That is, the game reduces to this “sum”-game, in which a player chooses one of the regions and does a legal move in that component, or takes a stone of its own colour from the second row.

Next, we have to give a value to each of the region-games.

– the right-most game has value $0$ as the second player has a winning strategy by reflecting the first player’s move with respect to the central (dead) spot.

– the left-most game is equivalent to one black stone. Black can make two moves in the game, independent of the only move that white can make. So it has value $+1$.

– the sum-game of the two middle games has value zero. The second player can win by mirroring the first player’s move in the other component. This is called the Tweedledee-Tweedledum argument.

But then, the total value of the endgame position is

zero, so the first player to move looses the game!

Penrose tiles in Helsinki


(image credit: Steve’s travels & stuff)

A central street in Helsinki has been paved with Penrose tiles.


(image credit: Sattuman soittoa)

From a Finnish paper:

“The street could also be an object to mathematical awe. The stone under one’s feet is embroidered with some profound geometry, namely, Penrose tiling.

In 1974, a British mathematician Roger Penrose realised a plane could be fully covered with a few simple rules such that the pattern constantly changes. These kind of discontinuous patterns are interesting to mathematicians since the patterns can be used to solve other geometrical problems. Together, the tiles can randomly form patterns reminding a star or the Sun but they do not regularly recur in the tiling.

Similar features are found in the old Arabic ornaments. The tiling of the Central Street prom was selected by Yrjö Rossi.

If your kid stays put to stare at the tiling, they might have what they need in order to become a mathematician.”

(via Reddit/m)

Chomp and the moonshine thread

Chomp is a 2-player game, usually played with chocolate bars.

The players take turns in choosing one chocolate block and “eat it”, together with all other blocks that are below it and to its right. There is a catch: the top left block contains poison, so the first player forced to eat it dies, that is, looses the game.

If you start with a rectangular bar, the first player has a winning strategy, though it may take you too long to actually find the correct first move. See this post for the strategy-stealing argument.

If you label the blocks of the rectangular bar by $(a,b)$ with $0 \leq a \leq k$ and $0 \leq b \leq l$, with the poisonous one being $(0,0)$, then this can be viewed as choosing a divisor $d$ of $N=p^k q^l$ and removing all multiples of $d$ from the set of divisors of $N$. The first person forced to name $1$ looses.

This allows for higher dimensional versions of Chomp.

If you start with the set of all divisors of a given natural number $N$, then the strategy-stealing argument shows that the first player has a winning move.

A general position of the game corresponds to a finite set of integers, closed under taking divisors. At each move the player has to choose an element of this set and remove it as well as all its multiples.

The thread of $(N|1)$, relevant in understanding a moonshine group of the form $(n|m)+e,f,\dots$ with $N=n \times h$, consists of all divisors of $N$.

But then, the union of all threads for all 171 moonshine groups is a position in higher dimensional Chomp.

Who wins starting from this moonshine thread?

Perhaps not terribly important, but it forces one to imagine the subgraph of the monstrous moonshine picture on the $97$ number-lattices way better than by its Hasse diagram.

Click on the image for a larger version.

By the way, notice the (slight) resemblance with the ‘monstrous moonshine painting’ by Atria

Here’s how the Hasse diagram of the moonshine thread was produced. These are ‘notes to self’, because I tend to forget such things quickly.

1. Work though the list of 171 moonshine groups in Monstrous Moonshine, pages 327-329. Add to a list all divisors of $N$ for a group of type $N+e,f,\dots$ or $n|h+e,f,\dots$ with $N=n \times h$. This should give you these $97$ integers:

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,
31,32,33,34,35,36,38,39,40,41,42,44,45,46,47,48,50,51,52,54,55,56,57,59,60,62,
63,64,66,68,69,70,71,72,78,80,84,87,88,90,92,93,94,95,96,104,105,110,112,117,
119,120,126,136,144,160,168,171,176,180,208,224,252,279,288,360,416

2. Let $L$ be this list and use Sage:

P=Poset((L,attrcall("divides")),linear_extension=True)
H=P.hasse_diagram()
H.graphviz_string()

3. Copy the output to a file, say chomp.dot, and remove all new-line breaks from it.

4. Install Graphviz on Mac OS X.

5. In Terminal, type
dot -Tpng chomp.dot -o chomp.png

the monstrous moonshine picture – 1

We’re slowly closing in on the elusive moonshine picture, which is the subgraph of Conway’s Big Picture needed to describe all 171 moonshine groups.

About nine years ago I had a first go at it, drawing a tiny fraction of it, just enough to understand the 9 moonshine groups appearing in Duncan’s realization of McKay’s E(8)-observation.

Over the last weeks I’ve made enough doodles to feel confident that the full picture is within reach and is less unwieldy than I once feared it might be.

The moonshine picture only involves about 212 lattices and there are about 97 snakes crawling into it, the dimension of the largest cell being 3.

I write ‘about’ on purpose as I may have forgotten a few, or counted some twice as is likely to happen in all projects involving a few hundreds of things. I’ll come back to it later.

For now, I can only show you the monstrous moonshine painting, which is a work by the Chilean artist Magdalena Atria.

Here’s a close up:

It is a large scale painting made with plasticine, directly attached to the wall of the Alejandra Von Hartz gallery where it was exhibited in 2010.

What does it have to do with monstrous moonshine?

From the press release:

“In mathematics ‘monstrous moonshine’ is a term devised by John H. Conway and Simon P. Norton in 1979, used to describe the (then totally unexpected) connection between the monster group M and modular functions.

The term ‘monstrous moonshine’ was picked to convey the feelings from the bizarre relations between seemingly unrelated structures. The same spirit of connecting apparently unrelated situations, at times revealing deeper links and at times constructing them, permeates through Atria’s work in this exhibition.”

I was impressed by the first sentence until I read the Wikipedia article on monstrous moonshine which starts off with:

“In mathematics, monstrous moonshine, or moonshine theory, is the unexpected connection between the monster group M and modular functions, in particular, the j function. The term was coined by John Conway and Simon P. Norton in 1979.”

It appears that curators of art-exhibitions, and the intended public of their writings, are familiar with modular forms and functions, but fail to grasp the $j$-function.

When they speak about ‘modular forms’, I fear they’re thinking of something entirely different.

A tetrahedral snake

A tetrahedral snake, sometimes called a Steinhaus snake, is a collection of tetrahedra, linked face to face.

Steinhaus showed in 1956 that the last tetrahedron in the snake can never be a translation of the first one. This is a consequence of the fact that the group generated by the four reflexions in the faces of a tetrahedron form the free product $C_2 \ast C_2 \ast C_2 \ast C_2$.

For a proof of this, see Stan Wagon’s book The Banach-Tarski paradox, starting at page 68.

The tetrahedral snake we will look at here is a snake in the Big Picture which we need to determine the moonshine group $(3|3)$ corresponding to conjugacy class 3C of the Monster.

The thread $(3|3)$ is the spine of the $(9|1)$-snake which involves the following lattices
\[
\xymatrix{& & 1 \frac{1}{3} \ar@[red]@{-}[dd] & & \\
& & & & \\
1 \ar@[red]@{-}[rr] & & 3 \ar@[red]@{-}[rr] \ar@[red]@{-}[dd] & & 1 \frac{2}{3} \\
& & & & \\
& & 9 & &} \]
It is best to look at the four extremal lattices as the vertices of a tetrahedron with the lattice $3$ corresponding to its point of gravity.

The congruence subgroup $\Gamma_0(9)$ fixes each of these lattices, and the arithmetic group $\Gamma_0(3|3)$ is the conjugate of $\Gamma_0(1)$
\[
\Gamma_0(3|3) = \{ \begin{bmatrix} \frac{1}{3} & 0 \\ 0 & 1 \end{bmatrix}.\begin{bmatrix} a & b \\ c & d \end{bmatrix}.\begin{bmatrix} 3 & 0 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} a & \frac{b}{3} \\ 3c & 1 \end{bmatrix}~|~ad-bc=1 \} \]
We know that $\Gamma_0(3|3)$ normalizes the subgroup $\Gamma_0(9)$ and we need to find the moonshine group $(3|3)$ which should have index $3$ in $\Gamma_0(3|3)$ and contain $\Gamma_0(9)$.

So, it is natural to consider the finite group $A=\Gamma_0(3|3)/\Gamma_9(0)$ which is generated by the co-sets of
\[
x = \begin{bmatrix} 1 & \frac{1}{3} \\ 0 & 1 \end{bmatrix} \qquad \text{and} \qquad y = \begin{bmatrix} 1 & 0 \\ 3 & 0 \end{bmatrix} \]
To determine this group we look at the action of it on the lattices in the $(9|1)$-snake. It will fix the central lattice $3$ but will move the other lattices.

Recall that it is best to associate to the lattice $M.\frac{g}{h}$ the matrix
\[
\alpha_{M,\frac{g}{h}} = \begin{bmatrix} M & \frac{g}{h} \\ 0 & 1 \end{bmatrix} \]
and then the action is given by right-multiplication.

\[
\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}.x = \begin{bmatrix} 1 & \frac{1}{3} \\ 0 & 1 \end{bmatrix}, \quad \begin{bmatrix} 1 & \frac{1}{3} \\ 0 & 1 \end{bmatrix}.x = \begin{bmatrix} 1 & \frac{2}{3} \\ 0 & 1 \end{bmatrix}, \quad \begin{bmatrix} 1 & \frac{2}{3} \\ 0 & 1 \end{bmatrix}.x=\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \]
That is, $x$ corresponds to a $3$-cycle $1 \rightarrow 1 \frac{1}{3} \rightarrow 1 \frac{2}{3} \rightarrow 1$ and fixes the lattice $9$ (so is rotation around the axis through the vertex $9$).

To compute the action of $y$ it is best to use an alternative description of the lattice, replacing the roles of the base-vectors $\vec{e}_1$ and $\vec{e}_2$. These latices are projectively equivalent
\[
\mathbb{Z} (M \vec{e}_1 + \frac{g}{h} \vec{e}_2) \oplus \mathbb{Z} \vec{e}_2 \quad \text{and} \quad \mathbb{Z} \vec{e}_1 \oplus \mathbb{Z} (\frac{g’}{h} \vec{e}_1 + \frac{1}{h^2M} \vec{e}_2) \]
where $g.g’ \equiv~1~(mod~h)$. So, we have equivalent descriptions of the lattices
\[
M,\frac{g}{h} = (\frac{g’}{h},\frac{1}{h^2M}) \quad \text{and} \quad M,0 = (0,\frac{1}{M}) \]
and we associate to the lattice in the second normal form the matrix
\[
\beta_{M,\frac{g}{h}} = \begin{bmatrix} 1 & 0 \\ \frac{g’}{h} & \frac{1}{h^2M} \end{bmatrix} \]
and then the action is again given by right-multiplication.

In the tetrahedral example we have
\[
1 = (0,\frac{1}{3}), \quad 1\frac{1}{3}=(\frac{1}{3},\frac{1}{9}), \quad 1\frac {2}{3}=(\frac{2}{3},\frac{1}{9}), \quad 9 = (0,\frac{1}{9}) \]
and
\[
\begin{bmatrix} 1 & 0 \\ \frac{1}{3} & \frac{1}{9} \end{bmatrix}.y = \begin{bmatrix} 1 & 0 \\ \frac{2}{3} & \frac{1}{9} \end{bmatrix},\quad
\begin{bmatrix} 1 & 0 \\ \frac{2}{3} & \frac{1}{9} \end{bmatrix}. y = \begin{bmatrix} 1 & 0 \\ 0 & \frac{1}{9} \end{bmatrix}, \quad
\begin{bmatrix} 1 & 0 \\ 0 & \frac{1}{9} \end{bmatrix}. y = \begin{bmatrix} 1 & 0 \\ \frac{1}{3} & \frac{1}{9} \end{bmatrix} \]
That is, $y$ corresponds to the $3$-cycle $9 \rightarrow 1 \frac{1}{3} \rightarrow 1 \frac{2}{3} \rightarrow 9$ and fixes the lattice $1$ so is a rotation around the axis through $1$.

Clearly, these two rotations generate the full rotation-symmetry group of the tetrahedron
\[
\Gamma_0(3|3)/\Gamma_0(9) \simeq A_4 \]
which has a unique subgroup of index $3$ generated by the reflexions (rotations with angle $180^o$ around axis through midpoints of edges), generated by $x.y$ and $y.x$.

The moonshine group $(3|3)$ is therefore the subgroup generated by
\[
(3|3) = \langle \Gamma_0(9),\begin{bmatrix} 2 & \frac{1}{3} \\ 3 & 1 \end{bmatrix},\begin{bmatrix} 1 & \frac{1}{3} \\ 3 & 2 \end{bmatrix} \rangle \]

the 171 moonshine groups

Monstrous moonshine associates to every element of order $n$ of the monster group $\mathbb{M}$ an arithmetic group of the form
\[
(n|h)+e,f,\dots \]
where $h$ is a divisor of $24$ and of $n$ and where $e,f,\dots$ are divisors of $\frac{n}{h}$ coprime with its quotient.

In snakes, spines, and all that we’ve constructed the arithmetic group
\[
\Gamma_0(n|h)+e,f,\dots \]
which normalizes $\Gamma_0(N)$ for $N=h.n$. If $h=1$ then this group is the moonshine group $(n|h)+e,f,\dots$, but for $h > 1$ the moonshine group is a specific subgroup of index $h$ in $\Gamma_0(n|h)+e,f,\dots$.

I’m sure one can describe this subgroup explicitly in each case by analysing the action of the finite group $(\Gamma_0(n|h)+e,f,\dots)/\Gamma_0(N)$ on the $(N|1)$-snake. Some examples were worked out by John Duncan in his paper Arithmetic groups and the affine E8 Dynkin diagram.

But at the moment I don’t understand the general construction given by Conway, McKay and Sebbar in On the discrete groups of moonshine. I’m stuck at the last sentence of (2) in section 3. Nothing a copy of Charles Ferenbaugh Ph. D. thesis cannot fix.

The correspondence between the conjugacy classes of the Monster and these arithmetic groups takes up 3 pages in Conway & Norton’s Monstrous Moonshine. Here’s the beginning of it.