\documentclass[12pt]{article}

\usepackage{e-jc,amsfonts}
\specs{P34}{20(2)}{2013}

\usepackage{latexsym}
\usepackage{subfigure}
\usepackage{amsmath}
\bibliographystyle{plain}
\usepackage{fullpage}

%environments
\newtheorem{thm}{Theorem}
\newtheorem{exa}{Example}
\newtheorem{lem}{Lemma}
\newtheorem{cor}{Corollary}
\newtheorem{prop}{Proposition}
\newtheorem{conj}{Conjecture}


%notation
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\ub}{\underbrace}
\newcommand{\ep}{\mathop{\rm EP}\nolimits}
\newcommand{\rowrev}{\mathop{\rm rowrev}\nolimits}
\newcommand{\colrev}{\mathop{\rm colrev}\nolimits}
\newcommand{\rot}{\mathop{\rm rot}\nolimits}
\newcommand{\qed}{\unskip\protect\nolinebreak\mbox{\quad$\Box$}\vspace{3mm}}
\newcommand{\subsoma}{\mathop{\rm subSOMA}\nolimits}

%\setlength{\parindent}{0in}
%\setlength{\parskip}{3mm}



\begin{document}



\title{An Extension Theorem for Terraces}

\author{M.~A.~Ollis\footnote{Corresponding author, email address: \texttt{matt@marlboro.edu.}} \  and Devin T.~Willmott \\
              {\small Marlboro College, P.O.~Box A, Marlboro} \\[-0.8ex]    
              {\small Vermont 05344, USA}  
}
              
\date{\dateline{Mar 23, 2012}{May 10, 2013}{May 24, 2013}}

\maketitle

\begin{abstract}
We generalise an extension theorem for terraces for abelian groups to apply to non-abelian groups with a central subgroup isomorphic to the Klein 4-group~$V$.  We also give terraces for three of the non-abelian groups of order a multiple of~8 that have a cyclic subgroup of index~2 that may be used in the extension theorem.  These results imply the existence of terraces for many groups that were not previously known to be terraced, including~27 non-abelian groups of order~64 and all groups of the form $V^s \times D_{8t}$ for all $s$ and all $t > 1$ where $D_{8t}$ is the dihedral group of order~$8t$.  

\medskip

AMS 2010 Subject Classification. Primary: 20D60. Secondary: 05B99.

Keywords: 2-sequencing, Bailey's conjecture, extendable terrace, rotational terrace, terrace.
\end{abstract}


\section{Introduction}
Let $G$ be a group of order $n$ and let ${\bf a} = (a_1, a_2, \ldots, a_n)$ be an arrangement of all of the elements of $G$.  Define ${\bf b} = (b_1, b_2, \ldots, b_{n-1})$ by $b_i = a_i^{-1}a_{i+1}$.  If each involution of $G$ appears once in ${\bf b}$ and there are two appearances from each set $\{ g, g^{-1} : g^2 \neq e \}$ in ${\bf b}$  then ${\bf a}$ is a {\em terrace} for $G$ and ${\bf b}$ is its associated {\em 2-sequencing}.  If a group has a terrace then it is {\em terraced}.  Left-multiplying each element of a terrace by any element of the group produces another terrace for the group; choosing $a_1^{-1}$ gives a terrace with the identity, $e$, as the first element---such a terrace is called {\em basic}.

Terraces for cyclic groups were implicitly used by Williams in \cite{Williams49} and the concept was formally defined and extended to arbitrary groups by Bailey \cite{Bailey84}.  They were originally of interest because the Cayley table of a group may be presented as a quasi-complete Latin square if and only if the group is terraced \cite{Bailey84} but have since been used for other applications and studied as objects of interest in their own right.  The purpose of this paper is to move closer to a proof of Bailey's Conjecture:

\begin{conj} {\rm \cite{Bailey84}}  
All groups, except the non-cyclic elementary abelian 2-groups, are terraced.
\end{conj}

It is known that the non-cyclic elementary abelian 2-groups are not terraced \cite{Bailey84}.

\begin{exa}\label{ex:lww}
Let $\Z_n$ be the additively-written cyclic group of order $n$. 
The Lucas-Walecki-Williams terrace (so-called because it was implicitly used by Lucas and Walecki \cite{Lucas92}  for even~$n$ and by Williams \cite{Williams49} for all $n$) for $\Z_n$ is $( 0, 1, n-1, 2, n-2, \ldots)$ and has associated 2-sequencing $(1,n-2,3,n-4, \ldots)$.
\end{exa}

There have been two main lines of attack on Bailey's Conjecture.  First, one may directly construct terraces for a particular family of groups.  Second, one can produce theorems that build a terrace for a group out of terraces for smaller groups.  The most powerful example of the second approach is the following result:

