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!

a wintry chataigneraie

It took us some time to clear the array of old chestnut trees.

But it paid off. A good harvest easily gives half a ton of chestnuts, including some rare, older varieties.

In the autumn, the coloured leaves make a spectacular view. Now it looks rather desolate.

But, the wind piles up the fallen leaves in every nook, cranny, corner or entrance possible.

My day in the mountains: ‘harvesting’ fallen leaves…

Coxeter on Escher’s Circle Limits

Conway’s orbifold notation gives a uniform notation for all discrete groups of isometries of the sphere, the Euclidian plane as well as the hyperbolic plane.

This includes the groups of symmetries of Escher’s Circle Limit drawings. Here’s Circle Limit III

And ‘Angels and Devils’ aka Circle Limit IV:

If one crawls along a mirror of this pattern until one hits another mirror and then turns right along this mirror and continues like this, you get a quadrilateral path with four corners $\frac{\pi}{3}$, whose center seems to be a $4$-fold gyration point. So, it appears to have symmetry $4 \ast 3$.

(image credit: MathCryst)

However, looking more closely, every fourth figure (either devil or angel) is facing away rather than towards us, so there’s no gyration point, and the group drops to $\ast 3333$.

Harold S. M. Coxeter met Escher in Amsterdam at the ICM 1954.

The interaction between the two led to Escher’s construction of the Circle Limits, see How did Escher do it?

Here’s an old lecture by Coxeter on the symmetry of the Circle Limits:

Roots of unity and the Big Picture

All lattices in the moonshine picture are number-like, that is of the form $M \frac{g}{h}$ with $M$ a positive integer and $0 \leq g < h$ with $(g,h)=1$. To understand the action of the Bost-Connes algebra on the Big Picture it is sometimes better to view the lattice $M \frac{g}{h}$ as a primitive $h$-th root of unity, centered at $hM$.

The distance from $M$ to any of the lattices $M \frac{g}{h}$ is equal to $2 log(h)$, and the distances from $M$ and $M \frac{g}{h}$ to $hM$ are all equal to $log(h)$.

For a prime value $h$, these $h$ lattices are among the $h+1$ lattices branching off at $hM$ in the $h$-adic tree (the remaining one being $h^2M$).

For general $h$ the situation is more complex. Here’s the picture for $h=6$ with edges in the $2$-adic tree painted blue, those in the $3$-adic tree red.

\xymatrix{& & M \frac{1}{2} \ar@[blue]@{-}[d] & \\
& M \ar@[blue]@{-}[r] \ar@[red]@{-}[d] & 2M \ar@[red]@{-}[d] & M \frac{1}{6} \ar@[red]@{-}[d] \\
M \frac{1}{3} \ar@[red]@{-}[r] & 3M \ar@[blue]@{-}[r] \ar@[red]@{-}[d] & \boxed{6 M} \ar@[blue]@{-}[r] & 3M \frac{1}{2} \ar@[red]@{-}[d] \\ & M \frac{2}{3} & & M \frac{5}{6}} \]

