Category: games

How to win transfinite Nimbers?

Published January 11, 2011 by lievenlb

Last time we introduced the game of transfinite Nimbers and asked a winning move for the transfinite game with stones a at position $~(2,2) $, b at $~(4,\omega) $, c at $~(\omega+2,\omega+3) $ and d at position $~(\omega+4,\omega+1) $.

Above is the unique winning move : we remove stone d and by the rectangle-rule add three new stones, marked 1. We only need to compute in finite fields to solve this and similar problems.

First note that the largest finite number occuring in a stone-coordinate is 4, so in this case we can perform all calculations in the field $\mathbb{F}_{2^{2^2}}(\omega) = \mathbb{F}_{2^{12}} $ where (as before) we identify $\mathbb{F}_{2^{2^2}} = { 0,1,2,\ldots,15 } $ and we have seen that $\omega^3=2 $ (for ease of notation all Nim-additions and Nim-multiplications are denoted this time by + and x instead of $\oplus $ and $\otimes $ as we did last time, so for example $\omega^3 = \omega \otimes \omega \otimes \omega $).

If you’re not nimble with the Nim-tables, you can check all calculations in SAGE where we define this finite field via

sage: R.< x,y,z>=GF(2)[]
sage: S.< t,f,o>=R.quotient((x^2+x+1,y^2+y+x,z^3+x))

and we can now calculate in $\mathbb{F}_{2^{12}} $ using the symbols t for Two, f for Four and o for $\omega $. For example, we have seen that the nim-value of a stone is the nim-multiplication of its coordinates

sage: t*t
t + 1
sage: f*o
f*o
sage: (o+t)*(o+t+1)
o^2 + o + 1
sage: (o+f)*(o+1)
f*o + o^2 + f + o

That is, the nim-value of stone a is 3, stone b is $4 \times \omega $, stone c is $\omega^2+\omega+1 $ and finally that of stone d is equal to $\omega^2+5 \times \omega +4 $.

By adding them up, the nim-value of the original position is a finite number : 6. Being non-zero we know that the 2nd player has a winning strategy.

Just as in ordinary nim, we compare the value of a stone to the sum of the values of the other stones, to determine the stone we will play. These sums are for the four stones : 5 for a, $4 \times \omega+6 $ for b, $\omega^2+\omega+7 $ for c and $\omega^2+5 \times \omega+2 $ for d. There is only one stone where this sum is smaller than the stone-value, so we know we have to make our move with stone d.

By the Nimbers-rule we need to find a rectangle with top-right hand corner $~(\omega+4,\omega+1) $ and lower-left hand corner $~(u,v) $ such that the values of the three new corners adds up to $\omega^2+5 \times \omega+2 $, that is we have to solve

$u \times v + u \times (\omega+1) + (\omega+4)\times v = \omega^2+5 \times \omega+2 $

where u and v are ordinals smaller than $\omega+4 $ and $\omega+1 $. u and v cannot be both finite, for then we wouldn’t obtain a $\omega^2 $ term. Similarly (u,v) cannot be of the form $~(u,\omega) $ with u finite because then the left-hand sum would be $\omega^2+4 \times \omega + u $ and likewise it cannot be of the form $~(\omega+i,v) $ with i and v finite as then the coefficient of $\omega $ in the left-hand sum will be i+1 and we cannot take i equal to 4.

The only remaining possibility is that (u,v) is of the form $~(\omega+i,\omega) $ with i finite, in which case the left-hand sum equals $~\omega^2+ 5 \times \omega + i $ whence i=2 and we have found our unique winning move!

But, our opponent can make life difficult by forcing us to compute in larger and larger finite fields. For example, if she would move next by dropping the c stone down to the 256-th row, what would be our next move?

(one possible winning move is to remove the stone at $~(\omega+2,\omega) $ and add stones at the three new corners of the rectangle : $~(257,2), (257,\omega) $ and $~(\omega+2,2) $)

Leave a Comment

n-dimensional and transfinite Nimbers

Published January 8, 2011 by lievenlb

Today, we will expand the game of Nimbers to higher dimensions and do some transfinite Nimber hacking.

In our identification between $\mathbb{F}_{16}^* $ and 15-th roots of unity, the number 8 corresponds to $\mu^6 $, whence $\sqrt{8}=\mu^3=14 $. So, if we add a stone at the diagonal position (14,14) to the Nimbers-position of last time

we get a position of Nim-value 0, that is, winnable for the second player. In fact, this is a universal Nimbers-truth :

Either the 2nd player wins a Nimbers-position, or one can add one stone to the diagonal such that it becomes a 2nd player win.

The proof is elementary : choose a Fermat 2-power such that all stones have coordinates smaller than $2^{2^n} $. If the Nim-value of the position isn’t zero, it corresponds to a unit $\alpha \in \mathbb{F}_{2^{2^n}}^* $. Now,the Frobenius map $x \mapsto x^2 $ is an automorphism of any finite field of characteristic two, so the square root $\sqrt{\alpha} $ also belongs to $\mathbb{F}_{2^{2^n}} $, done!

3-dimensional Nimbers is played in the first octant of the integral lattice $\mathbb{Z}^3 $ by placing a finite number of balls at places $~(a,b,c) \in \mathbb{N}^3 $ with $abc \geq 1 $.

Moves are defined by replacing the rectangular-rule of the two-dimensional version by the cuboid-rule : take a cuboid with faces parallel to the coordinate planes whose corner of maximal distance from the origin is one of the balls in the position. Remove that ball and add new balls to the unoccupied corners and remove balls at occupied corners.

Here, we allow the corner-points to have zero as some of its coordinates, but these balls are considered dead in the game. As in the two-dimensional game, this cuboid-rule encompasses several legal moves depending on the number of corners in the cuboid having zero-coordinates.

Again, it follows by induction that the Nim-value of a ball placed at position $~(a,b,c) $ is equal to the Nim-multiplication $a \otimes b \otimes c $ and we can calculate the Nim-value of a 3-dimensional Nimbers-position by computing in a suitable field $\mathbb{F}_{2^{2^n}} $. (The extension to higher dimensions is now obvious)

Does 3-dimensional Nimbers satisfy the ‘universal truth’, that is, can one make any position a 2nd player win by adding at most one stone to the body-diagonal?

The previous argument fails. As $\mathbb{F}_4^* $ is the cyclic group of order three, the 3rd roots of unity in $\overline{\mathbb{F}_2} $ correspond to the numbers 1,2 and 3, so the map $x \mapsto x^3 $ cannot be a bijection on any of the finite fields $\mathbb{F}_{2^{2^n}} $.

But then, perhaps, a third root is added by going to a larger such field $\mathbb{F}_{2^{2^N}} $? Well, not quite. Take for example 2, then $\sqrt[3]{2} \notin \mathbb{F}_{2^{2^N}} $. (2 has order 3 in $\mathbb{F}_4 $ and so its 3rd root must have order 9, but 9 does not divide any number of the form $2^{2^N}-1 $ as the Fermat-powers mod 9 can only be 4 or 7).

In fact one can show that this also holds for any number not in the image of the cubing-map in some $\mathbb{F}_{2^{2^n}} $ as

$\mathbb{N}={ 0,1,2,\ldots } = \cup_N \mathbb{F}_{2^{2^N}} $

