Jesse Douglas – yet another Beautiful Mind?

Nobel prize winner John Nash struggled with mental illness for most of his life. His struggles were described Sylvia Nasar’s well-known biography, A Beautiful Mind, as well as a film of the same name starring Russell Crowe. Now, John Nash is practically a household name, honored for his contributions to the mathematics of game theory and economics.

While Jesse Douglas isn’t nearly as well-known as Nash, and didn’t win a Nobel Prize, he was (with Lars Ahlfors in 1936) the first recipient of the Fields Medal. According to one source, he too struggled with mental illness. However, before talking about the life of Jesse Douglas, let’s talk about his mathematical research.

Jesse-Douglas-1940-1941_250x250

Jesse Douglas in his 40s.

His Mathematics

Jesse Douglas solved a geometrical problem formulated in the 1700’s now called Plateau’s problem.  Plateau’s problem (also known as the soap bubble problem) is to show the existence of a minimal surface with a given boundary. Plateau was a a Belgian physicist who lived in the 1800s, known for his experiments with soap films. A minimal surface is a surface that locally minimizes its area. For example, the catenoid (see below) obviously doesn’t have minimum area for its (disconnected) boundary, but any piece of it bounded by a (connected) closed curve does have minimum area.

 

 

 

His research was not universally recognized at first. According to Reid [R76]:

Arriving in the year 192901930 at the end of a European tour as a National Research Fellow, he proposed to talk about his not-yet-published work on Plateau’s Problem at the weekly meeting of the mathematische Gesellschaft [at Gottingen University]. The problem had been around for a long time. Many outstanding mathematicians, including Riemann himself, had worked on it. The members of the Gesellschaft simply did not believe that an American had solved it. … When he had finished his presentation, some of the members of the Gesellschaft took him severely to task on almost every detail of the proof. Let left Gottingen deeply offended …

Douglas solved this geometrical problem in his paper “Solution of the problem of Plateau,” Trans. Amer. Math. Soc. 33 (1931)263–321. Gray and Micallef [GM07] do an excellent job of describing Jesse’s mathematical approach to the problem. Jesse continued working on generalizing and refining aspects of his research on this problem for the next 10 years or so. Some of his papers in this field include

  • A method of numerical solution of the problem of Plateau, Annals of Mathematics 29(1927 – 1928)180-188
  • Solution of the problem of Plateau, Trans. Amer. Math. Soc. 33 (1931) 263–321.
  • Systems of K-dimensional manifolds in an N-dimensional space, Mathematische Annalen 105 (1931) 707-733.
  • The Problem of Plateau for Two Contours, Studies in Applied Mathematics 10(1931)315-359.
  • One-sided minimal surfaces with a given boundary, Trans. Am Math Soc 34(1932)731–756.
  • A Jordan space curve no arc of which can form part of a contour which bounds a finite area, Annals of Mathematics 35(1934) 100-103.
  • Green’s function and the problem of Plateau, American Journal of Mathematics. 61 (1939) 545–589.
  • The most general form of the problem of Plateau, American Journal of Mathematics. 61 (1939)590–608.
  • Solution of the inverse problem of the calculus of variations, Proceedings of the National Academy of Sciences. 25(1939) 631–637.
  • The analytic prolongation of a minimal surface across a straight line, Proc Natl Acad Sci USA. 25(1939)375-377.
  • The higher topological form of Plateau’s problem, Annali della Scuola Normale Superiore di Pisa , 8 (1939)195-218.
  • Minimal surfaces of higher topological structure, Annals of Mathematics 40(1939) 205-298 .
  • Theorems in the inverse problem of the calculus of variations, Proc Natl Acad Sci USA, 26(1940) 215–221.

He also wrote papers in other fields in mathematics, for example, the theory of finite groups. For example, in 1951 he published a series of short articles On finite groups with two independent generators, all in the Proc. Natl. Acad. Sci. USA. Also, in 1953, he published a series of short articles On the basis theorem for finite abelian groups, again, all in the Proc. Natl. Acad. Sci. USA.

