Goldsmiths’ 2014 Mathematics

Tuesday 22nd July

Latin Squares and related combinatorial designs

Professor L H Soicher

image

Recreational maths can lead to lots of different applications.

http://en.wikipedia.org/wiki/Sudoku

Sudoku (originally called Number Place, is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9 × 9 grid with digits so that each column, each row, and each of the nine 3 × 3 sub-grids that compose the grid (also called “boxes”, “blocks”, “regions”, or “sub-squares”) contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a unique solution.

Completed puzzles are always a type of Latin square with an additional constraint on the contents of individual regions. For example, the same single integer may not appear twice in the same row, column or in any of the nine 3×3 subregions of the 9 x 9 playing board.

The puzzle was popularized in 1986 by the Japanese puzzle company Nikoli, under the name Sudoku, meaning single number. It became an international hit in 2005.

Sudoku puzzles are very popular and can give you a buzz when solving them.

Here is “Sudoku #043 (Medium)” from Livewire Puzzles

image

(http://www.puzzles.ca/sudoku.html)

Why not have a go as I am going to be mean and not give you the answer.

Like mathematical research solving a Sudoku puzzle requires you to think mathematically.

The problem is stated precisely and has a precisely defined solution.

You need to think logically and apply appropriate algorithms precisely.

However solving soduku is different from mathematical research because it has only one solution. With research you don’t know if there is going to be even one solution to a problem or many solutions. Sudoku puzzles are limited to small sizes (usually 9 by 9) and use limited shapes of subregions (usually subsquares), but mathematicians usually want to study a problem in greater generality, and obtain proved truths (theorems).

A completed Sudoku is an example of a combinatorial design, in which objects from a finite set are placed in a given structure so that given properties are satisfied.

http://en.wikipedia.org/wiki/Combinatorial_design

Combinatorial designs include mathematical objects called block designs, Latin squares, gerechte designs, mutually orthogonal Latin squares, SOMAs, orthogonal arrays, generalised t-designs, and many more.

In combinatorial mathematics, a block design is a set together with a family of subsets (repeated subsets are allowed at times) whose members are chosen to satisfy some set of properties that are deemed useful for a particular application. These applications come from many areas, including experimental design, finite geometry, software testing, cryptography, and algebraic geometry. Many variations have been examined, but the most intensely studied are the balanced incomplete block designs (BIBDs or 2-designs) which historically were related to statistical issues in the design of experiments.

http://en.wikipedia.org/wiki/Block_design

In combinatorics and in experimental design, a Latin square is an n × n array filled with n different symbols, each occurring exactly once in each row and exactly once in each column.

image

http://en.wikipedia.org/wiki/Latin_square

Gerechte designs were introduced by W.U. Behrens in 1956.

A gerechte design is an n × n table filled with n different symbols and partitioned into n regions, each containing n small squares of the grid, in such a way that each symbol occurs exactly once in each row, each column and each region. Sometimes numbers are replaced by colours.

http://zimmer.csufresno.edu/~ovega/research/Centennial.pd

A set of mutually orthogonal latin squares, or MOLS, is a set of two or more latin squares of the same order, all of which are orthogonal to one another.

Let L1, L2 and L3 be three latin squares of order n = 4

image

Then

image

image

Since L1 and L2 are orthogonal, as well as L1 with L3, and L2 with L3. We say that L1, L2 and L3 are MOLS.

The Soma cube is a solid dissection puzzle invented by Piet Hein in 1933 during a lecture on quantum mechanics conducted by Werner Heisenberg. Seven pieces made out of unit cubes must be assembled into a 3x3x3 cube. The pieces can also be used to make a variety of other 3D shapes.

image

Piet Hein (16 December 1905 – 17 April 1996) was a Danish scientist, mathematician, inventor, designer, author, and poet, often writing under the Old Norse pseudonym “Kumbel” meaning “tombstone”.

http://en.wikipedia.org/wiki/Piet_Hein_(scientist)

SOMAs are involved in tractor deeding units.

http://en.wikipedia.org/wiki/Soma_cube

In mathematics, in the area of combinatorial designs, an orthogonal array is a “table” (array) whose entries come from a fixed finite set of symbols (typically, {1,2,…,n}), arranged in such a way that there is an integer t so that for every selection of t columns of the table, all ordered t-tuples of the symbols, formed by taking the entries in each row restricted to these columns, appear the same number of times. The number t is called the strength of the orthogonal array. Below is a simple example of an orthogonal array with symbol set {1,2}:

image

http://en.wikipedia.org/wiki/Orthogonal_array

A t-(v, k, l) design, or (for short) a t-design, is an incidence structure of points and blocks with the following properties:

there are v points;

each block is incident with k points;

any t points are incident with l common blocks.

http://designtheory.org/library/encyc/tdes/g/

http://www.maths.qmul.ac.uk/~mj/AnnCook/08-09/Patterson.pdf

Combinatorial designs are studied by statisticians for their use in the design of comparative experiments, and by pure mathematicians for their often beautiful structure and connections to finite geometry, graph theory (the study of connections and networks) and group theory (the abstract study of symmetry).

A finite geometry is any geometric system that has only a finite number of points.

image

The image above is a finite affine plane of order 2, containing 4 points and 6 lines. Lines of the same colour are “parallel”.

http://en.wikipedia.org/wiki/Finite_geometry

In mathematics and computer science, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A “graph” in this context is made up of “vertices” or “nodes” and lines called edges that connect them. A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another; see graph (mathematics) for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics.

image

A drawing of a graph

http://en.wikipedia.org/wiki/Graph_theory

In mathematics and abstract algebra, group theory studies the algebraic structures known as groups. The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces can all be seen as groups endowed with additional operations and axioms. Groups recur throughout mathematics, and the methods of group theory have influenced many parts of algebra. Linear algebraic groups and Lie groups are two branches of group theory that have experienced advances and have become subject areas in their own right.

Various physical systems, such as crystals and the hydrogen atom, can be modelled by symmetry groups. Thus group theory and the closely related representation theory have many important applications in physics, chemistry, and materials science. Group theory is also central to public key cryptography.

http://en.wikipedia.org/wiki/Group_theory

First, a completed Sudoku is an example of a Latin square of order n, which is an n by n array, with each cell of the array containing just one element from a given set of n symbols, such that each of the n symbols occurs once in each row and once in each column of the array.

Next, a completed Sudoku is a special case of a gerechte design, which is a Latin square of order n whose cells are partitioned into n regions, each containing n cells, such that each symbol occurs once in each region. As mentioned previously, Gerechte designs were introduced in 1956 by W.U. Behrens for the statistical design of agricultural experiments.

Examples

Below left is a Latin square of order 4.

image

Above right is a gerechte design. The regions are indicated by the colours, and are defined by the positions of the symbols in the Latin square on the left (so the white region consists of the cells where 1 occurs, the yellow region where 2 occurs, and so on).

When an n by n gerechte design can be made in this way, having regions defined by the positions of the symbols in a given Latin square of order n, we see that when we superimpose the Latin square of the gerechte design on the given Latin square, like so:

image

that the cells contain every possible pairing of a symbol from one square with a symbol from the other square (there are exactly n^2 such pairings), and we say that our two Latin squares are orthogonal.

A set of Latin squares of order n is called a set of mutually orthogonal Latin squares (or MOLS) when each pair of distinct squares in the set are orthogonal.

For a given n, the maximum size that a set of MOLS of order n can attain is denoted by N(n). The example below illustrates a set of three MOLS of order 4, superimposed, and shows that N(4) is at least 3.

image

Some things known about N(n)

image

image

Leonhard Euler (15 April 1707 – 18 September 1783) was a pioneering Swiss mathematician and physicist. He made important discoveries in fields as diverse as infinitesimal calculus and graph theory. He also introduced much of the modern mathematical terminology and notation, particularly for mathematical analysis, such as the notion of a mathematical function. He is also renowned for his work in mechanics, fluid dynamics, optics, astronomy, and music theory.

http://en.wikipedia.org/wiki/Leonhard_Euler

Gaston Tarry (September 27, 1843 – June 21, 1913) was a French mathematician. Born in Villefranche de Rouergue, Aveyron, he studied mathematics at high school before joining the civil service in Algeria.

He pursued mathematics as an amateur, his most famous achievement being his confirmation in 1901 of Leonhard Euler’s conjecture that no 6 × 6 Graeco-Latin square was possible.

http://en.wikipedia.org/wiki/Gaston_Tarry

N(n) is at least 2 unless n = 2 or n = 6. (This was proved in 1960 by R.C. Bose, S.S. Shrikhande and E.T. Parker. Euler had conjectured that there were no pairs of orthogonal Latin squares of order n for n = 2, 6, 10, 14, 18, and so on, but this turned out to be spectacularly wrong.)

image

Raj Chandra Bose (19 June 1901 – 31 October 1987) was an Indian American mathematician and statistician best known for his work in design theory and the theory of error-correcting codes in which the class of BCH codes is partly named after him. He was notable for his work along with S. S. Shrikhande and E. T. Parker in their disproof of the famous conjecture made by Leonhard Euler dated 1782 that there do not exist two mutually orthogonal Latin squares of order 4n + 2 for every n.

http://en.wikipedia.org/wiki/Raj_Chandra_Bose

Sharadchandra Shankar Shrikhande (born October 19, 1917) is an Indian mathematician with distinguished and well-recognized achievements in combinatorial mathematics. He is notable for his breakthrough work along with R. C. Bose and E. T. Parker in their disproof of the famous conjecture made by Leonhard Euler dated 1782 that there do not exist two mutually orthogonal latin squares of order 4n + 2 for every n. Shrikhande’s specialty was combinatorics, and statistical designs. Shrikhande graph is used in statistical designs.

http://en.wikipedia.org/wiki/Sharadchandra_Shankar_Shrikhande

Ernest Tilden Parker is a professor emeritus of The University of Illinois. He is notable for his breakthrough work along with R. C. Bose and S. S. Shrikhande in their disproof of the famous conjecture made by Leonhard Euler dated 1782 that there do not exist two mutually orthogonal latin squares of order 4n + 2 for every n. He was at that time employed in the UNIVAC division of Remington Rand, but he subsequently joined the mathematics faculty at The University of Illinois. In 1968, he and a Ph.D. student, K. B. Reid, disproved a conjecture on tournaments by Erdős and Moser.

http://en.wikipedia.org/wiki/E._T._Parker

If n divided by 4 has remainder 1 or 2 and n is not the sum of two squares of integers, then N(n) < n – 1. (This was proved by R.H. Bruck and H.J. Ryser in 1949. Thus, for example, N(14) < 13.)

Richard Hubert Bruck (December 26, 1914 – 1991) was an American mathematician best known for his work in the field of algebra, especially in its relation to projective geometry and combinatorics.

http://en.wikipedia.org/wiki/R._H._Bruck

image

Herbert John Ryser (July 28, 1923, Milwaukee, Wisconsin – July 12, 1985, Pasadena, California) was a professor of mathematics, widely regarded as one of the major figures in combinatorics in the 20th century. He is the namesake of the Bruck–Ryser–Chowla theorem and Ryser’s formula for the computation of the permanent of a matrix.

http://en.wikipedia.org/wiki/H._J._Ryser

Although

image

so the converse of the above result is false. (This was shown by C.W.H. Lam et al. in 1989, featuring much mathematics and very heavy computation. This was checked in 2011, by D. Roy, an MSc student at Carleton University, Ottawa.)

Further results give better upper or lower bounds on N(n) for specific n. For example:

image

Some of the many things not known about N(n)

The greatest unknown: Are there any n with n not a power of a prime, but with N(n) = n – 1? The first open case is n = 12.

Indeed, for each specific n greater than 6 such that n is not a power of a prime, the exact value of N(n) is not known!

Is there a set of three MOLS of order 10? (The problem is “combinatorial explosion”. Up to permutations of rows and columns and the naming of symbols, there are just 22 Latin squares of order 6, but the corresponding number for Latin squares of order 10 is 208,904,371,354,363,006.)

SOMAs: generalising sets of MOLS

Returning to the picture of three superimposed MOLS of order n = 4:

image

Each cell contains the same number k = 3 of symbols. Each of the kn = 12 symbols occurs once in each row and once in each column, and each pair of distinct symbols occur together in a cell at most once (two symbols from the same Latin square never occur together and two symbols from different Latin squares occur together exactly once).

This motivates the definition of a SOMA(k,n), which generalises the concept of a set of k MOLS of order n. (SOMA stands for simple orthogonal multiarray.)

http://www.maths.qmul.ac.uk/~rab/slsdef.html

http://akbar.marlboro.edu/~jarhin/thedocument2.pdf

Why do this?

Mathematicians like to generalise.

Designers of experiments may need (and have needed) designs that are like sets of k MOLS of order n, but where such a set does not exist or is not known to exist.

SOMA(k,n)s have also arisen in other contexts, such as tournament design and message authentication.

SOMA(k,n)s turn out to have nice properties.

Definition Let k > 0, n > 1. A SOMA(k,n) is an n by n array, whose cells each contain exactly k elements chosen from a given set of kn symbols, such that each of the kn symbols occurs once in each row and once in each column, and each pair of distinct symbols occur together in at most one cell.

Note that a SOMA(1,n) is the same thing as a Latin square of order n and that a set of k superimposed MOLS of order n gives a SOMA(k,n)

A SOMA(k,n) is indecomposable if it is not the superimposition of two smaller n by n SOMAs.

Example N(6) = 1, but later you can see a SOMA(3,6), decomposed into a Latin square of order 6 and an indecomposable SOMA(2,6). (This particular design arose in a number of different contexts and was discovered or studied independently by a number of researchers, including R.A. Bailey, E.F. Brickell, N.C.K. Phillips and W.D. Wallis.)

image

Rosemary A. Bailey (born 1947) is a British statistician who is renowned for her work in the design of experiments and the analysis of variance and in related areas of combinatorial design, especially in association schemes. She has written books on the design of experiments, on association schemes, and on linear models in statistics. She is Professor Emerita of Statistics in the School of Mathematical Sciences at Queen Mary, University of London, England. She is currently Professor of Mathematics and Statistics in the School of Mathematics and Statistics at the University of St Andrews, Scotland.

http://en.wikipedia.org/wiki/Rosemary_A._Bailey

http://www.maths.qmul.ac.uk/~rab/

Decomposable SOMA(3,6) with symmetry group of size 120

image

Some things known about SOMA(k,n)s

Each SOMA(k,n) has a unique unrefinable decomposition into n by n arrays which are themselves SOMAs (proved by J. Arhin, who also gave an efficient algorithm to determine such a decomposition).

If n is greater than 1, then k is at most n – 1, and a SOMA(n – 1,n) must be a superimposition of n -1 MOLS (proved by R.A. Bailey).

A SOMA(n – 2,n) must be a superimposition of n – 2 MOLS (proved by J. Arhin); however, there exists an indecomposable SOMA(2,5), an indecomposable SOMA(3,6) and an indecomposable SOMA(4,7).

For n £ 6, the SOMA(k,n)s have been completely classified (done by Professor Soicher using his GRAPE and DESIGN packages in the GAP system for computational algebra and discrete mathematics).

There exist both decomposable and indecomposable SOMA(3,10)s, an indecomposable SOMA(4,10) and indecomposable SOMA(4,14)s (constructed by Professor Soicher, using assumed symmetry, algorithms, and computation using GRAPE).

Since it is known that N(n) is at least 3 when n > 10, we now know that there exists a decomposable SOMA(3,n) for all n > 3.

Later, you will see a SOMA(3,10), which is decomposed into a Latin square of order 10 and an indecomposable SOMA(2,10) and an indecomposable SOMA(4,10).

image

image

The professor would be very interested to see a SOMA(k,10) with k> 4, a SOMA(4,18) or a SOMA(4,22).

In addition, relatively little has been done to construct infinite families of SOMAs which are not superimpositions of MOLS. There is indeed scope for many new results.

Perhaps some of our A level students will be able to do this in the future.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s