To describe the moonshine group $(n|h)+e,f,\dots$ (an example was worked out in the tetrahedral snake post), we need to study the action of base-change with the matrix
x = \begin{bmatrix} 1 & \frac{1}{h} \\ 0 & 1 \end{bmatrix} \]
which sends a lattice of the form $M \frac{g}{h}$ with $0 \leq g < h$ to $M \frac{g+M}{h}$, so is a rotation over $\frac{2 \pi M}{h}$ around $h M$. But, we also have to describe the base-change action with the matrix \[ y = \begin{bmatrix} 1 & 0 \\ n & 1 \end{bmatrix} \] and for this we better use the second description of the lattice as $M \frac{g}{h}=(\frac{g'}{h},\frac{1}{h^2M})$ with $g'$ the multiplicative inverse of $g$ modulo $h$. Under the action by $y$, the second factor $\frac{1}{h^2M}$ will be fixed, so this time we have to look at all lattices of the form $(\frac{g}{h},\frac{1}{h^2M})$ with $0 \leq g < h$, which again can be considered as another set of $h$-th roots of unity, centered at $hM$. Here's this second interpretation for $h=6$: \[ \xymatrix{M \frac{5}{6} \ar@[red]@{-}[d] & & 4M \frac{1}{3} \ar@[red]@{-}[d] & \\ 3M \frac{1}{2} \ar@[blue]@{-}[r] \ar@[red]@{-}[d] & \boxed{6M} \ar@[blue]@{-}[r] \ar@[red]@{-}[d] & 12 M \ar@[red]@{-}[r] \ar@[red]@{-}[d] & 4 M \frac{2}{3} \\ M \frac{1}{6} & 18 M \ar@[blue]@{-}[r] \ar@[blue]@{-}[d] & 36 M & \\ & 9M \frac{1}{2} & & } \] Under $x$ the first set of $h$-th roots of unity centered at $hM$ is permuted, whereas $y$ permutes the second set of $h$-th roots of unity.
These interpretations can be used to spot errors in computing the finite groups $\Gamma_0(n|h)/\Gamma_0(n.h)$.

Here’s part of the calculation of the action of $y$ on the $(360|1)$-snake (which consists of $60$-lattices).

First I got a group of order roughly $600.000$. After correcting some erroneous cycles, the order went down to 6912.

Finally I spotted that I mis-numbered two lattices in the description of $x$ and $y$, and the order went down to $48$ as it should, because I knew it had to be equal to $C_2 \times C_2 \times A_4$.

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)

nc-geometry and moonshine?

A well-known link between Conway’s Big Picture and non-commutative geometry is given by the Bost-Connes system.

This quantum statistical mechanical system encodes the arithmetic properties of cyclotomic extensions of $\mathbb{Q}$.

The corresponding Bost-Connes algebra encodes the action by the power-maps on the roots of unity.

It has generators $e_n$ and $e_n^*$ for every natural number $n$ and additional generators $e(\frac{g}{h})$ for every element in the additive group $\mathbb{Q}/\mathbb{Z}$ (which is of course isomorphic to the multiplicative group of roots of unity).

The defining equations are
e_n.e(\frac{g}{h}).e_n^* = \rho_n(e(\frac{g}{h})) \\
e_n^*.e(\frac{g}{h}) = \Psi^n(e(\frac{g}{h}).e_n^* \\
e(\frac{g}{h}).e_n = e_n.\Psi^n(e(\frac{g}{h})) \\
e_n.e_m=e_{nm} \\
e_n^*.e_m^* = e_{nm}^* \\
e_n.e_m^* = e_m^*.e_n~\quad~\text{if $(m,n)=1$}

Here $\Psi^n$ are the power-maps, that is $\Psi^n(e(\frac{g}{h})) = e(\frac{ng}{h}~mod~1)$, and the maps $\rho_n$ are given by
\rho_n(e(\frac{g}{h})) = \sum e(\frac{i}{j}) \]
where the sum is taken over all $\frac{i}{j} \in \mathbb{Q}/\mathbb{Z}$ such that $n.\frac{i}{j}=\frac{g}{h}$.

Conway’s Big Picture has as its vertices the (equivalence classes of) lattices $M,\frac{g}{h}$ with $M \in \mathbb{Q}_+$ and $\frac{g}{h} \in \mathbb{Q}/\mathbb{Z}$.

The Bost-Connes algebra acts on the vector-space with basis the vertices of the Big Picture. The action is given by:
e_n \ast \frac{c}{d},\frac{g}{h} = \frac{nc}{d},\rho^m(\frac{g}{h})~\quad~\text{with $m=(n,d)$} \\
e_n^* \ast \frac{c}{d},\frac{g}{h} = (n,c) \times \frac{c}{nd},\Psi^{\frac{n}{m}}(\frac{g}{h})~\quad~\text{with $m=(n,c)$} \\
e(\frac{a}{b}) \ast \frac{c}{d},\frac{g}{h} = \frac{c}{d},\Psi^c(\frac{a}{b}) \frac{g}{h}

This connection makes one wonder whether non-commutative geometry can shed a new light on monstrous moonshine?

This question is taken up by Jorge Plazas in his paper Non-commutative geometry of groups like $\Gamma_0(N)$

Plazas shows that the bigger Connes-Marcolli $GL_2$-system also acts on the Big Picture. An intriguing quote:

“Our interest in the $GL_2$-system comes from the fact that its thermodynamic properties encode the arithmetic theory of modular functions to an extend which makes it possible for us to capture aspects of moonshine theory.”

Looks like the right kind of paper to take along when I disappear next week for some time in the French mountains…