Picture of an isomorphism

We spent a very busy and enjoyable weekend with Hans Hockey, a statistician who lives in Hamilton, and his family.

When we arrived, Hans showed me a picture he had taken, of the 81 SET cards laid out on a table in an arrangement with a number of remarkable properties, which I describe here. It turns out that it is a picture of an isomorphism between the SET pack and the Sudoku grid.

SET

The game SET is played with a pack of 81 cards. Each card carries a picture
with four attributes, each with three possible values:

  • the number of copies of a symbol may be 1, 2 or 3;
  • the colour of the symbol may be red, green or purple;
  • the shape of the symbol may be diamond, oval, or “squiggle”;
  • the shading of the symbol may be hollow, line shaded, or solid.

A set of three cards is a SET if the values of each attribute are either all the same or all different. It is easy to see that any two cards are contained in a unique SET; so the cards and SETs form a Steiner triple system of order 81.

A SET  Another SET

Coordinatisation

Label the three values of each attribute with the three elements 0, 1, 2 of the field GF(3) (the integers modulo 3). The labelling is arbitrary, although it is natural to label the number of symbols with its value modulo 3. Thus each card is identified by a 4-tuple of elements of GF(3).

The 4-dimensional affine space over GF(3) is defined as follows: the points are the vectors of a 4-dimensional vector space over GF(3); lines, planes and 3-spaces are cosets (translates) of subspaces of dimension 1, 2, 3 respectively of the vector space.

For example, a line has the form {0,b,2b}+a = {a,a+b,a+2b}, where a and b are vectors and b ≠ 0. Observe that

  • The three points in a line sum to 0 (using the fact that 3a = 3b = 0); and conversely, three points which sum to 0 form a line of the affine space.
  • In GF(3), three elements sum to 0 if and only if they are either all equal or all distinct.

As a corollary of the last two statements, we see that three cards form a SET if and only if their coordinates form a line in the affine space. So we have identified the Steiner system formed by the SET cards with the points and lines of the affine space.

Planes and 3-spaces

Three points of the affine space which do not form a line “generate” a plane. (If the three points are x,y,z, then the plane is the translate by x of the vector subspace spanned by yx and zx.)

The structure of the 9-point affine plane over GF(3) is most easily shown by arranging the points in a 3×3 array, so that the rows and columns of the array are lines. The other lines can be described as the sets of three positions corresponding to the six terms in the expansion of a 3×3 determinant: that is, each set has one point in each row and one in each column, and the six possible such sets form the remaining lines. In particular, the two diagonals of the square are lines.

This can be realised by SET cards as shown.

A plane

In a similar way, four points, with no three collinear and not contained in a plane, generate a 3-space, which could be imagined by going into the third spatial dimension and stacking three planes one above the other. Then the vertical and diagonal lines containing three points, one from each plane, are also affine lines; but there are others too, which become harder to imagime.

Five points, with no three collinear, no four coplanar, and not lying in a 3-space, generate the entire geometry.

Laying out the SET cards

We’ve seen how to lay out nine cards forming a plane.

Now choose one of the 72 remaining cards and put it next to the plane, in row 1 and column 4. Then we can fill in three rows of nine cards each to form a 3-space. For example, positions (1,1), (1,4) and (1,7) must form a SET, which determines the card in position (1,7).

Finally, choose one of the 54 remaining cards, and place it in row 4 and column 1. Now similar rules determine the position of every card in the pack. We end up with a layout which might look like this:

The complete layout

The layout has various other properties. For example, the central card in the centre square and any two cards in diametrically opposite positions always form a SET.

The Sudoku grid

The 9×9 layout can be matched up with the Sudoku grid. Details are in a paper by Rosemary Bailey, Robert Connelly and me in the American Mathematical Monthly 115 (2008), 383–404.

We coordinatise the grid with four coordinates, each taking values 0, 1 or 2, as follows. The first coordinate describes which “fat row” of three 3×3 squares the chosen cell lies in; the second tells which row within that fat row it is in; the third and fourth coordinate describe the same for columns.

We use this coordinatisation, together with properties of the affine and projective spaces and other discrete structures such as Hamming codes, to give a complete description of symmetric Sudoku, a variant of Sudoku invented by Connelly and independently by Vaughan Jones.

If we regard the coordinates as lying in GF(3), we see that the rows, columns and subsquares of the Sudoku grid are affine planes. Indeed, they are defined by equations of the form

  • x1 = a, x2 = b (for rows);
  • x3 = c, x4 = d (for columns);
  • x1 = e, x3 = f (for subsquares).

Thus, our picture above of the SET cards layout is really a picture of an isomorphism between the SET pack and the Sudoku grid, as claimed.

The five cards in positions (1,1), (1,2), (1,4), (2,1) and (4,1) determine everything. (In the Sudoku numbering these are 0000, 0001, 0010, 0100 and 1000, so the origin and the standard basis for the vector space.)

So now look at the cards in these positions, and suppose that you have chosen the numbering of attributes so that their Set coordinates are a, b, c, d, e. (Each of these is a 4-tuple, regarded as a vector in the 4-dimensional vector space.) Then the card in position with Sudoku coordinates wxyz is the one with Set coordinates a+z(ba)+y(ca)+x(da)+w(ea) – this is the linear function which takes the values a, b, c, d, e on the five points given.

In particular, if the cards in these five positions have Set coordinates equal to their Sudoku coordinates 0000, 0001, etc., then every card in the layout will have its Set coordinates equal to its Sudoku coordinates.

Counting

There are 81 choices of the first card to go in the top right position, then 80 choices of the card to put to its right, 78 for the card beneath it (the unique card forming a set with the first two is excluded), 72 for the card in position (1,4), and 54 for the card in position (4,1). So the total number of arrangements of the pack is 81.80.78.72.54 = 1965150720, a large number but tiny by comparison with the total number 81! of orderings of the pack. The chance of producing this layout at random is vanishingly small.

Some of the arrangements are special. For example, all the cards having a particular value of a particular attribute form a 3-space. So we could arrange the cards so that the first three rows are red, the next three green, and the last three purple, for example.

Magic squares

It fairly often happens that the nine cards of an affine plane, laid out in a 3×3 array, form a magic square: the number of symbols in any row, column or diagonal is 6. This is because, of the 1080 lines (SETs), 729 have the property that the numbers are all different. So often we will end up with a plane in which all but three of the lines have all the numbers different. If we lay this plane out so that the main diagonal has the three cards bearing 2 symbols each, we will have a magic square as required. In fact, of the 81.80.78 = 505440 plane layouts, 27.26.54.2 = 75816 will be magic squares of this form. [A magic square must have one of the two diagonals having two symbols on its cards. Assuming it is the principal diagonal, there are 27.26 ways to choose two cards with two symbols, and 54 ways to choose a card with a different number of symbols for position (1,2): this determines the plane.]

There is another, slightly silly, kind of magic square: those in which every card carries two symbols. There are 27.26.24 = 16848 of these, giving
altogether 92664 magic squares, or 11/60 of the total number of planes.

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , , , , , . Bookmark the permalink.

One Response to Picture of an isomorphism

  1. Some interesting background history on Magic Squares in art, science and culture on this blog: http://www.glennwestmore.com.au

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s