\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{}{}{}

\usepackage{amsmath,amsthm,amssymb}
\usepackage{graphicx}
\usepackage{tikz}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\DeclareMathOperator{\aut}{Aut}
\newcommand{\Z}[1][n]{\mathbb{Z}^{#1}_2}
\newcommand{\cS}{\mathcal{S}}


%% IMW recommends leaving title like this
\title{\bf\hbox{\bf $\!\!\!$Cycle structures of orthomorphisms extending} partial orthomorphisms of Boolean groups}

\author{Nichole L. Schimanski\\
\small Dept. of Mathematics and Statistics\\[-0.8ex]
\small Portland State University\\[-0.8ex] 
\small Portland, Oregon, U.S.A.\\
\small\tt nls@pdx.edu\\
\and
John S. Caughman IV\\
\small Dept. of Mathematics and Statistics\\[-0.8ex]
\small Portland State University\\[-0.8ex] 
\small Portland, Oregon, U.S.A.\\
\small\tt caughman@pdx.edu\\
}

\date{\dateline{Oct 12, 2015}{Aug 17, 2016}{}\\
\small Mathematics Subject Classifications: 05A05, 05B15, 20B99, 68P25}



\begin{document}
\maketitle
\begin{abstract}
  A \emph{partial orthomorphism} of a group $G$ (with additive
  notation) is an injection $\pi:S \to G$ for some $S \subseteq G$
  such that $\pi(x)-x \not= \pi(y)-y$ for all distinct $x,y \in S$. We
  refer to $|S|$ as the $\emph{size}$ of $\pi$, and if $S = G$, then
  $\pi$ is an {\em orthomorphism}. Despite receiving a fair amount of
  attention in the research literature, many basic questions remain
  concerning the number of orthomorphisms of a given group, and what
  cycle types these permutations have.

  It is known that conjugation by automorphisms of $G$ forms a group
  action on the set of orthomorphisms of $G$.  In this paper, we
  consider the additive group of binary $n$-tuples, $\Z$, where we
  extend this result to include conjugation by translations in $\Z$
  and related compositions. We apply these results to show that, for
  any integer $n >1$, the distribution of cycle types of
  orthomorphisms of the group $\Z$ that extend any given partial
  orthomorphism of size two is independent of the particular partial
  orthomorphism considered.  A similar result holds for size one. We
  also prove that the corresponding result does not hold for
  orthomorphisms extending partial orthomorphisms of size three, and
  we give a bound on the number of cycle-type distributions for the
  case of size three. As a consequence of these results, we find that
  all partial orthomorphisms of $\Z$ of size two can be extended to
  complete orthomorphisms.
\end{abstract}

\section{Introduction}
Let $G$ be a finite group written with additive notation. A
\emph{partial orthomorphism} of $G$ is an injection $\pi:S \to G$ such
that $\pi(x)-x = \pi(y)-y$ implies $x=y$ for all
$x,y \in S \subseteq G$. The \emph{size} of a partial orthomorphism
is the cardinality of the domain $S$. If $S = G$, then $\pi$ is an
\emph{orthomorphism}.  An orthomorphism $\sigma$ is said to
\emph{extend} a partial orthomorphism $\pi$ whenever $\sigma$ agrees
with $\pi$ everywhere on the domain of $\pi$. A partial orthomorphism
(or orthomorphism) is \emph{canonical} if $\pi(0) =0$.

Orthomorphisms grew out of the study of mutually orthogonal Latin
squares, initiated by Euler in \cite{euler}. The concept of
orthomorphism was further developed by Johnson, et al. in
\cite{JDMpaper}, motivated by the study of mutually orthogonal Latin
squares. Since then, results on the number of orthomorphisms of some
small groups have been computed and an upper bound on the maximum
number of orthomorphisms for a group of a given size has been proved.
See \cite{wanless} for an exposition of the current state of research
in the context of Latin squares. Further, in the context of Latin
squares, the existence of extensions of partial orthomorphisms of
various sizes for the group $\mathbb{Z}_n$ has been studied
\cite{cavenagh,gruttmuller,stones}.

Applications of orthomorphisms of the group $\Z$ to cryptography are
found in the construction of block ciphers and hash functions--most
famously in the Lai-Massey scheme \cite{laimassey}, but also in the less
well-known FOX family of block ciphers \cite{FOX}. More recently,
orthomorphisms have been used to strengthen the Even-Mansour block
cipher against a cryptographic attack which makes use of the
non-uniformity of $p(x)-x$ when $p$ is a random permutation
\cite{balancedperm}.

Interest in the algebraic structure of orthomorphisms, of the group
$\Z$ specifically, can be found in \cite{lothrop} where Mittenthal
shows that a permutation is an orthomorphism if and only if it maps
every maximal subgroup half into itself and half into its
complement. Further mathematical research on orthomorphisms of the
group $\Z$ can be found in \cite{genlinorthos} and \cite{genorthos}.

Since orthomorphisms are permutations, it is natural to consider their
cycle types. Although the number of different cycle types for a
permutation of a set with $m$ elements is given by the number of
integer partitions of $m$, we find that for orthomorphisms of $\Z$,
the number of possible cycle types is significantly reduced. For
example, it is elementary to show that orthomorphisms of $\Z$ must
have exactly one fixed point and can have no cycles of length
two. These constraints alone dramatically limit the number of cycle
types possible for orthomorphisms. Our results extend these elementary
observations and offer further information concerning the permissible
cycle types.

Indeed, although the set of orthomorphisms of $\Z$ for the $n\leq 4$
cases can be easily generated with a computer, it turns out that, as
of the date of this writing, even the cardinality of this set is
unknown for any $n \geq 5$.  When $n=1$, there are no
orthomorphisms. When $n=2$, it is easily shown that all 8
orthomorphisms have cycle type 1,3, that is, they have precisely one
fixed point and one cycle of length three.  Similarly, when $n=3$, all
384 orthomorphisms have cycle type 1,7.  When $n=4$, however, we find
that there are a total of 244,744,192 orthomorphisms, and they are
distributed among exactly 16 cycle types. This is out of 231 total
partitions of the number $2^4=16$, and out of just 17 that have a
single fixed point and no cycles of length two.

To investigate these cycle structures further, we will consider a
number of group actions on the set of orthomorphisms. These group
actions lead to a uniformity in the cycle types of orthomorphisms that
extend certain partial orthomorphisms. Specifically, we show that, for
any integer $n > 1$, the distribution of cycle types of orthomorphisms
of the group $\Z$ that extend any given partial orthomorphism of size
two is independent of the particular partial orthomorphism considered.
A similar result holds for size one.  However, we also prove that the
corresponding result does not hold for orthomorphisms extending
partial orthomorphisms of size three, and we give a bound on the
number of cycle type distributions for the case of size three.

\section{Bijective, cycle-preserving maps}\label{sec:preserving}
In this section, we introduce a class of bijective cycle-type
preserving functions defined on sets of orthomorphisms. The basic
functions in this class are conjugations by automorphisms
$g \in \textrm{Aut}(\Z)$, conjugations by translations 
\[T_k(x)= x+k,\]
for $x, k \in \Z$, and the inverse map. In particular, we consider all
functions of the form $C_h(\pi) = h\pi h^{-1}$ where $h$ is a finite
composition of automorphisms and translations, and $\pi$ is an
orthomorphism. As conjugations, the functions $C_h$ are obviously
bijective and cycle-type preserving. Similarly, the inverse map is
bijective and cycle-type preserving. The critical point, in all cases,
is to verify that these functions map orthomorphisms to
orthomorphisms.

\begin{lemma}\label{conjAut}\textup{\cite[p.361]{JDMpaper}} For any
  $g \in \aut(\Z)$ and any orthomorphism $\pi$ of $\Z$,
$$ C_g(\pi) = g \pi g^{-1}$$
is an orthomorphism of $\Z$.
\end{lemma}

\begin{proof}
  Since $g,\pi$ are permutations of $\Z$, it suffices to show that the
  map $x \mapsto g\pi g^{-1}(x)-x$ is a permutation. Since $\pi$ is an
  orthomorphism, the map $\sigma: x \mapsto \pi(x)-x$ is a
  permutation. Therefore
  \begin{align*}
    g \pi g^{-1}(x) - x &=   g (\pi (g^{-1}(x))) -g(g^{-1}(x))\\
                        &=   g (\pi (g^{-1}(x))- g^{-1}(x)) \\
                        &=   g \sigma g^{-1}(x),
  \end{align*}
  and $g \sigma g^{-1}$ is a permutation.
\end{proof}

We note that, as the proof above shows, Lemma~\ref{conjAut} is
generally true for any group $G$, not just $\Z$. Next we consider
conjugating by translations.

\begin{lemma}\label{conjTrans} For any $k \in \Z$ and any
  orthomorphism $\pi$ of $\Z$, the map
$$ C_{T_k}(\pi) = T_k \pi T_k^{-1}$$
is an orthomorphism of $\Z$.
\end{lemma}

\begin{proof}
  Since $T_k,\pi$ are permutations of $\Z$, it suffices to show
  the map $x \mapsto T_k\pi T_k^{-1}(x)-x$ is a permutation. Since
  $\pi$ is an orthomorphism, the map $\sigma: x \mapsto \pi(x)-x$ is a
  permutation. Therefore, 
  \begin{align*}
    T_k \pi T_k^{-1}(x) - x &=   T_k (\pi (x-k))) - x\\
                            &=   \pi (x-k)+ k-x \\
                            &=   \pi (x-k)- (x-k) \\
                            &=   \sigma T_k^{-1}(x)
  \end{align*}
  is also a permutation.
\end{proof}

We note that, as the above proof shows, if $G$ is an arbitrary group,
then Lemma~\ref{conjTrans} holds.

\begin{corollary}
  If $\pi$ is an orthomorphism and $h$ is any composition of a finite
  number of automorphisms and translations of $\Z$, then $C_h(\pi)$ is
  an orthomorphism. Moreover, the cycle type of $C_h(\pi)$ is the same
  as that of $\pi$.
\end{corollary}

\begin{proof}
  An immediate consequence of Lemmas~\ref{conjAut} and
  \ref{conjTrans}. The cycle type of any permutation is preserved by
  conjugation \cite[p. 125]{dummitfoote}.
\end{proof}

The final cycle-type preserving function on orthomorphism sets we
describe in this paper will be used in Section \ref{sec:len3pf}. Once
again, as the proof shows, the result is generally true for any group G.

\begin{lemma}\label{reverse}
For any orthomorphism $\pi$ of $\Z$, the map
\begin{align*}
R(\pi) = \pi^{-1}
\end{align*}
is an orthomorphism of $\Z$ with the same cycle type as $\pi$.
\end{lemma}

\begin{proof}
  Since $\pi^{-1}$ is a permutation with the same cycle-type as $\pi$,
  it suffices to show $x \mapsto \pi^{-1}(x)-x$ is injective. Let
  $x,y\in \Z$. Since $\pi$ is bijective, there exists unique
  $x',y'\in\Z$ such that $\pi(x')=x$ and $\pi(y')=y$. The following
  are equivalent,
\begin{align*}
\pi^{-1}(x)-x &= \pi^{-1}(y)-y \\
\pi^{-1}(\pi(x'))-\pi(x') &= \pi^{-1}(\pi(y'))-\pi(y') \\
x'-\pi(x') &= y'-\pi(y'), 
\end{align*}
thus, since $\pi$ is an orthomorphism, $x'=y'$. Further, since $\pi$
is well-defined, $x=y$. 
\end{proof}

We observe that the group $\Z$ may be viewed as an $n$-dimensional
vector space over the field with two elements. So, the following theorem is
fundamental to most of the arguments in Sections \ref{sec:one} and
\ref{sec:two}.

\begin{theorem}\label{rem:AutStrength}
For any $n \in \mathbb{N}$, the automorphism group of $\Z$ satisfies the following properties.
\begin{enumerate}
\item $\textrm{Aut}(\Z) \cong \textrm{GL}_n(\mathbb{Z}_2)$, the group
  of invertible $n \times n$ matrices.
\item Each element of $g \in \textrm{Aut}(\Z)$ can be represented by a
  matrix in $\textrm{GL}_n(\mathbb{Z}_2)$ and its action on $\Z$ corresponds to matrix multiplication.
\item Let $g$ be an element of $\textrm{Aut}(\Z)$. Any
  $x_1,\dots,x_k \in \Z$ satisfies a dependence relation
\begin{align*}
c_1x_1+\cdots+c_kx_k=0 &\hspace{5mm} (c_1,\dots,c_k \in \mathbb{Z}_2)
\end{align*}
if and only if $g(x_1),\dots,g(x_k)$ satisfies the same relation.
\item In particular, if $g \in \textrm{Aut}(\Z)$ then any
  $x_1,\dots,x_k \in \Z$ are linearly dependent (independent) if and
  only if $g(x_1),\dots,g(x_k)$ are linearly dependent (independent).
\end{enumerate}
\end{theorem}

\begin{proof}
  For more about these standard results from linear algebra, we refer
  the interested reader to the excellent texts
  \cite[Chapter~11]{dummitfoote} and \cite{poole}.
\end{proof}

\section{Notation}

\begin{definition} \label{def:portho} If $\pi$ is a partial
  orthomorphism of size one with a domain in $\Z$ such that
  $\pi(r)=i$, then we write $\pi$ as $(i_r)$. If $\pi$ is a partial
  orthomorphism of size two such that $\pi(r)=i$ and $\pi(s) = j$ for
  distinct $r,s$, then we write $\pi$ as $(i_r,j_s)$. Further, if
  $\pi$ is a partial orthomorphism of size three such that $\pi(r)=i$,
  $\pi(s) = j$, and $\pi(t) = k$, then we write $\pi$ as
  $(i_r,j_s,k_t)$.
\end{definition}

Note that in the partial orthomorphism $(i_r,j_s)$, the elements $i$
and $j$ are distinct since the partial orthomorphism is injective; and
$i+r \neq j+s$ which follows from the definition of partial
orthomorphism.

\begin{definition} If $\pi$ is a partial orthomorphism of size one
  with a domain in $\Z$ such that $\pi(r)=i$, then the set of all
  orthomorphisms that extend $\pi$ is denoted $\cS(i_r)$. If
  $(i_r,j_s)$ is a partial orthomorphism of size two then the set of
  all orthomorphisms that extend it is denoted
  $\cS(i_r,j_s)$. Further, if $(i_r,j_s,k_t)$ is a partial
  orthomorphism then the set of all orthomorphisms that extend it is
  denoted $\cS(i_r,j_s,k_t)$.
\end{definition}

We now define a sequence that encodes the distribution of
orthomorphisms among the possible cycle types.

\begin{definition}
  For a fixed $n$, let $\mathcal{C}_n$ be the set of all possible
  cycle types of permutations of $\Z$. Then, for any partial
  orthomorphism $(i_r,j_s)$, we define
  $$ \vec{\bf d}(i_r,j_s) = (n_t)_{t \in \mathcal{C}_n}$$
  to be the $|\mathcal{C}_n|$-tuple of nonnegative integers, indexed
  by $\mathcal{C}_n$, whose entries $n_t$ equal the number of elements
  of $\cS(i_r,j_s)$ with the given cycle type $t$. For partial
  orthomorphisms of size one (and three), we define $\vec{\bf d}(i_r)$
  (and $\vec{\bf d}(i_r,j_s,k_t)$) similarly.
\end{definition}

\section{Cycle type distributions and partial orthomorph\-isms of size
  one}\label{sec:one}
In this section we show that the set of orthomorphisms that extend any
partial orthomorphism of size one has a cycle-type distribution which
does not depend on the particular partial orthomorphism of size one
chosen.

We begin by considering some canonical partial orthomorphisms of
size one and two.

\begin{lemma}\label{lem:0fixed} Suppose $(0_0,i_r)$ is
  a partial orthomorphism of $\Z$ and $n>1$. Then
$$ \vec{\bf d}(0_0) = (2^n-2) \vec{\bf d}(0_0,i_r).$$
\end{lemma}

\begin{proof}
  Partitioning the set of canonical orthomorphisms $\cS(0_0)$
  according to the partial orthomorphisms of size two on $\{0,r \}$
  they extend, we have
  \begin{align*}
    \vec{\bf d}(0_0) = \sum_{j \neq 0,r} \vec{\bf d}(0_0,j_r).
  \end{align*}
  For any $i,j\in \Z\setminus\{0,r\}$, the sets $\{r,i\}$ and
  $\{r,j\}$ are linearly independent. So, by Theorem
  \ref{rem:AutStrength}, there exists an automorphism $g$ of $\Z$ such
  that $g(r) = r$ and $g(i) =j$. Then the function $C_g$ maps
  $\cS(0_0,i_r)$ onto $\cS(0_0,j_r)$ bijectively, showing that
  $\vec{\bf d}(0_0,i_r) = \vec{\bf d}(0_0,j_r)$. It follows that each
  of the $2^n-2$ terms in the sum shares the common value
  $\vec{\bf d}(0_0,i_r)$, so
\[
  \vec{\bf d}(0_0) = \sum_{j \neq 0,r} \vec{\bf d}(0_0,j_r) = (2^n-2)
  \vec{\bf d}(0_0,i_r),
\]
as desired.
\end{proof}

\begin{lemma}\label{lem:1fixed}
  Suppose $(i_s,t_t)$ is a partial orthomorphism of $\Z$ and $n>1$.
  Then
$$\vec{\bf d}(i_s) = (2^n-2)\vec{\bf d}(i_s,t_t).$$
\end{lemma}

\begin{proof}
  First note that $i, s, t$ must be distinct since $(i_s,t_t)$ is a
  partial orthomorphism. Indeed, observe that any $x \in \Z$ is a
  fixed point of an orthomorphism $\pi$ if and only if
  $\pi(x) - x =0$. So, if $r$ and $s$ are fixed points of $\pi$ then
  \[
    \pi(r)-r=0=\pi(s)-s,
  \]
  but the map $x \mapsto \pi(x)-x$ is a permutation when $\pi$ is an
  orthomorphism. So, by injectivity, every orthomorphism of $\Z$ has
  at most 1 fixed point; and by surjectivity, some $x$ must satisfy
  $\pi(x)-x=0$, so every orthomorphism has at least 1 fixed
  point. Therefore, every orthomorphism of $\Z$ has precisely one
  fixed point. So, we can partition the set of orthomorphisms
  $\cS(i_s)$ so that:
  \begin{align*}
    \vec{\bf d}(i_s) = \sum_{j \neq i,s} \vec{\bf d}(i_s,j_j).
  \end{align*}
  For any $j,t \in \Z\setminus\{i,s\}$, the sets $\{i+s,t+s\}$ and
  $\{i+s,j+s\}$ are linearly independent. So, by Theorem
  \ref{rem:AutStrength}, there exists an automorphism $g$ of $\Z$ such
  that $g(i+s) = i+s$ and $g(t+s)=j+s$. Set $h = T_sgT_s$, and note
  that the function $C_h$ maps $\cS(i_s,t_t)$ onto $\cS(i_s,j_{j})$
  bijectively, showing that
  $\vec{\bf d}(i_s,t_t) = \vec{\bf d}(i_s,j_{j})$.  It follows that
  all $2^n-2$ terms in the above sum are equal, so
\[ 
\vec{\bf d}(i_s) = (2^n-2) \vec{\bf d}(i_s,t_t),
\]
as desired.
\end{proof}

With the lemmas above, we are now ready to prove our result
concerning size one partial orthomorphisms.

\begin{theorem}\label{thm:l1pe}
  For any integer $n >1$, the distribution of cycle types of
  orthomorphisms of the group $\Z$ that extend any given partial
  orthomorphism of size one is independent of the particular partial
  orthomorphism considered.
\end{theorem}

\begin{proof}
  Let $i,s,i',s' \in \Z$. If $i=s$ and $i'=s'$ then $C_h$ maps
  $\cS(i_s)$ onto $\cS(i'_{s'})$ bijectively when $h =T_{s+s'}$. If
  $i \neq s$ and $i' \neq s'$, we can instead use the map
  $h=T_{s'}gT_{s}$, where $g$ is any automorphism satisfying
  $g(i+s) = i'+s'$. We are left to show that $\cS(0_0)$ has the same
  cycle type distribution as $\cS(i_s)$ for some $i \neq s$. From
  Lemmas \ref{lem:0fixed} and \ref{lem:1fixed}, we can write
  \begin{align*}
    \vec{\bf d}(0_0) = (2^n-2)\vec{\bf d}(i_s,0_0) = \vec{\bf d}(i_s),
  \end{align*}
  and the statement is proved.
\end{proof}

\section{Cycle type distributions and partial orthomorph\-isms of size
  two}\label{sec:two}
Investigating partial orthomorphisms of size two leads to the
consideration of three basic types of cycle structures.  We will
explore each of these cases separately by first proving cycle
distribution uniformity within each category.  Then we complete the
argument by establishing uniformity across the cases. Note that the
2-cycle and two 1-cycles are not partial orthomorphisms, so cases
related to them are not considered.

\tikzset{every loop/.style={min distance=7mm,in=150,out=210,looseness=10}}

\begin{center}
  \begin{tabular}{c c c}
    Case &  Orthomorphism Set & Digraph Representation \\ \hline
       1 &  $\cS(t_t,i_s)$ &  \begin{tikzpicture}[scale=0.75]
  \path (0,0) coordinate[label=above:{\scriptsize $t$}] (t);
  \fill (t) circle (.5mm);

  \path (1,0) coordinate[label=above:{\scriptsize $s$}] (s);
  \fill (s) circle (.5mm);
  
  \path (2,0) coordinate[label=above:{\scriptsize $i$}] (i);
  \fill (i) circle (.5mm);
  
  \path[shorten >=0.5mm,->] (t) edge  [loop above] node {} ();
  
  \draw[shorten >=0.5mm,->] (s) -- (i);
\end{tikzpicture} \\
       2 & $\cS(t_r,r_s)$ & \begin{tikzpicture}[scale=0.75]
  \path (2,0) coordinate[label=above:{\scriptsize $t$}] (t);
  \fill (t) circle (.5mm);

  \path (0,0) coordinate[label=above:{\scriptsize $s$}] (s);
  \fill (s) circle (.5mm);
  
  \path (1,0) coordinate[label=above:{\scriptsize $r$}] (r);
  \fill (r) circle (.5mm);
  
  \draw[shorten >=0.5mm,->] (s) -- (r);
  \draw[shorten >=0.5mm,->] (r) -- (t);
\end{tikzpicture}  \\
       3 & $\cS(t_r,i_s)$ & \begin{tikzpicture}[scale=0.75]
  \path (0,0) coordinate[label=above:{\scriptsize $r$}] (r);
  \fill (r) circle (.5mm);

  \path (1,0) coordinate[label=above:{\scriptsize $t$}] (t);
  \fill (t) circle (.5mm);
  
  \path (2,0) coordinate[label=above:{\scriptsize $s$}] (s);
  \fill (s) circle (.5mm);

  \path (3,0) coordinate[label=above:{\scriptsize $i$}] (i);
  \fill (i) circle (.5mm);
  
  \draw[shorten >=0.5mm,->] (r) -- (t);
  \draw[shorten >=0.5mm,->] (s) -- (i);
\end{tikzpicture} \\
  \end{tabular}
\end{center}

Regarding Cases 1 and 2, notice that if $(t_t,i_s)$ is a partial
orthomorphism then $i,s,t \in\Z$ are distinct. Similarly, if
$(t_r,r_s)$ is a partial orthomorphism then $r,s,t$ are distinct. This
pattern does not continue for the partial orthomorphism
$(t_r,i_s)$. To distinguish Case 3 from the others, we make the
additional assumption that $i,r,s,t \in \Z$ are distinct.

\begin{lemma}[Case 1]
  Suppose $(t_t,i_s)$ and $(t'_{t'},i'_{s'})$ are partial
  orthomorphisms of $\Z$ and $n>1$.  Then
  \[\vec{\bf d}(t_t,i_s) = \vec{\bf d}(t'_{t'},i'_{s'}).\]
