Sequenceable Groups and Related Topics

M. A. Ollis

School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London, E1 4NS, UK.

                         M.A.Ollis@qmul.ac.uk

Submitted November 15, 2001; Accepted August 12, 2002. MR Subject Classifications: 20D60, 05B15

Abstract

In 1980, about 20 years after sequenceable groups were introduced by Gordon to construct row-complete latin squares, Keedwell published a survey of all the available results concerning sequencings. This was updated (jointly with Dénes) in 1991 and a short overview, including results about complete mappings and Rsequencings, was given in the CRC Handbook of Combinatorial Designs in 1995. In Sections 1 and 2 we give a survey of the current situation concerning sequencings. In Section 3 we consider some concepts closely related to sequenceable groups: terraces, R-sequencings, super sequenceable groups (also known as super P-groups) and the Gordon game. We also look at constructions for row-complete latin squares that do not use sequencings.

Contents

1 Introduction 2

2 Classifying Sequenceable Groups 5 2.1 Abelian Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Dihedral Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3 Binary Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4 Groups of Odd Order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3 Related Concepts 17 3.1 Terraces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2 R-sequencings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3 Super Sequenceable Groups . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.4 The Gordon Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.5 Row-Complete Latin Squares . . . . . . . . . . . . . . . . . . . . . . . . . 25

4 Index Of Notation 29

5 Acknowledgements 29

1 Introduction

A non-trivial finite group G of order n is said to be sequenceable if its elements can be arranged in a sequence (b_{1}, b_{2}, …, b_{n}) in such a way that the partial products (a_{1}, a_{2}, …, a_{n}), where a_{i} = b_{1}b_{2} ⋯ b_{i}, are distinct. The sequence (b_{1}, b_{2}, …, b_{n}) is called a sequencing for G. If (b_{1}, b_{2}, …, b_{n}) is a sequencing for G then b_{1} = e, where e is the identity of G (if b_{i} = e for some i ≠ 1 then a_{i−1} = a_{i}). The sequence (a_{1}, a_{2}, …, a_{n}) is called a basic directed terrace (for any element g ∈ G the sequence (ga_{1}, ga_{2}, …, ga_{n}) is called a directed terrace—observe that Theorem 1 still holds for this more general definition).

Note that a sequencing uniquely determines a basic directed terrace and that a basic directed terrace uniquely determines a sequencing.

Unless explicitly stated, group theoretic terms may be found in [69]. Sequencings were introduced by Gordon [40] because of a connection to complete latin squares (see Theorem 1). They have been previously surveyed by Keedwell [51, 54] and Dénes and Keedwell [32, chapter 3].

A latin square of order n is an n × n array defined on a set X with n elements such that every element of X appears once in each row and once in each column. The notation L = (l_{ij}) represents a latin square L with l_{ij} in the ith row and jth column. A latin square is said to be based on a group G if the latin square can be bordered with the elements of G to form the Cayley table of G.

An n×n latin square is said to be row complete if every pair {x, y} of distinct elements of X occurs exactly once in each order in adjacent horizontal cells. A latin square is said to be column complete if every pair {x, y} of distinct elements of X occurs exactly once in each order in adjacent vertical cells. If a latin square is both row complete and column complete then it is said to be complete.

There are a number of reasons for interest in complete latin squares. For example, in an agricultural experiment a symbol may represent a treatment to be given to a plot of land (to test its effectiveness at promoting the growth of a particular crop, say). If there are n treatments to test, a complete latin square of order n is a good design if there is a possibility that treatments will affect neighbouring plots. This is because each treatment x will occur exactly once immediately to the left, once immediately to the right, once immediately above and once immediately below any other treatment y. Williams [77] gives an example of use of a row-complete latin square in an experiment concerning pulp suspensions which are beaten in a Lampen mill (only row completeness is required—the experiment is performed sequentially and the neighbour effects are expected across time). Isaac, Dean and Ostrom [47] survey the statistical literature relating to row-complete latin squares (which they call sequentially counterbalanced latin squares).

Another application is to graph theory. If there is a row-complete latin square of order n then the complete directed graph on n vertices can be decomposed into n disjoint Hamiltonian paths (a Hamiltonian path is a path which passes through each vertex exactly once; paths are disjoint if they have no edges in common). This is done by associating each symbol in the latin square with a vertex in the graph and taking a path to traverse the vertices in the order a row lists the symbols. As we are using a latin square the paths are Hamiltonian (since each symbol occurs exactly once in each row). As the latin square is row complete each ordered pair of symbols (x, y) occurs exactly once in adjacent horizontal cells, thus no edge is repeated and the paths are disjoint. Example 1 demonstrates this for n = 4. Observe that we have not used the property that each symbol occurs once in each column. If this property is removed from the definition of a row-complete latin square then we have a Tuscan square. A Tuscan square of order n is equivalent to a decomposition of the complete graph on n vertices into n Hamiltonian paths. See [39] for more details about Tuscan squares.

Theorem 1 [40] Let G be a sequenceable group and (b_{1}, b_{2}, …, b_{n}) be a sequencing with associated basic directed terrace (a_{1}, a_{2}, …, a_{n}). Then L = (l_{ij}), where l_{ij} = a_{i}^{−1}a_{j} for 1 ≤ i, j ≤ n, is a complete latin square.

Proof: Suppose l_{ij} = l_{ik} for some 1 ≤ i, j, k ≤ n. Then a_{i}^{−1}a_{j} = a_{i}^{−1}a_{k}, giving a_{j} = a_{k}. Therefore j = k and L has no repeated entries in any row. Similarly, L has no repeated entries in any column. Therefore L is a latin square.

To show that L is row complete we need a_{i}^{−1}a_{j} = x and a_{i}^{−1}a_{j+1} = y to have a unique solution for i and j given any ordered pair (x, y) of distinct elements of G.

Inverting both sides of the first equation and post-multiplying by the second gives a_{j}^{−1}a_{j+1} = x^{−1}y, that is b_{j+1} = x^{−1}y, uniquely determining j. Now a_{i}^{−1}a_{j} = x uniquely determines i, and L is row complete.

An analogous argument shows that L is also column complete. Therefore L is a complete latin square. □

Example 1 Let G = ℤ_{4}, written additively. Then (0, 3, 2, 1) is a sequencing of G with basic directed terrace (0, 3, 1, 2). The corresponding complete latin square L is given in Figure 1. Figure 2 shows how this leads to a decomposition of the complete directed graph on 4 vertices into disjoint hamiltonian paths.

0 3 1 2 1 0 2 3 3 2 0 1 2 1 3 0 ; Figure 1: L

[figure: 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3]

Figure 2: Decomposition of the complete directed graph with 4 vertices

Sequencings with special properties have been used to solve problems concerning bipartite tournaments balanced for carry-over effects [14, 24] and some cases of the Oberwolfach problem [65]. Also, if a group is sequenceable then the Cayley table of the group has an almost transversal. This result follows because a sequencing gives rise to a near-complete mapping; see [54] for an explanation of this and other results concerning complete and near-complete mappings.

In the next section we describe the progress that has been made towards classifying sequenceable groups and in Section 3 we consider some concepts related to sequenceable groups: terraces, R-sequencings, super sequenceable groups (also known as super P-groups) and the Gordon game. We also look at constructions for row-complete latin squares that do not use sequencings.

2 Classifying Sequenceable Groups

In his paper [40], which introduced the concept of a sequencing, Gordon also completely classified the sequenceable abelian groups: see Section 2.1. He also noted that the quaternion group, Q_{8}, of order 8 and D_{6} and D_{8}, the dihedral groups of order 6 and 8 respectively, are not sequenceable. He did find, however, that D_{10} is sequenceable. In 1968 Dénes and Tőrők [33] confirmed these results and added D_{12}, D_{14}, D_{16} and the non-abelian group of order 21 (the smallest non-abelian group of odd order) to the list of known sequenceable groups. Also in 1968 Mendelsohn [57] published an independently obtained sequencing for the non-abelian group of order 21. In 1973 Keedwell [50] sequenced the non-abelian group of order 27 with exponent 9 and Wang [76] sequenced the non-abelian groups of orders 39, 55 and 57.

In 1976 more significant headway started to be made with the question of which dihedral groups are sequenceable: see Section 2.2. Also in 1976 the concept of a symmetric sequencing was introduced. This set in motion the now nearly complete classification of sequenceable binary groups: see Section 2.3. We define a binary group to be a group with a single element of order 2. This does not contradict Dickson’s [34] use of the term and fits well as a generalisation of binary polyhedral groups: see [29]. In the literature on sequencings, binary groups are usually called Λ-groups. In 1981 Keedwell was the first to give sequencings of infinitely many non-abelian groups of odd order: see Section 2.4.

Throughout this section we give the constructions for sequencings of the groups in question but usually refer the reader to the relevant papers for proofs of their correctness.

2.1 Abelian Groups

In this section we shall write abelian groups additively. In [40] Gordon proved the following theorem, which shows exactly which abelian groups are sequenceable. Recall that a binary group is defined to be a group with a single element of order 2.

Theorem 2 [40] A finite abelian group G is sequenceable if and only if G is a binary group.

Proof (⇒): Suppose (b_{1}, …, b_{n}) is a sequencing for G with associated basic directed terrace (a_{1}, …, a_{n}). Since G is abelian we have that a_{n} is the sum of the elements of G written in any order.

We first suppose that G has no elements of order 2. For each g ∈ G \ {0} we have g ≠ −g, so the non-identity elements of the sequencing will cancel in pairs. This gives a_{n} = 0, contradicting a_{1} = 0.

Now suppose that G has k elements, h_{i}, of order 2, where k > 1. These elements, along with 0, form a subgroup H of G of order k + 1 = 2^{l} for some l > 1. Then H has a basis {u_{1}, …, u_{l}} for some u_{1}, …, u_{l} ∈ H, thus each h_{i} is expressible in the form ϵ_{1}u_{1} + ⋯ + ϵ_{l}u_{l} with each ϵ_{i} ∈ {0, 1}. Each expression of this form represents one of the elements of order 2. Therefore 2^{l−1} elements of H involve the generator u_{i} for each i. Since each element u_{i} occurs an even number of times in the expression for a_{n}, and 2u_{i} = 0 for all i, we again reach the contradiction a_{n} = 0.

Note that if G has exactly one element, h, of order 2 then a_{n} = h.

(⇐): Gordon gave a direct construction of sequencings in abelian binary groups. However, later results have made possible a simpler proof; we give this simpler proof in Section 3.1. □

Example 2 Consider the cyclic group of even order, ℤ_{2n}. The following b is a sequencing and has corresponding basic directed terrace a.

b = (0, 1, 2n − 2, 3, 2n − 4, 5, …, 4, 2n − 3, 2, 2n − 1)
a = (0, 1, 2n − 1, 2, 2n − 2, 3, …, n + 2, n − 1, n + 1, n).

This sequencing was first given (implicitly) by Lucas (who gave credit to Walecki) in [56], where it was used to solve a problem concerning schoolchildren performing round-dances. Further solutions to this problem which use sequencings and related ideas are given in [20].

