The \(\sP\)-position sets of some combinatorial games have special combinatorial structures.
For example, the \(\sP\)-position set of the hexad game, first investigated by Conway and Ryba, is the block set of the Steiner system \(S(5, 6, 12)\) in the shuffle numbering, denoted by \(\shD\).
There were, however, few known games related to Steiner systems like the hexad game.
For a given Steiner system, we construct a game whose \(\sP\)-position set is its block set.

By using constructed games, we obtain the following two results.
First, we characterize \(\shD\) among the 5040 isomorphic \(\ccS(5, 6, 12)\) with point set \(\set{0, 1, \dotsc, 11}\).
For each \(\ccS(5, 6, 12)\), our construction produces a game whose \(\sP\)-position set is its block set.
From \(\shD\), we obtain the hexad game, and this game is characterized as a unique game with the minimum number of positions among the obtained 5040 games.
Second, we characterize projective Steiner triple systems by using game distributions.
Here, the game distribution of a Steiner system \(\cD\) is the frequency distribution of the numbers of positions in games obtained from Steiner systems isomorphic to \(\cD\).
We find that the game distribution of an \(\ccS(\cct, \cct + 1, \ccv)\) can be decomposed into symmetric components and that a Steiner triple system is projective if and only if its game distribution has a unique symmetric component.

§ INTRODUCTION

sec-introThe starting point of this paper is a two-player (impartial) game called the hexad game [6, 13].[According to [13], the hexad game was first investigated by Conway and Ryba.]
In combinatorial game theory, one of the fundamental goals is to determine the \(\sP\)-position set of a game,
where a \(\sP\)-position is a winning position for the Previous player to move.
The hexad game is notable because its \(\sP\)-position set, which is a subset of \(\binom{[12]}{6}\), is the block set of a Steiner system \(S(5, 6, 12)\) [6, 13],
where \([12] = \set{0, 1, \dotsc, 11}\) and \({[12] \choose 6} = \bigfamily{\ccP \subset [12] : \size{\ccP} = 6}\).
Here, a pair \(\bigl([\ccv], \Block\bigr)\) is called a Steiner system \(S(\cct, \cck, \ccv)\) with point set \([v]\) and block set \(\Block\) if \(\Block \subseteq {[\ccv] \choose \cck}\) and every \(\ccT \in {[\ccv] \choose \cct}\) is contained in a unique \(\ccB \in \Block\).
Further, Conway and Sloane [6] found a game whose \(\sP\)-position set is the block set of a Steiner system \(S(5, 8, 24)\).
No methods, however, were known to find games related to Steiner systems like the above games.

p2-4For a given Steiner system, we construct a game whose \(\sP\)-position set is equal to its block set (Corollary <ref>).[Since we start with a \(\sP\)-position set, our approach may be referred to as reverse game theory or mechanism design (see [12]).]
We here illustrate our construction using the \(\ccS(1, 2, 4)\) with block set \(\bigfamily{\set{0, 2}, \set{1, 3}}\);
our aim is to obtain the game shown in Figure <ref>.
We use a digraph to represent a game.
Let \(\Gamma\) be a digraph with vertex set \({[4] \choose 2}\) and edge set

\[
\biggset{\bigl(\ccP, \ccP^{(\ccp\ \ccq)} \bigr) \in {[4] \choose 2}^2 : \ccq < \ccp,\ \ccp \in \ccP,\ \ccq \not \in \ccP},
\]

where \((\ccp\ \ccq)\) is the transposition of \(\ccp\) and \(\ccq\).
We denote by \(\Position{\Gamma}\) and \(\Edge{\Gamma}\) the vertex and edge sets of \(\Gamma\), respectively.
For example, \(\bigl(\set{2, 3}, \set{2, 3}^{(3\ 0)}\bigr) = \bigl(\set{2, 3}, \set{0, 2}\bigr) \in \Edge{\Gamma}\).
For \(\ccP \in \Position{\Gamma}\), let \(\InNeighbors{\ccP}[\Gamma]\) and \(\OutNeighbors{\ccP}[\Gamma]\) be the sets of in-neighbors and out-neighbors of \(\ccP\), respectively.
That is,

\[
\InNeighbors{\ccP}[\Gamma] = \bigset{\ccR \in \Position{\Gamma} : (\ccR, \ccP) \in \Edge{\Gamma}} \quad \tand \quad
\OutNeighbors{\ccP}[\Gamma] = \bigset{\ccQ \in \Position{\Gamma} : (\ccP, \ccQ) \in \Edge{\Gamma}}.
\]

For example, \(\InNeighbors{\ymod{\set{0, 2}}}[\Gamma][\bigcbrackets] = \bigfamily{\set{1, 2}, \set{0, 3}, \set{2, 3}}\).

\begin{equation}
\label{equ:def-bposition}
\bPosition{\Block}[\Gamma] = \Block \cup \bigcup_{\ccB \in \Block} \InNeighbors{\ccB}[\Gamma],
\end{equation}

where \(\Block = \bigfamily{\set{0, 2}, \set{1, 3}}\).
Then \(\bPosition{\Block}[\Gamma] = {[4] \choose 2} \setminus \bigfamily{\set{0, 1}}\).
Let \(\Induced{\Gamma}{\ymod{\bPosition{\Block}[\Gamma]}}[\bigcbrackets]\) denote the subgraph induced in \(\Gamma\) by \(\ymod{\bPosition{\Block}[\Gamma]}\), that is, the digraph with vertex set \(\ymod{\bPosition{\Block}[\Gamma]}\) and edge set

\[
\Bigset{(\ccP, \ccQ) \in \Edge{\Gamma}: \ccP, \ccQ \in \ymod{\bPosition{\Block}[\Gamma]}}.
\]

We consider the digraph \(\Induced{\Gamma}{\bPosition{\Block}[\Gamma]}[\bigcbrackets]\) as the following two-player game.
Before a game begins, we put a token on a starting vertex \(\ccP \in \bPosition{\ymod{\Block}}[\Gamma]\).
The first player moves the token from \(\ccP\) to an out-neighbor \(\ccQ\) of \(\ccP\).
Similarly, the second player moves it from \(\ccQ\) to an out-neighbor \(\ccR\) of \(\ccQ\).
In this way, the two players alternately move the token from the current vertex to one of its out-neighbors.
The player who moves the token last wins.

In this manner, we can view a digraph as a two-player game.
Then the \(\sP\)-position set of \(\Induced{\Gamma}{\bPosition{\Block}[\Gamma]}[\bigcbrackets]\) is \(\Block\).

A game whose \(\sP\)-position set is \(\bigfamily{\set{0, 2}, \set{1, 3}}\). The labels \(\sP\) and \(\sN\) indicate winning positions for the previous and next players, respectively.

For example, if \(\set{1, 3}\) is the starting vertex,
then the first player can move the token only to \(\set{0, 3}\) or \(\set{1, 2}\),
so the second player can move it to \(\set{0, 2}\) and win.
Thus \(\set{1, 3}\) is a winning position for the second player (the previous player to move), that is, a \(\sP\)-position.
In the same way, for a given Steiner system, we can construct a game whose \(\sP\)-position set is its block set (Corollary <ref>).

In this paper, we investigate the frequency distribution of the numbers of positions of games obtained from a Steiner system.
Let \(\cD\) be an \(\ccS(\cct, \cck, \ccv)\) with point set \([\ccv]\), and let \(\ccN\)
be the index of the automorphism group of \(\cD\) in the symmetric group \(\Sym([\ccv])\) on \([\ccv]\).
Then there are \(\ccN\) Steiner systems \(\ccS(\cct, \cck, \ccv)\) with point set \([\ccv]\) isomorphic to \(\cD\),
and, for each of them, we can construct a game whose \(\sP\)-position set is its block set.
The frequency distribution of the numbers of positions (vertices) of the obtained \(\ccN\) games is called the game distribution of \(\cD\).
For example, there are three \(\ccS(1, 2, 4)\) with point set \([4]\), and their block sets are as follows:

\[
\Block = \bigfamily{\set{0, 2}, \set{1, 3}}, \quad \Block' = \bigfamily{\set{0, 1}, \set{2, 3}}, \quad \Block'' = \bigfamily{\set{0, 3}, \set{1, 2}}.
\]

As we have seen, \(\size{\bPosition{\Block}[\Gamma]} = 5\).
A direct computation shows that

