MINIMOGs and Mathematical blackjack

This is an exposition of some ideas of Conway, Curtis, and Ryba on S(5,6,12) and a card game called mathematical blackjack (which has almost no relation with the usual Blackjack).

Many thanks to Alex Ryba and Andrew Buchanan for helpful discussions on this post.

Definitions

An m-(sub)set is a (sub)set with m elements. For integers k<m<n, a Steiner system S(k,m,n) is an n-set X and a set S of m-subsets having the property that any k-subset of X is contained in exactly one m-set in S. For example, if X = \{1,2,\dots,12\}, a Steiner system S(5,6,12) is a set of 6-sets, called hexads, with the property that any set of 5 elements of X is contained in (“can be completed to”) exactly one hexad.

Rob Beezer has a nice Sagemath description of S(5,6,12).

If S is a Steiner system of type (5,6,12) in a 12-set X then any element the symmetric group \sigma\in S_X\cong S_{12} of X sends S to another Steiner system \sigma(S) of X. It is known that if XS and S’ are any two Steiner systems of type (5,6,12) in X then there is a \sigma\in S_X such that S'=\sigma(S). In other words, a Steiner system of this type is unique up to relabelings. (This also implies that if one defines M_{12} to be the stabilizer of a fixed Steiner system of type (5,6,12) in X then any two such groups, for different Steiner systems in X, must be conjugate in S_X. In particular, such a definition is well-defined up to isomorphism.)

Curtis’ kitten

 

NICOLESHENTING-Cats-Playing-Poker-Cards-Art-Silk-Fabric-Poster-Canvas-Print-13x20-24x36inch-Funny-Pictures-Home.jpg_640x640

NICOLE SHENTING – Cats Playing Poker Cards

J. Conway and R. Curtis [Cu1] found a relatively simple and elegant way to construct hexads in a particular Steiner system S(5,6,12) using the arithmetical geometry of the projective line over the finite field with 11 elements. This section describes this.

 

Let \mathbf{P}^1(\mathbf{F}_{11}) =\{\infty,0,1,2,...,9,10\} denote the projective line over the finite field \mathbf{F}_{11} with 11 elements. Let Q=\{0,1,3,4,5,9\} denote the quadratic residues with 0, and let
L=<\alpha,\beta>\cong PSL(2,\mathbf{F}_{11}),
where \alpha(y)=y+1 and \beta(y)=-1/y. Let S=\{\lambda(Q)\ \vert\ \lambda\in L\}.

Lemma 1: S is a Steiner system of type (5,6,12).

The elements of S are known as hexads (in the “modulo 11 labeling”).

 	 	 	 	 	\infty	 	 	 	 	 
 	 	 	 	 	 	 	 	 	 	 
 	 	 	 	 	6	 	 	 	 	 
 	 	 	 	 	 	 	 	 	 	 
 	 	 	 	2	 	10	 	 	 	 
 	 	 	 	 	 	 	 	 	 	 
 	 	 	5	 	7	 	3	 	 	 
 	 	 	 	 	 	 	 	 	 	 
 	 	6	 	9	 	4	 	6	 	 
 	 	 	 	 	 	 	 	 	 	 
 	2	 	10	 	8	 	2	 	10	 
 	 	 	 	 	 	 	 	 	 	 
0	 	 	 	 	 	 	 	 	 	1
 	 	 	 	 	 	 	 	 	 	 

Curtis’ Kitten.

 

In any case, the “views” from each of the three “points at infinity” is given in the following tables.

6	10	3
2	7	4
5	9	8
picture at \infty

5	7	3
6	9	4
2	10	8
picture at 0	

5	7	3
9	4	6
8	2	10
picture at 1

Each of these 3\times 3 arrays may be regarded as the plane \mathbf{F}_3^2. The lines of this plane are described by one of the following patterns.

\bullet	\bullet	\bullet
\times	\times	\times
\circ	\circ	\circ	
slope 0	

\bullet	\times	\circ
\bullet	\times	\circ
\bullet	\times	\circ	
slope infinity

\bullet	\times	\circ
\circ	\bullet	\times
\times	\circ	\bullet	
slope -1