\end{lemma}

\begin{proof}
  By Lemma \ref{lem:1fixed} and Theorem \ref{thm:l1pe}, we have
\[
    \vec{\bf d}(t_t,i_s) = \left(\tfrac{1}{2^n-2} \right)\vec{\bf d}(i_s) 
                         = \left(\tfrac{1}{2^n-2} \right)\vec{\bf d}(i'_{s'}) 
                         = \vec{\bf d}(t'_{t'},i'_{s'}). \qedhere
\]
\end{proof}

\medskip

\begin{lemma}[Case 2]\label{lem:case2equiv}
  Suppose $(t_r,r_s)$ and $(t'_{r'},r'_{s'})$ are partial
  orthomorphisms of $\Z$ and $n>1$.  Then
  \[\vec{\bf d}(t_r,r_s) = \vec{\bf d}(t'_{r'},r'_{s'}).\]
\end{lemma}

\begin{proof}
  Observe that the sets $\{r+s,t+s\}$ and $\{r'+s',t'+s'\}$ are
  linearly independent whenever $(t_r,r_s)$ and $(t'_{r'},r'_{s'})$
  are partial orthomorphisms.  So, by Theorem \ref{rem:AutStrength},
  there exists an automorphism $g$ of $\Z$ that satisfies
  $g(r+s) = r'+s'$ and $g(t+s) = t'+s'$. Finally, apply $C_h$ where
  $h = T_{s'}gT_s$ to $\cS(t_r,r_s)$ to prove the statement of the
  lemma.
\end{proof}

We make note of the following corollary, which relates Case 2 for
partial orthomorphisms of size two back to the distributions for
partial orthomorphisms of size one.

\begin{corollary} \label{coro:c2decompose} For distinct $r,s,t \in\Z$,
  and $n>1$,
  \[
    \vec{\bf d}(t_r) = (2^n-2)\vec{\bf d}(t_r,r_s).
  \]
\end{corollary}

\begin{proof}
  By Lemma \ref{lem:case2equiv}, we have
  $\vec{\bf d}(t_r,r_s) = \vec{\bf d}(t_r,r_{s'})$ for all
  $s' \in \Z\setminus\{r,t\}$. So,
  \begin{align*}
\phantom{kick v. far right}
    \vec{\bf d}(t_r) &= \sum_{s' \neq r,t} \vec{\bf d}(t_r,r_{s'}) && \\
                     &= (2^n-2) \vec{\bf d}(t_r,r_{s}). &&\qedhere
  \end{align*}
\end{proof}

We now turn to Case 3.

\begin{lemma}[Case 3]\label{lem:c3}
  Suppose $(t_r,i_s)$ and $(t'_{r'},i'_{s'})$ are partial
  orthomorphisms of $\Z$ and $n>1$ where $i,r,s,t \in \Z$ are distinct
  and $i',r',s',t' \in \Z$ are distinct.  Then
  \[\vec{\bf d}(t_r,i_s) = \vec{\bf d}(t'_{r'},i'_{s'}).\]
