# Multiple Contractions of Permutation Arrays

Carmen Amarra  Institute of Mathematics, University of the Philippines
Diliman, 1101 Quezon City, Philippines<EMAIL_ADDRESS>,  Dom Vito
A. Briones  Institute of Mathematics, University of the Philippines Diliman,
1101 Quezon City, Philippines<EMAIL_ADDRESS>and  Manuel Joseph C.
Loquias  Institute of Mathematics, University of the Philippines Diliman, 1101
Quezon City, Philippines<EMAIL_ADDRESS>
###### Abstract.

Given a permutation $\sigma$ on $n$ symbols $\\{0,1,\ldots,n-1\\}$ and an
integer $1\leq m\leq n-1$, the $m$th contraction of $\sigma$ is the
permutation $\sigma^{{\footnotesize\sf CT}^{m}}$ on $n-m$ symbols obtained by
deleting the symbols $n-1,n-2,\ldots,n-m$ from the cycle decomposition of
$\sigma$. The Hamming distance ${\rm hd}(\sigma,\tau)$ between two
permutations $\sigma$ and $\tau$ is the number of symbols $x$ such that
$\sigma(x)\neq\tau(x)$. In this paper we give a complete characterization of
the effect of a single contraction on the Hamming distance between two
permutations. This allows us to obtain sufficient conditions for ${\rm
hd}(\sigma,\tau)-{\rm hd}(\sigma^{{\footnotesize\sf
CT}^{m}},\tau^{{\footnotesize\sf CT}^{m}})\leq 2m$.

###### Key words and phrases:

Permutation Arrays, Hamming distance, Contraction, AGL(1,q), PGL(2,q)

###### 2010 Mathematics Subject Classification:

05A05, 94B25, 94B65

##  1\. Introduction

A _permutation array_ on $n$ symbols is a non-empty subset of the symmetric
group $S_{n}$ on the $n$ symbols $\\{0,1,\ldots,n-1\\}$. The _Hamming
distance_ ${\rm hd}(\sigma,\tau)$ between two permutations $\sigma$ and $\tau$
in $S_{n}$ is the number of symbols $x$ such that $\sigma(x)\neq\tau(x)$, and
the Hamming distance of a permutation array $P$ is the minimum among all
Hamming distances between pairs of distinct permutations in $P$. For positive
integers $n$ and $d$, $M(n,d)$ denotes the maximum size of a permutation array
on $n$ symbols with Hamming distance $d$.

The value of $M(n,d)$ for arbitrary $n$ and $d$ remains unsolved. Among the
known general lower bounds for $M(n,d)$ are the Gilbert-Varshamov bound [8]
and $M(n,d)\geq n!/q^{d-2}$, where $q\geq n$ is a prime power [10]. For some
special cases, exact values were obtained using combinatorial techniques [6]
or permutation group theory [8]. For instance, results from [8, 12] tell us
that for prime powers $q$, $M(q,q-1)=q(q-1)$ and $M(q+1,q-1)=q(q+1)(q-1)$. In
addition to this, methods for constructing permutation arrays that yield lower
bounds for $M(n,d)$, for certain $n$ and $d$, have also been developed. These
include the method of partitions and extensions [4], permutation polynomials
[5], coset search algorithms [1], rational polynomials [2], and clique search
and the use of automorphisms or isometries [11, 5, 9].

In [1], Bereg et al. introduced the method of contraction to obtain a new
permutation array from a given one. The _contraction_ of a permutation
$\sigma$ in $S_{n}$ is the permutation $\sigma^{{\footnotesize\sf CT}}$ in
$S_{n-1}$ obtained by deleting the symbol $n-1$ from the disjoint cycle
notation of $\sigma$. Taking the contraction of each permutation in a
permutation array $P$ yields the contraction $P^{{\footnotesize\sf CT}}$ of
$P$. Bereg et al. examined the effect of contraction on the Hamming distance
of a given permutation array. They found that the Hamming distance between any
two permutations can decrease by at most $3$ after one contraction, and they
provided necessary and sufficient conditions in order for the decrease in
Hamming distance to be equal to $3$. Moreover, they gave sufficient conditions
for the Hamming distance between two permutations to decrease by $2$ after one
contraction and to decrease by at most $4$ after two contractions. They
applied their results to the affine general linear group and the projective
general linear group to yield lower bounds for $M(n,d)$ where $(n,d)$ is of
the form $(q,q-3)$ or $(q-1,q-3)$, where $q$ is a prime power such that
$3\nmid(q-1)$, and of the form $(q-2,q-5)$, where $q$ is a prime power such
that $q\equiv 2\allowbreak\mkern 10.0mu({\operator@font mod}\,\,3)$ and
$q\not\equiv 0,1\allowbreak\mkern 10.0mu({\operator@font mod}\,\,5)$. In [3],
lower bounds for $M(n,d)$ were obtained for the case where $(n,d)$ is either
$(q,q-3)$ or $(q-1,q-3)$ for some prime power $q\equiv 1\allowbreak\mkern
10.0mu({\operator@font mod}\,\,3)$, using contraction graphs of certain
permutation arrays. These are graphs whose vertices are the elements of the
permutation array, with adjacency defined using conditions on the Hamming
distance of two permutations and the Hamming distance of their contractions.
Furthermore, Bereg et. al. derived other lower bounds using contractions of
permutations obtained from permutation rational functions [2]. These works
suggest that contraction, used in combination with other computational
methods, is a useful tool in deriving lower bounds for $M(n,d)$.

This paper extends the combinatorial work in [1] on the effect of contraction
on the Hamming distance between two permutations. In particular, we identify
necessary and sufficient conditions for ${\rm hd}(\sigma,\tau)-{\rm
hd}(\sigma^{{\footnotesize\sf CT}},\tau^{\footnotesize\sf CT})=d$ for each
$d\in\\{0,1,2,3\\}$. Moreoever, we consider the effect of more than two
contractions on the Hamming distance of a permutation array. Our main result
is Theorem 5.2, which gives a lower bound for the Hamming distance between the
$m$th contractions $\sigma^{{\footnotesize\sf CT}^{m}}$ and
$\tau^{{\footnotesize\sf CT}^{m}}$ of two permutations $\sigma$ and $\tau$.

######  Theorem 5.2.

Let $\sigma,\tau\in S_{n}$ with ${\rm hd}(\sigma,\tau)=d$. Let
$m\in\\{1,\ldots,n-1\\}$ and assume that the disjoint cycle decomposition of
$\sigma^{-1}\tau$ has no factor of odd length $\ell$ where $3\leq\ell\leq
2m+1$. Then ${\rm hd}\big{(}\sigma^{{\footnotesize\sf
CT}^{m}},\tau^{{\footnotesize\sf CT}^{m}}\big{)}\geq d-2m$.

Applying Theorem 5.2 to the group ${\rm PGL}(2,q)$ for prime powers $q$ yields
new lower bounds for $M(q-1,q-5)$, which we show in Table 6. Other lower
bounds we obtain are improvements on the Gilbert-Varshamov bound [8] and the
bound $M(n,d)\geq n!/q^{d-2}$ in [10], but not of some of the other current
best lower bounds [5, 11, 1, 2].

The rest of this paper is organized as follows: In Section 2 we define the
contraction of a permutation and give its basic properties. Next, we consider
the contraction $P^{{\footnotesize\sf CT}}$ of a given permutation array $P$
in Section 3, and compare its size and Hamming distance with that of $P$. In
Section 4, we determine necessary and sufficient conditions for each possible
value of ${\rm hd}(\sigma,\tau)-{\rm hd}(\sigma^{{\footnotesize\sf
CT}},\tau^{{\footnotesize\sf CT}})$, for any two distinct permutations
$\sigma$ and $\tau$. We push further in Section 5 and consider the $m$th
contraction $P^{{\footnotesize\sf CT}^{m}}$ of a given permutation array $P$
for any $m$, and use the results of the previous sections to compare its size
and Hamming distance with that of $P$. We conclude the paper in Section 6 by
putting in context the lower bounds obtained in Section 5.

##  2\. Preliminaries

We consider the symmetric group $S_{n}$ on the $n$ symbols
$\\{0,1,\ldots,n-1\\}$. We adopt the convention that compositions of
permutations are computed from left to right. That is, given $\sigma,\tau\in
S_{n}$ and $x\in\\{0,\ldots,n-1\\}$, $\tau\sigma(x):=\sigma(\tau(x))$. The
support of a permutation $\sigma\in S_{n}$ is
$\operatorname{supp}(\sigma)=\\{x\in\\{0,\ldots,n-1\\}\,:\,\sigma(x)\neq
x\\}$.

A _permutation array_ on $n$ elements is a non-empty subset of $S_{n}$. The
_Hamming distance_ ${\rm hd}(\sigma,\tau)$ between permutations
$\sigma,\tau\in S_{n}$ is

${\rm
hd}(\sigma,\tau)=|\\{x\in\\{0,\ldots,n-1\\}\,:\,\sigma(x)\neq\tau(x)\\}|.$

The Hamming distance ${\rm hd}(P)$ of a permutation array $P$ is given by

${\rm hd}(P)=\min\\{{\rm hd}(\sigma,\tau)\,:\,\sigma,\tau\in
P,\;\sigma\neq\tau\\}.$

We denote by $M(n,d)$ the maximum size of a permutation array on $n$ symbols
with Hamming distance $d$.

Permutation arrays with maximum possible size can be obtained from groups
which act on sets in a particular way. A group $G$ acting on a set $X$ is said
to be _sharply $k$-transitive_ (for some positive integer $k\leq|X|$) if it
has a single orbit on the set of all ordered $k$-tuples of distinct elements
of $X$, and if only the identity element fixes any such $k$-tuple. It was
shown in [8] that a group acting sharply $k$-transitively on a set of $n$
elements has Hamming distance $d=n-k+1$ and has the maximum possible size
$M(n,d)$. The sharply $k$-transitive groups are all known: they exist only for
$k\leq 5$, and the only examples are a few infinite families and some
sporadics such as the Mathieu groups [7]. In particular, apart from a finite
number of examples, the only sharply $2$-transitive groups are the one-
dimensional affine groups ${\rm AGL}(1,q)$ in their natural action on the
field ${\rm GF}(q)$ of order $q$. Hence, for any prime power $q$,

$M(q,q-1)=q(q-1).$

There are two infinite families of sharply $3$-transitive groups, all of which
arise from finite fields: one is ${\rm PGL}(2,q)$ in its natural action on the
points of the projective line ${\rm PG}(1,q)={\rm GF}(q)\cup\\{\infty\\}$. For
odd prime powers $q$ there is a second family of sharply $3$-transitive
groups: a group also of order $q(q+1)(q-1)$ but is not permutation isomorphic
to ${\rm PGL}(2,q)$ acting on ${\rm PG}(1,q)$ [7]. Thus, for any prime power
$q$,

$M(q+1,q-1)=q(q+1)(q-1).$

The _contraction_ of $\sigma\in S_{n}$ is the permutation
$\sigma^{{\footnotesize\sf CT}}\in S_{n-1}$ defined by

