SOMA Update

This page, authored by Leonard H. Soicher, reports on new SOMAs and new information on SOMAs. It supplements and updates the paper:

L.H. Soicher, On the structure and classification of SOMAs: generalizations of mutually orthogonal Latin squares, Electronic J. Combinatorics 6 (1999), #R32, 15 pp.
which we shall refer to as [SOMAs]. The paper [SOMAs] defines basic terms and concepts for SOMAs, gives results about how a SOMA may decompose, constructs and classifies certain classes of decomposable and indecomposable SOMA(3,10)s, and constructs two (indecomposable) SOMA(4,14)s.

As of 10 August 2000 this page:

Added 4 January 2001: All SOMA(k,n)s with n<6.

Added 25 November 2002: The complete classification of SOMA(k,6)s. For k=0,1,2,3,4,5 there are, respectively, exactly 1,17,2799,4,0,0 isomorphism classes (as defined below) of SOMA(k,6)s. The classification of SOMA(2,6)s was completed using an improved backtrack search program written in GAP and GRAPE. Of the isomorphism class representatives of the SOMA(2,6)s, just 199 have non-trivial automorphism group, and just one has automorphism group of size 120, the largest size of an automorphism group of a SOMA(2,6). For further analysis, here are lists of GRAPE graphs for representatives of the isormorphism classes for k=1, k=2, and k=3. (The graph Phi(A) corresponding to a SOMA A is described at the end of section 5 of [SOMAs].) The "efficient" SOMA(2,6)s from a statistical point of view are given in: R.A. Bailey and G. Royle, Optimal semi-Latin squares with side six and block size two, Proc. R. Soc. Lond. A 453 (1997), 1903-1914. The SOMA(3,6)s are illustrated and discussed further here.

Added 27 July 2012: A, D, E, and MV statistical efficiency measures of the illustrated SOMA(3,6)s and SOMA(4,10) are given.

More information will be added as it becomes available. Please email me  if:

Note A SOMA(k,n) is the same thing as a simple (n×n)/k semi-Latin square, and so readers of this web-page should also be interested in R.A. Bailey's semi-Latin squares page.

Note (added 5 September 2006): New results on SOMAs and further classifications of SOMAs can be found on John Arhin's Further SOMA Update web-page.
 

Some basic definitions

For convenience, we give some basic definitions concerning SOMAs. Also see  [SOMAs], where from section 2 onwards, a SOMA is usually regarded as a certain set of permutations.

Definition Let k and n be non-negative integers, with n>1. A SOMA, or more specifically a SOMA(k,n), is an n by n array A, whose entries are k-subsets of a kn-set X (the symbol-set), such that each element of X occurs exactly once in each row and exactly once in each column of A, and no 2-subset of X is contained in more than one entry of A.

Definition Let A and B be SOMAs. We say that B is isomorphic to A if B can be obtained from A by applying an isomorphism,  which consists of one or more of the following operations:

(Some people do not allow transposing, and would say that our concept of isomorphism is weak isomorphism.) An automorphism of A is an isomorphism from A to A. The automorphisms of A form a group, called the automorphism group of A.

Definition Let k1,...,km be positive integers adding up to k>0. A SOMA(k,n) is of type (k1,...,km) if it is the superposition of a SOMA(k1,n), a SOMA(k2,n), ..., and a SOMA(km,n). If the only type of a SOMA(k,n) A is (k), then we say that A is indecomposable; otherwise we say that A is decomposable.

(It is not difficult to see that a SOMA(k,n) is of type (1,...,1) if and only if it is the superposition of k mutually orthogonal Latin squares (MOLS) of order n, having pairwise disjoint symbol-sets.)

The SOMA(3,6)s

The SOMA(3,6)s were first classified by Phillips and Wallis (up to permutations of rows and columns, and renaming symbols) and were published  in:  N.C.K. Phillips and W.D. Wallis, All solutions to a tournament problem, Congressus Numerantium 114 (1996), 193-196. Unfortunately, due to an error in preparation, their list of SOMA(3,6)s in that paper includes one of their classes twice and misses out one class, as pointed out in: D.A. Preece and N.C.K. Phillips, Euler at the bowling green, Utilitas Mathematica 61 (2002), 129-165. I thus feel it is worthwhile to record my independent classification of SOMA(3,6)s (up to isomorphism), done in 1997. Phillips and Wallis also showed there is no SOMA(4,6), which I also determined independently (in 1997).