\end{lemma}

\begin{proof}
  To begin, note that the set $\{t+r,i+r,s+r\}$ is linearly
  independent whenever $(t_r,i_s)$ is a partial orthomorphism with
  distinct elements. Similarly, the set $\{t'+r',i'+r',s'+r'\}$ is
  linearly independent. Then by Theorem~\ref{rem:AutStrength}, there
  exists an automorphism $g$ of $\Z$ such that $g(t+r)=t'+r'$,
  $g(i+r)=i'+r'$, and $g(s+r)=s'+r'$. Setting $h=T_{r'}gT_r$, the map
  $C_h$ defines a cycle-type preserving bijection from from
  $\cS(t_r,i_s)$ onto $\cS(t'_{r'},i'_{s'})$.
\end{proof}

Again we make note of a relationship between Case 3 for partial
orthomorphisms of size two and the distributions for partial
orthomorphisms of size one.

\begin{corollary}\label{coro:c3decompose}
  For distinct $r, s, t \in \Z$ and $n>1$,
  \[
    \vec{\bf d}(t_r) = (2^n-2)\vec{\bf d}(t_r,i_s)
  \]
  for all $i \in \Z\setminus\{r,s,t,t+r+s\}$.
\end{corollary}

\begin{proof}
  Given that $r,t \in \Z$ and $r \neq t$, we have
  \begin{align*}
    \vec{\bf d}(t_r) &= \sum_{i \neq t, t+r+s} \vec{\bf d}(t_r,i_s).
  \end{align*}
  Using Lemma \ref{lem:c3}, Corollary \ref{coro:c2decompose}, and
  Lemma \ref{lem:1fixed}, we see that, for some
  $i \in \Z\setminus\{r, s, t, r+s+t\}$,
  \begin{align*}
    \vec{\bf d}(t_r) &= (2^n-4) \vec{\bf d}(t_r,i_s) + \vec{\bf d}(t_r,r_s) + \vec{\bf d}(t_r,s_s) \\
                     &= (2^n-4) \vec{\bf d}(t_r,i_s) + \left(\frac{1}{2^n-2}\right)\vec{\bf d}(t_r) + \left(\frac{1}{2^n-2}\right)\vec{\bf d}(t_r).
  \end{align*}
  Solving for $\vec{\bf d}(t_r)$ yields
  \begin{align*}
    \vec{\bf d}(t_r) &= (2^n-2) \vec{\bf d}(t_r,i_s),
  \end{align*}
  as desired.
