Skip to content →

Tag: games

A question of loyalty

On the island of two truths, statements are either false (truth-value $0$), Q-true (value $Q$) or K-true (value $K$).

The King and Queen of the island have an opinion on all statements which may differ from their actual truth-value. We say that the Queen believes a statement $p$ is she assigns value $Q$ to it, and that she knows $p$ is she believes $p$ and the actual truth-value of $p$ is indeed $Q$. Similarly for the King, replacing $Q$’s by $K$’s.

All other inhabitants of the island are loyal to the Queen, or to the King, or to both. This means that they agree with the Queen (or King, or both) on all statements they have an opinion on. Two inhabitants are said to be loyal to each other if they agree on all statements they both have an opinion of.

Last time we saw that Queen and King agree on all statements one of them believes to be false, as well as the negation of such statements. This raised the question:

Are the King and Queen loyal to each other? That is, do Queen and King agree on all statements?

We cannot resolve this issue without the information Oscar was able to extract from Pointex in Karin Cvetko-Vah‘s post Pointex:

“Oscar was determined to get some more information. “Could you at least tell me whether the queen and the king know that they’re loyal to themselves?” he asked.
“Well, of course they know that!” replied Pointex.
“You said that a proposition can be Q-TRUE, K-TRUE or FALSE,” Oscar said.
“Yes, of course. What else!” replied Pointex as he threw the cap high up.
“Well, you also said that each native was loyal either to the queen or to the king. I was just wondering … Assume that A is loyal to the queen. Then what is the truth value of the statement: A is loyal to the queen?”
“Q, of course,” answered Pointex as he threw the cap up again.
“And what if A is not loyal to the queen? What is then the truth value of the statement: A is loyal to the queen?”
He barely finished his question as something fell over his face and covered his eyes. It was the funny cap.
“Thanx,” said Pointex as Oscar handed him the cap. “The value is 0, of course.”
“Can the truth value of the statement: ‘A is loyal to the queen’ be K in any case?”
“Well, what do you think? Of course not! What a ridiculous thing to ask!” replied Pointex.”

Puzzle : Show that Queen and King are not loyal to each other, that is, there are statements on which they do not agree.



Solution : ‘The King is loyal to the Queen’ must have actual truth-value $0$ or $Q$, and the sentence ‘The Queen is loyal to the King’ must have actual truth-value $0$ or $K$. But both these sentences are the same as the sentence ‘The Queen and King are loyal to each other’ and as this sentence can have only one truth-value, it must have value $0$ so the statement is false.

Note that we didn’t produce a specific statement on which the Queen and King disagree. Can you find one?

Leave a Comment

the strange island of two truths

Last time we had a brief encounter with the island of two truths, invented by Karin Cvetko-Vah. See her posts:

On this island, false statements have truth-value $0$ (as usual), but non-false statements are not necessarily true, but can be given either truth-value $Q$ (statements which the Queen on the island prefers) or $K$ (preferred by the King).

Think of the island as Trump’s paradise where nobody is ever able to say: “Look, alternative truths are not truths. They’re falsehoods.”



Even the presence of just one ‘alternative truth’ has dramatic consequences on the rationality of your reasoning. If we know the truth-values of specific sentences, we can determine the truth-value of more complex sentences in which we use logical connectives such as $\vee$ (or), $\wedge$ (and), $\neg$ (not), and $\implies$ (then) via these truth tables:

\[
\begin{array}{c|ccc}
\downarrow~\bf{\wedge}~\rightarrow & 0 & Q & K \\
\hline
0 & 0 & 0 & 0 \\
Q & 0 & Q & Q \\
K & 0 & K & K
\end{array} \quad
\begin{array}{c|ccc}
\downarrow~\vee~\rightarrow & 0 & Q & K \\
\hline
0 & 0 & Q & K \\
Q & Q & Q & K \\
K & K & Q & K
\end{array} \]
\[
\begin{array}{c|ccc}
\downarrow~\implies~\rightarrow & 0 & Q & K \\
\hline
0 & Q & Q & K \\
Q & 0 & Q & K \\
K & 0 & Q & K
\end{array} \quad
\begin{array}{c|c}
\downarrow & \neg~\downarrow \\
\hline
0 & Q \\
Q & 0 \\
K & 0
\end{array}
\]