\begin{thm}\label{th:crcr} {\rm \cite{AandI92, AandI93}}
Let $G$ be a group with normal subgroup $N$.  If $N$ has odd index and is terraced, then $G$ is terraced.  If $N$ has odd order and $G/N$ is terraced then $G$ is terraced.
\end{thm}

In \cite{Ollis05} a theorem that constructed a terrace for an abelian group $G$ that has a subgroup of order~4 and a particular type of terrace for the quotient group was presented.  This theorem is not fully correct in the case when the subgroup of order~4 is cyclic; see \cite{OW1} in which the error is corrected and it is shown that all of the groups claimed to be terraced are indeed terraced.  In the next section we present a more general version of the correct case (when the subgroup is isomorphic to~$V$, the Klein 4-group) that applies to many non-abelian groups. 

The extension result in the next section allows us to find terraces for a considerable array of previously unterraced groups.  As input the theorem requires terraces with particular properties; some such terraces are catalogued in Section~\ref{sec:cat}.




\section{The extension theorem}\label{sec:ext}

We first define the properties we require of a terrace to be used in the theorem.  Let $K$ be a group of order $m \geq 6$ and let ${\bf a} = (a_1, a_2, \ldots, a_m)$ be a basic terrace for $K$.  If $a_m = a_2^2$ and $a_{j-1}a_{j+1} = a_j = a_{j+1}a_{j-1}$ for some $5 \leq j < m$ then ${\bf a}$ is {\em extendable}.

An important intermediary object is an R-terrace, or rotational terrace.  Following the convention of earlier papers we write circular lists in square brackets and consider the subscripts to be calculated modulo the length of the list.
Let $K$ be a group of order $m$ and let ${\bf a} = [ a_1, a_2, \ldots, a_{m-1} ]$  be a circular arrangement of the non-identity elements of $K$.  Define ${\bf b} = [b_1, b_2, \ldots, b_{m-1}]$ by $b_i = a_i^{-1} a_{i+1}$ for $1 
\leq i \leq m-1$.  If ${\bf b}$ contains exactly one occurrence of each involution of $K$ and exactly two occurrences from each set $\{ k, k^{-1} : k^2 \neq e \}$ then ${\bf a}$ is a {\em rotational terrace} or {\em R-terrace} for $K$ and ${\bf b}$ is the associated {\em rotational 2-sequencing} or {\em R-2-sequencing} of $K$.   If there are no repeats among the elements of ${\bf b}$ then the R-terrace is {\em directed} and the R-2-sequencing is an {\em R-sequencing}.
Further, if $a_1 = a_{m-1} a_{2} = a_2a_{m-1}$  then ${\bf a}$ is a {\em standard R$^*$-terrace} for $K$ and  if $b_r  = a_{r+1}^{-1}$ for some $r$ then $r$ is a {\em right match-point} of ${\bf b}$.   Note that a standard R$^*$-terrace cannot have an R-2-sequencing with~1 as a right match-point.

Standard R$^*$-terraces whose R-2-sequencings have particular right match-points and extendable terraces are equivalent: The circular list $[ a_1, a_2, \ldots, a_{m-1} ]$ is a standard R$^*$-terrace whose R-2-sequencing has a right match-point $r$ for some $2 \leq r \leq m-3$ if and only if $$(e, a_{r+1}, a_{r+2}, \ldots, a_{m-1}, a_1, a_2, \ldots, a_r)$$ is an extendable terrace.

The following lemma restricts which groups may have an extendable terrace.
\begin{lem} {\rm \cite{Ollis05}}\label{lem:2odd}
If the order of $G$ is congruent to $2$ modulo $4$ then $G$ does not have a rotational terrace.
\end{lem}


We can now prove our main result.  The {\em Klein 4-group} is the non-cyclic group of order~4 and a subgroup is {\em central} if each of its elements commutes with every element of the group (that is, it is contained in the centre of the group).

\begin{thm}\label{th:big}
Let $G$ be a group with a central subgroup $V$ of index~$m \geq 7$, where $V$ is isomorphic to the Klein 4-group.  Suppose $G/V$ has a standard R$^*$-terrace $[K_1, K_2, \ldots, K_{m-1}]$ whose R-2-sequencing has a match-point $r$ for some $2 \leq r \leq m-3$ and such that there is a pair of elements, one in $K_2$ and one in $K_{m-1}$, that commute. Then $G$ has an extendable terrace.
\end{thm}

