%From m.a.ollis@qmul.ac.uk Thu Jul 11 08:15:34 2002
%
% LaTeX file for 34 page document: A DYNAMIC SURVEY
%
%
% Sequenceable Groups and Related Topics
%
% M. A. Ollis
%
%
% Electronic Journal of Combinatorics 9 (2002) #DS00
%
% Submitted 15th November 2001
% Resubmitted 11th July 2002
%
\documentclass[12pt]{article}
\setlength{\textwidth}{6.3in}
\setlength{\textheight}{8.7in}
\setlength{\topmargin}{0pt}
\setlength{\headsep}{0pt}
\setlength{\headheight}{0pt}
\setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}
\makeatletter
\newfont{\footsc}{cmcsc10 at 8truept}
\newfont{\footbf}{cmbx10 at 8truept}
\newfont{\footrm}{cmr10 at 10truept}
\renewcommand{\ps@plain}{%
\renewcommand{\@oddfoot}{\footsc the electronic journal of combinatorics,
DS\#10\hfil\footrm\thepage}}
\makeatother
\pagestyle{plain}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage[colorlinks,backref]{hyperref}
\newtheorem{lem}{Lemma}
\newtheorem{thm}{Theorem}
\newtheorem{con}{Conjecture}
\newtheorem{prop}{Proposition}
\newtheorem{cor}{Corollary}
\newtheorem{exa}{Example}
\newcommand{\qed}{\unskip\protect\nolinebreak\mbox{\quad$\Box$}}
\newcommand{\noqed}{\begin{flushright}$\Box$\end{flushright}}
\newcommand{\pspace}{\vspace{5mm}}
\newcommand{\ul}{\underline}
\setcounter{tocdepth}{5}
\begin{document}
\title{Sequenceable Groups and Related Topics}
\author{M. A. Ollis \\
\small School of Mathematical Sciences,\\[-0.8ex]
\small Queen Mary, University of London,\\[-0.8ex]
\small Mile End Road, London, E1 4NS, UK.\\[-0.8ex]
\small \texttt{M.A.Ollis@qmul.ac.uk}}
\date{\small Submitted November 15, 2001; Accepted August 12, 2002.\\
\small MR Subject Classifications: 20D60, 05B15}
\maketitle
\begin{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\'{e}nes)
in 1991 and a short overview,
including results about complete mappings and R-sequencings,
was given in the CRC Handbook of Combinatorial Designs in 1995.
In Sections~\ref{intro} and~\ref{class}
we give a survey of the current situation concerning
sequencings.
In Section~\ref{relsub} 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.
\end{abstract}
\newpage
\tableofcontents
\vspace{10mm}
\section{Introduction}\label{intro}
A non-trivial finite group $G$ of order $n$ is said to be
{\em sequenceable} if its elements can be arranged in a
sequence
$(b_{1}, b_{2}, \ldots, b_{n})$ in such a way that
the partial products
$(a_{1}, a_{2}, \ldots, a_{n})$, where $a_{i} = b_{1}b_{2}\cdots b_{i}$,
are distinct. The sequence $(b_{1}, b_{2}, \ldots, b_{n})$ is
called a {\em sequencing} for $G$.
If $(b_{1},b_{2},\ldots,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 \neq 1$ then $a_{i-1}=a_{i}$).
The sequence
$(a_{1},a_{2},\ldots,a_{n})$ is called a
{\em basic directed terrace} (for any
element $g~\in~G$ the sequence
$(ga_{1},ga_{2}, \ldots, ga_{n})$ is
called a {\em directed terrace}---observe that
Theorem~\ref{compls} 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
\cite{rotman}.
Sequencings were introduced by Gordon \cite{gord}
because of a connection to complete latin squares
(see Theorem~\ref{compls}). They have been previously
surveyed by Keedwell \cite{survey, crckeed} and
D\'{e}nes and Keedwell \cite[chapter 3]{dk2}.
A {\em latin square} of order $n$ is an $n \times 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
$i$th row and $j$th column.
A latin square is said to be {\em 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 \times n$ latin square is said
to be {\em 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
{\em 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 {\em 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 \cite{will} 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 \cite{IDandO} survey the statistical
literature relating to row-complete
latin squares (which they call {\em 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 {\em Hamiltonian path}
is a path which passes through each vertex exactly
once; paths are {\em 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~\ref{exa44}
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 {\em 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 \cite{GandH85}
for more details about Tuscan squares.
\begin{thm}\label{compls} {\rm \cite{gord}}
Let $G$ be a sequenceable group and
$(b_{1},b_{2},\ldots,b_{n})$ be a sequencing with
associated basic directed terrace
$(a_{1},a_{2},\ldots,a_{n})$. Then
$L = (l_{ij})$, where $l_{ij} = {a_{i}}^{-1}a_{j}$
for $1 \leq i,j \leq n$,
is a complete latin square.
\end{thm}
Proof: Suppose $l_{ij} = l_{ik}$ for some
$1 \leq i,j,k \leq 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.
\qed\
\begin{exa}\label{exa44}
Let $G = \mathbb{Z}_{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~\ref{ls4}. Figure~\ref{piccy}
shows how this leads to a decomposition of the
complete directed graph on $4$ vertices into
disjoint hamiltonian paths.
\begin{figure}[htbp]\label{ls4}
\[
\begin{tabular}{cccc}
0 & 3 & 1 & 2\\
1 & 0 & 2 & 3\\
3 & 2 & 0 & 1\\
2 & 1 & 3 & 0
\end{tabular}\]
\caption{$L$}
\end{figure}
\begin{figure}[htbp]
\begin{center}
\setlength{\unitlength}{1.1pt}
\begin{picture}(330,90)
\put(25,25){\circle*{3}}
\put(75,75){\circle*{3}}
\put(25,75){\circle*{3}}
\put(75,25){\circle*{3}}
\put(105,25){\circle*{3}}
\put(155,25){\circle*{3}}
\put(105,75){\circle*{3}}
\put(155,75){\circle*{3}}
\put(185,25){\circle*{3}}
\put(235,25){\circle*{3}}
\put(185,75){\circle*{3}}
\put(235,75){\circle*{3}}
\put(265,25){\circle*{3}}
\put(315,75){\circle*{3}}
\put(265,75){\circle*{3}}
\put(315,25){\circle*{3}}
\put(25,25){\vector(1,0){47}}
\put(75,25){\vector(-1,1){47}}
\put(25,75){\vector(1,0){47}}
\put(105,75){\vector(0,-1){47}}
\put(105,25){\vector(1,1){47}}
\put(155,75){\vector(0,-1){47}}
\put(235,25){\vector(0,1){47}}
\put(235,75){\vector(-1,-1){47}}
\put(185,25){\vector(0,1){47}}
\put(315,75){\vector(-1,0){47}}
\put(265,75){\vector(1,-1){47}}
\put(315,25){\vector(-1,0){47}}
\tiny
\put(20,20){\makebox(0,0){0}}
\put(20,80){\makebox(0,0){1}}
\put(80,80){\makebox(0,0){2}}
\put(80,20){\makebox(0,0){3}}
\put(100,20){\makebox(0,0){0}}
\put(100,80){\makebox(0,0){1}}
\put(160,80){\makebox(0,0){2}}
\put(160,20){\makebox(0,0){3}}
\put(180,20){\makebox(0,0){0}}
\put(180,80){\makebox(0,0){1}}
\put(240,80){\makebox(0,0){2}}
\put(240,20){\makebox(0,0){3}}
\put(260,20){\makebox(0,0){0}}
\put(260,80){\makebox(0,0){1}}
\put(320,80){\makebox(0,0){2}}
\put(320,20){\makebox(0,0){3}}
\end{picture}
\caption{Decomposition of the complete directed graph with 4 vertices}\label{piccy}
\end{center}
\end{figure}
\end{exa}
Sequencings with special properties have been used to solve
problems concerning bipartite tournaments balanced for carry-over
effects \cite{bbt, dbmaormw} and some cases of the Oberwolfach problem
\cite{secterr}. 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 \cite{crckeed} 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.
\section{Classifying Sequenceable Groups}\label{class}
In his paper \cite{gord}, which introduced
the concept of a sequencing, Gordon also
completely classified the sequenceable
abelian groups: see Section~\ref{abelian}.
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\'{e}nes
and T\H{o}r\H{o}k \cite{dt} 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 \cite{mendel} published an
independently obtained sequencing for the
non-abelian group of order 21. In 1973
Keedwell \cite{nonab27} sequenced the non-abelian group
of order 27 with exponent 9
and Wang \cite{nonab39} 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~\ref{dihed}. 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~\ref{lambda}.
We define a {\em binary group} to be a group with a single element
of order 2. This does not contradict Dickson's \cite{Dickson} use
of the term and fits well as a generalisation of binary
polyhedral groups: see \cite{cox}. In the literature
on sequencings, binary groups are usually called {\em $\Lambda$-groups}.
In 1981 Keedwell was the first to give sequencings
of infinitely many non-abelian groups of odd
order: see Section~\ref{pq}.
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.
\subsection{Abelian Groups}\label{abelian}
In this section we shall write abelian groups
additively.
In \cite{gord} 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.
\begin{thm}\label{ab} { \rm \cite{gord} }
A finite abelian group $G$ is sequenceable
if and only if $G$ is a binary group.
\end{thm}
Proof ($\Rightarrow$):
Suppose $(b_{1}, \ldots ,b_{n})$ is a
sequencing for $G$ with associated basic
directed terrace $(a_{1}, \ldots ,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~\in~G \setminus \{ 0 \}$ we have
$g \neq -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}, \ldots ,u_{l}\}$
for some $u_{1}, \ldots ,u_{l} \in H$,
thus each $h_{i}$ is expressible
in the form $\epsilon_{1}u_{1}+\cdots+
\epsilon_{l}u_{l}$ with each
$\epsilon_{i} \in \{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$.
($\Leftarrow$): 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~\ref{terracesec}. \qed\
\begin{exa}\label{cyc2n}
Consider the cyclic group of
even order, $\mathbb{Z}_{2n}$. The following
${\bf b}$ is a sequencing and has
corresponding basic directed terrace ${\bf a}$.
\[ {\bf b} =
(0,1,2n-2,3,2n-4,5, \ldots ,4,2n-3,2,2n-1) \]
\[ {\bf a} =
(0,1,2n-1,2,2n-2,3, \ldots ,n+2,n-1,n+1,n). \]
This
sequencing was first given (implicitly) by Lucas (who gave credit to
Walecki) in {\rm \cite{lucas}}, 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 {\rm \cite{rabmaodap}}.
\end{exa}
Combining Example~\ref{cyc2n}
and Theorem~\ref{compls} gives
a method for constructing a complete
latin square of any even order.
\subsection{Dihedral Groups}\label{dihed}
Let $n \geq 3$. We describe the dihedral group $D_{2n}$,
of order $2n$, as the set of ordered
pairs $(x,\epsilon)$ with
$x \in \mathbb{Z}_{n}$ and
$\epsilon \in \mathbb{Z}_{2}$ and multiplication
defined by:
\begin{eqnarray*}
(x,0)(y,\delta) &=& (x+y,\delta) \\
(x,1)(y,\delta) &=& (x-y,1+\delta).
\end{eqnarray*}
In 1976 Anderson \cite{and:seqstart} showed that
$D_{2p}$ is sequenceable
if $p$ is a prime with a primitive root $r$ such
that $3r \equiv -1 \pmod{p}$. Also in 1976 Friedlander
\cite{fried} showed that $D_{2p}$ is sequenceable
if $p$ is prime and $p \equiv 1 \pmod{4}$. In 1981 Hoghton
and Keedwell
\cite{hogh} added the groups $D_{2p}$,
where $p$ is a prime such that
$p \equiv 7 \pmod{8}$ and $p$ has
a primitive root $r$ such that
$2r \equiv -1 \pmod{p}$.
All of these results were obtained
using quotient sequencings (see Section~\ref{pq})
and number theoretic arguments of
varying intricacy.
In 1987 Anderson \cite{and:loseqs}
used a computer search to show that
all dihedral groups $D_{2n}$ for
$5 \leq n \leq 50$ are sequenceable.
In 1990 Isbell \cite{isb}
produced a general argument which,
when allied to Anderson's computer
search, covered all of the infinite
classes mentioned above and more:
\begin{thm}\label{isbell} {\rm \cite{isb}}
The dihedral groups $D_{2n}$, of
order $2n$, are sequenceable for
all $n$, where $n \neq 3$ ($D_6$
is not sequenceable) and
$n \neq 4k$.
\end{thm}
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
${\bf b} = (e,\alpha,\beta,\gamma)$ where
$e$ is the identity, $\alpha$ and $\gamma$
partition the remaining elements of the form $(x,0)$
and $\beta$ consists of the elements of
the form $(x,1)$.
Case 1; $n=4k+1$:
We define $\alpha$, $\beta$ and $\gamma$
as follows:
\begin{eqnarray*}
\alpha &=& (2k-1,0),(2-2k,0),(2k-3,0),
(4-2k,0), \ldots, (3,0),(-2,0), \\
& & (1,0),(2k,0) \\
\beta &=& (0,1),(1,1),(2,1), \ldots,
(2k-1,1),(4k,1),(2k,1),(2k+1,1), \ldots, \\
& & (4k-1,1) \\
\gamma &=& (-2k,0),(-1,0),(2,0),(-3,0),(4,0),
\ldots, (3-2k,0),(2k-2,0), \\
& & (1-2k,0).
\end{eqnarray*}
Case 2; $n=8k+7$, ($k \geq 1$):
We produce $\beta$ in the same manner as
before:
\[ \beta = (0,1),(1,1), \ldots ,(4k+2,1),
(8k+6,1),(4k+3,1), \ldots ,(8k+5,1). \]
Now, working in $\mathbb{Z}_{8k+7}$, consider the
following sequence:
\begin{eqnarray*}
\sigma &=& -(2k+1),(4k+2),-(4k+1),4k, \ldots,-(2k+3),(2k+2), \\
& & -1,-2k,(2k-1),-(2k-2), \ldots,3,-2.
\end{eqnarray*}
Define $\alpha$ to be the sequence in $D_{2n}$ with
$\sigma$ in the first co-ordinates and $0$'s in the
second, followed by $(-(4k+3),0)$. Define $\gamma$
to be $(4k+3,0)$ followed by the sequence with
$- \sigma$ in the first co-ordinates and $0$'s in
the second. Now the sequence $(e,\alpha,\beta,\gamma)$
lists all elements of $D_{2n}$ and is the required sequencing.
Case 3; $n=8k+3$, ($k \neq 1,2,4 $):
Again we use the list $(e, \alpha, \beta, \gamma)$
but here $\beta$ is slightly more complicated:
\begin{eqnarray*}
\beta &=& (0,1),(1,1), \ldots ,(4k-1,1),(8k,1),
(8k+1,1),(8k+2,1),(4k,1), \\
& & (4k+1,1), \ldots, (8k-1,1).
\end{eqnarray*}
Similarly to the $n=8k+7$ case we look at sequences in
$\mathbb{Z}_{8k+3}$ first. Define
\[ X_{(k)} = \{x : -k \leq x \leq k-1, x \neq 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 \leq i \leq 2k-2$.
This condition is satisfied by the following three
orderings:
\begin{eqnarray*}
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).
\end{eqnarray*}
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)}$ $(\supseteq X_{(k)})$
of integers defined as follows:
\[ Y_{(k)} = \{x : -(2k-1) \leq x \leq 2k, x \neq -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 \leq i \leq 4k-2$:
\[ (\underbrace{2, \ldots, -k}_{X_{k}},
k,-(k+1),k+1, \ldots, -(2k-1),(2k-1),2k,1). \]
Let $\tau_{k}$ be the sequence of differences
of consecutive elements in this ordering
$Y_{k}$: then the partial sums of $\tau_{k}$
list the translate $-2 + Y_{(k)}$ without
repetition. Define $\alpha$ to be the
sequence with $\tau_{k}$ in the first
co-ordinates and $0$'s in the second,
followed by $({-(4k+1)},0),(4k-1,0),(-4k,0)$.
Define $\gamma$ to be $(4k,0)$ followed
by the sequence with $-\tau_{k}$ in the
first co-ordinates and $0$'s in the
second, finishing with $(4k+1,0),(-(4k-1),0)$.
We now have $(e,\alpha,\beta,\gamma)$ listing
$D_{2n}$ without repetition and this is the required
sequencing.
Case 4; $n=4k+2$, $k$ even ($k \geq 2$):
For this we use the sequence
$(e,\beta,\alpha,\delta,\gamma)$ where $e$
is the identity, $\alpha$ and $\gamma$
partition the remaining elements
$(x,0)$ (here $\alpha$ and $\gamma$
are not of equal length), $\delta$ is
$(4k+1,1)$ and $\beta$ covers
the other elements $(x,1)$. We construct
$\beta$ in the same manner as in case
$n=4k+1$, that is
\begin{eqnarray*}
\beta &=& (0,1),(1,1),(2,1), \ldots,
(2k-1,1),(4k,1),(2k,1),(2k+1,1), \ldots, \\
& & (4k-1,1).
\end{eqnarray*}
Consider the
following two sequences in $\mathbb{Z}_{4k+2}$:
\begin{eqnarray*}
\sigma_{1} &=& -3,5,-7,9, \ldots, 2k-3,
\underbrace{1-2k,2k-2},-(2k-3),2k-5,
\ldots, -5, \\
& & -3 \\
\sigma_{2} &=& -2,4,-6,8, \ldots, 2k-4,
\underbrace{-(2k-2),1,2k-1,-1}, -(2k-4), \\
& & 2k-6, \ldots, -4,2.
\end{eqnarray*}
Define $\alpha$ to be $(2k+2,0)$ followed by
the sequence with $\sigma_{1}$ in the first
co-ordinates and $0$'s in the second, followed
by $(2k,0),(2k+1,0)$. Define $\gamma$ to be
the sequence with $\sigma_{2}$ as the first
co-ordinates and 0's as the second.
Now $\alpha$ and $\gamma$ cover all
elements $(x,0)$ such that $x \neq 0$, and
$(e, \beta, \alpha, \delta, \gamma)$
is a sequencing of $D_{2n}$.
Case 5; $n=4k+2$, $k$ odd ($k \geq 3$):
We define the sequencing
$(e,\beta,\alpha,\delta,\gamma)$ as in the previous case, but
we need to modify $\sigma_{1}$ and $\sigma_{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
\begin{eqnarray*}
\sigma_{1} &=& -3,5,-7,9, \ldots, -(2k-3),
\underbrace{2k-2,1-2k},2k-3,-(2k-5), \ldots, \\
& & -5,3 \\
\sigma_{2} &=& -2,4,-6,8, \ldots, -(2k-4),
\underbrace{-1,2k-1,1,-(2k-2)}, 2k-4, \\
& & -(2k-6), \ldots, -4,2.
\end{eqnarray*}
The construction now goes through as before.
The anomalous cases:
The sequencings given here are those
due to Anderson \cite{and:loseqs},
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 \cite{gptables}).
Recall that $D_{6}$ is not sequenceable.
Below, ${\cal S}_{2n}$ is a sequencing
for $D_{2n}$.
\begin{eqnarray*}
{\cal S}_{12} &:& (1,11,2,7,3,9,12,10,6,5,8,4) \\
{\cal S}_{14} &:& (1,8,2,10,7,6,9,5,11,4,14,13,12,3) \\
{\cal S}_{22} &:& (1,8,18,15,16,5,10,4,6,13,11,3,19,17,7,9,
22,2,14,12,20,21) \\
{\cal 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) \\
{\cal 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)
\end{eqnarray*}
\noqed\
In 1997 Li \cite{li} completed the classification of
sequenceable dihedral groups by sequencing $D_{2n}$
where $n \equiv 0 \pmod{4}, \: n \neq 4$. Recourse to Anderson's
computer search \cite{and:loseqs} was again needed for some
small cases.
\begin{thm}\label{Lithm} {\rm \cite{li} }
The dihedral groups $D_{2n}$ are sequenceable when $n = 4k$,
except when $n = 4$.
\end{thm}
Construction:
The construction varies slightly as
$k$ varies modulo 4. For each
case the sequencing is ((a), (b), $\ldots$, (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.
\begin{table}[p]
\caption{$k \equiv 0 \pmod{4}$, $k \geq 4$}\label{tab0m4}
\begin{footnotesize}
\begin{tabular}{|c|l|l|} \hline
\multicolumn{2}{|l|}{Sequencing} & No. of terms \\ \hline
(a) & $(0,0)$ & 1 \\
(b) & $(0,1),(1,1),(2,1), \ldots, (2k-2,1)$ & $2k-1$ \\
(c) & $(4k-2,1)$ & 1 \\
(d) & $(2k-1), (2k,1),(2k+1,1), \ldots, (4k-3,1)$ & $2k-1$ \\
(e) & $(2k,0)$ & 1 \\
(f) & $(4k-3,0),(5,0),(4k-7,0),(9,0), \ldots, (2k-3,0)$ & $k-2$ \\
(g) & $(2k+2,0)$ & 1 \\
(h) & $(2k-1,0),(2k+3,0),(2k-5,0),(2k+7,0), \ldots ,(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), \ldots, (k-2,0)$ & $k/2 - 1$ \\
(l) & $(1,0)$ & 1 \\
(m) & $(3k-4,0), (k+6,0), (3k-8,0),(k+10,0), \ldots, (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), \ldots ,(3k-2,0)$ & $k/2 - 2$ \\
(r) & $(4k-1,0)$ & 1 \\
(s) & $(k,0),(3k+2,0),(k-4,0),(3k+6,0), \ldots ,(4,0)$ & $k/2 - 1$ \\ \hline
\end{tabular}
\end{footnotesize}
\end{table}
\begin{table}[p]
\caption{$k \equiv 1 \pmod{4}$, $k \geq 5$}\label{tab1m4}
\begin{footnotesize}
\begin{tabular}{|c|l|l|} \hline
\multicolumn{2}{|l|}{Sequencing} & No. of terms \\ \hline
(a) & $(0,0)$ & 1 \\
(b) & $(0,1),(1,1),(2,1), \ldots, (2k-2,1)$ & $2k-1$ \\
(c) & $(4k-2,1)$ & 1 \\
(d) & $(2k-1), (2k,1),(2k+1,1), \ldots, (4k-3,1)$ & $2k-1$ \\
(e) & $(2k,0)$ & 1 \\
(f) & $(4k-3,0),(5,0),(4k-7,0),(9,0), \ldots, (2k-1,0)$ & $k-1$ \\
(g) & $(2k+2,0)$ & 1 \\
(h) & $(2k-3,0),(2k+5,0),(2k-7,0),(2k+9,0), \ldots ,(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), \ldots, (k,0)$ & $(k-3)/2$ \\
(l) & $(1,0)$ & 1 \\
(m) & $(3k-3,0), (k+5,0), (3k-7,0),(k+9,0), \ldots, (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), \ldots ,(3k-1,0)$ & $(k-1)/2$ \\
(r) & $(4k-1,0)$ & 1 \\
(s) & $(k-1,0),(3k+3,0),(k-5,0),(3k+7,0), \ldots ,(4,0)$ & $(k-3)/2$ \\ \hline
\end{tabular}
\end{footnotesize}
\end{table}
\begin{table}[p]
\caption{$k \equiv 2 \pmod{4}$, $k \geq 6$}\label{tab2m4}
\begin{footnotesize}
\begin{tabular}{|c|l|l|} \hline
\multicolumn{2}{|l|}{Sequencing} & No. of terms \\ \hline
(a) & $(0,0)$ & 1 \\
(b) & $(0,1),(1,1),(2,1), \ldots, (2k-2,1)$ & $2k-1$ \\
(c) & $(4k-2,1)$ & 1 \\
(d) & $(2k-1), (2k,1),(2k+1,1), \ldots, (4k-3,1)$ & $2k-1$ \\
(e) & $(2k,0)$ & 1 \\
(f) & $(4k-3,0),(5,0),(4k-7,0),(9,0), \ldots, (2k-3,0)$ & $k-2$ \\
(g) & $(2k+2,0)$ & 1 \\
(h) & $(2k-1,0),(2k+3,0),(2k-5,0),(2k+7,0), \ldots ,(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), \ldots, (k,0)$ & $k/2$ \\
(l) & $(4k-1,0)$ & 1 \\
(m) & $(3k-2,0), (k+4,0), (3k-6,0),(k+8,0), \ldots, (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), \ldots ,(3k-4,0)$ & $k/2 - 3$ \\
(r) & $(1,0)$ & 1 \\
(s) & $(k-2,0),(3k+4,0),(k-6,0),(3k+8,0), \ldots ,(4,0)$ & $k/2 - 2$ \\ \hline
\end{tabular}
\end{footnotesize}
\end{table}
\begin{table}[p]
\caption{$k \equiv 3 \pmod{4}$, $k \geq 7$}\label{tab3m4}
\begin{footnotesize}
\begin{tabular}{|c|l|l|} \hline
\multicolumn{2}{|l|}{Sequencing} & No. of terms \\ \hline
(a) & $(0,0)$ & 1 \\
(b) & $(0,1),(1,1),(2,1), \ldots, (2k-2,1)$ & $2k-1$ \\
(c) & $(4k-2,1)$ & 1 \\
(d) & $(2k-1), (2k,1),(2k+1,1), \ldots, (4k-3,1)$ & $2k-1$ \\
(e) & $(2k,0)$ & 1 \\
(f) & $(4k-3,0),(5,0),(4k-7,0),(9,0), \ldots, (2k-1,0)$ & $k-1$ \\
(g) & $(2k+2,0)$ & 1 \\
(h) & $(2k-3,0),(2k+5,0),(2k-7,0),(2k+9,0), \ldots ,(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), \ldots, (k-1,0)$ & $(k-1)/2$ \\
(l) & $(4k-1,0)$ & 1 \\
(m) & $(3k-1,0), (k+3,0), (3k-5,0),(k+7,0), \ldots, (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), \ldots ,(3k-3,0)$ & $(k-3)/2$ \\
(r) & $(1,0)$ & 1 \\
(s) & $(k-3,0),(3k+5,0),(k-7,0),(3k+9,0), \ldots ,(4,0)$ & $(k-5)/2$ \\ \hline
\end{tabular}
\end{footnotesize}
\end{table}
The anomalous cases:
As in the proof of Theorem~\ref{isbell} 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 ${\cal S}_{2n}$ for $D_{2n}$ \cite{and:loseqs}:
\begin{eqnarray*}
{\cal S}_{16} &:& (1,13,11,16,4,14,3,5,6,15,8,7,9,12,2,10) \\
{\cal 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)
\end{eqnarray*}
We have now covered all required values of $n$. \qed
\subsection{Binary Groups}\label{lambda}
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 $\Lambda(G)$.
The subgroup $\Lambda(G)$ is necessarily normal.
Let $G$ be
a binary group of order $2n$ with $z$ as
its unique element of order 2. A sequencing
${\bf b}$ of $G$ is said to be {\em symmetric} if
it is of the form
\[ {\bf b} = (e,b_{2},b_{3}, \ldots,b_{n},z,b_{n}^{-1},
\ldots , b_{3}^{-1},b_{2}^{-1}). \]
Note that as $z$ is the only element of
order 2 we have immediately that
$b_{i} \neq b_{i}^{-1}$ for $2 \leq i \leq n$.
Gordon's construction (Theorem~\ref{ab}) for sequencing abelian
groups gives symmetric sequencings, as does our new proof of that
theorem in Section~\ref{terracesec}.
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
\cite[chapter 3.18]{pass}, as is the automorphism group of a
switching class of tournaments~\cite{bc}.
We have already noted that the binary polyhedral groups are
binary groups.
Coxeter\cite[p.~82]{cox} 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 \cite{bc} 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~\cite[p.~132]{burn}: they are cyclic or
generalised quaternion groups. Here, the \emph{generalised quaternion group}
$Q_{2^n}$ is defined by
\[Q_{2^n}=\langle u,v\colon u^{2^{n-1}}=e, v^2=u^{2^{n-2}}, vuv^{-1}=u^{-1}
\rangle.\]
The Sylow 2-subgroups of
$G/\Lambda(G)$ have the form $S/\Lambda(S)$
for Sylow 2-subgroups $S$ of $G$. The quotient $S/\Lambda(S)$
is cyclic or
dihedral according as $S$ is cyclic or generalised quaternion.
Conversely, a cohomological argument due to Glauberman, reported
in~\cite{bc}, 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/\Lambda(G)\cong 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~\cite[p.~155]{burn}
and the Gorenstein--Walter Theorem~\cite{goren,bender}.
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 $2$-subgroup~$T$. Then
\begin{itemize}
\item
if $T$ is cyclic, then $H/O(H)\cong T$;
\item
if $T$ is dihedral, then $H/O(H)$ is isomorphic to the alternating group
$A_7$, or to a subgroup of $\mathrm{P}\Gamma\mathrm{L}(2,q)$ containing
$\mathrm{PSL}(2,q)$ (where $q$ is an odd prime power), or to $T$.
\end{itemize}
In particular, if $G$ is a soluble binary group, then $G/O(G)\Lambda(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 \cite{lucas}, although he did not use this terminology.
Following on from Gordon's construction, further results
have been obtained by Bailey and Praeger \cite{rabandp},
Nilrat and Praeger \cite{nilrat} 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 \cite{secterr}. Theorem 5 is an early result
which the rest of the work can be seen as generalising:
\begin{thm}\label{prod1} {\rm \cite{and:seqstart}}
If $G$ is a sequenceable group of odd
order $n$ then $G \times C_{2}$ has a
symmetric sequencing.
\end{thm}
Proof: Let $z$ be the non-identity element of $C_2$.
Observe first that $G \times C_2$ is
a binary group with $(e,z)$ as its unique element
of order two.
Let $(e,d_{2}, \ldots ,d_{n})$ be
a sequencing of $G$. Since $G$ is of
odd order, every non-identity element
is distinct from its inverse.
Partition $G \setminus \{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 ${\bf b}$, where
${\bf b} = (b_{1},b_{2}, \ldots ,b_{2n})$,
for $G \times C_{2}$:
\[
(b_{1},b_{2}, \ldots ,b_{n}) =
((e,e),(d_{2},\epsilon_{2}), \ldots ,
(d_{n},\epsilon_{n})) \]
where
\[ \epsilon_{i} = \left\{ \begin{array}{ll}
z & \mbox{if $d_{i}$ is a chosen element} \\
e & \mbox{otherwise,}
\end{array}
\right. \]
\[ b_{n+1} = (e,z) \]
and
\[ (b_{n+2},b_{n+3}, \ldots ,b_{2n}) =
(({d_{n}}^{-1},\epsilon_{n}),
({d_{n-1}}^{-1},\epsilon_{n-1}) \ldots ,
({d_{2}}^{-1},\epsilon_{2})). \]
Now ${\bf b}$ lists $G \times C_{2}$
without repetition and does so
symmetrically (since
${(b_{i},\epsilon_{i})}^{-1} = ({b_{i}}^{-1}, \epsilon_{i})$).
Also, all of the elements in
$G \times 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)$. \qed\
\vspace{4mm}
A key concept on which the work
relies is that of a 2-sequencing (or equivalently
a basic terrace), introduced by Bailey \cite{rabenum}.
A {\em $2$-sequencing}
of $H$, a group of order $n$, is a sequence of
elements $(e,d_{2},d_{3},\ldots,d_{n})$, not necessarily
distinct, such that:
\begin{itemize}
\item the associated partial products
$e,ed_{2},ed_{2}d_{3}, \ldots, ed_{2} \cdots d_{n}$
are all distinct; this sequence is called
a {\em basic terrace},
\item if $h \in H$ and $h \neq h^{-1}$ then
\[ |\{i : 2 \leq i \leq n, \ d_{i} \in \{h,h^{-1}\}\}|=2, \]
\item if $h \in H$ and $h=h^{-1}$ then
\[ |\{i: 1 \leq i \leq n, \ d_{i} = h \}| = 1. \]
\end{itemize}
Note that a sequencing for $H$ is also a 2-sequencing
for $H$.
The following generalisation of Theorem~\ref{prod1}
is pivotal:
\begin{thm}\label{symiff2} {\rm \cite{dic1}}
Let $G$ be a binary group of order $2n$.
Then $G$ has a symmetric sequencing if
and only if $G/\Lambda(G)$ has a
$2$-sequencing.
\end{thm}
Proof:
Let $\pi: G \rightarrow G/\Lambda(G)$ be
the natural projection. Then it is straightforward
to check that if
$(e,b_{2}, \ldots , b_{n},z,{b_{n}}^{-1}, \ldots, {b_{2}}^{-1})$
is a symmetric sequencing of $G$ then
$(\pi(e), \pi(b_{2}), \ldots, \pi(b_{n}))$ is a
2-sequencing of $G/\Lambda(G)$.
Let $z$ be the element of order 2 in $G$. If $y \in G/\Lambda(G)$ then
$y = \{ x, xz \}$ for some $x \in G$.
Suppose we are given a 2-sequencing of $G/\Lambda(G)$.
Lift this back to a sequence in $G$ as follows:
(i): If $y \in G/\Lambda(G)$, $y \neq 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 \in G/\Lambda(G)$, $y \neq 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 \in G/\Lambda(G)$, $y = y^{-1}$ and
$y \neq \{e,z\}$ then $y$ must occur once in our
2-sequencing. Now $y = \{ x, x^{-1} \}$ and
$y$ may be lifted back to either $x$
or $x^{-1}$.
(iv): If $y = \{ e,z \} \in G/\Lambda(G)$ then
$y$ must be lifted to $e$.
This process clearly gives a sequence of the form
$(e, b_{2}, \ldots, b_{n})$ in $G$ where
$b_{i} \neq b_{j}$ and ${b_{i}}^{-1} \neq b_{j}$
for $i,j \leq n$, where $i \neq j$.
Extend this to a sequence of all the elements of $G$:
$(e, b_{2}, \ldots, b_{n},z,{b_{n}}^{-1}, \ldots, {b_{2}}^{-1})$.
We claim that this is a symmetric sequencing of $G$.
The partial products are
$(e, a_{2}, \ldots, a_{n}, a_{n}z, a_{n-1}z, \ldots, a_{2}z)$:
we therefore need that $\{e, a_{2}, \ldots, a_{n} \}$ is
a transversal of $\{ \{w,wz\}:w \in G \}$. This follows
because each $a_{i}$ is either $w_{i}$ or $w_{i}z$ for
some $w_{i} \in G$ and the elements
$\{ e,z \} , \{ w_{2},w_{2}z \} , \ldots, \{ w_{n},w_{n}z \}$
of $G/\Lambda(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. \qed
Note that the construction of Theorem~\ref{symiff2} gives $2^{(n+k-1)/2}$
different symmetric sequencings of $G$ for each
2-sequencing of $G/\Lambda(G)$, where $k$ is the number of
elements of order 2 in $G/\Lambda(G)$.
\vspace{4mm}
Anderson and Ihrig extend this further to show:
\begin{thm}\label{andk}{\rm \cite{and:last}}
If $G$ is a binary group and $G/O(G)\Lambda(G)$ has
a 2-sequencing then $G$ has a symmetric sequencing.
\noqed\
\end{thm}
The groups $A_{4}$ and $S_{4}$ have
sequencings \cite{and:loseqs} and hence
have 2-sequencings.
We have also seen that cyclic and dihedral 2-groups
have sequencings (Example~\ref{cyc2n} and Theorem~\ref{Lithm}).
Prior to the proof of Theorem~\ref{Lithm}, Anderson had shown
that all dihedral groups have 2-sequencings \cite{dic1,dic2, dic12}.
The case $G/O(G)\Lambda(G) \cong 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 \cite{hamil} show that the groups
$Q_{8} \times 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 \cite{and:last} show that
all soluble binary groups $G$ with $G/O(G)\Lambda(G) \cong V$,
where $G \neq Q_{8}$, have symmetric sequencings.
Theorem~\ref{andk} now gives:
\begin{thm} {\rm \cite{and:last}}
All finite soluble binary groups,
except $Q_{8}$, have symmetric
sequencings.
\noqed\
\end{thm}
In \cite{symnon} 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 2-sequencings
of $A_{7}$, $\mathrm{PSL}(2,q)$ and $\mathrm{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 $\mathrm{PSL}(2,5) \cong A_{5}$ \cite{nonab32},
showing that such infinite sets of
sequenceable insoluble binary groups do exist.
\subsection{Groups of Odd Order}\label{pq}
Keedwell \cite{keedpq} and Wang \cite{WangDM} 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 \cite{fried}).
Let $G$ be a group of order $pq$
with normal subgroup $H$ of order $q$.
A sequence $\cal Q$ of length $pq$ containing
elements of $G/H$ is said to be a
{\em quotient sequencing} of $G/H$ if
each element of $G/H$ occurs $q$ times
in both $\cal Q$ and the partial product
sequence (the {\em basic quotient directed terrace})
of $\cal Q$. Note that the natural
map $G \rightarrow 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 \cong C_p$ for some odd
prime $p$, where $C_p = \langle u : u^p = e \rangle$. Let
$\beta$ be a primitive root of $p$ such that $\beta / (\beta - 1)$ is
also a primitive root of $p$ (Wang \cite{WangDM} reports that such a
$\beta$ exists, using the results of \cite{CandM}). Wang \cite{WangDM}
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, \ldots, e,x \ \ \ \mathrm{(} q \ \mathrm{elements)} \]
followed by $q-2$ copies of the sequence
\[ x^{\beta^{p-2}}, x^{\beta^{p-3}}, \ldots, x \ \ \ \mathrm{(} p-1 \ \mathrm{elements)} \]
and finishing with
\[ x^{\beta^{p-2}}, x^{\beta^{p-3}}, \ldots, x^{\beta},
x^{\beta}, x^{\beta^2 / (\beta - 1)}, x^{\beta^3 / (\beta - 1)^2}, \ldots,
x^{\beta - 1}, e \ \ \ \mathrm{(} 2(p-1) \ \mathrm{elements).} \]
Wang observes that this is a generalisation of the quotient directed
terrace used by Keedwell \cite{keedpq}.
The second important concept is the R-sequencing.
An {\em R-sequencing}\label{def:rseq} (sometimes called
a {\em near-sequencing}) of a
group $G$ is a sequence $(e,b_{2},b_{3}, \ldots, b_{n})$ of all the elements
of $G$
such that the partial products
$(e, eb_{2},eb_{2}b_{3}, \ldots,$
$eb_{2}b_{3} \cdots b_{n-1})$ are distinct
and $eb_{2}b_{3} \cdots 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 \cite{keedpq}
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- \beta}}$ and $x^{r - r^{1- \beta} - 1}$ are
adjacent for some $r$ with $r^p \equiv 1 \pmod{q}$ and
$r \not\equiv 1 \pmod{q}$. In \cite{WangDiss} Wang gives some examples of
such R-sequencings where 2 is not a primitive root of
$p$.
Wang \cite{WangDM} 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},\ldots ,b_{n})$,
is said to be a {\em starter-translate}
sequencing (Anderson \cite{prod2seq} abbreviates this to {\em st-sequencing})
if both of the sets
$\{b_{2},b_{4}, \ldots, b_{n-1} \}$ and
$\{b_{3},b_{5}, \ldots, b_{n} \}$ contain
precisely one of $g$ and $g^{-1}$ for
each $g \in G \setminus \{e\}$.
Anderson \cite{prod2seq} shows that if $G$ and $H$ are groups with
st-sequencings then $G \times 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.
\subsection{Summary}\label{summary}
In addition to the results given already in this
chapter, Anderson \cite{and:loseqs, nonab32} has used a
hill-climbing algorithm to sequence all non-abelian
groups of order $n$, where $10 \leq n \leq 32$, and $A_{5}$ and $S_{5}$,
the alternating and symmetric groups on 5 symbols.
Therefore the following groups are known to be sequenceable.
\begin{itemize}
\item Dihedral groups of order at least $10$
\item Soluble (including abelian) binary groups, except
$Q_{8}$
\item Insoluble binary groups $G$ with $A_{5}$ as their
only non-abelian composition factor
\item Some groups of order $pq$ where $p$ and $q$ are odd primes
\item Direct products of some of the groups of the previous type if both
$p$ and $q$ are congruent to 3 modulo 4
\item At least one of the non-abelian groups of order $p^m$, for
$p$ an odd prime and $m \geq 3$
\item Non-abelian groups of order $n$, where $10 \leq n \leq 32$
\item $A_{5}$ and $S_{5}$
\end{itemize}
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}$.
\begin{con}\label{keedcon}
{\rm (Keedwell)} $D_{6}$, $D_{8}$ and $Q_{8}$ are
the only non-abelian non-sequenceable groups.
\end{con}
A milder conjecture is
\begin{con}
{\rm (Anderson)} $Q_{8}$ is the only binary group which does not have a
symmetric sequencing.
\end{con}
\section{Related Concepts}\label{relsub}
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.
\subsection{Terraces}\label{terracesec}
As we noted in Section~\ref{lambda}, terraces
and 2-sequencings are equivalent. We say that a group that has a terrace
is {\em terraced}. Terraces were introduced
by Bailey \cite{rabenum} to prove Theorem~\ref{qcompls}---an
analogue of Theorem~\ref{compls} for quasi-complete latin squares.
An $n \times n$ latin square is said to be {\em 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 {\em 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 {\em quasi-complete}.
Row-quasi-complete latin squares were used by Williams
\cite{will} 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 \cite{BandP89}. 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 $\times$ 1m. A similar experiment is described in
\cite{Smart94}. 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
\cite{Freeman79, Freeman81} and Campbell and Geller \cite{CandG80}.
\begin{thm}\label{qcompls} {\rm \cite{rabenum}}
Let $G$ be a terraced group
with terrace $(a_{1}, a_{2},
\ldots, a_{n})$. Then the square
$(l_{ij}) = ({a_{i}}^{-1}a_{j})$, where
$1 \leq i,j \leq n$, is a
quasi-complete latin square.
\end{thm}
Proof: Similar to the proof of Theorem~\ref{compls}. \qed\
\vspace{4mm}
We would therefore like to know which groups are terraced.
The following result is originally due to
Williams \cite{will} and has
been rediscovered, in various guises, by many authors.
\begin{thm}\label{zterr} {\rm \cite{will}}
For all positive integers $n$, the cyclic group
$\mathbb{Z}_{n}$ is terraced.
\end{thm}
Proof: A terrace for $\mathbb{Z}_n$ is
$(0,1,n-1,2,n-2, \ldots )$, having
$(0,1,{n-2},3,{n-4}, \ldots )$ as its 2-sequencing.
\qed
Note that
when $n$ is even the terrace given in Theorem~\ref{zterr}
is directed (and is the one
given in Example~\ref{cyc2n}).
In fact there are many terraces known for $\mathbb{Z}_{n}$: see
\cite{q2c, lbcd, powerseq, witchhat, secterr, str, will} for
examples.
The following two results are due to Bailey.
\begin{thm}\label{no2seq} {\rm \cite{rabenum}}
$G = {\mathbb{Z}_{2}}^{n}$ is not $2$-sequenceable for $n > 1$.
\end{thm}
Proof: For each $g \in G$, we have $g = -g$.
Thus $G$ is 2-sequenceable if and only if
$G$ is sequenceable, but $G$ is not sequenceable,
by Theorem~\ref{ab}. \qed\
\begin{thm}\label{oddab}{\rm \cite{rabenum}}
Abelian groups of odd order are terraced.
\end{thm}
Proof: Let $\mathbb{Z}_{n_{1}} \times \cdots \times \mathbb{Z}_{n_{l}}$
be an abelian group of odd order.
We use induction on the number of summands.
By Theorem~\ref{zterr}, \
$\mathbb{Z}_{n_{1}}$ is terraced.
Suppose that $\mathbb{Z}_{n_{1}} \times \cdots \times \mathbb{Z}_{n_{k-1}}$ is
terraced with terrace ${\bf a} = (a_{1},a_{2}, \ldots ,a_{m})$
and let ${\bf c} = (c_{1},c_{2}, \ldots ,c_{n_{k}})$ be
the Williams terrace for $\mathbb{Z}_{n_{k}}$.
For $i > 0$ let
\begin{center}
$
\begin{array}{rcll}
\alpha^{(0)} & = & (a_{1},0), (a_{2},0), \ldots, (a_{m},0) & \\
\alpha^{(i)} & = & (a_{m},c_{i}), (a_{m-1},c_{i+1}), (a_{m-2},c_{i}), (a_{m-3},c_{i+1}),
\ldots, (a_{1},c_{i}) & \mbox{if $i$ is odd} \\
\alpha^{(i)} & = & (a_{1},c_{i}), (a_{2},c_{i-1}), (a_{3},c_{i}), (a_{4},c_{i-1}),
\ldots, (a_{m},c_{i}) & \mbox{if $i$ is even}
\end{array}
$
\end{center}
We claim that $(\alpha^{(0)},\alpha^{(1)}, \ldots, \alpha^{(n_{k})})$
is a terrace
for $\mathbb{Z}_{n_{1}} \times \cdots \times \mathbb{Z}_{n_{k}}$:
An allowable set of differences with zeros in the second
co-ordinate occurs within the differences produced by
$\alpha^{(0)}$ as ${\bf 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 $\alpha^{(i)}$ and $\alpha^{(i+1)}$ as ${\bf 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 $\mathbb{Z}_{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 \in \mathbb{Z}_{n_{k}}$). Then $x$ or
$-x$ occurs in the second co-ordinate of the differences
in $\alpha^{(i)}$ and $\alpha^{(i+1)}$ (and nowhere else).
As ${\bf a}$ is a terrace, for each non-zero $y$, where
$y \in \mathbb{Z}_{n_{1}} \times \cdots \times \mathbb{Z}_{n_{k-1}}$,
we get one of the following combinations of differences among the
differences produced by $\alpha^{(i)}$ and $\alpha^{(i+1)}$:
\begin{itemize}
\item two occurrences each of $(y,x)$ and
$(-y,x)$ (and no occurrences of $(y,-x)$ or $(-y,-x)$)
\item one occurrence each of $(y,x)$, $(-y,x)$,
$(y,-x)$ and $(-y,-x)$
\item two occurrences each of $(y,-x)$ and
$(-y,-x)$ (and no occurrences of $(y,x)$ or $(-y,x)$).
\end{itemize}
None of these combinations contravene the definition
of a terrace, so $(\alpha^{(0)},\alpha^{(1)}, \ldots, \alpha^{(n_{k})})$
is a terrace as claimed. The result now follows
by induction on $k$. \qed\
\vspace{4mm}
We can now complete the proof of Theorem~\ref{ab}; that
is, abelian binary groups have directed terraces:
Proof: Let
$A$
be an abelian binary group,
say $A = \mathbb{Z}_{2^{m}} \times B$
where $m > 1$ and $B$ is
an abelian group of odd order.
Then $A / \mathbb{Z}_{2} \cong \mathbb{Z}_{2^{m-1}} \times B$
and Theorem~\ref{symiff2}
says that if $A / \mathbb{Z}_{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$. \qed\
\vspace{4mm}
The next result collects together most of the
known terraced groups; it is due predominantly to
independent work by Anderson and Bailey.
\begin{thm}\label{2seqcond}
The following groups are terraced: \\
(i) all sequenceable groups, \\
(ii) $K \times C_n$ where $K$ is terraced and $n$ is odd, \\
(iii) $G \times C_{2}$ where $G$ is a soluble binary group,
$G \neq C_2$, \\
(iv) all groups of odd order, \\
(v) all groups of order up to $86$ (except
possibly $64$) not ruled out by Theorem~\ref{no2seq}.
\end{thm}
Proof:
(i): Follows immediately from the definitions.
(ii): See \cite{rabenum}.
(iii): The case when $G$ is abelian was proved in \cite{hamil}, the
more general result is in \cite{gc2}.
(iv): See \cite{and:odd2seq}
(v): See \cite{and:bail87}. \qed\
\vspace{4mm}
In Section~\ref{pq} we defined starter-translate
sequencings. This definition applies equally well
to 2-sequencings. A {\em starter-translate $2$-sequencing}
({\em st-$2$-sequencing}) of a group of odd order is a 2-sequencing
$(b_{1},b_{2}, \ldots, b_{n})$ with the property
that both $\{b_{2},b_{4}, \ldots, b_{n-1} \}$ and
$\{b_{3},b_{5}, \ldots, b_{n} \}$ contain precisely
one of $g$ and $g^{-1}$ for each $g \in G$.
Note that with a st-sequencing 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 \cite{and:odd2seq} show
that all groups of odd order have
st-2-sequencings and use this \cite{and:last} to generalise
Theorem~\ref{2seqcond}(ii), showing that
a group $G$ is terraced whenever
$G$ has a normal subgroup $N$ of odd order and $G/N$ is terraced.
\begin{con} {\rm (Bailey)} All finite groups, except
the elementary abelian 2-groups of order at least 4, are terraced.
\end{con}
In 1988 Morgan \cite{morgbpd} generalised the
concept of a terrace as follows. Let
$G$ be a
group of order $n$ and let
${\bf a}$ be a list
$(a_{1},a_{2}, \ldots ,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 ${\bf a}$ let
${\bf b} = ({a_{1}}^{-1}a_{2}, {a_{2}}^{-1}a_{3}, \ldots ,{a_{p-1}}^{-1}a_{p})$.
We say that ${\bf a}$ is an {\em $m$-terrace} of $G$ if
each element of $G$ occurs in ${\bf a}$ either $\lfloor p/n \rfloor$
or $\lfloor p/n \rfloor +1$ times
($\lfloor k \rfloor$ denotes the least integer greater than $k-1$)
and
if ${\bf b}$ consists of
\begin{itemize}
\item $m/2$ occurrences of each non-identity element $g$ which
satisfies $g = g^{-1}$
\item $m$ total occurrences from the pair $ \{ g, g^{-1} \} $
for each element $g$ which does not satisfy $g = g^{-1}$.
\end{itemize}
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 {\em 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 \cite{Wright} 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 quasi-complete
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 {\em 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 {\em 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' \in \{ i-1,i,i+1 \}$, $j' \in \{ 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 ${\bf a}$ be an $m_1$-terrace $(a_{1},a_{2}, \ldots , a_{p})$ and
let ${\bf c}$ be an $m_2$-terrace $(c_{1}, c_{2}, \ldots ,c_{q})$.
Define $R({\bf a},{\bf c})$ to be the
$p \times q$ array with $a_{i}c_{j}$ as the
$(i,j)$-entry and let $gR({\bf a},{\bf c})$
be the array obtained by (left) multiplying
each element of $R({\bf a},{\bf c})$
by $g$.
\begin{thm}\label{morgbig} {\rm \cite{morgbpd}}
Take an abelian group $G$ of order $n$ with
$m_{1}$-terrace ${\bf a} = (a_{1},a_{2}, \ldots , a_{p})$
and $m_{2}$-terrace ${\bf c} = (c_{1}, c_{2}, \ldots ,c_{q})$.
Then the set of arrays
$\{ gR({\bf a},{\bf c}):g \in 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.
\end{thm}
Proof: Our first aim is to show that $R({\bf a},{\bf 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 \leq i \leq p-1$ and $1 \leq j \leq 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({\bf a},{\bf c})$ is a
non-directional balanced neighbour difference array.
It follows that in
$\{ gR({\bf a},{\bf c}):g \in 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({\bf a},{\bf c}): g \in G \}$
is a completely balanced non-directional polycross design.
\qed
\vspace{4mm}
By analogy with Theorems~\ref{compls} and \ref{qcompls},
it would seem more natural in the above theorem to use
$R({\bf a^{-1}},{\bf c})$, where
${\bf a^{-1}} = (a_1^{-1}, a_2^{-1}, \ldots, a_p^{-1})$.
However, we require $G$ to be abelian and in an abelian
group ${\bf a^{-1}}$ is an $m$-terrace if and only if
${\bf a}$ is an $m$-terrace.
Note that if ${\bf a}$ and
${\bf c}$ are 2-terraces then
$\{ gR({\bf a},{\bf c}): g \in G \}$
is a set of $n$ quasi-complete
latin squares of order $n$. If either ${\bf a}$ or
${\bf b}$ is not a 2-terrace then
the arrays in the design will not be latin squares.
\begin{exa}\label{polyc}
Let $G = \mathbb{Z}_{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~\ref{polycr}.
\begin{figure}[htb]
\caption{A completely balanced non-directional
polycross design} \label{polycr}
\begin{center}
$
\begin{array}{rrrrrrrrrrrrrrrrrrrrrrr}
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
\end{array}
$
\end{center}
\end{figure}
\end{exa}
\begin{thm}{\rm \cite{morgbpd}}
The cyclic groups $\mathbb{Z}_{n}$ have $2$- and $4$-terraces
when $n$ is even and $1$-, $2$-, $3$- and $4$-terraces
when $n$ is odd.
\end{thm}
Proof: Suppose $n$ is even, $n = 2k$ say. Then
\[ (0,1,2k-1,2,2k-2, \ldots ,k-1,k+1,k) \]
is a 2-terrace for $\mathbb{Z}_{n}$ (see Theorem~\ref{zterr})
and
\[ (k,k+1,k-1, \ldots , 2k-1,1,0,1,2k-1, \ldots ,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, \ldots ,k,k+1) \]
is a 2-terrace (see Theorem~\ref{zterr}) and
\[ (k+1,k, \ldots ,2k,1,0,1,2k, \ldots ,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.
\qed
\vspace{4mm}
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 \cite{morgbpd,morgpdw,morgtcf,morgssc} extends
this work in several directions, the main two being
to consider directional balance and to condense the
arrays of Theorem~\ref{morgbig} into one array
whilst preserving the balance properties.
\subsection{R-sequencings}\label{rseqs}
A pair of latin squares $(l_{ij})$ and
$(l_{ij}')$ are said to be {\em orthogonal}
if every ordered pair of symbols occurs exactly
once among the $n^{2}$ pairs $(l_{ij},l_{ij}')$.
It is shown in \cite{paige} that the existence of a group of
order $n$ having an R-sequencing (see page~\pageref{def:rseq}
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 \cite{crckeed} 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
\cite[chapter 5]{dk1} 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 \cite{FGandM} have shown:
\begin{thm}\label{abnearseq}
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 \geq 2$, \\
(iv) $C_{2} \times C_{4n}$, where $n \geq 1$, \\
(v) Abelian groups with Sylow $2$-subgroups ${C_{2}}^{n}$, where
$n = 2$ or $n \geq 4$, \\
(vi) Abelian groups with Sylow $2$-subgroups $C_{2} \times C_{2^{n}}$,
where $n$ is odd.
\noqed\
\end{thm}
It is reported in \cite[Chapter 3]{dk2} that Ringel
claims to have shown that $C_{2} \times C_{6n+2}$ is
R-sequenceable for $n \geq 1$.
Since then Headley \cite{headley} has extended these results
to include all abelian groups whose Sylow 2-subgroups
are neither cyclic nor $C_{2} \times C_{4}$ nor
$C_{2} \times C_{2} \times C_{2}$.
The following theorem gives the position for non-abelian groups.
The dicyclic group $Q_{4n}$ is defined by
\[ Q_{4n} = \langle a,b : a^{2n} = e, b^{2} = a^{n}, ab = ba^{-1} \rangle. \]
If $n$ is a power of 2 then $Q_{4n}$ is a generalised quaternion
group.
\begin{thm}
(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.
\end{thm}
Proof:
(i): See \cite{pqnear}.
(ii): See \cite{WandL}.
(iii): The case when $p < q$ and $p$ has 2 as a primitive root
was covered by Keedwell in \cite{pqnear}. Wang and Leonard subsequently
removed the primitive root condition in \cite{WandL}.
(iv): See \cite{db}.
\qed\
\subsection{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 \cite{denesh,rhem} 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 {\em P-groups}, but this
name is now redundant).
In 1983 Keedwell \cite{pqnear} defined super P-groups,
which we now call super sequenceable groups.
A {\em super sequenceable group} is a finite group $G$ in which
each element $g$ of the special coset
is either
\begin{itemize}
\item the last element of some basic directed terrace, or
\item the last element of the partial
product sequence associated with some R-sequencing.
\end{itemize}
The second condition is used only when $g = e$; we
have $g = e$ only when $hG' = G'$.
Keedwell \cite{pqnear} proved the following two theorems:
\begin{thm}\label{supab}
Let $G$ be an abelian group. Then $G$ is a
super sequenceable group if and only if $G$ is
sequenceable or R-sequenceable.
\end{thm}
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~\ref{ab}).
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.
\qed\
\begin{thm}\label{supnonab}
The following groups are super sequenceable groups: \\
(i) Dihedral groups $D_{2n}$ where $n \geq 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$.
\noqed\
\end{thm}
Also, Bedford \cite{db} has shown that both of the non-abelian
groups of order 27 are super sequenceable groups.
\subsection{The Gordon Game}
In 1992 Isbell \cite{gordgame} introduced the idea of {\lq}competitive'
sequencing: the Gordon game $\Gamma(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} \not\in \{ e, x_{1}, \ldots, x_{n} \} \]
and
\[ {x_{n}}^{-1}x_{n+1} \not\in \{ x_{1}, {x_{1}}^{-1}x_{2}, \ldots,
{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}, \ldots, x_{ \mid G \mid -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{array}{rlccrlccrl}
C_{2}: & W & & & C_{3}: & W & & & C_{4}: & W \\
C_{2} \times C_{2}: & B & & & C_{5}: & W & & & C_{6}: & B \\
D_{6}: & W & & & C_{7}: & B & & & C_{8}: & B \\
C_{2} \times C_{4}: & W & && C_{2} \times C_{2} \times C_{2}: & B & & & D_{8}: & B \\
Q_{8}: & W & & & C_{9}: & B & & & C_{3} \times C_{3}: & B \\
C_{10}: & W & & & C_{11}: & B & & & C_{13}: & B
\end{array}$
Isbell tentatively suggests
\begin{con}
Black wins $\Gamma(C_p)$ for
primes $p > 5$.
\end{con}
The reasoning behind this conjecture is (as
Isbell freely admits) shaky. Fix $h \in C_{p} \setminus \{ e \}$. White's
first move is irrelevant as for each $g \in C_{p} \setminus \{ 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 $\Gamma(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.
\subsection{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 \times mq$ array of symbols from $\mathbb{F}_{q} \times \mathbb{Z}_{m}$,
where $\mathbb{F}_{q}$ is the field with $q$ elements.
Write $A_{ij} = (x_{ij},y_{ij})$ for $1 \leq i \leq q$,
$1 \leq j \leq mq$. Then $A$ is a {\em generating array} if
the following conditions hold:
\begin{itemize}
\item each symbol appears once in each row of $A$;
\item if $x_{ij} = x_{i'j}$ then $i = i'$;
\item 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')$.
\end{itemize}
Given a $q \times mq$ generating array, $A$, define $L$ to
be the $mq \times mq$ array (with symbols from
$\mathbb{F}_{q} \times \mathbb{Z}_{m}$) with
\[ L_{kq+i,j} = (x_{ij},y_{ij}+k) \]
where $1 \leq i \leq q$, $1 \leq j \leq mq$ and
$0 \leq k \leq m-1$.
\begin{thm}\label{archrcls}
{\rm \cite{archetal}} $L$, as defined above,
is an $mq \times mq$ row-complete latin square.
\end{thm}
\noqed\
Thus to construct an $mq \times mq$ row-complete latin square we
need only to construct a $q \times mq$ generating array.
\begin{exa}\label{rcls9}
{\rm \cite{archetal}} Let $n = 9$,
$\mathbb{F}_{3} = \{0,1,2 \}$, $\mathbb{Z}_{3} = \{ 0,1,2 \}$.
Then the array $A$ given in Figure~\ref{gen9} is a
generating array. The corresponding
row-complete latin square $L$ is given in
Figure~\ref{rcls99}. It is obtained by using
the map $\phi: \mathbb{F}_{3} \times \mathbb{Z}_{3} \rightarrow
\{1,2, \ldots ,9 \}$, $(x,y) \mapsto 3x+y+1$ as integers.
\begin{figure}[htb]
\begin{center}
\caption{A $3 \times 9$ generating array, $A$.}\label{gen9}
$
\begin{array}{lllllllll}
(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{array}
$
\end{center}
\end{figure}
\begin{figure}[htb]
\begin{center}
\caption{A $9 \times 9$ row-complete latin square, $L$.}\label{rcls99}
$
\begin{array}{lllllllll}
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
\end{array}
$
\end{center}
\end{figure}
\end{exa}
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
\cite{heda} (they are given as column-complete latin squares
there; transposing gives row-complete squares).
Archdeacon, Dinitz, Stinson and Tillson \cite{archetal}
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 \cite[chapter 3]{dk2} 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 \cite{hig1} 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 row-complete latin square of order $mn$. In 1998
he returned to the concept of a generating array to show
\begin{thm}
{\rm \cite{hig2}} Row-complete latin squares
of all odd composite orders exist.
\end{thm}
Proof: We will show how to construct the appropriate
generating arrays. Detailed proofs of their correctness
may be found in \cite{hig2}.
Let $q$ be an odd prime power, $q > 3$. We construct
a $q \times 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 \times 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,
\begin{flushleft}
$(0, 4r, 1, 4r-1, \ldots , r-2, 3r+2, r-1,
3r+1, r,$
\end{flushleft}
\begin{flushright}
$3r-1, r+1, 3r-2, \ldots , 2r-2,
2r+1, 2r-1, 2r, 0)$
\end{flushright}
is the sequence of partial sums of
an R-sequencing of $\mathbb{Z}_{m}$ (see Section~\ref{rseqs}).
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,
\begin{flushleft}
$w = (2r+1, 4r, 2r+2, 4r-1, \ldots , 3r-1, 3r+2,
3r, 3r+1,$
\end{flushleft}
\begin{flushright}
$r+1, r, r+2, r-1, \ldots ,
2r-1, 2, 2r, 1).$
\end{flushright}
Let $s_{j}$ be the $j$th 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 \times q$
{\em component latin squares}, $C^{(k)}$, $0 \leq k \leq m-1$.
The $k$th 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
$l$th column of $C^{(k)}$ in the first co-ordinates of
the $l$th column of $A$ which consists of the symbol $k$
in the second co-ordinate ($1 \leq l \leq q$).
We now define these component squares. Let
$\sigma$ be a primitive element of $\mathbb{F}_{q}$
such that $\sigma \neq 2$.
The field $\mathbb{F}_{q}$ has such a $\sigma$
for $q$ an odd prime power $\geq 5$.
Let $\mathbb{F}_{q} = \{ f_{1},f_{2}, \ldots f_{q} \}$. Then
\[ {C^{(k)}}_{ij} = \left\{ \begin{array}{ll}
a_{k}f_{i}+b_{k}{\sigma^{j}}+c_{k} & \mbox{if $1 \leq j < q$} \\
a_{k}f_{i}+c_{k} & \mbox{if $j=q$}
\end{array}
\right. \]
where $a_{0} = \cdots = a_{2r} = 1$,
$a_{2r+1} = \cdots = a_{4r} = -1$,
$b_{0}=1$, $b_{1} = 1 - \sigma$,
$b_{2} = \cdots = b_{r} = 1$,
$b_{r+1} = \cdots = b_{2r} = -1$,
$b_{2r+1} = \cdots = b_{3r} = 1/2 - 1/\sigma$,
$b_{3r+1} = \cdots = b_{4r} = 1/2$,
$c_{0} = -\sigma/2$ and
$c_{1} = \cdots = 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,
\begin{flushleft}
$(0, 4r+2, 1, 4r+1, \ldots , r-2,3r+4, r-1, 3r+3,
r,$
\end{flushleft}
\begin{flushright}
$3r+1, r+1, 3r, r+2, 3r-1, \ldots ,
2r-1, 2r+2, 2r, 2r+1, 0)$
\end{flushright}
is the sequence of partial sums
of an R-sequencing in $\mathbb{Z}_{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,
\begin{flushleft}
$w = (2r+1, 1, 2r, 2, \ldots ,
r+3, r-1, r+2, r, r+1,$
\end{flushleft}
\begin{flushright}
$3r+2, 3r+1, 3r+3, 3r,
3r+4, \ldots , 4r, 2r+3, 4r+1, 2r+2, 4r+2)$.
\end{flushright}
Again, let $s_{j}$ be the $j$th 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 $\sigma$ be a primitive
element of $\mathbb{F}_{q}$ such that $\sigma \neq 2$ and $3\sigma \neq 2$.
The field $\mathbb{F}_q$ has such a $\sigma$ for $q$ an odd
prime power power $\geq 5$.
Let $\mathbb{F}_{q} = \{ f_{1},f_{2}, \ldots ,f_{q} \}$. Then
\[ {C^{(k)}}_{ij} = \left\{ \begin{array}{ll}
a_{k}f_{i}+b_{k}{\sigma^{j}}+c_{k} & \mbox{if $1 \leq j < q$} \\
a_{k}f_{i}+c_{k} & \mbox{if $j=q$}
\end{array}
\right. \]
where $a_{0} = \cdots = a_{2r} = 1$,
$a_{2r+1} = \cdots = a_{4r+1} = -1$,
$a_{4r+2} = 1$,
$b_{0} = \cdots = b_{r} = 1$,
$b_{r+1} = \cdots = b_{2r} = -1$,
$b_{2r+1} = 1/2 - 1/\sigma$,
$b_{2r+2} = \cdots = b_{3r+1} = 1$,
$b_{3r+2} = \cdots = b_{4r+1} = -1$,
$c_{0} = -\sigma/2$ and
$c_{1} = \cdots = 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.
\qed
\vspace{4mm}
It is known that there are no $n \times n$ row-complete
latin squares for $n = 3,5$ or $7$, but the question for other odd primes
remains open.
\section{Index Of Notation}
\begin{tabular}{rcp{5in}}
${\mathbb Z_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 \\
${\mathbb F}_q$ & : & The field with $q$ elements ($q$ must be a
prime power) \\
$\mathrm{PSL}(2,q)$ & : & The projective special linear group of
$2 \times 2$ matrices over $\mathbb{F}_q$ \\
$\mathrm{PGL}(2,q)$ & : & The projective general linear group of
$2 \times 2$ matrices over ${\mathbb F}_q$ \\
$\mathrm{P}\Gamma\mathrm{L}(2,q)$ & : & The automorphism group of
$\mathrm{PSL}(2,q)$ \\
$G'$ & : & The derived subgroup of a group $G$ \\
$O(G)$ & : & The largest normal subgroup of odd order of
a group $G$ \\
$\Lambda(G)$ & : & The normal subgroup of order 2 of a
binary group $G$ \\
$\lfloor k \rfloor$ & : & The smallest integer greater than $k-1$
\end{tabular}
\section{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~\ref{lambda}
\begin{thebibliography}{99}
\bibitem{and:seqstart} B. A. Anderson, Sequencings and starters,
{\em Pacific J. Math.} {\bf 64} (1976) 17--24.
\bibitem{and:loseqs} B. A. Anderson, A fast method for sequencing
low order non-abelian groups, {\em Ann. Discrete Math.}
{\bf 34} (1987) 27--42.
\bibitem{dic1} B. A. Anderson, Sequencings of dicyclic
groups, {\em Ars Combin.} {\bf 23} (1987) 131--142.
\bibitem{nonab32} B. A. Anderson, $S_{5}$, $A_{5}$ and
all non-abelian groups of order 32 are sequenceable,
{\em Congr. Numer.} {\bf 58} (1987) 53--68.
\bibitem{dic2} B. A. Anderson, Sequencings of dicyclic
groups II, {\em J. Combin. Math. Combin. Comp.} {\bf 3}
(1988) 5--27.
\bibitem{dic12} B. A. Anderson, All dicyclic groups
of order at least 12 have symmetric sequencings,
{\em Contemp. Math.} {\bf 111} (1990) 5--21.
\bibitem{q2c} B. A. Anderson, Some quasi-2-complete latin squares,
{\em Congr. Numer.} {\bf 70} (1990) 65--79.
\bibitem{prod2seq} B. A. Anderson, A product theorem
for 2-sequencings, {\em Discrete Math.} {\bf 87} (1991) 221--236.
\bibitem{and:bail87} B. A. Anderson, Bailey's conjecture
holds through 87 except possibly for 64, {\em J. Combin.
Math. Combin. Comp.} {\bf 12} (1992) 187--195.
\bibitem{and:odd2seq} B. A. Anderson and E. C. Ihrig,
All groups of odd order have starter-translate
2-sequencings, {\em Australas.
J. Combin.} {\bf 6} (1992) 135--146.
\bibitem{and:last} 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,
{\em J. Combin. Des.} {\bf 1} (1993) 3--14.
\bibitem{symnon} B. A. Anderson and E. C. Ihrig,
Symmetric sequencings of non-solvable groups,
{\em Congr. Numer.} {\bf 93} (1993) 73--82.
\bibitem{hamil} B. A. Anderson and P. A. Leonard,
Symmetric sequencings of finite Hamiltonian groups
with a unique element of order 2, {\em Congr. Numer.}
{\bf 65} (1988) 147--158.
\bibitem{bbt} I. Anderson and R. A. Bailey, Completeness
properties of conjugates of latin squares based on groups,
and an application to bipartite tournaments, {\em Bull.
Inst. Combin. Appl.} {\bf 21} (1997), 95--99.
\bibitem{lbcd} I. Anderson and D. A. Preece, Locally
balanced change-over designs, to appear in {\em Util. Math.}
\bibitem{powerseq} I. Anderson and D. A. Preece, Power
sequence terraces for $\mathbb{Z}_{n}$, where $n$ is
a prime power, submitted to {\em Discrete Math.}
\bibitem{archetal} D. S. Archdeacon, J. H. Dinitz,
D. R. Stinson and T. W. Tillson, Some new row-complete
latin squares, {\em J. Combin. Theory Ser. A} {\bf 29} (1980)
395--398.
\bibitem{bc}
L.~Babai and P.~J.~Cameron,
Automorphisms and enumeration of switching classes of tournaments,
\textit{Electronic J. Combinatorics} \textbf{7} (2000), \#R38.
\bibitem{rabenum} R. A. Bailey, Quasi-complete latin
squares: construction and randomization,
{\em J. R. Stat. Soc. Ser. B Stat. Methodol.} {\bf 46}
(1984) 323--334.
\bibitem{rabmaodap} R. A. Bailey, M. A. Ollis and D. A. Preece,
Round-dance neighbour designs from terraces,
{\em Discrete Math.}, to appear.
\bibitem{BandP89} R. A. Bailey and R. W. Payne, Experimental
design: statistical research and its application. In
{\em 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.
\bibitem{rabandp} R. A. Bailey and C. E. Praeger, Directed
terraces for direct product groups, {\em Ars Combin.} {\bf 25A}
(1988) 73--76.
\bibitem{db} 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).
\bibitem{dbmaormw} D. Bedford, M. A. Ollis and R. M. Whitaker,
On bipartite tournaments balanced with respect to carry-over
effects for both teams, {\em Discrete Math} {\bf 231} (2001) 81--87.
\bibitem{bender} H. Bender, Finite groups with dihedral
2-Sylow subgroups, {\em J. Algebra} {\bf 70} (1981) 216--228.
\bibitem{burn}
W.~Burnside,
\textit{Theory of Groups of Finite Order},
Dover Publications (reprint), New York, 1955.
\bibitem{CandG80} G. Campbell and S. Geller, Balanced latin squares,
{\em Purdue University Department of Statistics Mimeoseries} {\bf 80-26}
(1980).
\bibitem{CandM} S. D. Cohen and G. L. Mullen, Primitive elements
in finite fields and Costas arrays, {\em Appl. Algebra Engr.
Comm. Comput.} {\bf 2} (1991) 45--53.
\bibitem{cox}
H.~S.~M.~Coxeter,
\textit{Regular Complex Polytopes},
Cambridge University Press, Cambridge, 1974.
\bibitem{denesh} J. D\'{e}nes and P. Hermann, On the product
of all the elements of a finite group, {\em Ann. Discrete Math.}
{\bf 15} (1982) 105--109.
\bibitem{dk1} J. D\'{e}nes and A. D. Keedwell, {\em Latin Squares and their
Applications,} Akad\'{e}miai Kiad\'{o}, Budapest/English Universities Press,
London/Academic Press (1974).
\bibitem{dk2} J. D\'{e}nes and A. D. Keedwell, {\em Latin Squares:
New Developments in the Theory and Applications}, North-Holland
(1991).
\bibitem{dt} J. D\'{e}nes and E. T\H{o}r\H{o}k, Groups
and Graphs, {\em Combinatorial Theory and its Applications}, North
Holland (1970) 257--289.
\bibitem{Dickson} L. E. Dickson, On finite algebras, {\em Nachrichten
der K\"{o}niglichen Gesellschaft der Wissenschaften in
G\"{o}ttingen (Math.-Phys. Klasse)} (1905) 358--393.
\bibitem{Freeman79} G. H. Freeman, Some two-dimensional designs balanced
for nearest neighbours, {\em J. R. Statist. Soc. B} {\bf 41} (1979) 88--95.
\bibitem{Freeman81} G. H. Freeman, Further results on quasi-complete
latin squares, {\em J. R. Statist. Soc. B} {\bf 43} (1981) 314--320.
\bibitem{fried} R. Friedlander, Sequences in groups with
distinct partial products, {\em Aequationes Math.} {\bf 14}
(1976) 59--66.
\bibitem{FGandM} R. J. Friedlander, B. Gordon and M. D. Miller,
On a group sequencing problem of Ringel, {\em Congr. Numer.}
{\bf 21} (1978) 307--321.
\bibitem{GandH85} S. W. Golomb and H. Taylor, Tuscan squares---a
new family of combinatorial designs, {\em Ars Combin.} {\bf 20B}
(1985) 115--132.
\bibitem{gord} B. Gordon, Sequences in groups with distinct
partial products, {\em Pacific J. Math.} {\bf 11} (1961)
1309--1313.
\bibitem{goren} D. Gorenstein and J. H. Walter, The
characterization of finite groups with dihedral
Sylow 2-subgroups, I, II and III, {\em J. Algebra} {\bf 2}
(1965) 85--151, 218--270, 334--393.
\bibitem{headley} P. Headley, R-sequenceability and
R*-sequenceability of abelian 2-groups, {\em Discrete Math.}
{\bf 131} (1994) 345--350.
\bibitem{heda} A. Hedayat and K. Afsarinejad, Repeated
measurements designs II, {\em Ann. Statist.} {\bf 6}
(1978) 619--628.
\bibitem{hig1} J. Higham, A product theorem for
row-complete latin squares, {\em J. Combin. Des.}
{\bf 5} (1997) 311--318.
\bibitem{hig2} J. Higham, Row-complete latin squares
of every composite order exist, {\em J. Combin. Des.}
{\bf 6} (1998) 63--77.
\bibitem{hogh} G. B. Hoghton and A. D. Keedwell, On the
sequenceability of dihedral groups, {\em Ann.
Discrete Math.} {\bf 15} (1982) 253--258.
\bibitem{IDandO} P. D. Isaac, A. M. Dean and T. Ostrom, Sequentially
counterbalanced latin squares, {\em Statistics and Applications}
{\bf 3} (2001) 25--46.
\bibitem{isb} J. Isbell, Sequencing certain dihedral groups,
{\em Discrete Math.} {\bf 85} (1990) 323--328.
\bibitem{gordgame} J. Isbell, The Gordon game of a finite group,
{\em Amer. Math. Monthly} {\bf 99} (1992) 567--569.
\bibitem{nonab27} A. D. Keedwell, Some problems concerning
complete latin squares, {\em L.M.S. Lecture Notes} {\bf 13}: {\em
Combinatorics: Proc. of the British Comb. Conf. Aberystwyth 1973
(Eds: T.~P.~McDonough and V.~C.~Mavron)}
(1974) 89--96.
\bibitem{survey} A. D. Keedwell, Sequenceable groups: a survey,
{\em L.M.S. Lecture Notes} {\bf 49}: {\em 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.
\bibitem{keedpq} A. D. Keedwell, On the sequenceability of
non-abelian groups of order $pq$, {\em Discrete Math.} {\bf 37}
(1981) 203--216.
\bibitem{pqnear} A. D. Keedwell, On the $R$-sequenceability and
$R_{h}$-sequenceability of groups, {\em Ann. Discrete Math.}
{\bf 18} (1983) 535--548.
\bibitem{crckeed} A. D. Keedwell, Complete mappings and
sequencings of finite groups, {\em The CRC Handbook of
Combinatorial Designs. (Eds. C.~J.~Colbourn and J.~H.~Dinitz)}
CRC press (1996) 246--253.
\bibitem{li} P. Li, Sequencing the dihedral groups $D_{4k}$,
{\em Discrete Math.} {\bf 175} (1997) 271--276.
\bibitem{lucas} E. Lucas, {\em R\'{e}cr\'{e}ations Math\'{e}matiques,
T\^{o}me II}. Albert Blanchard, Paris, 1892, reprinted 1975.
\bibitem{mendel} N. S. Mendelsohn, Hamiltonian decomposition
of the complete directed $n$-graph, {\em Proc. Colloq. Tihany: 1966},
Academic Press (1968) 237--241.
\bibitem{morgbpd} J. P. Morgan, Balanced polycross designs,
{\em J. R. Stat. Soc. Ser. B Stat. Methodol.} {\bf 50} (1988) 93--104.
\bibitem{morgpdw} J. P. Morgan, Polycross designs with
complete neighbour balance, {\em Euphytica} {\bf 39}
(1988) 59--63.
\bibitem{morgtcf} J. P. Morgan, Terrace constructions for
bordered, two-dimensional neighbour designs, {\em Ars Combin.}
{\bf 26} (1988) 123--140.
\bibitem{morgssc} J. P. Morgan, Some series constructions
for two-dimensional neighbor designs, {\em J. Statist. Plann.
Inference} {\bf 24} (1990) 37--54.
\bibitem{nilrat} C. K. Nilrat and C. E. Praeger, Complete
Latin squares: terraces for groups, {\em Ars Combin.} {\bf 25}
(1988) 17--29.
\bibitem{witchhat} M. A. Ollis, Protection against premature
termination of experiments based on Williams squares with
circular structure, to appear in {\em Util. Math.}
\bibitem{gc2} M. A. Ollis, Terraces for $G \times C_2$, where
$G$ is a soluble group with a single involution, in preparation.
\bibitem{secterr} M. A. Ollis and D. A. Preece, Sectionable
terraces and the (generalised) Oberwolfach problem,
{\em Discrete Math.}, to appear.
\bibitem{paige} L. J. Paige, Complete mappings of finite
groups, {\em Pacific J. Math.} {\bf 1} (1951) 111--116.
\bibitem{pass}
D.~S.~Passman, {\em Permutation Groups},
Benjamin, New York, 1968.
\bibitem{rhem} A. R. Rhemtulla, On a problem of L. Fuchs,
{\em Studia Sci. Math. Hungar.} {\bf 4} (1969) 195--200.
\bibitem{rotman} J. J. Rotman, {\em An Introduction to
the Theory of Groups (4th Edition),} Springer-Verlag (1994).
\bibitem{Smart94} 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,
{\em Sitona lineatus} L., {\em Crop Protection} {\bf 13}
(1994) 127--136.
\bibitem{str} D. J. Street, Some repeated measurements designs,
{\em Comm. Statist. Theory Methods} {\bf 17(1)},
(1988) 87--104.
\bibitem{gptables} A. D. Thomas and G. V. Wood, {\em Group Tables,}
Shiva Publishing (1980).
\bibitem{WangDiss} ChengDe Wang, Sequenceability, R-sequenceability,
and harmoniousness of finite groups, Dissertation, Arizona State
University, August 2000.
\bibitem{WangDM} ChengDe Wang, Complete latin squares of order
$p^n$ exist for odd primes $p$ and $n>2$, {\em Discrete Math.}, to
appear.
\bibitem{WandL} ChengDe Wang and P. A. Leonard, More on sequences in groups,
{\em Australas. J. Combin.} {\bf 21} (2000) 187--196.
\bibitem{nonab39} L. L. Wang, A test for the sequencing of a class
of finite groups with two generators, {\em Amer. Math. Soc. Notices}
{\bf 20} (1973) 73T--A275.
\bibitem{will} E. J. Williams, Experimental designs balanced for the estimation
of residual effects of treatments, {\em Aust. J. Sci. Res. A}
{\bf 2} (1949) 149--168.
\bibitem{Wright} C. E. Wright, A systematic polycross design,
{\em Res. Exp. Rec. Min. Agric. N.I.} {\bf 11:1} (1961) 7--8.
\end{thebibliography}
\end{document}