$\sigma^{{\footnotesize\sf CT}}(x)=\begin{cases}\sigma(n-1)&\text{if
}x=\sigma^{-1}(n-1),\\\ \sigma(x)&\text{otherwise.}\end{cases}$

If $\sigma$ is a cycle that fixes $n-1$, then $\sigma^{{\footnotesize\sf
CT}}=\sigma$. On the other hand, if $\sigma$ is the cycle $(a_{1}\ a_{2}\
\cdots\ a_{k-1}\ n-1)$ for some
$a_{1},a_{2},\ldots,a_{k-1}\in\\{0,\ldots,n-2\\}$ then
$\sigma^{{\footnotesize\sf CT}}$ is the cycle $(a_{1}\ a_{2}\ \cdots\
a_{k-1})$ in $S_{n-1}$ obtained by deleting $n-1$ from $\sigma$. More
generally, if $\sigma$ has disjoint cycle decomposition
$\sigma_{1}\sigma_{2}\cdots\sigma_{k}$ then $\sigma^{{\footnotesize\sf
CT}}=\sigma_{1}^{{\footnotesize\sf CT}}\sigma_{2}^{{\footnotesize\sf
CT}}\cdots\sigma_{k}^{{\footnotesize\sf CT}}$. Observe that there is nothing
special about the symbol $n-1$ insofar as we may contract with respect to any
of the symbols in $\\{0,1,\ldots,n-1\\}$ (cf. [3]). For the purposes of this
paper, we shall always contract a permutation array $P\subseteq S_{n}$ with
respect to the symbol $n-1$.

Lemma 2.1 can be easily deduced from the definition above.

######  Lemma 2.1.

For any $\sigma\in S_{n}$, $\left(\sigma^{{\footnotesize\sf
CT}}\right)^{-1}=\left(\sigma^{-1}\right)^{{\footnotesize\sf CT}}$.

###### Proof.

It suffices to consider cycles $\sigma$ which does not fix $n-1$, say,
$\sigma=(a_{1}\ a_{2}\ \cdots\ a_{k-1}\ n-1)$ for some
$a_{1},a_{2},\ldots,a_{k-1}\in\\{0,\ldots,n-2\\}$. We have

$\left(\sigma^{{\footnotesize\sf CT}}\right)^{-1}=(a_{1}\ a_{k-1}\ a_{k-2}\
\cdots\ a_{2})=\left(\sigma^{-1}\right)^{{\footnotesize\sf CT}}.\qed$

For any $\sigma\in S_{n}$ and integer $m$ with $1\leq m\leq n-1$,

$\sigma^{{\footnotesize\sf CT}^{m}}:=\left(\sigma^{{\footnotesize\sf
CT}^{m-1}}\right)^{{\footnotesize\sf CT}}$

and for any $P\subseteq S_{n}$,

$P^{{\footnotesize\sf CT}^{m}}:=\left\\{\sigma^{{\footnotesize\sf
CT}^{m}}\,:\,\sigma\in P\right\\}.$

Bereg et al. gave a bound on the change in Hamming distance between two
permutations after contraction, and in addition provided necessary and
sufficient conditions for some cases. These can be found in the observations
in the discussion leading to the statement of [1, Lemma 4], and in the
statement itself. We collect all of these in Lemma 2.2.

######  Lemma 2.2.

[1] The following hold for any $\sigma,\tau\in S_{n}$.

  1. (1)

${\rm hd}(\sigma,\tau)-{\rm hd}\left(\sigma^{{\footnotesize\sf
CT}},\tau^{{\footnotesize\sf CT}}\right)\leq 3$

  2. (2)

The equation ${\rm hd}(\sigma,\tau)-{\rm hd}\left(\sigma^{{\footnotesize\sf
CT}},\tau^{{\footnotesize\sf CT}}\right)=3$ holds if and only if the cycle

$\rho=\big{(}n-1,\ \sigma(n-1),\ \tau(n-1)\big{)}$

is a factor in the disjoint cycle decomposition of $\sigma^{-1}\tau$.
Furthermore, $\left(\sigma^{{\footnotesize\sf
CT}}\right)^{-1}\tau^{{\footnotesize\sf CT}}=\sigma^{-1}\tau\rho^{-1}$.

  3. (3)

If ${\rm hd}(\sigma,\tau)-{\rm hd}(\sigma^{{\footnotesize\sf
CT}},\tau^{{\footnotesize\sf CT}})=2$ then

    1. a.

$\sigma^{-1}\tau(n-1)\neq n-1$, and

    2. b.

if $\pi$ is the cycle containing $n-1$ in the disjoint cycle decomposition of
$\sigma^{-1}\tau$, then the disjoint cycle decomposition of
$(\sigma^{{\footnotesize\sf CT}})^{-1}\tau^{{\footnotesize\sf CT}}$ is the
same as that of $\sigma^{-1}\tau$ except that $\pi$ is replaced by the cycle
obtained by removing from $\pi$ the symbols $n-1$ and one of $\pi(n-1)$ or
$\pi^{-1}(n-1)$.

The following theorem is a consequence of Lemma 2.2.

######  Theorem 2.3.

[1, Theorem 3] Let $P\subseteq S_{n}$ be a permutation array with Hamming
distance $d$. Then the following hold:

  1. (1)

${\rm hd}\Big{(}P^{{\footnotesize\sf CT}^{2}}\Big{)}\geq d-6$;

  2. (2)

if for any $\sigma,\tau\in P$ the disjoint cycle decomposition of
$\sigma^{-1}\tau$ has no cycles of length $3$ or $5$, then ${\rm
hd}\Big{(}P^{{\footnotesize\sf CT}^{2}}\Big{)}\geq d-4$.

Applying Theorem 2.3 to the permutation arrays $P^{{\footnotesize\sf CT}^{2}}$
for $P={\rm AGL}(1,q)$, and to $P^{{\footnotesize\sf CT}}$ for $P={\rm
PGL}(2,q)$, yields the following corollary.

######  Corollary 2.4.

[1, Corollary 4, Corollary 5, and Theorem 4] Let $q$ be a prime power.

  1. (1)

If $q\not\equiv 1\allowbreak\mkern 10.0mu({\operator@font mod}\,\,3)$ then

$M(q-1,\,q-3)\geq q^{2}-1$

and

$M(q,\,q-3)\geq(q+1)q(q-1).$

  2. (2)

If $q\equiv 2\allowbreak\mkern 10.0mu({\operator@font mod}\,\,3)$ and
$q\not\equiv 0,1\allowbreak\mkern 10.0mu({\operator@font mod}\,\,5)$ then

$M(q-2,\,q-5)\geq q(q-1).$

##  3\. The order and Hamming distance of $P^{{\footnotesize\sf CT}}$

Clearly $|P^{{\footnotesize\sf CT}}|\leq|P|$; we have $|P^{{\footnotesize\sf
CT}}|<|P|$ exactly when there are two distinct permutations $\sigma$ and
$\tau$ in $P$ with $\sigma^{{\footnotesize\sf CT}}=\tau^{{\footnotesize\sf
CT}}$. Theorem 3.1 gives an easy sufficient condition in order for the $m$th
contraction of $P$ to have the same order as $P$.

######  Theorem 3.1.

Let $P\subseteq S_{n}$ be a permutation array with Hamming distance $d$. Then
$|P^{{\footnotesize\sf CT}^{m}}|=|P|$ for any positive integer $m<d/3$.

###### Proof.

By Lemma 2.2.1, ${\rm hd}\big{(}\sigma^{{\footnotesize\sf
CT}},\tau^{{\footnotesize\sf CT}}\big{)}\geq{\rm hd}(\sigma,\tau)-3$ for any
$\sigma,\tau\in P$. As such, ${\rm hd}(\sigma^{{\footnotesize\sf
CT}^{m}},\tau^{{\footnotesize\sf CT}^{m}})\geq{\rm hd}(\sigma,\tau)-3m\geq
d-3m>0$ for any integer $m<d/3$. Hence $|P^{{\footnotesize\sf CT}^{m}}|=|P|$
for all such $m$, as required. ∎

Next we consider the effect of the contraction operation on the Hamming
distance of a permutation array. The Hamming distance may increase or
decrease, as illustrated in the next example.

######  Example 3.2.

Let $P_{1}=\\{(0),(1\ 4),(0\ 1\ 2),(1\ 2\ 3)\\}\subseteq S_{5}$. We obtain
$P_{1}^{{\footnotesize\sf CT}}=\\{(0),(0\ 1\ 2),(1\ 2\ 3)\\}\subseteq S_{4}$,
and ${\rm hd}\big{(}P_{1}^{{\footnotesize\sf CT}}\big{)}=3>2={\rm hd}(P_{1})$.

Now consider $P_{2}=\\{(0\ 1\ 2),(1\ 3\ 2)\\}\subseteq S_{4}$. Then
$P_{2}^{{\footnotesize\sf CT}}=\\{(0\ 1\ 2),(1\ 2)\\}\subseteq S_{3}$. Notice
in this case that ${\rm hd}\big{(}P_{2}^{{\footnotesize\sf
CT}}\big{)}=2<3={\rm hd}(P_{2})$.

Theorem 3.3 gives a necessary and sufficient condition for the Hamming
distance of a permutation array to increase after contraction.

######  Theorem 3.3.

Let $P$ be a permutation array with ${\rm hd}(P)=d$ and $|P^{{\footnotesize\sf
CT}}|\geq 2$. Then ${\rm hd}\big{(}P^{{\footnotesize\sf CT}}\big{)}>{\rm
hd}(P)$ if and only if the following conditions hold:

  1. (1)

any $\sigma,\tau\in P$ with ${\rm hd}(\sigma,\tau)=d$ satisfy
$\sigma^{{\footnotesize\sf CT}}=\tau^{{\footnotesize\sf CT}}$; and

  2. (2)

any $\sigma,\tau\in P$ with ${\rm hd}(\sigma,\tau)>d$ satisfy ${\rm
hd}\big{(}\sigma^{{\footnotesize\sf CT}},\tau^{{\footnotesize\sf
CT}}\big{)}>d$ or $\sigma^{{\footnotesize\sf CT}}=\tau^{{\footnotesize\sf
CT}}$.

###### Proof.

Suppose conditions (1) and (2) hold. Let $\pi$ and $\rho$ be distinct
permutations in $P^{{\footnotesize\sf CT}}$, and let $\sigma,\tau\in P$ such
that $\sigma^{{\footnotesize\sf CT}}=\pi$ and $\tau^{{\footnotesize\sf
CT}}=\rho$. Since ${\rm hd}(P)=d$, we then have ${\rm hd}(\sigma,\tau)\geq d$.
However, ${\rm hd}(\sigma,\tau)\neq d$, because otherwise, $\pi=\rho$ by (1).
Thus ${\rm hd}(\sigma,\tau)>d$ and we obtain from (2) that ${\rm
hd}(\pi,\rho)>d$ by (2) . Since $\pi$ and $\rho$ are arbitrary it follows that
${\rm hd}\big{(}P^{{\footnotesize\sf CT}}\big{)}>d$.