with Nim-addition and multiplication is the quadratic closure of $\mathbb{F}_2 $ (see for example ONAG).

The situation changes if we allow ourself to play transfinite Nimbers, with the same rules as before but now we allow the stone, balls etc. to be placed at points of which the coordinates are not restricted to $\mathbb{N}_+ = \{ 1,2,3,\ldots \} $ but may vary over $[\beta]_+ $ for some ordinal $\beta $ where $[\beta]_+=\{ 1,2,\ldots,\omega,\omega+1,\ldots \} $ is the set of all ordinals smaller than $\beta $.

In transfinite 3-dimensional Nimbers the ‘universal truth’ still holds, provided we play it on a cube of sizes $[\omega^{\omega}]_+ $. In particular we have that $\sqrt[3]{2}=\omega $ by the simplicity rule (see ONAG or the Conway’s nim-arithmetic post)

In general, n-dimensional transfinite Nimbers played on an n-gid of sizes $[\omega^{\omega^{\omega}}]_+ $ satisfies the universal truth : either a position is a 2nd player win or it becomes one by adding one n-ball to a diagonal position! (this follows immediately because $[\omega^{\omega^{\omega}}] $ with Nim-addition and multiplication is isomorphic to the algebraic closure of $\mathbb{F}_2 $).

2-dimensional transfinite Nimbers is still pretty playable. Below a position on a $\omega.2 $-board with stones as positions $~(2,2),(4,\omega),(\omega+2,\omega+3) $ and $~(\omega+4,\omega+1) $

Give a winning move for the first player!

Leave a Comment

How to play Nimbers?

Published January 7, 2011 by lievenlb

Nimbers is a 2-person game, winnable only if you understand the arithmetic of the finite fields $\mathbb{F}_{2^{2^n}} $ associated to Fermat 2-powers.

It is played on a rectangular array (say a portion of a Go-board, for practical purposes) having a finite number of stones at distinct intersections. Here’s a typical position

The players alternate making a move, which is either

removing one stone, or
moving a stone to a spot on the same row (resp. the same column) strictly to the left (resp. strictly lower), and if there’s already a stone on this spot, both stones are removed, or
adding stones to the empty corners of a rectangle having as its top-right hand corner a chosen stone and removing stones at the occupied corners

Here we illustrate two possible moves from the above position, in the first we add two new stones and remove 2 existing stones, in the second we add three new stones and remove only the top right-hand stone.

As always, the last player able to move wins the game!

Note that Nimbers is equivalent to Lenstra’s ‘turning corners’-game (as introduced in his paper Nim-multiplication or mentioned in Winning Ways Chapter 14, page 473).

If all stones are placed on the left-most column (or on the bottom row) one quickly realizes that this game reduces to classical Nim with Nim-heap sizes corresponding to the stones (for example, the left-most stone corresponds to a heap of size 3).

Nim-addition $n \oplus m $ is defined inductively by

$n \oplus m = mex(n’ \oplus m,n \oplus m’) $

where $n’ $ is any element of ${ 0,1,\ldots,n-1 } $ and $m’ $ any element of ${ 0,1,\ldots,m-1 } $ and where ‘mex’ stands for Minimal EXcluded number, that is the smallest natural number which isn’t included in the set. Alternatively, one can compute $n \oplus m $ buy writing $n $ and $m $ in binary and add these binary numbers without carrying-over. It is well known that a winning strategy for Nim tries to shorten one Nim-heap such that the Nim-addition of the heap-sizes equals zero.

This allows us to play Nimber-endgames, that is, when all the stones have been moved to the left-column or the bottom row.

To evaluate general Nimber-positions it is best to add another row and column, the coordinate axes of the array

and so our stones lie at positions (1,3), (4,7), (6,4), (10,3) and (14,8). In this way all legal moves follow the rectangle-rule when we allow rectangles to contain corners on the added coordinate axes. For example, removing a stone is achieved by taking a rectangle with two sides on the added axes, and, moving a stone to the left (or the bottom) is done by taking a rectangle with one side at the x-axes (resp. the y-axes)

However, the added stones on the coordinate axes are considered dead and may be removed from the game. This observation allows us to compute the Grundy number of a stone at position (m,n) to be

$G(m,n)=mex(G(m’,n’) \oplus G(m’,n) \oplus G(m,n’)~:~0 \leq m’ < m, 0 \leq n’ < n) $

and so by induction these Grundy numbers are equal to the Nim-multiplication $G(m,n) = m \otimes n $ where

$m \otimes n = mex(m’ \otimes n’ \oplus m’ \otimes n \oplus m \otimes n’~:~0 \leq m’ < m, 0 \leq n’ < n) $

Thus, we can evaluate any Nimbers-position with stone-coordinates smaller than $2^{2^n} $ by calculating in a finite field using the identification (as for example in the odd Knights of the round table-post) $\mathbb{F}_{2^{2^n}} = \{ 0,1,2,\ldots,2^{2^n}-1 \} $

For example, when all stones lie in a 15×15 grid (as in the example above), all calculations can be performed using

Here, we’ve identified the non-zero elements of $\mathbb{F}_{16} $ with 15-th roots of unity, allowing us to multiply, and we’ve paired up couples $(n,n \oplus 1) $ allowing u to reduce nim-addition to nim-multiplication via

$n \oplus m = (n \otimes \frac{1}{m}) \otimes (m \oplus 1) $

In particular, the stone at position (14,8) is equivalent to a Nim-heap of size $14 \otimes 8=10 $. The nim-value of the original position is equal to 8

Suppose your opponent lets you add one extra stone along the diagonal if you allow her to start the game, where would you have to place it and be certain you will win the game?

One Comment

Seating the first few thousand Knights

Published February 3, 2010 by lievenlb

The Knight-seating problems asks for a consistent placing of n-th Knight at an odd root of unity, compatible with the two different realizations of the algebraic closure of the field with two elements.
The first identifies the multiplicative group of its non-zero elements with the group of all odd complex roots of unity, under complex multiplication. The second uses Conway’s ‘simplicity rules’ to define an addition and multiplication on the set of all ordinal numbers.

The odd Knights of the round table-problem asks for a specific one-to-one correspondence between two realizations of ‘the’ algebraic closure $\overline{\mathbb{F}_2} $ of the field of two elements.

The first identifies the multiplicative group of its non-zero elements with the group of all odd complex roots of unity, under complex multiplication. The addition on $\overline{\mathbb{F}_2} $ is then recovered by inducing an involution on the odd roots, pairing the one corresponding to x to the one corresponding to x+1.

The second uses Conway’s ‘simplicity rules’ to define an addition and multiplication on the set of all ordinal numbers. Conway proves in ONAG that this becomes an algebraically closed field of characteristic two and that $\overline{\mathbb{F}_2} $ is the subfield of all ordinals smaller than $\omega^{\omega^{\omega}} $. The finite ordinals (the natural numbers) form the quadratic closure of $\mathbb{F}_2 $.

On the natural numbers the Conway-addition is binary addition without carrying and Conway-multiplication is defined by the properties that two different Fermat-powers $N=2^{2^i} $ multiply as they do in the natural numbers, and, Fermat-powers square to its sesquimultiple, that is $N^2=\frac{3}{2}N $. Moreover, all natural numbers smaller than $N=2^{2^{i}} $ form a finite field $\mathbb{F}_{2^{2^i}} $. Using distributivity, one can write down a multiplication table for all 2-powers.