His Life

Jesse’s father, Louis, was a Polish immigrant who moved to Canada sometime in the late 1800s. The family name was changed at Canadian Immigration and I don’t know his original name. At some point, Louis married Sarah Kommel (I don’t know when the move occurred, nor when and where they met) and moved to New York City. I think both Louis and Sarah were Jewish. Jesse was born in NYC on July 3rd, 1897. According to a geneology website, Sarah’s parents were Leazar Louis Kommel (1851-1923) and Chaya Lande, who died in 1906. Jesse’s mother Sarah passed away in 1939, a year before Jesse married (as we will see below).

Jesse was educated at public schools in New York City. According to Steinhardt [St92], Jesse had a photographic memory. After graduation from high school, he entered the City College of New York and won the Belden Medal for excellence in mathematics in his first year at City College of New York, the youngest recipient at the time. He graduated with a B.Sc. cum laude in February 1916 at the age of 18. Then he entered Columbia University to undertake research under the supervision of Edward Kasner. He took part in Kasner’s seminar on differential geometry and it was there that Jesse first heard of Plateau’s Problem. He submitted his doctoral thesis On Certain Two-Point Properties of General Families of Curves in 1920 (some references say 1921). After getting his PhD, he was an instructor at Columbia from 1920 to 1926. (Was this in the statistics department or the mathematics department? I don’t know.)

He won a National Research Fellowship and as a result, traveled widely for four years, visiting Princeton and Harvard in 1927, Chicago in 1928, and Paris from 1928 to 1930, with trips to Gottingen, Hamburg, and Rome. Jesse was offered an Assistant Professor position at MIT in January 1930. He took leave of absence for a term in 1932. After his promotion to Associate Professor at MIT in 1934, he almost at once took leave of absence again to be a Research Worker at the Institute for Advanced Study in Princeton from 1934 to 1935.  After returning to MIT, Jesse was awarded the first Fields Medal, together with Lars Ahlfors, in 1936. Once again, Jesse took leave of absence from MIT in 1936, and on 1 July 1938, he resigned. According to Aronson [A13], Jesse “became ill” at this time and Levinson was eventually hired as his replacement.

This may seem like the romantic life of a world-class mathematician, but it really is very unusual to be “homeless” 18 years after your get your PhD degree. Something is going on. According to Hersh [H10]:

Douglas’s name is almost forgotten today. He is a rather tragic figure, one of several important mathematicians gravely handicapped by what are now called bipolar, and used to be called manic-depressive, symptoms. He had a junior position at M.I.T., which he lost as a result of inability to perform consistently in the classroom.

According to Steinhardt [St92],

… the volatility of this mix of great gifts and sharp emotions [in which his “over-sized sensitivity surfaced not infrequently in intense feelings articulated vigorously to colleagues”] in Douglas’ makeup worked to the disadvantage of the great American mathematician’s external fortunes.

I don’t know what he did professionally in the 1939-1940 period, but he married Jessie Nayler on June 30th, 1940 (they had one son Lewis Philip Douglas). The husband named Jesse and the wife named Jessie! He often taught summer courses at Columbia University, as well as courses at Yeshiva University. The following year, Jesse was a Guggenheim fellow at Columbia University from 1940 to 1941. He taught at Brooklyn College from 1942 to 1946, as an assistant professor. His teaching during these war years went well according to a letter of commendation (did he teach students from the US Military Academy during this time?), and he received a Distinguished Service Award. In 1945, Jesse wrote an application letter for a teaching position saying [St92]:

This semester I have a teaching load of 19 hours per week at Brooklyn College, including two advances courses: complex variables and calculus of variations.

It is no surprise that he published nothing in the period 1942-1950. According to Micallef [M13],

There is a blank in Douglas’s career from 1946 to 1950, and the later part of Douglas’ life seems to have been troubled. His marriage ended in divorce in 1950.