Note that the truth-values $Q$ and $K$ are not completely on equal footing as we have to make a choice which one of them will stand for $\neg 0$.

Common tautologies are no longer valid on this island. The best we can have are $Q$-tautologies (giving value $Q$ whatever the values of the components) or $K$-tautologies.

Here’s one $Q$-tautology (check!) : $(\neg p) \vee (\neg \neg p)$. Verify that $p \vee (\neg p)$ is neither a $Q$- nor a $K$-tautology.

Can you find any $K$-tautology at all?

Already this makes it incredibly difficult to adapt Smullyan-like Knights and Knaves puzzles to this skewed island. Last time I gave one easy example.



Puzzle : On an island of two truths all inhabitants are either Knaves (saying only false statements), Q-Knights (saying only $Q$-valued statements) or K-Knights (who only say $K$-valued statements).

The King came across three inhabitants, whom we will call $A$, $B$ and $C$. He asked $A$: “Are you one of my Knights?” $A$ answered, but so indistinctly that the King could not understand what he said.

He then asked $B$: “What did he say?” $B$ replies: “He said that he is a Knave.” At this point, $C$ piped up and said: “That’s not true!”

Was $C$ a Knave, a Q-Knight or a K-Knight?

Solution : Q- and K-Knights can never claim to be a Knave. Neither can Knaves because they can only say false statements. So, no inhabitant on the island can ever claim to be a Knave. So, $B$ lies and is a Knave, so his stament has truth-value $0$. $C$ claims the negation of what $B$ says so the truth-value of his statement is $\neg 0 = Q$. $C$ must be a Q-Knight.

As if this were not difficult enough, Karin likes to complicate things by letting the Queen and King assign their own truth-values to all sentences, which may coincide with their actual truth-value or not.

Clearly, these two truth-assignments follow the logic of the island of two truths for composed sentences, and we impose one additional rule: if the Queen assigns value $0$ to a statement, then so does the King, and vice versa.

I guess she wanted to set the stage for variations to the island of two truths of epistemic modal logical puzzles as in Smullyan’s book Forever Undecided (for a quick summary, have a look at Smullyan’s paper Logicians who reason about themselves).

A possible interpretation of the Queen’s truth-assignment is that she assigns value $Q$ to all statements she believes to be true, value $0$ to all statements she believes to be false, and value $K$ to all statements she has no fixed opinion on (she neither believes them to be true nor false). The King assigns value $K$ to all statements he believes to be true, $0$ to those he believes to be false, and $Q$ to those he has no fixed opinion on.

For example, if the Queen has no fixed opinion on $p$ (so she assigns value $K$ to it), then the King can either believe $p$ (if he also assigns value $K$ to it) or can have no fixed opinion on $p$ (if he assigns value $Q$ to it), but he can never believe $p$ to be false.



Puzzle : We say that Queen and King ‘agree’ on a statement $p$ if they both assign the same value to it. So, they agree on all statements one of them (and hence both) believe to be false. But there’s more:

  • Show that Queen and King agree on the negation of all statements one of them believes to be false.
  • Show that the King never believes the negation of whatever statement.
  • Show that the Queen believes all negations of statements the King believes to be false.

Solution : If one of them believes $p$ to be false (s)he will assign value $0$ to $p$ (and so does the other), but then they both have to assign value $Q$ to $\neg p$, so they agree on this.

The value of $\neg p$ can never be $K$, so the King does not believe $\neg p$.

If the King believes $p$ to be false he assigns value $0$ to it, and so does the Queen, but then the value of $\neg p$ is $Q$ and so the Queen believes $\neg p$.

We see that the Queen and King agree on a lot of statements, they agree on all statements one of them believes to be false, and they agree on the negation of such statements!

Can you find any statement at all on which they do not agree?

Well, that may be a little bit premature. We didn’t say which sentences about the island are allowed, and what the connection (if any) is between the Queen and King’s value-assignments and the actual truth values.

For example, the Queen and King may agree on a classical ($0$ or $1$) truth-assignments to the atomic sentences for the island, and replace all $1$’s with $Q$. This will give a consistent assignment of truth-values, compatible with the island’s strange logic. (We cannot do the same trick replacing $1$’s by $K$ because $\neg 0 = Q$).

Clearly, such a system may have no relation at all with the intended meaning of these sentences on the island (the actual truth-values).