The Knight-seating problems asks for a consistent placing of n-th Knight $K_n $ at an odd root of unity, compatible with the two different realizations of $\overline{\mathbb{F}_2} $. Last time, we were able to place the first 15 Knights as below, and asked where you would seat $K_{16} $

$K_4 $ was placed at $e^{2\pi i/15} $ as 4 was the smallest number generating the ‘Fermat’-field $\mathbb{F}_{2^{2^2}} $ (with multiplicative group of order 15) subject to the compatibility relation with the generator 2 of the smaller Fermat-field $\mathbb{F}_2 $ (with group of order 15) that $4^5=2 $.

To include the next Fermat-field $\mathbb{F}_{2^{2^3}} $ (with multiplicative group of order 255) consistently, we need to find the smallest number n generating the multiplicative group and satisfying the compatibility condition $n^{17}=4 $. Let’s first concentrate on finding the smallest generator : as 2 is a generator for 1st Fermat-field $\mathbb{F}_{2^{2^1}} $ and 4 a generator for the 2-nd Fermat-field $\mathbb{F}_{2^{2^2}} $ a natural conjecture might be that 16 is a generator for the 3-rd Fermat-field $\mathbb{F}_{2^{2^3}} $ and, more generally, that $2^{2^i} $ would be a generator for the next field $\mathbb{F}_{2^{2^{i+1}}} $.

However, an “exercise” in the 1978-paper by Hendrik Lenstra Nim multiplication asks : “Prove that $2^{2^i} $ is a primitive root in the field $\mathbb{F}_{2^{2^{i+1}}} $ if and only if i=0 or 1.”

I’ve struggled with several of the ‘exercises’ in Lenstra’s paper to the extend I feared Alzheimer was setting in, only to find out, after taking pen and paper and spending a considerable amount of time calculating, that they are indeed merely exercises, when looked at properly… (Spoiler-warning : stop reading now if you want to go through this exercise yourself).

In the picture above I’ve added in red the number $x(x+1)=x^2+1 $ to each of the involutions. Clearly, for each pair these numbers are all distinct and we see that for the indicated pairing they make up all numbers strictly less than 8.

By Conway’s simplicity rules (or by checking) the pair (16,17) gives the number 8. In other words, the equation
$x^2+x+8 $ is an irreducible polynomial over $\mathbb{F}_{16} $ having as its roots in $\mathbb{F}_{256} $ the numbers 16 and 17. But then, 16 and 17 are conjugated under the Galois-involution (the Frobenius $y \mapsto y^{16} $). That is, we have $16^{16}=17 $ and $17^{16}=16 $ and hence $16^{17}=8 $. Now, use the multiplication table in $\mathbb{F}_{16} $ given in the previous post (or compute!) to see that 8 is of order 5 (and NOT a generator). As a consequence, the multiplicative order of 16 is 5×17=85 and so 16 cannot be a generator in $\mathbb{F}_{256} $.
For general i one uses the fact that $2^{2^i} $ and $2^{2^i}+1 $ are the roots of the polynomial $x^2+x+\prod_{j<i} 2^{2^j} $ over $\mathbb{F}_{2^{2^i}} $ and argues as before.

Right, but then what is the minimal generator satisfying $n^{17}=4 $? By computing we see that the pairings of all numbers in the range 16…31 give us all numbers in the range 8…15 and by the above argument this implies that the 17-th powers of all numbers smaller than 32 must be different from 4. But then, the smallest candidate is 32 and one verifies that indeed $32^{17}=4 $ (use the multiplication table given before).

Hence, we must place Knight $K_{32} $ at root $e^{2 \pi i/255} $ and place the other Knights prior to the 256-th at the corresponding power of 32. I forgot the argument I used to find-by-hand the requested place for Knight 16, but one can verify that $32^{171}=16 $ so we seat $K_{16} $ at root $e^{342 \pi i/255} $.

But what about Knight $K_{256} $? Well, by this time I was quite good at squaring and binary representations of integers, but also rather tired, and decided to leave that task to the computer.

If we denote Nim-addition and multiplication by $\oplus $ and $\otimes $, then Conway’s simplicity results in ONAG establish a field-isomorphism between $~(\mathbb{N},\oplus,\otimes) $ and the field $\mathbb{F}_2(x_0,x_1,x_2,\ldots ) $ where the $x_i $ satisfy the Artin-Schreier equations

$x_i^2+x_i+\prod_{j < i} x_j = 0 $

and the i-th Fermat-field $\mathbb{F}_{2^{2^i}} $ corresponds to $\mathbb{F}_2(x_0,x_1,\ldots,x_{i-1}) $. The correspondence between numbers and elements from these fields is given by taking $x_i \mapsto 2^{2^i} $. But then, wecan write every 2-power as a product of the $x_i $ and use the binary representation of numbers to perform all Nim-calculations with numbers in these fields.

Therefore, a quick and dirty way (and by no means the most efficient) to do Nim-calculations in the next Fermat-field consisting of all numbers smaller than 65536, is to use sage and set up the field $\mathbb{F}_2(x_0,x_1,x_2,x_3) $ by

R.< x,y,z,t > =GF(2)[]
S.< a,b,c,d >=R.quotient((x^2+x+1,y^2+y+x,z^2+z+x*y,t^2+t+x*y*z))

To find the smallest number generating the multiplicative group and satisfying the additional compatibility condition $n^{257}=32 $ we have to find the smallest binary number $i_1i_2 \ldots i_{16} $ (larger than 255) satisfying

(i1*a*b*c*t+i2*b*c*t+i3*a*c*t+i4*c*t+i5*a*b*t+i6*b*t+
i7*a*t+i8*t+i9*a*b*c+i10*b*c+i11*a*c+i12*c+i13*a*b+
i14*b+i15*a+i16)^257=a*c

It takes a 2.4GHz 2Gb-RAM MacBook not that long to decide that the requested generator is 1051 (killing another optimistic conjecture that these generators might be 2-powers). So, we seat Knight
$K_{1051} $ at root $e^{2 \pi i/65535} $ and can then arrange seatings for all Knight queued up until we reach the 65536-th! In particular, the first Knight we couldn’t place before, that is Knight $K_{256} $, will be seated at root $e^{65826 \pi i/65535} $.

If you’re lucky enough to own a computer with more RAM, or have the patience to make the search more efficient and get the seating arrangement for the next Fermat-field, please drop a comment.

I’ll leave you with another Lenstra-exercise which shouldn’t be too difficult for you to solve now : “Prove that $x^3=2^{2^i} $ has three solutions in $\mathbb{N} $ for each $i \geq 2 $.”

2 Comments

can -oids save group-theory 101?

Published February 15, 2009 by lievenlb

Two questions from my last group-theory 101 exam:

(a) : What are the Jordan-Holder components of the Abelian group $\mathbb{Z}/20 \mathbb{Z} $?

(b) : Determine the number of order 7 elements in a simple group of order 168.

Give these to any group of working mathematicians, and, I guess all of them will solve (a), whereas the number of correct solutions to (b) will be (substantially) smaller.