\end{proof}

Finally, Lemma~\ref{lem:c1toc2} will show that the orthomorphism sets
from Cases 1 and 2 have the same distribution, and
Lemma~\ref{lem:c1toc3} will show that the orthomorphism sets from Cases
1 and 3 have the same distribution.

\begin{lemma}\label{lem:c1toc2}
  For distinct $i,r,s,t \in \Z$ and $n>1$,
  \[
    \vec{\bf d}(t_t,i_s) = \vec{\bf d}(t_r,r_s)
  \]
\end{lemma}

\begin{proof}
  If $t,r,s,i \in \Z$ are distinct, then
  \begin{align*}
    \vec{\bf d}(t_t,i_s) &= \left(\frac{1}{2^n-2}\right) \vec{\bf d}(i_s) && \text{Lemma }\ref{lem:1fixed}\\
                         &= \left(\frac{1}{2^n-2}\right) \vec{\bf d}(t_r) && \text{Theorem }\ref{thm:l1pe}\\
                         &= \vec{\bf d}(t_r,r_s) && \text{Corollary }\ref{coro:c2decompose}. &&\qedhere
  \end{align*}
\end{proof}

\smallskip

\begin{lemma}\label{lem:c1toc3}
  For distinct $r,s,t \in \Z$ and $n>1$,
  \[
    \vec{\bf d}(t_t,r_s) = \vec{\bf d}(t_r,i_s)
  \]
  for any $i \in \Z\setminus \{t, t+r+s\}$.