That’s why Karin Cvetko-Vah introduced the notions of ‘loyalty’ and ‘sanity’ for inhabitants of the island. That’s for next time, and perhaps then you’ll be able to answer the question whether Queen and King agree on all statements.

(all images in this post are from Smullyan’s book Alice in Puzzle-Land)

Leave a Comment

some skew Smullyan stumpers

Raymond Smullyan‘s logic puzzles are legendary. Among his best known are his Knights (who always tell the truth) and Knaves (who always lie) puzzles. Here’s a classic example.

“On the day of his arrival, the anthropologist Edgar Abercrombie came across three inhabitants, whom we will call $A$, $B$ and $C$. He asked $A$: “Are you a Knight or a Knave?” $A$ answered, but so indistinctly that Abercrombie could not understand what he said.

He then asked $B$: “What did he say?” $B$ replies: “He said that he is a knave.” At this point, $C$ piped up and said: “Don’t believe that; it’s a lie!”

Was $C$ a Knight or a Knave?”

If you are stumped by this, try to figure out what kind of inhabitant can say “I am a Knave”.

Some years ago, my friend and co-author Karin Cvetko-Vah wrote about a much stranger island, the island of two truths.

“The island was ruled by a queen and a king. It is important to stress that the queen was neither inferior nor superior to the king. Rather than as a married couple one should think of the queen and the king as two parallel powers, somewhat like the Queen of the Night and the King Sarastro in Mozart’s famous opera The Magic Flute. The queen and the king had their own castle each, each of them had their own court, their own advisers and servants, and most importantly each of them even had their own truth value.

On the island, a proposition p is either FALSE, Q-TRUE or K-TRUE; in each of the cases we say that p has value 0, Q or K, respectively. The queen finds the truth value Q to be superior, while the king values the most the value K. The queen and the king have their opinions on all issues, while other residents typically have their opinions on some issues but not all.”

The logic of the island of two truths is the easiest example of what Karin and I called a non-commutative frame or skew Heyting algebra (see here), a notion we then used, jointly with Jens Hemelaer, to define the notion of a non-commutative topos.

If you take our general definitions, and take Q as the distinguished top-element, then the truth tables for the island of two truths are these ones (value of first term on the left, that of the second on top):

\[
\begin{array}{c|ccc}
\wedge & 0 & Q & K \\
\hline
0 & 0 & 0 & 0 \\
Q & 0 & Q & Q \\
K & 0 & K & K
\end{array} \quad
\begin{array}{c|ccc}
\vee & 0 & Q & K \\
\hline
0 & 0 & Q & K \\
Q & Q & Q & K \\
K & K & Q & K
\end{array} \quad
\begin{array}{c|ccc}
\rightarrow & 0 & Q & K \\
\hline
0 & Q & Q & K \\
Q & 0 & Q & K \\
K & 0 & Q & K
\end{array} \quad
\begin{array}{c|c}
& \neg \\
\hline
0 & Q \\
Q & 0 \\
K & 0
\end{array}
\]

Note that on this island the order of statements is important! That is, the truth value of $p \wedge q$ may differ from that of $q \wedge p$ (and similarly for $\vee$).

Let’s reconsider Smullyan’s puzzle at the beginning of this post, but now on an island of two truths, where every inhabitant is either of Knave, or a Q-Knight (uttering only Q-valued statements), or a K-Knight (saying only K-valued statements).

Again, can you determine what type $C$ is?

Well, if you forget about the distinction between Q- and K-valued sentences, then we’re back to classical logic (or more generally, if you divide out Green’s equivalence relation from any skew Heyting algebra you obtain an ordinary Heyting algebra), and we have seen that then $B$ must be a Knave and $C$ a Knight, so in our new setting we know that $C$ is either a Q-Knight or a K-Knight, but which of the two?

Now, $C$ claims the negation of what $B$ said, so the truth value is $\neg 0 = Q$, and therefore $C$ must be a Q-Knight.

Recall that in Karin Cvetko-Vah‘s island of two truths all sentences have a unique value which can be either $0$ (false) or one of the non-false values Q or K, and the value of combined statements is given by the truth tables above. The Queen and King both have an opinion on all statements, which may or may not coincide with the actual value of that statement. However, if the Queen assigns value $0$ to a statement, then so does the King, and conversely.

Other inhabitants of the island have only their opinion about a subset of all statements (which may be empty). Two inhabitants agree on a statement if they both have an opinion on it and assign the same value to it.