Guess what? All(!) my students solved (b) correctly, whereas almost none of them had anything sensible to say about (a). A partial explanation is that they had more drill-exercises applying the Sylow-theorems than ones concerning the Jordan-Holder theorem.

A more fundamental explanation is that (b) has to do with sub-structures whereas (a) concerns quotients. Over the years I’ve tried numerous methods to convey the quotient-idea : putting things in bags, dividing a big group-table into smaller squares, additional lessons on relations, counting modulo numbers … No method appears to have an effect, lasting until the examination.

At the moment I’m seriously considering to rewrite the entire course, ditching quotients and using them only in disguise via groupoids. Before you start bombarding me with comments, I’m well aware of the problems inherent in this approach.

Before you do groupoids, students have to know some basic category theory. But that’s ok with me. Since last year it has been decided that I should sacrifice the first three weeks of the course telling students the basics of sets, maps and relations. After this, the formal definition of a category will appear more natural to them than the definition of a group, not? Besides, most puzzle-problems I use to introduce groups are actually examples of groupoids…

But then, what are the main theorems on finite groupoids? Well, I can see the groupoid cardinality result, giving you in one stroke Lagrange’s theorem as well as the orbit-counting method. From this one can then prove the remaining classical group-results such as Cauchy and the Sylows, but perhaps there are more elegant approaches?

Have you seen a first-year group-theory course starting off with groupoids? Do you know an elegant way to prove a classical group-result using groupoids?

2 Comments

On2 : extending Lenstra’s list

Published January 27, 2009 by lievenlb

We have seen that John Conway defined a nim-addition and nim-multiplication on the ordinal numbers in such a way that the subfield $[\omega^{\omega^{\omega}}] \simeq \overline{\mathbb{F}}_2 $ is the algebraic closure of the field on two elements. We’ve also seen how to do actual calculations in that field provided we can determine the mystery elements $\alpha_p $, which are the smallest ordinals not being a p-th power of ordinals lesser than $[\omega^{\omega^{k-1}}] $ if $p $ is the $k+1 $-th prime number.

Hendrik Lenstra came up with an effective method to compute these elements $\alpha_p $ requiring a few computations in certain finite fields. I’ll give a rundown of his method and refer to his 1977-paper “On the algebraic closure of two” for full details.

For any ordinal $\alpha < \omega^{\omega^{\omega}} $ define its degree $d(\alpha) $ to be the degree of minimal polynomial for $\alpha $ over $\mathbb{F}_2 = [2] $ and for each prime number $p $ let $f(p) $ be the smallest number $h $ such that $p $ is a divisor of $2^h-1 $ (clearly $f(p) $ is a divisor of $p-1 $).

In the previous post we have already defined ordinals $\kappa_{p^k}=[\omega^{\omega^{k-1}.p^{n-1}}] $ for prime-power indices, but we now need to extend this definition to allow for all indices. So. let $h $ be a natural number, $p $ the smallest prime number dividing $h $ and $q $ the highest power of $p $ dividing $h $. Let $g=[h/q] $, then Lenstra defines

$\kappa_h = \begin{cases} \kappa_q~\text{if q divides}~d(\kappa_q)~\text{ and} \\ \kappa_g + \kappa_q = [\kappa_g + \kappa_q]~\text{otherwise} \end{cases} $

With these notations, the main result asserts the existence of natural numbers $m,m’ $ such that

$\alpha_p = [\kappa_{f(p)} + m] = [\kappa_{f(p)}] + m’ $

Now, assume by induction that we have already determined the mystery numbers $\alpha_r $ for all odd primes $r < p $, then by teh argument of last time we can effectively compute in the field $[\kappa_p] $. In particular, we can compute for every element its multiplicative order $ord(\beta) $ and therefore also its degree $d(\beta) $ which has to be the smallest number $h $ such that $ord(\beta) $ divides $[2^h-1] $.

Then, by the main result we only have to determine the smallest number m such that $\beta = [\kappa_{f(p)} +m] $ is not a p-th power in $\kappa_p $ which is equivalent to the condition that

$\beta^{(2^{d(\beta)}-1)/p} \not= 1 $ if $p $ divides $[2^{d(\beta)}-1] $

All these conditions can be verified within suitable finite fields and hence are effective. In this manner, Lenstra could extend Conway’s calculations (probably using a home-made finite field program running on a slow 1977 machine) :

[tex]\begin{array}{c|c|c} p & f(p) & \alpha_p \\ \hline 3 & 2 & [2] \\ 5 & 4 & [4] \\ 7 & 3 & [\omega]+1 \\ 11 & 10 & [\omega^{\omega}]+1 \\ 13 & 12 & [\omega]+4 \\ 17 & 8 & [16] \\ 19 & 18 & [\omega^3]+4 \\ 23 & 11 & [\omega^{\omega^3}]+1 \\ 29 & 28 & [\omega^{\omega^2}]+4 \\ 31 & 5 & [\omega^{\omega}]+1 \\ 37 & 36 & [\omega^3]+4 \\ 41 & 20 & [\omega^{\omega}]+1 \\ 43 & 14 & [\omega^{\omega^2}]+ 1 \end{array}[/tex]

Right, so let’s try the case $p=47 $. To begin, $f(47)=23 $ whence we have to determine the smallest field containg $\kappa_{23} $. By induction (Lenstra’s tabel) we know already that

$\kappa_{23}^{23} = \kappa_{11} + 1 = [\omega^{\omega^3}]+1 $ and $\kappa_{11}^{11} = \kappa_5 + 1 = [\omega^{\omega}]+1 $ and $\kappa_5^5=[4] $

Because the smallest field containg $4 $ is $[16]=\mathbb{F}_{2^4} $ we have that $\mathbb{F}_2(4,\kappa_5,\kappa_{11}) \simeq \mathbb{F}_{2^{220}} $. We can construct this finite field, together with a generator $a $ of its multiplicative group in Sage via

sage: f1.< a >=GF(2^220)

In this field we have to pinpoint the elements $4,\kappa_5 $ and $\kappa_{11} $. As $4 $ has order $15 $ in $\mathbb{F}_{2^4} $ we know that $\kappa_5 $ has order $75 $. Hence we can take $\kappa_5 = a^{(2^{220}-1)/75} $ and then $4=\kappa_5^5 $.

If we denote $\kappa_5 $ by x5 we can obtain $\kappa_{11} $ as x11 by the following sage-commands

sage: c=x5+1

sage: x11=c.nth_root(11)

It takes about 7 minutes to find x11 on a 2.4 GHz MacBook. Next, we have to set up the field extension determined by $\kappa_{23} $ (which we will call x in sage). This is done as follows

sage: p1.=PolynomialRing(f1)


sage: f=x^23-x11-1

sage: F2=f1.extension(f,'u')

The MacBook needed 8 minutes to set up this field which is isomorphic to $\mathbb{F}_{2^{5060}} $. The relevant number is therefore $n=\frac{2^{5060}-1}{47} $ which is the gruesome

34648162040462867047623719793206539850507437636617898959901744136581<br/>
259144476645069239839415478030722644334257066691823210120548345667203443<br/>
317743531975748823386990680394012962375061822291120459167399032726669613
<br/>
442804392429947890878007964213600720766879334103454250982141991553270171