Combining Example 2 and Theorem 1 gives a method for constructing a complete latin square of any even order.

2.2 Dihedral Groups

Let n ≥ 3. We describe the dihedral group D_{2n}, of order 2n, as the set of ordered pairs (x, ϵ) with x ∈ ℤ_{n} and ϵ ∈ ℤ_{2} and multiplication defined by:

(x, 0)(y, δ) = (x + y, δ)
(x, 1)(y, δ) = (x − y, 1 + δ).

In 1976 Anderson [1] showed that D_{2p} is sequenceable if p is a prime with a primitive root r such that 3r ≡ −1 (mod p). Also in 1976 Friedlander [37] showed that D_{2p} is sequenceable if p is prime and p ≡ 1 (mod 4). In 1981 Hoghton and Keedwell [46] added the groups D_{2p}, where p is a prime such that p ≡ 7 (mod 8) and p has a primitive root r such that 2r ≡ −1 (mod p).

All of these results were obtained using quotient sequencings (see Section 2.4) and number theoretic arguments of varying intricacy.

In 1987 Anderson [2] used a computer search to show that all dihedral groups D_{2n} for 5 ≤ n ≤ 50 are sequenceable. In 1990 Isbell [48] produced a general argument which, when allied to Anderson’s computer search, covered all of the infinite classes mentioned above and more:

Theorem 3 [48] The dihedral groups D_{2n}, of order 2n, are sequenceable for all n, where n ≠ 3 (D_{6} is not sequenceable) and n ≠ 4k.

Construction: We split the construction into five cases and then some anomalous small examples. For the first three cases we exhibit a sequencing of the form b = (e, α, β, γ) where e is the identity, α and γ partition the remaining elements of the form (x, 0) and β consists of the elements of the form (x, 1).

Case 1; n = 4k + 1: We define α, β and γ as follows:

α = (2k − 1, 0), (2 − 2k, 0), (2k − 3, 0), (4 − 2k, 0), …, (3, 0), (−2, 0),
(1, 0), (2k, 0)
β = (0, 1), (1, 1), (2, 1), …, (2k − 1, 1), (4k, 1), (2k, 1), (2k + 1, 1), …,
(4k − 1, 1)
γ = (−2k, 0), (−1, 0), (2, 0), (−3, 0), (4, 0), …, (3 − 2k, 0), (2k − 2, 0),
(1 − 2k, 0).

Case 2; n = 8k + 7, (k ≥ 1): We produce β in the same manner as before:

β = (0, 1), (1, 1), …, (4k + 2, 1), (8k + 6, 1), (4k + 3, 1), …, (8k + 5, 1).

Now, working in ℤ_{8k+7}, consider the following sequence:

σ = −(2k + 1), (4k + 2), −(4k + 1), 4k, …, −(2k + 3), (2k + 2),
−1, −2k, (2k − 1), −(2k − 2), …, 3, −2.

Define α to be the sequence in D_{2n} with σ in the first co-ordinates and 0’s in the second, followed by (−(4k + 3), 0). Define γ to be (4k + 3, 0) followed by the sequence with −σ in the first co-ordinates and 0’s in the second. Now the sequence (e, α, β, γ) lists all elements of D_{2n} and is the required sequencing.

Case 3; n = 8k +3, (k ≠ 1, 2, 4): Again we use the list (e, α, β, γ) but here β is slightly more complicated:

β = (0, 1), (1, 1), …, (4k − 1, 1), (8k, 1), (8k + 1, 1), (8k + 2, 1), (4k, 1),
(4k + 1, 1), …, (8k − 1, 1).

Similarly to the n = 8k + 7 case we look at sequences in ℤ_{8k+3} first. Define

X_{(k)} = {x : −k ≤ x ≤ k − 1, x ≠ 1, −1}.

We construct orderings X_{k} of X_{(k)} beginning with 2 and ending with −k such that the 2k − 3 differences between consecutive elements contain exactly one of i and −i for 2 ≤ i ≤ 2k − 2. This condition is satisfied by the following three orderings:

X_{3} = (2, −2, 0, −3)
X_{5} = (2, 0, −4, 4, −3, 3, −2, −5)
X_{7} = (2, −5, 4, 0, −2, 3, −3, 5, −6, 6, −4, −7).

We now extend inductively from k to k + 3. Note that the penultimate element in each case is −(k − 3); this condition will also be preserved by the induction.

To order X_{(k+3)} list X_{k} as far as the penultimate element −(k − 3), then continue k + 2, −(k + 2), k + 1, −(k + 1), k, −k, −(k + 3). This satisfies the conditions.

Consider the sets Y_{(k)} (⊇ X_{(k)}) of integers defined as follows:

Y_{(k)} = {x : −(2k − 1) ≤ x ≤ 2k, x ≠ −1}.

We define an ordering Y_{k} of Y_{(k)} beginning with 2, ending with 1 and having differences of consecutive elements exactly one of i and −i for 1 ≤ i ≤ 4k − 2:

(\underbrace{2, …, −k}_{X_{k}}, k, −(k + 1), k + 1, …, −(2k − 1), (2k − 1), 2k, 1).

Let τ_{k} be the sequence of differences of consecutive elements in this ordering Y_{k}: then the partial sums of τ_{k} list the translate −2 + Y_{(k)} without repetition. Define α to be the sequence with τ_{k} in the first co-ordinates and 0’s in the second, followed by (−(4k + 1), 0), (4k − 1, 0), (−4k, 0). Define γ to be (4k, 0) followed by the sequence with −τ_{k} in the first co-ordinates and 0’s in the second, finishing with (4k+1, 0), (−(4k−1), 0). We now have (e, α, β, γ) listing D_{2n} without repetition and this is the required sequencing.

Case 4; n = 4k + 2, k even (k ≥ 2): For this we use the sequence (e, β, α, δ, γ) where e is the identity, α and γ partition the remaining elements (x, 0) (here α and γ are not of equal length), δ is (4k + 1, 1) and β covers the other elements (x, 1). We construct β in the same manner as in case n = 4k + 1, that is

β = (0, 1), (1, 1), (2, 1), …, (2k − 1, 1), (4k, 1), (2k, 1), (2k + 1, 1), …,
(4k − 1, 1).

Consider the following two sequences in ℤ_{4k+2}:

σ_{1} = −3, 5, −7, 9, …, 2k − 3, \underbrace{1 − 2k, 2k − 2}, −(2k − 3), 2k − 5, …, −5,
−3
σ_{2} = −2, 4, −6, 8, …, 2k − 4, \underbrace{−(2k − 2), 1, 2k − 1, −1}, −(2k − 4),
2k − 6, …, −4, 2.

Define α to be (2k + 2, 0) followed by the sequence with σ_{1} in the first co-ordinates and 0’s in the second, followed by (2k, 0), (2k + 1, 0). Define γ to be the sequence with σ_{2} as the first co-ordinates and 0’s as the second. Now α and γ cover all elements (x, 0) such that x ≠ 0, and (e, β, α, δ, γ) is a sequencing of D_{2n}.

Case 5; n = 4k + 2, k odd (k ≥ 3): We define the sequencing (e, β, α, δ, γ) as in the previous case, but we need to modify σ_{1} and σ_{2} slightly as the length of the list each side of the braces is now odd, meaning that the sign alternation causes a problem. This problem is rectified by reversing the order of the terms in the braces, that is

σ_{1} = −3, 5, −7, 9, …, −(2k − 3), \underbrace{2k − 2, 1 − 2k}, 2k − 3, −(2k − 5), …,
−5, 3
σ_{2} = −2, 4, −6, 8, …, −(2k − 4), \underbrace{−1, 2k − 1, 1, −(2k − 2)}, 2k − 4,
−(2k − 6), …, −4, 2.

The construction now goes through as before.

The anomalous cases: The sequencings given here are those due to Anderson [2], though Isbell did produce sequencings for D_{14}, D_{22}, D_{38} and D_{70} similar in style to his sequencings of the infinite classes. For brevity, we identify (i, 0) with i + 1 and (i, 1) with n + i + 1 (exactly as in [72]). Recall that D_{6} is not sequenceable.

Below, S_{2n} is a sequencing for D_{2n}.

S_{12} : (1, 11, 2, 7, 3, 9, 12, 10, 6, 5, 8, 4)
S_{14} : (1, 8, 2, 10, 7, 6, 9, 5, 11, 4, 14, 13, 12, 3)
S_{22} : (1, 8, 18, 15, 16, 5, 10, 4, 6, 13, 11, 3, 19, 17, 7, 9, 22, 2, 14, 12, 20, 21)
S_{38} : (1, 32, 15, 24, 23, 8, 38, 14, 22, 19, 37, 34, 5, 33, 36, 26, 12, 25, 13, 6, 28,
21, 7, 29, 10, 4, 20, 11, 31, 18, 31, 35, 32, 16, 17, 27, 9)
S_{70} : (1, 3, 45, 10, 22, 33, 11, 16, 32, 54, 47, 61, 43, 62, 31, 12, 53, 20, 67, 35, 8,
46, 29, 21, 7, 60, 25, 39, 34, 57, 64, 59, 6, 55, 66, 4, 38, 63, 65, 51, 70, 2, 13,
68, 28, 37, 26, 50, 30, 24, 23, 58, 5, 40, 27, 69, 15, 48, 19, 42, 56, 9, 18, 36,
17, 41, 44, 49, 14, 52)
□

In 1997 Li [55] completed the classification of sequenceable dihedral groups by sequencing D_{2n} where n ≡ 0 (mod 4), n ≠ 4. Recourse to Anderson’s computer search [2] was again needed for some small cases.

Theorem 4 [55] The dihedral groups D_{2n} are sequenceable when n = 4k, except when n = 4.

Construction: The construction varies slightly as k varies modulo 4. For each case the sequencing is ((a), (b), …, (s)) from the appropriate table amongst Tables 1, 2, 3 and 4. Note that for some small values of k some of the components may be empty.

The anomalous cases: As in the proof of Theorem 3 we identify (i, 0) with i + 1 and (i, 1) with n + i + 1. Recall that D_{8} is not sequenceable. Here we give Anderson’s sequencing S_{2n} for D_{2n} [2]:

S_{16} : (1, 13, 11, 16, 4, 14, 3, 5, 6, 15, 8, 7, 9, 12, 2, 10)
S_{24} : (1, 17, 4, 11, 2, 8, 9, 13, 10, 3, 23, 24, 22, 15, 14, 6, 20, 18, 16, 7, 21, 19, 12, 5)

We have now covered all required values of n. □

Table 1: k ≡ 0 (mod 4), k ≥ 4