Now, each inhabitant is either loyal to the Queen or to the King (or both), meaning that they agree with the Queen (resp. King) on all statements they have an opinion of. An inhabitant loyal to the Queen is said to believe a sentence when she assigns value $Q$ to it (and symmetric for those loyal to the King), and knows the statement if she believes it and that value coincides with the actual value of that statement.

Further, if A is loyal to the Queen, then the value of the statement ‘A is loyal to the Queen’ is Q, and if A is not loyal to the Queen, then the value of the sentence ‘A is loyal to the Queen’ is $0$ (and similarly for statements about loyalty to the King).

These notions are enough for the first batch of ten puzzles in Karin’s posts

Just one example:

Show that if anybody on the island knows that A is not loyal to the Queen, then everybody that has an opinion about the sentence ‘A is loyal to the Queen’ knows that.

After these two posts, Karin decided that it was more fun to blog about the use of non-commutative frames in data analysis.

But, she once gave me a text containing many more puzzles (as well as all the answers), so perhaps I’ll share these in a follow-up post.

Leave a Comment

A suit with shorts

I’m retiring in two weeks so I’m cleaning out my office.

So far, I got rid of almost all paper-work and have split my book-collection in two: the books I want to take with me, and those anyone can grab away.

Here’s the second batch (math/computer books in the middle, popular science to the right, thrillers to the left).



If you’re interested in some of these books (click for a larger image, if you want to zoom in) and are willing to pay the postage, leave a comment and I’ll try to send them if they survive the current ‘take-away’ phase.

Here are two books I definitely want to keep. On the left, an original mimeographed version of Mumford’s ‘Red Book’.

On the right, ‘Een pak met een korte broek’ (‘A suit with shorts’), a collection of papers by family and friends, presented to Hendrik Lenstra on the occasion of the defence of his Ph.D. thesis on Euclidean number-fields, May 18th 1977.

If the title intrigues you, a photo of young Hendrik in suit and shorts is included.

This collection includes hilarious ‘papers’ by famous people including

  • ‘A headache-causing problem’ by Conway (J.H.), Paterson (M.S.), and Moscow (U.S.S.R.)
  • ‘A projective plain of order ten’ by A.M. Odlyzko and N.J.A. Sloane
  • ‘La chasse aux anneaux principaux non-Euclidiens dans l’enseignement’ by Pierre Samuel
  • ‘On time-like theorems’ by Michiel Hazewinkel
  • ‘She loves me, she loves me not’ by Richard K. Guy
  • ‘Theta invariants for affine root systems’ by E.J.N. Looijenga
  • ‘The prime of primes’ by F. Lenstra and A.J. Oort
  • (and many more, most of them in Dutch)

Perhaps I can do a couple of posts on some of these papers. It might break this clean-up routine.

One Comment

the L-game

In 1982, the BBC ran a series of 10 weekly programmes entitled de Bono’s Thinking Course. In the book accompanying the series Edward de Bono recalls the origin of his ‘L-Game’:



Many years ago I was sitting next to the famous mathematician, Professor Littlewood, at dinner in Trinity College. We were talking about getting computers to play chess. We agreed that chess was difficult because of the large number of pieces and different moves. It seemed an interesting challenge to design a game that was as simple as possible and yet could be played with a degree of skill.

As a result of that challenge I designed the ‘L-Game’, in which each player has only one piece (the L-shape piece). In turn he moves this to any new vacant position (lifting up, turning over, moving across the board to a vacant position, etc.). After moving his L-piece he can – if he wishes – move either one of the small neutral pieces to any new position. The object of the game is to block your opponent’s L-shape so that no move is open to it.

It is a pleasant exercise in symmetry to calculate the number of possible L-game positions.

The $4 \times 4$ grid has $8$ symmetries, making up the dihedral group $D_8$: $4$ rotations and $4$ reflections.

An L-piece breaks all these symmetries, that is, it changes in form under each of these eight operations. That is, using the symmetries of the $4 \times 4$-grid we can put one of the L-pieces (say the Red one) on the grid as a genuine L, and there are exactly 6 possibilities to do so.

For each of these six positions one can then determine the number of possible placings of the Blue L-piece. This is best done separately for each of the 8 different shapes of that L-piece.

Here are the numbers when the red L is placed in the left bottom corner:



In total there are thus 24 possibilities to place the Blue L-piece in that case. We can repeat the same procedure for the remaining Red L-positions. Here are the number of possibilities for Blue in each case:



That is, there are 82 possibilities to place the two L-pieces if the Red one stands as a genuine L on the board.

But then, the L-game has exactly $18368 = 8 \times 82 \times 28$ different positions, where the factor

  • $8$ gives the number of symmetries of the square $4 \times 4$ grid.
  • Using these symmetries we can put the Red L-piece on the grid as a genuine $L$ and we just saw that this leaves $82$ possibilities for the Blue L-piece.
  • This leaves $8$ empty squares and so $28 = \binom{8}{2}$ different choices to place the remaining two neutral pieces.

The $2296 = 82 \times 28$ positions in which the red L-piece is placed as a genuine L can then be analysed by computer and the outcome is summarised in Winning Ways 2 pages 384-386 (with extras on pages 408-409).

Of the $2296$ positions only $29$ are $\mathcal{P}$-positions, meaning that the next player (Red) will loose. Here are these winning positions for Blue




Here, neutral piece(s) should be put on the yellow square(s). A (potential) remaining neutral piece should be placed on one of the coloured squares. The different colours indicate the remoteness of the $\mathcal{P}$-position:

  • Pink means remoteness $0$, that is, Red has no move whatsoever, so mate in $0$.
  • Orange means remoteness $2$: Red still has a move, but will be mated after Blue’s next move.
  • Purple stands for remoteness $4$, that is, Blue mates Red in $4$ moves, Red starting.
  • Violet means remoteness $6$, so Blue has a mate in $6$ with Red starting
  • Olive stands for remoteness $8$: Blue mates within eight moves.

Memorising these gives you a method to spot winning opportunities. After Red’s move image a board symmetry such that Red’s piece is a genuine L, check whether you can place your Blue piece and one of the yellow pieces to obtain one of the 29 $\mathcal{P}$-positions, and apply the reverse symmetry to place your piece.

If you don’t know this, you can run into trouble very quickly. From the starting position, Red has five options to place his L-piece before moving one of the two yellow counters.



All possible positions of the first option loose immediately.



For example in positions $a,b,c,d,f$ and $l$, Blue wins by playing



Here’s my first attempt at an opening repertoire for the L-game. Question mark means immediate loss, question mark with a number means mate after that number of moves, x means your opponent plays a sensible strategy.









Surely I missed cases, and made errors in others. Please leave corrections in the comments and I’ll try to update the positions.

Leave a Comment

eBook ‘geometry and the absolute point’ v0.1


In preparing for next year’s ‘seminar noncommutative geometry’ I’ve converted about 30 posts to LaTeX, centering loosely around the topics students have asked me to cover : noncommutative geometry, the absolute point (aka the field with one element), and their relation to the Riemann hypothesis.

The idea being to edit these posts thoroughly, add much more detail (and proofs) and also add some extra sections on Borger’s work and Witt rings (and possibly other stuff).

For those of you who prefer to (re)read these posts on paper or on a tablet rather than perusing this blog, you can now download the very first version (minimally edited) of the eBook ‘geometry and the absolute point’. All comments and suggestions are, of course, very welcome. I hope to post a more definite version by mid-september.

I’ve used the thesis-documentclass to keep the same look-and-feel of my other course-notes, but I would appreciate advice about turning LaTeX-files into ‘proper’ eBooks. I am aware of the fact that the memoir-class has an ebook option, and that one can use the geometry-package to control paper-sizes and margins.

Soon, I will be releasing a LaTeX-ed ‘eBook’ containing the Bourbaki-related posts. Later I might also try it on the games- and groups-related posts…

2 Comments

mathblogging and poll-results

Mathblogging.org is a recent initiative and may well become the default starting place to check on the status of the mathematical blogosphere.

Handy, if you want to (re)populate your RSS-aggregator with interesting mathematical blogs, is their graphical presentation of (nearly) all math-blogs ordered by type : group blogs, individual researchers, teachers and educators, journalistic writers, communities, institutions and microblogging (twitter). Links to the last 7 posts are given so you can easily determine whether that particular blog is of interest to you.

The three people behind the project, Felix Breuer, Frederik von Heymann and Peter Krautzberger, welcome you to send them links to (micro)blogs they’ve missed. Surely, there must be a lot more mathematicians with a twitter-account than the few ones listed so far…