938532417844211304203805934829097913753132491802446697429102630902307815

301045433019807776921086247690468136447620036910689177286910624860871748

150613285530830034500671245400628768674394130880959338197158054296625733

206509650361461537510912269982522844517989399782602216622257291361930850

885916974186835958466930689748400561295128553674118498999873244045842040

080195019701984054428846798610542372150816780493166669821114184374697446

637066566831036116390063418916814141753876530004881539570659100352197393

997895251223633176404672792711603439161147155163219282934597310848529360

118189507461132290706604796116111868096099527077437183219418195396666836

014856037176421475300935193266597196833361131333604528218621261753883518

667866835204501888103795022437662796445008236823338104580840186181111557

498232520943552183185687638366809541685702608288630073248626226874916669

186372183233071573318563658579214650042598011275864591248749957431967297

975078011358342282941831582626985121760847852546207377440873367589369439

085660784239080183415569559585998884824991911321095149718147110882474280

968166266224151511519773175933506503369761671964823112231808283557885030

984081329986188655169245595411930535264918359325712373064120338963742590

76555755141425

Remains ‘only’ to take x,x+1,etc. to the n-th power and verify which is the first to be unequal to 1. For this it is best to implement the usual powering trick (via digital expression of the exponent) in the field F2, something like

sage: def power(e,n): ...: le=n.bits() ...: v=n.digits() ...: mn=F2(e) ...: out=F2(1) ...: i=0 ...: while i< le : ...: if v[i]==1 : out=F2(out_mn) ...: m=F2(mn_mn) ...: mn=F2(m) ...: i=i+1 ...: return(out) ...:

then it takes about 20 seconds to verify that power(x,n)=1 but that power(x+1,n) is NOT! That is, we just checked that $\alpha_{47}=\kappa_{11}+1 $.

It turns out that 47 is the hardest nut to crack, the following primes are easier. Here’s the data (if I didn’t make mistakes…)

[tex]\begin{array}{c|c|c} p & f(p) & \alpha_p \\ \hline 47 & 23 & [\omega^{\omega^{7}}]+1 \\ 53 & 52 & [\omega^{\omega^4}]+1 \\ 59 & 58 & [\omega^{\omega^8}]+1 \\ 61 & 60 & [\omega^{\omega}]+[\omega] \\ 67 & 66 & [\omega^{\omega^3}]+[\omega] \end{array}[/tex]

It seems that Magma is substantially better at finite field arithmetic, so if you are lucky enough to have it you’ll have no problem finding $\alpha_p $ for all primes less than 100 by the end of the day. If you do, please drop a comment with the results…

Leave a Comment

On2 : Conway’s nim-arithmetics

Published January 26, 2009 by lievenlb

Last time we did recall Cantor’s addition and multiplication on ordinal numbers. Note that we can identify an ordinal number $\alpha $ with (the order type of) the set of all strictly smaller ordinals, that is, $\alpha = { \alpha’~:~\alpha’ < \alpha } $. Given two ordinals $\alpha $ and $\beta $ we will denote their Cantor-sums and products as $[ \alpha + \beta] $ and $[\alpha . \beta] $.

The reason for these square brackets is that John Conway constructed a well behaved nim-addition and nim-multiplication on all ordinals $\mathbf{On}_2 $ by imposing the ‘simplest’ rules which make $\mathbf{On}_2 $ into a field. By this we mean that, in order to define the addition $\alpha + \beta $ we must have constructed before all sums $\alpha’ + \beta $ and $\alpha + \beta’ $ with $\alpha’ < \alpha $ and $\beta’ < \beta $. If + is going to be a well-defined addition on $\mathbf{On}_2 $ clearly $\alpha + \beta $ cannot be equal to one of these previously constructed sums and the ‘simplicity rule’ asserts that we should take $\alpha+\beta $ the least ordinal different from all these sums $\alpha’+\beta $ and $\alpha+\beta’ $. In symbols, we define

$\alpha+ \beta = \mathbf{mex} { \alpha’+\beta,\alpha+ \beta’~|~\alpha’ < \alpha, \beta’ < \beta } $

where $\mathbf{mex} $ stands for ‘minimal excluded value’. If you’d ever played the game of Nim you will recognize this as the Nim-addition, at least when $\alpha $ and $\beta $ are finite ordinals (that is, natural numbers) (to nim-add two numbers n and m write them out in binary digits and add without carrying). Alternatively, the nim-sum n+m can be found applying the following two rules :