Up to isomorphism (including transposing), there are exactly four SOMA(3,6)s, given below. For further analysis, they are also given as a GAP  list of their corresponding  GRAPE  graphs  here. (The graph Phi(A) corresponding to a SOMA A is described at the end of section 5 of [SOMAs].) The statistical efficiency measures given are defined in R.A. Bailey and G. Royle, Proc. R. Soc. Lond. A 453 (1997), 1903-1914, where MV is called E'. These measures were computed using the DESIGN 1.6 package for GAP 4.5.

 
Decomposable SOMA(3,6) with automorphism group of order 120 and statistical efficiency measures A=697/1007≈0.692155, D≈0.698609, E≈0.597996, MV=164/249≈0.658635
1 
7 9 		 2 
11 13 		 3 
10 15 		 5 
8 17 		 4 
12 18 		 6 
14 16 
2 
12 14 		 1 
8 10 		 6 
7 18 		 4 
9 16 		 3 
11 17 		 5 
13 15 
6 
8 15 		 3 
9 18 		 2 
16 17 		 1 
12 13 		 5 
10 14 		 4 
7 11 
4 
10 17 		 5 
7 16 		 1 
11 14 		 2 
15 18 		 6 
9 13 		 3 
8 12 
3 
13 16 		 4 
14 15 		 5 
9 12 		 6 
10 11 		 2 
7 8 		 1 
17 18 
5 
11 18 		 6 
12 17 		 4 
8 13 		 3 
7 14 		 1
15 16 		 2 
9 10 
 
Decomposable SOMA(3,6) with automorphism group of order 60 and statistical efficiency measures A=697/1007≈0.692155, D≈0.698609, E≈0.597996, MV=164/249≈0.658635
1 
7 9 		 2 
11 13		 4 
12 15 		 3 
8 17 		 5 
14 18 		 6 
10 16 
3 
12 14 		 1 
8 10 		 2 
7 18 		 4 
11 16 		 6 
13 17 		 5 
9 15 
6 
11 18 		 4 
9 14 		 1 
16 17 		 5 
7 13 		 3 
10 15 		 2 
8 12 
4 
10 13 		 5 
12 17 		 6 
8 14 		 1 
15 18 		 2 
9 16 		 3 
7 11 
2 
15 17 		 3 
16 18 		 5 
10 11 		 6 
9 12 		 4 
7 8 		 1 
13 14 
5 
8 16 		 6 
7 15 		 3 
9 13 		 2 
10 14 		 1 
11 12 		 4 
17 18 
 
Indecomposable SOMA(3,6) with automorphism group of order 72 and statistical efficiency measures A=2312/3353≈0.689532, D≈0.697667, E≈0.594290, MV=136/209≈0.650718
1 
2 4 		 6 
8 10 		 3 
9 12 		 7 
14 15 		 5 
13 17 		 11 
16 18 
7 
9 11 		 1 
3 5 		 6 
14 16 		 2 
8 13 		 4 
12 18 		 10 
15 17 
5 
6 18 		 11 
12 14 		 4 
13 15 		 1 
9 17 		 2 
10 16 		 3 
7 8 
10 
13 14 		 4 
7 17 		 1 
8 18 		 5 
12 16 		 3 
11 15 		 2 
6 9 
8 
12 15 		 9 
13 16 		 2 
11 17 		 3 
10 18 		 1 
6 7 		 4 
5 14 
3 
16 17 		 2 
15 18 		 5 
7 10 		 4 
6 11 		 8 
9 14 		 1 
12 13 
 
Indecomposable SOMA(3,6) with automorphism group of order 24 and statistical efficiency measures A=54230/78459≈0.691189, D≈0.698250, E≈0.590429, MV=3190/4867≈0.655435
1 
2 4		 6 
8 10 		 5 
7 12 		 3 
13 15 		 9 
14 17 		 11 
16 18 
7 
9 11 		 1
3 5 		 2 
14 16 		 4 
6 12 		 8 
13 18 		 10 
15 17 
3 
10 18 		 9 
12 15 		 1 
11 13 		 7 
16 17 		 2 
5 6 		 4 
8 14 
8 
12 16 		 2 
11 17 		 6 
15 18 		 1 
10 14 		 3 
4 7 		 5 
9 13 
5 
14 15 		 4 
13 16 		 3 
8 17 		 2 
9 18 		 10 
11 12 		 1 
6 7 
6 
13 17 		 7 
14 18 		 4 
9 10 		 5 
8 11 		 1 
15 16 		 2 
3 12 

 

A SOMA(4,10)

When   [SOMAs]  was published, it was not known whether there existed a SOMA(k,10) with k>3. However, using the  techniques in [SOMAs], together with the  GAP  system and its GRAPE  share package,  I have since  found a SOMA(4,10), S, illustrated below. (I am grateful to Donald Preece for asking me about SOMA(k,10)s invariant under a group of order 9, which led to this discovery.)
 