Proof.
Choose coset representatives $k_i$,
for $1 \leq i \leq m-1$, such that $k_i \in K_i$ and that both $k_{m-1}k_2 = k_1 = k_2k_{m-1}$ and $k_{r}^{-1} k_{r+1} = k_{r+1}^{-1}$.  These two criteria potentially interact if $r=2$. In this case, choose any $k_3 \in K_3$, set $k_2= k_3^2$ and then there is a $k_{m-1} \in K_{m-1}$ that commutes with $k_2$: if $\ell_2 \in K_2$ and $\ell_{m-1} \in K_{m-1}$ are the commuting elements we know to exist then there is a $v_0 \in V$ with $k_2 = v_0\ell_2$ and this commutes with $\ell_{m-1}$, which we may set to be $k_{m-1}$, by the centrality of $V$.



Note that each element of $G$ is uniquely expressible in the form $vk$ for $v \in V$ and $k \in \{e, k_1, k_2, \ldots, k_{m-1} \}$.  

We build the standard R$^*$-terrace by showing the lists of the $v$ components and $k$ components separately.   Let $V = \{e, v_1, v_2, v_3 \}$, then $[v_1, v_2, v_3]$ is an R-terrace for $V$ (that is, any circular list of the non-identity elements of $V$ is an R-terrace).  We list the $v$ components as the rows of a $4 \times m$ matrix.  Let $(v_1,v_2,v_3)_{t-1}$ denote $t-1$ repetitions of the sequence $(v_1,v_2,v_3)$, and similarly for other subscripted sequences.  There are three slightly different matrices for the $v$ components as $m$ varies modulo 3.

Case 1: $m = 3t$ for $t\geq3$.  Take 
\[ \left[ 
\begin{array}{ccccccc}
e   & e      & \ldots       & &  e    & v_2       & v_1   \\
v_3 & (v_1,v_2,v_3)_{t-2} & v_1 & v_3 & v_3 & v_2 & v_1 \\
v_3 & v_2 & (v_3,v_1,v_2)_{t-2} & v_3 & v_2 & v_1 & v_3 \\
v_2 & v_1 & (v_2,v_3,v_1)_{t-2} & v_2 & v_1 & e \\
\end{array}
\right]
\]  
to be the $v$ component matrix. \\

Case 2: $m = 3t+1$ for $t \geq 2$.  Take
\[ \left[ 
\begin{array}{ccccc}
e   & e      & \ldots                             & v_2       & v_1   \\
v_3 & (v_2,v_1,v_3)_{t-1} & v_3 & v_2 & v_1 \\
v_3 & v_2 & (v_1,v_3,v_2)_{t-1} & v_1 & v_3 \\
v_2 & v_1 & (v_3,v_2,v_1)_{t-1} & e \\
\end{array}
\right]
\]
to be the $v$ component matrix.  \\

Case 3: $m = 3t+2$ for $t \geq 2$.  Take
\[ \left[ 
\begin{array}{cccccc}
e   & e      & \ldots              & e               & v_2       & v_1   \\
v_3 & (v_2,v_1,v_3)_{t-1} & v_2 & v_3 & v_2 & v_1 \\
v_3 & v_2 & (v_1,v_3,v_2)_{t-1} & v_1 & v_1 & v_3 \\
v_2 & v_1 & (v_3,v_2,v_1)_{t-1} & v_3 & e \\
\end{array}
\right]
\]
to be the $h$ component matrix.

For each of the above cases the $k$ component matrix is 
\[ \left[
\begin{array}{cccccc}
k_1     & k_2  & \ldots &         & k_{m-1}     & e   \\
k_2     & k_3  & \ldots & k_{m-1} & k_1         & k_1 \\
k_1     & k_2  & \ldots &         & k_{m-1}     & e   \\
e       & k_2  & k_3    & \ldots  & k_{m-1}     &     \\
\end{array}
\right]
\]

As $V$ is central in $G$ and $k_{m-1}k_2 = k_1 = k_2k_{m-1}$ we get the following matrix of quotients in the $k$ component:
$$ 
\left[
%\setlength{\arraycolsep}{1.15mm}
\begin{array}{cccccccc}
k_1^{-1}k_2 & k_2^{-1}k_3 & \ldots & \ldots & k_{m-2}^{-1}k_{m-1} & k_1^{-1}k_2   & k_{m-1}^{-1}k_1  \\
k_2^{-1}k_3 & k_3^{-1}k_4 & \ldots & k_{m-2}^{-1}k_{m-1} & k_{m-1}^{-1}k_1 & e       & e  \\
k_1^{-1}k_2 & k_2^{-1}k_3 &    \ldots    & \ldots    & k_{m-2}^{-1}k_{m-1}     & k_1^{-1}k_2 & e\\
k_{m-1}^{-1}k_1 & k_2^{-1}k_3 & k_3^{-1}k_4 & \ldots & k_{m-2}^{-1}k_{m-1} & k_{m-1}^{-1}k_1 &\\
\end{array}
\right]
$$
Each repeated sequence in the $v$ component matrix is a directed R-terrace and so when the quotient matrices are combined we get a sequence that obeys the conditions of an R-2-sequencing.