In 1951, Jesse published a string of papers in a completely different field, finite group theory. Perhaps the end of Jesse’s marriage to Jessie caused him to reinvent himself, mathematically?

According to some sources, Douglas harbored resentment towards his research “competition” Rado (who he strongly beieved should not be credited with solving Plateau’s Problem [St92]) and Courant, as well as J.F. Ritt at Columbia, who may have blocked his appointment to a permanent position at his alma mater. (Sadly, anti-Semitic prejudices common of those times may have played a role in Jesse’s troubles in this regard.) Never-the-less, he is remembered as a helpful, sympathetic, and approachable colleague [St92].

His resentment of Courant was unfortunate because some 10 years earlier, in March 1935, Courant invited Jesse to speak at NYU. According to Reid [R76]:

Courant’s invitation to Douglas to speak at NYU was to a certain extent an olive branch. … Remembering this past history [Jesse’s reception at Gottingen 5 years earlier], Courant did his best to make Douglas’ lecture at NYU an event.

Clearly, Courant appreciated Jesse’s work and tried to treat him with due respect.

Other than Jesse’s mathematical research, this does not appear to have been a happy period in Jesse’s life. According to O’Conner and Robertson [OCR],

His [ex-]wife, Jessie Douglas died in 1955, the year in which Douglas was appointed professor of mathematics at the City College of New York. He remained in that post for the final ten years of his life, living in Butler Hall, 88 Morningside Drive in New York.

Steinhardt [St92] recalls the difficulty that Abraham Schwartz had in having CCNY give tenure at the full professor level to Jesse, when he was 1958. Except for the logician Emil Post, there was no one at CCNY at the time close to Jesse’s stature as a researcher. Ironically, a number of CCNY mathematicians “felt threatened by the appointment”, presumably fearing Jesse would require them to work harder.

There are a number of anecdotes of Jesse Douglas and his interactions with students. They aren’t universally flattering and I hesitate to repeat the negative ones, as I don’t know how typical they are. A number of sources suggest that when he was feeling well, he could be an impressive, charismatic, self-confident expositor and a lucid  teacher. While I don’t know the teaching load at Columbia University the time (where he belonged), I do know that, compared to today’s teaching loads, they were often quite heavy (see for example Parikh’s biography, The Unreal Life of Oscar Zariski). Are these unflattering reports of Jesse’s interactions with students merely due to his oppressive teaching load and inability to handle that volume of students? I don’t know. Perhaps he held others to the same very high standards that he held himself in his own mathematical research.

Unfortunately, not enough is known about this very remarkable mathematician.

References

[A13] D.G. Aronson, Norman Levinson: 1912-1975, Biographical memoirs, Nat. Acad. Sci., 2013.

[GM07] Jeremy Gray, Mario Micallef, The work of Jesse Douglas on minimal surfaces, 2013. (appeared in Bull AMS 2008)  pdf

[H10] R. Hersh, Under-represented then over-represented, College J. Math, 2010.

[M13] M. Micallef, The work of Jesse Douglas on Minimal Surfaces, talk at Universidad de Granada, 2013-02-07.

[OCR] John J. O’Connor and Edmund F. Robertson, Jesse Douglas.

[R76] C. Reid, Courant, Springer-Verlag, 1976.

[St92] F. Steinhardt, “Jesse Douglas as teacher and colleague”, in The Problem of Plateau, ed. T. Rassias, World Scientific, 1992.

Ring theory, via coding theory and cryptography

In these notes on ring theory, I tried to cover enough material to get a feeling for basic ring theory, via cyclic codes and ring-based cryptosystems such as NTRU. Here’s a list of the topics.

1 Introduction to rings
1.1 Definition of a ring
1.2 Integral domains and fields
1.3 Ring homomorphisms and ideals
1.4 Quotient rings
1.5 UFDs
1.6 Polynomial rings
1.6.1 Application: Shamir’s Secret Sharing Scheme
1.6.2 Application: NTRU
1.6.3 Application: Modified NTRU
1.6.4 Application to LFSRs