\end{lemma}

\begin{proof}
  As in the previous lemma, we argue as follows
  \begin{align*}
    \vec{\bf d}(t_t,r_s) &= \left(\frac{1}{2^n-2}\right) \vec{\bf d}(r_s) && \text{Lemma }\ref{lem:1fixed}\\
                         &= \left(\frac{1}{2^n-2}\right) \vec{\bf d}(t_r) && \text{Theorem }\ref{thm:l1pe}\\
                         &= \vec{\bf d}(t_r,i_s), && 
  \end{align*}
  with the last equality holding: for $i=r$ by Corollary
  \ref{coro:c2decompose}; for all $i \in \Z\setminus\{r,s,t,t+r+s\}$
  by Corollary \ref{coro:c3decompose}; and for $i=s$ by Lemma
  \ref{lem:1fixed}. Therefore,
  $\vec{\bf d}(t_t,r_s) = \vec{\bf d}(t_r,i_s)$ for all
  $i \in \Z\setminus \{t, t+r+s\}$.
\end{proof}

To summarize, we have established the following.

\begin{theorem}\label{thm:len2}
  Suppose $(t_r,i_s) $ and $(t'_{r'},i'_{s'})$ are partial
  orthomorphisms of $\Z$ and $n>1$.  Then
  \[
    \vec{\bf d}(t_r,i_j) = \vec{\bf d}(t'_{r'},i'_{j'}).
  \]
  In other words, the distribution of cycle types of orthomorphisms of
  the group $\Z$ that extend any given partial orthomorphism of size
  two is independent of the particular partial orthomorphism
  considered.
\end{theorem}

\begin{table}[htb]
\centering
\begin{tabular}{l  r }\hline
Cycle Type& Orthomorphism Count\\\hline
1,4,4,7	& 23040\\
1,3,3,3,6	& 3840\\
1,4,5,6	& 57600\\
1,3,4,8	& 74880\\
1,3,12	& 109440\\
1,5,5,5	& 9984\\
1,4,11	& 80640\\
1,3,6,6	& 13440\\
1,15	& 332544\\
1,5,10	& 99072\\
1,7,8	& 92160\\
1,3,3,3,3,3	& 2048\\
1,6,9	& 46080\\
1,3,5,7	& 103680\\
1,3,3,9	& 42240\\
1,3,4,4,4	& 1920\\\hline \hline
total & 1092608 \\ \hline
\end{tabular}
\caption{Cycle type distribution of $\cS(t_r,i_j)$ in $\Z[4]$ when $(t_r,i_j)$ is a partial orthomorphism.}\label{fig:lengthtwo}
\end{table}

As an illustration of Theorem~\ref{thm:len2}, consider the set of
orthomorphisms of $\Z[4]$. For any given partial orthomorphism of size
two, there are 1,092,608 orthomorphisms that extend it. The cycle-type
distribution of this set of orthomorphisms is given in 
Table~\ref{fig:lengthtwo}.


An important consequence of Theorem \ref{thm:len2} is the following corollary.

\begin{corollary}
  Every partial orthomorphism of size two of $\Z$ for $n>1$ can be
  extended to an orthomorphism.
\end{corollary}

\begin{proof}
  Since an orthomorphism exists for each $n>1$ in $\Z$ (see
  \cite{paige}), there exists a partial orthomorphism of size two that
  the orthomorphism extends. So, by Theorem \ref{thm:len2}, every
  partial orthomorphism of size two can be extended to an
  orthomorphism.
\end{proof}

\section{Examples and the case of size three}

\begin{table}[tb]
\centering
\begin{tabular}{l  r r r}\hline
Cycle Type&	$\pi$&	$\sigma$&	$\tau$ \\\hline
1,4,4,7	&1920&	0&	0\\
1,3,3,3,6	&320&	2304&	0\\
1,4,5,6	&4608&	0&	2304\\
1,3,4,8	&5696&	14976&	6528\\
1,3,12	&8768&	21888&	4224\\
1,5,5,5	&768&	0&	768\\
1,4,11	&6400&	0&	3840\\
1,3,6,6	&1024&	2688&	1152\\
1,15	&25600&	0&	25344\\
1,5,10	&7488&	0&	9216\\
1,7,8	&7104&	0&	6912\\
1,3,3,3,3,3	&128&	2048&	512\\
1,6,9	&3840&	0&	0\\
1,3,5,7	&7360&	20736&	15360\\
1,3,3,9	&3072&	16896&	5376\\
1,3,4,4,4	&128&	384&	384\\ \hline \hline
total &84224 &81920 & 84224 \\ \hline
\end{tabular}
\caption{Cycle-type distributions for $\tau$, $\pi$, and $\sigma$ defined in Example \ref{ex:len3}.}\label{fig:example_plot}
\end{table}

\begin{example}\label{ex:len3} As shown in Theorem \ref{thm:len2}, 
  the cycle-type distribution of orthomorphisms that extend partial
  orthomorphisms of size two is independent of the particular partial
  orthomorphism of size two chosen. However, as mentioned earlier, a
  similar statement for partial orthomorphisms of size three does not
  hold. For example, consider the group $\Z[4]$ and let $\pi$,
  $\sigma$, and $\tau$ denote the partial orthomorphisms of size three
  defined below.
\[
\begin{tabular}{c||c|c|c}
  $x$ & $\pi(x)$ & $\sigma(x)$ & $\tau(x)$ \\ \hline \hline
  $0000$ & 0000 & 0001 & 0000 \\
  $0001$ & 0010 & 0010 & 0010 \\
  $0010$ & 0100 & 0000 & 0011 \\
\end{tabular}
\]
There are 84,224 orthomorphisms that extend $\pi$, but there are
81,920 that extend $\sigma$. So the sets of orthomorphisms extending
$\pi$, $\sigma$ do not share the same cardinality, much less the same
distribution of cycle types.

On the other hand, the number of orthomorphisms extending $\tau$ is
also 84,224 which matches $\pi$, and yet these sets have different
cycle-type distributions. See Table \ref{fig:example_plot}.
\end{example}

\section{Cycle-type distributions and partial
  ortho\-morph\-isms of  size three}\label{sec:len3pf}

As illustrated in the previous section, the cycle-type
distributions of orthomorphisms that extend partial orthomorphisms of
size three are not all the same. In this section, we show that, for any $n>2$,
there are at most 12 cycle-type distributions for these
orthomorphisms.