Further, as the first two entries and the last entry of every $v$ component matrix is $e$, it follows from our choices of $k_1$, $k_2$, and $k_{m-1}$ that the R-terrace is a standard R$^*$-terrace.  As the first $m-2$ entries of every $v$ component matrix are all $e$, our choices of $k_r$ and $k_{r+1}$ give us the match-point we require in position $r$ of the R-2-sequencing.
\qed


The awkward condition in Theorem~\ref{th:big} regarding commuting elements in commuting cosets is automatically satisfied in the cases where we have appropriate direct products or abelian (sub)groups.  Hence an immediate consequence of the theorem is:

\begin{cor}\label{cor:easyversion}
Let $A$ be an abelian 2-group that has a normal series with all factors isomorphic to the Klein 4-group and let $K$ be a group with an extendable terrace.  Then $A \times K$ has an extendable terrace.  In particular, $\Z_2^{2s} \times K$ has an extendable terrace for all $s$.
\end{cor}



Our goal now is to construct extendable terraces for as many groups as possible.


\section{Extendable terraces}\label{sec:cat}

The following results for abelian groups are established in \cite{Ollis05, Ollis12, OW1}:
\begin{itemize}
\item The cyclic group $\Z_n$ has an extendable terrace if and only if $n \geq 7$ and $n$ is not twice an odd number.
\item All abelian 2-groups of order at least~8, except the elementary abelian 2-groups, have an extendable terrace.
\item Let $p$ be an odd prime.  The group $\Z_2^{2t} \times \Z_p$ has an extendable terrace unless $t=0$ and $p \leq 5$. 
\item The groups $\Z_2^{2t+1} \times \Z_3$ and $\Z_2^{2t+1} \times \Z_5$ have an extendable terrace for all $t \geq 1$.
\end{itemize}

Other than the unterraceable elementary abelian 2-groups, these results and Theorem~\ref{th:crcr} now give terraces for all abelian groups except for those of order coprime to~15 with elementary abelian Sylow 2-subgroup of order~$2^{2t+1}$ for $t \geq1$  \cite{Ollis05, Ollis12, OW1}.  When $t \geq  2$ it is known that these groups are terraced \cite{Ollis12}.

In this section we present extendable terraces for each of three non-abelian groups of order $8t$ with $t \geq 2$: the dihedral group $D_{8t}$, the semidihedral group $S_{8t}$ and a third group that also has a cyclic subgroup of index~2 but does not appear to have a common name in the literature---we denote it $M_{8t}$ following Gorenstein's use,   reported in \cite{HLW}, of the letter $M$ (but with a different subscript convention) for this group when it has order a power of~2.  For even $t$, other than finitely many small cases, the terraces given for $S_{8t}$ and $M_{8t}$ are the first known.  Here are presentations for these groups:
\begin{eqnarray*}
D_{8t} &=& \langle u,v : u^{4t} = e = v^2,  \ vu = u^{4t-1}v \rangle \\
S_{8t} &=& \langle u,v : u^{4t} = e = v^2, \ vu = u^{2t-1}v \rangle \\
M_{8t} &=& \langle u,v : u^{4t} = e= v^2, \ vu = u^{2t+1}v \rangle
\end{eqnarray*}

Before constructing the desired terraces we introduce a related concept and prove a lemma that is crucial to the construction.

An arrangement ${\bf g} = (g_1, g_2, \ldots, g_n)$ of the integers $\{0, 1, \ldots, n-1 \}$ is a {\em graceful sequence of length $n$} if each element of the set $\{1,2, \ldots, n-1\}$ can be written $|{g_{i+1} - g_i}|$ for some~$i$.  This is equivalent to the notion of a graceful labelling of a path in graph theory \cite{Gallian}.  If ${\bf g}$ is a graceful sequence then so are its {\em reverse} $(g_n, g_{n-1}, \ldots, g_1)$ and its {\em complement} $((n - 1) - g_1, (n - 1) - g_2, \ldots, (n - 1) - g_n)$.  Considered to be a sequence in $\Z_n$ rather than $\Z$ a graceful sequence is a terrace, called a {\em graceful terrace}.

\begin{exa}  The {\em negated LWW terrace} for $\Z_n$, obtained by negating each element of the LWW terrace of Example~\ref{ex:lww}, is a graceful terrace.
\end{exa}


\begin{lem}\label{lem:twizzler}
For all $t \geq 2$ there is a graceful sequence of length $2t-1$ with endpoints $t-2$ and $2t-3$.
\end{lem}

