Knights and Knaves, the Heyting way

(image credit: Joe Blitzstein via Twitter)

Smullyan’s Knights and Knaves problems are classics. On an island all inhabitants are either Knights (who only tell true things) and Knaves (who always lie). You have to determine their nature from a few statements. Here’s a very simple problem:

“Abercrombie met just two inhabitants, A and B. A made the following statement: “Both of us are Knaves.” What is A and what is B?”

Now, this one is simple enough to solve, but for more complicated problems a generic way to solve the puzzles is to use propositional calculas, as explained in Smullyan’s Logical Labyrinths”, chapter 8 “Liars, truth-tellers and propositional logic’.

If an inhabitants $A$ asserts a proposition $P$, and if $k_A$ is the assertion ‘$A$ is a Knight’, then the statement can be rephrased as

\[
k_A \Leftrightarrow P \]

for if $A$ is a Knight, $P$ must be true and if $A$ is a Knave $P$ must be false.

Usually, one can express $P$ as a propositional statement involving $k_A,k_B,k_C,\dots$.
The example above can be rephrased as

\[
k_A \Leftrightarrow (\neg k_A \wedge \neg k_B) \]

Assigning truth values to $k_A$ and $k_B$ and setting up the truth-table for this sentence, one sees that the only possibility for this to be true is that $k_A$ equals $0$ and $k_B$ equals $1$. So, $A$ is a Knave and $B$ is a Knight.

Clearly, one only requires this approach for far more difficult problems.

In almost all Smullyan puzzles, the only truth values are $0$ and $1$. There’s a short excursion to Boolean algebras (sorry, Boolean islands) in chapter 9 ‘Variable Liars’ in Logical Labyrinths. But then, the type of problems are about finding equivalent notions of Boolean algebras, rather that generalised Knights&Knaves puzzles.

Did anyone pursue the idea of Smullyanesque puzzles with truth values in a proper Heyting algebra?

I only found one blog-post on this: Non-Classical Knights and Knaves by Jason Rosenhouse.