Similar to orthomorphism sets that extend partial orthomorphisms of
size two, a set of 5 basic types of cycle structures arise. We
consider each case separately. In each of the cases displayed in the
following table, we assume the elements in each of the partial
orthomorphisms are distinct.

\begin{center}
\begin{minipage}[c]{0.9\textwidth}
\begin{center}
\begin{tabular}{c c c}
Case  & Orthomorphism Set & Digraph Representation \\ \hline
1 &  $\cS(r_r,t_s,i_t)$ & \begin{tikzpicture}[scale=0.75]
 \foreach \i / \c in {0/r,1/s,2/t,3/i}
 {
   \path (\i,0) coordinate[label=above:{\scriptsize $\c$}] (\c);
   \fill (\c) circle (.5mm);
 }
 \path[shorten >=0.5mm,->] (r) edge  [loop above] node {} ();
 \draw[shorten >=0.5mm,->] (s) -- (t);
 \draw[shorten >=0.5mm,->] (t) -- (i);
\end{tikzpicture}\\
2 &   $\cS(r_r,i_s,j_t)$ & \begin{tikzpicture}[scale=0.75]
 \foreach \i / \c in {0/r,1/s,2/i,3/t,4/j}
 {
   \path (\i,0) coordinate[label=above:{\scriptsize $\c$}] (\c);
   \fill (\c) circle (.5mm);
 }
 \path[shorten >=0.5mm,->] (r) edge  [loop above] node {} ();
 \draw[shorten >=0.5mm,->] (s) -- (i);
 \draw[shorten >=0.5mm,->] (t) -- (j);
\end{tikzpicture}\\
3 &  $\cS(r_t,s_r,t_s)$ & \begin{tikzpicture}[scale=0.75]
 \foreach \i / \c in {0/t,1/r,2/s}
 {
   \path (\i,0) coordinate[label=above:{\scriptsize $\c$}] (\c);
   \fill (\c) circle (.5mm);
 }
 \path[shorten >=0.5mm,->] (s) edge  [bend left] node {} (t);
 \draw[shorten >=0.5mm,->] (t) -- (r);
 \draw[shorten >=0.5mm,->] (r) -- (s);
\end{tikzpicture}\\
4 &  $\cS(i_r,t_s,j_t)$ & \begin{tikzpicture}[scale=0.75]
 \foreach \i / \c in {0/r,1/i,2/s,3/t,4/j}
 {
   \path (\i,0) coordinate[label=above:{\scriptsize $\c$}] (\c);
   \fill (\c) circle (.5mm);
 }
 \draw[shorten >=0.5mm,->] (r) -- (i);
 \draw[shorten >=0.5mm,->] (s) -- (t);
 \draw[shorten >=0.5mm,->] (t) -- (j);
\end{tikzpicture}\\
5 &  $\cS(i_r,j_s,k_t)$ & \begin{tikzpicture}[scale=0.75]
 \foreach \i / \c in {0/r,1/i,2/s,3/j,4/t,5/k}
 {
   \path (\i,0) coordinate[label=above:{\scriptsize $\c$}] (\c);
   \fill (\c) circle (.5mm);
 }
 \draw[shorten >=0.5mm,->] (r) -- (i);
 \draw[shorten >=0.5mm,->] (s) -- (j);
 \draw[shorten >=0.5mm,->] (t) -- (k);
\end{tikzpicture}
\\
\end{tabular}
\end{center}
\end{minipage}%
\begin{minipage}[c]{0.1\textwidth}
$(\ast)$
\end{minipage}
\end{center}

We begin with the following lemma which is the basis for each of the
case arguments in this section.

\begin{lemma}\label{equiv}
Suppose $(i_r,j_s,k_t)$ and $(i'_{r'},j'_{s'},k'_{t'})$ are
partial orthomorphisms of $\Z$. Then
\[
\vec{\bf d}(i_r,j_s,k_t)=\vec{\bf d}(i'_{r'},j'_{s'},k'_{t'})
\]
whenever $(i+r,j+r,s+r,k+r,t+r)$ and $(i'+r',j'+r',s'+r',k'+r',t'+r')$
satisfy the same set of dependence relations.
\end{lemma}