Proof.  When $t \equiv 5 \pmod{6}$ we use the complement of the ``3-twizzler" graceful terrace described in \cite{PreeceZF}.   The 3-twizzler terrace is obtained from the negated LWW terrace for $\Z_{2t-1}$ by dividing the terrace into subsequences of length~3 and reversing (``twizzling") each of them.  After taking the complement we have:
$$ \ub{2t-3, \  0,\ 2t-2},\  \ub{2,\ 2t-4,\ 1},  \ldots, \ub{t-1,\ t,\ t-2}.$$
When $t \equiv 2 \pmod{6}$ the complement of 3-twizzler terrace begins the same way but ends $t-1,t-2,t$.  Switching the last two elements preserves the gracefulness of the sequence and gives us the $t-2$ that we need as an endpoint.

When $t \equiv 0 \pmod{3}$ we can use the complement of the ``imperfect 3-twizzler" graceful terrace of \cite{PreeceZF}.  In Preece's imperfect 3-twizzler terrace all but the final two elements are obtained by 3-twizzling as above.  Here is its complement:
$$ \ub{2t-3,\ 0,\ 2t-2},\  \ub{2,\ 2t-4, \ 1}, \ldots,\  \ub{t,\ t-3,\ t+1},\  t-1,\  t-2.$$

Finally, when $t \equiv 1 \pmod{3}$ we give a new graceful terrace using similar ideas.  We begin as in the previous cases by twizzling subsequences of length~3 from the negated LWW graceful terrace, however this time we stop with~7 elements remaining and rearrange those to give a final element of $t-2$ while preserving the gracefulness of the sequence:
\begin{flushleft}
$\ub{2t-3,\  0,\ 2t-2},\  \ub{2,\ 2t-4,\ 1}, \ldots,\  \ub{t-5,\ t+3,\ t-6},$
\end{flushleft}
\begin{flushright}
$t+1, \ t-3,\  t+2,\  t-4,\  t-1,\  t,\  t-2.$
\end{flushright}
This completes the proof.
\qed



\begin{thm}\label{th:dsm}
The groups $D_{8t}$, $S_{8t}$ and $M_{8t}$ have an extendable terrace for all $t \geq 2$.
\end{thm}

Proof.  The similar structure of the three groups allows us to use a slightly unusual approach.  We give a sequence of elements of the form $u^xv^y$ with $0 \leq x \leq 4t-1$ and $y \in \{0, 1 \}$ and this sequence is a terrace regardless of to which group we interpret the elements belonging.

The terrace takes the form ${\bf a} = (e, \alpha, \beta, u^{2t}, v, \gamma, u^tv, \delta)$, where each Greek letter represents a sequence of elements.  With the exception of $\delta$, each of these sequences can be expressed in a ``zigzag" pattern.  The partial terrace up to $u^tv$ is given in Table~\ref{tab:terrsdm}. 


\begin{table}
\begin{center}
\caption{Partial extendable terrace for $D_{8t}$, $S_{8t}$ and $M_{8t}$} \label{tab:terrsdm}
\begin{tabular}{l | p{2.4 cm} r}
$e$ & &
 $e$ \\
$\alpha $& &
 $u^{2t-1}, uv,  u^{2t-2},  u^2v,  u^{2t-3}, \ldots, u^{t+1}, u^{t-1}v, u^t$ \\
$\beta$ & &
 $u^{t+1}v, u^{t-1}, u^{t+2}v, u^{t-2}, \ldots, u^2, u^{2t-1}v, u, u^{2t}v$ \\
$u^{2t}$ & &
 $u^{2t}$ \\
$v$ &  &
 $v$ \\
$\gamma$ & &
 $u^{2t+1}v, u^{4t-1}v, u^{2t+2}v, u^{4t-2}v, \ldots, u^{3t-1}v, u^{3t+1}v, u^{3t}v$ \\
$u^tv$ & &
 $u^tv$ \\
\end{tabular} 
\end{center}
\end{table}


The associated partial 2-sequencings arising from the partial terrace for $D_{8t}$, $S_{8t}$ and $M_{8t}$ are given in Tables~\ref{tab:2seqd}, \ref{tab:2seqs} and~\ref{tab:2seqm} respectively with each row starting with the difference created by joining the subsequence with the previous one.


\begin{table}\caption{Partial $2$-sequencing for $D_{8t}$} \label{tab:2seqd}
\begin{center}
\begin{tabular}{l | p{3.5 cm} r}
$\alpha $ & &
 $u^{2t-1}, u^{2t+2}v, u^{2t+3}v, u^{2t+4}v, \ldots, u^{4t-2}v, u^{4t-1}v$ \\
$\beta$ & &
 $uv, u^2v, u^3v, \ldots, u^{2t-2}v, u^{2t-1}v$ \\
$u^{2t}$ & &
 $v$ \\