\times	\circ	\bullet
\circ	\bullet	\times
\bullet	\times	\circ
slope 1

The union of any two perpendicular lines is called a cross. There are 18 crosses. The complement of a cross in \mathbf{F}_3^2 is called a square. Of course there are also 18 squares. The hexads are

  1. \{0,1,\infty\}\cup \{{\rm any\ line}\},
  2. the union of any two (distinct) parallel lines in the same picture,
  3. one “point at infinity” union a cross in the corresponding picture,
  4. two “points at infinity” union a square in the picture corresponding to the omitted point at infinity.

Lemma 2 (Curtis [Cu1]) There are 132 such hexads (12 of type 1, 12 of type 2, 54 of type 3, and 54 of type 4). They form a Steiner system of type $(5,6,12)$.

The MINIMOG description

Following Curtis’ description [Cu2] of a Steiner system S(5,8,24) using a $4\times 6$ array, called the MOG, Conway [Co1] found and analogous description of S(5,6,12) using a 3\times 4 array, called the MINIMOG. This section is devoted to the MINIMOG. The tetracode words are

0	0	0	0		0	+	+	+		0	-	-	-
+	0	+	-		+	+	-	0		+	-	0	+
-	0	-	+		-	+	0	-		-	-	+	0

With ”0″=0, “+”=1, “-“=2, these vectors form a linear code over GF(3). (This notation is Conway’s. One must remember here that “+”+”+”=”-“!) They may also be described as the set of all 4-tuples in  of the form
(0,a,a,a),(1,a,b,c),(2,c,b,a),
where abc is any cyclic permutation of 012. The MINIMOG in the shuffle numbering is the  array
\begin{array}{cccc} 6 & 3 & 0 & 9\\ 5 & 2 & 7 & 10 \\ 4 & 1 & 8 & 11 \end{array}
We label the rows of the MINIMOG array as follows:

  1. the first row has label 0,
  2. the second row has label +,
  3. the third row has label –

A col (or column) is a placement of three + signs in a column of the MINIMOG array. A tet (or tetrad) is a placement of 4 + signs having entries corresponding (as explained below) to a tetracode.

+	+	+	+
 	 	 	 
 	 	 	 
0	0	0	0
+	 	 	 
 	+	+	+
 	 	 	 
0	+	+	+
+	 	 	 
 	 	 	 
 	+	+	+


0	-	-	-

 	+	 	 
+	 	+	 
 	 	 	+

+	0	+	-
 	 	 	+
+	+	 	 
 	 	+	 

+	+	-	0
 	 	+	 
+	 	 	+
 	+	 	 


+	-	0	+
 	+	 	 
 	 	 	+
+	 	+	 

-	0	-	+

 	 	+	 
 	+	 	 
+	 	 	+

-	+	0	-

 	 	 	+
 	 	+	 
+	+	 	 


-	-	+	0

Each line in \mathbf{F}_3^2 with finite slope occurs once in the 3\times 3 part of some tet. The odd man out for a column is the label of the row corresponding to the non-zero digit in that column; if the column has no non-zero digit then the odd man out is a “?”. Thus the tetracode words associated in this way to these patterns are the odd men out for the tets. The signed hexads are the combinations $6$-sets obtained from the MINIMOG from patterns of the form

col-col, col+tet, tet-tet, col+col-tet.Lemma 3 (Conway, [CS1], chapter 11, page 321) If we ignore signs, then from these signed hexads we get the 132 hexads of a Steiner system S(5,6,12). These are all possible $6$-sets in the shuffle labeling for which the odd men out form a part (in the sense that an odd man out “?” is ignored, or regarded as a “wild-card”) of a tetracode word and the column distribution is not 0,1,2,3 in any order.

Furthermore, it is known [Co1] that the Steiner system S(5,6,12) in the shuffle labeling has the following properties.

  1. There are 11 hexads with total 21 and none with lower total.
  2. The complement of any of these 11 hexads in \{0,1,...,11\} is another hexad.
  3. There are 11 hexads with total 45 and none with higher total.

Mathematical blackjack

