Orthogonal Latin squares

Suppose that we have a set of nk “cells”. Earlier in this sequence of posts, I said that a partition into n sets of k and another partition into k sets of n are orthogonal if any part of the first meets every part of the second in a single cell. If we have two orthogonal partitions, then we have given the set of cells the structure of a k×n rectangle.

I want to consider here the special case k = n. The special feature of this case is that two orthogonal partitions have the same shape, so it is possible to have a collection of more than two partitions, any two of which are orthogonal.

Go back and look at the solution of the diamond squares puzzle. This involved arranging the jacks, queens, kings and aces of a regular pack of cards into a 4 4 array in such a way that each value and each suit occurs once in each row and once in each column. In the solution, we have four partitions of the set of 16 cards, into suits, values, rows, and columns; any two of these partitions are orthogonal.

So suppose we have a collection of r pairwise orthogonal partitions of n2 cells into n sets of n. As explained, the first two partitions give the set of cells the structure of a n×n square. Given any further partition, number its parts from 1 to n, and write in each cell the number of the part containing it. Orthogonality of this partition to the first two implies that each number occurs exactly once in each row and each column; in other words, the structure is a Latin square. (Note that this is a more symmetric way of looking at Latin squares; the usual representation obscures the fact that the three partitions defined by rows, columns and symbols are all on the same footing.)

Now suppose that we have at least four partitions. Use the first two to define the square grid, and then each further partition defines a Latin square. The orthogonality of these partitions implies that any two of the Latin squares have the property that, given a symbol of the first and a symbol of the second, there is exactly one cell in which these symbols occur. In other words, the Latin squares are orthogonal.

How many pairwise orthogonal partitions can we have? Suppose there are r partitions in our set. Choose one cell, and look at the r parts of these partitions which contain it. These parts each contain n−1 further cells, and there is no further overlap, since two parts of different partitions meet in only one cell. So the parts cover r(n−1) cells other than the chosen one. So r(n−1) ≤ n2−1; in other words, r ≤ n+1.

Can the bound be achieved?

Examples can be constructed for prime power values of n; no examples are known for other values. The simplest construction is geometric, and uses the fact (due to Galois) that, if n is a prime power, then there is a field F with n elements. (Finite fields are usually referred to as Galois fields.) Now take the plane with Cartesian coordinates (x,y), where x and y run over F, as the set of cells. One partition consists of the vertical lines x = c, for cF. For each mF, there is also a partition into lines with slope m (having equation y = mx+c, for cF). This gives us our n+1 partitions, and it is clear that any two are orthogonal.

In fact, if there exists a set of n+1 pairwise orthogonal partitions of a set of size n2, then the set of cells has the geometric structure of an affine plane, whose lines are the parts of all these partitions: it is easy to see that any two points lie in a unique line, and that given any line L, there is a unique parallel (a member of the same partition) through any point outside L.

Adding a “line at infinity” to an affine plane gives a projective plane. So the existence questions for the following objects are identical:

  • n+1 pairwise orthogonal partitions of a set of size n2;
  • n−1 pairwise orthogonal Latin squares of order n;
  • an affine plane of order n;
  • a projective plane of order n.

As I said, we know how to construct such things only in the case where n is a prime power. There are constructions other than the one given, but all known constructions have an algebraic flavour, depending on a structure satisfying many of the field axioms. In the other direction, we know that the construction is impossible if n is congruent to 1 or 2 (mod 4) and is not the sum of two squares (the Bruck–Ryser theorem); and we know that it is not possible for n = 10, by a huge computer search by Lam et al.. This is surely one of the big unsolved problems in modern mathematics!

If there is no affine plane of order n, the problem of finding the maximum number of pairwise orthogonal partitions remains. The gap in our knowledge is huge. At one end, Euler conjectured that if n is congruent to 2 (mod 4), there exist three but not four partitions; in other words, there is a Latin square of order n, but no two orthogonal squares. This is true for n = 2 and n = 6, but in the 1960s it was shown by Bose, Shrikhande and Parker that it is false for all other values. Indeed, it is known that the maximum number of orthogonal partitions is bounded below by a slowly-growing function of n.

In the other direction, Bruck showed that there is another slowly-growing function of n with the property that, if a set of orthogonal partitions falls short of the theoretical maximum size n+1 by at most this amount, then it can be completed uniquely to a set achieving the maximm. So if there is no affine plane of order n, then the “defect” is bounded below by an increasing function of n.

But the gap between “a slowly growing function” and “n+1 minus a slowly growing function” is embarrassingly large.

Orthogonal Latin squares were invented by Euler, as a technique for constructing magic squares. He called them Graeco-Latin squares, imagining that the symbols of the first square were Latin letters and those of the second were Greek letters.

Suppose that we have two orthogonal Latin squares of order n, and use the symbol set {0,1,…,n−1} for each square. Superimposing the two squares, we have a pair of digits in each cell, being the base n representation of a number in the range from 0 to n2−1 (all numbers which can be represented by two digits in base n). It is easy to see that the sum of the numbers in any row or column of this array is n(n2−1)/2. If, moreover, the diagonals are transversals for both squares (that is, each symbol of either square occurs once on each diagonal), then the diagonal numbers have the same sum. Adding one to each number, we obtain the more conventional magic squares, with entries {1,…,n2} and row, column and diagonal sums n(n2+1)/2.

If you look back at the diamond puzzle, you will see that it does fulfil all these conditions. So you can use it to construct a 4×4 magic square. The second version of the puzzle asks for prescribed values in two opposite corners.

There is far more to be said about Latin squares. For example, we know how to choose a random Latin square, but not how to choose a random pair of Latin squares. Ian Wanless gave an invited talk about a small part of the theory (questions about transversals) at the recent British Combinatorial Conference. But this is enough for now!

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.

3 Responses to Orthogonal Latin squares

  1. Gordon Royle says:

    Do you think that the absence of any sets of orthogonal partitions “close” to the upper bound for n not a prime power is evidence that projective planes of these orders do not exist?

    • I think so, but on no very good grounds.

      There are quite a lot of ways in which to measure how close we are to a projective plane; the maximum number of orthogonal partitions; the maximum number of permutations any two agreeing in at most one position; the maximum number of entries that can be put into a putative incidence matrix. (The first corresponds to adding lines a parallel class at a time; the second to adding lines one at a time; in the third you are allowed to add incomplete lines.) They seem to give rather different measures of how far away from a plane you can get. This might be a good topic for someone to investigate…

  2. A Magic Mapping occurs when we map any Latin Square across any Magic Square. Some Magic Mappings fail to regenerate a Latin Square, but produce values in a wide variety of arrangements. Read more about it on my blog: http://www.glennwestmore.com.au/category/latin-squares/.

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