the nim-sum of a number of distinct 2-powers is their ordinary sum (e.g. $8+4+1=13 $, and,
the nim-sum of two equal numbers is 0.

So, all we have to do is to write numbers n and m as sums of two powers, scratch equal terms and add normally. For example, $13+7=(8+4+1)+(4+2+1)=8+2=10 $ (of course this is just digital sum without carry in disguise).

Here’s the beginning of the nim-addition table on ordinals. For example, to define $13+7 $ we have to look at all values in the first 7 entries of the row of 13 (that is, ${ 13,12,15,14,9,8,11 } $) and the first 13 entries in the column of 7 (that is, ${ 7,6,5,4,3,2,1,0,15,14,13,12,11 } $) and find the first number not included in these two sets (which is indeed $10 $).

In fact, the above two rules allow us to compute the nim-sum of any two ordinals. Recall from last time that every ordinal can be written uniquely as as a finite sum of (ordinal) 2-powers :
$\alpha = [2^{\alpha_0} + 2^{\alpha_1} + \ldots + 2^{\alpha_k}] $, so to determine the nim-sum $\alpha+\beta $ we write both ordinals as sums of ordinal 2-powers, delete powers appearing twice and take the Cantor ordinal sum of the remaining sum.

Nim-multiplication of ordinals is a bit more complicated. Here’s the definition as a minimal excluded value

$\alpha.\beta = \mathbf{mex} { \alpha’.\beta + \alpha.\beta’ – \alpha’.\beta’ } $

for all $\alpha’ < \alpha, \beta’ < \beta $. The rationale behind this being that both $\alpha-\alpha’ $ and $\beta – \beta’ $ are non-zero elements, so if $\mathbf{On}_2 $ is going to be a field under nim-multiplication, their product should be non-zero (and hence strictly greater than 0), that is, $~(\alpha-\alpha’).(\beta-\beta’) > 0 $. Rewriting this we get $\alpha.\beta > \alpha’.\beta+\alpha.\beta’-\alpha’.\beta’ $ and again the ‘simplicity rule’ asserts that $\alpha.\beta $ should be the least ordinal satisfying all these inequalities, leading to the $\mathbf{mex} $-definition above. The table gives the beginning of the nim-multiplication table for ordinals. For finite ordinals n and m there is a simple 2 line procedure to compute their nim-product, similar to the addition-rules mentioned before :

the nim-product of a number of distinct Fermat 2-powers (that is, numbers of the form $2^{2^n} $) is their ordinary product (for example, $16.4.2=128 $), and,
the square of a Fermat 2-power is its sesquimultiple (that is, the number obtained by multiplying with $1\frac{1}{2} $ in the ordinary sense). That is, $2^2=3,4^2=6,16^2=24,… $

Using these rules, associativity and distributivity and our addition rules it is now easy to work out the nim-multiplication $n.m $ : write out n and m as sums of (multiplications by 2-powers) of Fermat 2-powers and apply the rules. Here’s an example

$5.9=(4+1).(4.2+1)=4^2.2+4.2+4+1=6.2+8+4+1=(4+2).2+13=4.2+2^2+13=8+3+13=6 $

Clearly, we’d love to have a similar procedure to calculate the nim-product $\alpha.\beta $ of arbitrary ordinals, or at least those smaller than $\omega^{\omega^{\omega}} $ (recall that Conway proved that this ordinal is isomorphic to the algebraic closure $\overline{\mathbb{F}}_2 $ of the field of two elements). From now on we restrict to such ‘small’ ordinals and we introduce the following special elements :

$\kappa_{2^n} = [2^{2^{n-1}}] $ (these are the Fermat 2-powers) and for all primes $p > 2 $ we define
$\kappa_{p^n} = [\omega^{\omega^{k-1}.p^{n-1}}] $ where $k $ is the number of primes strictly smaller than $p $ (that is, for p=3 we have k=1, for p=5, k=2 etc.).

Again by associativity and distributivity we will be able to multiply two ordinals $< \omega^{\omega^{\omega}} $ if we know how to multiply a product

$[\omega^{\alpha}.2^{n_0}].[\omega^{\beta}.2^{m_0}] $ with $\alpha,\beta < [\omega^{\omega}] $ and $n_0,m_0 \in \mathbb{N} $.

Now, $\alpha $ can be written uniquely as $[\omega^t.n_t+\omega^{t-1}.n_{t-1}+\ldots+\omega.n_2 + n_1] $ with t and all $n_i $ natural numbers. Write each $n_k $ in base $p $ where $p $ is the $k+1 $-th prime number, that is, we have for $n_0,n_1,\ldots,n_t $ an expression

$n_k=[\sum_j p^j.m(j,k)] $ with $0 \leq m(j,k) < p $

The point of all this is that any of the special elements we want to multiply can be written as a unique expression as a decreasing product

$[\omega^{\alpha}.2^{n_0}] = [ \prod_q \kappa_q^m(q) ] $

where $q $ runs over all prime powers. The crucial fact now is that for this decreasing product we have a rule similar to addition of 2-powers, that is Conway-products coincide with the Cantor-products

$[ \prod_q \kappa_q^m(q) ] = \prod_q \kappa_q^m(q) $

But then, using associativity and commutativity of the Conway-product we can ‘nearly’ describe all products $[\omega^{\alpha}.2^{n_0}].[\omega^{\beta}.2^{m_0}] $. The remaining problem being that it may happen that for some q we will end up with an exponent $m(q)+m(q’)>p $. But this can be solved if we know how to take p-powers. The rules for this are as follows

$~(\kappa_{2^n})^2 = \kappa_{2^n} + \prod_{1 \leq i < n} \kappa_{2^i} $, for 2-powers, and,

$~(\kappa_{p^n})^p = \kappa_{p^{n-1}} $ for a prime $p > 2 $ and for $n \geq 2 $, and finally

$~(\kappa_p)^p = \alpha_p $ for a prime $p > 2 $, where $\alpha_p $ is the smallest ordinal $< \kappa_p $ which cannot be written as a p-power $\beta^p $ with $\beta < \kappa_p $. Summarizing : if we will be able to find these mysterious elements $\alpha_p $ for all prime numbers p, we are able to multiply in $[\omega^{\omega^{\omega}}]=\overline{\mathbb{F}}_2 $.

Let us determine the first one. We have that $\kappa_3 = \omega $ so we are looking for the smallest natural number $n < \omega $ which cannot be written in num-multiplication as $n=m^3 $ for $m < \omega $ (that is, also $m $ a natural number). Clearly $1=1^3 $ but what about 2? Can 2 be a third root of a natural number wrt. nim-multiplication? From the tabel above we see that 2 has order 3 whence its cube root must be an element of order 9. Now, the only finite ordinals that are subfields of $\mathbf{On}_2 $ are precisely the Fermat 2-powers, so if there is a finite cube root of 2, it must be contained in one of the finite fields $[2^{2^n}] $ (of which the mutiplicative group has order $2^{2^n}-1 $ and one easily shows that 9 cannot be a divisor of any of the numbers $2^{2^n}-1 $, that is, 2 doesn’t have a finte 3-th root in nim! Phrased differently, we found our first mystery number $\alpha_3 = 2 $. That is, we have the marvelous identity in nim-arithmetic

$\omega^3 = 2 $

Okay, so what is $\alpha_5 $? Well, we have $\kappa_5 = [\omega^{\omega}] $ and we have to look for the smallest ordinal which cannot be written as a 5-th root. By inspection of the finite nim-table we see that 1,2 and 3 have 5-th roots in $\omega $ but 4 does not! The reason being that 4 has order 15 (check in the finite field [16]) and 25 cannot divide any number of the form $2^{2^n}-1 $. That is, $\alpha_5=4 $ giving another crazy nim-identity

$~(\omega^{\omega})^5 = 4 $

And, surprises continue to pop up… Conway showed that $\alpha_7 = \omega+1 $ giving the nim-identity $~(\omega^{\omega^2})^7 = \omega+1 $. The proof of this already uses some clever finite field arguments. Because 7 doesn’t divide any number $2^{2^n}-1 $, none of the finite subfields $[2^{2^n}] $ contains a 7-th root of unity, so the 7-power map is injective whence surjective, so all finite ordinal have finite 7-th roots! That is, $\alpha_7 \geq \omega $. Because $\omega $ lies in a cubic extension of the finite field [4], the field generated by $\omega $ has 64 elements and so its multiplicative group is cyclic of order 63 and as $\omega $ has order 9, it must be a 7-th power in this field. But, as the only 7th powers in that field are precisely the powers of $\omega $ and by inspection $\omega+1 $ is not a 7-th power in that field (and hence also not in any field extension obtained by adjoining square, cube and fifth roots) so $\alpha_7=\omega +1 $.

Conway did stop at $\alpha_7 $ but I’ve always been intrigued by that one line in ONAG p.61 : “Hendrik Lenstra has computed $\alpha_p $ for $p \leq 43 $”. Next time we will see how Lenstra managed to do this and we will use sage to extend his list a bit further, including the first open case : $\alpha_{47}= \omega^{\omega^7}+1 $.

For an enjoyable video on all of this, see Conway’s MSRI lecture on Infinite Games. The nim-arithmetic part is towards the end of the lecture but watching the whole video is a genuine treat!

Leave a Comment

On2 : transfinite number hacking

Published January 8, 2009 by lievenlb

In ONAG, John Conway proves that the symmetric version of his recursive definition of addition and multiplcation on the surreal numbers make the class On of all Cantor’s ordinal numbers into an algebraically closed Field of characteristic two : On2 (pronounced ‘Onto’), and, in particular, he identifies a subfield
with the algebraic closure of the field of two elements. What makes all of this somewhat confusing is that Cantor had already defined a (badly behaving) addition, multiplication and exponentiation on ordinal numbers.

Over the last week I’ve been playing a bit with sage to prove a few exotic identities involving ordinal numbers. Here’s one of them ($\omega $ is the first infinite ordinal number, that is, $\omega={ 0,1,2,\ldots } $),

$~(\omega^{\omega^{13}})^{47} = \omega^{\omega^7} + 1 $

answering a question in Hendrik Lenstra’s paper Nim multiplication.

However, it will take us a couple of posts before we get there. Let’s begin by trying to explain what brought this on. On september 24th 2008 there was a meeting, intended for a general public, called a la rencontre des dechiffeurs, celebrating the 50th birthday of the IHES.

One of the speakers was Alain Connes and the official title of his talk was “L’ange de la géométrie, le diable de l’algèbre et le corps à un élément” (the angel of geometry, the devil of algebra and the field with one element). Instead, he talked about a seemingly trivial problem : what is the algebraic closure of $\mathbb{F}_2 $, the field with two elements? My only information about the actual content of the talk comes from the following YouTube-blurb

Alain argues that we do not have a satisfactory description of $\overline{\mathbb{F}}_2 $, the algebraic closure of $\mathbb{F}_2 $. Naturally, it is the union (or rather, limit) of all finite fields $\mathbb{F}_{2^n} $, but, there are too many non-canonical choices to make here.

Recall that $\mathbb{F}_{2^k} $ is a subfield of $\mathbb{F}_{2^l} $ if and only if $k $ is a divisor of $l $ and so we would have to take the direct limit over the integers with respect to the divisibility relation… Of course, we can replace this by an increasing sequence of a selection of cofinal fields such as

$\mathbb{F}_{2^{1!}} \subset \mathbb{F}_{2^{2!}} \subset \mathbb{F}_{2^{3!}} \subset \ldots $

But then, there are several such suitable sequences! Another ambiguity comes from the description of $\mathbb{F}_{2^n} $. Clearly it is of the form $\mathbb{F}_2[x]/(f(x)) $ where $f(x) $ is a monic irreducible polynomial of degree $n $, but again, there are several such polynomials. An attempt to make a canonical choice of polynomial is to take the ‘first’ suitable one with respect to some natural ordering on the polynomials. This leads to the so called Conway polynomials.

Conway polynomials for the prime $2 $ have only been determined up to degree 400-something, so in the increasing sequence above we would already be stuck at the sixth term $\mathbb{F}_{2^{6!}} $…

So, what Alain Connes sets as a problem is to find another, more canonical, description of $\overline{\mathbb{F}}_2 $. The problem is not without real-life interest as most finite fields appearing in cryptography or coding theory are subfields of $\overline{\mathbb{F}}_2 $.

(My guess is that Alain originally wanted to talk about the action of the Galois group on the roots of unity, which would be the corresponding problem over the field with one element and would explain the title of the talk, but decided against it. If anyone knows what ‘coupling-problem’ he is referring to, please drop a comment.)

Surely, Connes is aware of the fact that there exists a nice canonical recursive construction of $\overline{\mathbb{F}}_2 $ due to John Conway, using Georg Cantor’s ordinal numbers.

In fact, in chapter 6 of his book On Numbers And Games, John Conway proves that the symmetric version of his recursive definition of addition and multiplcation on the surreal numbers make the class $\mathbf{On} $ of all Cantor’s ordinal numbers into an algebraically closed Field of characteristic two : $\mathbf{On}_2 $ (pronounced ‘Onto’), and, in particular, he identifies a subfield

$\overline{\mathbb{F}}_2 \simeq [ \omega^{\omega^{\omega}} ] $

with the algebraic closure of $\mathbb{F}_2 $. What makes all of this somewhat confusing is that Cantor had already defined a (badly behaving) addition, multiplication and exponentiation on ordinal numbers. To distinguish between the Cantor/Conway arithmetics, Conway (and later Lenstra) adopt the convention that any expression between square brackets refers to Cantor-arithmetic and un-squared ones to Conway’s. So, in the description of the algebraic closure just given $[ \omega^{\omega^{\omega}} ] $ is the ordinal defined by Cantor-exponentiation, whereas the exotic identity we started out with refers to Conway’s arithmetic on ordinal numbers.

Let’s recall briefly Cantor’s ordinal arithmetic. An ordinal number $\alpha $ is the order-type of a totally ordered set, that is, if there is an order preserving bijection between two totally ordered sets then they have the same ordinal number (or you might view $\alpha $ itself as a totally ordered set, namely the set of all strictly smaller ordinal numbers, so e.g. $0= \emptyset,1= { 0 },2={ 0,1 },\ldots $).

For two ordinals $\alpha $ and $\beta $, the addition $[\alpha + \beta ] $ is the order-type of the totally ordered set $\alpha \sqcup \beta $ (the disjoint union) ordered compatible with the total orders in $\alpha $ and $\beta $ and such that every element of $\beta $ is strictly greater than any element from $\alpha $. Observe that this definition depends on the order of the two factors. For example,$ [1 + \omega] = \omega $ as there is an order preserving bijection ${ \tilde{0},0,1,2,\ldots } \rightarrow { 0,1,2,3,\ldots } $ by $\tilde{0} \mapsto 0,n \mapsto n+1 $. However, $\omega \not= [\omega + 1] $ as there can be no order preserving bijection ${ 0,1,2,\ldots } \rightarrow { 0,1,2,\ldots,0_{max} } $ as the first set has no maximal element whereas the second one does. So, Cantor’s addition has the bad property that it may be that $[\alpha + \beta] \not= [\beta + \alpha] $.

The Cantor-multiplication $ \alpha . \beta $ is the order-type of the product-set $\alpha \times \beta $ ordered via the last differing coordinate. Again, this product has the bad property that it may happen that $[\alpha . \beta] \not= [\beta . \alpha] $ (for example $[2 . \omega ] \not=[ \omega . 2 ] $). Finally, the exponential $\beta^{\alpha} $ is the order type of the set of all maps $f~:~\alpha \rightarrow \beta $ such that $f(a) \not=0 $ for only finitely many $a \in \alpha $, and ordered via the last differing function-value.

Cantor’s arithmetic allows normal-forms for ordinal numbers. More precisely, with respect to any ordinal number $\gamma \geq 2 $, every ordinal number $\alpha \geq 1 $ has a unique expression as

$\alpha = [ \gamma^{\alpha_0}.\eta_0 + \gamma^{\alpha_1}.\eta_1 + \ldots + \gamma^{\alpha_m}.\eta_m] $

for some natural number $m $ and such that $\alpha \geq \alpha_0 > \alpha_1 > \ldots > \alpha_m \geq 0 $ and all $1 \leq \eta_i < \gamma $. In particular, taking the special cases $\gamma = 2 $ and $\gamma = \omega $, we have the following two canonical forms for any ordinal number $\alpha $

$[ 2^{\alpha_0} + 2^{\alpha_1} + \ldots + 2^{\alpha_m}] = \alpha = [ \omega^{\beta_0}.n_0 + \omega^{\beta_1}.n_1 + \ldots + \omega^{\beta_k}.n_k] $

with $m,k,n_i $ natural numbers and $\alpha \geq \alpha_0 > \alpha_1 > \ldots > \alpha_m \geq 0 $ and $\alpha \geq \beta_0 > \beta_1 > \ldots > \beta_k \geq 0 $. Both canonical forms will be important when we consider the (better behaved) Conway-arithmetic on $\mathbf{On}_2 $, next time.

One Comment

sporadic simple games

Published July 13, 2008 by lievenlb

About a year ago I did a series of posts on games associated to the Mathieu sporadic group $M_{12} $, starting with a post on Conway’s puzzle M(13), and, continuing with a discussion of mathematical blackjack. The idea at the time was to write a book for a general audience, as discussed at the start of the M(13)-post, ending with a series of new challenging mathematical games. I asked : “What kind of puzzles should we promote for mathematical thinking to have a fighting chance to survive in the near future?”

Now, Scientific American has (no doubt independently) taken up this lead. Their July 2008 issue features the article Rubik’s Cube Inspired Puzzles Demonstrate Math’s “Simple Groups” written by Igor Kriz and Paul Siegel.

By far the nicest thing about this article is that it comes with three online games based on the sporadic simple groups, the Mathieu groups $M_{12} $, $M_{24} $ and the Conway group $.0 $.

the M(12) game

Scrambles to an arbitrary permutation in $M_{12} $ and need to use the two generators $INVERT=(1,12)(2,11)(3,10)(4,9)(5,8)(6,7) $ and $MERGE=(2,12,7,4,11,6,10,8,9,5,3) $ to return to starting position.

Here is the help-screen :

They promise the solution by july 27th, but a few-line GAP-program cracks the puzzle instantly.

the M(24) game

Similar in nature, again using two generators of $M_{24} $. GAP-solution as before.

This time, they offer this help-screen :

the .0 game

Their most original game is based on Conway’s $.0 $ (dotto) group. Unfortunately, they offer only a Windows-executable version, so I had to install Bootcamp and struggle a bit with taking screenshots on a MacBook to show you the game’s starting position :

Dotto:

Dotto, our final puzzle, represents the Conway group Co0, published in 1968 by mathematician John H. Conway of Princeton University. Co0 contains the sporadic simple group Co1 and has exactly twice as many members as Co1. Conway is too modest to name Co0 after himself, so he denotes the group “.0” (hence the pronunciation “dotto”).

In Dotto, there are four moves. This puzzle includes the M24 puzzle. Look at the yellow/blue row in the bottom. This is, in fact, M24, but the numbers are arranged in a row instead of a circle. The R move is the “circle rotation to the right”: the column above the number 0 stays put, but the column above the number 1 moves to the column over the number 2 etc. up to the column over the number 23, which moves to the column over the number 1. You may also click on a column number and then on another column number in the bottom row, and the “circle rotation” moving the first column to the second occurs. The M move is the switch, in each group of 4 columns separated by vertical lines (called tetrads) the “yellow” columns switch and the “blue” columns switch. The sign change move (S) changes signs of the first 8 columns (first two tetrads). The tetrad move (T) is the most complicated: Subtract in each row from each tetrad 1/2 times the sum of the numbers in that tetrad. Then in addition to that, reverse the signs of the columns in the first tetrad.

Strategy hints: Notice that the sum of squares of the numbers in each row doesn’t change. (This sum of squares is 64 in the first row, 32 in every other row.) If you manage to get an “8”in the first row, you have almost reduced the game to M24 except those signs. To have the original position, signs of all numbers on the diagonal must be +. Hint on signs: if the only thing wrong are signs on the diagonal, and only 8 signs are wrong, those 8 columns can be moved to the first 8 columns by using only the M24 moves (M,R).

Leave a Comment

Surreal numbers & chess

Published April 8, 2008 by lievenlb

Most chess programs are able to give a numerical evaluation of a position. For example, the position below is considered to be worth +8.7 with white to move, and, -0.7 with black to move (by a certain program). But, if one applies combinatorial game theory as in John Conway’s ONAG and the Berlekamp-Conway-Guy masterpiece Winning Ways for your Mathematical Plays it will turn out that the position can be proved to have an infinitesimal advantage for white…

So, what do we mean by this? First some basic rules of combinatorial game theory. To start, we evaluate a position without knowing which player has the move. A zero-game is by definition a position in which neither player has a good move, that is, any move by either player quickly leads to losing the game. Hence, a zero-game is a position in which the second player to move wins.

What is the chess-equivalent of a zero-position game? A position in which neither player has a good move is called a Mutual Zugzwang in chess literature. An example is given by the above position, if we restrict attention only to the 4 pieces in the upper right-hand corner and forget the rest. We don’t know who has the move, but, White cannot move at all and Black cannot move the King or Bishop without losing the Bishop and allowing White to promote the pawn and win quickly. In CGT-parlance, the upper-right position has value $\{ \emptyset | \emptyset \} = 0 $ where the left options denote the White moves and the right options the Black moves.

All other values are determined by recursion. For example, consider a position in which White has just one move left before the sitution is again a Mutual Zugzwang, and, Black has no good move whatsoever. After white’s move, the position will again be a zero-position and Black has no options, so the value of this position would be denoted by $\{ 0 | \emptyset \} $ and we call the value of this position to be $+1 $. Similarly, if white has no options and black has one final move to make, the position would be considered to have value $\{ \emptyset | 0 \}= -1 $.

Clearly, these are just the three easiest game-values to have and the real kick comes further down the road when one can prove by recursion that some games have non-integer values (such as $\{ 0 | 1 \} = \frac{1}{2} $ for a position in which white has one move to get to a mutual zugzwang and black has a move leading to a position of value $+1 $ (defined as before)), or non-number values such as $\ast = \{ 0 | 0 \} $ where both white and black’s best move is to get to a mutal zugzwang. Game-values such as $\ast $ are called fuzzy (or confused with zero) and are defined by the property that the first player to move wins.

Similarly, positive game-values are those positions where White wins, independent of who has the move and negatives are those that Black wins. There is a whole menagery of game-values and the WinningWays-booklets give an example based introduction to this fascinating theory.

Brief as this introduction was, it will allow us to determine the exact value of the position in the above diagram. We know already that we can forget about the right-hand upper corner (as this is a zero-position) and concentrate attention to the left-hand side of the board.

It is easy to see that neither Knight can move without loosing quickly, nor can the pawns on a5 and b7. That is, white has just 2 options : either c3-c4 (quickly loosing after d5xc4 2. d3xc4,d4-d3 3. Nc1xd3,Na1-b3) or, and this is the only valid option c3xd4 leading to the position on the left below. Black has only one valid move : d4xc3 leading to the position on the right below.

Clearly, the left-diagram has value 0 as it is a mutual Zugzwang. The position on the right takes a moment’s thought : White has one move left d3-d4 leading to a 0-position, whereas black has one move d5-d4 leading to a position of value -1 (as black still has one move left d6-d5, whereas white has none). That is, the CGT-value of the right-hand position is $\{ 0 | -1 \} $ and therefore, the value of the starting position is precisely equal to

\[ \{ 0 | \{ 0 | -1 \} \} = +_{1} \]

(called tiny-one among ONAGers)

It can be shown that $+_1 $ has a positive value (that is, White wins independently of who has the first move) but smaller than any positive number-valued games!

Noam Elkies has written a beautiful paper On numbers and endgames: Combinatorial game theory in chess endgames containing many interesting examples (the example above is an adaptation of his diagram9).

2 Comments