2 Structure of finite fields
2.1 Cyclic multiplicative group
2.2 Extension fields
2.3 Back to the LFSR

3 Error-correcting codes
3.1 The communication model
3.2 Basic definitions
3.3 Binary Hamming codes
3.4 Coset leaders and the covering radius
3.5 Reed-Solomon codes as polynomial codes
3.6 Cyclic codes as polynomial codes
3.6.1 Reed-Solomon codes as cyclic codes
3.6.2 Quadratic residue codes
3.6.3 BCH bound for cyclic codes
3.6.4 Decoding cyclic codes
3.6.5 Cyclic codes and LFSRs

4 Lattices
4.1 Basic definitions
4.2 The shortest vector problem
4.2.1 Application to a congruential PKC
4.3 LLL and a reduced lattice basis
4.4 Hermite normal form
4.5 NTRU as a lattice cryptosystem

Calculus on graphs

In these notes, I tried to cover enough material to get a feeling for “calculus on graphs”, with applications to sports rankings and the Friendship Theorem. Here’s a list of the topics.

1 . Introduction
2. Examples
3. Basic definitions
3.1 Diameter, radius, and all that
3.2 Treks, trails, paths
3.3 Maps between graphs
3.4 Colorings
3.5 Transitivity
4. Adjacency matrix
4.1 Definition
4.2 Basic results
4.3 The spectrum
4.4 Application to the Friendship Theorem
4.5 Eigenvector centrality and the Keener ranking
4.6 Strongly regular graphs
4.7  Orientation on a graph
5. Incidence matrix
5.1 The unsigned incidence matrix
5.2 The oriented case
5.3 Cycle space and cut space
6. Laplacian matrix
6.1 The Laplacian spectrum
7  Hodge decomposition for graphs
7.1 Abstract simplicial complexes
7.2 The Bjorner complex and the Riemann hypothesis
7.3 Homology groups
8. Comparison graphs
8.1 Comparison matrices
8.2 HodgeRank
8.3 HodgeRank example

Gray codes

This is based on work done about 20 years ago with a former student Jim McShea.

Gray codes were introduced by Bell Labs physicist Frank Gray in the 1950s. As introduced, a Gray code is an ordering of the n-tuples in GF(2)^n = \{0,1\}^n such that two successive terms differ in only one position. A Gray code can be regarded as a Hamiltonian path in the cube graph. For example:

[[0, 0, 0], [1, 0, 0], [1, 1, 0], [0, 1, 0], [0, 1, 1], [1, 1, 1], [1, 0, 1], [0, 0, 1]]

These can be generalized to n-tuples of integers (mod m) in the obvious way.

Gray codes have several applications:

  • solving puzzles such as the Tower of Hanoi and the Brain [G],
  • analog-digital-converters (goniometers) [S],
  • Hamiltonian circuits in hypercubes [Gil] and Cayley graphs of Coxeter groups [CSW],
  • capanology (the study of bell-ringing) [W],
  • continuous space-filling curves [Gi],
  • classification of Venn diagrams [R],
  • design of communication codes,
  • and more (see Wikipedia).
brain-puzzle

The Brain puzzle

Here's a SageMath/Python function for computing Gray codes.
def graycode(length,modulus):
    """
    Returns the n-tuple reverse Gray code mod m.


    EXAMPLES:
        sage: graycode(2,4)
        
        [[0, 0],
         [1, 0],
         [2, 0],
         [3, 0],
         [3, 1],
         [2, 1],
         [1, 1],
         [0, 1],
         [0, 2],
         [1, 2],
         [2, 2],
         [3, 2],
         [3, 3],
         [2, 3],
         [1, 3],
         [0, 3]]

    """
    n,m = length,modulus
    F = range(m)
    if n == 1:
        return [[i] for i in F]
    L = graycode(n-1, m)
    M = []
    for j in F:
        M = M+[ll+[j] for ll in L]
    k = len(M)
    Mr = [0]*m
    for i in range(m-1):
        i1 = i*int(k/m)
        i2 = (i+1)*int(k/m)
        Mr[i] = M[i1:i2]
    Mr[m-1] = M[(m-1)*int(k/m):]
    for i in range(m):
        if is_odd(i):
            Mr[i].reverse()
    M0 = []
    for i in range(m):
        M0 = M0+Mr[i]
    return M0