For the other direction, assume first that (1) does not hold. Then there are
permutations $\sigma,\tau\in P$ with ${\rm hd}(\sigma,\tau)=d$ and
$\sigma^{{\footnotesize\sf CT}}\neq\tau^{{\footnotesize\sf CT}}$. This implies
that

${\rm hd}\big{(}P^{{\footnotesize\sf CT}}\big{)}\leq{\rm
hd}\big{(}\sigma^{{\footnotesize\sf CT}},\tau^{{\footnotesize\sf
CT}}\big{)}\leq{\rm hd}(\sigma,\tau)=d={\rm hd}(P).$

On the other hand, if (2) does not hold, then there are permutations
$\sigma,\tau\in P$ with ${\rm hd}(\sigma,\tau)>d$ such that
$\sigma^{{\footnotesize\sf CT}}\neq\tau^{{\footnotesize\sf CT}}$ and ${\rm
hd}(\sigma^{{\footnotesize\sf CT}},\tau^{{\footnotesize\sf CT}})\leq d$. Again
we have

${\rm hd}\big{(}P^{{\footnotesize\sf CT}}\big{)}\leq{\rm
hd}\big{(}\sigma^{{\footnotesize\sf CT}},\tau^{{\footnotesize\sf
CT}}\big{)}\leq d={\rm hd}(P),$

which completes the proof. ∎

It follows from Theorem 3.3 that ${\rm hd}\big{(}P^{{\footnotesize\sf
CT}}\big{)}\leq{\rm hd}(P)$ whenever $|P^{{\footnotesize\sf CT}}|=|P|$, since
in this case $\sigma^{{\footnotesize\sf CT}}\neq\tau^{{\footnotesize\sf CT}}$
for any distinct $\sigma,\tau\in P$, and in particular for those with ${\rm
hd}(\sigma,\tau)=d$. This observation together with Theorem 3.1 yields the
following result.

######  Corollary 3.4.

If ${\rm hd}(P)\geq 4$ then ${\rm hd}\big{(}P^{{\footnotesize\sf
CT}}\big{)}\leq{\rm hd}(P)$.

###### Proof.

If $d:={\rm hd}(P)\geq 4$ then $d/3>1$, so that $|P^{{\footnotesize\sf
CT}}\big{|}=|P|$ by Theorem 3.1. Thus, by the comments above, ${\rm
hd}\big{(}P^{{\footnotesize\sf CT}}\big{)}\leq{\rm hd}(P)$. ∎

##  4\. Hamming distance of two permutations after contraction

In this section we investigate the effect of the contraction operation on the
Hamming distance of two permutations. The main results in this section are
Propositions 4.2 and 4.4, both of which will be used in the proof of the main
result in Section 5. Proposition 4.2 gives necessary and sufficient conditions
for each possible change in Hamming distance, while Proposition 4.4 describes
the disjoint cycle decomposition of $\sigma^{-1}\tau$ for permutations
$\sigma$ and $\tau$ which contract to different permutations.

Let $\sigma\in S_{n}$ be a cycle which does not fix $n-1$. Recall from the
definition of the contraction operation that for any
$x\in\\{0,1,\ldots,n-2\\}$,