$v$ &  &
 $u^{2t}v$ \\
$\gamma$ & &
 $u^{2t-1}, u^{2t+2}, u^{2t-3}, u^{2t+4}, \ldots, u^3, u^{4t-2}, u$ \\
$u^tv$ & &
 $u^{2t}$ \\
\end{tabular}
\end{center}
\end{table}


\begin{table}[t] \caption{Partial $2$-sequencing for $S_{8t}$}\label{tab:2seqs}
\begin{center}
\begin{tabular}{l | p{3 cm} r}
$\alpha $ & &
 $u^{2t-1}, u^{2t+2}v, u^{3}v, u^{2t+4}v, u^{5}v, \ldots, u^{4t-2}v, u^{2t-1}v$ \\
$\beta$ & &
 $uv, u^2v, u^3v, \ldots, u^{2t-2}v, u^{2t-1}v$ \\
$u^{2t}$ & &
 $v$ \\
$v$ &  &
 $u^{2t}v$ \\
$\gamma$ & &
 $u^{4t-1}, u^{2t+2}, u^{4t-3}, u^{2t+4}, \ldots, u^{2t+3}, u^{4t-2}, u$ \\
$u^tv$ & &
 $u^{2t}$ \\
\end{tabular}
\end{center}
\end{table}

\begin{table}[th] \caption{Partial $2$-sequencing for $M_{8t}$} \label{tab:2seqm}
\begin{center}
\begin{tabular}{l | p{1.9 cm} r}
$\alpha $ & &
 $u^{2t-1}, u^{2t+2}v, u^{4t-3}v, u^{2t+4}v, u^{4t-5}v, \ldots, u^{4t-2}v, u^{2t+1}v$ \\
$\beta$ & &
 $uv, u^{4t-2}v, u^3v, u^{4t-4}, \ldots, u^{2t+2}v, u^{2t-1}v$ \\
$u^{2t}$ & &
 $v$ \\
$v$ &  &
 $u^{2t}v$ \\
$\gamma$ & &
  $u, u^{2t-2}, u^{3}, u^{2t-4}, \ldots, u^{2t-3}, u^{2}, u^{2t-1}$ \\
$u^tv$ & &
 $u^{2t}$ \\
\end{tabular}
\end{center}
\end{table}



In each case, to complete the sequence to a terrace $\delta$ needs to satisfy three conditions. First, it must generate the final quotient of the form $u^xv$, which it can do by starting with $u^{3t-1}$. Second,  it must contain the elements of the form $u^x$ for $2t+1 \leq x \leq 4t-1$.  Third, it must generate one from each inverse pair within $\langle u \rangle$ except for $u^{2t}$ and $u^{\pm (2t-1)}$.  Further, for the terrace to be extendable, the last element of $\delta$ must be $u^{4t-2}$.  

These conditions can be met by taking a graceful sequence $(g_1, g_2, \ldots, g_{2t-1})$ that starts with $t-2$ and ends with $2t-3$ and defining the $i$th element of $\delta$ to be $u^{2t+1+{g_i}}$.  Such a sequence exists by Lemma~\ref{lem:twizzler}.

Finally, we need to check the other condition to be extendable; that $a_{j-1}a_{j+1} = a_j = a_{j+1}a_{j-1}$ for some $j \geq 5$.   Setting $j = 4t-1$, we find that $a_{j-1} = u^{2t}v$, $a_j = u^{2t}$ and $a_{j+1} = v$; a valid choice in each of the three groups.
\qed



\begin{exa}
The terrace for $D_{32}$, $S_{32}$ and $M_{32}$ given by Theorem~\ref{th:dsm} is
\begin{flushleft}
$e,u^{7},uv,u^{6},u^2v,u^{5},u^3v,u^{4}, u^{5}v, u^{3},u^{6}v,u^2,u^{7}v,u,u^{8}v,u^{8},$ 
\end{flushleft}
\begin{flushright}
$v,u^{9}v,u^{15}v,u^{10}v,u^{14}v,u^{11}v,u^{13}v,u^{12}v,u^4v,u^{11},u^{13},u^{12},u^9,u^{15},u^{10},u^{14}.$
\end{flushright}

\end{exa}

When considering which groups are most likely to give a counterexample to Bailey's conjecture those with many involutions and/or large elementary abelian 2-groups as subgroups are natural contenders.  Theorem~\ref{th:dsm} and Corollary~\ref{cor:easyversion} imply that many such contenders are indeed terraced; groups of the form $\Z_2^{2s} \times D_{8t}$ for all~$s$ and for $t \geq 2$, for example.