REFERENCES

[CSW] J. Conway, N. Sloane, and A. Wilks, “Gray codes and reflection groups”, Graphs and combinatorics 5(1989)315-325

[E] M. C. Er, “On generating the N-ary reflected Gray codes”, IEEE transactions on computers, 33(1984)739-741

[G] M. Gardner, “The binary Gray code”, in Knotted donuts and other mathematical entertainments, F. H. Freeman and Co., NY, 1986

[Gi] W. Gilbert, “A cube-filling Hilbert curve”, Math Intell 6 (1984)78

[Gil] E. Gilbert, “Gray codes and paths on the n-cube”, Bell System Technical Journal 37 (1958)815-826

[R] F. Ruskey, “A Survey of Venn Diagrams“, Elec. J. of Comb.(1997), and updated versions.

[S] Web page of T. Sillke

[W] A. White, “Ringing the cosets”, Amer. Math. Monthly 94(1987)721-746

Elizebeth Friedman and the Holmwood case

Elizebeth Smith Friedman was the top cryptographer for the Coast Guard (then the enforcement arm of the Department of the Treasury) during the Prohibition Era.

According to wrecksite.eu, the SS Holmwood was a steam ship made in 1911. It was a New Zealand passenger/cargo ship with dimensions 50.4 x 8 x 3.9 m and equipped with a triple expansion engine and a 1 singleboiler engine, capable of 78 n.h.p..

The Holmwood case is a prohibition-era legal investigation concerning events up to and including the seizure of the SS Holmwood in October 5, 1933, in the Hudson River, and the subsequent trial of the smugglers. The New York Intelligence Office (of the Coast Guard, as part of the Treasury Department) used Elizebeth Friedman’s cryptanalysis of telegraph messages between the Holmwood and shore-based agents.

The best source of information from the ESF collection at the Marshall library, Box 6, File 24, “Notes on the solution of cipher and code used by the Holmwood” (14 pages), dated October 11, 1934. This document describes the investigation of the liquor smuggling operations of the Holmwood from 1930 to 1934. The first interception was November, 1930, by the New York Intelligence Office of the Treasury Department. The Coast Guard operated radio stations which monitored rum-runner telegraph stations. Usually these were in a telegraph cipher-code but sometimes they were in plain English. For example, it was reported that at 1505 on October 3, 1933, Radioman First Class B. E. Howell, of the New York Intelligence Unit, intercepted the following message

Anchor the boat in good place immediately. Take all men off in one of life boats. Hide the life boat if possible. Come ashore on New York side. Call [undecoded phone number] when you come ashore. PA code.

This message was preceded by a telegraph cipher-code

JDSLE 2221 1612 WJJE …. DEMPY.

which was decoded (by the office of ESF) as

Heave your anchor immediately and get underway. Stand up the river towards Albany.

This led to the seizure of the Holmwood. ESF wrote a strong commendation letter for Radioman Howell for his hard work and dedication to service.

For more on the life of Elizebeth Friedman, see [1], [2], or the book Divine Fire, by Katie Letcher Lyle (and some additional material by myself).

[1] Smith, G. Stuart, A Life in Code: Pioneer Cryptanalyst Elizebeth Smith Friedman, McFarland & Company, Jefferson, NC, 2017.

[2] Fagone, Jason, The Woman Who Smashed Codes: A True Story of Love, Spies, and the Unlikely Heroine Who Outwitted America’s Enemies, Dey Street Books, New York, 2017

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.