\begin{proof}
  By Theorem \ref{rem:AutStrength}, let $g$ be an automorphism that
  satisfies $g(i+r)=i'+r'$, $g(j+r)=j'+r'$, $g(s+r)=s'+r'$,
  $g(k+r)=k'+r'$, and $g(t+r)=t'+r'$, then apply $C_h$ where
  $h=T_{r'}gT_r$ to $\mathcal{S}(i_r,j_s,k_t)$.
\end{proof}
The apparent distinction of $r$ (and $r'$) relative to the other
parameters in Lemma \ref{equiv} is insignificant, as we see in Remark
\ref{write} below, since many symmetries exist among the parameters.

\begin{remark}\label{write}
Notice that, by construction, the order in which the coordinates are written in the
expression $(i_r,j_s,k_t)$ has no effect on the cycle-type
distribution of $\mathcal{S}(i_r,j_s,k_t)$. That is,
\begin{align*}
\vec{\bf d}(i_r,j_s,k_t)&=\vec{\bf d}(i_{r},k_{t},j_{s}) 
=\vec{\bf d}(j_s,k_t,i_r)\\
&=\vec{\bf d}(j_s,i_r,k_t)
=\vec{\bf d}(k_t,j_s,i_r)
=\vec{\bf d}(k_t,i_r,j_s).
\end{align*}
Additionally, using the inverse map, $R$, presented in Lemma
\ref{reverse} of Section \ref{sec:preserving}, we find
\begin{align*}
\vec{\bf d}(i_r,j_s,k_t)&=\vec{\bf d}(r_{i},s_{j},t_{k}).
\end{align*}
\end{remark}

\medskip

Each of the case arguments in this section have the following
form. With Lemma \ref{equiv}, it is sufficient to examine the
collection of the possible sets of dependence relations on
$\{i+r,j+r,s+r,k+r,t+r\}$ to determine the possible cycle-type
distributions of $\mathcal{S}(i_r,j_s,k_t)$. So, the number of
cycle-type distributions is at most the number of sets of dependence
relations. With the help of the content of Remark \ref{write}, we can
reduce the upper bound on the number of cycle-type distributions
further.

Note that there exist no partial orthomorphisms of $\Z[2]$ that fall
into Cases 2, 4, or 5, as there are only 4 elements in $\Z[2]$ and each
of these cases requires more than 4 distinct elements.  We now proceed with
each of the five cases given in $(\ast)$.

\begin{lemma}[Case 1] 
  Suppose $(r_r,t_s,i_t)$ is a partial orthomorphism for distinct
  $i,r,s,t \in \Z$ and $n>1$. Then $\mathcal{S}(r_r,t_s,i_t)$ has one
  of at most 2 different cycle-type distributions.
\end{lemma}

\begin{proof}
  Note that $\{t+r,s+r,i+r\}$ is linearly dependent if and only if
  $t+r+s+i=0$, since all other possible dependence relations
  contradict the assumption that $(r_r,t_s,i_t)$ is a partial
  orthomorphism and $i,r,s,t$ are distinct. The statement then follows
  from Lemma \ref{equiv}.
\end{proof}

\begin{lemma}[Case 2]
  Suppose $(r_r,i_s,j_t)$ is a partial orthomorphism for distinct $i$,
  $j$, $r$, $s$, $t \in \Z$ and $n>2$. Then $\mathcal{S}(r_r,i_s,j_t)$
  has one of at most 2 different cycle-type distributions.
\end{lemma}

\begin{proof}
  By Lemma \ref{equiv}, it is sufficient to examine the possible sets
  of dependence relations on the set $\{i+r,s+r,j+r,t+r\}$ to
  determine the possible cycle-type distributions of
  $\mathcal{S}(r_r,i_s,j_t)$. If $\{i+r,s+r,j+r,t+r\}$ is linearly
  dependent and $(r_r,i_s,j_t)$ is a partial orthomorphism for distinct
  $i,j,r,s,t$, then one of the following is true: (a) $r+s+t+i=0$, (b)
  $r+s+t+j=0$, (c) $r+s+i+j=0$, (d) $r+t+i+j=0$. By Remark
  \ref{write}, an orthomorphism set in Case 2 that satisfies equation
  (a) has the same cycle-type distribution as a set that satisfies
  equation (b). Similarly for sets that satisfy (c) and (d). By Lemma
  \ref{reverse}, an orthomorphism set that satisfies equation (a) has
  the same cycle-type distribution as a set that satisfies equation
  (c). Thus, there are two possible cycle-type distributions for
  orthomorphism sets in Case 2 distinguished by whether the set
  $\{i+r,s+r,j+r,t+r\}$ is linearly dependent or not.
\end{proof}


\begin{lemma}[Case 3]
  Suppose $(r_t,s_r,t_s)$ is a partial orthomorphism for distinct
  $r,s,t \in \Z$ and $n>1$. Then $\mathcal{S}(r_t,s_r,t_s)$ shares one
  common cycle-type distribution.
\end{lemma}

\begin{proof}
  Since $(r_t,s_r,t_s)$ is a partial orthomorphism for distinct
  $r,s,t$, the set $\{s+r,t+r\}$ is linearly independent. The stated
  lemma follows from Lemma \ref{equiv}.
\end{proof}


\begin{lemma}[Case 4]
  Suppose $(i_r,t_s,j_t)$ is a partial orthomorphism for distinct
  $i,j,r,s,t \in \Z$ and $n>2$. Then $\mathcal{S}(i_r,t_s,j_t)$ has
  one of at most 3 different cycle-type distributions.
\end{lemma}

\begin{proof}
  By Lemma \ref{equiv}, it is sufficient to examine the possible sets
  of dependence relations on the set $\{i+r,s+r,t+r,j+r\}$ to
  determine the possible cycle-type distributions of
  $\mathcal{S}(i_r,t_s,j_t)$.  If $\{i+r,s+r,t+r,j+r\}$ is linearly
  dependent and $(i_r,t_s,j_t)$ is a partial orthomorphism for distinct
  $i,j,r,s,t$, then one of the following is true: (a) $s+t+i+j=0$, (b)
  $r+s+t+j=0$, (c) $r+s+i+j=0$. By Lemma \ref{reverse}, an
  orthomorphism set in Case 4 that satisfies equation (a) has the same
  cycle-type distribution as a set that satisfies equation (b). Thus,
  there are at most three possible cycle-type distributions for
  orthomorphism sets in Case 4: two when $\{i+r,s+r,j+r,t+r\}$ is
  linearly dependent and one when $\{i+r,s+r,j+r,t+r\}$ is linearly
  independent.
\end{proof}


\begin{lemma}[Case 5]
  Suppose $(i_r,j_s,k_t)$ is a partial orthomorphism for distinct $i$,
  $j$, $k$, $r$, $s$, $t \in \Z$ and $n>2$. Then
  $\mathcal{S}(i_r,j_s,k_t)$ has one of at most 4 different cycle-type
  distributions.
\end{lemma}

\begin{proof}
  By Lemma \ref{equiv}, it is sufficient to examine the possible sets
  of dependence relations on the set $\{i+r,j+r,s+r,k+r,t+r\}$ to
  determine the possible cycle-type distributions of
  $\mathcal{S}(i_r,j_s,k_t)$. There are 14 possible sets of linear
  relations on $\{i+r,j+r,s+r,k+r,t+r\}$ when $(i_r,j_s,k_t)$ is
  a partial orthomorphism and $i,j,r,s,t \in \Z$ are distinct.  Two of
  the sets of relations correspond to the set
  $\{i+r,j+r,s+r,k+r,t+r\}$ being linearly independent, and the
  dependence relation $r+s+t+i+j+k=0$. We show the remaining 12 sets
  of relations reduce to orthomorphism sets with just two different
  cycle-type distributions by first grouping the single-element relation
  sets in the following way.
\[%begin{displaymath}
\begin{array}{l r}
  \left.
  \begin{array}{l}
    \left.
    \begin{array}{rl}
      i+s+j+k&=0 \\
      i+t+j+k&=0 \\
      i+j+k+r&=0 
    \end{array} 
    \right\}\text{\footnotesize Type 1a}\vspace{2mm}\\
    
    \left.
   \begin{array}{rl}
      r+i+s+t&=0 \\
      r+j+s+t&=0 \\
      r+s+k+t&=0 
    \end{array}
    \right\}\text{\footnotesize Type 1b}%\vspace{2mm}
  \end{array}
  \right\} \text{\footnotesize Type 1}%\vspace{2mm}
&

  \left.
  \begin{array}{rl}
    i+j+s+t&=0 \\
    i+s+t+k&=0 \\
    r+i+t+j&=0 \\
    r+i+s+k&=0 \\
    r+j+s+k&=0 \\
    r+j+k+t&=0 
  \end{array}
  \right\}\text{\footnotesize Type 2}%\vspace{2mm}
\end{array}
\]%end{displaymath}

For the equations of Type 1a, we may relabel the elements in
$(i_r,j_s,k_t)$ and use Remark \ref{write} to show
$\vec{\bf d}(i_r,j_s,k_t)$ is the same for each line. A similar
argument holds for the equations of Type 1b and equations of Type
2. To show orthomorphism sets with relations of Type 1a and Type 1b
have the same cycle-type distribution, we may relabel the
elements in $(i_r,j_s,k_t)$ and use Lemma \ref{reverse}.

Thus, there are at most four possible cycle-type distributions for
orthomorphism sets in Case 5.
\end{proof}

\begin{table}[htp!]
\centering
\begin{tabular}{l r r r r r}\hline
  Cycle Type        & $(0_0,2_1,3_2)$ & $(0_0,2_1,8_4)$ & $(1_0,2_1,0_2)$ & $(1_0,4_2,3_4)$ & $(1_0,4_2,6_4)$ \\ \hline
  1,4,4,7     &               0 &            1920 &               0 &            1920 &            1920 \\
  1,3,3,3,6   &               0 &             320 &            2304 &             128 &             320 \\
  1,4,5,6     &            2304 &            4896 &               0 &            4800 &            4608 \\
  1,3,4,8     &            6528 &            6512 &           14976 &            4992 &            5696 \\
  1,3,12      &            4224 &            9296 &           21888 &            7296 &            8768 \\
  1,5,5,5     &             768 &             864 &               0 &             832 &             768 \\
  1,4,11      &            3840 &            6880 &               0 &            6720 &            6400 \\
  1,3,6,6     &            1152 &            1168 &            2688 &             896 &            1024 \\
  1,15        &           25344 &           28768 &               0 &           27712 &           25600 \\
  1,5,10      &            9216 &            8640 &               0 &            8256 &            7488 \\
  1,7,8       &            6912 &            7968 &               0 &            7680 &            7104 \\
  1,3,3,3,3,3 &             512 &             192 &            2048 &               0 &             128 \\
  1,6,9       &               0 &            3840 &               0 &            3840 &            3840 \\
  1,3,5,7     &           15360 &            9280 &           20736 &            6912 &            7360 \\
  1,3,3,9     &            5376 &            3744 &           16896 &            2112 &            3072 \\
  1,3,4,4,4   &             384 &             176 &             384 &             128 &             128 \\ \hline \hline