A computer search for extendable terraces for small groups has been implemented in GAP \cite{gap}.   Neither of the two non-abelian groups of order~8 has an extendable terrace.  Extendable terraces were found for all twelve non-abelian groups of orders~12, 16 and~20 not covered by Theorem~\ref{th:dsm}.   The notation $G_{n/p}$ indicates that the group has order~$n$ and is in position~$p$ in GAP's small group library.      Where the group has a common name that is indicated as well, and we use the more familiar permutation notation for the alternating group~$A_4$.  The value for~$j$ in the definition of an extendable terrace is also given.  

\bigskip

Order~12: 
\begin{eqnarray*}
G_{12/1} &=& \langle a,b : a^6 = e, b^2 = a^3, ab = ba^{-1} \rangle \cong Q_{12}, \  j=5 \\
&& e,a^2,a,b,a^3b,a^3,a^4b,a^5,a^5b,ab,a^2b,a^4  \\
G_{12/3} &\cong& A_{4}, \ j=7 \\
&&  \hspace{-7mm} (), (123), (234), (124), (134), (14)(23), (12)(34), (13)(24), (142), (143), (243), (132)  \\
G_{12/4} &=& \langle a,b : a^6 = b^2 = e, ab = ba^{-1} \rangle \cong D_{12}, \  j=6 \\
&& e,a,a^2b,a^5,a^4b,ab,a^3,a^3b,a^5b,b,a^4,a^2 
\end{eqnarray*}

Order 16:
\begin{eqnarray*}
G_{16/3} &=& \langle a,b,c : a^4 = b^2 = c^2 = e, ab = bac, [a,c]=[b,c]=e \rangle, \ j=6 \\
&& e,a,a^3,a^3c,a^2b,bc,a^2c,b,ab,ac,abc,c,a^3bc,a^2bc,a^3b,a^2 \\
G_{16/4} &=& \langle a,b : a^4 = b^4 = e, ab = ba^{-1} \rangle, \ j = 13 \\
&& e,a^2b,a^3b^3,a^3,ab^3,a^2,a,a^3b^2,b,b^3,a^2b^3,a^3b,a^2b^2,ab,ab^2,b^2 \\
G_{16/9} &=& \langle a,b : a^8 = e, b^2 = a^4, ab = ba^{-1} \rangle \cong Q_{16}, \  j=5 \\
&& e,a^2b,ab,a,a^7,a^6,b,a^3b,a^7b,a^5b,a^2,a^5,a^6b,a^3,a^4b,a^4 \\
G_{16/11} &=& \langle a,b,c : a^4 = b^2 = c^2 = e, ab = ba^{-1},  [a,c]=[b,c]=e \rangle \cong D_8 \times \Z_2, \  j=8 \\
&& e,a^3c,a^3,a,b,a^3b,bc,a^2c,a^2b,c,ab,a^3bc,a^2bc,ac,abc,a^2 \\
G_{16/12} &=& \langle a,b,c : a^4 = c^2 = e, b^2 = a^2, ab = ba^{-1},  [a,c]=[b,c]=e \rangle \cong Q_8 \times \Z_2, \ j = 10 \\
&& e,b,ab,ac,bc,c,a,a^3c,a^3b,a^2c,a^3bc,abc,a^2b,a^2bc,a^3,a^2 \\
G_{16/13} &=& \langle a,b,c : a^2 = b^2 = c^4 = e, ab = bac^2,  [a,c]=[b,c]=e) \rangle, \ j=8 \\
&& e,c,ac^2,abc^2,bc^3,ac,bc,b,c^3,ab,bc^2,ac^3,abc,abc^3,a,c^2
\end{eqnarray*}

\bigskip

Order 20:
\begin{eqnarray*}
G_{20/1} &=& \langle a,b : a^{10} = e, b^2 = a^5, ab = ba^{-1} \rangle \cong Q_{20}, \ j=9 \\
&& e,b,a^6b,ab,a^4b,a,a^3b,a^7,a^6,a^9, a^2b,a^2,a^4,a^8b,a^7b,a^8,a^5b,a^9b,a^3,a^5 \\
G_{20/3} &=& \langle a,b : a^5 = b^4 = e, ab = ba^2 \rangle, \  j=17 \\
&& e,a^2,ab,a^3,a^4b^3,ab^3,a^2b^2,a^2b,b^2,a, a^4b^2,b,a^3b,a^3b^3,a^3b^2,ab^2,a^2b^3,a^4b,b^3,a^4 \\
G_{20/4} &=& \langle a,b : a^{10} = b^2 = e, ab = ba^{-1} \rangle \cong D_{20},  \ j=5 \\
&& e,a^6,a^4b,a^5,a^8b,a^3b,b,a^4,a^5b,a^8, a^2b,a^9b,a^7b,a^6b,a,ab,a^9,a^7,a^3,a^2 
\end{eqnarray*}

\bigskip