Mathematical blackjack is a 2-person combinatorial game whose rules will be described below. What is remarkable about it is that a winning strategy, discovered by Conway and Ryba [CS2] and [KR], depends on knowing how to determine hexads in the Steiner system S(5,6,12) using the shuffle labeling.

Mathematical blackjack is played with 12 cards, labeled 0,\dots ,11 (for example: king, ace, 2, 3, …, 10, jack, where the king is 0 and the jack is 11). Divide the 12 cards into two piles of 6 (to be fair, this should be done randomly). Each of the 6 cards of one of these piles are to be placed face up on the table. The remaining cards are in a stack which is shared and visible to both players. If the sum of the cards face up on the table is less than 21 then no legal move is possible so you must shuffle the cards and deal a new game. (Conway [Co2] calls such a game *={0|0}, where 0={|}; in this game the first player automatically wins.)

  1. Players alternate moves.
  2. A move consists of exchanging a card on the table with a lower card from the other pile.
  3. The player whose move makes the sum of the cards on the table under 21 loses.

The winning strategy (given below) for this game is due to Conway and Ryba [CS2], [KR]. There is a Steiner system S(5,6,12) of hexads in the set \{0,1,...,11\}. This Steiner system is associated to the MINIMOG of in the “shuffle numbering” rather than the “modulo 11 labeling”.

Proposition 6Lemma 7 The probability that the first player has a win in mathematical blackjack (with a random initial deal) is 6/7.

An example is given in this expository hexads_sage. This paper was inspired by the research done in Ann Luers’ thesis.

Bibliography

[Cu1] R. Curtis, “The Steiner system $S(5,6,12)$, the Mathieu group $M_{12}$, and the kitten,” in Computational group theory, ed. M. Atkinson, Academic Press, 1984.
[Cu2] —, “A new combinatorial approach to $M_{24}$,” Math Proc Camb Phil Soc 79(1976)25-42
[Co1] J. Conway, “Hexacode and tetracode – MINIMOG and MOG,” in Computational group theory, ed. M. Atkinson, Academic Press, 1984.
[Co2] —, On numbers and games (ONAG), Academic Press, 1976.
[CS1] J. Conway and N. Sloane, Sphere packings, Lattices and groups, 3rd ed., Springer-Verlag, 1999.
[CS2] —, “Lexicographic codes: error-correcting codes from game theory,” IEEE Trans. Infor. Theory32(1986)337-348.
[KR] J. Kahane and A. Ryba, “The hexad game,” Electronic Journal of Combinatorics, 8 (2001)

Simple unsolved math problem, 8

Sylver coinage is a game for 2 players invented by John H. Conway.

The two players take turns naming positive integers that are not the sum of non-negative multiples of any previously named integers. The player who is forced to name 1 loses.

James Joseph Sylvester proved the following fact.

Lemma: If a and b are relatively prime positive integers, then (a – 1)(b – 1) – 1 is the largest number that is not a sum of nonnegative multiples of a and b.

Therefore, if a and b have no common prime factors and are the first two moves, this formula gives an upper bound on the next number that can still be played.

R. L. Hutchings proved the following fact.

Theorem: If the first player selects any prime number p>3 as a first move then he/she has a winning strategy.

Very little is known about the subsequent winning moves. That is, a winning strategy exists but it’s not know what it is!

Unsolved problem:Are there any non-prime winning opening moves in Sylver coinage?

For further info, Sicherman maintains a Sylver coinage game webpage.

Sports ranking methods, 4

This is the fourth of a series of expository posts on matrix-theoretic sports ranking methods. This post discusses the Elo rating.

This system was originally developed by Arpad Elo (Elo (1903-1992) was a physics professor at Marquette University in Milwaukee and a chess master, eight-time winner of the Wisconsin State Chess Championships.) Originally, it was developed for rating chess players in the 1950s and 1960s. Now it is used for table tennis, basketball, and other sports.

We use the following version of his rating system.

As above, assume all the $n$ teams play each other (ties allowed)
and let r_i denote the rating of Team i, i=1,2,\dots,n.

Let A=(A_{ij}) denote an $n\times n$ matrix of score results:

A_{ij}= \left\{ \begin{array}{rr} -1,& {\rm if\ team\ } i {\rm \ lost\ to\ team\ } j,\\ +1,& {\rm if\ team\ } i {\rm\ beat\ team\ } j,\\ 0, & {\rm if}\ i=j. \end{array} \right.

Let S_{ij}=(A_{ij}+1)/2.

As in the previous post, the matrix A associated to the example of the Patriot league is the adjacency matrix of a diagraph.

  1. Initialize all the ratings to be 100: {\bf r}=(r_1,\dots,r_n) = (100,\dots,100).
  2. After Team i plays Team j, update their rating using the formula

    r_i = r_i+K(S_{ij}-mu_{ij}),

    where K=10 and

    \mu_{ij} = (1+e^{-(r_i-r_j)/400})^{-1}.

In the example of the Patriot league, the ratings vector is

{\bf r}=(85.124, 104.79, 104.88, 85.032, 94.876, 124.53).

This gives the ranking

Lafayette < Army < Lehigh < Bucknell < Holy Cross < Navy.

This gives a prediction failure rate of 13.3\%.

Some SageMath code for this:

def elo_rating(A):
    """
    A is a signed adjacency matrix for a directed graph.

    Returns elo ratings of the vertices of Gamma = Graph(A) 
        
    EXAMPLES:
        sage: A = matrix(QQ,[
        [0 , -1 , 1  , -1 , -1 , -1 ],
        [1,   0 ,  -1,  1,  1,   -1  ],
        [-1 , 1 ,  0 ,  1 , 1  , -1  ],
        [1 , -1 , -1,  0 ,  -1 , -1  ],
        [1 , - 1 , - 1 , 1 , 0 , - 1  ],
        [1 ,  1  ,  1  , 1  , 1  , 0 ]
        ])
        sage: elo_rating(A)
        (85.124, 104.79, 104.88, 85.032, 94.876, 124.53)

    """
    n = len(A.rows())
    RR = RealField(prec=20)
    V = RR^n
    K = 10
    r0 = 100 # initial rating
    r = n*[r0]
    for i in range(n):
        for j in range(n):
            if ij and A[i][j]==1:
                S = 1
            elif ij and A[i][j]==-1:
                S = 0
            else:
                S = 1/2
            mu = 1/(1+e^(-(r[i]-r[j])/400))
            r[i] = r[i]+K*(S-mu)
    return V(r)

Sports ranking methods, 3

This is the third of a series of expository posts on matrix-theoretic sports ranking methods. This post discusses the random walker ranking.

We follow the presentation in the paper by Govan and Meyer (Ranking National Football League teams using Google’s PageRank). The table of “score differentials” based on the table in a previous post is:

\begin{tabular}{c|cccccc} \verb+x\y+ & Army & Bucknell & Holy Cross & Lafayette & Lehigh & Navy \\ \hline Army & 0 & 0 & 1 & 0 & 0 & 0 \\ Bucknell & 2 & 0 & 0 & 2 & 3 & 0 \\ Holy Cross & 0 & 3 & 0 & 4 & 14 & 0 \\ Lafayette & 10 & 0 & 0 & 0 & 0 & 0 \\ Lehigh & 2 & 0 & 0 & 11 & 0 & 0 \\ Navy & 11 & 14 & 8 & 22 & 6 & 0 \\ \end{tabular}
This leads to the following matrix:

M_0=\left(\begin{array}{cccccc} 0 & 0 & 1 & 0 & 0 & 0 \\ 2 & 0 & 0 & 2 & 3 & 0 \\ 0 & 3 & 0 & 4 & 14 & 0 \\ 10 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 11 & 0 & 0 \\ 11 & 14 & 8 & 22 & 6 & 0 \\ \end{array}\right) .

The edge-weighted score-differential graph associated to M_0 (regarded as a weighted adjacency matrix) is in the figure below.

sm261_baseball-ranking-application_teams-digraph2

This matrix M_0 must be normalized to create a (row) stochastic matrix:

M = \left(\begin{array}{cccccc} 0 & 0 & 1 & 0 & 0 & 0 \\ {2}/{7} & 0 & 0 /{7} /{7} & 0 \\ 0 /{7} & 0 /{21} /{3} & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ {2}/{13} & 0 & 0 /{13} & 0 & 0 \\ {11}/{61} /{61} /{61} /{61} /{61} & 0 \\ \end{array}\right) .

Next, to insure it is irreducible, we replace M by A=(M+J)/2, where J is the 6\times 6 doubly stochastic matrix with every entry equal to 1/6:

A=\left(\begin{array}{cccccc} {1}/{12} & 1/{12} & 7/{12} & 1/{12} & 1/{12} & 1/{12} \\ {19}/{84} & 1/{12} & 1/{12} & 19/{84} & 25/{84} & 1/{12} \\ {1}/{12} & 13/{84} & 1/{12} & 5/{28} & 5/{12} & 1/{12} \\ {7}/{12} & 1/{12} & 1/{12} & 1/{12} & 1/{12} & 1/{12} \\ {25}/{156} & 1/{12} & 1/{12} & 79/{156} & 1/{12} & 1/{12} \\ {127}/{732} & 145/{732} & 109/{732} & 193/{732} & 97/{732} & 1/{12} \end{array}\right).

Let

{\bf v}_0 = \left( \frac{1}{6} , \frac{1}{6} , \frac{1}{6} , \frac{1}{6} , \frac{1}{6} , \frac{1}{6}\right).

The ranking determined by the random walker method is the reverse of the left eigenvector of A associated to the largest eigenvalue \lambda_{max}=1 (by reverse, I mean that the vector ranks the teams from worst-to-best, not from best-to-worst, as we have seen in previous ranking methods).
In other words, the vector

{\bf r}^*=\lim_{n\to \infty}{\bf v}_0A^n.

This is approximately

{\bf r}^* \cong \left(0.2237\dots ,\,0.1072\dots ,\,0.2006\dots ,\,0.2077\dots ,\,0.1772\dots ,\,0.0833\dots \right).

Its reverse gives the ranking:

Army < Lafayette < Bucknell < Lehigh < Holy Cross < Navy.

This gives a prediction failure rate of 13.3\%.

Sports ranking methods, 2

This is the second of a series of expository posts on matrix-theoretic sports ranking methods. This post discusses Keener’s method (see J.P. Keener, The Perron-Frobenius theorem and the ranking of football, SIAM Review 35 (1993)80-93 for details).

See the first post in the series for a discussion of the data we’re using to explain this method. We recall the table of results:

X\Y Army Bucknell Holy Cross Lafayette Lehigh Navy
Army x 14-16 14-13 14-24 10-12 8-19
Bucknell 16-14 x 27-30 18-16 23-20 10-22
Holy Cross 13-14 30-27 x 19-15 17-13 9-16
Lafayette 24-14 16-18 15-19 x 12-23 17-39
Lehigh 12-10 20-23 13-17 23-12 x 12-18
Navy 19-8 22-10 16-9 39-17 18-12 x
sm261_baseball-ranking-application_teams-digraph

Win-loss digraph of the Patriot league mens baseball from 2015

Suppose T teams play each other. Let A=(a_{ij})_{1\leq i,j\leq T} be a non-negative square matrix determined by the results of their games, called the preference matrix. In his 1993 paper, Keener defined the score of the ith team to be given by

s_i = \frac{1}{n_i}\sum_{j=1}^T a_{ij}r_j,

where n_i denotes the total number of games played by team i and {\bf r}=(r_1,r_2,\dots ,r_T) is the rating vector (where r_i\geq 0 denotes the rating of team i).

One possible preference matrix the matrix A of total scores obtained from the pre-tournament table below:

A = \left(\begin{array}{rrrrrr} 0 & 14 & 14 & 14 & 10 & 8 \\ 16 & 0 & 27 & 18 & 23 & 28 \\ 13 & 30 & 0 & 19 & 27 & 43 \\ 24 & 16 & 15 & 0 & 12 & 17 \\ 12 & 20 & 43 & 23 & 0 & 12 \\ 19 & 42 & 30 & 39 & 18 & 0 \end{array}\right),

(In this case, n_i=4 so we ignore the 1/n_i factor.)

In his paper, Keener proposed a ranking method where the ranking vector {\bf r} is proportional to its score. The score is expressed as a matrix product A{\bf r}, where A is a square preference matrix. In other words, there is a constant \rho>0 such that s_i=\rho r_i, for each i. This is the same as saying A {\bf r} = \rho {\bf r}.

The Frobenius-Perron theorem implies that S has an eigenvector {\bf r}=(r_1,r_2,r_3,r_4,r_5,r_6) having positive entries associated to the largest eigenvalue $\lambda_{max}$ of A, which has (geometric) multiplicity 1. Indeed, A has maximum eigenvalue \lambda_{max}= 110.0385..., of multiplicity 1, with eigenvector

{\bf r}=(1, 1.8313\dots , 2.1548\dots , 1.3177\dots , 1.8015\dots , 2.2208\dots ).

Therefore the teams, according to Kenner’s method, are ranked,

Army < Lafayette < Lehigh < Bucknell < Holy Cross < Navy.

This gives a prediction failure rate of just 6.7\%.

Memories of TS Michael, by Thomas Quint

TS Michael passed away on November 22, 2016, from cancer. I will miss him as a colleague and a kind, wise soul. Tom Quint has kindly allowed me to post these reminiscences that he wrote up.


Well, I guess I could start with the reason TS and I met in the first place. I was a postdoc at USNA in about 1991 and pretty impressed with myself. So when USNA offered to continue my postdoc for two more years (rather than give me a tenure track position), I turned it down. Smartest move I ever made, because TS got the position and so we got to know each other.

We started working w each other one day when we both attended a talk on “sphere of influence graphs”. I found the subject moderately interesting, but he came into my office all excited, and I couldn’t get rid of him — wouldn’t leave until we had developed a few research ideas.

Interestingly, his position at USNA turned into a tenure track, while mine didn’t. It wasn’t until 1996 that I got my position at U of Nevada.

Work sessions with him always followed the same pattern. As you may or may not know, T.S. a) refused to fly in airplanes, and b) didn’t drive. Living across the country from each other, the only way we could work together face-to-face was: once each summer I would fly out to the east coast to visit my parents, borrow one of their cars for a week, and drive down to Annapolis. First thing we’d do is go to Whole Foods, where he would load up my car with food and other supplies, enough to last at least a few months. My reward was that he always bought me the biggest package of nigiri sushi we could find — not cheap at Whole Foods!