$\sigma^{{\footnotesize\sf CT}}(x)=\left\\{\begin{aligned}
&\sigma(x)&&\text{if }x\neq\sigma^{-1}(n-1),\\\ &\sigma(n-1)&&\text{if
}x=\sigma^{-1}(n-1).\end{aligned}\right.$

Hence $\sigma^{{\footnotesize\sf CT}}(x)=\sigma(x)$ if and only if
$x\neq\sigma^{-1}(n-1)$. It follows that to determine the Hamming distance
after contraction of two permutations $\sigma$ and $\tau$ in $S_{n}$, we only
need to examine the images of $n-1$, $\sigma^{-1}(n-1)$, and $\tau^{-1}(n-1)$.
Let

(1)
$\delta(\sigma,\tau)=\big{|}\big{\\{}x\in\big{\\{}n-1,\,\sigma^{-1}(n-1),\,\tau^{-1}(n-1)\big{\\}}\,:\,\sigma(x)\neq\tau(x)\big{\\}}\big{|}$

and

(2) $\delta^{{\footnotesize\sf
CT}}(\sigma,\tau)=\big{|}\big{\\{}x\in\big{\\{}\sigma^{-1}(n-1),\,\tau^{-1}(n-1)\big{\\}}\,:\,\sigma^{{\footnotesize\sf
CT}}(x)\neq\tau^{{\footnotesize\sf CT}}(x)\big{\\}}\big{|}.$

######  Lemma 4.1.

Let $\sigma,\tau\in S_{n}$, and let $\delta(\sigma,\tau)$ and
$\delta^{{\footnotesize\sf CT}}(\sigma,\tau)$ be as in (1) and (2),
respectively. Then

${\rm hd}(\sigma,\tau)-{\rm hd}\big{(}\sigma^{{\footnotesize\sf
CT}},\tau^{{\footnotesize\sf
CT}}\big{)}=\delta(\sigma,\tau)-\delta^{{\footnotesize\sf CT}}(\sigma,\tau).$

###### Proof.

Let
$\gamma=\big{|}\big{\\{}x\notin\big{\\{}n-1,\,\sigma^{-1}(n-1),\,\tau^{-1}(n-1)\big{\\}}\,:\,\sigma(x)\neq\tau(x)\big{\\}}\big{|}$.
Then ${\rm hd}(\sigma,\tau)=\gamma+\delta(\sigma,\tau)$. Since we also have
$\sigma^{{\footnotesize\sf CT}}(x)=\sigma(x)$ and $\tau^{{\footnotesize\sf
CT}}(x)=\tau(x)$ for any
$x\notin\big{\\{}n-1,\,\sigma^{-1}(n-1),\,\tau^{-1}(n-1)\big{\\}}$, we have
${\rm hd}\big{(}\sigma^{{\footnotesize\sf CT}},\tau^{{\footnotesize\sf
CT}}\big{)}=\gamma+\delta^{{\footnotesize\sf CT}}(\sigma,\tau)$. The result
follows immediately. ∎

Recall from Lemma 2.2 that for any distinct permutations $\sigma$ and $\tau$,

${\rm hd}(\sigma,\tau)-3\leq{\rm hd}\big{(}\sigma^{{\footnotesize\sf
CT}},\tau^{{\footnotesize\sf CT}}\big{)}\leq{\rm hd}(\sigma,\tau).$

The following proposition describes when each possible decrease in Hamming
distance occurs.

######  Proposition 4.2.

Let $\sigma,\tau\in S_{n}$, and let $i=\sigma^{-1}(n-1)$, $j=\tau^{-1}(n-1)$,
$a=\tau(i)$, $b=\sigma(j)$, $c=\sigma(n-1)$, and $d=\tau(n-1)$. Let
$\delta(\sigma,\tau)$ and $\delta^{{\footnotesize\sf CT}}(\sigma,\tau)$ be as
in (1) and (2), respectively. Then ${\rm hd}\big{(}\sigma,\tau\big{)}-{\rm
hd}\big{(}\sigma^{{\footnotesize\sf CT}},\tau^{{\footnotesize\sf
CT}}\big{)}=\Delta{\rm hd}\big{(}\sigma,\tau\big{)}$ holds as given in Table
1.

| $\Delta{\rm hd}(\sigma,\tau)$ | Conditions
---|---|---
1 | $0$ |  $i$, $j$, $n-1$ pairwise distinct; $a\neq b$ and $c=d$
2 |  |  $i$, $j$, $n-1$ pairwise distinct; $a=b$ and $c=d$
3 |  |  $i=j\neq n-1$, $a=b=n-1$, $c\neq d$
4 |  |  $i=j\neq n-1$; $a=b=n-1$, $c=d$
5 |  |  $i=j=n-1$; $a=b=c=d=n-1$
6 | $1$ |  $i$, $j$, $n-1$ pairwise distinct; $a$, $b$, $c$, $d$ pairwise distinct
7 |  |  $i$, $j$, $n-1$ pairwise distinct; $a=b$, $c\neq d$
8 |  |  $i=n-1\neq j$; $a=d$, $b$, $c=n-1$ pairwise distinct
9 |  |  $j=n-1\neq i$; $a$, $b=c$, $d=n-1$ pairwise distinct
10 | $2$ |  $i$, $j$, $n-1$ pairwise distinct; $a=c$, $b\neq d$
11 |  |  $i$, $j$, $n-1$ pairwise distinct; $a\neq c$, $b=d$
12 |  |  $i=n-1\neq j$; $a=b=d\neq c=n-1$
13 |  |  $j=n-1\neq i$; $a=b=c\neq d=n-1$
14 | $3$ |  $i$, $j$, $n-1$ pairwise distinct; $a=c$, $b=d$
Table 1. Necessary and sufficient conditions for each possible value of
$\Delta{\rm hd}(\sigma,\tau)={\rm hd}(\sigma,\tau)-{\rm
hd}\big{(}\sigma^{{\footnotesize\sf CT}},\tau^{{\footnotesize\sf CT}}\big{)}$

###### Proof.

The images of $i$, $j$, and $n-1$ under $\sigma$, $\tau$,
$\sigma^{{\footnotesize\sf CT}}$, and $\tau^{{\footnotesize\sf CT}}$ are given
in the following tables:

$x$ | $i$ | $j$ | $n-1$
---|---|---|---
$\sigma(x)$ | $n-1$ | $b$ | $c$
$\tau(x)$ | $a$ | $n-1$ | $d$
$x$ | $i$ | $j$
---|---|---
$\sigma^{{\footnotesize\sf CT}}(x)$ | $c$ | $b$
$\tau^{{\footnotesize\sf CT}}(x)$ | $a$ | $d$

The values of $\delta(\sigma,\tau)$ and $\delta^{{\footnotesize\sf
CT}}(\sigma,\tau)$ are easily obtained from the tables by counting the number
of columns having different entries in each row. We divide into four cases.

_Case 1._ Assume that $i$, $j$, and $n-1$ are pairwise distinct. Since
$\sigma$ and $\tau$ are bijections, it follows that $a\neq d$, $b\neq c$, and
$a$, $b$, $c$, and $d$ are each distinct from $n-1$. Furthermore, either $a$,
$b$, $c$, and $d$ are pairwise distinct, or at least one of the following
holds: $a=b$, $a=c$, $b=d$, $c=d$. The only possible relationships among $a$,
$b$, $c$, and $d$, together with the corresponding values of
$\delta(\sigma,\tau)$ and $\delta^{{\footnotesize\sf CT}}(\sigma,\tau)$, are
given in Table 2. These correspond to the entries in lines 1, 2, 6, 7, 10, 11,
and 14 of Table 1.

Conditions on $a,b,c,d$ | $\delta(\sigma,\tau)$ | $\delta^{{\footnotesize\sf CT}}(\sigma,\tau)$
---|---|---
$a$, $b$, $c$, $d$ pairwise distinct | $3$ | $2$
$a=b$, $c$, $d$ pairwise distinct | $3$ | $2$
$a=b\neq c=d$ | $2$ | $2$
$a=c$, $b$, $d$ pairwise distinct | $3$ | $1$
$a=c\neq b=d$ | $3$ | $0$
$a$, $b=d$, $c$ pairwise distinct | $3$ | $1$
$a$, $b$, $c=d$ pairwise distinct | $2$ | $2$
Table 2. Values of $\delta$ and $\delta^{{\footnotesize\sf CT}}$ for Case 1 of
the proof of Proposition 4.2

_Case 2._ Assume that either $i=n-1\neq j$ or $j=n-1\neq i$. If $i=n-1\neq j$
then $a=d\neq n-1$ and $b\neq c=n-1$. Similarly, if $j=n-1\neq i$ then
$b=c\neq n-1$ and $a\neq d=n-1$. The only possible relationships among $a$,
$b$, $c$, and $d$, together with the corresponding values of
$\delta(\sigma,\tau)$ and $\delta^{{\footnotesize\sf CT}}(\sigma,\tau)$, are
given in Table 3. These correspond to lines 8, 9, 12, and 13 of Table 1.

Conditions on $a$, $b$, $c$, $d$ | $\delta(\sigma,\tau)$ | $\delta^{{\footnotesize\sf CT}}(\sigma,\tau)$
---|---|---
$a=d$, $b$, $c=n-1$ pairwise distinct | $2$ | $1$
$a=b=d\neq c=n-1$ | $2$ | $0$
$a$, $b=c$, $d=n-1$ pairwise distinct | $2$ | $1$
$a=b=c\neq d=n-1$ | $2$ | $0$
Table 3. Values of $\delta$ and $\delta^{{\footnotesize\sf CT}}$ for Case 2 of
the proof of Proposition 4.2

_Case 3._ Assume that $i=j\neq n-1$. Then $a=n-1=b$, $c\neq n-1$, and $d\neq
n-1$. It follows that $a=b\neq c$, $a=b\neq d$, and either $c=d$ or $c\neq d$.
The only possible relationships among $a$, $b$, $c$, and $d$ and the
corresponding values of $\delta(\sigma,\tau)$ and $\delta^{{\footnotesize\sf
CT}}(\sigma,\tau)$ are shown in Table 4. These correspond to lines 3 and 4 of
Table 1.

Conditions on $a$, $b$, $c$, $d$ | $\delta(\sigma,\tau)$ | $\delta^{{\footnotesize\sf CT}}(\sigma,\tau)$
---|---|---
$a=b$, $c$, $d$ pairwise distinct | $1$ | $1$
$a=b\neq c=d$ | $0$ | $0$
Table 4. Values of $\delta$ and $\delta^{{\footnotesize\sf CT}}$ for Case 3 of
the proof of Proposition 4.2

_Case 4._ Assume that $i=j=n-1$. Then $a=b=c=d=n-1$ and so
$\delta(\sigma,\tau)=\delta^{{\footnotesize\sf CT}}(\sigma,\tau)=0$. This
yields line 5 of Table 1.

Statements 1–4 of the proposition follow immediately from Table 1. This
completes the proof. ∎

The proof of Proposition 4.4 relies on the next lemma, which tells us that the
actions of the permutations $\sigma^{-1}\tau$ and
$\big{(}\sigma^{{\footnotesize\sf CT}}\big{)}^{-1}\tau^{{\footnotesize\sf
CT}}$ are mostly the same. Recall from Lemma 2.1 that the operations of
contraction and inversion commute, and that for any $\sigma\in S_{n}$,
$\sigma^{{\footnotesize\sf CT}}(x)=\sigma(x)$ whenever
$x\neq\sigma^{-1}(n-1)$.

######  Lemma 4.3.

Let $\sigma,\tau\in S_{n}$ and $x\in\\{0,1,\ldots,n-2\\}$. If
$x\notin\big{\\{}\sigma(n-1),\tau^{-1}\sigma(n-1)\big{\\}}$, then
$\big{(}\sigma^{{\footnotesize\sf CT}}\big{)}^{-1}\tau^{{\footnotesize\sf
CT}}(x)=\sigma^{-1}\tau(x)$.

###### Proof.

It follows from Lemma 2.1 and from $x\neq\sigma(n-1)$ that

$\sigma^{-1}(x)=\big{(}\sigma^{-1}\big{)}^{{\footnotesize\sf
CT}}(x)=\big{(}\sigma^{{\footnotesize\sf CT}}\big{)}^{-1}(x).$

Note that $y:=\sigma^{-1}(x)\neq\tau^{-1}(n-1)$. Thus

$\sigma^{-1}\tau(x)=\tau(y)=\tau^{{\footnotesize\sf
CT}}(y)=\sigma^{-1}\tau^{{\footnotesize\sf
CT}}(x)=\big{(}\sigma^{{\footnotesize\sf
CT}}\big{)}^{-1}\tau^{{\footnotesize\sf CT}}(x).\qed$

We denote the length of a cycle $\rho$ by $|\rho|$. Following [1], we define
the length of the identity permutation to be zero. Likewise, we will say that
a symbol $x\in\\{0,1,\ldots,n-1\\}$ _belongs to a cycle of zero length_ in the
disjoint cycle decomposition of $\sigma\in S_{n}$ whenever $\sigma(x)=x$.

######  Proposition 4.4.

Let $\sigma,\tau\in S_{n}$ such that $\sigma^{{\footnotesize\sf
CT}}\neq\tau^{{\footnotesize\sf CT}}$. Let $\omega$ and $\pi$ be the cycles in
the disjoint cycle decomposition of $\sigma^{-1}\tau$ which contain $n-1$ and
$\sigma(n-1)$, respectively. Suppose that

$\sigma^{-1}\tau=\begin{cases}\rho\,\omega\,\pi&\text{if }\omega\neq\pi,\\\
\rho\,\omega&\text{if }\omega=\pi,\end{cases}$

where $\rho\in S_{n}$ is disjoint from $\omega$ and $\pi$. Then

$\big{(}\sigma^{{\footnotesize\sf CT}}\big{)}^{-1}\tau^{CT}=\rho\,\chi$

for some $\chi\in S_{n-1}$ disjoint from $\rho$, and the following hold.

  1. (1)

If ${\rm hd}\big{(}\sigma^{{\footnotesize\sf CT}},\tau^{{\footnotesize\sf
CT}}\big{)}={\rm hd}(\sigma,\tau)$, then either $\omega=(0)$ or $\pi=(0)$, and
$\chi$ is a cycle with $|\chi|=|\omega\,\pi|$.

  2. (2)

Suppose that ${\rm hd}\big{(}\sigma^{{\footnotesize\sf
CT}},\tau^{{\footnotesize\sf CT}}\big{)}={\rm hd}(\sigma,\tau)-1$.

    1. (a)

If $\omega=\pi$ then either $\chi$ is a cycle with $|\chi|=|\omega|-1$, or
$\chi$ is a product of two disjoint cycles $\omega^{\prime}$ and
$\pi^{\prime}$ with $|\omega^{\prime}|+|\pi^{\prime}|=|\omega|-1$.

    2. (b)

If $\omega\neq\pi$ then $\chi$ is a cycle with $|\chi|=|\omega|+|\pi|-1$.

  3. (3)

If ${\rm hd}\big{(}\sigma^{{\footnotesize\sf CT}},\tau^{{\footnotesize\sf
CT}}\big{)}={\rm hd}(\sigma,\tau)-2$, then $\omega=\pi$ and $\chi$ is a cycle
with $|\chi|=|\omega|-2$.

  4. (4)

If ${\rm hd}\big{(}\sigma^{{\footnotesize\sf CT}},\tau^{{\footnotesize\sf
CT}}\big{)}={\rm hd}(\sigma,\tau)-3$, then $\omega=\pi$, $|\omega|=3$, and
$\chi=(0)$.

###### Proof.

Let $i=\sigma^{-1}(n-1)$, $j=\tau^{-1}(n-1)$, $a=\tau(i)$, $b=\sigma(j)$,
$c=\sigma(n-1)$, and $d=\tau(n-1)$. Since $\sigma^{-1}\tau(b)=n-1$, the
disjoint cycle decomposition of $\sigma^{-1}\tau$ contains a cycle
$\omega:=(b,\,n-1,\,a,\mathbf{x})$, where $\mathbf{x}$ is either empty or a
sequence of distinct elements of $\\{0,1,\ldots,n-1\\}\setminus\\{a,b,n-1\\}$.
Likewise $\sigma^{-1}\tau(c)=d$, so the disjoint cycle decomposition of
$\sigma^{-1}\tau$ contains a cycle $\pi:=(c,\,d,\mathbf{y})$, with
$\mathbf{y}$ empty or a sequence of distinct elements of
$\\{0,1,\ldots,n-1\\}\setminus\\{c,d\\}$. We can write $\sigma^{-1}\tau$ as
$\sigma^{-1}\tau=\rho\,\omega\,\pi$ when $\omega\neq\pi$ and
$\sigma^{-1}\tau=\rho\,\omega$ when $\omega=\pi$. Here $\rho\in S_{n}$ is
disjoint from $\omega$ and $\pi$, so $\rho$ fixes both $n-1$ and $c$, and
hence also $a$, $b$, and $d$.

Suppose that the conditions in the last column of line 1 of Table 1 hold. Then
$\sigma^{-1}\tau(c)=d=c$, so that $\pi=(c)=(d)=(0)$. Since $a\neq b$, the
cycle $\omega$ is nontrivial, and thus $\omega\neq\pi$.

By going through the conditions in each line of Table 1 in a similar manner,
we can deduce all possible forms of $\omega$ and $\pi$. We summarize these in
Table 5.

| $\omega$ | $\pi$ |  | $\chi$
---|---|---|---|---
1 | $(b,\,n-1,\,a,\,\mathbf{x})$ | $(0)$ | $\omega\neq\pi$ | $(b,\,c,\,a,\,\mathbf{x})$
2 | $(b,\,n-1)$ | $(0)$ | $\omega\neq\pi$ | $(b,\,c)$
3 | $(0)$ | $(c,\,d,\mathbf{y})$ | $\omega\neq\pi$ | $(c,\,d,\,\mathbf{y})$
4 | $(0)$ | $(0)$ |  | $(0)$
5 | $(0)$ | $(0)$ |  | $(0)$
6 | $(b,\,n-1,\,a,\,\mathbf{x})$ | $(c,\,d,\,\mathbf{y})$ | $\omega\neq\pi$ | $(b,\,d,\,\mathbf{y},\,c,\,a,\,\mathbf{x})$
| $(b,\,n-1,\,a,\,\mathbf{x},\,c,\,d,\,\mathbf{y})$ | $(b,\,n-1,\,a,\,\mathbf{x},\,c,\,d,\,\mathbf{y})$ |  | $(b,\,d,\,\mathbf{y})(c,\,a,\,\mathbf{x})$
7 | $(b,\,n-1)$ | $(c,\,d,\,\mathbf{y})$ | $\omega\neq\pi$ | $(b,\,d,\,\mathbf{y},\,c)$
8 | $(b,\,n-1,\,a,\,\mathbf{x})$ | $(b,\,n-1,\,a,\,\mathbf{x})$ |  | $(b,\,a,\,\mathbf{x})$
9 | $(b,\,n-1,\,a,\,\mathbf{x})$ | $(b,\,n-1,\,a,\,\mathbf{x})$ |  | $(b,\,a,\,\mathbf{x})$
10 | $(b,\,n-1,\,a,\,d,\,\mathbf{x})$ | $(b,\,n-1,\,a,\,d,\,\mathbf{x})$ |  | $(b,\,d,\,\mathbf{x})$
11 | $(b,\,n-1,\,a,\,\mathbf{x},c)$ | $(b,\,n-1,\,a,\,\mathbf{x},\,c)$ |  | $(a,\,\mathbf{x},\,c)$
12 | $(b,\,n-1)$ | $(b,\,n-1)$ |  | $(0)$
13 | $(b,\,n-1)$ | $(b,\,n-1)$ |  | $(0)$
14 | $(b,\,n-1,\,a)$ | $(b,\,n-1,\,a)$ |  | $(0)$
Table 5. Factors $\omega$ and $\pi$ of $\sigma^{-1}\tau$, and $\chi$ of
$\big{(}\sigma^{{\footnotesize\sf CT}}\big{)}^{-1}\tau^{{\footnotesize\sf
CT}}$, corresponding to each line of Table 1

By Lemma 4.3, $(\sigma^{{\footnotesize\sf CT}})^{-1}\tau^{{\footnotesize\sf
CT}}(x)=\sigma^{-1}\tau(x)$ for any $x\in{\rm supp}(\rho)$. Thus

$(\sigma^{{\footnotesize\sf CT}})^{-1}\tau^{{\footnotesize\sf CT}}=\rho\chi$

for some $\chi\in S_{n-1}$ that is disjoint from $\rho$, and which moves some
element in $\\{a,b,c,d\\}$ if $\chi\neq(0)$.

To determine the form of $\chi$, we consider the images and inverse images of
$a$, $b$, $c$, and $d$ under $\big{(}\sigma^{{\footnotesize\sf
CT}}\big{)}^{-1}\tau^{{\footnotesize\sf CT}}$. By Lemma 4.3 we have
$\big{(}\sigma^{{\footnotesize\sf CT}}\big{)}^{-1}\tau^{{\footnotesize\sf
CT}}(x)=\sigma^{-1}\tau(x)$ for any $x\notin\\{b,c\\}$, and
$\big{(}\tau^{{\footnotesize\sf CT}}\big{)}^{-1}\sigma^{{\footnotesize\sf
CT}}(x)=\tau^{-1}\sigma(x)$ for any $x\notin\\{a,d\\}$.

Assume that the conditions in line 1 of Table 1 hold. Then $a\notin\\{b,c\\}$,
so $\big{(}\sigma^{{\footnotesize\sf CT}}\big{)}^{-1}\tau^{{\footnotesize\sf
CT}}(a)=\sigma^{-1}\tau(a)=\omega(a)$ by the above. Similarly,
$b\notin\\{a,d\\}$, so that $\big{(}\tau^{{\footnotesize\sf
CT}}\big{)}^{-1}\sigma^{{\footnotesize\sf
CT}}(b)=\tau^{-1}\sigma(b)=\omega^{-1}(b)$. Moreover $j\neq i$, so that
$\sigma^{{\footnotesize\sf CT}}(j)=\sigma(j)=b$ and

$\big{(}\sigma^{{\footnotesize\sf CT}}\big{)}^{-1}\tau^{{\footnotesize\sf
CT}}(b)=\tau^{{\footnotesize\sf CT}}(j)=\tau(n-1)=d=c.$

Since $c=\sigma(n-1)=\sigma^{{\footnotesize\sf CT}}(i)$ and $i\neq j$,

$\big{(}\sigma^{{\footnotesize\sf CT}}\big{)}^{-1}\tau^{{\footnotesize\sf
CT}}(d)=\big{(}\sigma^{{\footnotesize\sf
CT}}\big{)}^{-1}\tau^{{\footnotesize\sf CT}}(c)=\tau^{{\footnotesize\sf
CT}}(i)=\tau(i)=a.$

A similar analysis yields the other images and inverse images corresponding to
the conditions in each line of Table 1.

We now obtain $\chi$. Note that $\big{(}\sigma^{{\footnotesize\sf
CT}}\big{)}^{-1}\tau^{{\footnotesize\sf CT}}(x)=\chi(x)$ for
$x\in\\{a,b,c,d\\}$ and $\big{(}\sigma^{{\footnotesize\sf
CT}}\big{)}^{-1}\tau^{{\footnotesize\sf CT}}(x)=\sigma^{-1}\tau(x)$ otherwise.
Thus, for the conditions in line 1 of Table 1, we have

$\chi(b)=c,\ \chi(c)=a,\ \chi(a)=\omega(a),$

and if $\mathbf{x}$ is non-empty, $\chi(x)=\omega(x)$ for any
$x\in\mathbf{x}$. Thus, $\chi=(b,\,c,\,a,\,\mathbf{x})$. The forms for $\chi$
corresponding to the rest of the lines in Table 1 are obtained similarly.
These are summarized in the last column of Table 5.

The conclusions of the proposition follow immediately from Table 5. ∎

##  5\. Multiple contractions

In this section we consider the effect on Hamming distance when applying the
contraction operation several times. The main results of this section are
Theorem 5.2 and Corollaries 5.3, 5.4, 5.5, and 5.6. These give conditions that
bound the decrease in Hamming distance after repeated contractions.

For a permutation array $P\subseteq S_{n}$ with ${\rm hd}(P)=d$ and for any
$m\in\\{1,\ldots,n-1\\}$ such that $\big{|}P^{{\footnotesize\sf
CT}^{m}}\big{|}>1$, it follows from Lemma 2.2.1 that

${\rm hd}\big{(}P^{{\footnotesize\sf CT}^{m}}\big{)}\geq d-3m.$

Indeed, for any distinct $\sigma,\tau\in P$, ${\rm
hd}\big{(}\sigma^{{\footnotesize\sf CT}^{i}},\tau^{{\footnotesize\sf
CT}^{i}}\big{)}-{\rm hd}\big{(}\sigma^{{\footnotesize\sf
CT}^{i+1}},\tau^{{\footnotesize\sf CT}^{i+1}}\big{)}\leq 3$ for each
$i\in\\{0,\ldots,m-1\\}$; thus

$\displaystyle{\rm hd}(\sigma,\tau)-{\rm hd}\big{(}\sigma^{{\footnotesize\sf
CT}^{m}},\tau^{{\footnotesize\sf CT}^{m}}\big{)}$
$\displaystyle=\sum_{i=0}^{m-1}\left({\rm hd}\big{(}\sigma^{{\footnotesize\sf
CT}^{i}},\tau^{{\footnotesize\sf CT}^{i}}\big{)}-{\rm
hd}\big{(}\sigma^{{\footnotesize\sf CT}^{i+1}},\tau^{{\footnotesize\sf
CT}^{i+1}}\big{)}\right)$ $\displaystyle\leq 3m$

and so ${\rm hd}\big{(}\sigma^{{\footnotesize\sf
CT}^{m}},\tau^{{\footnotesize\sf CT}^{m}}\big{)}\geq{\rm
hd}(\sigma,\tau)-3m\geq d-3m$. In Theorem 5.2 we give conditions that lead to
an improvement of this bound. We first prove Lemma 5.1, which is a technical
result used in the proof of Theorem 5.2.

######  Lemma 5.1.

Let $\mathcal{C}=\\{\gamma_{1},\ldots,\gamma_{r}\\}$ be a set of cycles of odd
length in the disjoint cycle decomposition of
$\big{(}\sigma^{{\footnotesize\sf CT}}\big{)}^{-1}\tau^{{\footnotesize\sf
CT}}$. Let $\omega$ and $\pi$ be the factors in the disjoint cycle
decomposition of $\sigma^{-1}\tau$ as described in Proposition 4.4. Then,
under a suitable rearrangement of the indices of the elements of
$\mathcal{C}$, the disjoint cycle decomposition of $\sigma^{-1}\tau$ has a set
$\mathcal{D}$ of cycle factors of odd length, where $\mathcal{D}$ satisfies
one of the following:

  1. (1)

If ${\rm hd}\big{(}\sigma^{{\footnotesize\sf CT}},\tau^{{\footnotesize\sf
CT}}\big{)}={\rm hd}(\sigma,\tau)$, then $\mathcal{D}$ is $\mathcal{C}$ or
$\\{\gamma_{1},\ldots,\gamma_{r-1},\omega\pi\\}$, with
$|\omega\pi|=|\gamma_{r}|$;

  2. (2)

If ${\rm hd}\big{(}\sigma^{{\footnotesize\sf CT}},\tau^{{\footnotesize\sf
CT}}\big{)}={\rm hd}(\sigma,\tau)-1$ and $r>1$, then $\mathcal{D}$ is
$\\{\gamma_{1},\ldots,\gamma_{r-2},\delta_{r-1}\\}$ for some
$\delta_{r-1}\in\\{\gamma_{r-1},\omega\\}$, with
$|\delta_{r-1}|\in\\{|\gamma_{r-1}|,\ |\gamma_{r-1}|+|\gamma_{r}|+1\\}$;

  3. (3)

If ${\rm hd}\big{(}\sigma^{{\footnotesize\sf CT}},\tau^{{\footnotesize\sf
CT}}\big{)}={\rm hd}(\sigma,\tau)-2$, then $\mathcal{D}$ is $\mathcal{C}$ or
$\\{\gamma_{1},\ldots,\gamma_{r-1},\omega\\}$, with $|\omega|=|\gamma_{r}|+2$;

  4. (4)

If ${\rm hd}\big{(}\sigma^{{\footnotesize\sf CT}},\tau^{{\footnotesize\sf
CT}}\big{)}={\rm hd}(\sigma,\tau)-3$, then
$\mathcal{D}=\mathcal{C}\cup\\{\omega\\}$, with $|\omega|=3$.

###### Proof.

Recall that $\omega$ and $\pi$ are the respective cycles containing $n-1$ and
$\sigma(n-1)$ in the disjoint cycle decomposition of $\sigma^{-1}\tau$.
Suppose that $\sigma^{-1}\tau=\rho\,\omega\,\pi$ if $\omega\neq\pi$ and
$\sigma^{-1}\tau=\rho\,\omega$ if $\omega=\pi$, where $\rho$ is disjoint from
$\omega$ and $\pi$. Then by Proposition 4.4, $\big{(}\sigma^{{\footnotesize\sf
CT}}\big{)}^{-1}\tau^{{\footnotesize\sf CT}}=\rho\chi$ for some permutation
$\chi$ disjoint from $\rho$ which is given in Table 5.

Assume first that the conditions in any of the lines 1–5 and 7–14, or in line
6 with $\omega\neq\pi$, of Table 1 are satisfied. In each case $\chi$ is
either a cycle or the identity permutation. It follows that there is at most
one cycle in $\\{\gamma_{1},\ldots,\gamma_{r}\\}$ which is equal to $\chi$; if
$r>1$ assume without loss of generality that $\gamma_{i}\neq\chi$ for all
$i\in\\{1,\ldots,r-1\\}$. Then each $\gamma_{i}\neq\chi$ is a factor in the
disjoint cycle decomposition of $\rho$, and hence is a factor in the disjoint
cycle decomposition of $\sigma^{-1}\tau$. Take $\delta_{i}=\gamma_{i}$ for
each $i\in\\{1,\ldots,r-1\\}$. If ${\rm hd}\big{(}\sigma^{{\footnotesize\sf
CT}},\tau^{{\footnotesize\sf CT}}\big{)}={\rm hd}(\sigma,\tau)-1$, then we
have proved part of statement 2 of the proposition. Otherwise, it remains for
us to choose $\delta_{r}$ and, if necessary, $\delta_{r+1}$.

If ${\rm hd}\big{(}\sigma^{{\footnotesize\sf CT}},\tau^{{\footnotesize\sf
CT}}\big{)}={\rm hd}(\sigma,\tau)$, take

$\delta_{r}=\left\\{\begin{aligned} &\gamma_{r}&&\text{if
}\chi\neq\gamma_{r},\\\ &\omega\pi&&\text{if
}\chi=\gamma_{r}.\end{aligned}\right.$

Since $\omega\pi$ is a cycle of length $|\chi|$ by Proposition 4.4 (1), in
both cases $\delta_{r}$ is a factor in the disjoint cycle decomposition of
$\sigma^{-1}\tau$ and $|\delta_{r}|=|\gamma_{r}|$. If ${\rm
hd}\big{(}\sigma^{{\footnotesize\sf CT}},\tau^{{\footnotesize\sf
CT}}\big{)}={\rm hd}(\sigma,\tau)-2$, take

$\delta_{r}=\left\\{\begin{aligned} &\gamma_{r}&&\text{if
}\chi\neq\gamma_{r},\\\ &\omega&&\text{if
}\chi=\gamma_{r}.\end{aligned}\right.$

In both cases $\delta_{r}$ is a factor in the disjoint cycle decomposition of
$\sigma^{-1}\tau$. For the case $\delta_{r}=\omega$, we have
$|\omega|=|\chi|+2=|\gamma_{r}|+2$ by Proposition 4.4 (3). Setting
$\mathcal{D}=\\{\delta_{1},\ldots,\delta_{r}\\}$ proves statements 1 and 3 of
the proposition.

If ${\rm hd}\big{(}\sigma^{{\footnotesize\sf CT}},\tau^{{\footnotesize\sf
CT}}\big{)}={\rm hd}(\sigma,\tau)-3$, then $\chi=(0)$ by Table 5 so that
$\chi\neq\gamma_{r}$. In this case we take $\delta_{r}=\gamma_{r}$ and
$\delta_{r+1}=\omega$. Note that $\delta_{r}$ and $\delta_{r+1}$ are factors
in the disjoint cycle decomposition of $\sigma^{-1}\tau$, and that $\omega$ is
a cycle of length $3$ by Proposition 4.4 (4). Setting
$\mathcal{D}=\\{\delta_{1},\ldots,\delta_{r+1}\\}$ proves statement 4 of the
proposition.

Now assume that the conditions in line 6 of Table 1 hold, with $\omega=\pi$.
Then by Table 5, $\chi$ is a product of two disjoint cycles $\omega^{\prime}$
and $\pi^{\prime}$. This means that there are at most two cycles in
$\\{\gamma_{1},\ldots,\gamma_{r}\\}$ which are not disjoint from $\chi$. If
$r>2$ assume without loss of generality that
$\gamma_{i}\notin\\{\omega^{\prime},\pi^{\prime}\\}$ for all
$i\in\\{1,\ldots,r-2\\}$. In addition, if
$\\{\omega^{\prime},\pi^{\prime}\\}\neq\\{\gamma_{r-1},\gamma_{r}\\}$ assume
without loss of generality that
$\gamma_{r-1}\notin\\{\omega^{\prime},\pi^{\prime}\\}$. Then each
$\gamma_{i}\notin\\{\omega^{\prime},\pi^{\prime}\\}$ is a factor in the
disjoint cycle decomposition of $\rho$, and hence is a factor in the disjoint
cycle decomposition of $\sigma^{-1}\tau$. Take $\delta_{i}=\gamma_{i}$ for
each $i\in\\{1,\ldots,r-2\\}$, and

$\delta_{r-1}=\left\\{\begin{aligned} &\gamma_{r-1}&&\text{if
}\\{\omega^{\prime},\pi^{\prime}\\}\neq\\{\gamma_{r-1},\gamma_{r}\\},\\\
&\omega&&\text{if
}\\{\omega^{\prime},\pi^{\prime}\\}=\\{\gamma_{r-1},\gamma_{r}\\}.\end{aligned}\right.$

In both cases $\delta_{r-1}$ is a factor in the disjoint cycle decomposition
of $\sigma^{-1}\tau$. By Proposition 4.4 (2), the permutation $\omega$ is a
cycle of length $|\omega^{\prime}|+|\pi^{\prime}|+1$ . Thus, in each case we
obtain $|\delta_{r-1}|\in\\{|\gamma_{r-1}|,\
|\gamma_{r-1}|+|\gamma_{r}|+1\\}$. This completes the proof of statement 2 of
the proposition. ∎

Theorem 5.2 is a generalization of [1, Theorem 3] to multiple contractions. It
may seem that the result follows inductively from [1, Theorem 3]. On the
contrary, the proof of Theorem 5.2 relies heavily on Lemma 5.1.

######  Theorem 5.2.

Let $\sigma,\tau\in S_{n}$ with ${\rm hd}(\sigma,\tau)=d$. Let
$m\in\\{1,\ldots,n-1\\}$ and assume that the disjoint cycle decomposition of
$\sigma^{-1}\tau$ has no factor of odd length $\ell$ where $3\leq\ell\leq
2m+1$. Then ${\rm hd}\big{(}\sigma^{{\footnotesize\sf
CT}^{m}},\tau^{{\footnotesize\sf CT}^{m}}\big{)}\geq d-2m$.

###### Proof.

Since the Hamming distance between two permutations is non-negative, we assume
that $d>2m$. We proceed by induction on $m$.

Suppose the disjoint cycle decomposition of $\sigma^{-1}\tau$ has no factor of
length $3$. It follows from Lemma 2.2.1 and Lemma 2.2.2 that ${\rm
hd}(\sigma,\tau)-{\rm hd}(\sigma^{{\footnotesize\sf
CT}},\tau^{{\footnotesize\sf CT}})\leq 2$. So

${\rm hd}(\sigma^{{\footnotesize\sf CT}},\tau^{{\footnotesize\sf CT}})\geq{\rm
hd}(\sigma,\tau)-2=d-2,$

and the result holds for $m=1$.

Let $d>2(m+1)$ and suppose that the result holds for $1\leq m<n-1$. We will
show that the assumption

${\rm hd}\big{(}\sigma^{{\footnotesize\sf CT}^{m+1}},\tau^{{\footnotesize\sf
CT}^{m+1}}\big{)}<d-2(m+1)=d-2m-2$

leads to the conclusion that the disjoint cycle decomposition of
$\sigma^{-1}\tau$ includes a factor of odd length $\ell$ where $3\leq\ell\leq
2m+3$.

By Lemma 2.2.1 we have ${\rm hd}\big{(}\sigma^{{\footnotesize\sf
CT}^{m}},\tau^{{\footnotesize\sf CT}^{m}}\big{)}-{\rm
hd}\big{(}\sigma^{{\footnotesize\sf CT}^{m+1}},\tau^{{\footnotesize\sf
CT}^{m+1}}\big{)}\leq 3$, so that

${\rm hd}\big{(}\sigma^{{\footnotesize\sf CT}^{m+1}},\tau^{{\footnotesize\sf
CT}^{m+1}}\big{)}\geq{\rm hd}\big{(}\sigma^{{\footnotesize\sf
CT}^{m}},\tau^{{\footnotesize\sf CT}^{m}}\big{)}-3\geq d-2m-3.$

Hence we must have ${\rm hd}\big{(}\sigma^{{\footnotesize\sf
CT}^{m+1}},\tau^{{\footnotesize\sf CT}^{m+1}}\big{)}=d-2m-3$ and ${\rm
hd}\big{(}\sigma^{{\footnotesize\sf CT}^{m}},\tau^{{\footnotesize\sf
CT}^{m}}\big{)}=d-2m$.

For each $i\in\\{1,\ldots,m+1\\}$ let $d_{i}={\rm
hd}\big{(}\sigma^{{\footnotesize\sf CT}^{i-1}},\tau^{{\footnotesize\sf
CT}^{i-1}}\big{)}-{\rm hd}\big{(}\sigma^{{\footnotesize\sf
CT}^{i}},\tau^{{\footnotesize\sf CT}^{i}}\big{)}$. Then by the above
$d_{m+1}=3$. Again by Lemma 2.2.1 we have $0\leq d_{i}\leq 3$ for each $i$,
and

$\sum_{i=1}^{m+1}d_{i}={\rm hd}(\sigma,\tau)-{\rm
hd}\big{(}\sigma^{{\footnotesize\sf CT}^{m+1}},\tau^{{\footnotesize\sf
CT}^{m+1}}\big{)}=d-(d-2m-3)=2m+3.$

It follows from Lemma 2.2.2 that for $d_{i}=3$, the disjoint cycle
decomposition of $\big{(}\sigma^{{\footnotesize\sf
CT}^{i-1}}\big{)}^{-1}\tau^{{\footnotesize\sf CT}^{i-1}}$ contains a factor
$\beta_{i}$ of length $3$. In particular, since $d_{m+1}=3$, the cycle
decomposition of $\big{(}\sigma^{{\footnotesize\sf
CT}^{m}}\big{)}^{-1}\tau^{{\footnotesize\sf CT}^{m}}$ contains a $3$-cycle
$\beta_{m}$. Set $E_{m}=\\{\beta_{m}\\}$. Applying Lemma 5.1 to
$\big{(}\sigma^{{\footnotesize\sf CT}^{m}}\big{)}^{-1}\tau^{{\footnotesize\sf
CT}^{m}}$ and $\big{(}\sigma^{{\footnotesize\sf
CT}^{m-1}}\big{)}^{-1}\tau^{{\footnotesize\sf CT}^{m-1}}$ with
$\mathcal{C}=E_{m}$, for $d_{m}\in\\{0,2,3\\}$ we obtain a non-empty set
$\mathcal{D}_{m-1}$ of odd cycles in the disjoint cycle decomposition of
$\big{(}\sigma^{{\footnotesize\sf
CT}^{m-1}}\big{)}^{-1}\tau^{{\footnotesize\sf CT}^{m-1}}$. Define $E_{m-1}$ by

$E_{m-1}=\left\\{\begin{aligned} &\mathcal{D}_{m-1}&&\text{if
}d_{m}\in\\{0,2,3\\},\\\ &\varnothing&&\text{if }d_{m}=1.\end{aligned}\right.$

For each $i\in\\{0,\ldots,m-2\\}$ define $E_{i}$ as follows: If
$E_{i+1}=\varnothing$, then

$E_{i}=\left\\{\begin{aligned} &\varnothing&&\text{if
$d_{i}\in\\{0,1,2\\}$},\\\ &\\{\beta_{i}\\}&&\text{if
$d_{i}=3$;}\end{aligned}\right.$

and if $E_{i+1}\neq\varnothing$, then

$E_{i}=\left\\{\begin{aligned} &\varnothing&&\text{if $d_{i}=1$ and
$|E_{i+1}|=1$},\\\ &\mathcal{D}_{i}&&\text{otherwise},\end{aligned}\right.$

where $\mathcal{D}_{i}$ is the set obtained by applying Lemma 5.1 to
$\big{(}\sigma^{{\footnotesize\sf CT}^{i}}\big{)}^{-1}\tau^{{\footnotesize\sf
CT}^{i}}$ and $\big{(}\sigma^{{\footnotesize\sf
CT}^{i+1}}\big{)}^{-1}\tau^{{\footnotesize\sf CT}^{i+1}}$ with
$\mathcal{C}=E_{i+1}$. Hence each non-empty $E_{i}$ consists of cycles of odd
length which appear in the disjoint cycle decomposition of
$\big{(}\sigma^{{\footnotesize\sf CT}^{i}}\big{)}^{-1}\tau^{{\footnotesize\sf
CT}^{i}}$. Moreover for each $i\in\\{0,\ldots,m-1\\}$ we have
$|E_{i}|=|E_{i+1}|$ if $d_{i}\in\\{0,2\\}$, $|E_{i}|=|E_{i+1}|+1$ if
$d_{i}=3$, and $|E_{i}|\geq|E_{i+1}|-1$ if $d_{i}=1$. Thus

$|E_{0}|\geq|E_{m}|+a\cdot(-1)+(c-1)\cdot 1=c-a,$

where $a=\big{|}\\{i\in\\{1,\ldots,m+1\\}\,:\,d_{i}=1\\}\big{|}$ and
$c=\big{|}\\{i\in\\{1,\ldots,m+1\\}\,:\,d_{i}=3\\}\big{|}$. Note that $a<c$,
otherwise

$\sum_{i=1}^{m+1}d_{i}\leq a\cdot 1+c\cdot 3+(m+1-a-c)\cdot 2\leq 2m+2<2m+3.$

Hence $|E_{0}|\geq 1$. That is, $E_{0}$ contains at least one cycle, which by
definition of $E_{0}$ is a cycle in the disjoint cycle decomposition of
$\sigma^{-1}\tau$ of odd length.

All that remains is to show that some cycle in $E_{0}$ has length at most
$2m+3$. In fact what we will establish is that every cycle in $E_{0}$ has
length at most $2m+3$. For each $i\in\\{0,\ldots,m\\}$, let

$\displaystyle a_{i}$
$\displaystyle=\big{|}\\{j\in\\{i+1,\ldots,m+1\\}\,:\,d_{j}=1\\}\big{|},$
$\displaystyle b_{i}$
$\displaystyle=\big{|}\\{j\in\\{i+1,\ldots,m+1\\}\,:\,d_{j}=2\\}\big{|},$
$\displaystyle c_{i}$
$\displaystyle=\big{|}\\{j\in\\{i+1,\ldots,m+1\\}\,:\,d_{j}=3\\}\big{|}.$

Clearly

$a_{0}+2b_{0}+3c_{0}=\sum_{i=1}^{m+1}d_{i}=2m+3.$

We claim that for each $i\in\\{0,\ldots,m\\}$, the sum of the lengths of the
cycles in $E_{i}$ is at most $a_{i}+2b_{i}+3c_{i}$. Indeed, for $i=m$, we have
$d_{m+1}=3$ so that $a_{m}=b_{m}=0$ and $c_{m}=1$. Also
$E_{m}=\\{\beta_{m}\\}$ where $|\beta_{m}|=3=a_{m}+2b_{m}+3c_{m}$, so the
claim holds for $i=m$. Now let $i\leq m$ and suppose that the claim holds for
$i$. We have the following cases.

_Case 1._ Assume that $E_{i}=\varnothing$. If $d_{i}\in\\{0,1,2\\}$ then
$E_{i-1}=\varnothing$ so the claim holds. If $d_{i}=3$ then $c_{i-1}\geq 1$
and $E_{i-1}=\\{\beta_{i-1}\\}$. The claim also holds because
$|\beta_{i-1}|=3=3\cdot 1\leq a_{i-1}+2b_{i-1}+3c_{i-1}$.

_Case 2._ Assume that $E_{i}\neq\varnothing$, say,
$E_{i}=\\{\gamma_{1},\ldots,\gamma_{r}\\}$. If $d_{i}=1$ and $r=1$ then
$E_{i-1}=\varnothing$, so the claim holds. Otherwise
$E_{i-1}=\mathcal{D}_{i-1}$; we consider each of the possibilities described
in Lemma 5.1.

_Case 2.1._ Suppose that $d_{i}=0$. Then
$E_{i-1}=\\{\delta_{1},\ldots,\delta_{r}\\}$ with $\delta_{j}=\gamma_{j}$ for
$1\leq j\leq r-1$ and $|\delta_{r}|=|\gamma_{r}|$. Also $a_{i-1}=a_{i}$,
$b_{i-1}=b_{i}$, and $c_{i-1}=c_{i}$. Hence

$\sum_{j=1}^{r}|\delta_{j}|=\sum_{j=1}^{r}|\gamma_{j}|\leq
a_{i}+2b_{i}+3c_{i}=a_{i-1}+2b_{i-1}+3c_{i-1}.$

_Case 2.2._ Suppose that $d_{i}=1$ and $r>1$. Then
$E_{i-1}=\\{\delta_{1},\ldots,\delta_{r-1}\\}$ where $\delta_{j}=\gamma_{j}$
for $1\leq j\leq r-2$ and $|\delta_{r-1}|\in\\{|\gamma_{r-1}|,\
|\gamma_{r-1}|+|\gamma_{r}|+1\\}$. Also $a_{i-1}=a_{i}+1$, $b_{i-1}=b_{i}$,
and $c_{i-1}=c_{i}$. Hence

$\sum_{j=1}^{r-1}|\delta_{j}|\leq 1+\sum_{j=1}^{r}|\gamma_{j}|\leq
a_{i-1}+2b_{i-1}+3c_{i-1}.$

_Case 2.3._ Suppose that $d_{i}=2$. Then
$E_{i-1}=\\{\delta_{1},\ldots,\delta_{r}\\}$ with $\delta_{j}=\gamma_{j}$ for
$1\leq j\leq r-1$ and $|\delta_{r}|\in\\{|\gamma_{r}|,\ |\gamma_{r}|+2\\}$.
Also $a_{i-1}=a_{i}$, $b_{i-1}=b_{i}+1$, and $c_{i-1}=c_{i}$. Hence

$\sum_{j=1}^{r}|\delta_{j}|\leq 2+\sum_{j=1}^{r}|\gamma_{j}|\leq
a_{i-1}+2b_{i-1}+3c_{i-1}.$

_Case 2.4._ Suppose that $d_{i}=3$. Then
$E_{i-1}=\\{\delta_{1},\ldots,\delta_{r+1}\\}$ with $\delta_{j}=\gamma_{j}$
for $1\leq j\leq r$ and $|\delta_{r+1}|=3$. Also $a_{i-1}=a_{i}$,
$b_{i-1}=b_{i}$, and $c_{i-1}=c_{i}+1$. Hence

$\sum_{j=1}^{r+1}|\delta_{j}|=3+\sum_{j=1}^{r}|\gamma_{r}|\leq
a_{i-1}+2b_{i-1}+3c_{i-1}.$

In each case the sum of the lengths of the cycles in $E_{i-1}$ is bounded
above by $a_{i-1}+2b_{i-1}+3c_{i-1}$. This proves the claim.

In particular the sum $L$ of the lengths of the cycles in $E_{0}$ satisfies

$L\leq a_{0}+2b_{0}+3c_{0}=2m+3.$

Hence each cycle in the non-empty set $E_{0}$ has length at most $2m+3$.
Therefore, each element of $E_{0}$ is a cycle in the disjoint cycle
decomposition of $\sigma^{-1}\tau$ of odd length $\ell$ where $3\leq\ell\leq
2m+3$. This completes the proof. ∎

We now apply Theorem 5.2 to obtain a lower bound for the Hamming distance of a
permutation array after applying the contraction operation $m$ times.

######  Corollary 5.3.

Let $P\subseteq S_{n}$ be a permutation array with Hamming distance $d$. Let
$m\in\\{1,\ldots,n-1\\}$, and suppose that $P$ has the property that for any
$\sigma,\tau\in P$ the disjoint cycle decomposition of $\sigma^{-1}\tau$ has
no cycle of odd length $\ell\in\\{3,\ldots,2m+1\\}$. Then

  1. (1)

${\rm hd}\big{(}P^{{\footnotesize\sf CT}^{m}}\big{)}\geq d-2m$, and

  2. (2)

if $d>2m$ then $\big{|}P^{{\footnotesize\sf CT}^{m}}\big{|}=|P|$.

###### Proof.

Note that ${\rm hd}(\sigma,\tau)\geq d$ for all distinct $\sigma,\tau\in P$,
so by Theorem 5.2,

${\rm hd}\big{(}\sigma^{{\footnotesize\sf CT}^{m}},\tau^{{\footnotesize\sf
CT}^{m}}\big{)}\geq{\rm hd}(\sigma,\tau)-2m\geq d-2m.$

Since $\sigma$ and $\tau$ are arbitrary, it follows that ${\rm
hd}(P^{{\footnotesize\sf CT}^{m}})\geq d-2m$. If $d-2m>0$ then ${\rm
hd}\big{(}\sigma^{{\footnotesize\sf CT}^{m}},\tau^{{\footnotesize\sf
CT}^{m}}\big{)}>0$ for all distinct $\sigma,\tau\in P$. Hence
$\sigma^{{\footnotesize\sf CT}^{m}}\neq\tau^{{\footnotesize\sf CT}^{m}}$ for
all distinct $\sigma,\tau\in P$, and therefore $\big{|}P^{{\footnotesize\sf
CT}^{m}}\big{|}=|P|$. This completes the proof. ∎

The remaining results arise from the special cases where $P$ is one of the
groups ${\rm AGL}(1,q)$, ${\rm PGL}(2,q)$, ${\rm A\Gamma L}(1,q)$, or ${\rm
P\Gamma L}(2,q)$. They are generalizations of [1, Theorem 4 and Corollaries 1,
3, and 4] for multiple contractions.

######  Corollary 5.4.

Let $q$ be a prime power and $m$ a positive integer such that $q>2m+1$ and
$q\not\equiv 0,1\allowbreak\mkern 10.0mu({\operator@font mod}\,\,2i+1)$ for
any $i\in\\{1,\ldots,m\\}$. Then $M(q-m,q-2m-1)\geq q(q-1)$.

###### Proof.

The hypothesis implies that $|{\rm AGL}(1,q)|=q(q-1)$ has no odd divisor
between $3$ and $2m+1$. Hence, for any distinct $\sigma,\tau\in{\rm
AGL}(1,q)$, $\big{|}\sigma^{-1}\tau\big{|}$ has no odd divisor between $3$ and
$2m+1$. It follows that $\sigma^{-1}\tau$ has no cycle of odd length between
$3$ and $2m+1$ in its disjoint cycle decomposition. By [8, Theorem 1 (ii)] we
have ${\rm hd}({\rm AGL}(1,q))\geq q-1$, so by Corollary 5.3.1 we have ${\rm
hd}\big{(}{\rm AGL}(1,q)^{{\footnotesize\sf CT}^{m}}\big{)}\geq q-1-2m$. In
addition, since $q>2m+1$, we get from Corollary 5.3.2 that $\big{|}{\rm
AGL}(1,q)^{{\footnotesize\sf CT}^{m}}\big{|}=|{\rm AGL}(1,q)|=q(q-1)$. Note
that ${\rm AGL}(1,q)^{{\footnotesize\sf CT}^{m}}\subseteq S_{q-m}$. The result
follows immediately. ∎

######  Corollary 5.5.

Let $q$ be a prime power such that $q>5$, $q\equiv 2\allowbreak\mkern
10.0mu({\operator@font mod}\,\,3)$, and $q\not\equiv 0,1\allowbreak\mkern
10.0mu({\operator@font mod}\,\,5)$. Then $M(q-1,q-5)\geq q(q-1)(q+1)$ and
$M(q-2,q-5)\geq q(q+1)$.

###### Proof.

Since ${\rm PGL}(2,q)$ has a sharply $3$-transitive action on a set of $q+1$
elements, it follows from [8, Theorem 1 (iii)] that ${\rm hd}({\rm
PGL}(2,q))\geq(q+1)-3+1=q-1$.

Let $\sigma,\tau$ be distinct elements of ${\rm PGL}(2,q)$. If ${\rm
hd}(\sigma,\tau)=q+1$, then by Lemma 2.2.1 we have

${\rm hd}\big{(}\sigma^{{\footnotesize\sf CT}^{2}},\tau^{{\footnotesize\sf
CT}^{2}}\big{)}\geq[(q+1)-3]-3=q-5.$

Suppose ${\rm hd}(\sigma,\tau)\neq q+1$. Then ${\rm hd}(\sigma,\tau)\geq{\rm
hd}({\rm PGL}(2,q))=q-1$. Also, since ${\rm PGL}(2,q)\subset S_{q+1}$ and
${\rm hd}(\sigma,\tau)\neq q+1$, $\sigma$ and $\tau$ must fix a common point
$x$ and $\sigma^{-1}\tau$ is in the stabilizer of $x$ in ${\rm PGL}(2,q)$. Any
point stabilizer in ${\rm PGL}(2,q)$ is isomorphic to ${\rm AGL}(1,q)$. It
follows from the hypotheses that $|{\rm AGL}(1,q)|=q(q-1)$ is not divisible by
$3$ or $5$, so the disjoint cycle decomposition of $\sigma^{-1}\tau$ has no
factor of length $3$ or $5$. Applying Theorem 5.2 we obtain

${\rm hd}\big{(}\sigma^{{\footnotesize\sf CT}^{2}},\tau^{{\footnotesize\sf
CT}^{2}}\big{)}\geq q-1-2\cdot 2=q-5.$

Finally, since $q-5>0$, we have $\big{|}{\rm PGL}(2,q)^{{\footnotesize\sf
CT}^{2}}\big{|}=|{\rm PGL}(2,q)|=q(q-1)(q+1)$ by Corollary 5.3.2. This proves
that $M(q-1,q-5)\geq q(q-1)(q+1)$.

Since $M(n,d)\leq nM(n-1,d)$ [5], it follows that $M(q-2,q-5)\geq
M(q-1,q-5)/(q-1)\geq q(q+1)$. ∎

Corollary 5.5 also follows from [1, Theorem 3(b)]. Observe that the lower
bound $q(q+1)$ for $M(q-2,q-5)$ is slightly better than the lower bound
$q(q-1)$ in [1, Corollary 4(ii)]. Note though that the proof of Corollary 5.5
does not extend to $m>3$ contractions, for then $q+1-3m<q-1-2m$.

The following corollary is proven in a manner similar to Corollaries 5.4 and
5.5. It is obtained from the application of multiple contractions to ${\rm
A\Gamma L}(1,q)$ and ${\rm P\Gamma L}(2,q)$, whose sizes are $kq(q-1)$ and
$kq(q-1)(q+1)$, respectively. The Hamming distances of the permutation arrays
from these groups are $q-p^{k^{*}}$, where $k^{*}$ is the largest proper
divisor of $k$ [1, Theorems 1 and 2].

######  Corollary 5.6.

Let $q=p^{k}$ with $p$ prime and $k\geq 2$, and let $k^{*}$ be the largest
proper divisor of $k$. Let $m$ be a positive integer such that
$q-p^{k^{*}}-2m>0$ and $kq(q-1)\not\equiv 0\allowbreak\mkern
10.0mu({\operator@font mod}\,\,2i+1)$ for any $i\in\\{1,\ldots,m\\}$. The
following statements hold.

  1. (1)

$M(q-m,q-p^{k^{*}}-2m)\geq kq(q-1)$.

  2. (2)

$M(q+1-m,q-p^{k^{*}}-2m)\geq kq(q-1)(q+1)$, if $q+1-3m\geq q-p^{k^{*}}-2m$.

We remark that Theorem 5.2 cannot be applied to the sporadic multiply-
transitive Mathieu groups $M(11)$, $M(12)$, $M(22)$, $M(23)$, and $M(24)$
because each of their orders is divisible by 3.

##  6\. Analysis of Lower Bounds Obtained After Multiple Contractions

We now inspect the lower bounds that we obtained in Section 5. Known lower
bounds can be found from tables and formulae in [5, 11, 1, 2]. Unfortunately,
the lower bounds for $M(q-m,q-2m-1)$ obtained from Corollary 5.4 were not
competitive with known lower bounds. Similarly, lower bounds for
$M(q-m,q-p^{k^{*}}-2m)$ and $M(q+1-m,q-p^{k^{*}}-2m)$ obtained from Corollary
5.6 were not better than the lower bounds in [2] or [5].

Nevertheless, we obtain new lower bounds for $M(q-1,q-5)$ for suitable prime
powers $q\leq 149$ (Table 6). If a lower bound for $M(q-1,q-5)$ is not present
in the literature, we compared our obtained lower bound instead with known
lower bounds for $M(q,q-5)/q$ (see [5]). The largest comparable lower bound is
included in Table 6. Lower bounds in bold are improvements of lower bounds
found in the literature.

The lower bounds in Table 6 were verified by applying two contractions to the
corresponding projective general linear groups via GAP 4.11.1. The permutation
representations of these groups were obtained through GAP’s “FinInG” package
and the Hamming distances were obtained through the GAP command
“DistancePerms()”. Moreover, the contraction of a permutation $\sigma$ was
accomplished in GAP by multiplying $\sigma$ by the cycle $(n-1,\sigma(n-1))$
from the right.

$q$ $M(q-1,q-5)$ Obtained Lower Bound Previous Lower Bound Reference for
Previous Lower Bound 8 $M(7,3)$ 504 2520 [5, Proposition 1.1] 17 $M(16,12)$
4896 40320 [11, Table 3] 23 $M(22,18)$ 12144 13680 [1, Table 2] 29 $M(28,24)$
24360 58968 [1, Corollary 3] 32 $M(31,27)$ 32736 $43400\leq M(32,27)/32$ [2,
Table 3] 47 $M(46,42)$ 103776 $103822\leq M(47,42)/47$ [2, Table 3] 53
$M(52,48)$ 148824 $148828\leq M(53,48)/53$ [2, Table 3] 59 $M(58,54)$ 205320
$102834\leq M(59,54)/59$ [2, Table 3] 83 $M(82,78)$ 571704 $576605\leq
M(83,78)/83$ [2, Table 3] 89 $M(88,84)$ 704880 $352704\leq M(89,84)/89$ [2,
Table 3] 107 $M(106,102)$ 1224936 $1213592\leq M(107,102)/107$ [2, Table 3]
113 $M(112,108)$ 1442784 $1430128\leq M(113,108)/113$ [2, Table 3] 128
$M(127,123)$ 2097024 $1032510\leq M(128,123)/128$ [2, Table 3] 137
$M(136,132)$ 2571216 $2552584\leq M(137,132)/137$ [2, Table 3] 149
$M(148,144)$ 3307800 $1632144\leq M(149,144)/149$ [2, Table 3]

Table 6. Lower bounds for $M(n,d)$ by two contractions of ${\rm PGL}(2,q)$

## Acknowledgements

The authors thank Dr. I.H. Sudborough for suggesting this problem on the
Hamming distances of multiply contracted permutation arrays.

## References

  * [1] Sergey Bereg, Avi Levy, and I. Hal Sudborough, _Constructing permutation arrays from groups_ , Des. Codes Cryptogr. 86 (2018), no. 5, 1095–1111.
  * [2] Sergey Bereg, Brian Malouf, Linda Morales, Thomas Stanley, and I. Hal Sudborough, _Improved lower bounds for permutation arrays using permutation rational functions_ , Arithmetic of finite fields, Lecture Notes in Comput. Sci., vol. 12542, Springer, Cham, [2021] ©2021, pp. 234–252.
  * [3] Sergey Bereg, Zevi Miller, Luis Gerardo Mojica, Linda Morales, and I. H. Sudborough, _New lower bounds for permutation arrays using contraction_ , Des. Codes Cryptogr. 87 (2019), no. 9, 2105–2128.
  * [4] Sergey Bereg, Linda Morales, and I. Hal Sudborough, _Extending permutation arrays: improving MOLS bounds_ , Des. Codes Cryptogr. 83 (2017), no. 3, 661–683.
  * [5] Wensong Chu, Charles J. Colbourn, and Peter Dukes, _Constructions for permutation codes in powerline communications_ , Des. Codes Cryptogr. 32 (2004), no. 1-3, 51–64.
  * [6] M. Deza and S. A. Vanstone, _Bounds for permutation arrays_ , J. Statist. Plann. Inference 2 (1978), no. 2, 197–209.
  * [7] John D Dixon and Brian Mortimer, _Permutation groups_ , vol. 163, Springer Science & Business Media, 1996.
  * [8] Péter Frankl and Mikhail Deza, _On the maximum number of permutations with given maximal or minimal distance_ , J. Combinatorial Theory Ser. A 22 (1977), no. 3, 352–360.
  * [9] Ingo Janiszczak, Wolfgang Lempken, Patric R. J. Östergård, and Reiner Staszewski, _Permutation codes invariant under isometries_ , Des. Codes Cryptogr. 75 (2015), no. 3, 497–507.
  * [10] Giacomo Micheli and Alessandro Neri, _New lower bounds for permutation codes using linear block codes_ , IEEE Trans. Inform. Theory 66 (2020), no. 7, 4019–4025.
  * [11] Derek H. Smith and Roberto Montemanni, _A new table of permutation codes_ , Des. Codes Cryptogr. 63 (2012), no. 2, 241–253.
  * [12] Katrin Tent, _Sharply 3-transitive groups_ , Adv. Math. 286 (2016), 722–728.