Even more convenient is their list of latest posts from their collection, ordered by date. I’ve put that page in my Bookmarks Bar the moment I discovered it! It would be nice, if they could provide an RSS-feed of this list, so that people could place it in their sidebar, replacing old-fashioned and useless blogrolls. The site does provide two feeds, but they are completely useless as they click through to empty pages…

While we’re on the topic of math-blogging, the results of the ‘What should we write about next?’-poll that ran the previous two days on the entry page. Of all people visiting that page, 2.6% left suggestions.

The vast majority (67%) wants more posts on noncommutative geometry. Most of you are craving for introductions (and motivation) accessible to undergraduates (as ‘it’s hard to find quality, updated information on this’). In particular, you want posts giving applications in mathematics (especially number theory), or explaining relationships between different approaches. One person knew exactly how I should go about to achieve the hoped-for accessibility : “As a rule, I’d take what you think would be just right for undergrads, and then trim it down a little more.”

Others want rather specialized posts, such as on ‘connection and parallel transport in noncommutative geometry’ or on ‘trees (per J-L. Loday, M. Aguiar, Connes/Kreimer renormalization (aka Butcher group)), or something completely other tree-related’.

Fortunately, some of you told me it was fine to write about ‘combinatorial games and cool nim stuff, finite simple groups, mathematical history, number theory, arithmetic geometry’, pushed me to go for ‘anything monstrous and moonshiney’ (as if I would know the secrets of the ‘connection between the Mathieu group M24 and the elliptic genus of K3’…) or wrote that ‘various algebraic geometry related posts are always welcome: posts like Mumford’s treasure map‘.

5 Comments

How to play Nimbers?

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

So, who did discover the Leech lattice?

For the better part of the 30ties, Ernst Witt (1) did hang out with the rest of the ‘Noetherknaben’, the group of young mathematicians around Emmy Noether (3) in Gottingen.

In 1934 Witt became Helmut Hasse‘s assistent in Gottingen, where he qualified as a university lecturer in 1936. By 1938 he has made enough of a name for himself to be offered a lecturer position in Hamburg and soon became an associate professor, the down-graded position held by Emil Artin (2) until he was forced to emigrate in 1937.

A former fellow student of him in Gottingen, Erna Bannow (4), had gone earlier to Hamburg to work with Artin. She continued her studies with Witt and finished her Ph.D. in 1939. In 1940 Erna Bannow and Witt married.

So, life was smiling on Ernst Witt that sunday january 28th 1940, both professionally and personally. There was just one cloud on the horizon, and a rather menacing one. He was called up by the Wehrmacht and knew he had to enter service in february. For all he knew, he was spending the last week-end with his future wife… (later in february 1940, Blaschke helped him to defer his military service by one year).

Still, he desperately wanted to finish his paper before entering the army, so he spend most of that week-end going through the final version and submitted it on monday, as the published paper shows.

In the 70ties, Witt suddenly claimed he did discover the Leech lattice $ {\Lambda} $ that sunday. Last time we have seen that the only written evidence for Witt’s claim is one sentence in his 1941-paper Eine Identität zwischen Modulformen zweiten Grades. “Bei dem Versuch, eine Form aus einer solchen Klassen wirklich anzugeben, fand ich mehr als 10 verschiedene Klassen in $ {\Gamma_{24}} $.”

But then, why didn’t Witt include more details of this sensational lattice in his paper?

Ina Kersten recalls on page 328 of Witt’s collected papers : “In his colloquium talk “Gitter und Mathieu-Gruppen” in Hamburg on January 27, 1970, Witt said that in 1938, he had found nine lattices in $ {\Gamma_{24}} $ and that later on January 28, 1940, while studying the Steiner system $ {S(5,8,24)} $, he had found two additional lattices $ {M} $ and $ {\Lambda} $ in $ {\Gamma_{24}} $. He continued saying that he had then given up the tedious investigation of $ {\Gamma_{24}} $ because of the surprisingly low contribution

$ \displaystyle | Aut(\Lambda) |^{-1} < 10^{-18} $

to the Minkowski density and that he had consented himself with a short note on page 324 in his 1941 paper.”

In the last sentence he refers to the fact that the sum of the inverse orders of the automorphism groups of all even unimodular lattices of a given dimension is a fixed rational number, the Minkowski-Siegel mass constant. In dimension 24 this constant is