It was fun, even though I had to suffer through eight million stories about the USNA Water Polo Team.

Oh yes, and he used to encourage me to sneak into one of the USNA gyms to work out. We figured that no one would notice if I wore my Nevada sweats (our color is also dark blue, and the pants also had a big “N” on them). It worked.

Truth be told, TS didn’t really have a family of his own, so I think he considered the mids as his family. He cared deeply about them (with bonus points if you were a math major or a water polo player :-).

One more TS anecdote, complete with photo.  Specifically, TS was especially thrilled to find out that we had named our firstborn son Theodore Saul Quint.  Naturally, TS took to calling him “Little TS”.  At any rate, the photo below is of “Big TS” holding “Little TS”, some time in the Fall of 2000.

tslittlets_photo2000

TS Michael in 2000.

Simple unsolved math problem, 7

Everyone’s heard of the number \pi = 3.141592…, right?

pi-pie

Robert Couse-Baker / CC BY http://2.0 / Flickr: 29233640@N07

And you probably know that \pi is not a rational number (i.e., a quotient of two integers, like 7/3). Unlike a rational number, whose decimal expansion is eventually periodic, if you look at the digits of \pi they seem random,

3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482…

But are they really? No one really knows. There’s a paper that explores the statistics of these digits using the first 22.4 trillion digits of \pi. Does any finite sequence of k digits (say, for example, the 4-digit sequence 2016) occur just as often as any other sequence of the same length (say, 1492), for each k? When the answer is yes, the number is called ‘normal.’ That is, a normal number is a real number whose infinite sequence of digits is distributed uniformly in the sense that each digit has the same natural density 1/10, also all possible k-tuples of digits are equally likely with density 1/k, for any integer k>1.

The following simple problem is unsolved:

Conjecture: \pi is normal.