Sequencing  No. of terms
(a) (0, 0)  1
(b) (0, 1), (1, 1), (2, 1), …, (2k − 2, 1)  2k − 1
(c) (4k − 2, 1)  1
(d) (2k − 1), (2k, 1), (2k + 1, 1), …, (4k − 3, 1)  2k − 1
(e) (2k, 0)  1
(f) (4k − 3, 0), (5, 0), (4k − 7, 0), (9, 0), …, (2k − 3, 0)  k − 2
(g) (2k + 2, 0)  1
(h) (2k − 1, 0), (2k + 3, 0), (2k − 5, 0), (2k + 7, 0), …, (3, 0)  k − 1
(i) (4k − 2, 0)  1
(j) (4k − 1, 1)  1
(k) (2, 0), (4k − 4, 0), (6, 0), (4k − 8, 0), …, (k − 2, 0)  k/2 − 1
(l) (1, 0)  1
(m) (3k − 4, 0), (k + 6, 0), (3k − 8, 0), (k + 10, 0), …, (2k − 2, 0)  k/2 − 2
(n) (3k, 0)  1
(o) (2k + 1, 0)  1
(p) (k + 2, 0)  1
(q) (2k − 4, 0), (2k + 6, 0), (2k − 8, 0), (2k + 10, 0), …, (3k − 2, 0) k/2 − 2
(r) (4k − 1, 0)  1
(s) (k, 0), (3k + 2, 0), (k − 4, 0), (3k + 6, 0), …, (4, 0)  k/2 − 1

Table 2: k ≡ 1 (mod 4), k ≥ 5

Sequencing  No. of terms
(a) (0, 0)  1
(b) (0, 1), (1, 1), (2, 1), …, (2k − 2, 1)  2k − 1
(c) (4k − 2, 1)  1
(d) (2k − 1), (2k, 1), (2k + 1, 1), …, (4k − 3, 1)  2k − 1
(e) (2k, 0)  1
(f) (4k − 3, 0), (5, 0), (4k − 7, 0), (9, 0), …, (2k − 1, 0)  k − 1
(g) (2k + 2, 0)  1
(h) (2k − 3, 0), (2k + 5, 0), (2k − 7, 0), (2k + 9, 0), …, (3, 0)  k − 2
(i) (4k − 2, 0)  1
(j) (4k − 1, 1)  1
(k) (2, 0), (4k − 4, 0), (6, 0), (4k − 8, 0), …, (k, 0)  (k − 3)/2
(l) (1, 0)  1
(m) (3k − 3, 0), (k + 5, 0), (3k − 7, 0), (k + 9, 0), …, (2k − 4, 0)  (k − 5)/2
(n) (3k + 1, 0)  1
(o) (2k + 1, 0)  1
(p) (k + 1, 0)  1
(q) (2k − 2, 0), (2k + 4, 0), (2k − 6, 0), (2k + 8, 0), …, (3k − 1, 0) (k − 1)/2
(r) (4k − 1, 0)  1
(s) (k − 1, 0), (3k + 3, 0), (k − 5, 0), (3k + 7, 0), …, (4, 0)  (k − 3)/2

Table 3: k ≡ 2 (mod 4), k ≥ 6

Sequencing  No. of terms
(a) (0, 0)  1
(b) (0, 1), (1, 1), (2, 1), …, (2k − 2, 1)  2k − 1
(c) (4k − 2, 1)  1
(d) (2k − 1), (2k, 1), (2k + 1, 1), …, (4k − 3, 1)  2k − 1
(e) (2k, 0)  1
(f) (4k − 3, 0), (5, 0), (4k − 7, 0), (9, 0), …, (2k − 3, 0)  k − 2
(g) (2k + 2, 0)  1
(h) (2k − 1, 0), (2k + 3, 0), (2k − 5, 0), (2k + 7, 0), …, (3, 0)  k − 1
(i) (4k − 2, 0)  1
(j) (4k − 1, 1)  1
(k) (2, 0), (4k − 4, 0), (6, 0), (4k − 8, 0), …, (k, 0)  k/2
(l) (4k − 1, 0)  1
(m) (3k − 2, 0), (k + 4, 0), (3k − 6, 0), (k + 8, 0), …, (2k − 2, 0)  k/2 − 1
(n) (3k, 0)  1
(o) (2k + 1, 0)  1
(p) (k + 2, 0)  1
(q) (2k − 4, 0), (2k + 6, 0), (2k − 8, 0), (2k + 10, 0), …, (3k − 4, 0) k/2 − 3
(r) (1, 0)  1
(s) (k − 2, 0), (3k + 4, 0), (k − 6, 0), (3k + 8, 0), …, (4, 0)  k/2 − 2

Table 4: k ≡ 3 (mod 4), k ≥ 7

Sequencing  No. of terms
(a) (0, 0)  1
(b) (0, 1), (1, 1), (2, 1), …, (2k − 2, 1)  2k − 1
(c) (4k − 2, 1)  1
(d) (2k − 1), (2k, 1), (2k + 1, 1), …, (4k − 3, 1)  2k − 1
(e) (2k, 0)  1
(f) (4k − 3, 0), (5, 0), (4k − 7, 0), (9, 0), …, (2k − 1, 0)  k − 1
(g) (2k + 2, 0)  1
(h) (2k − 3, 0), (2k + 5, 0), (2k − 7, 0), (2k + 9, 0), …, (3, 0)  k − 2
(i) (4k − 2, 0)  1
(j) (4k − 1, 1)  1
(k) (2, 0), (4k − 4, 0), (6, 0), (4k − 8, 0), …, (k − 1, 0)  (k − 1)/2
(l) (4k − 1, 0)  1
(m) (3k − 1, 0), (k + 3, 0), (3k − 5, 0), (k + 7, 0), …, (2k − 4, 0)  (k − 3)/2
(n) (3k + 1, 0)  1
(o) (2k + 1, 0)  1
(p) (k + 1, 0)  1
(q) (2k − 2, 0), (2k + 4, 0), (2k − 6, 0), (2k + 8, 0), …, (3k − 3, 0) (k − 3)/2
(r) (1, 0)  1
(s) (k − 3, 0), (3k + 5, 0), (k − 7, 0), (3k + 9, 0), …, (4, 0)  (k − 5)/2

2.3 Binary Groups

Recall that a binary group is defined to be a group with a unique element of order 2. If G is a binary group then we denote the unique subgroup of order 2 by Λ(G). The subgroup Λ(G) is necessarily normal. Let G be a binary group of order 2n with z as its unique element of order 2. A sequencing b of G is said to be symmetric if it is of the form

b = (e, b_{2}, b_{3}, …, b_{n}, z, b_{n}^{−1}, …, b_{3}^{−1}, b_{2}^{−1}).

Note that as z is the only element of order 2 we have immediately that b_{i} ≠ b_{i}^{−1} for 2 ≤ i ≤ n. Gordon’s construction (Theorem 2) for sequencing abelian groups gives symmetric sequencings, as does our new proof of that theorem in Section 3.1.

The aim of this section is to find symmetric sequencings for binary groups. We begin by considering the structure of binary groups.

The class of binary groups has arisen in several different contexts. For example, a Frobenius complement of even order (in particular, the multiplicative group of a nearfield) is a binary group [67, chapter 3.18], as is the automorphism group of a switching class of tournaments [18]. We have already noted that the binary polyhedral groups are binary groups. Coxeter[29, p. 82] posed the problem of classifying the binary groups, which is now solved (as we outline below). It is unclear who first solved this problem. Babai and Cameron [18] give a classification due to Glauberman but report that “[t]his result is known to some group theorists, but we are not aware of a proof in the literature”.

If G is a binary group, then so is any subgroup of even order; in particular, each Sylow 2-subgroup. Now, 2-groups with a unique involution are known [26, p. 132]: they are cyclic or generalised quaternion groups. Here, the generalised quaternion group Q_{2^{n}} is defined by

Q_{2^{n}} = ⟨u, v: u^{2^{n−1}} = e, v^{2} = u^{2^{n−2}}, vuv^{−1} = u^{−1}⟩.

The Sylow 2-subgroups of G/Λ(G) have the form S/Λ(S) for Sylow 2-subgroups S of G. The quotient S/Λ(S) is cyclic or dihedral according as S is cyclic or generalised quaternion.

Conversely, a cohomological argument due to Glauberman, reported in [18], shows that, if H is a finite group with cyclic or dihedral Sylow 2-subgroups, then there is a unique binary group G with G/Λ(G) ≅ H.

So the classification of binary groups reduces to that of groups with cyclic or dihedral Sylow 2-subgroups.

This classification is provided by Burnside’s Transfer Theorem [26, p. 155] and the Gorenstein–Walter Theorem [41, 25]. The result is as follows. Recall that O(G) is the largest normal subgroup of G of odd order. Let H be a finite group with Sylow 2subgroup T. Then

• if T is cyclic, then H/O(H) ≅ T;

• if T is dihedral, then H/O(H) is isomorphic to the alternating group A_{7}, or to a subgroup of PΓL(2, q) containing PSL(2, q) (where q is an odd prime power), or to T.

In particular, if G is a soluble binary group, then G/O(G)Λ(G) is isomorphic to A_{4}, S_{4}, V, or a cyclic or dihedral 2-group. (V denotes the elementary abelian 2-group of order 4).

It is not completely straightforward to describe the corresponding binary groups. Glauberman’s argument gives a description in cohomological terms.

The search for symmetric sequencings was effectively initiated by Lucas [56], although he did not use this terminology. Following on from Gordon’s construction, further results have been obtained by Bailey and Praeger [22], Nilrat and Praeger [62] and Anderson, working alone and with Ihrig and Leonard. Symmetric sequencings with special properties have been used to solve some cases of the Oberwolfach problem [65]. Theorem 5 is an early result which the rest of the work can be seen as generalising:

Theorem 5 [1] If G is a sequenceable group of odd order n then G × C_{2} has a symmetric sequencing.

Proof: Let z be the non-identity element of C_{2}. Observe first that G × C_{2} is a binary group with (e, z) as its unique element of order two. Let (e, d_{2}, …, d_{n}) be a sequencing of G. Since G is of odd order, every non-identity element is distinct from its inverse. Partition G \ {e} into (n − 1)/2 two-element subsets of the form {g, g^{−1}} and choose an element from each subset.

We now define a symmetric sequencing b, where b = (b_{1}, b_{2}, …, b_{2n}), for G × C_{2}:

(b_{1}, b_{2}, …, b_{n}) = ((e, e), (d_{2}, ϵ_{2}), …, (d_{n}, ϵ_{n}))

where