$ \displaystyle \sum_{L} \frac{1}{| Aut(L) |} = \frac {1027637932586061520960267}{129477933340026851560636148613120000000} \approx 7.937 \times 10^{-15} $

That is, Witt was disappointed by the low contribution of the Leech lattice to the total constant and concluded that there might be thousands of new even 24-dimensional unimodular lattices out there, and dropped the problem.

If true, the story gets even better : not only claims Witt to have found the lattices $ {A_1^{24}=M} $ and $ {\Lambda} $, but also enough information on the Leech lattice in order to compute the order of its automorphism group $ {Aut(\Lambda)} $, aka the Conway group $ {Co_0 = .0} $ the dotto-group!

Is this possible? Well fortunately, the difficulties one encounters when trying to compute the order of the automorphism group of the Leech lattice from scratch, is one of the better documented mathematical stories around.

The books From Error-Correcting Codes through Sphere Packings to Simple Groups by Thomas Thompson, Symmetry and the monster by Mark Ronan, and Finding moonshine by Marcus du Sautoy tell the story in minute detail.

It took John Conway 12 hours on a 1968 saturday in Cambridge to compute the order of the dotto group, using the knowledge of Leech and McKay on the properties of the Leech lattice and with considerable help offered by John Thompson via telephone.

But then, John Conway is one of the fastest mathematicians the world has known. The prologue of his book On numbers and games begins with : “Just over a quarter of a century ago, for seven consecutive days I sat down and typed from 8:30 am until midnight, with just an hour for lunch, and ever since have described this book as “having been written in a week”.”

Conway may have written a book in one week, Ernst Witt did complete his entire Ph.D. in just one week! In a letter of August 1933, his sister told her parents : “He did not have a thesis topic until July 1, and the thesis was to be submitted by July 7. He did not want to have a topic assigned to him, and when he finally had the idea, he started working day and night, and eventually managed to finish in time.”

So, if someone might have beaten John Conway in fast-computing the dottos order, it may very well have been Witt. Sadly enough, there is a lot of circumstantial evidence to make Witt’s claim highly unlikely.

For starters, psychology. Would you spend your last week-end together with your wife to be before going to war performing an horrendous calculation?

Secondly, mathematical breakthroughs often arise from newly found insight. At that time, Witt was also working on his paper on root lattices “Spiegelungsgrupen and Aufzähling halbeinfacher Liescher Ringe” which he eventually submitted in january 1941. Contained in that paper is what we know as Witt’s lemma which tells us that for any integral lattice the sublattice generated by vectors of norms 1 and 2 is a direct sum of root lattices.

This leads to the trick of trying to construct unimodular lattices by starting with a direct sum of root lattices and ‘adding glue’. Although this gluing-method was introduced by Kneser as late as 1967, Witt must have been aware of it as his 16-dimensional lattice $ {D_{16}^+} $ is constructed this way.

If Witt wanted to construct new 24-dimensional even unimodular lattices in 1940, it would be natural for him to start off with direct sums of root lattices and trying to add vectors to them until he got what he was after. Now, all of the Niemeier-lattices are constructed this way, except for the Leech lattice!

I’m far from an expert on the Niemeier lattices but I would say that Witt definitely knew of the existence of $ {D_{24}^+} $, $ {E_8^3} $ and $ {A_{24}^+} $ and that it is quite likely he also constructed $ {(D_{16}E_8)^+, (D_{12}^2)^+, (A_{12}^2)^+, (D_8^3)^+} $ and possibly $ {(A_{17}E_7)^+} $ and $ {(A_{15}D_9)^+} $. I’d rate it far more likely Witt constructed another two such lattices on sunday january 28th 1940, rather than discovering the Leech lattice.

Finally, wouldn’t it be natural for him to include a remark, in his 1941 paper on root lattices, that not every even unimodular lattices can be obtained from sums of root lattices by adding glue, the Leech lattice being the minimal counter-example?

If it is true he was playing around with the Steiner systems that sunday, it would still be a pretty good story he discovered the lattices $ {(A_2^{12})^+} $ and $ {(A_1^{24})^+} $, for this would mean he discovered the Golay codes in the process!

Which brings us to our next question : who discovered the Golay code?

4 Comments

Seating the first few thousand Knights

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