\[
\msize{\bPosition{\Block'}[\Gamma]} = \size{{[4] \choose 2}} = 6 \quad \tand \quad \msize{\bPosition{\Block''}[\Gamma]} = \size{{[4] \choose 2} \setminus \bigfamily{\set{0, 1}, \set{0, 2}}} = 4.
\]

Therefore the game distribution of an \(\ccS(1, 2, 4)\) is as follows:

\(\#\) positions     4     5     6     Total

\(\#\) games     1     1     1     3

By using game distributions, we present the following two results.

First, we characterize the Steiner system \(S(5, 6, 12)\) in the shuffle numbering, denoted by \(\shD\).
It is well-known that \(S(5, 6, 12)\) is unique up to isomorphism [18] and its automorphism group is the sporadic simple Mathieu group \(M_{12}\) [17].

Since the index of \(\ccM_{12}\) in \(\Sym([12])\) equals 5040, it follows that
there are 5040 \(S(5, 6, 12)\) with point set \([12]\), and our construction produces 5040 games.
Here, \(\shD\) is one of the 5040 \(S(5, 6, 12)\).
The name of the shuffle numbering comes from the fact that the automorphism group of \(\shD\) is
generated by the two permutations \(i \mapsto 11 - i\) and \(\cci \mapsto \min(2 \cci, 23 - 2 \cci)\) of \([12]\), called the Mongean shuffle,
and \(\shD\) has many interesting properties [7].
In fact, the \(\sP\)-position set of the hexad game is the block set of \(\shD\) [6, 13].
Conversely, our construction produces the hexad game from \(\shD\).
Surprisingly, this game can be characterized as a unique game with the minimum number of positions among the obtained 5040 games;
this result is easily seen by using the game distribution of an \(\ccS(5, 6, 12)\) (Theorem <ref>).
In particular, we can characterize \(\shD\) by using games.

Second, we characterize projective Steiner triple systems among all Steiner triple systems.
In this paragraph, we consider non-isomorphic designs unlike in the previous paragraph.
The projective geometry \(\text{PG}(d, 2)\) forms a Steiner system \(S(2, 3, 2^{d + 1} - 1)\), called the projective Steiner triple system of order \(2^{d + 1} - 1\) (Example <ref>).
It is known that there are 80 non-isomorphic Steiner systems \(S(2, 3, 15)\) [4], and one of them is projective.
How can we characterize the projective one among them?
In combinatorial design theory, characterizations of particular designs, including projective Steiner triple systems, have been studied (see, for example, [3, 9, 11, 16, 1]).
In this paper, we show that the game distribution of an \(S(\cct, \cct + 1, \ccv)\) can be decomposed into symmetric components (Proposition <ref>).
We then prove that an \(S(2, 3, \ccv)\) is projective if and only if its game distribution has a unique symmetric component (Theorem <ref>).

This paper is organized as follows. In Section <ref>, we recall the concepts of a Steiner system and an impartial game.
Section <ref> contains the construction of games whose \(\sP\)-position set equals the block set of a Steiner system.
In Section <ref>, we introduce game distributions and then characterize the \(S(5, 6, 12)\) in the shuffle numbering.
In Section <ref>, it is shown that the game distribution of an \(S(\cct, \cct + 1, \ccv)\) can be decomposed into symmetric components.
We finally characterize projective Steiner triple systems by using game distributions in Section <ref>.

§ PRELIMINARIES

We recall some facts about Steiner systems and impartial games that will be used later.

§.§ Steiner Systems

sec-steinerLet \(\cct\) be a nonnegative integer and let \(\ccv\), \(\cck\), and \(\lambda\) be positive integers with \(\cct \le \cck \le \ccv\).
A \(\design{\cct}{\ccv, \cck, \lambda}\) \(\cD\) is a pair \((\Vertex{\cD}, \Block[\cD])\) where \(\Vertex{\cD}\) is a set with \(\size{\Vertex{\cD}} = \ccv\)
and \(\Block[\cD]\), called the block set of \(\cD\), is a subset of \({\Vertex{\cD} \choose \cck}\) such that
every \(\ccT \in {\Vertex{\cD} \choose \cct}\) is contained in exactly \(\lambda\) blocks.
Note that a \(\design{\cct}{\ccv, \cck, 1}\) is a Steiner system \(\ccS(\cct, \cck, \ccv)\).
Throughout this paper, we assume that \(\Vertex{\cD} = [\ccv] = \set{0, 1, \dotsc, \ccv - 1}\) unless otherwise noted.
If \(\cD\) is a \(\design{\cct}{\ccv, \cck, \lambda}\), then it is also an \(\design{\cci}{\ccv, \cck, \lambda_\cci}\) for \(0 \le \cci \le \cct\), where

\begin{equation}
\label{equ:lambdai}
\lambda_\cci = \frac{{\ccv - \cci \choose \cct - \cci}}{{\cck - \cci \choose \cct - \cci}} \lambda.
\end{equation}

Note that \(\lambda_0\) equals the number of blocks of \(\cD\).

Let \(\Block = \bigfamily{\set{0, 1}, \set{2, 3}, \dotsc, \set{2 \ccv - 2, 2 \ccv - 1}}\).
Then \(([2 \ccv], \Block)\) is an \(S(1, 2, 2 \ccv)\).

[Projective Steiner triple systems]
Exm. [Projective Steiner triple systems]

Let \(\FF_2\) be the finite field with two elements.

\[
\Vertex{} = \FF_2^{\ccd + 1} \setminus \bigfamily{(0, \dotsc, 0)}\  \tand\ \Block = \biggfamily{\set{\ccp, \ccq, \ccp + \ccq} \in {\Vertex{} \choose 3} : \set{\ccp, \ccq} \in {\Vertex{} \choose 2}}.
\]

We see that \((\Vertex{}, \Block)\) is a Steiner system \(S(2, 3, 2^{\ccd + 1} - 1)\).
This design is called the projective Steiner triple system of order \(2^{\ccd + 1} - 1\),
since \(\Vertex{}\) and \(\Block\) can be regarded as the point and line sets of the projective geometry \(\text{PG}(\ccd, 2)\).
For example, if \(\ccd = 2\), then the blocks are as shown in Figure <ref>.

The blocks of the projective Steiner triple system of order 7. For example, \(\bigfamily{(1, 0, 0), (1, 1, 0), (0, 1, 0)}\) and \(\bigfamily{(1, 1, 0), (1, 0, 1), (0, 1, 1)}\) are blocks.

We next define isomorphisms.
Let \(\cD\) and \(\cD'\) be \(\designs{t}{v, k, \lambda}\).
A bijection \(\phi \colon \Vertex{\cD} \to \Vertex{\cD'}\) is called an isomorphism if
\(\phi(\ccB) \in \Block[\cD']\) for every \(\ccB \in \Block[\cD]\), where \(\phi(\ccB) = \set{\phi(\ccb) : \ccb \in \ccB}\).
If there is an isomorphism between \(\cD\) and \(\cD'\), then they are said to be isomorphic.
An isomorphism from \(\cD\) to \(\cD\) is called an automorphism of \(\cD\).
Let \(\Aut(\cD)\) denote the group of automorphisms of \(\cD\).

Let \(\cD\) be the \(S(1, 2, 4)\) with block set \(\bigfamily{\set{0, 1}, \set{2, 3}}\).
The automorphism group of \(\cD\) is generated by the two permutations
\((0\ 1)\) and \((0\ 2)(1\ 3)\). This group is isomorphic to the dihedral group \(D_8\) of order 8.
It is easy to see that \(S(1, 2, 4)\) is unique up to isomorphism.
In general, \(S(1, 2, 2v)\) is unique up to isomorphism.

A Steiner system \(S(2, 3, \ccv)\) is called a Steiner triple system (see [3] for details).
Kirkman [14] showed that
an \(S(2, 3, \ccv)\) exists if and only if \(\ccv \equiv 1, 3 \pmod{6}\).
Although \(S(2, 3, 7)\) and \(S(2, 3, 9)\) are unique up to isomorphism,
\(S(2, 3, \ccv)\) is not unique for \(\ccv > 9\) [8, 15]. For example,
there are 80 non-isomorphic \(S(2, 3, 15)\) [4] and one of them is projective.
Let \(\cD\) be an \(S(2, 3, \ccv)\).
By the Veblen-Young theorem [16], the following two conditions are equivalent:

* \(\cD\) is projective, that is, it is isomorphic to a projective Steiner triple system.

* If \(\set{a, b, c}\), \(\set{a, d, e}\), and \(\set{b, d, f}\) are distinct three blocks of \(\cD\), then \(\set{c, e, f}\) is also a block (see Figure <ref>).

A characterization of projective Steiner triple systems.

§.§ Impartial Games

sec-gamesWe recall the concept of an impartial game (see, for example, [2, 5] for more details).

We represent a game as a digraph.
Let \(\Gamma\) be a digraph \((\Position{\Gamma}, \Edge{\Gamma})\) satisfying

\begin{equation}
\label{equ:def-game}
\lg_{\Gamma}(\ccP) < \infty \quad \text{for every\ } \ccP \in \Position{\Gamma},
\end{equation}

where \(\lg_{\Gamma}(\ccP)\) is the maximum length of a walk from \(\ccP\).
The vertex set \(\Position{\Gamma}\) is called the position set of \(\Gamma\).
If \((\ccP, \ccQ) \in \Edge{\Gamma}\), then \(\ccQ\) is called an option of \(\ccP\).
A position without options is called a terminal position.
Suppose that \(\Gamma\) has at least one position; then \(\Gamma\) has a terminal position.
We consider \(\Gamma\) as a two-player game in the way described in the introduction.
This kind of game is called a (short) impartial game, and every impartial game can be
represented in this manner.
Thus we call a digraph satisfying (<ref>) a game graph or simply a game.[Although a (short) impartial game is defined as a vertex in a game graph \(\Gamma\), we can consider \(\Gamma\) itself as an impartial game by adding a vertex if necessary (see Remark <ref>). Therefore we call \(\Gamma\) simply a game.]

\[
\Gamma^1 = \bigl([4], \bigfamily{(3, 2), (3, 1), (2, 1), (2, 0), (1, 0)}\bigr)\ \tand\  \Gamma^2 = \bigl([2], \bigfamily{(1, 0), (0, 1)}\bigr).
\]

See Figure <ref>.
Then \(\Gamma^1\) is a game and position 0 is a terminal position in \(\Gamma^1\).
However, \(\Gamma^2\) is not a game since the walk \((1, 0, 1, 0, \dotsc)\) has infinite length.

\(\Gamma^1\) and \(\Gamma^2\).

[Welter's game and the hexad game]
Exm. [Welter's game and the hexad game]

Let \(\Wel{\ccv}{\cck}\) be the game with position set \({[\ccv] \choose \cck}\) and
edge set

\[
\biggset{(\ccP, \ccP^{(\ccp\ \ccq)}) \in {[\ccv] \choose \cck}^2 : \ccq < \ccp,\ \ccp \in \ccP,\ \ccq \not \in \ccP}.
\]

The game \(\Wel{\ccv}{\cck}\) is called Welter's game.

\[
\Position{\Hexad} = \biggset{\ccP \in {[12] \choose 6} : \sum_{\ccp \in \ccP} \ccp \ge 21}.
\]

The subgraph \(\Induced{\Wel{12}{6}}{\Position{\Hexad}}[\bigcbrackets]\) induced in \(\Wel{12}{6}\) by \(\Position{\Hexad}\) is called the hexad game and denoted by \(\Hexad\).

We next define \(\sP\)-position sets.
Let \(\sP\) and \(\sN\) be two symbols.
For a game \(\Gamma\) and a position \(\ccP \in \Position{\Gamma}\),
the outcome of \(\ccP\) is defined recursively by

\[
\cco_{\Gamma}(\ccP) = \begin{cases}
\sN & \tif \ccP \text{\ has an option\ } \ccQ \text{\ with\ } \cco_{\Gamma}(\ccQ) = \sP, \\
\sP & \totherwise. \mylink{p6-1}
\end{cases}
\]

Recall that \(\Gamma\) has a terminal position if it has at least one position.
By definition, the outcome of a terminal position is \(\sP\).
An easy induction shows that the previous player can force a win if and only if the outcome of the starting position is \(\sP\).

\[
\Winning{\Gamma} = \bigset{\ccP \in \Position{\Gamma} : \cco_{\Gamma}(\ccP) = \sP}.
\]

The set \(\Winning{\Gamma}\) is called the \(\sP\)-position set or winning position set of the game \(\Gamma\).
p6-18Note that \(\Winning{\Gamma}\) is an independent set in \(\Gamma\),
that is, \((\ccB, \ccC) \not \in \Edge{\Gamma}\) for any \(\ccB, \ccC \in \Winning{\Gamma}\).
As we will see in the next section,
our construction, described in the introduction, can be applied to an independent set in \(\Gamma\).
Note that if \(\Block\) is the block set of an \(\ccS(\cct, \cck, \ccv)\) with \(\cct < \cck\),
then \(\Block\) is an independent set in \(\Wel{\ccv}{\cck}\).

Let \(\Gamma^1\) be as in Example <ref>.
The outcomes of the four positions are shown in Figure <ref>.
Note that the previous player can force a win if we start at position 3.

Outcomes of positions.

p7-1Let \(\shD = ([12], \Winning{\Hexad})\). Then
\(\shD\) is an \(\ccS(5, 6, 12)\), called the Steiner system \(\ccS(5, 6, 12)\) in the shuffle numbering [6, 13].
For example, if \(\ccP\) is an element in \({[12] \choose 6}\) with \(\sum_{\ccp \in \ccP} \ccp = 21\),
then it is a terminal position in \(\Hexad\), so \(\ccP \in \Winning{\Hexad}\).
Incidentally, the whole \(\sP\)-positions of \(\Hexad\) can be obtained as the orbit

\[
\bigset{\set{0, 1, 2, 3, 4, 11}^\pi : \pi \in \ccG},
\]

where \(\set{0, 1, 2, 3, 4, 11}^\pi = \set{0^\pi, 1^\pi, 2^\pi, 3^\pi, 4^\pi, 11^\pi}\) and \(\ccG\) is the group generated by the two permutations \(\cci \mapsto 11 - \cci\) and \(\cci \mapsto \min(2 \cci, 23 - 2 \cci)\) of \([12]\),
which is the automorphism group of \(\shD\).
We can also explicitly describe \(\Winning{\Hexad}\) by using the
following \(3 \times 4\) array, called the MINIMOG in the shuffle numbering (see [7]).

§ CONSTRUCTION OF GAMES

For an independent set \(\Block\) in a game \(\Gamma\), we construct a game whose \(\sP\)-position set equals \(\Block\).
In particular, our construction works for the block set \(\Block\) of an \(\ccS(\cct, \cck, \ccv)\) with \(\cct < \cck\) since \(\Block\) is an independent set in \(\Wel{\ccv}{\cck}\).

For an independent set \(\Block\) in a game \(\Gamma\), define \(\bPosition{\Block}[\Gamma]\) by (<ref>).
When no confusion can arise, we write \(\bPosition{\Block}\), \(\InNeighbors{\ccP}\), and \(\OutNeighbors{\ccP}\) instead of \(\bPosition{\Block}[\Gamma]\), \(\InNeighbors{\ccP}[\Gamma]\), and \(\OutNeighbors{\ccP}[\Gamma]\), respectively.
Let \(\Phi(\Gamma, \Block)\) denote the family of the position sets of induced subgraphs of \(\Gamma\) whose \(\sP\)-position sets equal \(\Block\), that is,
\[
\ymodoff{\Phi(\Gamma, \Block) = \bigset{\cQ \subseteq \Position{\Gamma} : \Winning{\Induced{\Gamma}{\cQ}} = \Block}.}
\]

If \(\Gamma\) is a game and \(\Block\) is an independent set in \(\Gamma\), then
\[
\Phi(\Gamma, \Block) = \bigset{\cQ : \Block \subseteq \cQ \subseteq \bPosition{\Block}}\ymod{;}
\]

in particular, \(\Winning{\Induced{\Gamma}{\bPosition{\Block}}} = \Block\) and \(\bPosition{\Block}\) is the maximum element of \(\Phi(\Gamma, \Block)\) with respect to inclusion.

We begin by showing that if \(\cQ\) is a subset of \(\Position{\Gamma}\) with \(\Block \subseteq \cQ \subseteq \bPosition{\Block}\), then \(\cQ \in \Phi(\Gamma, \Block)\).
Let \(\Delta = \Induced{\Gamma}{\cQ}\). It suffices to show that \(\Winning{\Delta} = \Block\). Let \(\ccQ \in \cQ\) and \(\ccl = \lg_{\Delta}(\ccQ)\).
We show that \(\ccQ \in \Winning{\Delta}\) if and only \(\ccQ \in \Block\) by induction on \(\ccl\).
If \(\ccl = 0\), then \(\ccQ \in \Winning{\Delta}\) and \(\ccQ \in \Block\) since \(\ccQ\) is a terminal position of \(\Delta\) and \(\ccQ \in \cQ \subseteq \bPosition{\Block}\).
Suppose that \(\ccl > 0\).
First, we show that if \(\ccQ \in \Block\), then \(\ccQ \in \Winning{\Delta}\). Let \(\ccR\) be an option of \(\ccQ\).
Since \(\Block\) is an independent set, it follows that \(\ccR \not \in \Block\).
By the induction hypothesis, \(\ccR \not \in \Winning{\Delta}\).
This implies that \(\ccQ \in \Winning{\Delta}\).
Next, we show that if \(\ccQ \not \in \Block\), then \(\ccQ \not \in \Winning{\Delta}\).
Since \(\ccQ \in \cQ \subseteq \bPosition{\Block}\), it follows that \(\ccQ\) has an option \(\ccB\) with \(\ccB \in \Block\).
By the induction hypothesis, \(\ccB \in \Winning{\Delta}\), so \(\ccQ \not \in \Winning{\Delta}\).
Therefore \(\Winning{\Delta} = \Block\).

It remains to prove that if \(\cQ \in \Phi(\Gamma, \Block)\), then \(\Block \subseteq \cQ \subseteq \bPosition{\Block}\).
It is obvious that \(\cQ \supseteq \Block\). We show that \(\cQ \subseteq \bPosition{\Block}\).
Let \(\ccQ \in \cQ\) and \(\Delta = \Induced{\Gamma}{\cQ}\).
If \(\ccQ \in \Block\), then \(\ccQ \in \bPosition{\Block}\).
Suppose that \(\ccQ \not \in \Block\).
Since \(\Block = \Winning{\Delta}\), it follows that \(\ccQ \not \in \Winning{\Delta}\),
and that \(\ccQ\) has an option \(\ccB\) with \(\ccB \in \Winning{\Delta} = \Block\).
This implies that \(\ccQ \in \InNeighbors{\ccB} \subseteq \bPosition{\Block}\).
Therefore \(\cQ \subseteq \bPosition{\Block}\).

For a \(\design{\cct}{\ccv, \cck, \lambda}\) \(\cD\),
let \(\DWel{\cD}\) denote the game \(\Induced{\Wel{\ccv}{\cck}}{\bPosition{\cD}}[\bigcbrackets]\), where \(\bPosition{\cD} = \bPosition{\Block[\cD]}\).
If \(\Block[\cD]\) is an independent set in \(\Wel{\ccv}{\cck}\),
it follows from Theorem <ref> that \(\Winning{\DWel{\cD}} = \Block[\cD]\).
In particular, we obtain the following corollary.

If \(\cD\) is an \(S(\cct, \cck, \ccv)\) with \(\cct < \cck\), then
the \(\sP\)-position set of \(\DWel{\cD}\) equals \(\Block[\cD]\).

Let \(\cD\) be the \(\ccS(1, 2, 4)\) with block set \(\bigfamily{\set{0, 2}, \set{1, 3}}\).
As we have seen in the introduction, \(\bPosition{\cD} = {[4] \choose 2} \setminus \bigfamily{\set{0, 1}}\) and \(\Winning{\DWel{\cD}} = \bigfamily{\set{0, 2}, \set{1, 3}}\).

The game \(\DWel{\shD}\) equals \(\Hexad\).
To verify this, it suffices to show that \(\bPosition{\shD} = \Position{\Hexad}\).
Since \(\Winning{\Hexad}\) equals the block set \(\shBlock\) of \(\shD\),
it follows from Theorem <ref> that \(\Position{\Hexad} \subseteq \bPosition{\shD}\).
We show that \(\bPosition{\ymod{\shD}} \subseteq \Position{\Hexad}\).
If \(B \in \shBlock\) ($= \Winning{\Hexad}$), then \(B \in \Position{\Hexad}\), so \(\displaystyle \sum_{b \in B} b \ge 21\).
This implies that if \(\ccP \in \bPosition{\ymod{\shD}}\), then \(\displaystyle \sum_{p \in \ccP} p \ge 21\).
Thus \(\bPosition{\ymod{\shD}} \subseteq \Position{\Hexad}\). Therefore \(\bPosition{\ymod{\shD}} = \Position{\Hexad}\).

In this paper, we will investigate an \(S(t, t + 1, v)\) by using the above games obtained from Welter's game.
Incidentally, we can also consider games obtained from other than Welter's game to study \(S(t, t + m, v)\), especially when \(\ccm > 1\).[If \(\cD\) is an \(\ccS(\cct, \cct + \ccm, \ccv)\) with \(\ccm > 1\), then we can show that the number of positions in \(\DWel{\cD}\) always equals \(\lambda_0 + \bigl(\lambda_0\cck(\ccv - \cck)/2\bigr)\) by Lemma <ref>. Thus to investigate \(\cD\) by using its game distribution, we have to consider other games, for example, \(\Induced{\Gamma}{\bPosition{\Block}[\Gamma]}[\bigcbrackets]\) described in Remark <ref>.]
For example, let \(\cck = \cct + \ccm\) and let \(\Wel{\ccv}{\cck}^m\) be the game with position set \({[v] \choose k}\) and edge set

\[
\biggset{(P, Q) \in {[v] \choose k}^2 : P \neq Q, \text{\ there is a walk from\ } P \text{\ to } Q \text{\ of length at most\ } m \text{\ in\ } \Wel{\ccv}{\cck} }.
\]

For example, \(\bigl(\set{1, 4, 5}, \set{0, 2, 5}\bigr)\) is an edge in \(\Gamma_{6, 3}^2\) since \(\bigl(\set{1, 4, 5}, \set{0, 4, 5}, \set{0, 2, 5}\bigr)\) is a walk of length 2 in \(\Wel{6}{3}\).
Note that \(\Wel{\ccv}{\cck}^1\) is Welter's game \(\Wel{\ccv}{\cck}\). Let \(\Gamma = \Wel{\ccv}{\cck}^m\) and let \(\cD\) be an \(S(t, \cck, \ccv)\) with block set \(\Block\).
Then we can see that \(\Block\) is an independent set in \(\Gamma\).
Therefore the \(\sP\)-position set of \(\Induced{\Gamma}{\bPosition{\Block}[\Gamma]}[\bigcbrackets]\) is equal to \(\Block\).

p8-r14As we have mentioned, a game graph itself can be considered as a (short or long) impartial game
by adding a new vertex described below if necessary; our construction also works after adding the new vertex.
Let \(\Gamma\) be a game graph with at least one vertex.
If \(\ccP\) and \(\ccQ\) are two vertices in \(\Gamma\), then \(\ccQ\) is called a descendant of \(\ccP\) if there is a path from \(\ccP\) to \(\ccQ\).
A short impartial game can be defined as a vertex \(\ccP\) in \(\Gamma\) and a position in \(\ccP\) as a descendant of \(\ccP\).
Thus if \(\Gamma\) has a vertex \(\ccP\) such that the set of descendants of \(\ccP\) equals \(\Position{\Gamma}\),
then we can identify \(\Gamma\) with \(\ccP\), so \(\Gamma\) can be considered as a short impartial game.
For example, if \(\Gamma\) is Welter's game \(\Wel{\ccv}{\cck}\), then
the vertex \(\set{\ccv - \cck, \ccv - \cck + 1, \dotsc, \ccv - 1}\) satisfies the above condition.
Even when \(\Gamma\) does not have such a vertex,
we can add a new vertex satisfying this condition to \(\Gamma\) while preserving its \(\sP\)-positions as follows.
Let \(\ccP_{\infty}\) be a new vertex and let \(\tilde{\Gamma}\) be a digraph
with vertex set \(\Position{\Gamma} \cup \set{\ccP_\infty}\) and edge set

\[
\Edge{\Gamma} \cup \bigset{(\ccP_\infty, \ccP) : \ccP \in \Position{\Gamma}}.
\]

Then we can identify \(\tilde{\Gamma}\) with \(\ccP_\infty\).
Note that if \(\bigset{\lg_{\Gamma}(\ccP) : \ccP \in \Position{\Gamma}} = \NN\),
then \(\lg_{\tilde{\Gamma}}(\ccP_\infty)\) is not finite, which equals the first infinite ordinal \(\omega\),
and hence \(\tilde{\Gamma}\) does not satisfy (<ref>).
Such \(\tilde{\Gamma}\) is called a long impartial game.
Even if \(\tilde{\Gamma}\) is long, our construction works also when we use \(\tilde{\Gamma}\) instead of \(\Gamma\) because
\(\ccP_\infty\) is an \(\sN\)-position and \(\Winning{\tilde{\Gamma}} = \Winning{\Gamma}\).

§ GAME DISTRIBUTIONS

We introduce the game distribution of a Steiner system in this section.
The Steiner system \(\shD\) will be characterized by using its game distribution.
Hereafter, for \(\ccP \in {[\ccv] \choose \cck}\), let

\[
\InNeighbors{\ccP} = \InNeighbors{\ccP}[\Wel{\ccv}{\cck}] \tand \OutNeighbors{\ccP} = \OutNeighbors{\ccP}[\Wel{\ccv}{\cck}].
\]

For a \(\design{\cct}{\ccv, \cck, \lambda}\ \cD\) and a permutation \(\pi\) in \(\Sym([\ccv])\), let \(\cD^\pi\) denote the design obtained from \(\cD\) by applying \(\pi\), that is, \(\cD^\pi = \bigl([\ccv], \Block[\cD]^\pi\bigr)\), where
\(\Block[\cD]^\pi = \bigset{\ccB^\pi : \ccB \in \Block[\cD]}\) and \(\ccB^\pi = \bigset{\ccb^\pi : \ccb \in \ccB}\).

\[
\Orbit{\cD} = \bigset{\cD^\pi  : \pi \in \Sym([\ccv])}.
\]

For example, if \(\cD = \bigl([4], \bigfamily{\set{0, 2}, \set{1, 3}}\bigr)\), then

\begin{align*}
\Orbit{\cD} &= \bigset{\cD, \cD^{(1\ 2)}, \cD^{(2\ 3)}} \\
&= \Bigset{\bigl([4], \bigfamily{\set{0, 2}, \set{1, 3}}\bigr),\ \bigl([4], \bigfamily{\set{0, 1}, \set{2, 3}}\bigr),\ \bigl([4], \bigfamily{\set{0, 3}, \set{1, 2}}\bigr)}.
\end{align*}

Note that

\[
\size{\Orbit{\cD}} = \frac{\size{\Sym([\ccv])}}{\size{\Aut(\cD)}} = \frac{\ccv!}{\size{\Aut(\cD)}}.
\]

Let \(\Freq{\cD}(\ccn)\) denote the number of designs \(\cD' \in \Orbit{\cD}\) such that
the corresponding game \(\DWel{\cD'}\) has \(\ccn\) positions, that is,

\[
\Freq{\cD}(\ccn) = \size{\Set{\cD' \in \Orbit{\cD} : \msize{\bPosition{\cD'}} = \ccn}}.
\]

The function \(\Freq{\cD}\) will be called the game distribution of \(\cD\) (with respect to \(\Wel{\ccv}{\cck}\)).

Let \(\cD\) be an \(\ccS(1, 2, 4)\).
As we have seen in the introduction, the game distribution of \(\cD\) is as follows:

\(\ccn\)     4     5     6     Total

\(\Freq{\cD}(\ccn)\)     1     1     1     3

Let \(\cD\) be an \(S(2, 3, 7)\).
Then the game distribution of \(\cD\) is as follows:

\(\ccn\)     28     29     30     31     32     33     34     35     Total

\(\Freq{\cD}(\ccn)\)     1     3     5     6     6     5     3     1     30

Note that this distribution is symmetric, that is, \(\Freq{\cD}(\ccn) = \Freq{\cD}(63 - \ccn)\).
Incidentally, the game distribution of a Steiner system is not always symmetric.
For example, if \(\cD\) is an \(S(2, 3, 9)\), then its game distribution is as follows:
= 1mm

\(\ccn\)     68     69     70     71     72     73     74     75     76     77     78     79     80     Total

\(\Freq{\cD}(\ccn)\)     1     6     16     36     77     94     116     129     131     104     74     39     17     840

Let \(\cD\) be an \(S(5, 6, 12)\).
The game distribution of \(\cD\) is as follows:
= 1mm

\(\ccn\)     \(905\)     \(906\)     \(907\)     \(908\)     \(909\)     \(910\)     \(911\)     \(912\)     \(913\)     \(914\)     \(915\)     \(916\)     \(\mytext{Total}\)

\(\Freq{\cD}(\ccn)\)     \(1\)     \(10\)     \(42\)     \(150\)     \(351\)     \(650\)     \(1012\)     \(1237\)     \(939\)     \(532\)     \(115\)     \(1\)     \(5040\)

Moreover, \(\DWel{\shD}\) is the hexad game and is the unique minimum game, that is, \(\size{\bPosition{\shD}} = 905\).

Theorem <ref> can be obtained by computer.

Let \(\cD\) be the unique \(S(5, 6, 12)\) with \(\size{\bPosition{\cD}} = 916\).

\begin{align*}
{[12] \choose 6} \setminus \bPosition{\cD} = \{&\set{0, 1, 2, 3, 8, 9}, \set{0, 1, 2, 4, 7, 9}, \set{0, 1, 2, 4, 7, 10}, \set{0, 1, 2, 5, 7, 8}, \\
&\set{0, 1, 3, 5, 6, 8}, \set{0, 1, 3, 5, 7, 9}, \set{0, 1, 4, 5, 6, 7}, \set{0, 2, 3, 5, 6, 8}\}
\end{align*}

and the block set \(\Block[\cD]\) can be obtained from the following MINIMOG:

We close this section by remarking that the game distribution of \(\ccS(1, 2, 2 \ccv)\) can be calculated as follows.
If \(\cD\) is an \(S(1, 2, 2v)\), then

\begin{equation}
\label{equ:exm:1-2-2v-formula}
\sum_{n = 0}^\infty  \Freq{\cD}(\ccn) \ccx^{\ccn} = \ccx^{v^2} \prod_{i = 1}^{\ccv} \frac{\ccx^{2i - 1} - 1}{\ccx - 1}.
\end{equation}

For example, if \(\cD\) is an \(\ccS(1, 2, 6)\), then its game distribution and \(\sum \Freq{\cD}(\ccn) \ccx^\ccn\) are as follows:

\(\ccn\)     9     10     11     12     13     14     15     Total

\(\Freq{\cD}(\ccn)\)     1     2     3     3     3     2     1     15

\[
\sum_{\ccn = 0}^\infty \Freq{\cD}(\ccn) \ccx^n = \ccx^9 (\ccx^2 + \ccx + 1)(\ccx^4 + \ccx^3 + \ccx^2 + \ccx + 1).
\]

We sketch the proof.
Let \(\Freq~{\cD}(\ccn)\) denote the number of designs \(\cD' \in \Orbit{\cD}\) such that
the corresponding game \(\DWel{\cD'}\) has \(\ccn\) non-positions, that is,

\[
\Freq~{\cD}(\ccn) = \size{\Set{\cD' \in \Orbit{\cD} : \msize{\bPosition~{\cD'}} = \ccn}},
\]

where \(\bPosition~{\cD} = {[2 \ccv] \choose 2} \setminus \bPosition{\cD}\).
Since \(\bigsize{\bPosition~{\cD}} + \bigsize{\bPosition{\cD}} = \binom{2v}{2} = \ccv(2\ccv - 1)\), it follows that \(\Freq~{\cD}(\ccn) = \Freq{\cD}(\ccv(2 \ccv - 1) - \ccn)\).
We first show that

\begin{equation}
\label{equ:exm:1-2-2v}
\ymod{\sum_{n = 0}^\infty  \Freq~{\cD}(\ccn) \ccx^{\ccn}}  =  \prod_{i = 1}^{\ccv} \frac{\ccx^{2i - 1} - 1}{\ccx - 1}.
\end{equation}

Let \(\Psi_{\ccv}(\ccx)\) be the left-hand side of (<ref>).
We show (<ref>) by induction on \(\ccv\).
If \(\ccv = 1\), then \(\Freq~{\cD}(0) = 1\) and \(\Freq~{\cD}(\ccn) = 0\) for \(\ccn \ge 1\), so (<ref>) holds.
Suppose that \(\ccv \ge 2\), and let \(\set{0, \ccw} \in \Block[\cD]\).
We calculate \(\msize{\bPosition~{\cD}}\).
The number of \(\ccP \in \bPosition~{\cD}\) with \(\ccP \cap \set{0, \ccw} \neq \emptyset\)
equals \(\ccw - 1\) since the set of such \(\ccP\) is \(\bigfamily{\set{0, 1}, \dotsc, \set{0, \ccw - 1}}\).
Moreover, the number of \(\ccP \in \bPosition~{\cD}\) with \(\ccP \cap \set{0, \ccw} = \emptyset\) (i.e., \(\ccP \subseteq [2 \ccv] \setminus \set{0, \ccw}\))
equals \(\msize{\bPosition~{\cE}}\), where \(\cE\) is the \(\ccS(1, 2, 2 \ccv - 2)\) described below.
Write \([2 \ccv] \setminus \set{0, \ccw} = \set{\cca_0, \dotsc, \cca_{2 \ccv - 3}}\) with \(\cca_0 < \dotsb < \cca_{2 \ccv - 3}\),
and let \(\phi\) be the bijection \([2v] \setminus \set{0, \ccw} \ni \cca_\cci \mapsto \cci \in [2 \ccv - 2]\).
Note that \(\phi\) is order-preserving, that is, \(\phi(\cca) < \phi(\ccb)\) if and only if \(\cca < \ccb\).
Let \(\cE = \bigl([2 \ccv - 2], \bigset{\phi(\ccB) : \ccB \in \Block[\cD], \ccB \neq \set{0, \ccw}}\bigr)\).
Then \(\cE\) is an \(\ccS(1, 2, 2 \ccv - 2)\).
If \(\ccQ \subseteq [2 \ccv] \setminus \set{0, \ccw}\),
then \(\ccQ \in \bPosition~{\cD}\) if and only if \(\phi(\ccQ) \in \bPosition~{\cE}\)  since \(\phi\) is order-preserving.
Therefore the number of \(\ccP \in \bPosition~{\cD}\) with \(\ccP \subseteq [2 \ccv] \setminus \set{0, \ccw}\)
is equal to \(\msize{\bPosition~{\cE}}\). Thus \(\msize{\bPosition~{\cD}} = \ccw - 1 + \msize{\bPosition~{\cE}}\).
It follows from the induction hypothesis that

\[
\Psi_{\ccv}(\ccx) = (1 + \ccx + \dotsb + \ccx^{2\ccv - 2}) \Psi_{\ccv - 1}(\ccx) = \prod_{i = 1}^{\ccv}\frac{\ccx^{2i - 1} - 1}{\ccx - 1}.
\]

Therefore (<ref>) holds.
Since \(\Freq{\cD}(\ccn) = 0\) for \(\ccn > \ccv(2 \ccv - 1)\) and \(\Freq{\cD}(\ccn) = \Freq~{\cD}(\ccv(2\ccv - 1) - \ccn)\),
we see that

\begin{align*}
\sum_{n = 0}^{\infty}  \Freq{\cD}(\ccn) \ccx^{\ccn} &= \sum_{n = 0}^{\ccv(2 \ccv - 1)}  \Freq~{\cD}(\ccv (2 \ccv - 1) - \ccn) \ccx^{\ccn}  = \sum_{n = 0}^{\ccv(2 \ccv - 1)}  \Freq~{\cD}(\ccn) \ccx^{\ccv (2 \ccv - 1) - \ccn}  \\
&= \ccx^{\ccv(2 \ccv - 1)} \prod_{i = 1}^{\ccv} \ymod{(1 + x^{-1} + \dotsb + x^{-2i + 2})} = \ccx^{\ccv^2} \prod_{i = 1}^{\ccv}\frac{\ccx^{2i - 1} - 1}{\ccx - 1}.
\end{align*}

§ SYMMETRIC COMPONENTS

We show that the game distribution of an \(S(\cct, \cct + 1, \ccv)\) can be decomposed into symmetric components.
Using symmetric components, we characterize projective Steiner triple systems in Section <ref>.

For a \(\design{\cct}{\ccv, \cck, \lambda}\) \(\cD\) and a non-block \(\ccP \in {[\ccv] \choose k} \setminus \Block[\cD]\), a block \(\ccB \in \Block[\cD]\) is called an out-block of \(\ccP\) if \(\ccB \in \OutNeighbors{\ccP}\).
Define \(\cca_i(\cD)\) to be the number of non-blocks with \(i\) out-blocks, that is,

\[
\cca_i(\cD) = \size{\Set{\ccP \in {[\ccv] \choose \cck} \setminus \Block[\cD]: \bigsize{\OutNeighbors{\ccP} \cap \Block[\cD]} = i}}.
\]

For example, if \(\cD = \bigl([4], \bigfamily{\set{0, 2}, \set{1, 3}}\bigr)\), then \(\set{0, 1}\) has no out-blocks, \(\set{0, 3}\) and \(\set{1, 2}\) has an out-block \(\set{0, 2}\), and \(\set{2, 3}\) has two out-blocks \(\set{0, 2}\) and \(\set{1, 3}\), so

\[
\cca_0(\cD) = \size{\bigfamily{\set{0, 1}}} = 1,\ \cca_1(\cD) = \size{\bigfamily{\set{0, 3}, \set{1, 2}}} = 2,\ \cca_2(\cD) = \size{\bigfamily{\set{2, 3}}} = 1.
\]

Note that \(\size{\bPosition{\cD}} = \size{\Block[\cD]} + \sum_{i \ge 1} \cca_i(\cD)\) and \(\msize{\bPosition~{\cD}} = \cca_0(\cD)\),
where \(\bPosition~{\cD} = {[\ccv] \choose \cck} \setminus \bPosition{\cD}\).
Moreover, if \(\Block[\cD]\) is an independent set in \(\Wel{\ccv}{\cck}\), then \(\cca_{\cci}(\cD) = 0\) for \(\cci \ge \cck + 1\).
Indeed, if \(\size{\OutNeighbors{\ccP} \cap \Block[\cD]} \ge \cck + 1\) for some \(\ccP \in {[\ccv] \choose \cck} \setminus \Block[\cD]\),
then \(\ccP^{(\ccp\ \ccq)}, \ccP^{(\ccp\ \ccq')} \in \Block[\cD]\) for some \(\ccp \in \ccP\) and some \(\ccq, \ccq' \not \in \ccP\) with \(\ccq' < \ccq\),
so \(\Block[\cD]\) is not an independent set because \((\ccP^{(\ccp\ \ccq)}, \ccP^{(\ccp\ \ccq')})\) is an edge of \(\Wel{\ccv}{\cck}\).

\[
\ccs(\cD) = \Set{\cca_0(\cD') + \cca_{\cck}(\cD') : \cD' \in \Orbit{\cD}}
\]

\[
\Orbit{\cD}[\alpha] = \Set{\cD' \in \Orbit{\cD} : \cca_0(\cD') + \cca_{\cck}(\cD') = \alpha}
\]

for \(\alpha \in \ccs(\cD)\).

\[
\Freq{\cD}(\ccn)[\alpha] = \size{\Set{\cD' \in \Orbit{\cD}[\alpha] :  \msize{\bPosition{\cD'}} = \ccn}}
\]

\begin{align*}
\Freq~{\cD}(\ccn)[\alpha] &= \size{\Set{\cD' \in \Orbit{\cD}[\alpha] :  \msize{\bPosition~{\cD'}} = \ccn}} \\
&=  \bigsize{\bigset{\cD' \in \Orbit{\cD}[\alpha] :  \cca_0(\cD') = \ccn}}. \mylink{p13-25}
\end{align*}

By definition,

\[
\Freq{\cD}(\ccn) = \sum_{\alpha \in s(\cD)} \Freq{\cD}(\ccn)[\alpha].
\]

Let \(\cD\) be an \(S(\cct, \cct + 1, \ccv)\).
Then the following proposition says that \(\Freq{\cD}(\ccn)[\alpha]\) is symmetric.
From this, the function \(\Freq{\cD}[\alpha]\) is called a symmetric component of the game distribution of \(\cD\).

If \(\cD\) is an \(S(\cct, \cck, \ccv)\) with \(\cck = \cct + 1\), then

\[
\Freq~{\cD}(\ccn)[\alpha] = \Freq~{\cD}(\alpha - \ccn)[\alpha]
\]

for \(\ccn \in \NN\). In particular,

\[
\Freq{\cD}(\ccn)[\alpha] = \Freq{\cD}(2 {\ccv \choose \cck} - \alpha - \ccn)[\alpha].
\]

It suffices to show the assertion for \(\alpha = \cca_0(\cD) + \cca_{\cck}(\cD)\),
since \(\Freq~{\cD}(\ccn)[\alpha] = \Freq~{\cD'}(\ccn)[\alpha]\) for \(\cD' \in \Orbit{\cD}\).
Let \(\Block = \Block[\cD]\) and \(\ccP \in {[\ccv] \choose \cck} \setminus \Block\).
We first show that

\begin{equation}
\label{equ:prop:symmetric-components-sum}
\bigsize{\OutNeighbors{\ccP} \cap \Block} + \bigsize{\InNeighbors{\ccP} \cap \Block} = \cck.
\end{equation}

Let \(\ccp \in \ccP\).
Since \(\cck = \cct + 1\), there is a unique \(\ccp' \in [\ccv]\) such that
\(\ccP^{(\ccp\ \ccp')} \in \Block\).
Note that \(\size{\OutNeighbors{\ccP} \cap \Block}\) equals the number of \(\ccp \in \ccP\) with \(\ccp' < \ccp\).
Similarly,  \(\size{\InNeighbors{\ccP} \cap \Block}\) equals the number of \(\ccp \in \ccP\) with \(\ccp' > \ccp\).
Hence (<ref>) holds.

Let \(\cpi\) be the permutation \(\cci \mapsto \ccv - 1 - \cci\) of \([\ccv]\).
We next show that \(\cD^\cpi \in \Orbit{\cD}[\alpha]\).
Since \(\ccp < \ccq \iff \ccp^\cpi > \ccq^\cpi\) for \(\ccp, \ccq \in [\ccv]\), it follows that  \(\bigsize{\InNeighbors{\ccP} \cap \Block} = \bigsize{\OutNeighbors{\ccP^\cpi} \cap \Block^\cpi}\).
By (<ref>),

\[
\bigsize{\OutNeighbors{\ccP} \cap \Block} = i \iff \bigsize{\OutNeighbors{\ccP^\cpi} \cap \Block^\cpi} = \cck - \cci.
\]

This implies that \(\cca_i(\cD) = \cca_{\cck - i}(\cD^\cpi)\), and hence that
\(\cca_0(\cD^\cpi) + \cca_{\cck}(\cD^\cpi) = \cca_\cck(\cD) + \cca_0(\cD) = \alpha\).
Thus \(\cD^\cpi \in \Orbit{\cD}[\alpha]\).
We also see that

\[
\cca_0(\cD) = \ccn \iff \cca_0(\cD^\cpi) = \alpha - \ccn.
\]

Therefore \(\Freq~{\cD}(\ccn)[\alpha] = \Freq~{\cD}(\alpha - \ccn)[\alpha]\).

The symmetric components of the game distribution of an \(S(2, 3, 9)\) are as shown in Table <ref>.

= 1mm

The symmetric components of an \(S(2, 3, 9)\).

\(\ccn\)     68     69     70     71     72     73     74     75     76     77     78     79     80     Total

[0mm]0mm3.6mm \(\Freq{\cD}(\ccn)[24]\)     1     1     1     1     1     1     1     1     1                         9

\(\Freq{\cD}(\ccn)[22]\)          5     6     6     7     6     7     6     6     5                    54

\(\Freq{\cD}(\ccn)[20]\)               9     14     24     23     22     23     24     14     9               162

\(\Freq{\cD}(\ccn)[18]\)                    15     28     40     49     54     49     40     28     15          318

\(\Freq{\cD}(\ccn)[16]\)                         17     24     37     45     51     45     37     24     17     297

\(\Freq{\cD}(\ccn)\)     1     6     16     36     77     94     116     129     131     104     74     39     17     840

As shown in Table <ref>, the game distribution of an \(S(2, 3, 7)\) has a unique symmetric component.
This property characterizes projective Steiner triple systems as we will see in Theorem <ref>.

= 1mm

The symmetric component of an \(S(2, 3, 7)\).

\(n\)     28     29     30     31     32     33     34     35     Total

[0mm]0mm3.6mm \(\Freq{\cD}(\ccn)[7]\)     1     3     5     6     6     5     3     1     30

\(\Freq{\cD}(\ccn)\)     1     3     5     6     6     5     3     1     30

Let \(\cD\) be an \(S(5, 6, 12)\).

\begin{equation}
\label{equ:exm-5-6-12-comp}
\cca_i(\cD) = \cca_{6 - i}(\cD),
\end{equation}

so the symmetric components of \(\Freq{\cD}\) are as shown in Table <ref>.
We can prove (<ref>) as follows.
If \(\ccB \in \Block[\cD]\), then \(\overline{\ccB} \in \Block[\cD]\), where \(\overline{\ccB} = [12] \setminus \ccB\).
This implies that if \(\ccP \in {[12] \choose 6} \setminus \Block[\cD]\) and \(\ccP^{(\ccp\ \ccq)} \in \Block[\cD]\),
then \(\overline{\ccP} \in {[12] \choose 6} \setminus \Block[\cD]\) and \(\overline{\ccP}^{(\ccp\ \ccq)} = \overline{\ccP^{(\ccp\ \ccq)}} \in \Block[\cD]\).
For example, if \(\cD = \shD\) and \(\ccP = \set{1, 2, 3, 4, 5, 11}\), then \(\ccP^{(5\ 0)} = \set{1, 2, 3, 4, 0, 11} \in \Block[\cD]\) and \(\overline{\ccP}^{(5\ 0)} = \set{0, 6, 7, 8, 9, 10}^{(5\ 0)} = \set{5, 6, 7, 8, 9, 10} \in \Block[\cD]\).
Note that if \(\ccP^{(\ccp\ \ccq)} \in \OutNeighbors{\ccP}\), then \(\overline{\ccP}^{(\ccp\ \ccq)} \in \InNeighbors{\overline{\ccP}}\).
It follows that if \(\size{\OutNeighbors{\ccP} \cap \Block[\cD]} = i\), then \(\size{\OutNeighbors{\overline{\ccP}} \cap \Block[\cD]} = 6 - i\).
Hence \(\cca_i(\cD) = \cca_{6 - i}(\cD)\), so its symmetric components are as shown in Table <ref>.
The symmetric components of the game distribution of an \(S(4, 5, 11)\) are also shown in Table <ref>.

= 1mm

The symmetric components of an \(\ccS(5, 6, 12)\).

\(\ccn\)     905     906     907     908     909     910     911     912     913     914     915     916     Total

[0mm]0mm3.6mm \(\Freq{\cD}(\ccn)[38]\)     1                                                            1

\(\Freq{\cD}(\ccn)[36]\)          10                                                       10

\(\vdots\)                              \(\dotsm\)     \(\dotsm\)                              \(\vdots\)

\(\Freq{\cD}(\ccn)[18]\)                                                       115          115

\(\Freq{\cD}(\ccn)[16]\)                                                            1     1

\(\Freq{\cD}(\ccn)\)     1     10     42     150     351     650     1012     1237     939     532     115     1     5040

= 1mm

The symmetric components of an \(S(4, 5, 11)\).

\(\ccn\)     443     444     445     446     447     448     449     450     451     452     453     454     Total

[0mm]0mm3.6mm \(\Freq{\cD}(\ccn)[29]\)     1     1     3                         3     1     1               10

\(\Freq{\cD}(\ccn)[28]\)          7     7     12     8     8     8     12     7     7               76

\(\Freq{\cD}(\ccn)[27]\)          2     25     62     62     77     77     62     62     25     2          456

\(\Freq{\cD}(\ccn)[26]\)               7     44     106     155     212     155     106     44     7          836

\(\Freq{\cD}(\ccn)[25]\)                    31     167     220     345     345     220     167     31          1526

\(\Freq{\cD}(\ccn)[24]\)                    1     8     140     259     402     259     140     8     1     1218

\(\Freq{\cD}(\ccn)[23]\)                              50     101     216     216     101     50          734

\(\Freq{\cD}(\ccn)[22]\)                                   10     36     58     36     10          150

\(\Freq{\cD}(\ccn)[21]\)                                        6     9     9     6          30

\(\Freq{\cD}(\ccn)[20]\)                                             1     2     1          4

\(\Freq{\cD}(\ccn)\)     1     10     42     150     351     650     1012     1237     939     532     115     1     5040

§ A CHARACTERIZATION OF PROJECTIVE STEINER TRIPLE SYSTEMS

p14-thmIf \(\cD\) is an \(S(2, 3, \ccv)\),
then \(\cD\) is projective if and only if
its game distribution has a unique symmetric component, that is, \(\size{\ccs(\cD)} = 1\).

To prove Theorem <ref>, we show two lemmas.

Let \(\cD\) be an \(S(2, 3, \ccv)\).
The following lemma enables us to calculate \(\cca_0(\cD) + \cca_3(\cD)\).
Recall that \(\lambda_i\), defined in (<ref>), is the number of blocks of \(\cD\) containing \(i\) given points.

Let \(\cD\) be a \(\design{\cct}{\ccv, \cck, \lambda}\) with block set \(\Block\).

* If \(\cct \ge 1\) and \(\Block\) is an independent set in \(\Wel{\ccv}{\cck}\), then

\[
\displaystyle \sum_{i = 0}^k i \cca_i(\cD) = \frac{\lambda_0 \cck(\ccv - \cck)}{2}.
\]

* If \(\cD\) is an \(S(2, 3, \ccv)\), then

\[
\cca_0(\cD) + \cca_3(\cD) = \sum_{\set{B, C} \in {\Block \choose 2}} \ccI(\ccB, \ccC) - \frac{\ccv(\ccv - 1)(\ccv - 3)}{12},
\]

where \(\ccI(\ccB, \ccC) = \size{\InNeighbors{\ccB} \cap \InNeighbors{\ccC}}\).

(1) Let

\[
\IntersectPositions{\cD}{\cci} = \biggfamily{\ccP \in {[\ccv] \choose \cck} \setminus \Block : \bigsize{\OutNeighbors{\ccP} \cap \Block} = i}. \mylink{p16-6}
\]

Then \(\cca_i(\cD)= \size{\IntersectPositions{\cD}{\cci}}\).
Since \(\Block\) is an independent set,
we see that
\(\bigcup_{i = 0}^{\cck} \IntersectPositions{\cD}{\cci} = {[\ccv] \choose \cck} \setminus \Block\)

\begin{align*}
\sum_{i = 0}^{\cck} i \cca_i(\cD) &= \sum_{i = 0}^{\cck} \Bigsize{\Bigfamily{(\ccP, \ccB) : \ccP \in \IntersectPositions{\cD}{\cci},\ \ccB \in \OutNeighbors{\ccP} \cap \Block}} \\
&= \biggsize{\biggfamily{(\ccP, \ccB) : \ccP \in {[\ccv] \choose \cck} \setminus \Block,\ \ccB \in \OutNeighbors{\ccP} \cap \Block} } \\
&= \Bigsize{\Bigfamily{\rule[0mm]{0mm}{3.4mm}(\ccP, \ccB) : \ccB \in \Block,\ \ccP \in \InNeighbors{\ccB}}} \\
&= \sum_{\ccB \in \Block} \bigsize{\InNeighbors{\ccB}}.\mylink{p16-12}
\end{align*}

Let \(\ccB \in \Block\) and write \(\ccB = \set{\ccb_1, \dotsc, \ccb_k}\) with \(\ccb_1 < \dotsb < \ccb_k\).
Then \(\ccP \in \InNeighbors{\ccB}\) if and only if \(\ccP = \ccB^{(\ccb_i\ \ccp)}\) for some \(\ccb_i\) and \(\ccp \not \in \ccB\) with \(\ccp > \ccb_i\).
The number of such \(\ccp\) equals \(\ccv - 1 - \ccb_i - (\cck - i)\). Hence

\begin{align*}
\size{\InNeighbors{\ccB}} &= \sum_{i = 1}^\cck \bigl(\ccv - 1 - \ccb_i - (\cck - i)\bigr)
= \cck(\ccv - 1) - \sum_{\ccb \in \ccB} \ccb - \frac{\cck(\cck - 1)}{2}.
\end{align*}

\begin{align*}
\sum_{\ccB \in \Block} \sum_{\ccb \in \ccB} \ccb &= (0 + 1 + \dotsb + \ccv - 1) \lambda_1 \\
&= \frac{v(v - 1)}{2} \frac{{v - 1 \choose t - 1}}{{k - 1 \choose t - 1}} \lambda \\
&= \frac{k(v - 1)}{2} \frac{{v \choose t}}{{k \choose t}} \lambda \\
&= \frac{\cck(\ccv - 1) \lambda_0}{2},
\end{align*}

it follows that

\begin{align*}
\sum_{\ccB \in \Block} \bigsize{\InNeighbors{\ccB}} &= \lambda_0 \left(\cck(\ccv - 1) - \frac{\cck(\ccv - 1)}{2} - \frac{\cck(\cck - 1)}{2} \right)
= \frac{\lambda_0 \cck(\ccv - \cck)}{2}.
\end{align*}

(2) Let \(\cca_i = \cca_i(\cD)\).
We first show that p17-3

\begin{equation}
\label{equ:lem:a0a3}
\sum_{\cci = 0}^3 {i \choose 2} \cca_i = \cca_2 + 3 \cca_3 = \sum_{\set{\ccB, \ccC} \in {\Block \choose 2}} \ccI(\ccB, \ccC).
\end{equation}

By the definition of \(\cca_i\),

\begin{align*}
\sum_{\cci = 0}^3 {i \choose 2} \cca_i &=
\sum_{\cci = 0}^3 \size{\Set{\bigl(\ccP, \set{\ccB, \ccC}\bigr) : \ccP \in \IntersectPositions{\cD}{\cci},\ \set{\ccB, \ccC} \in {\OutNeighbors{\ccP} \cap \Block \choose 2}}} \\
&= \size{\Set{\bigl(\ccP, \set{\ccB, \ccC}\bigr) : \ccP \in {[\ccv] \choose 3} \setminus \Block,\ \set{\ccB, \ccC} \in {\OutNeighbors{\ccP} \cap \Block \choose 2}}} \\
&= \size{\Set{\bigl(\ccP, \set{\ccB, \ccC}\bigr) : \set{\ccB, \ccC} \in {\Block \choose 2},\ \ccP \in \InNeighbors{\ccB} \cap \InNeighbors{\ccC}}} \\
&= \sum_{\set{B, C} \in {\Block \choose 2}} \ccI(\ccB, \ccC).
\end{align*}

We now calculate \(\cca_0 + \cca_3\).
Note that \(\lambda_0 = \ccv(\ccv - 1)/6\).
By (1),

\[
\sum_{\cci = 0}^3 \cci \cca_i = \cca_1 + 2 \cca_2 + 3 \cca_3 = \frac{\lambda_0 3(\ccv - 3)}{2} = \frac{\ccv (\ccv - 1)(\ccv - 3)}{4}.
\]

\[
\sum_{\cci = 0}^3  \cca_i = \cca_0 + \cca_1 + \cca_2 + \cca_3 = {\ccv \choose 3} - \lambda_0 = \frac{\ccv (\ccv - 1)(\ccv - 3)}{6},
\]

it follows that

\[
\sum_{\cci = 0}^3 \cci \cca_i - \sum_{\cci = 0}^3 \cca_i = - \cca_0 + \cca_2 + 2 \cca_3 = \frac{\ccv (\ccv - 1)(\ccv - 3)}{12}. \mylink{p17-14}
\]

\[
\cca_0 + \cca_3 + \frac{\ccv (\ccv - 1)(\ccv - 3)}{12} = \cca_2 + 3 \cca_3 = \sum_{\set{B, C} \in {\Block \choose 2}} \ccI(\ccB, \ccC).
\]

From Lemma <ref>, to calculate \(\cca_0 + \cca_3\), it is enough to compute \(\sum I(B, C)\).
To do this, the following easy lemma will be used.

p26-lemLet \(\ccB\) and \(\ccC\) be two distinct blocks of an \(S(2, 3, \ccv)\).

* If \(\ccI(\ccB, \ccC) \neq 0\), then \(\size{\ccB \cap \ccC} = 1\).

* If \(\ccB = \set{\ccx, \ccb, \ccb'}\), \(\ccC' = \set{\ccx, \ccc, \ccc'}\), \(\ccb < \ccb'\), and \(\ccb < \ccc < \ccc'\), then

\begin{equation}
\label{equ:lem:intersection}
\ccI(\ccB, \ccC) = [\ccc < \ccb'] + [\ccc' < \ccb'],
\end{equation}

where \([\ ]\) is the Iverson bracket notation, that is, \([\ccS] \Teq 1\) if a statement \(\ccS\) holds, and \([\ccS] = 0\) otherwise.

* If

\[
\ccI(\ccB, \ccC) \neq \ccI(\ccB^{(i\ i + 1)}, \ccC^{(i\ i + 1)}),
\]

then \(\set{\ccB, \ccC} = \bigfamily{\set{\cci, \ccx, \ccy}, \set{\cci + 1, \ccx, \ccz}}\) for some \(\ccx, \ccy, \ccz \in [\ccv]\) with \(\ccy \neq \ccz\).

(1) If \(\ccB \cap \ccC = \emptyset\), then \(\ccI(\ccB, \ccC) = 0\).
If \(\size{\ccB \cap \ccC} \ge 2\), then \(\ccB = \ccC\). Hence \(\size{\ccB \cap \ccC} = 1\).

(2) Since \(\ccb < \ccb'\) and \(\ccb < \ccc < \ccc'\), it follows that

\[
\InNeighbors{\ccB} \cap \InNeighbors{\ccC} = \begin{cases}
\emptyset & \tif \ccb' < \ccc, \\
\bigfamily{\set{\ccx, \ccb', \ccc'} } & \tif \ccc < \ccb' < \ccc', \\
\bigfamily{\set{\ccx, \ccb', \ccc'}, \set{\ccx, \ccb', \ccc}} & \tif \ccc' < \ccb'.
\end{cases}
\]

Thus (<ref>) holds.

(3) By (1), if \(\size{\ccB \cap \ccC} \neq 1\) then \(\ccI(\ccB, \ccC) = \ccI\bigl(\ccB^{(i\ i + 1)}, \ccC^{(i\ i + 1)}\bigr)\).
Let \(\ccB = \set{\ccx, \ccb, \ccb'}\) and \(\ccC = \set{\ccx, \ccc, \ccc'}\).
We may assume that \(\ccb < \ccb'\) and \(\ccb < \ccc < \ccc'\).

\[
[\ccy^{(i\ i + 1)} < \ccz^{(i\ i + 1)}] \neq [\ccy <\ccz], \mylink{p18-8}
\]

then \(\set{\ccy, \ccz} = \set{i, i + 1}\).
It follows from (2) that \(\set{i, i + 1} \in \bigfamily{\set{\ccb, \ccc}, \set{\ccb', \ccc}, \set{\ccb', \ccc'}}\).
Hence \(\set{\ccB, \ccC} = \bigfamily{\set{\ccx, \cci, \ccy}, \set{\ccx, \cci + 1, \ccz}}\) for some \(\ccy, \ccz \in [\ccv]\) with \(\ccy \neq \ccz\).

Proof. [Proof of Theorem <ref> ]

Let \(\cD\) be an \(S(2, 3, \ccv)\) with block set \(\Block\).

We first show that if \(\cD\) is projective,
then \(\size{\ccs(\cD)} = 1\).
By Lemma <ref>,

\[
\sum_{\set{\ccB, \ccC} \in {\Block \choose 2}} \ccI(\ccB, \ccC) = \sum_{\set{\ccB, \ccC} \in {\Block \choose 2},\ \size{\ccB \cap \ccC} = 1} \hspace{-2em} \ccI(\ccB, \ccC).
\]

Let \(\set{\ccx, \ccb, \ccb'}\) and \(\set{\ccx, \ccc, \ccc'}\) be two distinct blocks of \(\cD\).
We may assume that \(\ccb < \ccb'\) and \(\ccb < \ccc < \ccc'\). p18-16
Since \(\cD\) is projective, there are \(\ccy, \ccz \in [\ccv]\) such that \(\set{\ccy, \ccb, \ccc}\), \(\set{\ccy, \ccb', \ccc'}\), \(\set{\ccz, \ccb, \ccc'}\), and \(\set{\ccz, \ccb', \ccc}\) are blocks.
Thus we obtain the following triple of pairs of blocks:

\[
\Bigfamily{\, \bigfamily{\set{\ccx, \ccb, \ccb'}, \set{\ccx, \ccc, \ccc'}}, \quad \bigfamily{\set{\ccy, \ccb, \ccc}, \set{\ccy, \ccb', \ccc'}}, \quad \bigfamily{\set{\ccz, \ccb, \ccc'}, \set{\ccz, \ccb', \ccc}}\, }.
\]

By Lemma <ref>,

\begin{equation}
\label{equ:six-blocks-sum}
\begin{split}
\ccI\bigl(\set{\ccx, \ccb, \ccb'}&,  \set{\ccx, \ccc, \ccc'}\bigr) + \ccI\bigl(\set{\ccy, \ccb, \ccc},  \set{\ccy, \ccb', \ccc'}\bigr) + \ccI\bigl(\set{\ccz, \ccb, \ccc'}, \set{\ccz, \ccb', \ccc}\bigr) \\
&= [\ccc < \ccb'] + [\ccc' < \ccb'] + [\ccb' < \ccc] + [\ccc' < \ccc] + [\ccb' < \ccc'] + [\ccc < \ccc'] = 3.
\end{split}
\end{equation}

Note that every pair \(\set{\ccB, \ccC}\) of blocks with \(\size{\ccB \cap \ccC} = 1\) belongs to exactly one such triple and there are \(\ccv {\lambda_1 \choose 2}/3\) triples.

\[
\sum_{\set{\ccB, \ccC} \in {\ccB \choose 2},\ \size{\ccB \cap \ccC} = 1} \hspace{-2em} \ccI(\ccB, \ccC) = \frac{\ccv {\lambda_1 \choose 2}}{3} {3}  = \frac{\ccv (\ccv - 1)(\ccv - 3)}{8}.
\]

By Lemma <ref>,

\[
\cca_0(\cD) + \cca_3(\cD) = \sum_{\set{B, C} \in {\Block \choose 2}} \ccI(\ccB, \ccC) - \frac{\ccv(\ccv - 1)(\ccv - 3)}{12} = \frac{\ccv (\ccv - 1)(\ccv - 3)}{24}.
\]

Therefore \(\ccs(\cD) = \set{\ccv(\ccv - 1)(\ccv - 3)/24}\).

p17-11We next show that if \(\cD\) is not projective,
then \(\size{\ccs(\cD)} > 1\).
Note that \(\ccv \ge 9\).
Since \(\cD\) is not projective,
it follows from Remark <ref> that we may assume that

\[
\set{0, \ccv - \ymod{2}, 2}, \set{1, \ccv - \ymod{2}, 3}, \set{0, \ccv - \ymod{3}, 3}, \set{1, \ccv - \ymod{3}, 4} \in \Block
\]

by replacing \(\cD\) with some \(\cD' \in \Orbit{\cD}\) if necessary (see Figure <ref>).

The four blocks of \(\cD\).

We may also assume that \(\set{0, 1, \ccv - 1} \in \Block\).
We show that

\begin{equation}
\label{equ:thm-projective-claim}
\sum_{\set{\ccB, \ccC} \in {\Block \choose 2}} \ccI(\ccB, \ccC) - \ccI(\ccB, \ccC)^{(0\ 1)} \neq 0 \quad \tor \sum_{\set{\ccB, \ccC} \in {\Block \choose 2}} \ccI(\ccB, \ccC)^{(2\ 3)} - \ccI(\ccB, \ccC)^{(2\ 3)(0\ 1)} \neq 0,
\end{equation}

where \(\ccI(\ccB, \ccC)^{(0\ 1)} = \ccI(\ccB^{(0\ 1)}, \ccC^{(0\ 1)})\).
If \(\set{\ccB, \ccC} \in {\Block \choose 2}\) and \(\ccI(\ccB, \ccC) \neq \ccI(\ccB, \ccC)^{(0\ 1)}\),
then, by Lemma <ref>,

\[
\set{\ccB, \ccC} = \bigfamily{\set{0, \ccx, \ccy}, \set{1, \ccx, \ccz}}
\]

for some \(\ccx, \ccy, \ccz \in [\ccv]\) with \(\ccy \neq \ccz\);
note that \(\ccx \neq \ccv - 1\) since \(\set{0, 1, \ccv - 1} \in \Block\).
For \(\ccx \in \set{2, 3, \dotsc, \ccv - \ymod{2}}\), let \(\ccB_{\ccx} = \set{0, \ccx, \ccy_{\ccx}} \in \Block\) and \(\ccC_x = \set{1, \ccx, \ccz_{\ccx}} \in \Block\).
By assumption,

\begin{equation}
\label{equ:theorem-assumption}
\begin{split}
&\ccB_{\ccv - \ymod{2}} = \set{0, \ccv - \ymod{2}, 2},\ \ccC_{\ccv - \ymod{2}} = \set{1, \ccv - \ymod{2}, 3},\\
&\ccB_{\ccv - \ymod{3}} = \set{0, \ccv - \ymod{3}, 3},\ \ccC_{\ccv - \ymod{3}} = \set{1, \ccv - \ymod{3}, 4}.
\end{split}
\end{equation}

We see that

\begin{equation}
\label{equ:sumBC}
\sum_{\set{\ccB, \ccC} \in {\Block \choose 2}} \ccI(\ccB, \ccC) - \ccI(\ccB, \ccC)^{(0\ 1)} = \sum_{\ccx = 2}^{\ccv - 2} \ccI(\ccB_\ccx, \ccC_\ccx) - \ccI(\ccB_\ccx, \ccC_\ccx)^{(0\ 1)}.
\end{equation}

Similarly, by Lemma <ref>, if \(\set{\ccB, \ccC} \in {\Block \choose 2}\) and \(\ccI(\ccB, \ccC)^{(2\ 3)} \neq \ccI(\ccB, \ccC)^{(2\ 3)(0\ 1)}\), then

\[
\bigset{\ccB^{(2\ 3)}, \ccC^{(2\ 3)}} = \bigfamily{\set{0, \ccx, \ccy}^{(2\ 3)}, \set{1, \ccx, \ccz}^{(2\ 3)}}
\]

for some \(\ccx, \ccy, \ccz \in [\ccv]\) with \(\ccy \neq \ccz\),
and hence
\(\set{\ccB, \ccC} = \set{\ccB_{\ymod{\ccx}}, \ccC_{\ymod{\ccx}}}\).

\begin{equation}
\label{equ:sumBC23}
\sum_{\set{\ccB, \ccC} \in {\Block \choose 2}} \ccI(\ccB, \ccC)^{(2\ 3)} - \ccI(\ccB, \ccC)^{(2\ 3)(0\ 1)} = \sum_{\ccx = 2}^{\ccv - 2} \ccI(\ccB_\ccx, \ccC_\ccx)^{(2\ 3)} - \ccI(\ccB_\ccx, \ccC_\ccx)^{(2\ 3)(0\ 1)}.
\end{equation}

If \(\ccI(\ccB_{\ymod{\ccx}}, \ccC_{\ymod{\ccx}}) \neq \ccI(\ccB_{\ymod{\ccx}}, \ccC_{\ymod{\ccx}})^{\ymod{^{(2\ 3)}}}\),
then \(\set{\ccB_{\ccx}, \ccC_{\ccx}} = \bigfamily{\set{2, \ccx, \ccu}, \set{3, \ccx, \ccw}}\) for some \(\ccu, \ccw \in [\ccv]\),
so \(\ymod{\ccx} = \ccv - 2\) by (<ref>).
Similarly, if
\(\ccI(\ccB_{\ymod{\ccx}}, \ccC_{\ymod{\ccx}})^{\ymod{(0\ 1)}} \neq \ccI(\ccB_{\ymod{\ccx}}, \ccC_{\ymod{\ccx}})^{\ymod{(2\ 3)(0\ 1)}}\),
then \(\ymod{\ccx} = \ccv - \ymod{2}\).
Let \(\ccB_{\ymod{o}} = \ccB_{\ccv - \ymod{2}}\) and \(\ccC_{\ymod{o}} = \ccC_{\ccv - \ymod{2}}\).
By (<ref>) and (<ref>),

\begin{align*}
&\sum_{\set{\ccB, \ccC} \in {\Block \choose 2}} \ccI(\ccB, \ccC) - \ccI(\ccB, \ccC)^{(0\ 1)} - \left(\ccI(\ccB, \ccC)^{(2\ 3)} - \ccI(\ccB, \ccC)^{(2\ 3)(0\ 1)}\right)\\
&=  \sum_{\ccx = 2}^{\ccv - 2} \ccI(\ccB_\ccx, \ccC_\ccx) - \ccI(\ccB_\ccx, \ccC_\ccx)^{(0\ 1)} - \left(\ccI(\ccB_\ccx, \ccC_\ccx)^{(2\ 3)} - \ccI(\ccB_\ccx, \ccC_\ccx)^{(2\ 3)(0\ 1)}\right)\\
&=  \sum_{\ccx = 2}^{\ccv - 2} \ccI(\ccB_\ccx, \ccC_\ccx) - \ccI(\ccB_\ccx, \ccC_\ccx)^{(2\ 3)} - \left(\ccI(\ccB_\ccx, \ccC_\ccx)^{(0\ 1)} - \ccI(\ccB_\ccx, \ccC_\ccx)^{(2\ 3)(0\ 1)}\right)\\
&= \ccI(\ccB_{\ymod{o}}, \ccC_{\ymod{o}}) - \ccI(\ccB_{\ymod{o}}, \ccC_{\ymod{o}})^{(2\ 3)} - \left(\ccI(\ccB_{\ymod{o}}, \ccC_{\ymod{o}})^{(0\ 1)} - \ccI(\ccB_{\ymod{o}}, \ccC_{\ymod{o}})^{(2\ 3)(0\ 1)}\right).
\end{align*}

\begin{align*}
\ccI(\ccB_{\ymod{o}}, \ccC_{\ymod{o}}) & =  \ccI(\set{0, \ccv - \ymod{2}, 2}, \set{1, \ccv - \ymod{2}, 3}) = 1, \\
\ccI(\ccB_{\ymod{o}}, \ccC_{\ymod{o}})^{\ymod{(2\ 3)}}  &= \ccI(\set{0, \ccv - \ymod{2}, 3}, \set{1, \ccv - \ymod{2}, 2}) = 2, \\
\ccI(\ccB_{\ymod{o}}, \ccC_{\ymod{o}})^{\ymod{(0\ 1)}}  &= \ccI(\set{1, \ccv - \ymod{2}, 2}, \set{0, \ccv - \ymod{2}, 3}) = 2, \\
\ccI(\ccB_{\ymod{o}}, \ccC_{\ymod{o}})^{\ymod{(2\ 3)(0\ 1)}} &= \ccI(\set{1, \ccv - \ymod{2}, 3}, \set{0, \ccv - \ymod{2}, 2}) = 1,
\end{align*}

we see that

\[
\sum_{\set{\ccB, \ccC} \in {\Block \choose 2}} \ccI(\ccB, \ccC) - \ccI(\ccB, \ccC)^{(0\ 1)} - \left(\ccI(\ccB, \ccC)^{(2\ 3)} - \ccI(\ccB, \ccC)^{(2\ 3)(0\ 1)}\right) = 1 - 2 - (2 - 1) = - 2.
\]

Therefore (<ref>) holds. It follows from Lemma <ref> that \(\size{\ccs(\cD)} > 1\).

[1]
A. Baartmans, I. Landjev, and V. D. Tonchev.
On the binary codes of Steiner triple systems.
Des. Codes Cryptogr., 8(1):29–43, 1996.

[2]
E. R. Berlekamp, J. H. Conway, and R. K. Guy.
Winning ways for your mathematical plays.
A.K. Peters, Natick, MA, 2nd edition, 2001.

[3]
C. J. Colbourn and A. Rosa.
Triple systems.
Clarendon Press, Oxford, 1999.

[4]
F. N. Cole, L. D. Cummings, and H. S. White.
The complete enumeration of triad systems in 15 elements.
Proc. Natl. Acad. Sci. USA, 3:197–199, 1917.

[5]
J. H. Conway.
On numbers and games.
A.K. Peters, Natick, MA, 2nd edition, 2001.

[6]
J. H. Conway and N. J. A. Sloane.
Lexicographic codes: error-correcting codes from game
IEEE Trans. Inform. Theory, 32(3):337–48, 1986.

[7]
J. H. Conway and N. J. A. Sloane.
Sphere packings, lattices and groups, volume 290.
Springer, New York, NY, 3rd edition, 1999.

[8]
V. de Pasquale.
Sui sistemi ternari di 13 elementi.
Rendiconti Reale Istituto Lombardo di Scienze e Lettere,
2(32):213–221, 1899.

[9]
M. Dehon.
Designs et hyperplans.
J. Combin. Theory Ser. A, 23(3):264–274,

[10]
P. Diaconis, R. L. Graham, and W. M. Kantor.
The mathematics of perfect shuffles.
Adv. Appl. Math., 4(2):175–196, 1983.

[11]
J. Doyen, X. Hubaut, and M. Vandensavel.
Ranks of incidence matrices of Steiner triple systems.
Math. Z., 163(3):251–259, 1978.

[12]
A. S. Fraenkel, U. Larsson.
Games on arbitrarily large rats and playability.
Integers, 19:1–29(#G04), 2019.

[13]
J. Kahane and A. J. Ryba.
The Hexad game.
Electron. J. Combin., 8(2):1–9(#R11),

[14]
T. P. Kirkman.
On a problem in combinations.
Cambridge and Dublin Mathematical Journal, 2:191–204, 1847.

[15]
E. H. Moore.
Concerning triple systems.
Math. Ann., 43(2):271–285, 1893.

[16]
O. Veblen and J. W. Young.
Projective geometry.
Ginn and Company, Boston, 1916.

[17]
E. Witt.
Die 5-fach transitiven gruppen von Mathieu.
Abh. Math. Semin. Univ. Hambg., 12(1):256–264, 1937.

[18]
E. Witt.
Über Steinersche systeme.
Abh. Math. Semin. Univ. Hambg., 12:265–275, 1937.


200 |  93139301545921 |  38503146951361 |  15916936250882 |  22370139308162 |  5372846095693
|  97568760404309 |  37267950234252 |  14235090298445 |  14235090298447 |  2076871684802
|  100169256075517 |  38271123030638 |  14622039889385 |  14644113016397 |  2140876896154
|  106974698806081 |  41357153980800 |  15988960048321 |  17096763136319 |  2732415356170
|  117669030460994 |  44945570212853 |  17167680177565 |  17167680177565 |  2504730781961
|  127353146734466 |  49235591884415 |  19034814375361 |  20353628918779 |  3252924806225
|  145624636022689 |  55623966835967 |  21246581423810 |  21247264485212 |  3100067821177
|  148135740183017 |  61359829568746 |  25416072313501 |  35943748523221 |  8721413592050
|  151620880341401 |  58614975076521 |  22659908684642 |  24224044888162 |  3870208044053
|  180995342924521 |  69256365627280 |  26500373448281 |  26773753957319 |  3960510195370
210 |  187611224490881 |  77557860622531 |  32062163448202 |  45062357376712 |  10823531789513
|  217774440785026 |  83329499390175 |  31885309605601 |  32214057385499 |  4765230894385
|  238763690000642 |  98703268009921 |  40803252436801 |  57346114029121 |  13773353872325
|  262229286072101 |  100188517542107 |  38278482154450 |  38336266554220 |  5604520209509
|  299713796309065 |  124145519261542 |  51422757785981 |  72722761475561 |  17645500813642
|  308061521170129 |  117669030460994 |  44945570212853 |  44945570212853 |  6557470319842
|  316141040381993 |  120759677612784 |  46127828641049 |  46137992456359 |  6733432474730
|  332380318337465 |  128500489573192 |  49679162421961 |  53121150382111 |  8489842695962
|  379325837704445 |  157121637984713 |  65081802158266 |  92039076249694 |  22332229220561
|  381249713544034 |  145625232114511 |  55624194524033 |  55625982799499 |  8116071573265
220 |  426776599819081 |  176766390491736 |  73214784551737 |  103522571656127 |  25111317834298
|  459789046174429 |  175623808514133 |  67082333460610 |  67082379367970 |  9787196235121
|  473638416248177 |  181233808565389 |  69347612525386 |  70063009447990 |  10364077584317
|  542557456311485 |  224289522541113 |  92719746704282 |  130311111311854 |  31298041403345
|  554510738235029 |  211804254955880 |  80902026460669 |  80902026632611 |  11803446645770
|  668746232531714 |  255438330978675 |  97568760404309 |  97568760404311 |  14235090298445
|  686480075504546 |  262279709932717 |  100207782712165 |  100359054293605 |  14671860317729
|  767465181141553 |  317894486677955 |  131676207785642 |  186218278892312 |  45184131144601
|  806515533049393 |  308061521170129 |  117669030460994 |  117669030460994 |  17167680177565
|  867493136119153 |  335363374569595 |  129647818893242 |  138596987589632 |  22143258740761
230 |  971341527703714 |  402319473791747 |  166636506702965 |  235616893671527 |  57153245279917
|  998123312425769 |  381251274127774 |  145625828206333 |  145630509957553 |  21248121516122
|  1032834620396045 |  399282575032962 |  154358279221721 |  165013104702841 |  26363683193762
|  1451727959691893 |  554510738385079 |  211804255013194 |  211804255463344 |  30901824500165
|  1491304701603697 |  570634798845219 |  218348452400746 |  220599694931960 |  32631980139097
|  1597456854383053 |  617587801992005 |  238763690000642 |  255306551592962 |  40803252436801
|  1746860020068409 |  723573111879672 |  299713796309065 |  423859315570607 |  102845515571962
|  1797110092720441 |  686612067374626 |  262330133793197 |  262726109403437 |  38408892611458
|  1965217522626434 |  814019750849633 |  337178020826785 |  476841729922465 |  115701204969701
|  2111485077978050 |  806515533049393 |  308061521170129 |  308061521170129 |  44945570212853
240 |  2210871958107149 |  915771584495037 |  379324361998130 |  536442795377962 |  130161709120097
|  2264132942340130 |  875289074233103 |  338377199123297 |  361734280359179 |  57793289051185
|  2487396418774357 |  1030253502313948 |  426720192655565 |  603364088167487 |  146357138790754
|  2613117102565793 |  998127398083769 |  381252834718834 |  381265091685514 |  55628226532685
|  2801598191304130 |  1158171440067873 |  478784248488001 |  672916128899489 |  161627787288901
|  3151440817820989 |  1203743419591266 |  459789126299113 |  459789440952809 |  67082436965410
|  3160519691308253 |  1306537163284433 |  540113502136330 |  759091798545046 |  182318230828625
|  3243440684655313 |  1241075655154880 |  474887297648177 |  479786280809327 |  70972432559626
|  3565466389961309 |  1473939293984652 |  609316371195845 |  856351491992647 |  205677966816002
|  4169218794693154 |  1611848648289613 |  623151768456005 |  666327150175685 |  106492821059521
250 |  4583654867317685 |  1750800366616467 |  668746232531714 |  668746232531716 |  97568760404309
|  4704586218916261 |  1797455638914941 |  686744088327362 |  687780697828562 |  100549180372873
|  4963446454828093 |  1918902125751537 |  741860600638090 |  793259922426518 |  126779106061681
|  5032254317345729 |  2084427882680008 |  863398255353985 |  1221029330694295 |  296271319451546
|  5527939700884757 |  2111485077978050 |  806515533049393 |  806515533049393 |  117669030460994
|  5909324059011749 |  2284480090460732 |  883155032892925 |  944116212370447 |  150838812283682
|  6369686478515453 |  2638257317407993 |  1092738503901850 |  1545085473708526 |  374789109184145
|  7054174412588354 |  2699221286155173 |  1032834620396045 |  1043489445877165 |  154358279221721
|  8487613404424009 |  3247711593052213 |  1242708649541930 |  1255521374732630 |  185721691988101
|  9950291461929757 |  3800673140690600 |  1451727959691893 |  1451727960142043 |  211804255013194
260 |  10181446324101389 |  4217293152016490 |  1746860020068409 |  2470433131948081 |  599427592618130
|  10216281973762705 |  3903279305965872 |  1491304701603697 |  1493555944134911 |  218348452400746
|  10881286283486669 |  4206780083103874 |  1626370100606233 |  1739053965824953 |  277936690319522
|  11454127114764514 |  4744454795874015 |  1965217522431409 |  2779237272857531 |  674356041403105
|  12315957481333442 |  4705490811168293 |  1797801251550925 |  1800514952171437 |  263223878282009
|  12885900008113189 |  5337505423958395 |  2210863357068434 |  3126616263761996 |  758637677978725
|  14472334024676221 |  5527939700884757 |  2111485077978050 |  2111485077978050 |  308061521170129
|  14497376284172417 |  6004661215090278 |  2487067701165605 |  3516607361098417 |  853018304121194
|  14851330019499401 |  5672916816810603 |  2166942971989610 |  2167420430932408 |  316315866542273
|  15423171693415289 |  5962429596483661 |  2305010110741498 |  2464117096035694 |  393685111186805
270 |  16320019794869474 |  6746642286687683 |  2789039640676885 |  3919907065193575 |  941522840835341
|  17910542369308357 |  6841223909613610 |  2613117102565793 |  2613129359532473 |  381252834718834
|  18410741231768629 |  7610874151194525 |  3146283173290594 |  4421881221814946 |  1062044884216825
|  20769646571311849 |  8586029106829510 |  3549405406115549 |  4988440749176681 |  1198120585374730
|  21600295969140418 |  8250579033871701 |  3151440817820989 |  3151441132474685 |  459789126299113
|  23854878116939714 |  9222459875899275 |  3565466389961309 |  3812501510758111 |  609316371195845
|  26050201244948621 |  9950291462322593 |  3800673140840650 |  3800673142019158 |  554510738578913
|  26071224093240493 |  10799054607088409 |  4473114879063674 |  6325939728024734 |  1534930362283105
|  28399179102482729 |  10979317867599065 |  4244679763551394 |  4538774500314466 |  725389768850885
|  31416837838692077 |  12000164235336588 |  4583654867317685 |  4583654867317687 |  668746232531714
280 |  32996473695239650 |  13667563554568793 |  5661280512684809 |  8006216968466729 |  1942616981990173
|  33809973988413085 |  13070566784642598 |  5052938405996713 |  5401726365514709 |  863018934527914
|  37889062373143906 |  14472334024676221 |  5527939700884757 |  5527939700884757 |  806515533049393
|  40254049821997474 |  15561775671567955 |  6016012379451749 |  6431277192706391 |  1027507207655485
|  41836262445484585 |  17294972731611518 |  7149684610974845 |  10048655749349969 |  2413587554589082
|  46890399112653461 |  17910553065691297 |  6841227995271610 |  6841260084420430 |  998132675950169
|  48306462250737473 |  18484066814863809 |  7072774740632834 |  7145738193853954 |  1057034027250125
|  53243232159418993 |  22010386141759859 |  9098942315500874 |  12787926265860584 |  3071396148367705
|  58122604880389733 |  22240110226042298 |  8509985123419585 |  8597725797737161 |  1271809634912210
|  59341817924539925 |  24580185800219268 |  10181446324101389 |  14398739476117879 |  3493720040136818
290 |  70014236857598818 |  26749958796218487 |  10220211312947065 |  10235639531056643 |  1496385896811481
|  74119312578961858 |  28655029879238381 |  11078229260495189 |  11845777058753285 |  1893196647988273
|  84408473716542145 |  32242381632832033 |  12315957481333442 |  12318671181953954 |  1797801251550925
|  84495546415824461 |  34997169175011122 |  14495460438077785 |  20495961109208905 |  4971675308457794
|  99194853094755497 |  37889062373143906 |  14472334024676221 |  14472334024676221 |  2111485077978050
|  101791412246620601 |  38881073241687600 |  14851330019499401 |  14851807478442199 |  2166942971989610
|  107246981290506205 |  44335547834263417 |  18328169036663258 |  25759662212284046 |  6187215614895025
|  120987879709637005 |  50015557712772738 |  20676087714928729 |  29058793428681209 |  6979322867359138
|  122760633575886146 |  46890427116134699 |  17910563762074237 |  17910647772517951 |  2613144737746085
|  148050629787671833 |  56550309487554483 |  21600296518323130 |  21600298674991616 |  3151441527253105
300 |  152098457523687709 |  58199154485574821 |  22269401267979938 |  22499005933036754 |  3328142022058225

##  Appendix F Some numerical experimentation

For funsies we have done some low-effort numerical investigation of the
uniqueness conjecture and the growth of Markoff numbers. The highest published
numerically confirmed bound that we are aware of is uniqueness of Markoff
numbers up to $10^{140}$ [Bar96]. We have checked uniqueness for all
$215596025$ Markoff numbers up to $10^{15000}$. The computation was done by a
straightforward implementation of the mutation algorithm in Python and took
about 29 hours on a laptop. Following an argument of Button [But01, p. 84], we
further conclude that the uniqueness conjecture is true for all Markoff
numbers of the form $Np^{n}$, where $p$ is a prime number, $n\geq 0$, and
$N\leq 10^{3750}$.

Zagier estimated the number $M(n)$ of Markoff numbers $\leq n$ with
$C\cdot(\log n)^{2}+$ $O(\log n(\log\log n)^{2})$ with $C\approx
0.180717104711507$ ([Zag82], see also [BU04]). Figure 12 shows the deviation
of $M(n)$ from $C\log(n)^{2}$. In the chosen scale the deviation appears to
follow a linear growth with slope close to $1/log(3)\approx 0.910239$ (only
every 100-th value is taken into account). The gray line represents
$-2.038389+0.914755\log_{10}n$ obtained from quadratic regression.

$0$$3{,}000$$6{,}000$$9{,}000$$12{,}000$$15{,}000$$0$$2{,}000$$4{,}000$$6{,}000$$8{,}000$$10{,}000$$12{,}000$$\log_{10}n$regression$M(n)-C\cdot\log(n)^{2}$
Figure 12. Deviation of $M(n)$ from Zagier’s estimate.

Zagier also conjectured an improved formula, $M(n)=C\cdot(\log 3n)^{2}+o(\log
n)$. Figure 13 shows the differences $M(n)-C\cdot(\log 3n)^{2}$ for every
$n=10^{k}$, $0\leq k\leq 15000$.

The counts are attached to this document here: 📎

Figure 13. Deviation of $M(n)$ from $C\cdot(\log 3n)^{2}$.

## References

  * [Aig13] M. Aigner.  Markov’s theorem and 100 years of the uniqueness conjecture.  Springer, 2013.
  * [Bae01] S. I. Baek.  Weak local dimension on deranged Cantor sets.  Real Anal. Exch., 26(2):553–558, 2001.
  * [Bae04] S. I. Baek.  Spectra of deranged Cantor set by weak local dimensions.  J. Math. Kyoto Univ., 44(3):493–500, 2004.
  * [Bar96] A. Baragar.  On the unicity conjecture for Markoff numbers.  Canad. Math. Bull., 39(1):3–9, 1996.
  * [Bow96] B. H. Bowditch.  A proof of McShane’s identity via Markoff triples.  Bull. London Math. Soc., 28(1):73–78, 1996.
  * [BU04] A. Baragar and K. Umeda.  The asymptotic growth of integer solutions to the Rosenberger equations.  Bull. Austral. Math. Fr., 69(3):481–497, 2004.
  * [But01] J. O. Button.  Markoff Numbers, Principal Ideals and Continued Fraction Expansions.  J. Number Theory, 87(1):77–95, 2001.
  * [Cas57] J. W. S. Cassels.  An introduction to Diophantine approximation.  Number 45 in Cambridge Tracts in Mathematics and Mathematical Physics. Cambridge University Press, 1957.
  * [CF89] T. W. Cusick and M. E. Flahive.  The Markoff and Lagrange spectra.  Number 30 in Mathematical Surveys and Monographs. American Mathematical Society, 1989.
  * [Coh55] H. Cohn.  Approach to Markoff’s minimal forms through modular functions.  Annals of Mathematics, 61(1):1–12, 1955.
  * [DL85] J. M. Drezet and J. Le Potier.  Fibrés stables et fibrés exceptionnels sur $\mathbb{P}_{2}$.  Ann. scient. Éc. Norm. Sup. $4^{e}$ série, 18:193–244, 1985.
  * [Fal97] K. Falconer.  Techniques in fractal geometry. John Wiley & Sons, 1997.
  * [Fro68] G. Frobenius.  Über die Markoffschen Zahlen.  In Gesammelte Abhandlungen, Band III, pages 598–627. Springer, 1968.
  * [GKP94] R. Graham, D. Knuth, and O. Patashnik.  Concrete mathematics.  Addison-Wesley, 2nd edition, 1994.
  * [Hac13] P. Hacking.  Exceptional bundles associated to degenerations of surfaces.  Duke Math. J., 162(6):1171–1202, 2013.
  * [HP08] L. Hille and M. Perling.  Exceptional sequences of invertible sheaves on rational surfaces.  arXiv:0810.1936, 2008.
  * [HP10] P. Hacking and Y. Prokhorov.  Smoothable del Pezzo surfaces with quotient singularities.  Compos. Math., 146(1):169–192, 2010.
  * [JS95] H. Jürgensen and L. Staiger.  Local Hausdorff dimension.  Acta Informatica, 32:491–507, 1995.
  * [Kos14] T. Koshy.  Pell and Pell-Lucas numbers with applications.  Springer, 2014.
  * [KS88] J. Kollár and N. Shepherd-Barron.  Threefolds and deformations of surface singularities.  Invent. Math., 91(2):299–338, 1988.
  * [LT07] M. L. Lang and S. P. Tan.  A simple proof of the Markoff conjecture for prime powers.  Geom. Dedicata, 129:15–22, 2007.
  * [Per54] O. Perron.  Die Lehre von den Kettenbrüchen, Bd. I.  Teubner, 3rd edition, 1954.
  * [Per18] M. Perling.  Combinatorial aspects of exceptional sequences on (rational) surfaces.  Math. Z., 288(1–2):243–286, 2018.
  * [Reu19] C. Reutenauer.  From Christoffel words to Markoff numbers.  Oxford University Press, 2019.
  * [Rud89] A. N. Rudakov.  Markov numbers and exceptional bundles on $\mathbb{P}^{2}$.  Math. USSR Izvestiya, 32(1):99–112, 1989.
  * [Slo] N. J. A Sloane.  The Online Encyclopedia of Integer Sequences.  Published electronically at http://oeis.org.
  * [Wah81] J. Wahl.  Smoothings of normal surface singularities.  Topology, 20(3):219–246, 1981.
  * [Zag82] D. Zagier.  On the number of Markoff numbers below a given bound.  Math. Comp., 39(160):709–723, 1982.