Indecomposable SOMA(4,10), S, with automorphism group of order 18
1 2 
19 20 		 3 21 
22 23 		 4 5 
24 37 		 6 7 
8 25 		 9 26 
27 39 		 10 28 
29 40 		 11 12 
13 30 		 14 15 
31 38 		 16 32 
33 34 		 17 18 
35 36 
17 30 
31 32 		 14 18 
26 33 		 9 21 
25 28 		 11 16 
35 37 		 1 6 
10 24 		 12 19 
22 39 		 4 23 
36 40 		 2 3 
13 34 		 5 7 
29 38 		 8 15 
20 27 
10 11 
36 38 		 8 29 
30 34 		 7 15 
22 32 		 12 23
24 28 		 13 17 
20 37 		 1 4 
14 35 		 2 21 
33 39 		 16 25 
27 40 		 3 9
18 31 		 5 6 
19 26 
9 12 
15 29 		 4 13 
27 38 		 6 31 
34 36 		 5 10 
21 30 		 2 23 
25 35		 3 8 
26 37 		 7 14 
16 20 		 18 28 
32 39 		 17 19 
24 40 		 1 11 
22 33 
8 33 
35 40 		 2 5 
12 36 		 3 16 
19 38 		 1 27 
29 31 		 4 11 
28 34 		 18 20 
24 25 		 6 9 
22 37 		 7 10 
17 26 		 15 23 
30 39 		 13 14 
21 32 
5 25 
34 39 		 6 20 
32 40 		 2 11 
18 27 		 9 17 
33 38 		 14 19 
29 36 		 13 16 
23 31 		 15 24 
26 35 		 1 12 
21 37 		 4 8 
10 22 		 3 7 
28 30 
4 6 
16 21 		 11 24 
31 39 		 1 26 
30 40 		 13 15 
18 19 		 8 12 
32 38 		 7 27 
33 36 		 3 17 
25 29 		 5 20 
22 35 		 2 14 
28 37 		 9 10 
23 34 
7 18 
23 37 		 1 16 
17 28 		 13 29 
35 39 		 14 22 
34 40 		 3 5 
15 33 		 2 6 
30 38 		 10 19 
27 32 		 8 9 
24 36 		 11 20 
21 26 		 4 12 
25 31 
13 22 
26 28 		 10 15 
25 37 		 8 14 
17 23 		 3 20 
36 39 		 7 21 
31 40 		 5 9 
11 32 		 1 18 
34 38 		 4 19 
30 33 		 6 12 
27 35 		 2 16 
24 29 
3 14 
24 27 		 7 9 
19 35 		 10 12 
20 33 		 2 4 
26 32 		 16 18 
22 30 		 15 17 
21 34 		 5 8 
28 31 		 6 11 
23 29 		 1 13 
25 36 		 37 38 
39 40 

I can show that  S is indecomposable. The automorphism group of S is cyclic of order 18, and furthermore, up to isomorphism, S is the unique SOMA(k,10) with k>3 invariant (up to permutations of symbols) under the group generated by:

The statistical efficiency measures of S are: These measures are defined in R.A. Bailey and G. Royle, Proc. R. Soc. Lond. A 453 (1997), 1903-1914, where MV is called E', and these measures were computed using the DESIGN 1.6 package for GAP 4.5. For further analysis,  S is given as a GRAPE  graph  here. (The graph Phi(A) corresponding to a SOMA A is described at the end of section 5 of [SOMAs].)

The classification of SOMA(k,10)s invariant under a group of order 25

In [SOMAs], we were mainly interested in SOMA(k,10)s with k>2 (since the existence of more than two MOLS of order 10 is unsettled), and in section 6 we classified all SOMA(k,10)s with k>2 whose automorphism group contains a group of order 25 containing an element of order 5 fixing no row and no column. It turns out not to be difficult to classify all  SOMA(k,10)s invariant under a group of order 25, just using the techniques in [SOMAs], together with the  GAP  system and its  GRAPE  share package.

I found that, when k>1, the SOMA(k,10)s invariant under a group of order 25 are (up to isomorphism) precisely those 41 SOMA(3,10)s already classified in  section 6 of [SOMAs].

There is just one SOMA(0,10), and it is (of course) invariant under a group of order 25. I found that, up to isomorphism, there are exactly 27 SOMA(1,10)s (essentially Latin squares of order 10) invariant under a group of order 25.

Leonard Soicher's Home Page | DesignTheory.org | Design Resources on the Web

This page is authored and maintained by L.H.Soicher@qmul.ac.uk
Last revised 27 July 2012