total & 81920 & 94464 & 81920 & 84224 & 84224 \\ \hline
\end{tabular}

\bigskip

\bigskip

\begin{tabular}{l r r r r} \hline
  Cycle Type        & $(1_0,4_2,8_4)$ & $(1_0,8_2,4_3)$ & $(1_0,8_2,3_4)$ & $(1_0,8_2,12_7)$\\ \hline
  1,4,4,7     &            1920 &            2072 &            1768 &             1920\\             
  1,3,3,3,6   &             368 &             288 &             304 &              416\\             
  1,4,5,6     &            4848 &            5088 &            4464 &             4800\\             
  1,3,4,8     &            6688 &            6392 &            5640 &             6864\\             
  1,3,12      &            9664 &            9184 &            8512 &            10032\\             
  1,5,5,5     &             848 &             872 &             776 &              832\\             
  1,4,11      &            6800 &            7016 &            6344 &             6720\\             
  1,3,6,6     &            1200 &            1160 &            1000 &             1232\\             
  1,15        &           28240 &           29216 &           25680 &            27712\\             
  1,5,10      &            8448 &            8520 &            7800 &             8256\\             
  1,7,8       &            7824 &            7920 &            7296 &             7680\\             
  1,3,3,3,3,3 &             224 &             144 &             144 &              256\\             
  1,6,9       &            3840 &            4032 &            3648 &             3840\\             
  1,3,5,7     &            9392 &            8816 &            7712 &             9504\\             
  1,3,3,9     &            3984 &            3584 &            2992 &             4224\\             
  1,3,4,4,4   &             176 &             160 &             144 &              176\\       \hline \hline
total &  94464 & 94464 & 84224 & 94464 \\ \hline
\end{tabular}
\caption{\label{fig:nisfour}Cycle type distributions realized for 9 representative partial orthomorphisms of size three of $\Z[4]$.}
\end{table}

With the lemmas above, we are now ready to prove our result concerning
partial orthomorphisms of size 3.

\begin{theorem}
  For any integer $n>2$, the set of orthomorphisms of the group $\Z$
  that extend any given partial orthomorphism of size three has one
  of at most 12 different cycle-type distributions.
\end{theorem}

For small values of $n$, not all cycle-type distributions are
realized. For $n=1$, there exist no orthomorphisms. For $n=2$, there
is only one possible cycle-type distribution for the set of all
orthomorphisms that extend a particular partial orthomorphism of size
three, since there is only one orthomorphism that extends any partial
orthomorphism of size three, and all orthomorphisms of $\Z[2]$ have
cycle-type 1,3.

As in the case when $n=2$, it turns out for $n=3$ there is only one
cycle-type distribution for the set of all orthomorphisms that extend
any particular partial orthomorphism of size three. For $n=4$, there
are 9 different cycle-type distributions realized. See Table
\ref{fig:nisfour} for 9 representative partial orthomorphisms of size
3 and their cycle-type distributions, where we use the notation
$2^3i_3+2^2i_2+2i_1+i_0 \in \mathbb{Z}$ for
$(i_3,i_2,i_1,i_0) \in \Z$. Values of $n$ greater than 4 have yet to
be studied computationally in this context, as working with
orthomorphisms of this group is infeasible with current knowledge and
technologies. Hopefully, future research will better illuminate the
structure of orthomorphisms for larger values of~$n$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Acknowledgements}
The authors would like to thank the
anonymous referees for a number of helpful suggestions.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\bibliographystyle{plain} 
%\bibliography{refs}

\begin{thebibliography}{10}

\bibitem{cavenagh}
Nicholas~J. Cavenagh, Carlo H{\"a}m{\"a}l{\"a}inen, and Adrian~M. Nelson.
\newblock On completing three cyclically generated transversals to a Latin
  square.
\newblock {\em Finite Fields and Their Applications}, 15(3):294--303, 2009.

\bibitem{genlinorthos}
Zong~Duo Dai, Solomon~W. Golomb, and Guang Gong.
\newblock Generating all linear orthomorphisms without repetition.
\newblock {\em Discrete Mathematics}, 205(1):47--55, 1999.

\bibitem{dummitfoote}
David~S. Dummit and Richard~M. Foote.
\newblock {\em Abstract Algebra}.
\newblock Prentice Hall Englewood Cliffs, 3rd edition, 2004.

\bibitem{euler}
Leonhard Euler.
\newblock {\em Recherches sur une nouvelle espece de quarr{\'e}s magiques}.
\newblock Zeeuwsch Genootschao, 1782.

\bibitem{balancedperm}
Shoni Gilboa and Shay Gueron.
\newblock Balanced permutations {Even-Mansour} ciphers.
\newblock Cryptology ePrint Archive, Report 2014/642, 2014.

\bibitem{genorthos}
Solomon~W. Golomb, Guang Gong, and Lothrop Mittenthal.
\newblock Constructions of orthomorphisms of $\Z$.
\newblock In {\em Finite Fields and Applications: Proceedings of The Fifth
  International Conference on Finite Fields and Applications}, page 178.
  Springer Science \& Business Media, 2001.

\bibitem{gruttmuller}
Martin Gr{\"u}ttm{\"u}ller.
\newblock Completing partial Latin squares with two cyclically generated
  prescribed diagonals.
\newblock {\em Journal of Combinatorial Theory, Series A}, 103(2):349--362,
  2003.

\bibitem{JDMpaper}
Diane~M. Johnson, {A. Lloyd} Dulmage, and {Nathan S.} Mendelsohn.
\newblock Orthomorphisms of groups and orthogonal Latin squares.
\newblock {\em Canadian Journal of Mathematics}, 13:356--372, 1961.

\bibitem{FOX}
Pascal Junod and Serge Vaudenay.
\newblock Fox: a new family of block ciphers.
\newblock In {\em The 11th International Workshop on Selected Areas in
  Cryptography}, volume 3357, pages 114--129, 2004.

\bibitem{lothrop}
Lothrop Mittenthal.
\newblock Block substitutions using orthomorphic mappings.
\newblock {\em Advances in Applied Mathematics}, 16(1):59--71, 1995.

\bibitem{paige}
{Lowell J.} Paige.
\newblock A note on finite abelian groups.
\newblock {\em Bulletin of the American Mathematical Society}, 53(6):590--593,
  1947.

\bibitem{poole}
David Poole.
\newblock {\em Linear Algebra: A Modern Introduction}.
\newblock Cengage Learning, 3rd edition, 2014.

\bibitem{stones}
Douglas~S. Stones and Ian~M. Wanless.
\newblock Compound orthomorphisms of the cyclic group.
\newblock {\em Finite Fields and Their Applications}, 16(4):277--289, 2010.

\bibitem{wanless}
{Ian M.} Wanless.
\newblock Transversals in Latin squares: a survey.
\newblock In Robin Chapman, editor, {\em Surveys in Combinatorics 2011}, pages
  403 -- 437. Cambridge University Press, 2011.

\bibitem{laimassey}
Aaram Yun, Je~Hong Park, and Jooyoung Lee.
\newblock {Lai-Massey} scheme and {quasi-Feistel} networks.
\newblock Cryptology ePrint Archive, Report 2007/347, 2007.

\end{thebibliography}

\end{document}