ϵ_{i} = \{ \begin{matrix}z & if d_{i} is a chosen element \\ e & otherwise, \end{matrix}
b_{n+1} = (e, z)

and

(b_{n+2}, b_{n+3}, …, b_{2n}) = ((d_{n}^{−1}, ϵ_{n}), (d_{n−1}^{−1}, ϵ_{n−1}) …, (d_{2}^{−1}, ϵ_{2})).

Now b lists G × C_{2} without repetition and does so symmetrically (since (b_{i}, ϵ_{i})^{−1} = (b_{i}^{−1}, ϵ_{i})).

Also, all of the elements in G × C_{2} are in the sequence of partial products. The partial products move through the basic directed terrace for G, with associated e’s and z’s in the second co-ordinate. Then, from the (n + 1)th position, they move back through G’s basic directed terrace with the e’s and z’s switched, finishing on (e, z). □

A key concept on which the work relies is that of a 2-sequencing (or equivalently a basic terrace), introduced by Bailey [19]. A 2-sequencing of H, a group of order n, is a sequence of elements (e, d_{2}, d_{3}, …, d_{n}), not necessarily distinct, such that:

• the associated partial products e, ed_{2}, ed_{2}d_{3}, …, ed_{2} ⋯ d_{n} are all distinct; this sequence is called a basic terrace, • if h ∈ H and h ≠ h^{−1} then

|{i : 2 ≤ i ≤ n, d_{i} ∈ {h, h^{−1}}}| = 2,

• if h ∈ H and h = h^{−1} then

|{i : 1 ≤ i ≤ n, d_{i} = h}| = 1.

Note that a sequencing for H is also a 2-sequencing for H.

The following generalisation of Theorem 5 is pivotal:

Theorem 6 [3] Let G be a binary group of order 2n. Then G has a symmetric sequencing if and only if G/Λ(G) has a 2-sequencing.

Proof: Let π : G → G/Λ(G) be the natural projection. Then it is straightforward to check that if (e, b_{2}, …, b_{n}, z, b_{n}^{−1}, …, b_{2}^{−1}) is a symmetric sequencing of G then (π(e), π(b_{2}), …, π(b_{n})) is a 2-sequencing of G/Λ(G).

Let z be the element of order 2 in G. If y ∈ G/Λ(G) then y = {x, xz} for some x ∈ G. Suppose we are given a 2-sequencing of G/Λ(G). Lift this back to a sequence in G as follows:

(i): If y ∈ G/Λ(G), y ≠ y^{−1} and y (equivalently y^{−1}) occurs twice in our 2-sequencing, the two occurrences of y = {x, xz} can be lifted back to x and xz (in either order).

(ii): If y ∈ G/Λ(G), y ≠ y^{−1} and both y and y^{−1} occur once in our 2-sequencing, say y = {x, xz} and y^{−1} = {x^{−1}, x^{−1}z}, we can either lift y to x and y^{−1} to x^{−1}z or y to xz and y^{−1} to x^{−1}.

(iii): If y ∈ G/Λ(G), y = y^{−1} and y ≠ {e, z} then y must occur once in our 2sequencing. Now y = {x, x^{−1}} and y may be lifted back to either x or x^{−1}.

(iv): If y = {e, z} ∈ G/Λ(G) then y must be lifted to e.

This process clearly gives a sequence of the form (e, b_{2}, …, b_{n}) in G where b_{i} ≠ b_{j} and b_{i}^{−1} ≠ b_{j} for i, j ≤ n, where i ≠ j. Extend this to a sequence of all the elements of G: (e, b_{2}, …, b_{n}, z, b_{n}^{−1}, …, b_{2}^{−1}).

We claim that this is a symmetric sequencing of G.

The partial products are (e, a_{2}, …, a_{n}, a_{n}z, a_{n−1}z, …, a_{2}z): we therefore need that {e, a_{2}, …, a_{n}} is a transversal of {{w, wz} : w ∈ G}. This follows because each a_{i} is either w_{i} or w_{i}z for some w_{i} ∈ G and the elements {e, z}, {w_{2}, w_{2}z}, …, {w_{n}, w_{n}z} of G/Λ(G) are distinct as we started from a 2-sequencing. The sequence is clearly symmetric, so the claim is verified and the proof is complete. □

Note that the construction of Theorem 6 gives 2^{(n+k−1)/2} different symmetric sequencings of G for each 2-sequencing of G/Λ(G), where k is the number of elements of order 2 in G/Λ(G).

Anderson and Ihrig extend this further to show:

Theorem 7 [11] If G is a binary group and G/O(G)Λ(G) has a 2-sequencing then G has a symmetric sequencing.

□

The groups A_{4} and S_{4} have sequencings [2] and hence have 2-sequencings. We have also seen that cyclic and dihedral 2-groups have sequencings (Example 2 and Theorem 4). Prior to the proof of Theorem 4, Anderson had shown that all dihedral groups have 2-sequencings [3, 5, 6].

The case G/O(G)Λ(G) ≅ V only arises when we consider binary groups with Q_{8} as their Sylow 2-subgroup. The group Q_{8} itself is not sequenceable, but Anderson and Leonard [13] show that the groups Q_{8} × B, where B is a non-trivial abelian group of odd order, have symmetric sequencings. These groups are Hamiltonian groups; that is, each is a non-abelian group every subgroup of which is normal. In fact, they are the only Hamiltonian binary groups. Anderson and Ihrig [11] show that all soluble binary groups G with G/O(G)Λ(G) ≅ V, where G ≠ Q_{8}, have symmetric sequencings. Theorem 7 now gives:

Theorem 8 [11] All finite soluble binary groups, except Q_{8}, have symmetric sequencings.

□

In [12] Anderson and Ihrig consider the structure of insoluble binary groups. They show that to find sequencings of all insoluble binary groups it is sufficient to find 2sequencings of A_{7}, PSL(2, q) and PGL(2, q) for q an odd prime power greater than 3. They also show that there is no redundancy here; finding a 2-sequencing of each of these groups gives symmetric sequencings for an infinite set of insoluble binary groups and these sets are disjoint. The only result in this direction to date is the sequencing of PSL(2, 5) ≅ A_{5} [4], showing that such infinite sets of sequenceable insoluble binary groups do exist.

2.4 Groups of Odd Order

Keedwell [52] and Wang [74] have sequenced some non-abelian groups of odd order which have a cyclic normal subgroup with prime index. We do not give the full constructions here, merely introduce the two crucial concepts.

The first concept is the quotient sequencing (this concept was introduced by Friedlander [37]). Let G be a group of order pq with normal subgroup H of order q. A sequence Q of length pq containing elements of G/H is said to be a quotient sequencing of G/H if each element of G/H occurs q times in both Q and the partial product sequence (the basic quotient directed terrace) of Q. Note that the natural map G → G/H maps a sequencing of G to a quotient sequencing of G/H; however, most quotient sequencings cannot be lifted to a sequencing of the parent group.

Suppose, with the above notation, that G/H ≅ C_{p} for some odd prime p, where C_{p} = ⟨u : u^{p} = e⟩. Let β be a primitive root of p such that β/(β − 1) is also a primitive root of p (Wang [74] reports that such a β exists, using the results of [28]). Wang [74] gives a quotient sequencing for G/H. Here we just give the associated basic quotient directed terrace as that may be expressed more simply:

e, e, …, e, x (q elements)

followed by q − 2 copies of the sequence

x^{β^{p−2}}, x^{β^{p−3}}, …, x (p − 1 elements)

and finishing with

x^{β^{p−2}}, x^{β^{p−3}}, …, x^{β}, x^{β}, x^{β^{2}/(β−1)}, x^{β^{3}/(β−1)^{2}}, …, x^{β−1}, e (2(p − 1) elements).

Wang observes that this is a generalisation of the quotient directed terrace used by Keedwell [52].

The second important concept is the R-sequencing. An R-sequencing (sometimes called a near-sequencing) of a group G is a sequence (e, b_{2}, b_{3}, …, b_{n}) of all the elements of G such that the partial products (e, eb_{2}, eb_{2}b_{3}, …, eb_{2}b_{3} ⋯ b_{n−1}) are distinct and eb_{2}b_{3} ⋯ b_{n} = e. Keedwell and Wang both consider groups G with a normal cyclic subgroup of order q and index a prime p. The method they use is to find an R-sequencing of C_{q} and use the first q − 1 elements of this for the first q − 1 elements of the sequencing, filling the rest of the sequencing in a way that is also compatible with the above quotient directed terrace.

Suppose that p and q are odd primes, with p < q. Then there is a non-abelian group of order pq if and only if q = 2ph + 1 for some positive integer h. This group has a cyclic normal subgroup of order q. Keedwell [52] found sequencings of groups of this type whenever 2 is a primitive root of p. Wang showed that it is sufficient to to find an R-sequencing of C_{q} in which x^{r−r^{1−β}} and x^{r−r^{1−β}−1} are adjacent for some r with r^{p} ≡ 1 (mod q) and r ≢ 1 (mod q). In [73] Wang gives some examples of such R-sequencings where 2 is not a primitive root of p.

Wang [74] also finds a sequencing which is compatible with the above quotient directed terrace for the unique non-abelian group of order p^{m} that has a cyclic normal subgroup of index p, where p is an odd prime and m > 3.

Let G be a group of odd order n. A sequencing (e, b_{2}, …, b_{n}), is said to be a startertranslate sequencing (Anderson [8] abbreviates this to st-sequencing) if both of the sets {b_{2}, b_{4}, …, b_{n−1}} and {b_{3}, b_{5}, …, b_{n}} contain precisely one of g and g^{−1} for each g ∈ G\{e}. Anderson [8] shows that if G and H are groups with st-sequencings then G × H also has an st-sequencing. He also shows that Keedwell’s sequencing of the non-abelian group of order pq is starter-translate whenever both p and q are congruent to 3 modulo 4. This considerably extends the set of odd integers n for which a sequenceable group of order n is known to exist.

2.5 Summary

In addition to the results given already in this chapter, Anderson [2, 4] has used a hillclimbing algorithm to sequence all non-abelian groups of order n, where 10 ≤ n ≤ 32, and A_{5} and S_{5}, the alternating and symmetric groups on 5 symbols. Therefore the following groups are known to be sequenceable.

• Dihedral groups of order at least 10

• Soluble (including abelian) binary groups, except Q_{8}

• Insoluble binary groups G with A_{5} as their only non-abelian composition factor

• Some groups of order pq where p and q are odd primes

• Direct products of some of the groups of the previous type if both p and q are congruent to 3 modulo 4

• At least one of the non-abelian groups of order p^{m}, for p an odd prime and m ≥ 3

• Non-abelian groups of order n, where 10 ≤ n ≤ 32

• A_{5} and S_{5}

The only groups known to be non-sequenceable are abelian groups which do not have a unique element of order 2 and the non-abelian groups D_{6}, D_{8} and Q_{8}.

Conjecture 1 (Keedwell) D_{6}, D_{8} and Q_{8} are the only non-abelian non-sequenceable groups.

A milder conjecture is

Conjecture 2 (Anderson) Q_{8} is the only binary group which does not have a symmetric sequencing.

3 Related Concepts

In this section we look at some concepts related to sequencings: terraces, R-sequencings, super sequenceable groups (also known as super P-groups) and the Gordon Game. We also look at an alternative method for constructing row-complete latin squares.

3.1 Terraces

As we noted in Section 2.3, terraces and 2-sequencings are equivalent. We say that a group that has a terrace is terraced. Terraces were introduced by Bailey [19] to prove Theorem 9—an analogue of Theorem 1 for quasi-complete latin squares. An n × n latin square is said to be row quasi-complete if each distinct pair of symbols {x, y} occurs in adjacent horizontal cells twice (in either order). It is said to be column quasi-complete if each pair of distinct symbols {x, y} occurs in adjacent vertical cells twice (in either order).

A latin square that is both row quasi-complete and column quasi-complete is said to be quasi-complete.

Row-quasi-complete latin squares were used by Williams [77] for designing experiments where carry-over effects are thought to be present. He uses them in pairs, one containing the reverses of the other’s rows, giving a design in which each pair of treatments occurs twice in each order as row-neighbours. He gives an example of such a design being used in practice to study the effect of diet on the milk yield of cows. An application where quasi-completeness is the natural requirement, rather than being used when completeness is unavailable, is given in [21]. The experiment described concerns five methods of controlling insects on spring beans. A quasi-complete latin square of order 5 is advocated because it was felt that there may be neighbour effects between adjacent plots from insects overspilling from a plot containing spring beans with a treatment that does little (or nothing) to repel them. It is pointed out that row neighbours should be kept distinct from column neighbours as plots in this type of experiment are rarely square—in this instance they measured 1.2m × 1m. A similar experiment is described in [70]. However, this experiment has six treatments and their quasi-complete latin square is also complete.

Quasi-complete latin squares have also been considered by Freeman [35, 36] and Campbell and Geller [27].

Theorem 9 [19] Let G be a terraced group with terrace (a_{1}, a_{2}, …, a_{n}). Then the square (l_{ij}) = (a_{i}^{−1}a_{j}), where 1 ≤ i, j ≤ n, is a quasi-complete latin square.

Proof: Similar to the proof of Theorem 1. □

We would therefore like to know which groups are terraced. The following result is originally due to Williams [77] and has been rediscovered, in various guises, by many authors.

Theorem 10 [77] For all positive integers n, the cyclic group ℤ_{n} is terraced.

Proof: A terrace for ℤ_{n} is (0, 1, n − 1, 2, n − 2, …), having (0, 1, n − 2, 3, n − 4, …) as its 2-sequencing. □

Note that when n is even the terrace given in Theorem 10 is directed (and is the one given in Example 2). In fact there are many terraces known for ℤ_{n}: see [7, 15, 16, 63, 65, 71, 77] for examples.

The following two results are due to Bailey.

Theorem 11 [19] G = ℤ_{2}^{n} is not 2-sequenceable for n > 1.

Proof: For each g ∈ G, we have g = −g. Thus G is 2-sequenceable if and only if G is sequenceable, but G is not sequenceable, by Theorem 2. □

Theorem 12 [19] Abelian groups of odd order are terraced.

Proof: Let ℤ_{n_{1}} × ⋯ × ℤ_{n_{l}} be an abelian group of odd order. We use induction on the number of summands. By Theorem 10, ℤ_{n_{1}} is terraced.

Suppose that ℤ_{n_{1}} × ⋯ × ℤ_{n_{k−1}} is terraced with terrace a = (a_{1}, a_{2}, …, a_{m}) and let c = (c_{1}, c_{2}, …, c_{n_{k}}) be the Williams terrace for ℤ_{n_{k}}. For i > 0 let

α^{(0)} = (a_{1}, 0), (a_{2}, 0), …, (a_{m}, 0)
α^{(i)} = (a_{m}, c_{i}), (a_{m−1}, c_{i+1}), (a_{m−2}, c_{i}), (a_{m−3}, c_{i+1}), …, (a_{1}, c_{i}) if i is odd
α^{(i)} = (a_{1}, c_{i}), (a_{2}, c_{i−1}), (a_{3}, c_{i}), (a_{4}, c_{i−1}), …, (a_{m}, c_{i})  if i is even

We claim that (α^{(0)}, α^{(1)}, …, α^{(n_{k})}) is a terrace for ℤ_{n_{1}} × ⋯ × ℤ_{n_{k}}:

An allowable set of differences with zeros in the second co-ordinate occurs within the differences produced by α^{(0)} as a is a terrace. An allowable set of differences with zeros in the first co-ordinate occurs within the differences produced by the juxtapositions of α^{(i)} and α^{(i+1)} as c is a terrace. These are the only occurrences of differences with zero in either co-ordinate.

Let x be a non-zero element of ℤ_{n_{k}} such that c_{i+1} − c_{i} = x for some odd i (this covers exactly one of x and −x for each x ∈ ℤ_{n_{k}}). Then x or −x occurs in the second co-ordinate of the differences in α^{(i)} and α^{(i+1)} (and nowhere else). As a is a terrace, for each non-zero y, where y ∈ ℤ_{n_{1}} × ⋯ × ℤ_{n_{k−1}}, we get one of the following combinations of differences among the differences produced by α^{(i)} and α^{(i+1)}:

• two occurrences each of (y, x) and (−y, x) (and no occurrences of (y, −x) or (−y, −x))

• one occurrence each of (y, x), (−y, x), (y, −x) and (−y, −x)

• two occurrences each of (y, −x) and (−y, −x) (and no occurrences of (y, x) or (−y, x)).

None of these combinations contravene the definition of a terrace, so (α^{(0)}, α^{(1)}, …, α^{(n_{k})}) is a terrace as claimed. The result now follows by induction on k. □

We can now complete the proof of Theorem 2; that is, abelian binary groups have directed terraces:

Proof: Let A be an abelian binary group, say A = ℤ_{2^{m}} × B where m > 1 and B is an abelian group of odd order. Then A/ℤ_{2} ≅ ℤ_{2^{m−1}} × B and Theorem 6 says that if A/ℤ_{2} is terraced then A has a directed terrace. The preceding theorem gives a terrace for B, so the result now follows by induction on m. □

The next result collects together most of the known terraced groups; it is due predominantly to independent work by Anderson and Bailey.

Theorem 13 The following groups are terraced:

(i) all sequenceable groups, (ii) K × C_{n} where K is terraced and n is odd, (iii) G × C_{2} where G is a soluble binary group, G ≠ C_{2}, (iv) all groups of odd order,

(v) all groups of order up to 86 (except possibly 64) not ruled out by Theorem 11.

Proof: (i): Follows immediately from the definitions.

(ii): See [19].

(iii): The case when G is abelian was proved in [13], the more general result is in [64]. (iv): See [10] (v): See [9]. □

In Section 2.4 we defined starter-translate sequencings. This definition applies equally well to 2-sequencings. A starter-translate 2-sequencing (st-2-sequencing) of a group of odd order is a 2-sequencing (b_{1}, b_{2}, …, b_{n}) with the property that both {b_{2}, b_{4}, …, b_{n−1}} and {b_{3}, b_{5}, …, b_{n}} contain precisely one of g and g^{−1} for each g ∈ G. Note that with a stsequencing we always have g in one set and g^{−1} in the other, whereas here it is possible for both sets to contain g and neither to contain g^{−1}. Anderson and Ihrig [10] show that all groups of odd order have st-2-sequencings and use this [11] to generalise Theorem 13(ii), showing that a group G is terraced whenever G has a normal subgroup N of odd order and G/N is terraced.

Conjecture 3 (Bailey) All finite groups, except the elementary abelian 2-groups of order at least 4, are terraced.

In 1988 Morgan [58] generalised the concept of a terrace as follows. Let G be a group of order n and let a be a list (a_{1}, a_{2}, …, a_{p}) of elements of G (repeats and omissions of elements permitted) where p = 1 + m(n − 1)/2 for some integer m. Note that if n is even then m must also be even. For such an a let b = (a_{1}^{−1}a_{2}, a_{2}^{−1}a_{3}, …, a_{p−1}^{−1}a_{p}). We say that a is an m-terrace of G if each element of G occurs in a either ⌊p/n⌋ or ⌊p/n⌋ + 1 times (⌊k⌋ denotes the least integer greater than k − 1) and if b consists of

• m/2 occurrences of each non-identity element g which satisfies g = g^{−1}

• m total occurrences from the pair {g, g^{−1}} for each element g which does not satisfy g = g^{−1}.

Observe that a 2-terrace is a terrace as previously defined.

The purpose of this generalisation is to aid in the construction of polycross designs. A polycross design is a rectangular array, or set of rectangular arrays, used for plant-breeding experiments where in each cell there is a particular genotype and the genotypes are left to cross-fertilize. The purpose of most polycross designs is to arrange the genotypes so that the different pairs of genotypes have equal chances of cross-fertilizing. See [78] for examples of polycross experiments where attempts to balance neighbours have been made. If we are considering only row and column neighbours then complete and quasicomplete latin squares are obviously good polycross designs; however, in general diagonal neighbours will be of importance and thus something more is needed.

A polycross design is said to be a completely balanced non-directional polycross design if each unordered pair of distinct symbols occur as neighbours a constant number of times in rows, a constant number of times in columns and a constant number of times in the diagonals. An array D = (d_{ij}) of elements of a group is said to be a non-directional balanced neighbour difference array if, among all the neighbour differences d_{ij}d_{i′j′}^{−1} and d_{i′j′}d_{ij}^{−1} (i′ ∈ {i − 1, i, i + 1}, j′ ∈ {j − 1, j, j + 1} with the obvious restrictions at the borders) over all i, j, each non-identity element occurs a constant number of times as a column difference, a constant number of times as a row difference and a constant number of times as a diagonal difference.

Let a be an m_{1}-terrace (a_{1}, a_{2}, …, a_{p}) and let c be an m_{2}-terrace (c_{1}, c_{2}, …, c_{q}). Define R(a, c) to be the p × q array with a_{i}c_{j} as the (i, j)-entry and let gR(a, c) be the array obtained by (left) multiplying each element of R(a, c) by g.

Theorem 14 [58] Take an abelian group G of order n with m_{1}-terrace a = (a_{1}, a_{2}, …, a_{p}) and m_{2}-terrace c = (c_{1}, c_{2}, …, c_{q}). Then the set of arrays {gR(a, c) : g ∈ G} is a completely balanced non-directional polycross design with each unordered pair of distinct symbols occurring as neighbours m_{2}p times in rows, m_{1}q times in columns and m_{1}m_{2}(n−2) times in the diagonals. Also, pairs of the same symbol occur together m_{1}m_{2}(n−1)/2 times as diagonal neighbours.

Proof: Our first aim is to show that R(a, c) is a balanced difference array. That we get m_{2}p occurrences of each difference in the rows and m_{1}q occurrences of each difference in the columns follows immediately from the definition of an m-terrace. The diagonal differences are:

a_{i}a_{i+1}^{−1}c_{j}c_{j+1}^{−1}, a_{1}a_{i+1}^{−1}c_{j}^{−1}c_{j+1}, a_{i}^{−1}a_{i+1}c_{j}c_{j+1}^{−1}, a_{i}^{−1}a_{i+1}c_{j}^{−1}c_{j+1}

for 1 ≤ i ≤ p − 1 and 1 ≤ j ≤ p − 1. Note that we have used the fact that G is abelian here. Now, a_{i}a_{i+1}^{−1} and a_{i}^{−1}a_{i+1} comprise each non-identity element of the group m_{1} times between them and c_{j}c_{j+1}^{−1} and c_{j}^{−1}c_{j+1} comprise each non-identity element of the group m_{2} times between them. Thus the four diagonal differences comprise the values of the multiplication table of the group, with the row and column for the identity omitted, m_{1}m_{2} times. Such a table has n−2 occurrences of each non-identity element and n − 1 occurrences of the identity. Thus R(a, c) is a non-directional balanced neighbour difference array.

It follows that in {gR(a, c) : g ∈ G} each pair of distinct symbols occurs m_{2}p times as row neighbours, m_{1}q times as column symbols and m_{1}m_{2}(n − 2) times as diagonal neighbours. Also each pair of identical symbols occurs m_{1}m_{2}(n − 1)/2 times as diagonal neighbours.

Therefore {gR(a, c) : g ∈ G} is a completely balanced non-directional polycross design. □

By analogy with Theorems 1 and 9, it would seem more natural in the above theorem to use R(a^{−1}, c), where a^{−1} = (a_{1}^{−1}, a_{2}^{−1}, …, a_{p}^{−1}). However, we require G to be abelian and in an abelian group a^{−1} is an m-terrace if and only if a is an m-terrace. Note that if a and c are 2-terraces then {gR(a, c) : g ∈ G} is a set of n quasi-complete latin squares of order n. If either a or b is not a 2-terrace then the arrays in the design will not be latin squares.

Figure 3: A completely balanced non-directional polycross design

0 1 3  1 2 4  2 3 0  3 4 1  4 0 2
1 2 4  2 3 0  3 4 1  4 0 2  0 1 3
3 4 1  4 0 2  0 1 3  1 2 4  2 3 0
2 3 0  3 4 1  4 0 2  0 1 3  1 2 4
4 0 2  0 1 3  1 2 4  2 3 0  3 4 1
1 2 4  2 3 0  3 4 1  4 0 2  0 1 3
0 1 3  1 2 4  2 3 0  3 4 1  4 0 2

Example 3 Let G = ℤ_{5}. Then (0, 1, 3, 2, 4, 1, 0) is a 3-terrace and (0, 1, 3) is a 1-terrace. This gives the completely balanced non-directional polycross design in Figure 3.

Theorem 15 [58] The cyclic groups ℤ_{n} have 2- and 4-terraces when n is even and 1-, 2-, 3- and 4-terraces when n is odd.

Proof: Suppose n is even, n = 2k say. Then

(0, 1, 2k − 1, 2, 2k − 2, …, k − 1, k + 1, k)

is a 2-terrace for ℤ_{n} (see Theorem 10) and

(k, k + 1, k − 1, …, 2k − 1, 1, 0, 1, 2k − 1, …, k − 1, k + 1, k)

is a 4-terrace.

Now suppose that n is odd, n = 2k + 1 say. Then

(0, 1, 2k, 2, 2k − 1, …, k, k + 1)

is a 2-terrace (see Theorem 10) and

(k + 1, k, …, 2k, 1, 0, 1, 2k, …, k, k + 1)

is 4-terrace. Also, the first k +1 terms of the 2-terrace form a 1-terrace and the first 3k+1 terms of the 4-terrace form a 3-terrace. □

This result is normally ample to cover any practical experiment. However, the process can be extended to larger values of m but care must be taken to ensure the elements appear an allowable number of times in the m-terrace.

Morgan [58, 59, 60, 61] extends this work in several directions, the main two being to consider directional balance and to condense the arrays of Theorem 14 into one array whilst preserving the balance properties.

3.2 R-sequencings

A pair of latin squares (l_{ij}) and (l′_{ij}) are said to be orthogonal if every ordered pair of symbols occurs exactly once among the n^{2} pairs (l_{ij}, l′_{ij}). It is shown in [66] that the existence of a group of order n having an R-sequencing (see page 16 for the definition) is a sufficient condition for there to exist a pair of orthogonal latin squares of order n. (More specifically, it is shown that having an R-sequencing is a sufficient condition for a group to have a complete mapping and having a complete mapping in a group of order n is sufficient to produce a pair of orthogonal latin squares of order n. See [54] for a summary of these and related topics.)

The study of orthogonal latin squares was originally motivated by a problem of Euler, set in 1779: “Thirty-six officers of six different ranks and taken from six different regiments, one of each rank in each regiment, are to be arranged, if possible, in a solid square formation of six by six, so that each row and each column contains one and only one officer of each rank and one and only one officer from each regiment”. The solution of this problem is equivalent to the construction of a pair of orthogonal latin squares of order 6. In 1782 Euler conjectured that no such pairs of latin squares exist for orders n = 4k + 2; this was proved true for n = 6 by Tarry in 1900 and false for all n > 6 by Bose, Shrikhande and Parker in 1960. It is easily seen to be true for n = 2. See [31, chapter 5] for a thorough account of orthogonal latin squares and the history of Euler’s conjecture.

Observe that for abelian groups the properties of being sequenceable and R-sequenceable are mutually exclusive as the final element of the partial product sequence is invariant. Friedlander, Gordon and Miller [38] have shown:

Theorem 16 The following types of abelian group are R-sequenceable:

(i) C_{n}, where n is odd, (ii) Abelian groups of odd order with (possibly trivial) cyclic Sylow 3-subgroups, (iii) C_{p}^{n} where p is prime and n ≥ 2, (iv) C_{2} × C_{4n}, where n ≥ 1,

(v) Abelian groups with Sylow 2-subgroups C_{2}^{n}, where n = 2 or n ≥ 4, (vi) Abelian groups with Sylow 2-subgroups C_{2} × C_{2^{n}}, where n is odd.

□

It is reported in [32, Chapter 3] that Ringel claims to have shown that C_{2} × C_{6n+2} is R-sequenceable for n ≥ 1.

Since then Headley [42] has extended these results to include all abelian groups whose Sylow 2-subgroups are neither cyclic nor C_{2} × C_{4} nor C_{2} × C_{2} × C_{2}.

The following theorem gives the position for non-abelian groups. The dicyclic group Q_{4n} is defined by

Q_{4n} = ⟨a, b : a^{2n} = e, b^{2} = a^{n}, ab = ba^{−1}⟩.

If n is a power of 2 then Q_{4n} is a generalised quaternion group.

Theorem 17 (i) The dihedral group D_{2n} of order 2n is R-sequenceable if and only if n is even. (ii) The dicyclic group Q_{4n} is R-sequenceable if and only if n is an even integer greater than 2. (iii) The non-abelian groups of order pq, where p and q are odd primes, are R-sequenceable. (iv) The two non-abelian groups of order 27 are R-sequenceable.

Proof: (i): See [53].

(ii): See [75].

(iii): The case when p < q and p has 2 as a primitive root was covered by Keedwell in [53]. Wang and Leonard subsequently removed the primitive root condition in [75].

(iv): See [23]. □

3.3 Super Sequenceable Groups

Let G be a group of order n with derived group G′. As the elements of G commute modulo G′, the products of all the elements of G lie in the same coset hG′ of G′, regardless of the order of multiplication. It is known [30, 68] that each element of this special coset may be expressed as the product of all of the group elements in some order (groups with this property were originally known as P-groups, but this name is now redundant).

In 1983 Keedwell [53] defined super P-groups, which we now call super sequenceable groups. A super sequenceable group is a finite group G in which each element g of the special coset is either

• the last element of some basic directed terrace, or

• the last element of the partial product sequence associated with some R-sequencing.

The second condition is used only when g = e; we have g = e only when hG′ = G′. Keedwell [53] proved the following two theorems:

Theorem 18 Let G be an abelian group. Then G is a super sequenceable group if and only if G is sequenceable or R-sequenceable.

Proof: Observe that G′ = {0}, so the relevant coset of G′ has just one element. This element is the identity if G is not a binary group, and is the unique element of order 2 if G is a binary group (see Theorem 2). Thus, if G is not a binary group then G is a super sequenceable group if and only if G is R-sequenceable. If G is a binary group then G is a super sequenceable group if and only if G is sequenceable. □

Theorem 19 The following groups are super sequenceable groups:

(i) Dihedral groups D_{2n} where n ≥ 5 is odd. (ii) Dihedral groups D_{2n} where n is twice an odd prime. (iii) Groups of order pq where p and q are primes, p < q and 2 is a primitive root of p.

□

Also, Bedford [23] has shown that both of the non-abelian groups of order 27 are super sequenceable groups.

3.4 The Gordon Game

In 1992 Isbell [49] introduced the idea of ‘competitive’ sequencing: the Gordon game Γ(G) for a given finite group G is played as follows.

A counter is placed on the identity, e, of G. White and Black then take turns (White first) to move the counter around the group subject to the condition that the (n + 1)st move (to x_{n+1}) must satisfy

x_{n+1} ∉ {e, x_{1}, …, x_{n}}

and

x_{n}^{−1}x_{n+1} ∉ {x_{1}, x_{1}^{−1}x_{2}, …, x_{n−1}^{−1}x_{n}}.

That is, if a game contained as many moves as the group had non-identity elements then the sequence (e, x_{1}, …, x_{|G|−1}) would be a directed terrace for G. The first player unable to make a move loses.

Isbell investigated the Gordon game for groups of small order, finding the following results. Here W and B denote forced wins for White and Black respectively.

\begin{matrix}C_{2} : & W & C_{3} : & W & C_{4} : & W \\ C_{2} × C_{2} : & B & C_{5} : & W & C_{6} : & B \\ D_{6} : & W & C_{7} : & B & C_{8} : & B \\ C_{2} × C_{4} : & W & C_{2} × C_{2} × C_{2} : & B & D_{8} : & B \\ Q_{8} : & W & C_{9} : & B & C_{3} × C_{3} : & B \\ C_{10} : & W & C_{11} : & B & C_{13} : & B \end{matrix}

Isbell tentatively suggests

Conjecture 4 Black wins Γ(C_{p}) for primes p > 5.

The reasoning behind this conjecture is (as Isbell freely admits) shaky. Fix h ∈ C_{p}\{e}. White’s first move is irrelevant as for each g ∈ C_{p} \ {e} there is an automorphism which maps g to h. However, this automorphism is unique and the argument for Black winning is that “in the unique game which Black faces after White’s first move in Γ(C_{p}) the p − 3 possible opening moves are all different (i.e. inequivalent by automorphisms). For large p, it is very unlikely that all are losing moves”.

As far as the author is aware, no further work has been done on this problem.

3.5 Row-Complete Latin Squares

We have already noted that sequencings were primarily investigated because they can be used to construct row-complete latin squares. In this section we outline another construction method.

Let q be an odd prime power. Let A be a q × mq array of symbols from 𝔽_{q} × ℤ_{m}, where 𝔽_{q} is the field with q elements. Write A_{ij} = (x_{ij}, y_{ij}) for 1 ≤ i ≤ q, 1 ≤ j ≤ mq. Then A is a generating array if the following conditions hold:

• each symbol appears once in each row of A; • if x_{ij} = x_{i′j} then i = i′;

• if y_{i,j+1} − y_{ij} = y_{i′,j′+1} − y_{i′j′} and (x_{ij}, x_{i,j+1}) = (x_{i′j′}, x_{i′,j′+1}) then (i, j) = (i′, j′).

Given a q × mq generating array, A, define L to be the mq × mq array (with symbols from 𝔽_{q} × ℤ_{m}) with

L_{kq+i,j} = (x_{ij}, y_{ij} + k)

where 1 ≤ i ≤ q, 1 ≤ j ≤ mq and 0 ≤ k ≤ m − 1.

Theorem 20 [17] L, as defined above, is an mq × mq row-complete latin square.

□

Thus to construct an mq × mq row-complete latin square we need only to construct a q × mq generating array.

Example 4 [17] Let n = 9, 𝔽_{3} = {0, 1, 2}, ℤ_{3} = {0, 1, 2}. Then the array A given in Figure 4 is a generating array. The corresponding row-complete latin square L is given in Figure 5. It is obtained by using the map ϕ : 𝔽_{3} × ℤ_{3} → {1, 2, …, 9}, (x, y) ↦ 3x + y + 1 as integers.

Figure 4: A 3 × 9 generating array, A.

\begin{matrix}(0, 0) & (1, 0) & (2, 0) & (0, 1) & (1, 2) & (2, 1) & (1, 1) & (2, 2) & (0, 2) \\ (1, 0) & (0, 1) & (0, 0) & (2, 1) & (2, 0) & (0, 2) & (2, 2) & (1, 1) & (1, 2) \\ (2, 0) & (2, 1) & (1, 2) & (1, 1) & (0, 1) & (1, 0) & (0, 2) & (0, 0) & (2, 2) \end{matrix}

Figure 5: A 9 × 9 row-complete latin square, L.

1 4 7 2 6 8 5 9 3
4 2 1 8 7 3 9 5 6
7 8 6 5 2 4 3 1 9
2 5 8 3 4 9 6 7 1
5 3 2 9 8 1 7 6 4
8 9 4 6 3 5 1 2 7
3 6 9 1 5 7 4 8 2
6 1 3 7 9 2 8 4 5
9 7 5 4 1 6 2 3 8

It seems that this method was used by Mertz and Sonneman to construct row-complete latin squares of orders 9 and 15 respectively, reported in [43] (they are given as columncomplete latin squares there; transposing gives row-complete squares). Archdeacon, Dinitz, Stinson and Tillson [17] first formally defined generating arrays; they also constructed row-complete latin squares of orders 9 and 15 and found examples of orders 21 and 27 not based on groups. In [32, chapter 3] it is reported that Owens, Dinitz and Stinson have found examples of orders 25 and 33. Until 1997 squares constructed from sequencings were the only other known row-complete latin squares of odd order. Higham [44] combined these squares to make larger ones, showing that if there is a sequenceable group of odd order m and a row-complete latin square of odd order n then there is a rowcomplete latin square of order mn. In 1998 he returned to the concept of a generating array to show

Theorem 21 [45] Row-complete latin squares of all odd composite orders exist.

Proof: We will show how to construct the appropriate generating arrays. Detailed proofs of their correctness may be found in [45].

Let q be an odd prime power, q > 3. We construct a q ×mq generating array A, where A_{ij} = (x_{ij}, y_{ij}). Note that every odd composite number except 9 has a proper prime power divisor greater than 3 and we have already seen a 9 × 9 row complete latin square.

Case 1, m = 4r + 1: We set the y_{ij}’s first. Choose y_{ij} to be constant within each column, y_{ij} = s_{j} say.

Now,

(0, 4r, 1, 4r − 1, …, r − 2, 3r + 2, r − 1, 3r + 1, r,

3r − 1, r + 1, 3r − 2, …, 2r − 2, 2r + 1, 2r − 1, 2r, 0)

is the sequence of partial sums of an R-sequencing of ℤ_{m} (see Section 3.2).

Let w be the sequence obtained from this by removing the final 0, adding r +1 to each term and cyclically shifting the new sequence forward 2r places. That is,

w = (2r + 1, 4r, 2r + 2, 4r − 1, …, 3r − 1, 3r + 2, 3r, 3r + 1,

r + 1, r, r + 2, r − 1, …, 2r − 1, 2, 2r, 1).

Let s_{j} be the jth element of the sequence that begins with q − 1 0’s, then has q − 1 copies of w, then the reverse of w and finishes with a 0.

To allocate the x_{ij}’s we produce m q ×q component latin squares, C^{(k)}, 0 ≤ k ≤ m−1. The kth component square is then matched with the symbol k where it occurs in the second co-ordinate of the generating array. More specifically, put the lth column of C^{(k)} in the first co-ordinates of the lth column of A which consists of the symbol k in the second co-ordinate (1 ≤ l ≤ q).

We now define these component squares. Let σ be a primitive element of 𝔽_{q} such that σ ≠ 2. The field 𝔽_{q} has such a σ for q an odd prime power ≥ 5. Let 𝔽_{q} = {f_{1}, f_{2}, … f_{q}}. Then

C^{(k)}_{ij} = \{ \begin{matrix}a_{k}f_{i} + b_{k}σ^{j} + c_{k} & if 1 ≤ j < q \\ a_{k}f_{i} + c_{k} & if j = q \end{matrix}

where a_{0} = ⋯ = a_{2r} = 1, a_{2r+1} = ⋯ = a_{4r} = −1, b_{0} = 1, b_{1} = 1 − σ, b_{2} = ⋯ = b_{r} = 1, b_{r+1} = ⋯ = b_{2r} = −1, b_{2r+1} = ⋯ = b_{3r} = 1/2 − 1/σ, b_{3r+1} = ⋯ = b_{4r} = 1/2, c_{0} = −σ/2 and c_{1} = ⋯ = c_{4r} = 0.

We now have a generating array for m = 4r + 1.

Case 2, m = 4r + 3: This differs only slightly from the previous case. Again choose y_{ij} = s_{j}

Now,

(0, 4r + 2, 1, 4r + 1, …, r − 2, 3r + 4, r − 1, 3r + 3, r,

3r + 1, r + 1, 3r, r + 2, 3r − 1, …, 2r − 1, 2r + 2, 2r, 2r + 1, 0)

is the sequence of partial sums of an R-sequencing in ℤ_{m}.

Let w be the sequence obtained from this by removing the final 0, adding r + 1 to each term, reversing the sequence and cyclically shifting the new sequence forward 2r + 1 places. That is,

w = (2r + 1, 1, 2r, 2, …, r + 3, r − 1, r + 2, r, r + 1,

3r + 2, 3r + 1, 3r + 3, 3r, 3r + 4, …, 4r, 2r + 3, 4r + 1, 2r + 2, 4r + 2).

Again, let s_{j} be the jth element of the sequence that begins with q − 1 0’s then has q − 1 copies of w, then the reverse of w and finishes with a 0.

We use component squares as before to allocate the x_{ij}’s. Let σ be a primitive element of 𝔽_{q} such that σ ≠ 2 and 3σ ≠ 2. The field 𝔽_{q} has such a σ for q an odd prime power power ≥ 5. Let 𝔽_{q} = {f_{1}, f_{2}, …, f_{q}}. Then

C^{(k)}_{ij} = \{ \begin{matrix}a_{k}f_{i} + b_{k}σ^{j} + c_{k} & if 1 ≤ j < q \\ a_{k}f_{i} + c_{k} & if j = q \end{matrix}

where a_{0} = ⋯ = a_{2r} = 1, a_{2r+1} = ⋯ = a_{4r+1} = −1, a_{4r+2} = 1, b_{0} = ⋯ = b_{r} = 1, b_{r+1} = ⋯ = b_{2r} = −1, b_{2r+1} = 1/2 − 1/σ, b_{2r+2} = ⋯ = b_{3r+1} = 1, b_{3r+2} = ⋯ = b_{4r+1} = −1, c_{0} = −σ/2 and c_{1} = ⋯ = c_{4r} = 0.

We now have a generating array for m = 4r + 3 and hence we have a row complete latin square of every odd composite order. □

It is known that there are no n × n row-complete latin squares for n = 3, 5 or 7, but the question for other odd primes remains open.

4 Index Of Notation

ℤ_{n}

: The integers modulo n (considered as the additively written cyclic

group of order n)

C_{n} : The (multiplicatively written) cyclic group of order n
D_{2n} : The dihedral group of order 2n

Q_{4n} : The dicyclic group of order 4n; this is a generalised quaternion group

if n is a power of 2

A_{n} : The alternating group on n symbols
S_{n} : The symmetric group on n symbols
𝔽_{q} : The field with q elements (q must be a prime power)
PSL(2, q) : The projective special linear group of 2 × 2 matrices over 𝔽_{q}
PGL(2, q) : The projective general linear group of 2 × 2 matrices over 𝔽_{q}
PΓL(2, q) : The automorphism group of PSL(2, q)
G′ : The derived subgroup of a group G
O(G) : The largest normal subgroup of odd order of a group G
Λ(G) : The normal subgroup of order 2 of a binary group G
⌊k⌋ : The smallest integer greater than k − 1

5 Acknowledgements

I am grateful to Prof. R. A. Bailey (Queen Mary, University of London) for reading preliminary versions of this paper and for many useful suggestions. I am also grateful for the useful suggestions of two referees, including the material on the structure of binary groups in Section 2.3

References

[1] B. A. Anderson, Sequencings and starters, Pacific J. Math. 64 (1976) 17–24. 2.2, 5

[2] B. A. Anderson, A fast method for sequencing low order non-abelian groups, Ann. Discrete Math. 34 (1987) 27–42. 2.2, 2.2, 2.2, 2.3, 2.5

[3] B. A. Anderson, Sequencings of dicyclic groups, Ars Combin. 23 (1987) 131–142. 6, 2.3

[4] B. A. Anderson, S_{5}, A_{5} and all non-abelian groups of order 32 are sequenceable, Congr. Numer. 58 (1987) 53–68. 2.3, 2.5

[5] B. A. Anderson, Sequencings of dicyclic groups II, J. Combin. Math. Combin. Comp. 3 (1988) 5–27. 2.3

[6] B. A. Anderson, All dicyclic groups of order at least 12 have symmetric sequencings, Contemp. Math. 111 (1990) 5–21. 2.3 [7] B. A. Anderson, Some quasi-2-complete latin squares, Congr. Numer. 70 (1990)

65–79. 3.1

[8] B. A. Anderson, A product theorem for 2-sequencings, Discrete Math. 87 (1991) 221–236. 2.4

[9] B. A. Anderson, Bailey’s conjecture holds through 87 except possibly for 64, J. Combin. Math. Combin. Comp. 12 (1992) 187–195. 3.1

[10] B. A. Anderson and E. C. Ihrig, All groups of odd order have starter-translate 2sequencings, Australas. J. Combin. 6 (1992) 135–146. 3.1

[11] B. A. Anderson and E. C. Ihrig, Every finite solvable group with a unique element of order two, except the quaternion group, has a symmetric sequencing, J. Combin. Des. 1 (1993) 3–14. 7, 2.3, 8, 3.1

[12] B. A. Anderson and E. C. Ihrig, Symmetric sequencings of non-solvable groups, Congr. Numer. 93 (1993) 73–82. 2.3

[13] B. A. Anderson and P. A. Leonard, Symmetric sequencings of finite Hamiltonian groups with a unique element of order 2, Congr. Numer. 65 (1988) 147–158. 2.3, 3.1

[14] I. Anderson and R. A. Bailey, Completeness properties of conjugates of latin squares based on groups, and an application to bipartite tournaments, Bull. Inst. Combin. Appl. 21 (1997), 95–99. 1

[15] I. Anderson and D. A. Preece, Locally balanced change-over designs, to appear in Util. Math. 3.1

[16] I. Anderson and D. A. Preece, Power sequence terraces for ℤ_{n}, where n is a prime power, submitted to Discrete Math. 3.1

[17] D. S. Archdeacon, J. H. Dinitz, D. R. Stinson and T. W. Tillson, Some new rowcomplete latin squares, J. Combin. Theory Ser. A 29 (1980) 395–398. 20, 4, 3.5

[18] L. Babai and P. J. Cameron, Automorphisms and enumeration of switching classes of tournaments, Electronic J. Combinatorics 7 (2000), #R38. 2.3

[19] R. A. Bailey, Quasi-complete latin squares: construction and randomization, J. R. Stat. Soc. Ser. B Stat. Methodol. 46 (1984) 323–334. 2.3, 3.1, 9, 11, 12, 3.1

[20] R. A. Bailey, M. A. Ollis and D. A. Preece, Round-dance neighbour designs from terraces, Discrete Math., to appear. 2

[21] R. A. Bailey and R. W. Payne, Experimental design: statistical research and its application. In Institute of Arable Crops Research Report for 1989, J. Abbott (ed.) (1989) 107–112. Harpenden: Agriculture and Food Research Council, Institute of Arable Crops Research. 3.1 [22] R. A. Bailey and C. E. Praeger, Directed terraces for direct product groups, Ars

Combin. 25A (1988) 73–76. 2.3

[23] D. Bedford, On groups of orders p, p^{2}, pq and p^{3}, p, q prime: their classification and a discussion as to whether they are super P-groups, Undergraduate Special Study, University of Surrey (1987). 3.2, 3.3

[24] D. Bedford, M. A. Ollis and R. M. Whitaker, On bipartite tournaments balanced with respect to carry-over effects for both teams, Discrete Math 231 (2001) 81–87. 1

[25] H. Bender, Finite groups with dihedral 2-Sylow subgroups, J. Algebra 70 (1981) 216–228. 2.3

[26] W. Burnside, Theory of Groups of Finite Order, Dover Publications (reprint), New York, 1955. 2.3

[27] G. Campbell and S. Geller, Balanced latin squares, Purdue University Department of Statistics Mimeoseries 80-26 (1980). 3.1

[28] S. D. Cohen and G. L. Mullen, Primitive elements in finite fields and Costas arrays, Appl. Algebra Engr. Comm. Comput. 2 (1991) 45–53. 2.4

[29] H. S. M. Coxeter, Regular Complex Polytopes, Cambridge University Press, Cambridge, 1974. 2, 2.3

[30] J. Dénes and P. Hermann, On the product of all the elements of a finite group, Ann. Discrete Math. 15 (1982) 105–109. 3.3

[31] J. Dénes and A. D. Keedwell, Latin Squares and their Applications, Akadémiai Kiadó, Budapest/English Universities Press, London/Academic Press (1974). 3.2

[32] J. Dénes and A. D. Keedwell, Latin Squares: New Developments in the Theory and Applications, North-Holland (1991). 1, 3.2, 3.5

[33] J. Dénes and E. Tőrők, Groups and Graphs, Combinatorial Theory and its Applications, North Holland (1970) 257–289. 2

[34] L. E. Dickson, On finite algebras, Nachrichten der Königlichen Gesellschaft der Wissenschaften in Göttingen (Math.-Phys. Klasse) (1905) 358–393. 2

[35] G. H. Freeman, Some two-dimensional designs balanced for nearest neighbours, J. R. Statist. Soc. B 41 (1979) 88–95. 3.1

[36] G. H. Freeman, Further results on quasi-complete latin squares, J. R. Statist. Soc. B 43 (1981) 314–320. 3.1

[37] R. Friedlander, Sequences in groups with distinct partial products, Aequationes Math. 14 (1976) 59–66. 2.2, 2.4 [38] R. J. Friedlander, B. Gordon and M. D. Miller, On a group sequencing problem of

Ringel, Congr. Numer. 21 (1978) 307–321. 3.2

[39] S. W. Golomb and H. Taylor, Tuscan squares—a new family of combinatorial designs, Ars Combin. 20B (1985) 115–132. 1

[40] B. Gordon, Sequences in groups with distinct partial products, Pacific J. Math. 11 (1961) 1309–1313. 1, 1, 2, 2.1, 2

[41] D. Gorenstein and J. H. Walter, The characterization of finite groups with dihedral Sylow 2-subgroups, I, II and III, J. Algebra 2 (1965) 85–151, 218–270, 334–393. 2.3

[42] P. Headley, R-sequenceability and R*-sequenceability of abelian 2-groups, Discrete Math. 131 (1994) 345–350. 3.2

[43] A. Hedayat and K. Afsarinejad, Repeated measurements designs II, Ann. Statist. 6 (1978) 619–628. 3.5

[44] J. Higham, A product theorem for row-complete latin squares, J. Combin. Des. 5 (1997) 311–318. 3.5

[45] J. Higham, Row-complete latin squares of every composite order exist, J. Combin. Des. 6 (1998) 63–77. 21, 3.5

[46] G. B. Hoghton and A. D. Keedwell, On the sequenceability of dihedral groups, Ann. Discrete Math. 15 (1982) 253–258. 2.2

[47] P. D. Isaac, A. M. Dean and T. Ostrom, Sequentially counterbalanced latin squares, Statistics and Applications 3 (2001) 25–46. 1

[48] J. Isbell, Sequencing certain dihedral groups, Discrete Math. 85 (1990) 323–328. 2.2, 3

[49] J. Isbell, The Gordon game of a finite group, Amer. Math. Monthly 99 (1992) 567– 569. 3.4

[50] A. D. Keedwell, Some problems concerning complete latin squares, L.M.S. Lecture Notes 13: Combinatorics: Proc. of the British Comb. Conf. Aberystwyth 1973 (Eds: T. P. McDonough and V. C. Mavron) (1974) 89–96. 2

[51] A. D. Keedwell, Sequenceable groups: a survey, L.M.S. Lecture Notes 49: Finite Geometries and Designs, Proc. of the 2nd Isle of Thorns Conference. (Eds: P. J. Cameron, J. W. P. Hirschfield and D. R. Hughes) (1980) 205–215. 1

[52] A. D. Keedwell, On the sequenceability of non-abelian groups of order pq, Discrete Math. 37 (1981) 203–216. 2.4

[53] A. D. Keedwell, On the R-sequenceability and R_{h}-sequenceability of groups, Ann. Discrete Math. 18 (1983) 535–548. 3.2, 3.3 [54] A. D. Keedwell, Complete mappings and sequencings of finite groups, The CRC

Handbook of Combinatorial Designs. (Eds. C. J. Colbourn and J. H. Dinitz) CRC press (1996) 246–253. 1, 1, 3.2

[55] P. Li, Sequencing the dihedral groups D_{4k}, Discrete Math. 175 (1997) 271–276. 2.2, 4

[56] E. Lucas, Récréations Mathématiques, Tôme II. Albert Blanchard, Paris, 1892, reprinted 1975. 2, 2.3

[57] N. S. Mendelsohn, Hamiltonian decomposition of the complete directed n-graph, Proc. Colloq. Tihany: 1966, Academic Press (1968) 237–241. 2

[58] J. P. Morgan, Balanced polycross designs, J. R. Stat. Soc. Ser. B Stat. Methodol. 50 (1988) 93–104. 3.1, 14, 15, 3.1

[59] J. P. Morgan, Polycross designs with complete neighbour balance, Euphytica 39 (1988) 59–63. 3.1

[60] J. P. Morgan, Terrace constructions for bordered, two-dimensional neighbour designs, Ars Combin. 26 (1988) 123–140. 3.1

[61] J. P. Morgan, Some series constructions for two-dimensional neighbor designs, J. Statist. Plann. Inference 24 (1990) 37–54. 3.1

[62] C. K. Nilrat and C. E. Praeger, Complete Latin squares: terraces for groups, Ars Combin. 25 (1988) 17–29. 2.3

[63] M. A. Ollis, Protection against premature termination of experiments based on Williams squares with circular structure, to appear in Util. Math. 3.1

[64] M. A. Ollis, Terraces for G × C_{2}, where G is a soluble group with a single involution, in preparation. 3.1

[65] M. A. Ollis and D. A. Preece, Sectionable terraces and the (generalised) Oberwolfach problem, Discrete Math., to appear. 1, 2.3, 3.1

[66] L. J. Paige, Complete mappings of finite groups, Pacific J. Math. 1 (1951) 111–116. 3.2

[67] D. S. Passman, Permutation Groups, Benjamin, New York, 1968. 2.3

[68] A. R. Rhemtulla, On a problem of L. Fuchs, Studia Sci. Math. Hungar. 4 (1969) 195–200. 3.3

[69] J. J. Rotman, An Introduction to the Theory of Groups (4th Edition), Springer-Verlag (1994). 1 [70] L. E. Smart, M. M. Blight, J. A. Pickett and B. J. Pye, Development of field strategies

incorporating semiochemicals for the control of the pea and bean weevil, Sitona lineatus L., Crop Protection 13 (1994) 127–136. 3.1

[71] D. J. Street, Some repeated measurements designs, Comm. Statist. Theory Methods 17(1), (1988) 87–104. 3.1

[72] A. D. Thomas and G. V. Wood, Group Tables, Shiva Publishing (1980). 2.2

[73] ChengDe Wang, Sequenceability, R-sequenceability, and harmoniousness of finite groups, Dissertation, Arizona State University, August 2000. 2.4

[74] ChengDe Wang, Complete latin squares of order p^{n} exist for odd primes p and n > 2, Discrete Math., to appear. 2.4

[75] ChengDe Wang and P. A. Leonard, More on sequences in groups, Australas. J. Combin. 21 (2000) 187–196. 3.2

[76] L. L. Wang, A test for the sequencing of a class of finite groups with two generators, Amer. Math. Soc. Notices 20 (1973) 73T–A275. 2

[77] E. J. Williams, Experimental designs balanced for the estimation of residual effects of treatments, Aust. J. Sci. Res. A 2 (1949) 149–168. 1, 3.1, 3.1, 10, 3.1

[78] C. E. Wright, A systematic polycross design, Res. Exp. Rec. Min. Agric. N.I. 11:1 (1961) 7–8. 3.1