He considers three valued logic (the Heyting algebra corresponding to the poset 0-N-1, and logical connectives as in the example on the Wiki-page on Heyting algebras.

On his island the natives cycle, repeatedly and unpredictably, between the two states. They are knights for a while, then they enter a transitional phase during which they are partly knight and partly knave, and then they emerge on the other side as knaves.

“If Joe is in the transitional phase, and you say, “Joe is a knight,” or “Joe is a knave,” what truth value should we assign to your statement? Since Joe is partly knight and partly knave, neither of the classical truth values seems appropriate. So we shall assign a third truth value, “N” to such statements. Think of N as standing for “neutral” or “neither true nor false.” On the island, vague statements are assigned the truth value N.

Just to be clear, it’s not just any statement that can be assigned the truth value N. It is only vague statements that receive that truth value, and for now our only examples of such statements are attributions of knight-hood and knave-hood to people in the transitional phase.

For the natives, entering the transitional phase implied a disconcerting loss of identity. Uncertain of how to behave, they hedged their bets by only making statements with truth value N. People in the transitional phase were referred to as neutrals. So there are now three kinds of people: Knights, who only make true statements; Knaves, who only make false statements; and Neutrals, who only make statements with the truth value N.”

He gives one example of a possible problem:

“Suppose you meet three people, named Dave, Evan and Ford. They make the following statements:

Dave: Evan is a knight.
Evan: Ford is a knave.
Ford: Dave is a neutral.

Can you determine the types of all three people?”

If you know of more of these Smullanesque problems using Heyting algebras, please leave a comment.

a SNORTgo endgame

SNORT, invented by Simon NORTon is a map-coloring game, similar to COL. Only, this time, neighbours may not be coloured differently.

SNORTgo, similar to COLgo, is SNORT played with go-stones on a go-board. That is, adjacent stones must have the same colour.

SNORT is a ‘hot’ game, meaning that each player is eager to move as most moves will improve your position. In COL players are reluctant to move, because a move limits your next moves.

For this reason, SNORT positions are much harder to evaluate, and one needs the full force of Conways’s ONAG.

Here’s a SNORTgo endgame. Who has a winning strategy?, and what is the first move in that strategy?

The method to approach such an endgame is similar to that in COLgo. First we remove all dead spots from the board.

What remains, are a 4 spots available only to Right (white) and 5 spots available only to Left (bLack). Further, there a 3 ‘live’ regions: the upper righthand corner and the two lower corners.

The value of these corners must be computed inductively.

Here’s the answer:

For example, Right’s best option in the left-most game (corresponding to the upper righthand corner of the endgame) is to put his stone on N12, resulting in a game in which neither player can move (the zero game).

On the other hand, Left can put a stone at either N11, N12 or N13 leaving a game in which she has two more moves, whereas Right han none (the $2$ game).

The other positions are computed similarly.

To get the value of the endgame we have to sum up all these values.

This can either be done using the addition rule given in ONAG, or by using programs in combinatorial game theory.

There’s Combinatorial Game Suite, developed by Aaron Siegel. But, for some reason I can no longer use it on macOS High Sierra.

Fortunately, the older program David Wolfe’s toolkit is still available, and runs on my MacBook.

The sum game evaluates to $\{ \{3|2 \}|-1 \}$, which is a ‘fuzzy’ game, that is, its value is confused with $0$.

This means that the first player to move has a winning strategy in the endgame.

Can you spot the (unique) winning move for Right (white) and one (of two) winning move for Left (bLack)?

Spoiler alert : solution in the comments.

a non-commutative Jack Daniels problem

At a seminar at the College de France in 1975, Tits wrote down the order of the monster group

\[
\# \mathbb{M} = 2^{46}.3^{20}.5^9.7^6.11^2.13^3.17·19·23·29·31·41·47·59·71 \]

Andrew Ogg, who attended the talk, noticed that the prime divisors are precisely the primes $p$ for which the characteristic $p$ super-singular $j$-invariants are all defined over $\mathbb{F}_p$.

Here’s Ogg’s paper on this: Automorphismes de courbes modulaires, Séminaire Delange-Pisot-Poitou. Théorie des nombres, tome 16, no 1 (1974-1975).

Ogg offered a bottle of Jack Daniels for an explanation of this coincidence.

Even Richard Borcherds didn’t claim the bottle of Jack Daniels, though his proof of the monstrous moonshine conjecture is believed to be the best explanation, at present.

A few years ago, John Duncan and Ken Ono posted a paper “The Jack Daniels Problem”, in which they prove that monstrous moonshine implies that if $p$ is not one of Ogg’s primes it cannot be a divisor of $\# \mathbb{M}$. However, the other implication remains mysterious.

Duncan and Ono say:

“This discussion does not prove that every $p ∈ \text{Ogg}$ divides $\# \mathbb{M}$. It merely explains how the first principles of moonshine suggest this implication. Monstrous moonshine is the proof. Does this then provide a completely satisfactory solution to Ogg’s problem? Maybe or maybe not. Perhaps someone will one day furnish a map from the characteristic $p$ supersingular $j$-invariants to elements of order $p$ where the group structure of $\mathbb{M}$ is apparent.”

I don’t know whether they claimed the bottle, anyway.

But then, what is the non-commutative Jack Daniels Problem?

A footnote on the first page of Conway and Norton’s ‘Monstrous Moonshine’ paper says:

“Very recently, A. Pizer has shown these primes are the only ones that satisfy a certain conjecture of Hecke from 1936 relating modular forms of weight $2$ to quaternion algebra theta-series.”

Pizer’s paper is “A note on a conjecture of Hecke”.

Maybe there’s a connection between monstrous moonshine and the arithmetic of integral quaternion algebras. Some hints:

The commutation relations in the Big Picture are reminiscent of the meta-commutation relations for Hurwitz quaternions, originally due to Conway in his booklet on Quaternions and Octonions.

The fact that the $p$-tree in the Big Picture has valency $p+1$ comes from the fact that the Brauer-Severi of $M_2(\mathbb{F}_p)$ is $\mathbb{P}^1_{\mathbb{F}_p}$. In fact, the Big Picture should be related to the Brauer-Severi scheme of $M_2(\mathbb{Z})$.

Then, there’s Jorge Plazas claiming that Connes-Marcolli’s $GL_2$-system might be related to moonshine.

One of the first things I’ll do when I return is to run to the library and get our copy of Shimura’s ‘Introduction to the arithmetic theory of automorphic functions’.

Btw. the bottle in the title image is not a Jack Daniels but the remains of a bottle of Ricard, because I’m still in the French mountains.

the monstrous moonshine picture – 2

Time to wrap up my calculations on the moonshine picture, which is the subgraph of Conway’s Big Picture needed to describe all 171 moonshine groups.

No doubt I’ve made mistakes. All corrections are welcome. The starting point is the list of 171 moonshine groups which are in the original Monstrous Moonshine paper.

The backbone is given by the $97$ number lattices, which are closed under taking divisors and were found by looking at all divisors of the numbers $N=n \times h$ for the 171 moonshine groups of the form $N+e,f,\dots$ or $(n|h)+e,f,\dots$.

The Hasse-diagram of this poset (under division) is here (click on the image to get a larger version)

There are seven types of coloured numbers, each corresponding to number-lattices which have the same local structure in the moonshine picture, as in the previous post.

The white numbered lattices have no further edges in the picture.

The yellow number lattices (2,10,14,18,22,26,32,34,40,68,80,88,90,112,126,144,180,208 = 2M) have local structure

\[
\xymatrix{& \color{yellow}{2M} \ar@{-}[r] & M \frac{1}{2}} \]

The green number lattices (3,15,21,39,57,93,96,120 = 3M) have local structure

\[
\xymatrix{M \frac{1}{3} \ar@[red]@{-}[r] & \color{green}{3M} \ar@[red]@{-}[r] & M \frac{2}{3}} \]

The blue number lattices (4,16,20,28,36,44,52,56,72,104 = 4M) have as local structure

\[
\xymatrix{M \frac{1}{2} \ar@{-}[d] & & M \frac{1}{4} \ar@{-}[d] \\
2M \ar@{-}[r] & \color{blue}{4M} \ar@{-}[r] & 2M \frac{1}{2} \ar@{-}[d] \\
& & M \frac{3}{4}} \]

where the leftmost part is redundant as they are already included in the yellow-bit.

The purple number lattices (6,30,42,48,60 = 6M) have local structure

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

where again the lefmost part is redundant, and I forgot to add the central part in the previous post… (updated now).

The unique brown number lattice 8 has local structure

\[
\xymatrix{& & 1 \frac{1}{4} \ar@{-}[d] & & 1 \frac{1}{8} \ar@{-}[d] & \\
& 1 \frac{1}{2} \ar@{-}[d] & 2 \frac{1}{2} \ar@{-}[r] \ar@{-}[d] & 1 \frac{3}{4} & 2 \frac{1}{4} \ar@{-}[r] & 1 \frac{5}{8} \\
1 \ar@{-}[r] & 2 \ar@{-}[r] & 4 \ar@{-}[r] & \color{brown}{8} \ar@{-}[r] & 4 \frac{1}{2} \ar@{-}[d] \ar@{-}[u] & \\
& & & 1 \frac{7}{8} \ar@{-}[r] & 2 \frac{3}{4} \ar@{-}[r] & 1 \frac{3}{8}} \]

The local structure in the two central red number lattices (not surprisingly 12 and 24) looks like the image in the previous post, but I have to add some ‘forgotten’ lattices.

That’ll have to wait…

Moonshine’s green anaconda

The largest snake in the moonshine picture determines the moonshine group $(24|12)$ and is associated to conjugacy class $24J$ of the monster.

It contains $70$ lattices, about one third of the total number of lattices in the moonshine picture.

The anaconda’s backbone is the $(288|1)$ thread below (edges in the $2$-tree are black, those in the $3$-tree red and coloured numbers are symmetric with respect to the $(24|12)$-spine and have the same local snake-structure.

\[
\xymatrix{9 \ar@{-}[r] \ar@[red]@{-}[d] & \color{green}{18} \ar@{-}[r] \ar@[red]@{-}[d] & \color{yellow}{36} \ar@{-}[r] \ar@[red]@{-}[d] & \color{yellow}{72} \ar@{-}[r] \ar@[red]@{-}[d] & \color{green}{144} \ar@{-}[r] \ar@[red]@{-}[d] & 288 \ar@[red]@{-}[d] \\
3 \ar@{-}[r] \ar@[red]@{-}[d] & \color{blue}{6} \ar@{-}[r] \ar@[red]@{-}[d] & \color{red}{12} \ar@{-}[r] \ar@[red]@{-}[d] & \color{red}{24} \ar@{-}[r] \ar@[red]@{-}[d] & \color{blue}{48} \ar@{-}[r] \ar@[red]@{-}[d] & 96 \ar@[red]@{-}[d] \\
1 \ar@{-}[r] & \color{green}{2} \ar@{-}[r] & \color{yellow}{4} \ar@{-}[r] & \color{yellow}{8} \ar@{-}[r] & \color{green}{16} \ar@{-}[r] & 32 } \]

These are the only number-lattices in the anaconda. The remaining lattices are number-like, that is of the form $M \frac{g}{h}$ with $M$ an integer and $1 \leq g < h$ with $(g,h)=1$.
There are

– $12$ with $h=2$ and $M$ a divisor of $72$.

– $12$ with $h=3$ and $M$ a divisor of $32$.

– $12$ with $h=4$ and $M$ a divisor of $18$.

– $8$ with $h=6$ and $M$ a divisor of $8$.

– $8$ with $h=12$ and $M=1,2$.

The non-number lattices in the snake are locally in the coloured numbers:

In $2,16,18,144=2M$

\[
\xymatrix{& \color{green}{2M} \ar@{-}[r] & M \frac{1}{2}} \]

In $4,8,36,72=4M$

\[
\xymatrix{M \frac{1}{2} \ar@{-}[d] & & M \frac{1}{4} \ar@{-}[d] \\
2M \ar@{-}[r] & \color{yellow}{4M} \ar@{-}[r] & 2M \frac{1}{2} \ar@{-}[d] \\
& & M \frac{3}{4}} \]

In $6,48=6M$

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

In $12,24=12M$ the local structure looks like

Here, we used the commutation relations to reach all lattices at distance $log(6)$ and $log(12)$ by first walking the $2$-adic tree and postpone the last step for the $3$-tree.

Perhaps this is also a good strategy to get a grip on the full moonshine picture:

First determine subsets of the moonshine thread with the same local structure, and then determine for each class this local structure.

a COLgo endgame

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

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

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

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

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

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

Spoiler alert: solution below.

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

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

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

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

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

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

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

But then, the total value of the endgame position is

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