%\begin{flushleft}
%$G_{16/6} = \langle a,b : a^8 = b^2 = e, ab = ba^5 \rangle \cong M_{16}, j=8$ \\
%\hspace{10 mm} $e,a^3,ab,a^2,a^3b,a,a^4b,a^4,b,a^5b,a^7b,a^6b,a^2b,a^5,a^7,a^6$
%\end{flushleft}

%\begin{flushleft}
%$G_{16/7} = \langle a,b : a^8 = b^2 = e, ab = ba^{-1} \rangle \cong D_{16}, j=8$ \\
%\hspace{10 mm} $e,a^3,ab,a^2,a^3b,a,a^4b,a^4,b,a^5b,a^7b,a^6b,a^2b,a^5,a^7,a^6$
%\end{flushleft}

%\begin{flushleft}
%$G_{16/8} = \langle a,b : a^8 = b^2 = e, ab = ba^3 \rangle \cong S_{16}, j=8$ \\
%\hspace{10 mm} $e,a^3,ab,a^2,a^3b,a,a^4b,a^4,b,a^5b,a^7b,a^6b,a^2b,a^5,a^7,a^6$
%\end{flushleft}

The smallest order for which Bailey's conjecture is not settled is~64.  The abelian case for this order was proven in \cite{Ollis05, OW1}.  Of the~256 non-abelian groups of order~64, only three were known to have terraces prior to this work \cite{survey}.  The extendable terraces for groups of order 16 above imply that at least~25 further non-abelian groups of order~64 are terraced (this is the number of groups that have commuting elements in {\em all} pairs of commuting cosets of some central Klein 4-group to use in Theorem~\ref{th:big}). Combining this with the known ones and the new terraces here for $S_{64}$ and $M_{64}$ gives a total of~30.  There are~208 non-abelian groups of order 64 that have a central Klein 4-group with at least one pair of commuting cosets that contain a pair of commuting elements; many of these may fall to Theorem~\ref{th:big} if an appropriate extendable terrace for the quotient group of order~16 can be found.


\bigbreak\bigskip

\begin{thebibliography}{99}


\bibitem{AandI92}
B.~A.~Anderson and E.~C.~Ihrig.
\newblock All groups of odd order have starter-translate 2-sequencings.
\newblock {\em Australas. J. Combin.} {\bf 6} (1992) 135--146.

\bibitem{AandI93} B.~A.~Anderson and E.~C.~Ihrig,
Symmetric sequencings of non-solvable groups,
{\em Congr. Numer.} {\bf 93} (1993) 73--82.


\bibitem{Bailey84}
R.~A.~Bailey,
Quasi-complete {L}atin squares: construction and randomization,
{\em J.~Royal Statist. Soc. Ser. B} {\bf 46} (1984) 323--334.


\bibitem{Gallian}
J.~A.~Gallian, A dynamic survey of graph labellings, Electron. J. Combin. {\bf DS6} (2001--2010), 246pp.

\bibitem{gap}
{{G}{A}{P} group}.
\newblock {G}{A}{P}---{G}roups, {A}lgorithms, and {P}rogramming, {V}ersion 4,
  1999.


\bibitem{HLW}
Y.-S.~Hwang, D.~B.~Leep and A.~R.~Wadsworth,
Galois groups of order $2n$ that contain a cyclic subgroup of order $n$, {\em Pacific J. Math.} {\bf 212} (2003) 297--319.

\bibitem{Lucas92}
\'{E}.~Lucas, {\em R\'{e}cr\'{e}ations Math\'{e}mathiques}, T\^{o}me II, Albert Blanchard, Paris, 1892 (reprinted 1975).

\bibitem{survey}
M.~A. Ollis, Sequenceable groups and related topics,
{\em Electron. J. Combin.} {\bf DS10} (2002) 34pp.

\bibitem{Ollis05}
M.~A.~Ollis, On terraces for abelian groups, {\em Disc. Math.} {\bf 305} (2005) 250--263.

\bibitem{Ollis12}
M.~A.~Ollis,  A note on terraces for abelian groups,  {\em Australas.~J.~Combin.}  {\bf 52} (2012),  229--234.

\bibitem{OW1}
M.~A.~Ollis and D.~T.~Willmott, On twizzler, zigzag and graceful terraces, {\em Australas.~J.~Combin.} {\bf 51} (2011) 243--257.


\bibitem{PreeceZF}
D.~A.~Preece, Zigzag and foxtrot terraces for $\Z_n$, {\em Australas. J. Combin.} {\bf 42} (2008) 261--278.



\bibitem{Williams49}
E.~J. Williams,
Experimental designs balanced for the estimation of residual effects
  of treatments,
{\em Aust. J. Scient. Res. A}, {\bf 2} (1949) 149--168.



\end{thebibliography}


\end{document}



